Add string_set.cpp; Code clean up

1 files changed, 184 insertions, 0 deletions

diff --git a/src/string_set.cpp b/src/string_set.cpp
new file mode 100644
index 000000000..9e44e1b1e
--- /dev/null
+++ b/src/string_set.cpp
@@ -0,0 +1,184 @@
+struct StringSetFindResult {
+	isize hash_index;
+	isize entry_prev;
+	isize entry_index;
+};
+
+struct StringSetEntry {
+	HashKey  key;
+	isize    next;
+	String   value;
+};
+
+struct StringSet {
+	Array<isize>          hashes;
+	Array<StringSetEntry> entries;
+};
+
+
+void string_set_init   (StringSet *s, gbAllocator a, isize capacity = 16);
+void string_set_destroy(StringSet *s);
+void string_set_add    (StringSet *s, String str);
+bool string_set_exists (StringSet *s, String str);
+void string_set_remove (StringSet *s, String str);
+void string_set_clear  (StringSet *s);
+void string_set_grow   (StringSet *s);
+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);
+}
+
+gb_inline void string_set_destroy(StringSet *s) {
+	array_free(&s->entries);
+	array_free(&s->hashes);
+}
+
+gb_internal isize string_set__add_entry(StringSet *s, HashKey key) {
+	StringSetEntry e = {};
+	e.key = key;
+	e.next = -1;
+	array_add(&s->entries, e);
+	return s->entries.count-1;
+}
+
+gb_internal StringSetFindResult string_set__find(StringSet *s, HashKey key) {
+	StringSetFindResult fr = {-1, -1, -1};
+	if (s->hashes.count > 0) {
+		// fr.hash_index  = u128_to_i64(key.key % u128_from_i64(s->hashes.count));
+		fr.hash_index = key.key % s->hashes.count;
+		fr.entry_index = s->hashes[fr.hash_index];
+		while (fr.entry_index >= 0) {
+			if (hash_key_equal(s->entries[fr.entry_index].key, key)) {
+				return fr;
+			}
+			fr.entry_prev = fr.entry_index;
+			fr.entry_index = s->entries[fr.entry_index].next;
+		}
+	}
+	return fr;
+}
+
+gb_internal StringSetFindResult string_set__find_from_entry(StringSet *s, StringSetEntry *e) {
+	StringSetFindResult 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;
+}
+
+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);
+	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] = -1;
+	}
+	for (i = 0; i < s->entries.count; i++) {
+		StringSetEntry *e = &s->entries[i];
+		StringSetFindResult fr;
+		if (ns.hashes.count == 0) {
+			string_set_grow(&ns);
+		}
+		fr = string_set__find(&ns, e->key);
+		j = string_set__add_entry(&ns, e->key);
+		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;
+		ns.entries[j].value = e->value;
+		if (string_set__full(&ns)) {
+			string_set_grow(&ns);
+		}
+	}
+	string_set_destroy(s);
+	*s = ns;
+}
+
+gb_inline bool string_set_exists(StringSet *s, String str) {
+	HashKey key = hash_string(str);
+	isize index = string_set__find(s, key).entry_index;
+	return index >= 0;
+}
+
+void string_set_add(StringSet *s, String str) {
+	isize index;
+	StringSetFindResult fr;
+	HashKey key = hash_string(str);
+	if (s->hashes.count == 0) {
+		string_set_grow(s);
+	}
+	fr = string_set__find(s, key);
+	if (fr.entry_index >= 0) {
+		index = fr.entry_index;
+	} else {
+		index = string_set__add_entry(s, key);
+		if (fr.entry_prev >= 0) {
+			s->entries[fr.entry_prev].next = index;
+		} else {
+			s->hashes[fr.hash_index] = index;
+		}
+	}
+	s->entries[index].value = str;
+
+	if (string_set__full(s)) {
+		string_set_grow(s);
+	}
+}
+
+
+void string_set__erase(StringSet *s, StringSetFindResult fr) {
+	StringSetFindResult 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 = string_set__find(s, s->entries[fr.entry_index].key);
+	if (last.entry_prev >= 0) {
+		s->entries[last.entry_prev].next = fr.entry_index;
+	} else {
+		s->hashes[last.hash_index] = fr.entry_index;
+	}
+}
+
+void string_set_remove(StringSet *s, String str) {
+	HashKey key = hash_string(str);
+	StringSetFindResult fr = string_set__find(s, key);
+	if (fr.entry_index >= 0) {
+		string_set__erase(s, fr);
+	}
+}
+
+gb_inline void string_set_clear(StringSet *s) {
+	array_clear(&s->hashes);
+	array_clear(&s->entries);
+}