From b99931340c7096f9046aa1582e0866a5b29230ec Mon Sep 17 00:00:00 2001
From: Tyge Løvset <60263450+tylo-work@users.noreply.github.com>
Date: Fri, 6 Mar 2020 14:59:06 +0100
Subject: Fixed erase

---
 cmap.h | 55 ++++++++++++++++++++++++++++++++-----------------------
 1 file changed, 32 insertions(+), 23 deletions(-)

diff --git a/cmap.h b/cmap.h
index 66826724..3f5e1c33 100644
--- a/cmap.h
+++ b/cmap.h
@@ -31,17 +31,21 @@
 
 
 // CMapEntry:
+enum { CMapEntry_VACANT = 0, 
+       CMapEntry_INUSE = 1,
+       CMapEntry_REMOVED = 2
+};
 #define declare_CMapEntry(tag, Key, Value, keyDestroy, valueDestroy) \
 struct CMapEntry_##tag { \
     Key key; \
     Value value; \
-    short _used, changed; \
+    uint8_t state, changed; \
 }; \
  \
 static inline void cmapentry_##tag##_destroy(struct CMapEntry_##tag* p) { \
     keyDestroy(&p->key); \
     valueDestroy(&p->value); \
-    p->_used = p->changed = 0; \
+    p->state = CMapEntry_VACANT; \
 } \
 typedef struct CMapEntry_##tag CMapEntry_##tag
 
@@ -89,7 +93,7 @@ static inline void cmap_##tag##_destroy(CMap_##tag* self) { \
     if (self->_size) { \
         size_t cap = _cvector_capacity(self->_vec); \
         CMapEntry_##tag* p = self->_vec.data, *end = p + cap; \
-        for (; p != end; ++p) if (p->_used) cmapentry_##tag##_destroy(p); \
+        for (; p != end; ++p) if (p->state == CMapEntry_INUSE) cmapentry_##tag##_destroy(p); \
     } \
     cvector_map_##tag##_destroy(&self->_vec); \
 } \
@@ -105,50 +109,54 @@ static inline void cmap_##tag##_swap(CMap_##tag* a, CMap_##tag* b) { \
     _cdef_swap(size_t, a->_size, b->_size); \
 } \
  \
-static inline size_t _cmap_##tag##_findIndex(CMap_##tag cm, KeyRaw rawKey) { \
+static inline size_t cmap_##tag##_bucket(CMap_##tag cm, KeyRaw rawKey) { \
     size_t cap = cvector_capacity(cm._vec); \
-    size_t idx = keyHasher(&rawKey, sizeof(Key)) % cap, first = idx; \
+    size_t idx = keyHasher(&rawKey, sizeof(Key)) % cap; \
+    size_t first = idx, found = cap, state = cm._vec.data[idx].state; \
     FIBONACCI_DECL; \
-    while (cm._vec.data[idx]._used && keyCompare(&cm._vec.data[idx].key, &rawKey, sizeof(Key)) != 0) \
-        idx = (first + FIBONACCI_NEXT) % cap; \
-    return idx; \
+    do { \
+        if ((state == CMapEntry_INUSE) && keyCompare(&cm._vec.data[idx].key, &rawKey, sizeof(Key)) == 0) return idx; \
+        if ((state == CMapEntry_REMOVED) && found == cap) found = idx; \
+        state = cm._vec.data[ idx = (first + FIBONACCI_NEXT) % cap ].state; \
+    } while (state != CMapEntry_VACANT); \
+    return found == cap ? idx : found; \
 } \
  \
 static inline CMapEntry_##tag* cmap_##tag##_get(CMap_##tag cm, KeyRaw rawKey) { \
     if (cm._size == 0) return NULL; \
-    size_t idx = _cmap_##tag##_findIndex(cm, rawKey); \
-    return cm._vec.data[idx]._used ? &cm._vec.data[idx] : NULL; \
+    size_t idx = cmap_##tag##_bucket(cm, rawKey); \
+    return cm._vec.data[idx].state == CMapEntry_INUSE ? &cm._vec.data[idx] : NULL; \
 } \
  \
-static inline size_t cmap_##tag##_rehash(CMap_##tag* self); /* predeclared */ \
+static inline size_t cmap_##tag##_reserve(CMap_##tag* self, size_t size); /* predeclared */ \
  \
 static inline CMapEntry_##tag* cmap_##tag##_put(CMap_##tag* self, KeyRaw rawKey, Value value) { \
     size_t cap = cvector_capacity(self->_vec); \
     if (self->_size >= cap * 4 / 5) \
-        cap = cmap_##tag##_rehash(self); \
-    size_t idx = _cmap_##tag##_findIndex(*self, rawKey); \
+        cap = cmap_##tag##_reserve(self, cap * 5 / 3); \
+    size_t idx = cmap_##tag##_bucket(*self, rawKey); \
     CMapEntry_##tag* e = &self->_vec.data[idx]; \
     e->value = value; \
-    e->changed = e->_used; \
-    if (!e->_used) { \
+    e->changed = (e->state == CMapEntry_INUSE); \
+    if (e->state != CMapEntry_INUSE) { \
         e->key = keyInit(rawKey); \
-        e->_used = 1; \
+        e->state = CMapEntry_INUSE; \
         ++self->_size; \
     } \
     return e; \
 } \
  \
-static inline size_t cmap_##tag##_rehash(CMap_##tag* self) { \
+static inline size_t cmap_##tag##_reserve(CMap_##tag* self, size_t size) { \
+    size_t oldcap = cvector_capacity(self->_vec), newcap = (oldcap < 50 ? 7 : 1) + (size / 2) * 2; \
+    if (oldcap >= newcap) return oldcap; \
     CVector_map_##tag vec = cvector_initializer; \
-    size_t newcap = 7 + cmap_capacity(*self) * 5 / 3; \
     cvector_map_##tag##_swap(&self->_vec, &vec); \
     cvector_map_##tag##_reserve(&self->_vec, newcap); \
     self->_size = 0; \
     memset(self->_vec.data, 0, sizeof(CMapEntry_##tag) * newcap); \
     CMapEntry_##tag* p = vec.data; \
-    size_t i, oldcap = cvector_capacity(vec); \
-    for (i = 0; i < oldcap; ++i, ++p) \
-        if (p->_used) cmap_##tag##_put(self, keyGetRaw(p->key), p->value); \
+    for (size_t i = 0; i < oldcap; ++i, ++p) \
+        if (p->state == CMapEntry_INUSE) cmap_##tag##_put(self, keyGetRaw(p->key), p->value); \
     return newcap; \
 } \
  \
@@ -156,6 +164,7 @@ static inline int cmap_##tag##_erase(CMap_##tag* self, KeyRaw rawKey) { \
     CMapEntry_##tag* entryPtr = cmap_##tag##_get(*self, rawKey); \
     if (entryPtr) { \
         cmapentry_##tag##_destroy(entryPtr); \
+        entryPtr->state = CMapEntry_REMOVED; \
         --self->_size; \
         return 1; \
     } \
@@ -166,13 +175,13 @@ static inline cmap_##tag##_iter_t cmap_##tag##_begin(CMap_##tag map) { \
     cmap_##tag##_iter_t null = {NULL, NULL}; \
     if (map._size == 0) return null; \
     CMapEntry_##tag* p = map._vec.data, *end = p + _cvector_capacity(map._vec); \
-    while (p != end && !p->_used) ++p; \
+    while (p != end && p->state != CMapEntry_INUSE) ++p; \
     cmap_##tag##_iter_t it = {p, end}; return it; \
 } \
  \
 static inline cmap_##tag##_iter_t cmap_##tag##_next(cmap_##tag##_iter_t it) { \
     ++it.item; \
-    while (it.item != it._end && !it.item->_used) ++it.item; \
+    while (it.item != it._end && !(it.item->state & CMapEntry_INUSE)) ++it.item; \
     return it; \
 } \
  \
-- 
cgit v1.2.3