From f593e22ddeb516e91044b2452767fec4ea95f167 Mon Sep 17 00:00:00 2001 From: Tyge Date: Thu, 30 Apr 2020 15:58:46 +0200 Subject: Refactored: made hashx into its own array (8 bit from 16 bit), instead of part of the bucket. Good speed increase and lower memory usage. --- stc/cmap.h | 96 ++++++++++++++++++++++++++++++++++---------------------------- 1 file changed, 53 insertions(+), 43 deletions(-) diff --git a/stc/cmap.h b/stc/cmap.h index 0ab8cb48..d0b058e2 100644 --- a/stc/cmap.h +++ b/stc/cmap.h @@ -23,15 +23,15 @@ #ifndef CMAP__H__ #define CMAP__H__ -#include "cvector.h" +#include "cdefs.h" -#define cmap_init {cvector_init, 0, 0, 90, 0} +#define cmap_init {NULL, NULL, 0, 0, 90, 0} #define cmap_size(map) ((size_t) (map)._size) #define cmap_bucketCount(map) ((size_t) (map)._cap) /* https://lemire.me/blog/2016/06/27/a-fast-alternative-to-the-modulo-reduction */ #define cmap_reduce(x, N) ((uint32_t) (((uint64_t) (x) * (N)) >> 32)) -enum {cmapentry_HASH=0x7fff, cmapentry_USED=0x8000}; +enum {cmapentry_HASH=0x7f, cmapentry_USED=0x80}; /* CMap: */ #define declare_CMap(...) \ @@ -70,26 +70,22 @@ enum {cmapentry_HASH=0x7fff, cmapentry_USED=0x8000}; struct CMapEntry_##tag { \ Key key; \ Value value; \ - uint16_t hashx; \ }; \ \ static inline struct CMapEntry_##tag cmapentry_##tag##_make(Key key, Value value) { \ - struct CMapEntry_##tag e = {key, value, 0}; \ - return e; \ + struct CMapEntry_##tag e = {key, value}; return e; \ } \ static inline void \ cmapentry_##tag##_destroy(struct CMapEntry_##tag* e) { \ keyDestroy(&e->key); \ valueDestroy(&e->value); \ - e->hashx = 0; \ } \ typedef struct CMapEntry_##tag CMapEntry_##tag; \ -\ - declare_CVector_4(map_##tag, CMapEntry_##tag, cmapentry_##tag##_destroy, c_noCompare); \ typedef RawKey cmap_##tag##_rawkey_t; \ \ typedef struct CMap_##tag { \ - CVector_map_##tag _table; \ + CMapEntry_##tag* _table; \ + uint8_t* _hashx; \ uint32_t _size, _cap; \ uint8_t maxLoadPercent; \ uint8_t shrinkLimitPercent; \ @@ -97,6 +93,7 @@ typedef struct CMap_##tag { \ \ typedef struct cmap_##tag##_iter_t { \ CMapEntry_##tag *item, *_end; \ + uint8_t* _hx; \ } cmap_##tag##_iter_t; \ \ STC_API void \ @@ -148,15 +145,17 @@ STC_API void \ cmap_##tag##_destroy(CMap_##tag* self) { \ if (cmap_size(*self)) { \ size_t cap = cmap_bucketCount(*self); \ - CMapEntry_##tag* e = self->_table.data, *end = e + cap; \ - for (; e != end; ++e) if (e->hashx) cmapentry_##tag##_destroy(e); \ + CMapEntry_##tag* e = self->_table, *end = e + cap; \ + uint8_t *hashx = self->_hashx; \ + for (; e != end; ++e) if (*hashx++) cmapentry_##tag##_destroy(e); \ } \ - free(_cvector_alloced(self->_table.data)); \ + free(self->_hashx); \ + free(self->_table); \ } \ \ STC_API void cmap_##tag##_clear(CMap_##tag* self) { \ - memset(self->_table.data, 0, sizeof(CMapEntry_##tag) * cmap_bucketCount(*self)); \ - self->_size = 0; \ + cmap_##tag##_destroy(self); \ + self->_cap = self->_size = 0; \ } \ \ STC_API void \ @@ -178,10 +177,10 @@ cmap_##tag##_bucket(CMap_##tag* self, const cmap_##tag##_rawkey_t* rawKeyPtr, ui uint32_t hash = keyHashRaw(rawKeyPtr, sizeof(cmap_##tag##_rawkey_t)), sx, hx = (hash & cmapentry_HASH) | cmapentry_USED; \ size_t cap = cmap_bucketCount(*self); \ size_t idx = cmap_reduce(hash, cap); \ - CMapEntry_##tag* slot = self->_table.data; \ - while ((sx = slot[idx].hashx)) { \ + uint8_t* hashx = self->_hashx; \ + while ((sx = hashx[idx])) { \ if (sx == hx) { \ - cmap_##tag##_rawkey_t r = keyGetRaw(&slot[idx].key); \ + cmap_##tag##_rawkey_t r = keyGetRaw(&self->_table[idx].key); \ if (keyEqualsRaw(&r, rawKeyPtr)) break; \ } \ if (++idx == cap) idx = 0; \ @@ -195,7 +194,7 @@ cmap_##tag##_get(CMap_##tag map, cmap_##tag##_rawkey_t rawKey) { \ if (cmap_size(map) == 0) return NULL; \ uint32_t hx; \ size_t idx = cmap_##tag##_bucket(&map, &rawKey, &hx); \ - return map._table.data[idx].hashx ? &map._table.data[idx] : NULL; \ + return map._hashx[idx] ? &map._table[idx] : NULL; \ } \ \ STC_API CMapEntry_##tag* \ @@ -204,12 +203,12 @@ cmap_##tag##_put(CMap_##tag* self, cmap_##tag##_rawkey_t rawKey, Value value) { cmap_##tag##_reserve(self, (size_t) 7 + (1.6 * cmap_bucketCount(*self))); \ uint32_t hx; \ size_t idx = cmap_##tag##_bucket(self, &rawKey, &hx); \ - CMapEntry_##tag* e = &self->_table.data[idx]; \ - if (e->hashx) \ + CMapEntry_##tag* e = &self->_table[idx]; \ + if (self->_hashx[idx]) \ valueDestroy(&e->value); \ else { \ e->key = keyInitRaw(rawKey); \ - e->hashx = hx; \ + self->_hashx[idx] = (uint8_t) hx; \ ++self->_size; \ } \ e->value = value; \ @@ -223,12 +222,12 @@ cmap_##tag##_insert(CMap_##tag* self, CMapEntry_##tag entry) { \ uint32_t hx; \ cmap_##tag##_rawkey_t r = keyGetRaw(&entry.key); \ size_t idx = cmap_##tag##_bucket(self, &r, &hx); \ - CMapEntry_##tag* e = &self->_table.data[idx]; \ - if (e->hashx) \ + CMapEntry_##tag* e = &self->_table[idx]; \ + if (self->_hashx[idx]) \ valueDestroy(&e->value); \ else { \ e->key = entry.key; \ - e->hashx = hx; \ + self->_hashx[idx] = (uint8_t) hx; \ ++self->_size; \ } \ e->value = entry.value; \ @@ -244,18 +243,26 @@ STC_API size_t \ cmap_##tag##_reserve(CMap_##tag* self, size_t size) { \ size_t oldcap = cmap_bucketCount(*self), newcap = 1 + (size / 2) * 2; \ if (cmap_size(*self) >= newcap * self->maxLoadPercent * 0.01) return oldcap; \ - CVector_map_##tag vec = cvector_init; \ - cvector_map_##tag##_reserve(&vec, (self->_cap = newcap)); \ - memset(vec.data, 0, sizeof(CMapEntry_##tag) * newcap); \ - cvector_map_##tag##_swap(&self->_table, &vec); \ + CMap_##tag tmp = { \ + c_new_2(CMapEntry_##tag, newcap), \ + (uint8_t *) calloc(newcap, sizeof(uint8_t)), \ + self->_size, (uint32_t) newcap, \ + self->maxLoadPercent, self->shrinkLimitPercent \ + }; \ + cmap_##tag##_swap(self, &tmp); \ \ - CMapEntry_##tag* e = vec.data, *slot = self->_table.data; \ + CMapEntry_##tag* e = tmp._table, *slot = self->_table; \ + uint8_t* hashx = self->_hashx; \ uint32_t hx; \ - cmap_##tag##_rawkey_t r; \ for (size_t i = 0; i < oldcap; ++i, ++e) \ - if (e->hashx) \ - slot[ cmap_##tag##_bucket(self, (r = keyGetRaw(&e->key), &r), &hx) ] = *e; \ - free(_cvector_alloced(vec.data)); /* not cvector_destroy() here */ \ + if (tmp._hashx[i]) { \ + cmap_##tag##_rawkey_t r = keyGetRaw(&e->key); \ + size_t idx = cmap_##tag##_bucket(self, &r, &hx); \ + slot[idx] = *e, \ + hashx[idx] = (uint8_t) hx; \ + } \ + free(tmp._hashx); \ + free(tmp._table); \ return newcap; \ } \ \ @@ -268,34 +275,37 @@ cmap_##tag##_erase(CMap_##tag* self, cmap_##tag##_rawkey_t rawKey) { \ cap = cmap_##tag##_reserve(self, cmap_size(*self) * 120 / self->maxLoadPercent); \ uint32_t hx; \ size_t i = cmap_##tag##_bucket(self, &rawKey, &hx), j = i, k; \ - CMapEntry_##tag* slot = self->_table.data; \ - if (! slot[i].hashx) \ + CMapEntry_##tag* slot = self->_table; \ + uint8_t* hashx = self->_hashx; \ + if (! hashx[i]) \ return false; \ cmap_##tag##_rawkey_t r; \ do { /* deletion from hash table without tombstone */ \ if (++j == cap) j = 0; /* ++j %= cap; is slow */ \ - if (! slot[j].hashx) \ + if (! hashx[j]) \ break; \ k = cmap_reduce(keyHashRaw((r = keyGetRaw(&slot[j].key), &r), \ sizeof(cmap_##tag##_rawkey_t)), cap); \ if ((j < i) ^ (k <= i) ^ (k > j)) /* is k outside (i, j]? */ \ - slot[i] = slot[j], i = j; \ + slot[i] = slot[j], hashx[i] = hashx[j], i = j; \ } while (true); \ - cmapentry_##tag##_destroy(&slot[i]); /* sets used=false */ \ + hashx[i] = 0; \ + cmapentry_##tag##_destroy(&slot[i]); \ --self->_size; \ return true; \ } \ \ STC_API cmap_##tag##_iter_t \ cmap_##tag##_begin(CMap_##tag* map) { \ - CMapEntry_##tag* e = map->_table.data, *end = e + cmap_bucketCount(*map); \ - while (e != end && !e->hashx) ++e; \ - cmap_##tag##_iter_t it = {e == end ? NULL : e, end}; return it; \ + uint8_t* hx = map->_hashx; \ + CMapEntry_##tag* e = map->_table, *end = e + cmap_bucketCount(*map); \ + while (e != end && !*hx) ++e, ++hx; \ + cmap_##tag##_iter_t it = {e == end ? NULL : e, end, hx}; return it; \ } \ \ STC_API cmap_##tag##_iter_t \ cmap_##tag##_next(cmap_##tag##_iter_t it) { \ - do { ++it.item; } while (it.item != it._end && !it.item->hashx); \ + do { ++it.item, ++it._hx; } while (it.item != it._end && !*it._hx); \ if (it.item == it._end) it.item = NULL; \ return it; \ } -- cgit v1.2.3