From 0e9d2ae98db4909913dfb9ae22f5606aae66b10d Mon Sep 17 00:00:00 2001 From: Tyge Løvset <60263450+tylo-work@users.noreply.github.com> Date: Mon, 16 Mar 2020 02:08:43 +0100 Subject: Fixed map, vector No longer using tombstones, erase cleans up properly. --- clib/cmap.h | 111 +++++++++++++++++++++++++-------------------------------- clib/cvector.h | 4 +-- 2 files changed, 51 insertions(+), 64 deletions(-) diff --git a/clib/cmap.h b/clib/cmap.h index a9813ca8..1c7f1d1b 100644 --- a/clib/cmap.h +++ b/clib/cmap.h @@ -25,27 +25,23 @@ #include "cvector.h" -#define cmap_initializer {cvector_initializer, 0, 0, 0.8f} +#define cmap_initializer {cvector_initializer, 0, 0.8f} #define cmap_size(map) ((size_t) (map)._size) #define cmap_buckets(map) cvector_capacity((map)._vec) // CMapEntry: -enum { CMapEntry_VACANT = 0, - CMapEntry_INUSE = 1, - CMapEntry_TOMBSTONE = 2 -}; #define declare_CMapEntry(tag, Key, Value, valueDestroy, keyDestroy) \ struct CMapEntry_##tag { \ Key key; \ Value value; \ - uint8_t state, changed; \ + uint8_t used, changed; \ }; \ \ static inline void cmapentry_##tag##_destroy(struct CMapEntry_##tag* e) { \ keyDestroy(&e->key); \ valueDestroy(&e->value); \ - e->state = CMapEntry_VACANT; \ + e->used = 0; \ } \ typedef struct CMapEntry_##tag CMapEntry_##tag @@ -82,7 +78,7 @@ typedef struct CMapEntry_##tag CMapEntry_##tag \ typedef struct CMap_##tag { \ CVector_map_##tag _vec; \ - size_t _size, _occupied; \ + size_t _size; \ float maxLoadFactor; \ } CMap_##tag; \ \ @@ -99,7 +95,7 @@ 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; \ - for (; e != end; ++e) if (e->state == CMapEntry_INUSE) cmapentry_##tag##_destroy(e); \ + for (; e != end; ++e) if (e->used) cmapentry_##tag##_destroy(e); \ } \ cvector_map_##tag##_destroy(&self->_vec); \ } \ @@ -117,7 +113,7 @@ static inline void cmap_##tag##_swap(CMap_##tag* a, CMap_##tag* b) { \ c_swap(size_t, a->_size, b->_size); \ } \ \ -static inline void cmap_##tag##_setmaxLoadFactor(CMap_##tag* self, float fac) { \ +static inline void cmap_##tag##_setMaxLoadFactor(CMap_##tag* self, float fac) { \ self->maxLoadFactor = fac; \ if (cmap_size(*self) > cmap_buckets(*self) * fac) \ cmap_##tag##_reserve(self, 1 + (size_t) (cmap_size(*self) / fac)); \ @@ -125,55 +121,33 @@ static inline void cmap_##tag##_setmaxLoadFactor(CMap_##tag* self, float 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(Key)), cap)/*, first = idx, m = 0*/; \ - do { \ - switch (self->_vec.data[idx].state) { \ - case CMapEntry_VACANT: \ - return erased_idx != cap ? erased_idx : idx; \ - case CMapEntry_INUSE: \ - if (keyCompareRaw(&self->_vec.data[idx].key, &rawKey, sizeof(Key)) != 0) \ - break; \ - if (erased_idx != cap) { \ - c_swap(CMapEntry_##tag, self->_vec.data[erased_idx], self->_vec.data[idx]); \ - return erased_idx; \ - } \ - return idx; \ - case CMapEntry_TOMBSTONE: \ - if (erased_idx == cap) erased_idx = idx; \ - break; \ - } \ - /*++m; if ((idx = first + m*m) >= cap) 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) \ if (++idx == cap) idx = 0; \ - } while (1); \ + 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].state == CMapEntry_INUSE ? &map._vec.data[idx] : NULL; \ + return map._vec.data[idx].used ? &map._vec.data[idx] : NULL; \ } \ \ static inline CMapEntry_##tag* cmap_##tag##_put(CMap_##tag* self, KeyRaw rawKey, Value value) { \ size_t cap = cvector_capacity(self->_vec); \ if (cmap_size(*self) >= cap * self->maxLoadFactor) \ - cap = cmap_##tag##_reserve(self, (size_t) 7 + (cap * 1.8)); \ - else if (self->_occupied >= 1.3 * cmap_size(*self)) \ - cap = cmap_##tag##_reserve(self, 1.4 * cmap_size(*self) / self->maxLoadFactor); \ + cap = cmap_##tag##_reserve(self, (size_t) 7 + (cap * 1.7)); \ size_t idx = cmap_##tag##_bucket(self, rawKey); \ CMapEntry_##tag* e = &self->_vec.data[idx]; \ - e->value = value; \ - switch (e->state) { \ - case CMapEntry_INUSE: \ - e->changed = true; \ - return e; \ - case CMapEntry_VACANT: \ - ++self->_occupied; \ - case CMapEntry_TOMBSTONE: \ - ++self->_size; \ - e->key = keyInitRaw(rawKey); \ - e->state = CMapEntry_INUSE; \ - default: return e; \ + if (e->used) \ + e->changed = 1; \ + else { \ + e->key = keyInitRaw(rawKey); \ + e->used = 1; \ + ++self->_size; \ } \ + e->value = value; \ + return e; \ } \ \ static inline size_t cmap_##tag##_reserve(CMap_##tag* self, size_t size) { \ @@ -183,38 +157,51 @@ static inline size_t cmap_##tag##_reserve(CMap_##tag* self, size_t size) { \ cvector_map_##tag##_reserve(&vec, newcap); \ memset(vec.data, 0, sizeof(CMapEntry_##tag) * newcap); \ cvector_map_##tag##_swap(&self->_vec, &vec); \ - CMapEntry_##tag* e = vec.data, *dst = self->_vec.data; \ + \ + CMapEntry_##tag* e = vec.data, *slot = self->_vec.data; \ for (size_t i = 0; i < oldcap; ++i, ++e) \ - if (e->state == CMapEntry_INUSE) \ - dst[ cmap_##tag##_bucket(self, keyGetRaw(e->key)) ] = *e; \ - self->_occupied = self->_size; \ - free(_cvector_alloced(vec.data)); /* not cvector_destroy here */ \ + if (e->used) \ + slot[ cmap_##tag##_bucket(self, keyGetRaw(e->key)) ] = *e; \ + free(_cvector_alloced(vec.data)); /* not cvector_destroy() here */ \ return newcap; \ } \ \ static inline bool cmap_##tag##_erase(CMap_##tag* self, KeyRaw rawKey) { \ - if (!self->_size) return false; \ - size_t idx = cmap_##tag##_bucket(self, rawKey); \ - CMapEntry_##tag* e = &self->_vec.data[idx]; \ - if (e->state == CMapEntry_INUSE) { \ - cmapentry_##tag##_destroy(e); \ - e->state = CMapEntry_TOMBSTONE; \ - --self->_size; \ - return true; \ - } \ - return false; \ + if (cmap_size(*self) == 0) \ + return false; \ + size_t i = cmap_##tag##_bucket(self, rawKey), k; \ + CMapEntry_##tag* slot = self->_vec.data; \ + if (! slot[i].used) \ + return false; \ + size_t cap = cvector_capacity(self->_vec), j = i; \ + do { \ + if (++j == cap) j = 0; \ + if (! slot[j].used) \ + break; \ + KeyRaw r = keyGetRaw(slot[j].key); \ + k = c_reduce(keyHashRaw(&r, sizeof(KeyRaw)), cap); \ + /* https://attractivechaos.wordpress.com/2019/12/28/deletion-from-hash-tables-without-tombstones/ \ + if (j > i && (k <= i || k > j) || \ + j < i && (k <= i && k > j))*/ \ + if ((j < i) ^ (k <= i) ^ (k > j)) /* simplified */ \ + slot[i] = slot[j], i = j; \ + } while (true); \ + cmapentry_##tag##_destroy(&slot[i]); \ + slot[i].used = 0; \ + --self->_size; \ + return true; \ } \ \ 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); \ - while (e != end && e->state != CMapEntry_INUSE) ++e; \ + while (e != end && !e->used) ++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->state != CMapEntry_INUSE); \ + do { ++it.item; } while (it.item != it._end && !it.item->used); \ return it; \ } \ \ diff --git a/clib/cvector.h b/clib/cvector.h index 15c58d27..3e6208c1 100644 --- a/clib/cvector.h +++ b/clib/cvector.h @@ -69,8 +69,8 @@ static inline void cvector_##tag##_destroy(CVector_##tag* self) { \ } \ \ static inline void cvector_##tag##_reserve(CVector_##tag* self, size_t cap) { \ - if (cap > cvector_capacity(*self)) { \ - size_t len = cvector_size(*self); \ + size_t len = cvector_size(*self); \ + if (cap >= len) { \ size_t* rep = (size_t *) realloc(_cvector_alloced(self->data), 2 * sizeof(size_t) + cap * sizeof(Value)); \ self->data = (Value *) (rep + 2); \ rep[0] = len; \ -- cgit v1.2.3