Merge pull request #1273 from odin-lang/compiler-map-improvements

Compiler Map Improvements

1 files changed, 40 insertions, 53 deletions

diff --git a/src/ptr_set.cpp b/src/ptr_set.cpp
index 0ca1921e8..8dd3cb4dc 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 <typename T>
 struct PtrSetEntry {
-	T           ptr;
-	PtrSetIndex next;
+	T        ptr;
+	MapIndex next;
 };
 
 template <typename T>
 struct PtrSet {
-	Slice<PtrSetIndex>    hashes;
+	Slice<MapIndex>    hashes;
 	Array<PtrSetEntry<T>> entries;
 };
 
@@ -40,7 +29,7 @@ void ptr_set_init(PtrSet<T> *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,23 @@ void ptr_set_destroy(PtrSet<T> *s) {
 }
 
 template <typename T>
-gb_internal PtrSetIndex ptr_set__add_entry(PtrSet<T> *s, T ptr) {
+gb_internal MapIndex ptr_set__add_entry(PtrSet<T> *s, T ptr) {
 	PtrSetEntry<T> 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 <typename T>
-gb_internal PtrSetFindResult ptr_set__find(PtrSet<T> *s, T ptr) {
-	PtrSetFindResult fr = {PTR_SET_SENTINEL, PTR_SET_SENTINEL, PTR_SET_SENTINEL};
+gb_internal MapFindResult ptr_set__find(PtrSet<T> *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));
+		u32 hash = ptr_map_hash_key(ptr);
+		fr.hash_index = cast(MapIndex)(hash & (s->hashes.count-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 +68,13 @@ gb_internal PtrSetFindResult ptr_set__find(PtrSet<T> *s, T ptr) {
 }
 
 template <typename T>
-gb_internal PtrSetFindResult ptr_set__find_from_entry(PtrSet<T> *s, PtrSetEntry<T> *e) {
-	PtrSetFindResult fr = {PTR_SET_SENTINEL, PTR_SET_SENTINEL, PTR_SET_SENTINEL};
+gb_internal MapFindResult ptr_set__find_from_entry(PtrSet<T> *s, PtrSetEntry<T> *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));
+		u32 hash = ptr_map_hash_key(e->ptr);
+		fr.hash_index = cast(MapIndex)(hash & (s->hashes.count-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;
 			}
@@ -105,24 +92,24 @@ gb_internal bool ptr_set__full(PtrSet<T> *s) {
 
 template <typename T>
 gb_inline void ptr_set_grow(PtrSet<T> *s) {
-	isize new_count = s->hashes.count*2;
+	isize new_count = gb_max(s->hashes.count<<1, 16);
 	ptr_set_rehash(s, new_count);
 }
 
 template <typename T>
 void ptr_set_reset_entries(PtrSet<T> *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<T> *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 +133,21 @@ 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 != PTR_SET_SENTINEL;
+	return index != MAP_SENTINEL;
 }
 
 // Returns true if it already exists
 template <typename T>
 T ptr_set_add(PtrSet<T> *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 +162,17 @@ 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
 	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 +187,9 @@ bool ptr_set_update(PtrSet<T> *s, T ptr) { // returns true if it previously exis
 
 
 template <typename T>
-void ptr_set__erase(PtrSet<T> *s, PtrSetFindResult fr) {
-	PtrSetFindResult last;
-	if (fr.entry_prev == PTR_SET_SENTINEL) {
+void ptr_set__erase(PtrSet<T> *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 +200,7 @@ void ptr_set__erase(PtrSet<T> *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 +209,8 @@ void ptr_set__erase(PtrSet<T> *s, PtrSetFindResult fr) {
 
 template <typename T>
 void ptr_set_remove(PtrSet<T> *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 +219,6 @@ template <typename T>
 gb_inline void ptr_set_clear(PtrSet<T> *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;
 	}
 }