From 395a2a460397723fdc5f2cd5ed3c3caba185e515 Mon Sep 17 00:00:00 2001
From: Tyge Løvset <60263450+tylo-work@users.noreply.github.com>
Date: Thu, 19 Mar 2020 16:12:27 +0100
Subject: More compact representation.

---
 c_lib/cmap.h | 52 ++++++++++++++++++++++++----------------------------
 1 file 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; \
 } \
  \
-- 
cgit v1.2.3