Add priority_queue.cpp and ptr_set.cpp

2 files changed, 290 insertions, 0 deletions

diff --git a/src/priority_queue.cpp b/src/priority_queue.cpp
new file mode 100644
index 000000000..7c36e6a22
--- /dev/null
+++ b/src/priority_queue.cpp
@@ -0,0 +1,96 @@
+template <typename T>
+struct PriorityQueue {
+	Array<T> queue;
+
+	int  (* cmp) (T *q, isize i, isize j);
+	void (* swap)(T *q, isize i, isize j);
+};
+
+template <typename T>
+bool priority_queue_shift_down(PriorityQueue<T> *pq, isize i0, isize n) {
+	// O(n log n)
+	isize i = i0;
+	isize j, j1, j2;
+	if (0 > i || i > n) return false;
+	for (;;) {
+		j1 = 2*i + 1;
+		if (0 > j1 || j1 >= n) break;
+		j = j1;
+		j2 = j1 + 1;
+		if (j2 < n && pq->cmp(&pq->queue[0], j2, j1) < 0) {
+			j = j2;
+		}
+		if (pq->cmp(&pq->queue[0], i, j) < 0) break;
+
+		pq->swap(&pq->queue[0], i, j);
+		i = j;
+	}
+	return i > i0;
+}
+
+template <typename T>
+void priority_queue_shift_up(PriorityQueue<T> *pq, isize j) {
+	while (0 <= j && j < pq->queue.count) {
+		isize i = (j-1)/2;
+		if (i == j || pq->cmp(&pq->queue[0], i, j) < 0) {
+			break;
+		}
+		pq->swap(&pq->queue[0], i, j);
+		j = i;
+	}
+}
+
+// NOTE(bill): When an element at index `i0` has changed its value, this will fix the
+// the heap ordering. This using a basic "heapsort" with shift up and a shift down parts.
+template <typename T>
+void priority_queue_fix(PriorityQueue<T> *pq, isize i) {
+	if (!priority_queue_shift_down(pq, i, pq->queue.count)) {
+		priority_queue_shift_up(pq, i);
+	}
+}
+
+template <typename T>
+void priority_queue_push(PriorityQueue<T> *pq, T const &value) {
+	array_add(&pq->queue, value);
+	priority_queue_shift_up(pq, pq->queue.count-1);
+}
+
+template <typename T>
+T priority_queue_pop(PriorityQueue<T> *pq) {
+	GB_ASSERT(pq->queue.count > 0);
+
+	isize n = pq->queue.count - 1;
+	pq->swap(&pq->queue[0], 0, n);
+	priority_queue_shift_down(pq, 0, n);
+	return array_pop(&pq->queue);
+}
+
+
+template <typename T>
+T priority_queue_remove(PriorityQueue<T> *pq, isize i) {
+	GB_ASSERT(0 <= i && i < pq->queue.count);
+	isize n = pq->queue.count - 1;
+	if (n != i) {
+		pq->swap(&pq->queue[0], i, n);
+		priority_queue_shift_down(pq, i, n);
+		priority_queue_shift_up(pq, i);
+	}
+	return array_pop(&pq->queue);
+}
+
+
+template <typename T>
+PriorityQueue<T> priority_queue_create(Array<T> queue,
+                                       int  (* cmp) (T *q, isize i, isize j),
+                                       void (* swap)(T *q, isize i, isize j)) {
+	PriorityQueue<T> pq = {};
+	pq.queue = queue;
+	pq.cmp   = cmp;
+	pq.swap  = swap;
+
+	isize n = pq.queue.count;
+	for (isize i = n/2 - 1; i >= 0; i--) {
+		priority_queue_shift_down(&pq, i, n);
+	}
+	return pq;
+}
diff --git a/src/ptr_set.cpp b/src/ptr_set.cpp
new file mode 100644
index 000000000..1eecee33e
--- /dev/null
+++ b/src/ptr_set.cpp
@@ -0,0 +1,194 @@
+struct PtrSetFindResult {
+	isize hash_index;
+	isize entry_prev;
+	isize entry_index;
+};
+
+
+template <typename T>
+struct PtrSetEntry {
+	T       ptr;
+	isize   next;
+};
+
+template <typename T>
+struct PtrSet {
+	Array<isize>          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> void ptr_set_add              (PtrSet<T> *s, T ptr);
+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);
+template <typename T> void ptr_set_grow             (PtrSet<T> *s);
+template <typename T> void ptr_set_rehash           (PtrSet<T> *s, isize new_count);
+
+
+template <typename T>
+void ptr_set_init(PtrSet<T> *s, gbAllocator a, isize capacity) {
+	array_init(&s->hashes,  a, capacity);
+	array_init(&s->entries, a, capacity);
+}
+
+template <typename T>
+void ptr_set_destroy(PtrSet<T> *s) {
+	array_free(&s->hashes);
+	array_free(&s->entries);
+}
+
+template <typename T>
+gb_internal isize ptr_set__add_entry(PtrSet<T> *s, T ptr) {
+	PtrSetEntry<T> e = {};
+	e.ptr = ptr;
+	e.next = -1;
+	array_add(&s->entries, e);
+	return 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) {
+		uintptr p = cast(uintptr)ptr;
+		uintptr n = cast(uintptr)s->hashes.count;
+		fr.hash_index = cast(isize)(p % n);
+		fr.entry_index = s->hashes[fr.hash_index];
+		while (fr.entry_index >= 0) {
+			if (s->entries[fr.entry_index].ptr == ptr) {
+				return fr;
+			}
+			fr.entry_prev = fr.entry_index;
+			fr.entry_index = s->entries[fr.entry_index].next;
+		}
+	}
+	return fr;
+}
+
+template <typename T>
+gb_internal PtrSetFindResult ptr_set__find_from_entry(PtrSet<T> *s, PtrSetEntry<T> *e) {
+	PtrSetFindResult fr = {-1, -1, -1};
+	if (s->hashes.count > 0) {
+		fr.hash_index  = e->key.key % s->hashes.count;
+		fr.entry_index = s->hashes[fr.hash_index];
+		while (fr.entry_index >= 0) {
+			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;
+}
+
+template <typename T>
+gb_internal b32 ptr_set__full(PtrSet<T> *s) {
+	return 0.75f * s->hashes.count <= s->entries.count;
+}
+
+template <typename T>
+gb_inline void ptr_set_grow(PtrSet<T> *s) {
+	isize new_count = ARRAY_GROW_FORMULA(s->entries.count);
+	ptr_set_rehash(s, new_count);
+}
+
+template <typename T>
+void ptr_set_rehash(PtrSet<T> *s, isize new_count) {
+	isize 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;
+	}
+	for (i = 0; i < s->entries.count; i++) {
+		PtrSetEntry<T> *e = &s->entries[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;
+		} else {
+			ns.entries[fr.entry_prev].next = j;
+		}
+		ns.entries[j].next = fr.entry_index;
+		if (ptr_set__full(&ns)) {
+			ptr_set_grow(&ns);
+		}
+	}
+	ptr_set_destroy(s);
+	*s = ns;
+}
+
+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;
+}
+
+template <typename T>
+void ptr_set_add(PtrSet<T> *s, T ptr) {
+	isize 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 {
+		index = ptr_set__add_entry(s, ptr);
+		if (fr.entry_prev >= 0) {
+			s->entries[fr.entry_prev].next = index;
+		} else {
+			s->hashes[fr.hash_index] = index;
+		}
+	}
+	if (ptr_set__full(s)) {
+		ptr_set_grow(s);
+	}
+}
+
+
+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;
+	} else {
+		s->entries[fr.entry_prev].next = s->entries[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;
+	} else {
+		s->hashes[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) {
+		ptr_set__erase(s, fr);
+	}
+}
+
+template <typename T>
+gb_inline void ptr_set_clear(PtrSet<T> *s) {
+	array_clear(&s->hashes);
+	array_clear(&s->entries);
+}