From e95204908a12d4386ba9bda6de1fed7c73f66d29 Mon Sep 17 00:00:00 2001 From: gingerBill Date: Fri, 5 Nov 2021 16:34:37 +0000 Subject: Add `PtrMap`, begin working change `Map` to `PtrMap` where possible --- src/common.cpp | 1 + 1 file changed, 1 insertion(+) (limited to 'src/common.cpp') diff --git a/src/common.cpp b/src/common.cpp index 7af7026b9..5d7c87b6d 100644 --- a/src/common.cpp +++ b/src/common.cpp @@ -277,6 +277,7 @@ gb_global bool global_module_path_set = false; #include "string_map.cpp" #include "map.cpp" +#include "ptr_map.cpp" #include "ptr_set.cpp" #include "string_set.cpp" #include "priority_queue.cpp" -- cgit v1.2.3 From 541beb615b745b45f2cc82813014a3e04f1a3231 Mon Sep 17 00:00:00 2001 From: gingerBill Date: Fri, 5 Nov 2021 17:13:07 +0000 Subject: Move more things to `PtrMap` --- src/check_stmt.cpp | 9 ++++----- src/common.cpp | 8 ++++---- src/exact_value.cpp | 33 ++++++++++++++------------------- src/ptr_map.cpp | 2 +- 4 files changed, 23 insertions(+), 29 deletions(-) (limited to 'src/common.cpp') diff --git a/src/check_stmt.cpp b/src/check_stmt.cpp index 103ffa071..24ad0eec1 100644 --- a/src/check_stmt.cpp +++ b/src/check_stmt.cpp @@ -699,7 +699,7 @@ struct TypeAndToken { }; -void add_constant_switch_case(CheckerContext *ctx, Map *seen, Operand operand, bool use_expr = true) { +void add_constant_switch_case(CheckerContext *ctx, PtrMap *seen, Operand operand, bool use_expr = true) { if (operand.mode != Addressing_Constant) { return; } @@ -707,7 +707,7 @@ void add_constant_switch_case(CheckerContext *ctx, Map *seen, Oper return; } - HashKey key = hash_exact_value(operand.value); + uintptr key = hash_exact_value(operand.value); TypeAndToken *found = map_get(seen, key); if (found != nullptr) { isize count = multi_map_count(seen, key); @@ -964,7 +964,7 @@ void check_switch_stmt(CheckerContext *ctx, Ast *node, u32 mod_flags) { } } - Map seen = {}; // NOTE(bill): Multimap, Key: ExactValue + PtrMap seen = {}; // NOTE(bill): Multimap, Key: ExactValue map_init(&seen, heap_allocator()); defer (map_destroy(&seen)); @@ -1133,8 +1133,7 @@ void check_switch_stmt(CheckerContext *ctx, Ast *node, u32 mod_flags) { continue; } ExactValue v = f->Constant.value; - HashKey key = hash_exact_value(v); - auto found = map_get(&seen, key); + auto found = map_get(&seen, hash_exact_value(v)); if (!found) { array_add(&unhandled, f); } diff --git a/src/common.cpp b/src/common.cpp index 5d7c87b6d..f7a0653ac 100644 --- a/src/common.cpp +++ b/src/common.cpp @@ -290,13 +290,13 @@ struct StringIntern { char str[1]; }; -Map string_intern_map = {}; // Key: u64 +PtrMap string_intern_map = {}; // Key: u64 gb_global Arena string_intern_arena = {}; char const *string_intern(char const *text, isize len) { u64 hash = gb_fnv64a(text, len); - u64 key = hash ? hash : 1; - StringIntern **found = map_get(&string_intern_map, hash_integer(key)); + uintptr key = cast(uintptr)(hash ? hash : 1); + StringIntern **found = map_get(&string_intern_map, key); if (found) { for (StringIntern *it = *found; it != nullptr; it = it->next) { if (it->len == len && gb_strncmp(it->str, (char *)text, len) == 0) { @@ -310,7 +310,7 @@ char const *string_intern(char const *text, isize len) { new_intern->next = found ? *found : nullptr; gb_memmove(new_intern->str, text, len); new_intern->str[len] = 0; - map_set(&string_intern_map, hash_integer(key), new_intern); + map_set(&string_intern_map, key, new_intern); return new_intern->str; } diff --git a/src/exact_value.cpp b/src/exact_value.cpp index 363c6d863..fd90278e5 100644 --- a/src/exact_value.cpp +++ b/src/exact_value.cpp @@ -63,44 +63,39 @@ struct ExactValue { gb_global ExactValue const empty_exact_value = {}; -HashKey hash_exact_value(ExactValue v) { +uintptr hash_exact_value(ExactValue v) { mutex_lock(&hash_exact_value_mutex); defer (mutex_unlock(&hash_exact_value_mutex)); - HashKey empty = {}; switch (v.kind) { case ExactValue_Invalid: - return empty; + return 0; case ExactValue_Bool: - return hash_integer(u64(v.value_bool)); + return gb_fnv32a(&v.value_bool, gb_size_of(v.value_bool)); case ExactValue_String: - { - char const *str = string_intern(v.value_string); - return hash_pointer(str); - } + return ptr_map_hash_key(string_intern(v.value_string)); case ExactValue_Integer: { - HashKey key = hashing_proc(v.value_integer.dp, gb_size_of(*v.value_integer.dp) * v.value_integer.used); + u32 key = gb_fnv32a(v.value_integer.dp, gb_size_of(*v.value_integer.dp) * v.value_integer.used); u8 last = (u8)v.value_integer.sign; - key.key = (key.key ^ last) * 0x100000001b3ll; - return key; + return (key ^ last) * 0x01000193; } case ExactValue_Float: - return hash_f64(v.value_float); + return gb_fnv32a(&v.value_float, gb_size_of(v.value_float)); case ExactValue_Pointer: - return hash_integer(v.value_pointer); + return ptr_map_hash_key(v.value_pointer); case ExactValue_Complex: - return hashing_proc(v.value_complex, gb_size_of(Complex128)); + return gb_fnv32a(v.value_complex, gb_size_of(Complex128)); case ExactValue_Quaternion: - return hashing_proc(v.value_quaternion, gb_size_of(Quaternion256)); + return gb_fnv32a(v.value_quaternion, gb_size_of(Quaternion256)); case ExactValue_Compound: - return hash_pointer(v.value_compound); + return ptr_map_hash_key(v.value_compound); case ExactValue_Procedure: - return hash_pointer(v.value_procedure); + return ptr_map_hash_key(v.value_procedure); case ExactValue_Typeid: - return hash_pointer(v.value_typeid); + return ptr_map_hash_key(v.value_typeid); } - return hashing_proc(&v, gb_size_of(ExactValue)); + return gb_fnv32a(&v, gb_size_of(ExactValue)); } diff --git a/src/ptr_map.cpp b/src/ptr_map.cpp index 2387a2a20..0a61d300f 100644 --- a/src/ptr_map.cpp +++ b/src/ptr_map.cpp @@ -253,7 +253,7 @@ template PtrMapEntry *multi_map_find_next(PtrMap *h, PtrMapEntry *e) { isize i = e->next; while (i != MAP_SENTINEL) { - if (hash_key_equal(h->entries.data[i].key, e->key)) { + if (h->entries.data[i].key == e->key) { return &h->entries.data[i]; } i = h->entries.data[i].next; -- cgit v1.2.3 From 26e3daf5adc6c59f7bf7c621abc4640ba7a8bda0 Mon Sep 17 00:00:00 2001 From: gingerBill Date: Fri, 5 Nov 2021 17:24:19 +0000 Subject: Unify `MapFindResult` types --- src/common.cpp | 3 +- src/ptr_map.cpp | 4 +-- src/ptr_set.cpp | 85 ++++++++++++++++++++++---------------------------- src/string_map.cpp | 91 ++++++++++++++++++++++-------------------------------- src/string_set.cpp | 64 ++++++++++++++++++-------------------- 5 files changed, 107 insertions(+), 140 deletions(-) (limited to 'src/common.cpp') diff --git a/src/common.cpp b/src/common.cpp index f7a0653ac..cca478421 100644 --- a/src/common.cpp +++ b/src/common.cpp @@ -275,10 +275,9 @@ gb_global String global_module_path = {0}; gb_global bool global_module_path_set = false; -#include "string_map.cpp" -#include "map.cpp" #include "ptr_map.cpp" #include "ptr_set.cpp" +#include "string_map.cpp" #include "string_set.cpp" #include "priority_queue.cpp" #include "thread_pool.cpp" diff --git a/src/ptr_map.cpp b/src/ptr_map.cpp index 19443d8a1..7937e6968 100644 --- a/src/ptr_map.cpp +++ b/src/ptr_map.cpp @@ -29,11 +29,11 @@ struct PtrMap { u32 ptr_map_hash_key(void const *key) { // TODO(bill): Improve ptr_map_hash_key - return gb_fnv32a(&key, gb_size_of(key)); + return fnv32a(&key, gb_size_of(key)); } u32 ptr_map_hash_key(uintptr key) { // TODO(bill): Improve ptr_map_hash_key - return gb_fnv32a(&key, gb_size_of(key)); + return fnv32a(&key, gb_size_of(key)); } template void map_init (PtrMap *h, gbAllocator a, isize capacity = 16); diff --git a/src/ptr_set.cpp b/src/ptr_set.cpp index 0ca1921e8..4ab3d3259 100644 --- a/src/ptr_set.cpp +++ b/src/ptr_set.cpp @@ -1,23 +1,12 @@ -typedef u32 PtrSetIndex; - -struct PtrSetFindResult { - PtrSetIndex hash_index; - PtrSetIndex entry_prev; - PtrSetIndex entry_index; -}; - -enum : PtrSetIndex { PTR_SET_SENTINEL = ~(PtrSetIndex)0 }; - - template struct PtrSetEntry { - T ptr; - PtrSetIndex next; + T ptr; + MapIndex next; }; template struct PtrSet { - Slice hashes; + Slice hashes; Array> entries; }; @@ -40,7 +29,7 @@ void ptr_set_init(PtrSet *s, gbAllocator a, isize capacity) { slice_init(&s->hashes, a, capacity); array_init(&s->entries, a, 0, capacity); for (isize i = 0; i < capacity; i++) { - s->hashes.data[i] = PTR_SET_SENTINEL; + s->hashes.data[i] = MAP_SENTINEL; } } @@ -51,24 +40,24 @@ void ptr_set_destroy(PtrSet *s) { } template -gb_internal PtrSetIndex ptr_set__add_entry(PtrSet *s, T ptr) { +gb_internal MapIndex ptr_set__add_entry(PtrSet *s, T ptr) { PtrSetEntry e = {}; e.ptr = ptr; - e.next = PTR_SET_SENTINEL; + e.next = MAP_SENTINEL; array_add(&s->entries, e); - return cast(PtrSetIndex)(s->entries.count-1); + return cast(MapIndex)(s->entries.count-1); } template -gb_internal PtrSetFindResult ptr_set__find(PtrSet *s, T ptr) { - PtrSetFindResult fr = {PTR_SET_SENTINEL, PTR_SET_SENTINEL, PTR_SET_SENTINEL}; +gb_internal MapFindResult ptr_set__find(PtrSet *s, T ptr) { + MapFindResult fr = {MAP_SENTINEL, MAP_SENTINEL, MAP_SENTINEL}; if (s->hashes.count != 0) { u64 hash = 0xcbf29ce484222325ull ^ cast(u64)cast(uintptr)ptr; u64 n = cast(u64)s->hashes.count; - fr.hash_index = cast(PtrSetIndex)(hash & (n-1)); + fr.hash_index = cast(MapIndex)(hash & (n-1)); fr.entry_index = s->hashes.data[fr.hash_index]; - while (fr.entry_index != PTR_SET_SENTINEL) { + while (fr.entry_index != MAP_SENTINEL) { if (s->entries.data[fr.entry_index].ptr == ptr) { return fr; } @@ -80,14 +69,14 @@ gb_internal PtrSetFindResult ptr_set__find(PtrSet *s, T ptr) { } template -gb_internal PtrSetFindResult ptr_set__find_from_entry(PtrSet *s, PtrSetEntry *e) { - PtrSetFindResult fr = {PTR_SET_SENTINEL, PTR_SET_SENTINEL, PTR_SET_SENTINEL}; +gb_internal MapFindResult ptr_set__find_from_entry(PtrSet *s, PtrSetEntry *e) { + MapFindResult fr = {MAP_SENTINEL, MAP_SENTINEL, MAP_SENTINEL}; if (s->hashes.count != 0) { u64 hash = 0xcbf29ce484222325ull ^ cast(u64)cast(uintptr)e->ptr; u64 n = cast(u64)s->hashes.count; - fr.hash_index = cast(PtrSetIndex)(hash & (n-1)); + fr.hash_index = cast(MapIndex)(hash & (n-1)); fr.entry_index = s->hashes.data[fr.hash_index]; - while (fr.entry_index != PTR_SET_SENTINEL) { + while (fr.entry_index != MAP_SENTINEL) { if (&s->entries.data[fr.entry_index] == e) { return fr; } @@ -112,17 +101,17 @@ gb_inline void ptr_set_grow(PtrSet *s) { template void ptr_set_reset_entries(PtrSet *s) { for (isize i = 0; i < s->hashes.count; i++) { - s->hashes.data[i] = PTR_SET_SENTINEL; + s->hashes.data[i] = MAP_SENTINEL; } for (isize i = 0; i < s->entries.count; i++) { - PtrSetFindResult fr; + MapFindResult fr; PtrSetEntry *e = &s->entries.data[i]; - e->next = PTR_SET_SENTINEL; + e->next = MAP_SENTINEL; fr = ptr_set__find_from_entry(s, e); - if (fr.entry_prev == PTR_SET_SENTINEL) { - s->hashes[fr.hash_index] = cast(PtrSetIndex)i; + if (fr.entry_prev == MAP_SENTINEL) { + s->hashes[fr.hash_index] = cast(MapIndex)i; } else { - s->entries[fr.entry_prev].next = cast(PtrSetIndex)i; + s->entries[fr.entry_prev].next = cast(MapIndex)i; } } } @@ -146,21 +135,21 @@ void ptr_set_rehash(PtrSet *s, isize new_count) { template gb_inline bool ptr_set_exists(PtrSet *s, T ptr) { isize index = ptr_set__find(s, ptr).entry_index; - return index != PTR_SET_SENTINEL; + return index != MAP_SENTINEL; } // Returns true if it already exists template T ptr_set_add(PtrSet *s, T ptr) { - PtrSetIndex index; - PtrSetFindResult fr; + MapIndex index; + MapFindResult fr; if (s->hashes.count == 0) { ptr_set_grow(s); } fr = ptr_set__find(s, ptr); - if (fr.entry_index == PTR_SET_SENTINEL) { + if (fr.entry_index == MAP_SENTINEL) { index = ptr_set__add_entry(s, ptr); - if (fr.entry_prev != PTR_SET_SENTINEL) { + if (fr.entry_prev != MAP_SENTINEL) { s->entries.data[fr.entry_prev].next = index; } else { s->hashes.data[fr.hash_index] = index; @@ -175,17 +164,17 @@ T ptr_set_add(PtrSet *s, T ptr) { template bool ptr_set_update(PtrSet *s, T ptr) { // returns true if it previously existsed bool exists = false; - PtrSetIndex index; - PtrSetFindResult fr; + MapIndex index; + MapFindResult fr; if (s->hashes.count == 0) { ptr_set_grow(s); } fr = ptr_set__find(s, ptr); - if (fr.entry_index != PTR_SET_SENTINEL) { + if (fr.entry_index != MAP_SENTINEL) { exists = true; } else { index = ptr_set__add_entry(s, ptr); - if (fr.entry_prev != PTR_SET_SENTINEL) { + if (fr.entry_prev != MAP_SENTINEL) { s->entries.data[fr.entry_prev].next = index; } else { s->hashes.data[fr.hash_index] = index; @@ -200,9 +189,9 @@ bool ptr_set_update(PtrSet *s, T ptr) { // returns true if it previously exis template -void ptr_set__erase(PtrSet *s, PtrSetFindResult fr) { - PtrSetFindResult last; - if (fr.entry_prev == PTR_SET_SENTINEL) { +void ptr_set__erase(PtrSet *s, MapFindResult fr) { + MapFindResult last; + if (fr.entry_prev == MAP_SENTINEL) { s->hashes.data[fr.hash_index] = s->entries.data[fr.entry_index].next; } else { s->entries.data[fr.entry_prev].next = s->entries.data[fr.entry_index].next; @@ -213,7 +202,7 @@ void ptr_set__erase(PtrSet *s, PtrSetFindResult fr) { } s->entries.data[fr.entry_index] = s->entries.data[s->entries.count-1]; last = ptr_set__find(s, s->entries.data[fr.entry_index].ptr); - if (last.entry_prev != PTR_SET_SENTINEL) { + if (last.entry_prev != MAP_SENTINEL) { s->entries.data[last.entry_prev].next = fr.entry_index; } else { s->hashes.data[last.hash_index] = fr.entry_index; @@ -222,8 +211,8 @@ void ptr_set__erase(PtrSet *s, PtrSetFindResult fr) { template void ptr_set_remove(PtrSet *s, T ptr) { - PtrSetFindResult fr = ptr_set__find(s, ptr); - if (fr.entry_index != PTR_SET_SENTINEL) { + MapFindResult fr = ptr_set__find(s, ptr); + if (fr.entry_index != MAP_SENTINEL) { ptr_set__erase(s, fr); } } @@ -232,6 +221,6 @@ template gb_inline void ptr_set_clear(PtrSet *s) { array_clear(&s->entries); for (isize i = 0; i < s->hashes.count; i++) { - s->hashes.data[i] = PTR_SET_SENTINEL; + s->hashes.data[i] = MAP_SENTINEL; } } diff --git a/src/string_map.cpp b/src/string_map.cpp index 448af624d..218a45482 100644 --- a/src/string_map.cpp +++ b/src/string_map.cpp @@ -1,28 +1,11 @@ -// NOTE(bill): This util stuff is the same for every `Map` - -typedef u32 StringMapIndex; - -struct StringMapFindResult { - StringMapIndex hash_index; - StringMapIndex entry_prev; - StringMapIndex entry_index; -}; - -enum : StringMapIndex { STRING_MAP_SENTINEL = ~(StringMapIndex)0 }; - - struct StringHashKey { - u64 hash; + u32 hash; String string; }; -u64 string_hashing_proc(void const *data, isize len) { - return fnv64a(data, len); -} - gb_inline StringHashKey string_hash_string(String const &s) { StringHashKey hash_key = {}; - hash_key.hash = string_hashing_proc(s.text, s.len); + hash_key.hash = fnv32a(s.text, s.len); hash_key.string = s; return hash_key; } @@ -40,14 +23,14 @@ bool operator!=(StringHashKey const &a, StringHashKey const &b) { return !string template struct StringMapEntry { - StringHashKey key; - StringMapIndex next; - T value; + StringHashKey key; + MapIndex next; + T value; }; template struct StringMap { - Slice hashes; + Slice hashes; Array > entries; }; @@ -79,7 +62,7 @@ gb_inline void string_map_init(StringMap *h, gbAllocator a, isize capacity) { slice_init(&h->hashes, a, capacity); array_init(&h->entries, a, 0, capacity); for (isize i = 0; i < capacity; i++) { - h->hashes.data[i] = STRING_MAP_SENTINEL; + h->hashes.data[i] = MAP_SENTINEL; } } @@ -90,21 +73,21 @@ gb_inline void string_map_destroy(StringMap *h) { } template -gb_internal StringMapIndex string_map__add_entry(StringMap *h, StringHashKey const &key) { +gb_internal MapIndex string_map__add_entry(StringMap *h, StringHashKey const &key) { StringMapEntry e = {}; e.key = key; - e.next = STRING_MAP_SENTINEL; + e.next = MAP_SENTINEL; array_add(&h->entries, e); - return cast(StringMapIndex)(h->entries.count-1); + return cast(MapIndex)(h->entries.count-1); } template -gb_internal StringMapFindResult string_map__find(StringMap *h, StringHashKey const &key) { - StringMapFindResult fr = {STRING_MAP_SENTINEL, STRING_MAP_SENTINEL, STRING_MAP_SENTINEL}; +gb_internal MapFindResult string_map__find(StringMap *h, StringHashKey const &key) { + MapFindResult fr = {MAP_SENTINEL, MAP_SENTINEL, MAP_SENTINEL}; if (h->hashes.count != 0) { - fr.hash_index = cast(StringMapIndex)(key.hash & (h->hashes.count-1)); + fr.hash_index = cast(MapIndex)(key.hash & (h->hashes.count-1)); fr.entry_index = h->hashes.data[fr.hash_index]; - while (fr.entry_index != STRING_MAP_SENTINEL) { + while (fr.entry_index != MAP_SENTINEL) { if (string_hash_key_equal(h->entries.data[fr.entry_index].key, key)) { return fr; } @@ -116,12 +99,12 @@ gb_internal StringMapFindResult string_map__find(StringMap *h, StringHashKey } template -gb_internal StringMapFindResult string_map__find_from_entry(StringMap *h, StringMapEntry *e) { - StringMapFindResult fr = {STRING_MAP_SENTINEL, STRING_MAP_SENTINEL, STRING_MAP_SENTINEL}; +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(StringMapIndex)(e->key.hash & (h->hashes.count-1)); + fr.hash_index = cast(MapIndex)(e->key.hash & (h->hashes.count-1)); fr.entry_index = h->hashes.data[fr.hash_index]; - while (fr.entry_index != STRING_MAP_SENTINEL) { + while (fr.entry_index != MAP_SENTINEL) { if (&h->entries.data[fr.entry_index] == e) { return fr; } @@ -147,17 +130,17 @@ gb_inline void string_map_grow(StringMap *h) { template void string_map_reset_entries(StringMap *h) { for (isize i = 0; i < h->hashes.count; i++) { - h->hashes.data[i] = STRING_MAP_SENTINEL; + h->hashes.data[i] = MAP_SENTINEL; } for (isize i = 0; i < h->entries.count; i++) { - StringMapFindResult fr; + MapFindResult fr; StringMapEntry *e = &h->entries.data[i]; - e->next = STRING_MAP_SENTINEL; + e->next = MAP_SENTINEL; fr = string_map__find_from_entry(h, e); - if (fr.entry_prev == STRING_MAP_SENTINEL) { - h->hashes[fr.hash_index] = cast(StringMapIndex)i; + if (fr.entry_prev == MAP_SENTINEL) { + h->hashes[fr.hash_index] = cast(MapIndex)i; } else { - h->entries[fr.entry_prev].next = cast(StringMapIndex)i; + h->entries[fr.entry_prev].next = cast(MapIndex)i; } } } @@ -181,7 +164,7 @@ void string_map_rehash(StringMap *h, isize new_count) { template T *string_map_get(StringMap *h, StringHashKey const &key) { isize index = string_map__find(h, key).entry_index; - if (index != STRING_MAP_SENTINEL) { + if (index != MAP_SENTINEL) { return &h->entries.data[index].value; } return nullptr; @@ -200,7 +183,7 @@ gb_inline T *string_map_get(StringMap *h, char const *key) { template T &string_map_must_get(StringMap *h, StringHashKey const &key) { isize index = string_map__find(h, key).entry_index; - GB_ASSERT(index != STRING_MAP_SENTINEL); + GB_ASSERT(index != MAP_SENTINEL); return h->entries.data[index].value; } @@ -216,17 +199,17 @@ gb_inline T &string_map_must_get(StringMap *h, char const *key) { template void string_map_set(StringMap *h, StringHashKey const &key, T const &value) { - StringMapIndex index; - StringMapFindResult fr; + MapIndex index; + MapFindResult fr; if (h->hashes.count == 0) { string_map_grow(h); } fr = string_map__find(h, key); - if (fr.entry_index != STRING_MAP_SENTINEL) { + if (fr.entry_index != MAP_SENTINEL) { index = fr.entry_index; } else { index = string_map__add_entry(h, key); - if (fr.entry_prev != STRING_MAP_SENTINEL) { + if (fr.entry_prev != MAP_SENTINEL) { h->entries.data[fr.entry_prev].next = index; } else { h->hashes.data[fr.hash_index] = index; @@ -251,9 +234,9 @@ gb_inline void string_map_set(StringMap *h, char const *key, T const &value) template -void string_map__erase(StringMap *h, StringMapFindResult const &fr) { - StringMapFindResult last; - if (fr.entry_prev == STRING_MAP_SENTINEL) { +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; } else { h->entries.data[fr.entry_prev].next = h->entries.data[fr.entry_index].next; @@ -264,7 +247,7 @@ void string_map__erase(StringMap *h, StringMapFindResult const &fr) { } 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); - if (last.entry_prev != STRING_MAP_SENTINEL) { + if (last.entry_prev != MAP_SENTINEL) { h->entries.data[last.entry_prev].next = fr.entry_index; } else { h->hashes.data[last.hash_index] = fr.entry_index; @@ -273,8 +256,8 @@ void string_map__erase(StringMap *h, StringMapFindResult const &fr) { template void string_map_remove(StringMap *h, StringHashKey const &key) { - StringMapFindResult fr = string_map__find(h, key); - if (fr.entry_index != STRING_MAP_SENTINEL) { + MapFindResult fr = string_map__find(h, key); + if (fr.entry_index != MAP_SENTINEL) { string_map__erase(h, fr); } } @@ -283,7 +266,7 @@ template 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] = STRING_MAP_SENTINEL; + h->hashes.data[i] = MAP_SENTINEL; } } diff --git a/src/string_set.cpp b/src/string_set.cpp index 671b2c9ff..1f2ea96a4 100644 --- a/src/string_set.cpp +++ b/src/string_set.cpp @@ -1,17 +1,11 @@ -struct StringSetFindResult { - isize hash_index; - isize entry_prev; - isize entry_index; -}; - struct StringSetEntry { - u64 hash; - isize next; - String value; + u32 hash; + MapIndex next; + String value; }; struct StringSet { - Array hashes; + Array hashes; Array entries; }; @@ -36,22 +30,22 @@ gb_inline void string_set_destroy(StringSet *s) { array_free(&s->hashes); } -gb_internal isize string_set__add_entry(StringSet *s, StringHashKey const &key) { +gb_internal MapIndex string_set__add_entry(StringSet *s, StringHashKey const &key) { StringSetEntry e = {}; e.hash = key.hash; - e.next = -1; + e.next = MAP_SENTINEL; e.value = key.string; array_add(&s->entries, e); - return s->entries.count-1; + return cast(MapIndex)(s->entries.count-1); } -gb_internal StringSetFindResult string_set__find(StringSet *s, StringHashKey const &key) { - StringSetFindResult fr = {-1, -1, -1}; +gb_internal MapFindResult string_set__find(StringSet *s, StringHashKey const &key) { + MapFindResult fr = {MAP_SENTINEL, MAP_SENTINEL, MAP_SENTINEL}; if (s->hashes.count > 0) { // fr.hash_index = u128_to_i64(key.key % u128_from_i64(s->hashes.count)); - fr.hash_index = key.hash % s->hashes.count; + fr.hash_index = cast(MapIndex)(((u64)key.hash) % s->hashes.count); fr.entry_index = s->hashes[fr.hash_index]; - while (fr.entry_index >= 0) { + while (fr.entry_index != MAP_SENTINEL) { auto const &entry = s->entries[fr.entry_index]; if (entry.hash == key.hash && entry.value == key.string) { return fr; @@ -79,21 +73,21 @@ void string_set_rehash(StringSet *s, isize new_count) { array_resize(&ns.hashes, new_count); array_reserve(&ns.entries, s->entries.count); for (i = 0; i < new_count; i++) { - ns.hashes[i] = -1; + ns.hashes[i] = MAP_SENTINEL; } for (i = 0; i < s->entries.count; i++) { StringSetEntry *e = &s->entries[i]; - StringSetFindResult fr; + MapFindResult fr; if (ns.hashes.count == 0) { string_set_grow(&ns); } StringHashKey key = {e->hash, e->value}; fr = string_set__find(&ns, key); j = string_set__add_entry(&ns, key); - if (fr.entry_prev < 0) { - ns.hashes[fr.hash_index] = j; + if (fr.entry_prev == MAP_SENTINEL) { + ns.hashes[fr.hash_index] = cast(MapIndex)j; } else { - ns.entries[fr.entry_prev].next = j; + ns.entries[fr.entry_prev].next = cast(MapIndex)j; } ns.entries[j].next = fr.entry_index; ns.entries[j].value = e->value; @@ -108,22 +102,22 @@ void string_set_rehash(StringSet *s, isize new_count) { gb_inline bool string_set_exists(StringSet *s, String const &str) { StringHashKey key = string_hash_string(str); isize index = string_set__find(s, key).entry_index; - return index >= 0; + return index != MAP_SENTINEL; } void string_set_add(StringSet *s, String const &str) { - isize index; - StringSetFindResult fr; + MapIndex index; + MapFindResult fr; StringHashKey key = string_hash_string(str); if (s->hashes.count == 0) { string_set_grow(s); } fr = string_set__find(s, key); - if (fr.entry_index >= 0) { + if (fr.entry_index != MAP_SENTINEL) { index = fr.entry_index; } else { index = string_set__add_entry(s, key); - if (fr.entry_prev >= 0) { + if (fr.entry_prev != MAP_SENTINEL) { s->entries[fr.entry_prev].next = index; } else { s->hashes[fr.hash_index] = index; @@ -137,9 +131,9 @@ void string_set_add(StringSet *s, String const &str) { } -void string_set__erase(StringSet *s, StringSetFindResult fr) { - StringSetFindResult last; - if (fr.entry_prev < 0) { +void string_set__erase(StringSet *s, MapFindResult fr) { + MapFindResult last; + if (fr.entry_prev == MAP_SENTINEL) { s->hashes[fr.hash_index] = s->entries[fr.entry_index].next; } else { s->entries[fr.entry_prev].next = s->entries[fr.entry_index].next; @@ -152,7 +146,7 @@ void string_set__erase(StringSet *s, StringSetFindResult fr) { *entry = s->entries[s->entries.count-1]; StringHashKey key = {entry->hash, entry->value}; last = string_set__find(s, key); - if (last.entry_prev >= 0) { + if (last.entry_prev != MAP_SENTINEL) { s->entries[last.entry_prev].next = fr.entry_index; } else { s->hashes[last.hash_index] = fr.entry_index; @@ -161,13 +155,15 @@ void string_set__erase(StringSet *s, StringSetFindResult fr) { void string_set_remove(StringSet *s, String const &str) { StringHashKey key = string_hash_string(str); - StringSetFindResult fr = string_set__find(s, key); - if (fr.entry_index >= 0) { + MapFindResult fr = string_set__find(s, key); + if (fr.entry_index != MAP_SENTINEL) { string_set__erase(s, fr); } } gb_inline void string_set_clear(StringSet *s) { - array_clear(&s->hashes); array_clear(&s->entries); + for_array(i, s->hashes) { + s->hashes.data[i] = MAP_SENTINEL; + } } -- cgit v1.2.3