Merge pull request #4860 from odin-lang/bill/typeid_hash_table

Change `typeid` definition to be based around the canonical type hash

1 files changed, 29 insertions, 16 deletions

diff --git a/src/checker.cpp b/src/checker.cpp
index 678126094..056eef3b2 100644
--- a/src/checker.cpp
+++ b/src/checker.cpp
@@ -6740,30 +6740,43 @@ gb_internal void check_parsed_files(Checker *c) {
 		}
 		array_sort(c->info.type_info_types, type_info_pair_cmp);
 
+		array_init(&c->info.type_info_types_hash_map, heap_allocator(), c->info.type_info_types.count*2 + 1);
 		map_reserve(&c->info.minimum_dependency_type_info_index_map, c->info.type_info_types.count);
 
-		for_array(i, c->info.type_info_types) {
-			auto const &tt = c->info.type_info_types[i];
-			bool exists = map_set_if_not_previously_exists(&c->info.minimum_dependency_type_info_index_map, tt.hash, i);
-			if (!exists) {
-				continue;
-			}
-			for (auto const &entry : c->info.minimum_dependency_type_info_index_map) {
-				if (entry.key != tt.hash) {
+		isize hash_map_len = c->info.type_info_types_hash_map.count;
+		for (auto const &tt : c->info.type_info_types) {
+			isize index = tt.hash % hash_map_len;
+			// NOTE(bill): no need for a sanity check since there
+			// will always be enough space for the entries
+			for (;;) {
+				if (index == 0 || c->info.type_info_types_hash_map[index].hash != 0) {
+					index = (index+1) % hash_map_len;
 					continue;
 				}
-				auto const &other = c->info.type_info_types[entry.value];
-				if (are_types_identical_unique_tuples(tt.type, other.type)) {
-					continue;
+				break;
+			}
+			c->info.type_info_types_hash_map[index] = tt;
+
+			bool exists = map_set_if_not_previously_exists(&c->info.minimum_dependency_type_info_index_map, tt.hash, index);
+			if (exists) {
+				for (auto const &entry : c->info.minimum_dependency_type_info_index_map) {
+					if (entry.key != tt.hash) {
+						continue;
+					}
+					auto const &other = c->info.type_info_types[entry.value];
+					if (are_types_identical_unique_tuples(tt.type, other.type)) {
+						continue;
+					}
+					gbString t = temp_canonical_string(tt.type);
+					gbString o = temp_canonical_string(other.type);
+					GB_PANIC("%s (%s) %llu vs %s (%s) %llu",
+					         type_to_string(tt.type, false),    t, cast(unsigned long long)tt.hash,
+					         type_to_string(other.type, false), o, cast(unsigned long long)other.hash);
 				}
-				gbString t = temp_canonical_string(tt.type);
-				gbString o = temp_canonical_string(other.type);
-				GB_PANIC("%s (%s) %llu vs %s (%s) %llu",
-				         type_to_string(tt.type, false),    t, cast(unsigned long long)tt.hash,
-				         type_to_string(other.type, false), o, cast(unsigned long long)other.hash);
 			}
 		}
 
+
 		GB_ASSERT(c->info.minimum_dependency_type_info_index_map.count <= c->info.type_info_types.count);
 	}