From 1ab90de4931f07ea61b1195de602f282a853568b Mon Sep 17 00:00:00 2001 From: gingerBill Date: Sat, 14 Jan 2023 12:33:42 +0000 Subject: Minimize `StringMap` structure usage --- src/string_map.cpp | 226 +++++++++++++++++++++++++++++------------------------ 1 file changed, 126 insertions(+), 100 deletions(-) (limited to 'src/string_map.cpp') diff --git a/src/string_map.cpp b/src/string_map.cpp index f7ecc4acc..3bd08d09f 100644 --- a/src/string_map.cpp +++ b/src/string_map.cpp @@ -1,3 +1,5 @@ +GB_STATIC_ASSERT(sizeof(MapIndex) == sizeof(u32)); + struct StringHashKey { u32 hash; String string; @@ -9,101 +11,108 @@ struct StringHashKey { return this->string; } }; +gb_internal gb_inline u32 string_hash(String const &s) { + return fnv32a(s.text, s.len) & 0x7fffffff; +} gb_internal gb_inline StringHashKey string_hash_string(String const &s) { StringHashKey hash_key = {}; - hash_key.hash = fnv32a(s.text, s.len); + hash_key.hash = string_hash(s); hash_key.string = s; return hash_key; } - -gb_internal gb_inline bool string_hash_key_equal(StringHashKey const &a, StringHashKey const &b) { - if (a.hash == b.hash) { - // NOTE(bill): If two string's hashes collide, compare the strings themselves - return a.string == b.string; - } - return false; -} - template struct StringMapEntry { - StringHashKey key; + String key; + u32 hash; MapIndex next; T value; }; template struct StringMap { - Slice hashes; - Array > entries; + MapIndex * hashes; + usize hashes_count; + StringMapEntry *entries; + u32 count; + u32 entries_capacity; }; -template gb_internal void string_map_init (StringMap *h, isize capacity = 16); -template gb_internal void string_map_destroy (StringMap *h); +template gb_internal void string_map_init (StringMap *h, usize capacity = 16); +template gb_internal void string_map_destroy (StringMap *h); -template gb_internal T * string_map_get (StringMap *h, char const *key); -template gb_internal T * string_map_get (StringMap *h, String const &key); -template gb_internal T * string_map_get (StringMap *h, StringHashKey const &key); +template gb_internal T * string_map_get (StringMap *h, char const *key); +template gb_internal T * string_map_get (StringMap *h, String const &key); +template gb_internal T * string_map_get (StringMap *h, StringHashKey const &key); -template gb_internal T & string_map_must_get (StringMap *h, char const *key); -template gb_internal T & string_map_must_get (StringMap *h, String const &key); -template gb_internal T & string_map_must_get (StringMap *h, StringHashKey const &key); +template gb_internal T & string_map_must_get(StringMap *h, char const *key); +template gb_internal T & string_map_must_get(StringMap *h, String const &key); +template gb_internal T & string_map_must_get(StringMap *h, StringHashKey const &key); -template gb_internal void string_map_set (StringMap *h, char const *key, T const &value); -template gb_internal void string_map_set (StringMap *h, String const &key, T const &value); -template gb_internal void string_map_set (StringMap *h, StringHashKey const &key, T const &value); +template gb_internal void string_map_set (StringMap *h, char const *key, T const &value); +template gb_internal void string_map_set (StringMap *h, String const &key, T const &value); +template gb_internal void string_map_set (StringMap *h, StringHashKey const &key, T const &value); -// template gb_internal void string_map_remove (StringMap *h, StringHashKey const &key); -template gb_internal void string_map_clear (StringMap *h); -template gb_internal void string_map_grow (StringMap *h); -template gb_internal void string_map_reserve (StringMap *h, isize new_count); +// template gb_internal void string_map_remove (StringMap *h, StringHashKey const &key); +template gb_internal void string_map_clear (StringMap *h); +template gb_internal void string_map_grow (StringMap *h); +template gb_internal void string_map_reserve (StringMap *h, usize new_count); gb_internal gbAllocator string_map_allocator(void) { return heap_allocator(); } template -gb_internal gb_inline void string_map_init(StringMap *h, isize capacity) { +gb_internal gb_inline void string_map_init(StringMap *h, usize capacity) { capacity = next_pow2_isize(capacity); - slice_init(&h->hashes, string_map_allocator(), capacity); - array_init(&h->entries, string_map_allocator(), 0, capacity); - for (isize i = 0; i < capacity; i++) { - h->hashes.data[i] = MAP_SENTINEL; - } + string_map_reserve(h, capacity); } template gb_internal gb_inline void string_map_destroy(StringMap *h) { - if (h->entries.allocator.proc == nullptr) { - h->entries.allocator = string_map_allocator(); - } - slice_free(&h->hashes, h->entries.allocator); - array_free(&h->entries); + gb_free(string_map_allocator(), h->hashes); + gb_free(string_map_allocator(), h->entries); } + +template +gb_internal void string_map__resize_hashes(StringMap *h, usize count) { + h->hashes_count = cast(u32)resize_array_raw(&h->hashes, string_map_allocator(), h->hashes_count, count); +} + + +template +gb_internal void string_map__reserve_entries(StringMap *h, usize capacity) { + h->entries_capacity = cast(u32)resize_array_raw(&h->entries, string_map_allocator(), h->entries_capacity, capacity); +} + + template -gb_internal MapIndex string_map__add_entry(StringMap *h, StringHashKey const &key) { +gb_internal MapIndex string_map__add_entry(StringMap *h, u32 hash, String const &key) { StringMapEntry e = {}; e.key = key; + e.hash = hash; e.next = MAP_SENTINEL; - array_add(&h->entries, e); - return cast(MapIndex)(h->entries.count-1); + string_map__reserve_entries(h, h->count+1); + h->entries[h->count++] = e; + return cast(MapIndex)(h->count-1); } template -gb_internal MapFindResult string_map__find(StringMap *h, StringHashKey const &key) { +gb_internal MapFindResult string_map__find(StringMap *h, u32 hash, String const &key) { MapFindResult fr = {MAP_SENTINEL, MAP_SENTINEL, MAP_SENTINEL}; - if (h->hashes.count != 0) { - fr.hash_index = cast(MapIndex)(key.hash & (h->hashes.count-1)); - fr.entry_index = h->hashes.data[fr.hash_index]; + if (h->hashes_count != 0) { + fr.hash_index = cast(MapIndex)(hash & (h->hashes_count-1)); + fr.entry_index = h->hashes[fr.hash_index]; while (fr.entry_index != MAP_SENTINEL) { - if (string_hash_key_equal(h->entries.data[fr.entry_index].key, key)) { + auto *entry = &h->entries[fr.entry_index]; + if (entry->hash == hash && entry->key == key) { return fr; } fr.entry_prev = fr.entry_index; - fr.entry_index = h->entries.data[fr.entry_index].next; + fr.entry_index = entry->next; } } return fr; @@ -112,15 +121,16 @@ gb_internal MapFindResult string_map__find(StringMap *h, StringHashKey const template gb_internal MapFindResult string_map__find_from_entry(StringMap *h, StringMapEntry *e) { MapFindResult fr = {MAP_SENTINEL, MAP_SENTINEL, MAP_SENTINEL}; - if (h->hashes.count != 0) { - fr.hash_index = cast(MapIndex)(e->key.hash & (h->hashes.count-1)); - fr.entry_index = h->hashes.data[fr.hash_index]; + if (h->hashes_count != 0) { + fr.hash_index = cast(MapIndex)(e->hash & (h->hashes_count-1)); + fr.entry_index = h->hashes[fr.hash_index]; while (fr.entry_index != MAP_SENTINEL) { - if (&h->entries.data[fr.entry_index] == e) { + auto *entry = &h->entries[fr.entry_index]; + if (entry == e) { return fr; } fr.entry_prev = fr.entry_index; - fr.entry_index = h->entries.data[fr.entry_index].next; + fr.entry_index = entry->next; } } return fr; @@ -128,24 +138,24 @@ gb_internal MapFindResult string_map__find_from_entry(StringMap *h, StringMap template gb_internal b32 string_map__full(StringMap *h) { - return 0.75f * h->hashes.count <= h->entries.count; + return 0.75f * h->hashes_count <= h->count; } template gb_inline void string_map_grow(StringMap *h) { - isize new_count = gb_max(h->hashes.count<<1, 16); + isize new_count = gb_max(h->hashes_count<<1, 16); string_map_reserve(h, new_count); } template gb_internal void string_map_reset_entries(StringMap *h) { - for (isize i = 0; i < h->hashes.count; i++) { - h->hashes.data[i] = MAP_SENTINEL; + for (u32 i = 0; i < h->hashes_count; i++) { + h->hashes[i] = MAP_SENTINEL; } - for (isize i = 0; i < h->entries.count; i++) { + for (isize i = 0; i < h->count; i++) { MapFindResult fr; - StringMapEntry *e = &h->entries.data[i]; + StringMapEntry *e = &h->entries[i]; e->next = MAP_SENTINEL; fr = string_map__find_from_entry(h, e); if (fr.entry_prev == MAP_SENTINEL) { @@ -157,27 +167,24 @@ gb_internal void string_map_reset_entries(StringMap *h) { } template -gb_internal void string_map_reserve(StringMap *h, isize cap) { - if (h->entries.allocator.proc == nullptr) { - h->entries.allocator = string_map_allocator(); - } - array_reserve(&h->entries, cap); - if (h->entries.count*2 < h->hashes.count) { +gb_internal void string_map_reserve(StringMap *h, usize cap) { + if (h->count*2 < h->hashes_count) { return; } - slice_resize(&h->hashes, h->entries.allocator, cap*2); + string_map__reserve_entries(h, cap); + string_map__resize_hashes(h, cap*2); string_map_reset_entries(h); } template -gb_internal T *string_map_get(StringMap *h, StringHashKey const &key) { +gb_internal T *string_map_get(StringMap *h, u32 hash, String const &key) { MapFindResult fr = {MAP_SENTINEL, MAP_SENTINEL, MAP_SENTINEL}; - if (h->hashes.count != 0) { - fr.hash_index = cast(MapIndex)(key.hash & (h->hashes.count-1)); - fr.entry_index = h->hashes.data[fr.hash_index]; + if (h->hashes_count != 0) { + fr.hash_index = cast(MapIndex)(hash & (h->hashes_count-1)); + fr.entry_index = h->hashes[fr.hash_index]; while (fr.entry_index != MAP_SENTINEL) { - auto *entry = &h->entries.data[fr.entry_index]; - if (string_hash_key_equal(entry->key, key)) { + auto *entry = &h->entries[fr.entry_index]; + if (entry->hash == hash && entry->key == key) { return &entry->value; } fr.entry_prev = fr.entry_index; @@ -187,52 +194,65 @@ gb_internal T *string_map_get(StringMap *h, StringHashKey const &key) { return nullptr; } + +template +gb_internal gb_inline T *string_map_get(StringMap *h, StringHashKey const &key) { + return string_map_get(h, key.hash, key.string); +} + template gb_internal gb_inline T *string_map_get(StringMap *h, String const &key) { - return string_map_get(h, string_hash_string(key)); + return string_map_get(h, string_hash(key), key); } template gb_internal gb_inline T *string_map_get(StringMap *h, char const *key) { - return string_map_get(h, string_hash_string(make_string_c(key))); + String k = make_string_c(key); + return string_map_get(h, string_hash(k), k); } template -gb_internal T &string_map_must_get(StringMap *h, StringHashKey const &key) { - isize index = string_map__find(h, key).entry_index; +gb_internal T &string_map_must_get(StringMap *h, u32 hash, String const &key) { + isize index = string_map__find(h, hash, key).entry_index; GB_ASSERT(index != MAP_SENTINEL); - return h->entries.data[index].value; + return h->entries[index].value; +} + +template +gb_internal T &string_map_must_get(StringMap *h, StringHashKey const &key) { + return string_map_must_get(h, key.hash, key.string); } template gb_internal gb_inline T &string_map_must_get(StringMap *h, String const &key) { - return string_map_must_get(h, string_hash_string(key)); + return string_map_must_get(h, string_hash(key), key); } template gb_internal gb_inline T &string_map_must_get(StringMap *h, char const *key) { - return string_map_must_get(h, string_hash_string(make_string_c(key))); + String k = make_string_c(key); + return string_map_must_get(h, string_hash(k), k); } template -gb_internal void string_map_set(StringMap *h, StringHashKey const &key, T const &value) { +gb_internal void string_map_set(StringMap *h, u32 hash, String const &key, T const &value) { MapIndex index; MapFindResult fr; - if (h->hashes.count == 0) { + if (h->hashes_count == 0) { string_map_grow(h); } - fr = string_map__find(h, key); + fr = string_map__find(h, hash, key); if (fr.entry_index != MAP_SENTINEL) { index = fr.entry_index; } else { - index = string_map__add_entry(h, key); + index = string_map__add_entry(h, hash, key); if (fr.entry_prev != MAP_SENTINEL) { - h->entries.data[fr.entry_prev].next = index; + h->entries[fr.entry_prev].next = index; } else { - h->hashes.data[fr.hash_index] = index; + h->hashes[fr.hash_index] = index; } } - h->entries.data[index].value = value; + h->entries[index].value = value; if (string_map__full(h)) { string_map_grow(h); @@ -249,25 +269,31 @@ gb_internal gb_inline void string_map_set(StringMap *h, char const *key, T co string_map_set(h, string_hash_string(make_string_c(key)), value); } +template +gb_internal gb_inline void string_map_set(StringMap *h, StringHashKey const &key, T const &value) { + string_map_set(h, key.hash, key.string, value); +} + + // template // gb_internal void string_map__erase(StringMap *h, MapFindResult const &fr) { // MapFindResult last; // if (fr.entry_prev == MAP_SENTINEL) { -// h->hashes.data[fr.hash_index] = h->entries.data[fr.entry_index].next; +// h->hashes[fr.hash_index] = h->entries[fr.entry_index].next; // } else { -// h->entries.data[fr.entry_prev].next = h->entries.data[fr.entry_index].next; +// h->entries[fr.entry_prev].next = h->entries[fr.entry_index].next; // } -// if (fr.entry_index == h->entries.count-1) { +// if (fr.entry_index == h->count-1) { // array_pop(&h->entries); // return; // } -// h->entries.data[fr.entry_index] = h->entries.data[h->entries.count-1]; -// last = string_map__find(h, h->entries.data[fr.entry_index].key); +// h->entries[fr.entry_index] = h->entries[h->count-1]; +// last = string_map__find(h, h->entries[fr.entry_index].key); // if (last.entry_prev != MAP_SENTINEL) { -// h->entries.data[last.entry_prev].next = fr.entry_index; +// h->entries[last.entry_prev].next = fr.entry_index; // } else { -// h->hashes.data[last.hash_index] = fr.entry_index; +// h->hashes[last.hash_index] = fr.entry_index; // } // } @@ -281,9 +307,9 @@ gb_internal gb_inline void string_map_set(StringMap *h, char const *key, T co template gb_internal gb_inline void string_map_clear(StringMap *h) { - array_clear(&h->entries); - for (isize i = 0; i < h->hashes.count; i++) { - h->hashes.data[i] = MAP_SENTINEL; + h->count = 0; + for (u32 i = 0; i < h->hashes_count; i++) { + h->hashes[i] = MAP_SENTINEL; } } @@ -291,20 +317,20 @@ gb_internal gb_inline void string_map_clear(StringMap *h) { template gb_internal StringMapEntry *begin(StringMap &m) noexcept { - return m.entries.data; + return m.entries; } template gb_internal StringMapEntry const *begin(StringMap const &m) noexcept { - return m.entries.data; + return m.entries; } template gb_internal StringMapEntry *end(StringMap &m) { - return m.entries.data + m.entries.count; + return m.entries + m.count; } template gb_internal StringMapEntry const *end(StringMap const &m) noexcept { - return m.entries.data + m.entries.count; + return m.entries + m.count; } \ No newline at end of file -- cgit v1.2.3