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/ptr_set.cpp | 85 +++++++++++++++++++++++++-------------------------------- 1 file changed, 37 insertions(+), 48 deletions(-) (limited to 'src/ptr_set.cpp') 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; } } -- cgit v1.2.3 From 0c9bb9d920e0af4e6fe8299390c542f01ef77177 Mon Sep 17 00:00:00 2001 From: gingerBill Date: Fri, 5 Nov 2021 17:32:17 +0000 Subject: Clean up logic --- src/ptr_set.cpp | 2 +- src/string_set.cpp | 81 +++++++++++++++++++++++++++++++++--------------------- 2 files changed, 51 insertions(+), 32 deletions(-) (limited to 'src/ptr_set.cpp') diff --git a/src/ptr_set.cpp b/src/ptr_set.cpp index 4ab3d3259..37815c057 100644 --- a/src/ptr_set.cpp +++ b/src/ptr_set.cpp @@ -94,7 +94,7 @@ gb_internal bool ptr_set__full(PtrSet *s) { template gb_inline void ptr_set_grow(PtrSet *s) { - isize new_count = s->hashes.count*2; + isize new_count = gb_max(s->hashes.count<<1, 16); ptr_set_rehash(s, new_count); } diff --git a/src/string_set.cpp b/src/string_set.cpp index 1f2ea96a4..e27145289 100644 --- a/src/string_set.cpp +++ b/src/string_set.cpp @@ -5,7 +5,7 @@ struct StringSetEntry { }; struct StringSet { - Array hashes; + Slice hashes; Array entries; }; @@ -21,13 +21,18 @@ void string_set_rehash (StringSet *s, isize new_count); gb_inline void string_set_init(StringSet *s, gbAllocator a, isize capacity) { - array_init(&s->hashes, a); - array_init(&s->entries, a); + capacity = next_pow2_isize(gb_max(16, 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] = MAP_SENTINEL; + } } gb_inline void string_set_destroy(StringSet *s) { + slice_free(&s->hashes, s->entries.allocator); array_free(&s->entries); - array_free(&s->hashes); } gb_internal MapIndex string_set__add_entry(StringSet *s, StringHashKey const &key) { @@ -42,7 +47,6 @@ gb_internal MapIndex string_set__add_entry(StringSet *s, StringHashKey const &ke 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 = cast(MapIndex)(((u64)key.hash) % s->hashes.count); fr.entry_index = s->hashes[fr.hash_index]; while (fr.entry_index != MAP_SENTINEL) { @@ -56,47 +60,62 @@ gb_internal MapFindResult string_set__find(StringSet *s, StringHashKey const &ke } return fr; } +gb_internal MapFindResult string_set__find_from_entry(StringSet *s, StringSetEntry *e) { + MapFindResult fr = {MAP_SENTINEL, MAP_SENTINEL, MAP_SENTINEL}; + if (s->hashes.count > 0) { + fr.hash_index = cast(MapIndex)(e->hash % s->hashes.count); + fr.entry_index = s->hashes[fr.hash_index]; + while (fr.entry_index != MAP_SENTINEL) { + if (&s->entries[fr.entry_index] == e) { + return fr; + } + fr.entry_prev = fr.entry_index; + fr.entry_index = s->entries[fr.entry_index].next; + } + } + return fr; +} + gb_internal b32 string_set__full(StringSet *s) { return 0.75f * s->hashes.count <= s->entries.count; } gb_inline void string_set_grow(StringSet *s) { - isize new_count = ARRAY_GROW_FORMULA(s->entries.count); + isize new_count = gb_max(s->hashes.count<<1, 16); string_set_rehash(s, new_count); } -void string_set_rehash(StringSet *s, isize new_count) { - isize i, j; - StringSet ns = {}; - string_set_init(&ns, s->hashes.allocator); - array_resize(&ns.hashes, new_count); - array_reserve(&ns.entries, s->entries.count); - for (i = 0; i < new_count; i++) { - ns.hashes[i] = MAP_SENTINEL; + +void string_set_reset_entries(StringSet *s) { + for (isize i = 0; i < s->hashes.count; i++) { + s->hashes.data[i] = MAP_SENTINEL; } - for (i = 0; i < s->entries.count; i++) { - StringSetEntry *e = &s->entries[i]; + for (isize i = 0; i < s->entries.count; i++) { 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); + StringSetEntry *e = &s->entries.data[i]; + e->next = MAP_SENTINEL; + fr = string_set__find_from_entry(s, e); if (fr.entry_prev == MAP_SENTINEL) { - ns.hashes[fr.hash_index] = cast(MapIndex)j; + s->hashes[fr.hash_index] = cast(MapIndex)i; } else { - ns.entries[fr.entry_prev].next = cast(MapIndex)j; - } - ns.entries[j].next = fr.entry_index; - ns.entries[j].value = e->value; - if (string_set__full(&ns)) { - string_set_grow(&ns); + s->entries[fr.entry_prev].next = cast(MapIndex)i; } } - string_set_destroy(s); - *s = ns; +} + +void string_set_reserve(StringSet *s, isize cap) { + array_reserve(&s->entries, cap); + if (s->entries.count*2 < s->hashes.count) { + return; + } + slice_resize(&s->hashes, s->entries.allocator, cap*2); + string_set_reset_entries(s); +} + + +void string_set_rehash(StringSet *s, isize new_count) { + string_set_reserve(s, new_count); } gb_inline bool string_set_exists(StringSet *s, String const &str) { -- cgit v1.2.3 From eb0faf9602224eb1ab381e28ac7b41b71ada3fbc Mon Sep 17 00:00:00 2001 From: gingerBill Date: Fri, 5 Nov 2021 17:58:11 +0000 Subject: Unify hash logic for `PtrSet` --- src/ptr_set.cpp | 10 ++++------ 1 file changed, 4 insertions(+), 6 deletions(-) (limited to 'src/ptr_set.cpp') diff --git a/src/ptr_set.cpp b/src/ptr_set.cpp index 37815c057..8dd3cb4dc 100644 --- a/src/ptr_set.cpp +++ b/src/ptr_set.cpp @@ -53,9 +53,8 @@ template 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(MapIndex)(hash & (n-1)); + u32 hash = ptr_map_hash_key(ptr); + fr.hash_index = cast(MapIndex)(hash & (s->hashes.count-1)); fr.entry_index = s->hashes.data[fr.hash_index]; while (fr.entry_index != MAP_SENTINEL) { if (s->entries.data[fr.entry_index].ptr == ptr) { @@ -72,9 +71,8 @@ template 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(MapIndex)(hash & (n-1)); + u32 hash = ptr_map_hash_key(e->ptr); + fr.hash_index = cast(MapIndex)(hash & (s->hashes.count-1)); fr.entry_index = s->hashes.data[fr.hash_index]; while (fr.entry_index != MAP_SENTINEL) { if (&s->entries.data[fr.entry_index] == e) { -- cgit v1.2.3