Added hash stored in table

1 files changed, 37 insertions, 29 deletions

diff --git a/c_lib/cmap.h b/c_lib/cmap.h
index 2b23a37c..218ef0e3 100644
--- a/c_lib/cmap.h
+++ b/c_lib/cmap.h
@@ -27,15 +27,17 @@
 

 #define cmap_initializer   {cvector_initializer, 0, 0.9f}

 #define cmap_size(map)     ((size_t) (map)._size)

-#define cmap_buckets(map)  cvector_capacity((map)._vec)

+#define cmap_buckets(map)  cvector_capacity((map)._table)

 

 

 // CMapEntry:

 #define declare_CMapEntry(tag, Key, Value, valueDestroy, keyDestroy) \

 struct CMapEntry_##tag { \

+    uint16_t used; \

+    uint16_t changed; \

+    uint32_t hash; \

     Key key; \

     Value value; \

-    uint8_t used, changed; \

 }; \

  \

 static inline void cmapentry_##tag##_destroy(struct CMapEntry_##tag* e) { \

@@ -77,7 +79,7 @@ typedef struct CMapEntry_##tag CMapEntry_##tag
   declare_CVector_3(map_##tag, CMapEntry_##tag, cmapentry_##tag##_destroy); \

  \

 typedef struct CMap_##tag { \

-    CVector_map_##tag _vec; \

+    CVector_map_##tag _table; \

     size_t _size; \

     float maxLoadFactor; \

 } CMap_##tag; \

@@ -93,11 +95,11 @@ static inline CMap_##tag cmap_##tag##_init(void) { \
  \

 static inline void cmap_##tag##_destroy(CMap_##tag* self) { \

     if (cmap_size(*self)) { \

-        size_t cap = _cvector_capacity(self->_vec); \

-        CMapEntry_##tag* e = self->_vec.data, *end = e + cap; \

+        size_t cap = _cvector_capacity(self->_table); \

+        CMapEntry_##tag* e = self->_table.data, *end = e + cap; \

         for (; e != end; ++e) if (e->used) cmapentry_##tag##_destroy(e); \

     } \

-    cvector_map_##tag##_destroy(&self->_vec); \

+    cvector_map_##tag##_destroy(&self->_table); \

 } \

  \

 static inline size_t cmap_##tag##_reserve(CMap_##tag* self, size_t size); /* predeclared */ \

@@ -109,42 +111,47 @@ static inline void cmap_##tag##_clear(CMap_##tag* self) { \
 } \

  \

 static inline void cmap_##tag##_swap(CMap_##tag* a, CMap_##tag* b) { \

-    cvector_map_##tag##_swap(&a->_vec, &b->_vec); \

+    cvector_map_##tag##_swap(&a->_table, &b->_table); \

     c_swap(size_t, a->_size, b->_size); \

 } \

  \

 static inline void cmap_##tag##_setMaxLoadFactor(CMap_##tag* self, float fac) { \

     self->maxLoadFactor = fac; \

-    if (cmap_size(*self) > cmap_buckets(*self) * fac) \

+    if (cmap_size(*self) >= cmap_buckets(*self) * fac) \

         cmap_##tag##_reserve(self, 1 + (size_t) (cmap_size(*self) / fac)); \

 } \

  \

-static inline size_t cmap_##tag##_bucket(CMap_##tag* self, KeyRaw rawKey) { \

-    size_t cap = cvector_capacity(self->_vec), erased_idx = cap; \

-    size_t idx = c_reduce(keyHashRaw(&rawKey, sizeof(KeyRaw)), cap); \

-    while (self->_vec.data[idx].used && keyCompareRaw(&self->_vec.data[idx].key, &rawKey, sizeof(Key)) != 0) {\

+static inline size_t cmap_##tag##_bucket(CMap_##tag* self, KeyRaw rawKey, uint32_t* h) { \

+    uint32_t hash = keyHashRaw(&rawKey, sizeof(KeyRaw)); \

+    size_t cap = cvector_capacity(self->_table); \

+    size_t idx = c_reduce(hash, cap); \

+    while (self->_table.data[idx].used && (self->_table.data[idx].hash != hash || keyCompareRaw(&self->_table.data[idx].key, &rawKey, sizeof(Key)) != 0)) {\

         if (++idx == cap) idx = 0; \

     } \

+    *h = hash; \

     return idx; \

 } \

  \

 static inline CMapEntry_##tag* cmap_##tag##_get(CMap_##tag map, KeyRaw rawKey) { \

     if (cmap_size(map) == 0) return NULL; \

-    size_t idx = cmap_##tag##_bucket(&map, rawKey); \

-    return map._vec.data[idx].used ? &map._vec.data[idx] : NULL; \

+    uint32_t h; \

+    size_t idx = cmap_##tag##_bucket(&map, rawKey, &h); \

+    return map._table.data[idx].used ? &map._table.data[idx] : NULL; \

 } \

  \

 static inline CMapEntry_##tag* cmap_##tag##_put(CMap_##tag* self, KeyRaw rawKey, Value value) { \

-    size_t cap = cvector_capacity(self->_vec); \

+    size_t cap = cvector_capacity(self->_table); \

     if (cmap_size(*self) + 1 >= cap * self->maxLoadFactor) \

         cap = cmap_##tag##_reserve(self, (size_t) 7 + (1.6 * cap)); \

-    size_t idx = cmap_##tag##_bucket(self, rawKey); \

-    CMapEntry_##tag* e = &self->_vec.data[idx]; \

+    uint32_t h; \

+    size_t idx = cmap_##tag##_bucket(self, rawKey, &h); \

+    CMapEntry_##tag* e = &self->_table.data[idx]; \

     if (e->used) \

         e->changed = true; \

     else { \

         e->key = keyInitRaw(rawKey); \

         e->used = true; \

+        e->hash = h; \

         ++self->_size; \

     } \

     e->value = value; \

@@ -152,17 +159,18 @@ static inline CMapEntry_##tag* cmap_##tag##_put(CMap_##tag* self, KeyRaw rawKey,
 } \

  \

 static inline size_t cmap_##tag##_reserve(CMap_##tag* self, size_t size) { \

-    size_t oldcap = cvector_capacity(self->_vec), newcap = 1 + (size / 2) * 2; \

+    size_t oldcap = cvector_capacity(self->_table), newcap = 1 + (size / 2) * 2; \

     if (cmap_size(*self) >= newcap * self->maxLoadFactor) return oldcap; \

     CVector_map_##tag vec = cvector_initializer; \

     cvector_map_##tag##_reserve(&vec, newcap); \

     memset(vec.data, 0, sizeof(CMapEntry_##tag) * newcap); \

-    cvector_map_##tag##_swap(&self->_vec, &vec); \

+    cvector_map_##tag##_swap(&self->_table, &vec); \

  \

-    CMapEntry_##tag* e = vec.data, *slot = self->_vec.data; \

+    CMapEntry_##tag* e = vec.data, *slot = self->_table.data; \

+    uint32_t h; \

     for (size_t i = 0; i < oldcap; ++i, ++e) \

         if (e->used) \

-            slot[ cmap_##tag##_bucket(self, keyGetRaw(e->key)) ] = *e; \

+            slot[ cmap_##tag##_bucket(self, keyGetRaw(e->key), &h) ] = *e; \

     free(_cvector_alloced(vec.data)); /* not cvector_destroy() here */ \

     return newcap; \

 } \

@@ -170,11 +178,12 @@ static inline size_t cmap_##tag##_reserve(CMap_##tag* self, size_t size) { \
 static inline bool cmap_##tag##_erase(CMap_##tag* self, KeyRaw rawKey) { \

     if (cmap_size(*self) == 0) \

         return false; \

-    size_t cap = cvector_capacity(self->_vec); \

+    size_t cap = cvector_capacity(self->_table); \

     if (cmap_size(*self) * 1.6 < cap * self->maxLoadFactor) \

         cap = cmap_##tag##_reserve(self, 1.2 * cmap_size(*self) / self->maxLoadFactor); \

-    size_t i = cmap_##tag##_bucket(self, rawKey), j = i, k; \

-    CMapEntry_##tag* slot = self->_vec.data; \

+    uint32_t h; \

+    size_t i = cmap_##tag##_bucket(self, rawKey, &h), j = i, k; \

+    CMapEntry_##tag* slot = self->_table.data; \

     if (! slot[i].used) \

         return false; \

     do { /* https://attractivechaos.wordpress.com/2019/12/28/deletion-from-hash-tables-without-tombstones/ */ \

@@ -183,11 +192,10 @@ static inline bool cmap_##tag##_erase(CMap_##tag* self, KeyRaw rawKey) { \
             break; \

         KeyRaw r = keyGetRaw(slot[j].key); \

         k = c_reduce(keyHashRaw(&r, sizeof(KeyRaw)), cap); \

-        if ((j < i) ^ (k <= i) ^ (k > j)) /* Check if k is outside [i, j) range */ \

+        if ((j < i) ^ (k <= i) ^ (k > j)) /* is k outside (i, j]? */ \

             slot[i] = slot[j], i = j; \

     } while (true); \

-    cmapentry_##tag##_destroy(&slot[i]); \

-    slot[i].used = false; \

+    cmapentry_##tag##_destroy(&slot[i]); /* sets used=false */ \

     --self->_size; \

     return true; \

 } \

@@ -195,7 +203,7 @@ static inline bool cmap_##tag##_erase(CMap_##tag* self, KeyRaw rawKey) { \
 static inline cmap_##tag##_iter_t cmap_##tag##_begin(CMap_##tag map) { \

     cmap_##tag##_iter_t null = {NULL, NULL}; \

     if (cmap_size(map) == 0) return null; \

-    CMapEntry_##tag* e = map._vec.data, *end = e + _cvector_capacity(map._vec); \

+    CMapEntry_##tag* e = map._table.data, *end = e + _cvector_capacity(map._table); \

     while (e != end && !e->used) ++e; \

     cmap_##tag##_iter_t it = {e, end}; return it; \

 } \

@@ -206,7 +214,7 @@ static inline cmap_##tag##_iter_t cmap_##tag##_next(cmap_##tag##_iter_t it) { \
 } \

  \

 static inline cmap_##tag##_iter_t cmap_##tag##_end(CMap_##tag map) { \

-    CMapEntry_##tag* end = (cmap_size(map) == 0) ? NULL : map._vec.data + _cvector_capacity(map._vec); \

+    CMapEntry_##tag* end = (cmap_size(map) == 0) ? NULL : map._table.data + _cvector_capacity(map._table); \

     cmap_##tag##_iter_t it = {end, end}; \

     return it; \

 } \