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