More compact representation.

1 files changed, 24 insertions, 28 deletions

diff --git a/c_lib/cmap.h b/c_lib/cmap.h
index c18ed91a..59645a88 100644
--- a/c_lib/cmap.h
+++ b/c_lib/cmap.h
@@ -35,18 +35,17 @@
 struct CMapEntry_##tag { \

     Key key; \

     Value value; \

-    uint8_t changed; \

-    uint8_t used; \

-    uint16_t hash; \

+    uint16_t hashx; \

 }; \

  \

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

     keyDestroy(&e->key); \

     valueDestroy(&e->value); \

-    e->used = false; \

+    e->hashx = 0; \

 } \

 typedef struct CMapEntry_##tag CMapEntry_##tag

 

+enum   {cmapentry_HASH=0x7fff, cmapentry_USED=0x8000};

 #define cmapentry_noCompare(x, y) (0)

 

 

@@ -100,7 +99,7 @@ static inline void cmap_##tag##_destroy(CMap_##tag* self) { \
     if (cmap_size(*self)) { \

         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); \

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

     } \

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

 } \

@@ -124,38 +123,35 @@ static inline void cmap_##tag##_setMaxLoadFactor(CMap_##tag* self, float fac) {
         cmap_##tag##_reserve(self, 1 + (size_t) (cmap_size(*self) / fac)); \

 } \

  \

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

-    uint32_t hash = keyHashRaw(&rawKey, sizeof(KeyRaw)), hx = hash & 0xffff; \

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

+    uint32_t hash = keyHashRaw(&rawKey, sizeof(KeyRaw)), hx = (hash & cmapentry_HASH) | cmapentry_USED; \

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

     size_t idx = c_reduce(hash, cap); \

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

-    while (slot[idx].used && (slot[idx].hash != hx || keyCompareRaw(keyGetRaw(slot[idx].key), rawKey) != 0)) { \

+    while (slot[idx].hashx && (slot[idx].hashx != hx || keyCompareRaw(keyGetRaw(slot[idx].key), rawKey) != 0)) { \

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

     } \

-    *h = hx; \

+    *hxPtr = hx; \

     return idx; \

 } \

  \

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

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

-    uint32_t h; \

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

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

+    uint32_t hx; \

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

+    return map._table.data[idx].hashx ? &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->_table); \

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

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

-    uint32_t h; \

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

+    uint32_t hx; \

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

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

-    if (e->used) \

-        e->changed = true; \

-    else { \

+    if (! e->hashx) { \

         e->key = keyInitRaw(rawKey); \

-        e->used = true; \

-        e->hash = h; \

+        e->hashx = hx; \

         ++self->_size; \

     } \

     e->value = value; \

@@ -171,10 +167,10 @@ static inline size_t cmap_##tag##_reserve(CMap_##tag* self, size_t size) { \
     cvector_map_##tag##_swap(&self->_table, &vec); \

  \

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

-    uint32_t h; \

+    uint32_t hx; \

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

-        if (e->used) \

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

+        if (e->hashx) \

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

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

     return newcap; \

 } \

@@ -185,14 +181,14 @@ static inline bool cmap_##tag##_erase(CMap_##tag* self, KeyRaw rawKey) { \
     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); \

-    uint32_t h; \

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

+    uint32_t hx; \

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

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

-    if (! slot[i].used) \

+    if (! slot[i].hashx) \

         return false; \

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

         if (++j == cap) j = 0; /* j %= cap; is slow */ \

-        if (! slot[j].used) \

+        if (! slot[j].hashx) \

             break; \

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

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

@@ -208,12 +204,12 @@ 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._table.data, *end = e + _cvector_capacity(map._table); \

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

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

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

 } \

  \

 static inline cmap_##tag##_iter_t cmap_##tag##_next(cmap_##tag##_iter_t it) { \

-    do { ++it.item; } while (it.item != it._end && !it.item->used); \

+    do { ++it.item; } while (it.item != it._end && !it.item->hashx); \

     return it; \

 } \

  \