aboutsummaryrefslogtreecommitdiff
path: root/src/ptr_set.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'src/ptr_set.cpp')
-rw-r--r--src/ptr_set.cpp137
1 files changed, 91 insertions, 46 deletions
diff --git a/src/ptr_set.cpp b/src/ptr_set.cpp
index e343628af..5432fa094 100644
--- a/src/ptr_set.cpp
+++ b/src/ptr_set.cpp
@@ -1,25 +1,30 @@
+typedef u32 PtrSetIndex;
+
struct PtrSetFindResult {
- isize hash_index;
- isize entry_prev;
- isize entry_index;
+ PtrSetIndex hash_index;
+ PtrSetIndex entry_prev;
+ PtrSetIndex entry_index;
};
+enum : PtrSetIndex { PTR_SET_SENTINEL = ~(PtrSetIndex)0 };
+
template <typename T>
struct PtrSetEntry {
- T ptr;
- isize next;
+ T ptr;
+ PtrSetIndex next;
};
template <typename T>
struct PtrSet {
- Array<isize> hashes;
+ Array<PtrSetIndex> hashes;
Array<PtrSetEntry<T>> entries;
};
template <typename T> void ptr_set_init (PtrSet<T> *s, gbAllocator a, isize capacity = 16);
template <typename T> void ptr_set_destroy(PtrSet<T> *s);
template <typename T> T ptr_set_add (PtrSet<T> *s, T ptr);
+template <typename T> bool ptr_set_update (PtrSet<T> *s, T ptr); // returns true if it previously existsed
template <typename T> bool ptr_set_exists (PtrSet<T> *s, T ptr);
template <typename T> void ptr_set_remove (PtrSet<T> *s, T ptr);
template <typename T> void ptr_set_clear (PtrSet<T> *s);
@@ -27,12 +32,31 @@ template <typename T> void ptr_set_grow (PtrSet<T> *s);
template <typename T> void ptr_set_rehash (PtrSet<T> *s, isize new_count);
+isize next_pow2_isize(isize n) {
+ if (n <= 0) {
+ return 0;
+ }
+ n--;
+ n |= n >> 1;
+ n |= n >> 2;
+ n |= n >> 4;
+ n |= n >> 8;
+ n |= n >> 16;
+ if (gb_size_of(isize) == 8) {
+ n |= n >> 32;
+ }
+ n++;
+ return n;
+}
+
template <typename T>
void ptr_set_init(PtrSet<T> *s, gbAllocator a, isize capacity) {
+ capacity = next_pow2_isize(gb_max(16, capacity));
+
array_init(&s->hashes, a, capacity);
array_init(&s->entries, a, 0, capacity);
for (isize i = 0; i < capacity; i++) {
- s->hashes.data[i] = -1;
+ s->hashes.data[i] = PTR_SET_SENTINEL;
}
}
@@ -43,72 +67,69 @@ void ptr_set_destroy(PtrSet<T> *s) {
}
template <typename T>
-gb_internal isize ptr_set__add_entry(PtrSet<T> *s, T ptr) {
+gb_internal PtrSetIndex ptr_set__add_entry(PtrSet<T> *s, T ptr) {
PtrSetEntry<T> e = {};
e.ptr = ptr;
- e.next = -1;
+ e.next = PTR_SET_SENTINEL;
array_add(&s->entries, e);
- return s->entries.count-1;
+ return cast(PtrSetIndex)(s->entries.count-1);
}
template <typename T>
gb_internal PtrSetFindResult ptr_set__find(PtrSet<T> *s, T ptr) {
- PtrSetFindResult fr = {-1, -1, -1};
- if (s->hashes.count > 0) {
+ PtrSetFindResult fr = {PTR_SET_SENTINEL, PTR_SET_SENTINEL, PTR_SET_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(isize)(hash % n);
- fr.entry_index = s->hashes[fr.hash_index];
- while (fr.entry_index >= 0) {
- if (s->entries[fr.entry_index].ptr == ptr) {
+ fr.hash_index = cast(PtrSetIndex)(hash & (n-1));
+ fr.entry_index = s->hashes.data[fr.hash_index];
+ while (fr.entry_index != PTR_SET_SENTINEL) {
+ if (s->entries.data[fr.entry_index].ptr == ptr) {
return fr;
}
fr.entry_prev = fr.entry_index;
- fr.entry_index = s->entries[fr.entry_index].next;
+ fr.entry_index = s->entries.data[fr.entry_index].next;
}
}
return fr;
}
template <typename T>
-gb_internal b32 ptr_set__full(PtrSet<T> *s) {
+gb_internal bool ptr_set__full(PtrSet<T> *s) {
return 0.75f * s->hashes.count <= s->entries.count;
}
-#define PTR_ARRAY_GROW_FORMULA(x) (4*(x) + 7)
-GB_STATIC_ASSERT(PTR_ARRAY_GROW_FORMULA(0) > 0);
-
template <typename T>
gb_inline void ptr_set_grow(PtrSet<T> *s) {
- isize new_count = PTR_ARRAY_GROW_FORMULA(s->entries.count);
+ isize new_count = s->hashes.count*2;
ptr_set_rehash(s, new_count);
}
template <typename T>
void ptr_set_rehash(PtrSet<T> *s, isize new_count) {
- isize i, j;
+ PtrSetIndex i, j;
PtrSet<T> ns = {};
ptr_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] = -1;
+ ns.hashes.data[i] = PTR_SET_SENTINEL;
}
for (i = 0; i < s->entries.count; i++) {
- PtrSetEntry<T> *e = &s->entries[i];
+ PtrSetEntry<T> *e = &s->entries.data[i];
PtrSetFindResult fr;
if (ns.hashes.count == 0) {
ptr_set_grow(&ns);
}
fr = ptr_set__find(&ns, e->ptr);
j = ptr_set__add_entry(&ns, e->ptr);
- if (fr.entry_prev < 0) {
- ns.hashes[fr.hash_index] = j;
+ if (fr.entry_prev == PTR_SET_SENTINEL) {
+ ns.hashes.data[fr.hash_index] = j;
} else {
- ns.entries[fr.entry_prev].next = j;
+ ns.entries.data[fr.entry_prev].next = j;
}
- ns.entries[j].next = fr.entry_index;
+ ns.entries.data[j].next = fr.entry_index;
if (ptr_set__full(&ns)) {
ptr_set_grow(&ns);
}
@@ -120,26 +141,24 @@ void ptr_set_rehash(PtrSet<T> *s, isize new_count) {
template <typename T>
gb_inline bool ptr_set_exists(PtrSet<T> *s, T ptr) {
isize index = ptr_set__find(s, ptr).entry_index;
- return index >= 0;
+ return index != PTR_SET_SENTINEL;
}
// Returns true if it already exists
template <typename T>
T ptr_set_add(PtrSet<T> *s, T ptr) {
- isize index;
+ PtrSetIndex index;
PtrSetFindResult fr;
if (s->hashes.count == 0) {
ptr_set_grow(s);
}
fr = ptr_set__find(s, ptr);
- if (fr.entry_index >= 0) {
- index = fr.entry_index;
- } else {
+ if (fr.entry_index == PTR_SET_SENTINEL) {
index = ptr_set__add_entry(s, ptr);
- if (fr.entry_prev >= 0) {
- s->entries[fr.entry_prev].next = index;
+ if (fr.entry_prev != PTR_SET_SENTINEL) {
+ s->entries.data[fr.entry_prev].next = index;
} else {
- s->hashes[fr.hash_index] = index;
+ s->hashes.data[fr.hash_index] = index;
}
}
if (ptr_set__full(s)) {
@@ -148,32 +167,58 @@ T ptr_set_add(PtrSet<T> *s, T ptr) {
return ptr;
}
+template <typename T>
+bool ptr_set_update(PtrSet<T> *s, T ptr) { // returns true if it previously existsed
+ bool exists = false;
+ PtrSetIndex index;
+ PtrSetFindResult fr;
+ if (s->hashes.count == 0) {
+ ptr_set_grow(s);
+ }
+ fr = ptr_set__find(s, ptr);
+ if (fr.entry_index != PTR_SET_SENTINEL) {
+ exists = true;
+ } else {
+ index = ptr_set__add_entry(s, ptr);
+ if (fr.entry_prev != PTR_SET_SENTINEL) {
+ s->entries.data[fr.entry_prev].next = index;
+ } else {
+ s->hashes.data[fr.hash_index] = index;
+ }
+ }
+ if (ptr_set__full(s)) {
+ ptr_set_grow(s);
+ }
+ return exists;
+}
+
+
template <typename T>
void ptr_set__erase(PtrSet<T> *s, PtrSetFindResult fr) {
PtrSetFindResult last;
- if (fr.entry_prev < 0) {
- s->hashes[fr.hash_index] = s->entries[fr.entry_index].next;
+ if (fr.entry_prev == PTR_SET_SENTINEL) {
+ s->hashes.data[fr.hash_index] = s->entries.data[fr.entry_index].next;
} else {
- s->entries[fr.entry_prev].next = s->entries[fr.entry_index].next;
+ s->entries.data[fr.entry_prev].next = s->entries.data[fr.entry_index].next;
}
if (fr.entry_index == s->entries.count-1) {
array_pop(&s->entries);
return;
}
- s->entries[fr.entry_index] = s->entries[s->entries.count-1];
- last = ptr_set__find(s, s->entries[fr.entry_index].ptr);
- if (last.entry_prev >= 0) {
- s->entries[last.entry_prev].next = fr.entry_index;
+ 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) {
+ s->entries.data[last.entry_prev].next = fr.entry_index;
} else {
- s->hashes[last.hash_index] = fr.entry_index;
+ s->hashes.data[last.hash_index] = fr.entry_index;
}
}
template <typename T>
void ptr_set_remove(PtrSet<T> *s, T ptr) {
PtrSetFindResult fr = ptr_set__find(s, ptr);
- if (fr.entry_index >= 0) {
+ if (fr.entry_index != PTR_SET_SENTINEL) {
ptr_set__erase(s, fr);
}
}
generated by cgit v1.2.3 (git 2.39.1) at 2026-02-15 12:42:27 +0000