Simplify `Map` and `StringMap` in the compiler to reuse the hashes' array data if possible.

3 files changed, 55 insertions, 37 deletions

diff --git a/src/array.cpp b/src/array.cpp
index ad0efcd74..90d85563c 100644
--- a/src/array.cpp
+++ b/src/array.cpp
@@ -1,4 +1,4 @@
-#define ARRAY_GROW_FORMULA(x) (2*(x) + 8)
+#define ARRAY_GROW_FORMULA(x) (gb_max(((x)+1)*3 >> 1, 8))
 GB_STATIC_ASSERT(ARRAY_GROW_FORMULA(0) > 0);
 
 #if 1
@@ -84,6 +84,23 @@ Slice<T> slice_make(gbAllocator const &allocator, isize count) {
 	return s;
 }
 
+template <typename T>
+void slice_init(Slice<T> *s, gbAllocator const &allocator, isize count) {
+	s->data = gb_alloc_array(allocator, T, count);
+	s->count = count;
+}
+
+template <typename T>
+void slice_free(Slice<T> *s, gbAllocator const &allocator) {
+	gb_free(allocator, s->data);
+}
+
+template <typename T>
+void slice_resize(Slice<T> *s, gbAllocator const &allocator, isize new_count) {
+	resize_array_raw(&s->data, allocator, s->count, new_count);
+	s->count = new_count;
+}
+
 
 template <typename T>
 Slice<T> slice_from_array(Array<T> const &a) {
diff --git a/src/map.cpp b/src/map.cpp
index 18cf486ce..51d0b9885 100644
--- a/src/map.cpp
+++ b/src/map.cpp
@@ -21,9 +21,7 @@ GB_STATIC_ASSERT(gb_size_of(u64) >= gb_size_of(void *));
 
 gb_inline HashKey hashing_proc(void const *data, isize len) {
 	HashKey h = {};
-	// h.key = u128_from_u64(gb_fnv64a(data, len));
 	h.key = gb_fnv64a(data, len);
-
 	return h;
 }
 
@@ -61,7 +59,7 @@ struct MapEntry {
 
 template <typename T>
 struct Map {
-	Array<isize>        hashes;
+	Slice<isize>        hashes;
 	Array<MapEntry<T> > entries;
 };
 
@@ -90,7 +88,8 @@ template <typename T> void  multi_map_remove_all(Map<T> *h, HashKey const &key);
 
 template <typename T>
 gb_inline void map_init(Map<T> *h, gbAllocator a, isize capacity) {
-	array_init(&h->hashes,  a, capacity);
+	capacity = next_pow2_isize(capacity);
+	slice_init(&h->hashes,  a, capacity);
 	array_init(&h->entries, a, 0, capacity);
 	for (isize i = 0; i < capacity; i++) {
 		h->hashes.data[i] = -1;
@@ -99,8 +98,8 @@ gb_inline void map_init(Map<T> *h, gbAllocator a, isize capacity) {
 
 template <typename T>
 gb_inline void map_destroy(Map<T> *h) {
+	slice_free(&h->hashes, h->entries.allocator);
 	array_free(&h->entries);
-	array_free(&h->hashes);
 }
 
 template <typename T>
@@ -116,8 +115,7 @@ template <typename T>
 gb_internal MapFindResult map__find(Map<T> *h, HashKey const &key) {
 	MapFindResult fr = {-1, -1, -1};
 	if (h->hashes.count > 0) {
-		// fr.hash_index  = u128_to_i64(key.key % u128_from_i64(h->hashes.count));
-		fr.hash_index = key.key % h->hashes.count;
+		fr.hash_index = key.key & (h->hashes.count-1);
 		fr.entry_index = h->hashes.data[fr.hash_index];
 		while (fr.entry_index >= 0) {
 			if (hash_key_equal(h->entries.data[fr.entry_index].key, key)) {
@@ -134,7 +132,7 @@ template <typename T>
 gb_internal MapFindResult map__find_from_entry(Map<T> *h, MapEntry<T> *e) {
 	MapFindResult fr = {-1, -1, -1};
 	if (h->hashes.count > 0) {
-		fr.hash_index  = e->key.key % h->hashes.count;
+		fr.hash_index  = e->key.key & (h->hashes.count-1);
 		fr.entry_index = h->hashes.data[fr.hash_index];
 		while (fr.entry_index >= 0) {
 			if (&h->entries.data[fr.entry_index] == e) {
@@ -152,12 +150,9 @@ gb_internal b32 map__full(Map<T> *h) {
 	return 0.75f * h->hashes.count <= h->entries.count;
 }
 
-#define MAP_ARRAY_GROW_FORMULA(x) (4*(x) + 7)
-GB_STATIC_ASSERT(MAP_ARRAY_GROW_FORMULA(0) > 0);
-
 template <typename T>
 gb_inline void map_grow(Map<T> *h) {
-	isize new_count = MAP_ARRAY_GROW_FORMULA(h->entries.count);
+	isize new_count = gb_max(h->hashes.count<<1, 16);
 	map_rehash(h, new_count);
 }
 
@@ -165,12 +160,14 @@ template <typename T>
 void map_rehash(Map<T> *h, isize new_count) {
 	isize i, j;
 	Map<T> nh = {};
-	map_init(&nh, h->hashes.allocator, new_count);
-	array_resize(&nh.hashes, new_count);
-	array_reserve(&nh.entries, h->entries.count);
+	new_count = next_pow2_isize(new_count);
+	nh.hashes = h->hashes;
+	nh.entries.allocator = h->entries.allocator;
+	slice_resize(&nh.hashes, h->entries.allocator, new_count);
 	for (i = 0; i < new_count; i++) {
 		nh.hashes.data[i] = -1;
 	}
+	array_reserve(&nh.entries, ARRAY_GROW_FORMULA(h->entries.count));
 	for (i = 0; i < h->entries.count; i++) {
 		MapEntry<T> *e = &h->entries.data[i];
 		MapFindResult fr;
@@ -190,7 +187,7 @@ void map_rehash(Map<T> *h, isize new_count) {
 			map_grow(&nh);
 		}
 	}
-	map_destroy(h);
+	array_free(&h->entries);
 	*h = nh;
 }
 
@@ -267,8 +264,10 @@ void map_remove(Map<T> *h, HashKey const &key) {
 
 template <typename T>
 gb_inline void map_clear(Map<T> *h) {
-	array_clear(&h->hashes);
 	array_clear(&h->entries);
+	for (isize i = 0; i < h->hashes.count; i++) {
+		h->hashes.data[i] = -1;
+	}
 }
 
 
diff --git a/src/string_map.cpp b/src/string_map.cpp
index 5a488cb2a..1b8f6cf93 100644
--- a/src/string_map.cpp
+++ b/src/string_map.cpp
@@ -23,15 +23,15 @@ gb_inline StringHashKey string_hash_string(String const &s) {
 }
 
 
-bool string_hash_key_equal(StringHashKey a, StringHashKey b) {
+bool string_hash_key_equal(StringHashKey const &a, StringHashKey const &b) {
 	if (a.hash == b.hash) {
 		// NOTE(bill): If two string's hashes collide, compare the strings themselves
 		return a.string == b.string;
 	}
 	return false;
 }
-bool operator==(StringHashKey a, StringHashKey b) { return string_hash_key_equal(a, b); }
-bool operator!=(StringHashKey a, StringHashKey b) { return !string_hash_key_equal(a, b); }
+bool operator==(StringHashKey const &a, StringHashKey const &b) { return string_hash_key_equal(a, b); }
+bool operator!=(StringHashKey const &a, StringHashKey const &b) { return !string_hash_key_equal(a, b); }
 
 template <typename T>
 struct StringMapEntry {
@@ -42,7 +42,7 @@ struct StringMapEntry {
 
 template <typename T>
 struct StringMap {
-	Array<isize>              hashes;
+	Slice<isize>              hashes;
 	Array<StringMapEntry<T> > entries;
 };
 
@@ -69,7 +69,8 @@ template <typename T> void string_map_rehash           (StringMap<T> *h, isize n
 
 template <typename T>
 gb_inline void string_map_init(StringMap<T> *h, gbAllocator a, isize capacity) {
-	array_init(&h->hashes,  a, capacity);
+	capacity = next_pow2_isize(capacity);
+	slice_init(&h->hashes,  a, capacity);
 	array_init(&h->entries, a, 0, capacity);
 	for (isize i = 0; i < capacity; i++) {
 		h->hashes.data[i] = -1;
@@ -78,8 +79,8 @@ gb_inline void string_map_init(StringMap<T> *h, gbAllocator a, isize capacity) {
 
 template <typename T>
 gb_inline void string_map_destroy(StringMap<T> *h) {
+	slice_free(&h->hashes, h->entries.allocator);
 	array_free(&h->entries);
-	array_free(&h->hashes);
 }
 
 template <typename T>
@@ -94,8 +95,8 @@ gb_internal isize string_map__add_entry(StringMap<T> *h, StringHashKey const &ke
 template <typename T>
 gb_internal StringMapFindResult string_map__find(StringMap<T> *h, StringHashKey const &key) {
 	StringMapFindResult fr = {-1, -1, -1};
-	if (h->hashes.count > 0) {
-		fr.hash_index = key.hash % h->hashes.count;
+	if (h->hashes.count != 0) {
+		fr.hash_index = key.hash & (h->hashes.count-1);
 		fr.entry_index = h->hashes.data[fr.hash_index];
 		while (fr.entry_index >= 0) {
 			if (string_hash_key_equal(h->entries.data[fr.entry_index].key, key)) {
@@ -111,8 +112,8 @@ gb_internal StringMapFindResult string_map__find(StringMap<T> *h, StringHashKey
 template <typename T>
 gb_internal StringMapFindResult string_map__find_from_entry(StringMap<T> *h, StringMapEntry<T> *e) {
 	StringMapFindResult fr = {-1, -1, -1};
-	if (h->hashes.count > 0) {
-		fr.hash_index  = e->key.hash % h->hashes.count;
+	if (h->hashes.count != 0) {
+		fr.hash_index  = e->key.hash & (h->hashes.count-1);
 		fr.entry_index = h->hashes.data[fr.hash_index];
 		while (fr.entry_index >= 0) {
 			if (&h->entries.data[fr.entry_index] == e) {
@@ -130,12 +131,9 @@ gb_internal b32 string_map__full(StringMap<T> *h) {
 	return 0.75f * h->hashes.count <= h->entries.count;
 }
 
-#define STRING_MAP_ARRAY_GROW_FORMULA(x) (4*(x) + 7)
-GB_STATIC_ASSERT(STRING_MAP_ARRAY_GROW_FORMULA(0) > 0);
-
 template <typename T>
 gb_inline void string_map_grow(StringMap<T> *h) {
-	isize new_count = STRING_MAP_ARRAY_GROW_FORMULA(h->entries.count);
+	isize new_count = gb_max(h->hashes.count<<1, 16);
 	string_map_rehash(h, new_count);
 }
 
@@ -143,12 +141,14 @@ template <typename T>
 void string_map_rehash(StringMap<T> *h, isize new_count) {
 	isize i, j;
 	StringMap<T> nh = {};
-	string_map_init(&nh, h->hashes.allocator, new_count);
-	array_resize(&nh.hashes, new_count);
-	array_reserve(&nh.entries, h->entries.count);
+	new_count = next_pow2_isize(new_count);
+	nh.hashes = h->hashes;
+	nh.entries.allocator = h->entries.allocator;
+	slice_resize(&nh.hashes, h->entries.allocator, new_count);
 	for (i = 0; i < new_count; i++) {
 		nh.hashes.data[i] = -1;
 	}
+	array_reserve(&nh.entries, ARRAY_GROW_FORMULA(h->entries.count));
 	for (i = 0; i < h->entries.count; i++) {
 		StringMapEntry<T> *e = &h->entries.data[i];
 		StringMapFindResult fr;
@@ -168,7 +168,7 @@ void string_map_rehash(StringMap<T> *h, isize new_count) {
 			string_map_grow(&nh);
 		}
 	}
-	string_map_destroy(h);
+	array_free(&h->entries);
 	*h = nh;
 }
 
@@ -275,7 +275,9 @@ void string_map_remove(StringMap<T> *h, StringHashKey const &key) {
 
 template <typename T>
 gb_inline void string_map_clear(StringMap<T> *h) {
-	array_clear(&h->hashes);
 	array_clear(&h->entries);
+	for (isize i = 0; i < h->hashes.count; i++) {
+		h->hashes.data[i] = -1;
+	}
 }