From 242307dd4466389e971b6273c1267708777b50dd Mon Sep 17 00:00:00 2001 From: gingerBill Date: Fri, 3 May 2024 12:34:12 +0100 Subject: Revert to old `StringMap` internal layout --- src/string_map.cpp | 292 +++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 292 insertions(+) (limited to 'src/string_map.cpp') diff --git a/src/string_map.cpp b/src/string_map.cpp index 4de88bbf9..802bf5853 100644 --- a/src/string_map.cpp +++ b/src/string_map.cpp @@ -24,6 +24,296 @@ gb_internal gb_inline StringHashKey string_hash_string(String const &s) { return hash_key; } + +#if 1 /* old string map */ + +template +struct StringMapEntry { + String key; + u32 hash; + MapIndex next; + T value; +}; + +template +struct StringMap { + MapIndex * hashes; + usize hashes_count; + StringMapEntry *entries; + u32 count; + u32 entries_capacity; +}; + + +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_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_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, usize capacity) { + capacity = next_pow2_isize(capacity); + string_map_reserve(h, capacity); +} + +template +gb_internal gb_inline void string_map_destroy(StringMap *h) { + 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, MAP_CACHE_LINE_SIZE); +} + + +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, MAP_CACHE_LINE_SIZE); +} + + +template +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; + if (h->count+1 >= h->entries_capacity) { + string_map__reserve_entries(h, gb_max(h->entries_capacity*2, 4)); + } + h->entries[h->count++] = e; + return cast(MapIndex)(h->count-1); +} + +template +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)(hash & (h->hashes_count-1)); + fr.entry_index = h->hashes[fr.hash_index]; + while (fr.entry_index != MAP_SENTINEL) { + 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 = entry->next; + } + } + return fr; +} + +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->hash & (h->hashes_count-1)); + fr.entry_index = h->hashes[fr.hash_index]; + while (fr.entry_index != MAP_SENTINEL) { + auto *entry = &h->entries[fr.entry_index]; + if (entry == e) { + return fr; + } + fr.entry_prev = fr.entry_index; + fr.entry_index = entry->next; + } + } + return fr; +} + +template +gb_internal b32 string_map__full(StringMap *h) { + 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); + string_map_reserve(h, new_count); +} + + +template +gb_internal void string_map_reset_entries(StringMap *h) { + for (u32 i = 0; i < h->hashes_count; i++) { + h->hashes[i] = MAP_SENTINEL; + } + for (isize i = 0; i < h->count; i++) { + MapFindResult fr; + StringMapEntry *e = &h->entries[i]; + e->next = MAP_SENTINEL; + fr = string_map__find_from_entry(h, e); + if (fr.entry_prev == MAP_SENTINEL) { + h->hashes[fr.hash_index] = cast(MapIndex)i; + } else { + h->entries[fr.entry_prev].next = cast(MapIndex)i; + } + } +} + +template +gb_internal void string_map_reserve(StringMap *h, usize cap) { + if (h->count*2 < h->hashes_count) { + return; + } + 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, u32 hash, String const &key) { + MapFindResult fr = {MAP_SENTINEL, MAP_SENTINEL, MAP_SENTINEL}; + 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[fr.entry_index]; + if (entry->hash == hash && entry->key == key) { + return &entry->value; + } + fr.entry_prev = fr.entry_index; + fr.entry_index = entry->next; + } + } + 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(key), key); +} + +template +gb_internal gb_inline T *string_map_get(StringMap *h, char const *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, u32 hash, String const &key) { + isize index = string_map__find(h, hash, key).entry_index; + GB_ASSERT(index != MAP_SENTINEL); + 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(key), key); +} + +template +gb_internal gb_inline T &string_map_must_get(StringMap *h, char const *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, u32 hash, String const &key, T const &value) { + MapIndex index; + MapFindResult fr; + if (h->hashes_count == 0) { + string_map_grow(h); + } + fr = string_map__find(h, hash, key); + if (fr.entry_index != MAP_SENTINEL) { + index = fr.entry_index; + } else { + index = string_map__add_entry(h, hash, key); + if (fr.entry_prev != MAP_SENTINEL) { + h->entries[fr.entry_prev].next = index; + } else { + h->hashes[fr.hash_index] = index; + } + } + h->entries[index].value = value; + + if (string_map__full(h)) { + string_map_grow(h); + } +} + +template +gb_internal gb_inline void string_map_set(StringMap *h, String const &key, T const &value) { + string_map_set(h, string_hash_string(key), value); +} + +template +gb_internal gb_inline void string_map_set(StringMap *h, char const *key, T const &value) { + 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 gb_inline void string_map_clear(StringMap *h) { + h->count = 0; + for (u32 i = 0; i < h->hashes_count; i++) { + h->hashes[i] = MAP_SENTINEL; + } +} + + + +template +gb_internal StringMapEntry *begin(StringMap &m) noexcept { + return m.entries; +} +template +gb_internal StringMapEntry const *begin(StringMap const &m) noexcept { + return m.entries; +} + + +template +gb_internal StringMapEntry *end(StringMap &m) noexcept { + return m.entries + m.count; +} + +template +gb_internal StringMapEntry const *end(StringMap const &m) noexcept { + return m.entries + m.count; +} + +#else /* new string map */ + template struct StringMapEntry { String key; @@ -305,3 +595,5 @@ gb_internal StringMapIterator const begin(StringMap const &m) noexcept { } return StringMapIterator{&m, index}; } + +#endif \ No newline at end of file -- cgit v1.2.3