From 3a570f70b2085ea7364d45f31f5513f941e7b062 Mon Sep 17 00:00:00 2001 From: Tyge Løvset <60263450+tylo-work@users.noreply.github.com> Date: Tue, 17 Mar 2020 12:45:49 +0100 Subject: Added hash stored in table --- c_lib/cmap.h | 66 ++++++++++++++++++++++++++++++++++-------------------------- 1 file 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; \ } \ -- cgit v1.2.3