From e95204908a12d4386ba9bda6de1fed7c73f66d29 Mon Sep 17 00:00:00 2001 From: gingerBill Date: Fri, 5 Nov 2021 16:34:37 +0000 Subject: Add `PtrMap`, begin working change `Map` to `PtrMap` where possible --- src/ptr_map.cpp | 318 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 318 insertions(+) create mode 100644 src/ptr_map.cpp (limited to 'src/ptr_map.cpp') diff --git a/src/ptr_map.cpp b/src/ptr_map.cpp new file mode 100644 index 000000000..af3cf86f9 --- /dev/null +++ b/src/ptr_map.cpp @@ -0,0 +1,318 @@ +#define PTR_MAP_ENABLE_MULTI_MAP 1 + + +template +struct PtrMapEntry { + static_assert(sizeof(K) == sizeof(void *), "Key size must be pointer size"); + + u32 hash; + MapIndex next; + K key; + V value; +}; + +template +struct PtrMap { + Slice hashes; + Array > entries; +}; + + +template +u32 ptr_map_hash_key(K key) { + return gb_fnv32a(&key, gb_size_of(key)); +} + +template void map_init (PtrMap *h, gbAllocator a, isize capacity = 16); +template void map_destroy (PtrMap *h); +template V * map_get (PtrMap *h, K key); +template void map_set (PtrMap *h, K key, V const &value); +template void map_remove (PtrMap *h, K key); +template void map_clear (PtrMap *h); +template void map_grow (PtrMap *h); +template void map_rehash (PtrMap *h, isize new_count); +template void map_reserve (PtrMap *h, isize cap); + +#if PTR_MAP_ENABLE_MULTI_MAP +// Mutlivalued map procedure +template PtrMapEntry * multi_map_find_first(PtrMap *h, K key); +template PtrMapEntry * multi_map_find_next (PtrMap *h, PtrMapEntry *e); + +template isize multi_map_count (PtrMap *h, K key); +template void multi_map_get_all (PtrMap *h, K key, V *items); +template void multi_map_insert (PtrMap *h, K key, V const &value); +template void multi_map_remove (PtrMap *h, K key, PtrMapEntry *e); +template void multi_map_remove_all(PtrMap *h, K key); +#endif + +template +gb_inline void map_init(PtrMap *h, gbAllocator a, isize 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] = MAP_SENTINEL; + } +} + +template +gb_inline void map_destroy(PtrMap *h) { + slice_free(&h->hashes, h->entries.allocator); + array_free(&h->entries); +} + +template +gb_internal MapIndex map__add_entry(PtrMap *h, K key) { + PtrMapEntry e = {}; + e.hash = ptr_map_hash_key(key); + e.key = key; + e.next = MAP_SENTINEL; + array_add(&h->entries, e); + return cast(MapIndex)(h->entries.count-1); +} + +template +gb_internal MapFindResult map__find(PtrMap *h, K key) { + MapFindResult fr = {MAP_SENTINEL, MAP_SENTINEL, MAP_SENTINEL}; + if (h->hashes.count == 0) { + return fr; + } + u32 hash = ptr_map_hash_key(key); + fr.hash_index = cast(MapIndex)(hash & (h->hashes.count-1)); + fr.entry_index = h->hashes.data[fr.hash_index]; + while (fr.entry_index != MAP_SENTINEL) { + if (h->entries.data[fr.entry_index].key == key) { + return fr; + } + fr.entry_prev = fr.entry_index; + fr.entry_index = h->entries.data[fr.entry_index].next; + } + return fr; +} + +template +gb_internal MapFindResult map__find_from_entry(PtrMap *h, PtrMapEntry *e) { + MapFindResult fr = {MAP_SENTINEL, MAP_SENTINEL, MAP_SENTINEL}; + if (h->hashes.count == 0) { + return fr; + } + fr.hash_index = cast(MapIndex)(e->hash & (h->hashes.count-1)); + fr.entry_index = h->hashes.data[fr.hash_index]; + while (fr.entry_index != MAP_SENTINEL) { + if (&h->entries.data[fr.entry_index] == e) { + return fr; + } + fr.entry_prev = fr.entry_index; + fr.entry_index = h->entries.data[fr.entry_index].next; + } + return fr; +} + +template +gb_internal b32 map__full(PtrMap *h) { + return 0.75f * h->hashes.count <= h->entries.count; +} + +template +gb_inline void map_grow(PtrMap *h) { + isize new_count = gb_max(h->hashes.count<<1, 16); + map_rehash(h, new_count); +} + +template +void map_reset_entries(PtrMap *h) { + for (isize i = 0; i < h->hashes.count; i++) { + h->hashes.data[i] = MAP_SENTINEL; + } + for (isize i = 0; i < h->entries.count; i++) { + MapFindResult fr; + PtrMapEntry *e = &h->entries.data[i]; + e->next = MAP_SENTINEL; + fr = map__find_from_entry(h, e); + if (fr.entry_prev == MAP_SENTINEL) { + h->hashes[fr.hash_index] = cast(MapIndex)i; + } else { + h->entries[fr.entry_prev].next = cast(MapIndex)i; + } + } +} + +template +void map_reserve(PtrMap *h, isize cap) { + array_reserve(&h->entries, cap); + if (h->entries.count*2 < h->hashes.count) { + return; + } + slice_resize(&h->hashes, h->entries.allocator, cap*2); + map_reset_entries(h); +} + + +template +void map_rehash(PtrMap *h, isize new_count) { + map_reserve(h, new_count); +} + +template +V *map_get(PtrMap *h, K key) { + isize index = map__find(h, key).entry_index; + if (index != MAP_SENTINEL) { + return &h->entries.data[index].value; + } + return nullptr; +} + +template +V &map_must_get(PtrMap *h, K key) { + isize index = map__find(h, key).entry_index; + GB_ASSERT(index != MAP_SENTINEL); + return h->entries.data[index].value; +} + +template +void map_set(PtrMap *h, K key, V const &value) { + MapIndex index; + MapFindResult fr; + if (h->hashes.count == 0) { + map_grow(h); + } + fr = map__find(h, key); + if (fr.entry_index != MAP_SENTINEL) { + index = fr.entry_index; + } else { + index = map__add_entry(h, key); + if (fr.entry_prev != MAP_SENTINEL) { + h->entries.data[fr.entry_prev].next = index; + } else { + h->hashes.data[fr.hash_index] = index; + } + } + h->entries.data[index].value = value; + + if (map__full(h)) { + map_grow(h); + } +} + + +template +void map__erase(PtrMap *h, MapFindResult const &fr) { + MapFindResult last; + if (fr.entry_prev == MAP_SENTINEL) { + h->hashes.data[fr.hash_index] = h->entries.data[fr.entry_index].next; + } else { + h->entries.data[fr.entry_prev].next = h->entries.data[fr.entry_index].next; + } + if (fr.entry_index == h->entries.count-1) { + array_pop(&h->entries); + return; + } + h->entries.data[fr.entry_index] = h->entries.data[h->entries.count-1]; + array_pop(&h->entries); + + last = map__find(h, h->entries.data[fr.entry_index].key); + if (last.entry_prev != MAP_SENTINEL) { + h->entries.data[last.entry_prev].next = fr.entry_index; + } else { + h->hashes.data[last.hash_index] = fr.entry_index; + } +} + +template +void map_remove(PtrMap *h, HashKey const &key) { + MapFindResult fr = map__find(h, key); + if (fr.entry_index != MAP_SENTINEL) { + map__erase(h, fr); + } +} + +template +gb_inline void map_clear(PtrMap *h) { + array_clear(&h->entries); + for (isize i = 0; i < h->hashes.count; i++) { + h->hashes.data[i] = MAP_SENTINEL; + } +} + + +#if PTR_MAP_ENABLE_MULTI_MAP +template +PtrMapEntry *multi_map_find_first(PtrMap *h, HashKey const &key) { + isize i = map__find(h, key).entry_index; + if (i == MAP_SENTINEL) { + return nullptr; + } + return &h->entries.data[i]; +} + +template +PtrMapEntry *multi_map_find_next(PtrMap *h, PtrMapEntry *e) { + isize i = e->next; + while (i != MAP_SENTINEL) { + if (hash_key_equal(h->entries.data[i].key, e->key)) { + return &h->entries.data[i]; + } + i = h->entries.data[i].next; + } + return nullptr; +} + +template +isize multi_map_count(PtrMap *h, HashKey const &key) { + isize count = 0; + PtrMapEntry *e = multi_map_find_first(h, key); + while (e != nullptr) { + count++; + e = multi_map_find_next(h, e); + } + return count; +} + +template +void multi_map_get_all(PtrMap *h, K key, V *items) { + isize i = 0; + PtrMapEntry *e = multi_map_find_first(h, key); + while (e != nullptr) { + items[i++] = e->value; + e = multi_map_find_next(h, e); + } +} + +template +void multi_map_insert(PtrMap *h, K key, V const &value) { + MapFindResult fr; + MapIndex i; + if (h->hashes.count == 0) { + map_grow(h); + } + // Make + fr = map__find(h, key); + i = map__add_entry(h, key); + if (fr.entry_prev == MAP_SENTINEL) { + h->hashes.data[fr.hash_index] = i; + } else { + h->entries.data[fr.entry_prev].next = i; + } + h->entries.data[i].next = fr.entry_index; + h->entries.data[i].value = value; + // Grow if needed + if (map__full(h)) { + map_grow(h); + } +} + +template +void multi_map_remove(PtrMap *h, HashKey const &key, PtrMapEntry *e) { + MapFindResult fr = map__find_from_entry(h, e); + if (fr.entry_index != MAP_SENTINEL) { + map__erase(h, fr); + } +} + +template +void multi_map_remove_all(PtrMap *h, HashKey const &key) { + while (map_get(h, key) != nullptr) { + map_remove(h, key); + } +} +#endif -- cgit v1.2.3 From 924faa58b43b5e727436cd50bded45b9c43ac3a4 Mon Sep 17 00:00:00 2001 From: gingerBill Date: Fri, 5 Nov 2021 16:45:27 +0000 Subject: Correct `map_remove(PtrMap)` --- src/checker.cpp | 18 +++++++++--------- src/checker.hpp | 2 +- src/ptr_map.cpp | 2 +- 3 files changed, 11 insertions(+), 11 deletions(-) (limited to 'src/ptr_map.cpp') diff --git a/src/checker.cpp b/src/checker.cpp index 643673afe..044342760 100644 --- a/src/checker.cpp +++ b/src/checker.cpp @@ -1086,7 +1086,7 @@ Scope *scope_of_node(Ast *node) { } ExprInfo *check_get_expr_info(CheckerContext *c, Ast *expr) { if (c->untyped != nullptr) { - ExprInfo **found = map_get(c->untyped, hash_pointer(expr)); + ExprInfo **found = map_get(c->untyped, expr); if (found) { return *found; } @@ -1094,7 +1094,7 @@ ExprInfo *check_get_expr_info(CheckerContext *c, Ast *expr) { } else { mutex_lock(&c->info->global_untyped_mutex); defer (mutex_unlock(&c->info->global_untyped_mutex)); - ExprInfo **found = map_get(&c->info->global_untyped, hash_pointer(expr)); + ExprInfo **found = map_get(&c->info->global_untyped, expr); if (found) { return *found; } @@ -1104,23 +1104,23 @@ ExprInfo *check_get_expr_info(CheckerContext *c, Ast *expr) { void check_set_expr_info(CheckerContext *c, Ast *expr, AddressingMode mode, Type *type, ExactValue value) { if (c->untyped != nullptr) { - map_set(c->untyped, hash_pointer(expr), make_expr_info(mode, type, value, false)); + map_set(c->untyped, expr, make_expr_info(mode, type, value, false)); } else { mutex_lock(&c->info->global_untyped_mutex); - map_set(&c->info->global_untyped, hash_pointer(expr), make_expr_info(mode, type, value, false)); + map_set(&c->info->global_untyped, expr, make_expr_info(mode, type, value, false)); mutex_unlock(&c->info->global_untyped_mutex); } } void check_remove_expr_info(CheckerContext *c, Ast *e) { if (c->untyped != nullptr) { - map_remove(c->untyped, hash_pointer(e)); - GB_ASSERT(map_get(c->untyped, hash_pointer(e)) == nullptr); + map_remove(c->untyped, e); + GB_ASSERT(map_get(c->untyped, e) == nullptr); } else { auto *untyped = &c->info->global_untyped; mutex_lock(&c->info->global_untyped_mutex); - map_remove(untyped, hash_pointer(e)); - GB_ASSERT(map_get(untyped, hash_pointer(e)) == nullptr); + map_remove(untyped, e); + GB_ASSERT(map_get(untyped, e) == nullptr); mutex_unlock(&c->info->global_untyped_mutex); } } @@ -4952,7 +4952,7 @@ void add_untyped_expressions(CheckerInfo *cinfo, UntypedExprInfoMap *untyped) { return; } for_array(i, untyped->entries) { - Ast *expr = cast(Ast *)cast(uintptr)untyped->entries[i].key.key; + Ast *expr = untyped->entries[i].key; ExprInfo *info = untyped->entries[i].value; if (expr != nullptr && info != nullptr) { mpmc_enqueue(&cinfo->checker->global_untyped_queue, UntypedExprInfo{expr, info}); diff --git a/src/checker.hpp b/src/checker.hpp index e7f152eb2..700cd7e54 100644 --- a/src/checker.hpp +++ b/src/checker.hpp @@ -264,7 +264,7 @@ struct UntypedExprInfo { ExprInfo *info; }; -typedef Map UntypedExprInfoMap; // Key: Ast * +typedef PtrMap UntypedExprInfoMap; typedef MPMCQueue ProcBodyQueue; // CheckerInfo stores all the symbol information for a type-checked program diff --git a/src/ptr_map.cpp b/src/ptr_map.cpp index af3cf86f9..153b40b7e 100644 --- a/src/ptr_map.cpp +++ b/src/ptr_map.cpp @@ -219,7 +219,7 @@ void map__erase(PtrMap *h, MapFindResult const &fr) { } template -void map_remove(PtrMap *h, HashKey const &key) { +void map_remove(PtrMap *h, K key) { MapFindResult fr = map__find(h, key); if (fr.entry_index != MAP_SENTINEL) { map__erase(h, fr); -- cgit v1.2.3 From c38d6dc9592cff3bfd21c45076cd82df2d763eb2 Mon Sep 17 00:00:00 2001 From: gingerBill Date: Fri, 5 Nov 2021 16:46:09 +0000 Subject: Remove HashKey usage for `PtrMap` calls --- src/ptr_map.cpp | 8 ++++---- 1 file changed, 4 insertions(+), 4 deletions(-) (limited to 'src/ptr_map.cpp') diff --git a/src/ptr_map.cpp b/src/ptr_map.cpp index 153b40b7e..4659fcf9b 100644 --- a/src/ptr_map.cpp +++ b/src/ptr_map.cpp @@ -237,7 +237,7 @@ gb_inline void map_clear(PtrMap *h) { #if PTR_MAP_ENABLE_MULTI_MAP template -PtrMapEntry *multi_map_find_first(PtrMap *h, HashKey const &key) { +PtrMapEntry *multi_map_find_first(PtrMap *h, K key) { isize i = map__find(h, key).entry_index; if (i == MAP_SENTINEL) { return nullptr; @@ -258,7 +258,7 @@ PtrMapEntry *multi_map_find_next(PtrMap *h, PtrMapEntry *e) { } template -isize multi_map_count(PtrMap *h, HashKey const &key) { +isize multi_map_count(PtrMap *h, K key) { isize count = 0; PtrMapEntry *e = multi_map_find_first(h, key); while (e != nullptr) { @@ -302,7 +302,7 @@ void multi_map_insert(PtrMap *h, K key, V const &value) { } template -void multi_map_remove(PtrMap *h, HashKey const &key, PtrMapEntry *e) { +void multi_map_remove(PtrMap *h, K key, PtrMapEntry *e) { MapFindResult fr = map__find_from_entry(h, e); if (fr.entry_index != MAP_SENTINEL) { map__erase(h, fr); @@ -310,7 +310,7 @@ void multi_map_remove(PtrMap *h, HashKey const &key, PtrMapEntry *e) } template -void multi_map_remove_all(PtrMap *h, HashKey const &key) { +void multi_map_remove_all(PtrMap *h, K key) { while (map_get(h, key) != nullptr) { map_remove(h, key); } -- cgit v1.2.3 From 6646348e1a0086d9a2341d0866f787ffc2608c8f Mon Sep 17 00:00:00 2001 From: gingerBill Date: Fri, 5 Nov 2021 17:03:02 +0000 Subject: Increase usage of `PtrMap` --- src/build_settings.cpp | 2 +- src/check_expr.cpp | 4 ++-- src/check_type.cpp | 6 +++--- src/checker.cpp | 40 ++++++++++++++++++---------------------- src/checker.hpp | 4 ++-- src/docs_writer.cpp | 44 +++++++++++++++++--------------------------- src/llvm_backend_stmt.cpp | 2 +- src/main.cpp | 2 +- src/ptr_map.cpp | 8 ++++++-- 9 files changed, 51 insertions(+), 61 deletions(-) (limited to 'src/ptr_map.cpp') diff --git a/src/build_settings.cpp b/src/build_settings.cpp index fa8922f61..182975d7b 100644 --- a/src/build_settings.cpp +++ b/src/build_settings.cpp @@ -244,7 +244,7 @@ struct BuildContext { gbAffinity affinity; isize thread_count; - Map defined_values; // Key: + PtrMap defined_values; }; diff --git a/src/check_expr.cpp b/src/check_expr.cpp index 2ad3cc4a6..7a0273805 100644 --- a/src/check_expr.cpp +++ b/src/check_expr.cpp @@ -314,7 +314,7 @@ bool find_or_generate_polymorphic_procedure(CheckerContext *old_c, Entity *base_ return false; } - auto *found_gen_procs = map_get(&info->gen_procs, hash_pointer(base_entity->identifier)); + auto *found_gen_procs = map_get(&info->gen_procs, base_entity->identifier.load()); if (found_gen_procs) { auto procs = *found_gen_procs; for_array(i, procs) { @@ -423,7 +423,7 @@ bool find_or_generate_polymorphic_procedure(CheckerContext *old_c, Entity *base_ } else { auto array = array_make(heap_allocator()); array_add(&array, entity); - map_set(&info->gen_procs, hash_pointer(base_entity->identifier), array); + map_set(&info->gen_procs, base_entity->identifier.load(), array); } if (poly_proc_data) { diff --git a/src/check_type.cpp b/src/check_type.cpp index 05d5c674a..398967af8 100644 --- a/src/check_type.cpp +++ b/src/check_type.cpp @@ -228,7 +228,7 @@ Entity *find_polymorphic_record_entity(CheckerContext *ctx, Type *original_type, mutex_lock(&ctx->info->gen_types_mutex); defer (mutex_unlock(&ctx->info->gen_types_mutex)); - auto *found_gen_types = map_get(&ctx->info->gen_types, hash_pointer(original_type)); + auto *found_gen_types = map_get(&ctx->info->gen_types, original_type); if (found_gen_types != nullptr) { // GB_ASSERT_MSG(ordered_operands.count >= param_count, "%td >= %td", ordered_operands.count, param_count); @@ -311,13 +311,13 @@ void add_polymorphic_record_entity(CheckerContext *ctx, Ast *node, Type *named_t named_type->Named.type_name = e; mutex_lock(&ctx->info->gen_types_mutex); - auto *found_gen_types = map_get(&ctx->info->gen_types, hash_pointer(original_type)); + auto *found_gen_types = map_get(&ctx->info->gen_types, original_type); if (found_gen_types) { array_add(found_gen_types, e); } else { auto array = array_make(heap_allocator()); array_add(&array, e); - map_set(&ctx->info->gen_types, hash_pointer(original_type), array); + map_set(&ctx->info->gen_types, original_type, array); } mutex_unlock(&ctx->info->gen_types_mutex); } diff --git a/src/checker.cpp b/src/checker.cpp index 044342760..16e699ee3 100644 --- a/src/checker.cpp +++ b/src/checker.cpp @@ -810,7 +810,7 @@ void init_universal(void) { bool defined_values_double_declaration = false; for_array(i, bc->defined_values.entries) { - char const *name = cast(char const *)cast(uintptr)bc->defined_values.entries[i].key.key; + char const *name = bc->defined_values.entries[i].key; ExactValue value = bc->defined_values.entries[i].value; GB_ASSERT(value.kind != ExactValue_Invalid); @@ -2199,7 +2199,7 @@ void add_entity_dependency_from_procedure_parameters(Map *M, } Array generate_entity_dependency_graph(CheckerInfo *info, gbAllocator allocator) { - Map M = {}; // Key: Entity * + PtrMap M = {}; map_init(&M, allocator, info->entities.count); defer (map_destroy(&M)); for_array(i, info->entities) { @@ -2207,7 +2207,7 @@ Array generate_entity_dependency_graph(CheckerInfo *info, gbA if (is_entity_a_dependency(e)) { EntityGraphNode *n = gb_alloc_item(allocator, EntityGraphNode); n->entity = e; - map_set(&M, hash_pointer(e), n); + map_set(&M, e, n); } } @@ -2227,9 +2227,7 @@ Array generate_entity_dependency_graph(CheckerInfo *info, gbA } GB_ASSERT(dep != nullptr); if (is_entity_a_dependency(dep)) { - EntityGraphNode **m_ = map_get(&M, hash_pointer(dep)); - GB_ASSERT(m_ != nullptr); - EntityGraphNode *m = *m_; + EntityGraphNode *m = map_must_get(&M, dep); entity_graph_node_set_add(&n->succ, m); entity_graph_node_set_add(&m->pred, n); } @@ -2244,7 +2242,7 @@ Array generate_entity_dependency_graph(CheckerInfo *info, gbA for_array(i, M.entries) { auto *entry = &M.entries[i]; - auto *e = cast(Entity *)cast(uintptr)entry->key.key; + auto *e = entry->key; EntityGraphNode *n = entry->value; if (e->kind == Entity_Procedure) { @@ -3728,7 +3726,7 @@ String path_to_entity_name(String name, String fullpath, bool strip_extension=tr #if 1 -void add_import_dependency_node(Checker *c, Ast *decl, Map *M) { +void add_import_dependency_node(Checker *c, Ast *decl, PtrMap *M) { AstPackage *parent_pkg = decl->file->pkg; switch (decl->kind) { @@ -3752,11 +3750,11 @@ void add_import_dependency_node(Checker *c, Ast *decl, Map *M ImportGraphNode *m = nullptr; ImportGraphNode *n = nullptr; - found_node = map_get(M, hash_pointer(pkg)); + found_node = map_get(M, pkg); GB_ASSERT(found_node != nullptr); m = *found_node; - found_node = map_get(M, hash_pointer(parent_pkg)); + found_node = map_get(M, parent_pkg); GB_ASSERT(found_node != nullptr); n = *found_node; @@ -3794,14 +3792,14 @@ void add_import_dependency_node(Checker *c, Ast *decl, Map *M } Array generate_import_dependency_graph(Checker *c) { - Map M = {}; // Key: AstPackage * + PtrMap M = {}; map_init(&M, heap_allocator(), 2*c->parser->packages.count); defer (map_destroy(&M)); for_array(i, c->parser->packages) { AstPackage *pkg = c->parser->packages[i]; ImportGraphNode *n = import_graph_node_create(heap_allocator(), pkg); - map_set(&M, hash_pointer(pkg), n); + map_set(&M, pkg, n); } // Calculate edges for graph M @@ -4507,9 +4505,9 @@ void check_import_entities(Checker *c) { } -Array find_entity_path(Entity *start, Entity *end, Map *visited = nullptr); +Array find_entity_path(Entity *start, Entity *end, PtrSet *visited = nullptr); -bool find_entity_path_tuple(Type *tuple, Entity *end, Map *visited, Array *path_) { +bool find_entity_path_tuple(Type *tuple, Entity *end, PtrSet *visited, Array *path_) { GB_ASSERT(path_ != nullptr); if (tuple == nullptr) { return false; @@ -4541,26 +4539,24 @@ bool find_entity_path_tuple(Type *tuple, Entity *end, Map *visited, Ar return false; } -Array find_entity_path(Entity *start, Entity *end, Map *visited) { - Map visited_ = {}; +Array find_entity_path(Entity *start, Entity *end, PtrSet *visited) { + PtrSet visited_ = {}; bool made_visited = false; if (visited == nullptr) { made_visited = true; - map_init(&visited_, heap_allocator()); + ptr_set_init(&visited_, heap_allocator()); visited = &visited_; } defer (if (made_visited) { - map_destroy(&visited_); + ptr_set_destroy(&visited_); }); Array empty_path = {}; - HashKey key = hash_pointer(start); - - if (map_get(visited, key) != nullptr) { + if (ptr_set_exists(visited, start)) { return empty_path; } - map_set(visited, key, start); + ptr_set_add(visited, start); DeclInfo *decl = start->decl_info; if (decl) { diff --git a/src/checker.hpp b/src/checker.hpp index 700cd7e54..ab8fce3d8 100644 --- a/src/checker.hpp +++ b/src/checker.hpp @@ -316,8 +316,8 @@ struct CheckerInfo { RecursiveMutex gen_procs_mutex; RecursiveMutex gen_types_mutex; - Map > gen_procs; // Key: Ast * | Identifier -> Entity - Map > gen_types; // Key: Type * + PtrMap > gen_procs; // Key: Ast * | Identifier -> Entity + PtrMap > gen_types; BlockingMutex type_info_mutex; // NOT recursive Array type_info_types; diff --git a/src/docs_writer.cpp b/src/docs_writer.cpp index 1603ca22c..e7254e16b 100644 --- a/src/docs_writer.cpp +++ b/src/docs_writer.cpp @@ -26,12 +26,10 @@ struct OdinDocWriter { StringMap string_cache; - Map file_cache; // Key: AstFile * - Map pkg_cache; // Key: AstPackage * - Map entity_cache; // Key: Entity * - Map entity_id_cache; // Key: OdinDocEntityIndex - Map type_cache; // Key: Type * - Map type_id_cache; // Key: OdinDocTypeIndex + PtrMap file_cache; + PtrMap pkg_cache; + PtrMap entity_cache; + PtrMap type_cache; OdinDocWriterItemTracker files; OdinDocWriterItemTracker pkgs; @@ -61,9 +59,7 @@ void odin_doc_writer_prepare(OdinDocWriter *w) { map_init(&w->file_cache, a); map_init(&w->pkg_cache, a); map_init(&w->entity_cache, a); - map_init(&w->entity_id_cache, a); map_init(&w->type_cache, a); - map_init(&w->type_id_cache, a); odin_doc_writer_item_tracker_init(&w->files, 1); odin_doc_writer_item_tracker_init(&w->pkgs, 1); @@ -81,9 +77,7 @@ void odin_doc_writer_destroy(OdinDocWriter *w) { map_destroy(&w->file_cache); map_destroy(&w->pkg_cache); map_destroy(&w->entity_cache); - map_destroy(&w->entity_id_cache); map_destroy(&w->type_cache); - map_destroy(&w->type_id_cache); } @@ -115,9 +109,7 @@ void odin_doc_writer_start_writing(OdinDocWriter *w) { map_clear(&w->file_cache); map_clear(&w->pkg_cache); map_clear(&w->entity_cache); - map_clear(&w->entity_id_cache); map_clear(&w->type_cache); - map_clear(&w->type_id_cache); isize total_size = odin_doc_writer_calc_total_size(w); total_size = align_formula_isize(total_size, 8); @@ -267,7 +259,7 @@ OdinDocPosition odin_doc_token_pos_cast(OdinDocWriter *w, TokenPos const &pos) { if (pos.file_id != 0) { AstFile *file = get_ast_file_from_id(pos.file_id); if (file != nullptr) { - OdinDocFileIndex *file_index_found = map_get(&w->file_cache, hash_pointer(file)); + OdinDocFileIndex *file_index_found = map_get(&w->file_cache, file); GB_ASSERT(file_index_found != nullptr); file_index = *file_index_found; } @@ -483,16 +475,16 @@ OdinDocTypeIndex odin_doc_type(OdinDocWriter *w, Type *type) { if (type == nullptr) { return 0; } - OdinDocTypeIndex *found = map_get(&w->type_cache, hash_pointer(type)); + OdinDocTypeIndex *found = map_get(&w->type_cache, type); if (found) { return *found; } for_array(i, w->type_cache.entries) { // NOTE(bill): THIS IS SLOW - Type *other = cast(Type *)cast(uintptr)w->type_cache.entries[i].key.key; + Type *other = w->type_cache.entries[i].key; if (are_types_identical(type, other)) { OdinDocTypeIndex index = w->type_cache.entries[i].value; - map_set(&w->type_cache, hash_pointer(type), index); + map_set(&w->type_cache, type, index); return index; } } @@ -502,8 +494,7 @@ OdinDocTypeIndex odin_doc_type(OdinDocWriter *w, Type *type) { OdinDocType doc_type = {}; OdinDocTypeIndex type_index = 0; type_index = odin_doc_write_item(w, &w->types, &doc_type, &dst); - map_set(&w->type_cache, hash_pointer(type), type_index); - map_set(&w->type_id_cache, hash_integer(type_index), type); + map_set(&w->type_cache, type, type_index); switch (type->kind) { case Type_Basic: @@ -776,12 +767,12 @@ OdinDocEntityIndex odin_doc_add_entity(OdinDocWriter *w, Entity *e) { return 0; } - OdinDocEntityIndex *prev_index = map_get(&w->entity_cache, hash_pointer(e)); + OdinDocEntityIndex *prev_index = map_get(&w->entity_cache, e); if (prev_index) { return *prev_index; } - if (e->pkg != nullptr && map_get(&w->pkg_cache, hash_pointer(e->pkg)) == nullptr) { + if (e->pkg != nullptr && map_get(&w->pkg_cache, e->pkg) == nullptr) { return 0; } @@ -789,8 +780,7 @@ OdinDocEntityIndex odin_doc_add_entity(OdinDocWriter *w, Entity *e) { OdinDocEntity* dst = nullptr; OdinDocEntityIndex doc_entity_index = odin_doc_write_item(w, &w->entities, &doc_entity, &dst); - map_set(&w->entity_cache, hash_pointer(e), doc_entity_index); - map_set(&w->entity_id_cache, hash_integer(doc_entity_index), e); + map_set(&w->entity_cache, e, doc_entity_index); Ast *type_expr = nullptr; @@ -901,7 +891,7 @@ void odin_doc_update_entities(OdinDocWriter *w) { defer (array_free(&entities)); for_array(i, w->entity_cache.entries) { - Entity *e = cast(Entity *)cast(uintptr)w->entity_cache.entries[i].key.key; + Entity *e = w->entity_cache.entries[i].key; entities[i] = e; } for_array(i, entities) { @@ -912,7 +902,7 @@ void odin_doc_update_entities(OdinDocWriter *w) { } for_array(i, w->entity_cache.entries) { - Entity *e = cast(Entity *)cast(uintptr)w->entity_cache.entries[i].key.key; + Entity *e = w->entity_cache.entries[i].key; OdinDocEntityIndex entity_index = w->entity_cache.entries[i].value; OdinDocTypeIndex type_index = odin_doc_type(w, e->type); @@ -955,7 +945,7 @@ OdinDocArray odin_doc_add_pkg_entities(OdinDocWriter *w, Ast if (pkg->scope == nullptr) { return {}; } - if (map_get(&w->pkg_cache, hash_pointer(pkg)) == nullptr) { + if (map_get(&w->pkg_cache, pkg) == nullptr) { return {}; } @@ -1056,7 +1046,7 @@ void odin_doc_write_docs(OdinDocWriter *w) { OdinDocPkg *dst = nullptr; OdinDocPkgIndex pkg_index = odin_doc_write_item(w, &w->pkgs, &doc_pkg, &dst); - map_set(&w->pkg_cache, hash_pointer(pkg), pkg_index); + map_set(&w->pkg_cache, pkg, pkg_index); auto file_indices = array_make(heap_allocator(), 0, pkg->files.count); defer (array_free(&file_indices)); @@ -1067,7 +1057,7 @@ void odin_doc_write_docs(OdinDocWriter *w) { doc_file.pkg = pkg_index; doc_file.name = odin_doc_write_string(w, file->fullpath); OdinDocFileIndex file_index = odin_doc_write_item(w, &w->files, &doc_file); - map_set(&w->file_cache, hash_pointer(file), file_index); + map_set(&w->file_cache, file, file_index); array_add(&file_indices, file_index); } diff --git a/src/llvm_backend_stmt.cpp b/src/llvm_backend_stmt.cpp index 4f57dbfa6..9d3d2c949 100644 --- a/src/llvm_backend_stmt.cpp +++ b/src/llvm_backend_stmt.cpp @@ -83,7 +83,7 @@ void lb_build_constant_value_decl(lbProcedure *p, AstValueDecl *vd) { DeclInfo *decl = decl_info_of_entity(e); ast_node(pl, ProcLit, decl->proc_lit); if (pl->body != nullptr) { - auto *found = map_get(&info->gen_procs, hash_pointer(ident)); + auto *found = map_get(&info->gen_procs, ident); if (found) { auto procs = *found; for_array(i, procs) { diff --git a/src/main.cpp b/src/main.cpp index e79e7203d..3fed50c80 100644 --- a/src/main.cpp +++ b/src/main.cpp @@ -1109,7 +1109,7 @@ bool parse_build_flags(Array args) { break; } - HashKey key = hash_pointer(string_intern(name)); + char const *key = string_intern(name); if (map_get(&build_context.defined_values, key) != nullptr) { gb_printf_err("Defined constant '%.*s' already exists\n", LIT(name)); diff --git a/src/ptr_map.cpp b/src/ptr_map.cpp index 4659fcf9b..2387a2a20 100644 --- a/src/ptr_map.cpp +++ b/src/ptr_map.cpp @@ -18,8 +18,12 @@ struct PtrMap { }; -template -u32 ptr_map_hash_key(K key) { +u32 ptr_map_hash_key(void const *key) { + // TODO(bill): Improve ptr_map_hash_key + return gb_fnv32a(&key, gb_size_of(key)); +} +u32 ptr_map_hash_key(uintptr key) { + // TODO(bill): Improve ptr_map_hash_key return gb_fnv32a(&key, gb_size_of(key)); } -- cgit v1.2.3 From 541beb615b745b45f2cc82813014a3e04f1a3231 Mon Sep 17 00:00:00 2001 From: gingerBill Date: Fri, 5 Nov 2021 17:13:07 +0000 Subject: Move more things to `PtrMap` --- src/check_stmt.cpp | 9 ++++----- src/common.cpp | 8 ++++---- src/exact_value.cpp | 33 ++++++++++++++------------------- src/ptr_map.cpp | 2 +- 4 files changed, 23 insertions(+), 29 deletions(-) (limited to 'src/ptr_map.cpp') diff --git a/src/check_stmt.cpp b/src/check_stmt.cpp index 103ffa071..24ad0eec1 100644 --- a/src/check_stmt.cpp +++ b/src/check_stmt.cpp @@ -699,7 +699,7 @@ struct TypeAndToken { }; -void add_constant_switch_case(CheckerContext *ctx, Map *seen, Operand operand, bool use_expr = true) { +void add_constant_switch_case(CheckerContext *ctx, PtrMap *seen, Operand operand, bool use_expr = true) { if (operand.mode != Addressing_Constant) { return; } @@ -707,7 +707,7 @@ void add_constant_switch_case(CheckerContext *ctx, Map *seen, Oper return; } - HashKey key = hash_exact_value(operand.value); + uintptr key = hash_exact_value(operand.value); TypeAndToken *found = map_get(seen, key); if (found != nullptr) { isize count = multi_map_count(seen, key); @@ -964,7 +964,7 @@ void check_switch_stmt(CheckerContext *ctx, Ast *node, u32 mod_flags) { } } - Map seen = {}; // NOTE(bill): Multimap, Key: ExactValue + PtrMap seen = {}; // NOTE(bill): Multimap, Key: ExactValue map_init(&seen, heap_allocator()); defer (map_destroy(&seen)); @@ -1133,8 +1133,7 @@ void check_switch_stmt(CheckerContext *ctx, Ast *node, u32 mod_flags) { continue; } ExactValue v = f->Constant.value; - HashKey key = hash_exact_value(v); - auto found = map_get(&seen, key); + auto found = map_get(&seen, hash_exact_value(v)); if (!found) { array_add(&unhandled, f); } diff --git a/src/common.cpp b/src/common.cpp index 5d7c87b6d..f7a0653ac 100644 --- a/src/common.cpp +++ b/src/common.cpp @@ -290,13 +290,13 @@ struct StringIntern { char str[1]; }; -Map string_intern_map = {}; // Key: u64 +PtrMap string_intern_map = {}; // Key: u64 gb_global Arena string_intern_arena = {}; char const *string_intern(char const *text, isize len) { u64 hash = gb_fnv64a(text, len); - u64 key = hash ? hash : 1; - StringIntern **found = map_get(&string_intern_map, hash_integer(key)); + uintptr key = cast(uintptr)(hash ? hash : 1); + StringIntern **found = map_get(&string_intern_map, key); if (found) { for (StringIntern *it = *found; it != nullptr; it = it->next) { if (it->len == len && gb_strncmp(it->str, (char *)text, len) == 0) { @@ -310,7 +310,7 @@ char const *string_intern(char const *text, isize len) { new_intern->next = found ? *found : nullptr; gb_memmove(new_intern->str, text, len); new_intern->str[len] = 0; - map_set(&string_intern_map, hash_integer(key), new_intern); + map_set(&string_intern_map, key, new_intern); return new_intern->str; } diff --git a/src/exact_value.cpp b/src/exact_value.cpp index 363c6d863..fd90278e5 100644 --- a/src/exact_value.cpp +++ b/src/exact_value.cpp @@ -63,44 +63,39 @@ struct ExactValue { gb_global ExactValue const empty_exact_value = {}; -HashKey hash_exact_value(ExactValue v) { +uintptr hash_exact_value(ExactValue v) { mutex_lock(&hash_exact_value_mutex); defer (mutex_unlock(&hash_exact_value_mutex)); - HashKey empty = {}; switch (v.kind) { case ExactValue_Invalid: - return empty; + return 0; case ExactValue_Bool: - return hash_integer(u64(v.value_bool)); + return gb_fnv32a(&v.value_bool, gb_size_of(v.value_bool)); case ExactValue_String: - { - char const *str = string_intern(v.value_string); - return hash_pointer(str); - } + return ptr_map_hash_key(string_intern(v.value_string)); case ExactValue_Integer: { - HashKey key = hashing_proc(v.value_integer.dp, gb_size_of(*v.value_integer.dp) * v.value_integer.used); + u32 key = gb_fnv32a(v.value_integer.dp, gb_size_of(*v.value_integer.dp) * v.value_integer.used); u8 last = (u8)v.value_integer.sign; - key.key = (key.key ^ last) * 0x100000001b3ll; - return key; + return (key ^ last) * 0x01000193; } case ExactValue_Float: - return hash_f64(v.value_float); + return gb_fnv32a(&v.value_float, gb_size_of(v.value_float)); case ExactValue_Pointer: - return hash_integer(v.value_pointer); + return ptr_map_hash_key(v.value_pointer); case ExactValue_Complex: - return hashing_proc(v.value_complex, gb_size_of(Complex128)); + return gb_fnv32a(v.value_complex, gb_size_of(Complex128)); case ExactValue_Quaternion: - return hashing_proc(v.value_quaternion, gb_size_of(Quaternion256)); + return gb_fnv32a(v.value_quaternion, gb_size_of(Quaternion256)); case ExactValue_Compound: - return hash_pointer(v.value_compound); + return ptr_map_hash_key(v.value_compound); case ExactValue_Procedure: - return hash_pointer(v.value_procedure); + return ptr_map_hash_key(v.value_procedure); case ExactValue_Typeid: - return hash_pointer(v.value_typeid); + return ptr_map_hash_key(v.value_typeid); } - return hashing_proc(&v, gb_size_of(ExactValue)); + return gb_fnv32a(&v, gb_size_of(ExactValue)); } diff --git a/src/ptr_map.cpp b/src/ptr_map.cpp index 2387a2a20..0a61d300f 100644 --- a/src/ptr_map.cpp +++ b/src/ptr_map.cpp @@ -253,7 +253,7 @@ template PtrMapEntry *multi_map_find_next(PtrMap *h, PtrMapEntry *e) { isize i = e->next; while (i != MAP_SENTINEL) { - if (hash_key_equal(h->entries.data[i].key, e->key)) { + if (h->entries.data[i].key == e->key) { return &h->entries.data[i]; } i = h->entries.data[i].next; -- cgit v1.2.3 From 0af69f8cda4e4bed8cfc732fd53bd93be55916f3 Mon Sep 17 00:00:00 2001 From: gingerBill Date: Fri, 5 Nov 2021 17:16:37 +0000 Subject: Remove `map.cpp` code --- src/checker.hpp | 7 -- src/map.cpp | 363 -------------------------------------------------------- src/ptr_map.cpp | 9 ++ 3 files changed, 9 insertions(+), 370 deletions(-) delete mode 100644 src/map.cpp (limited to 'src/ptr_map.cpp') diff --git a/src/checker.hpp b/src/checker.hpp index ab8fce3d8..6511dad32 100644 --- a/src/checker.hpp +++ b/src/checker.hpp @@ -406,13 +406,6 @@ gb_global AstPackage *intrinsics_pkg = nullptr; gb_global AstPackage *config_pkg = nullptr; -HashKey hash_node (Ast *node) { return hash_pointer(node); } -HashKey hash_ast_file (AstFile *file) { return hash_pointer(file); } -HashKey hash_entity (Entity *e) { return hash_pointer(e); } -HashKey hash_type (Type *t) { return hash_pointer(t); } -HashKey hash_decl_info(DeclInfo *decl) { return hash_pointer(decl); } - - // CheckerInfo API TypeAndValue type_and_value_of_expr (Ast *expr); Type * type_of_expr (Ast *expr); diff --git a/src/map.cpp b/src/map.cpp deleted file mode 100644 index cc91e51d4..000000000 --- a/src/map.cpp +++ /dev/null @@ -1,363 +0,0 @@ -// A `Map` is an unordered hash table which can allow for a key to point to multiple values -// with the use of the `multi_*` procedures. -// TODO(bill): I should probably allow the `multi_map_*` stuff to be #ifdefed out - -#define MAP_ENABLE_MULTI_MAP 1 - -#ifndef MAP_UTIL_STUFF -#define MAP_UTIL_STUFF -// NOTE(bill): This util stuff is the same for every `Map` - -typedef u32 MapIndex; - -struct MapFindResult { - MapIndex hash_index; - MapIndex entry_prev; - MapIndex entry_index; -}; - -enum : MapIndex { MAP_SENTINEL = ~(MapIndex)0 }; - - -struct HashKey { - u64 key; -}; -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 = fnv64a(data, len); - return h; -} - -gb_inline HashKey hash_pointer(void const *ptr) { - HashKey h = {}; - h.key = cast(u64)cast(uintptr)ptr; - return h; -} - -gb_inline HashKey hash_integer(u64 u) { - HashKey h = {}; - h.key = u; - return h; -} -gb_inline HashKey hash_f64(f64 f) { - HashKey h = {}; - h.key = bit_cast(f); - return h; -} - -gb_inline bool hash_key_equal(HashKey a, HashKey b) { - return a.key == b.key; -} -gb_inline bool operator==(HashKey a, HashKey b) { return hash_key_equal(a, b); } -gb_inline bool operator!=(HashKey a, HashKey b) { return !hash_key_equal(a, b); } - -#endif - -template -struct MapEntry { - HashKey key; - MapIndex next; - T value; -}; - -template -struct Map { - Slice hashes; - Array > entries; -}; - - -template void map_init (Map *h, gbAllocator a, isize capacity = 16); -template void map_destroy (Map *h); -template T * map_get (Map *h, HashKey const &key); -template T & map_must_get (Map *h, HashKey const &key); -template void map_set (Map *h, HashKey const &key, T const &value); -template void map_remove (Map *h, HashKey const &key); -template void map_clear (Map *h); -template void map_grow (Map *h); -template void map_rehash (Map *h, isize new_count); -template void map_reserve (Map *h, isize cap); - -#if MAP_ENABLE_MULTI_MAP -// Mutlivalued map procedure -template MapEntry * multi_map_find_first(Map *h, HashKey const &key); -template MapEntry * multi_map_find_next (Map *h, MapEntry *e); - -template isize multi_map_count (Map *h, HashKey const &key); -template void multi_map_get_all (Map *h, HashKey const &key, T *items); -template void multi_map_insert (Map *h, HashKey const &key, T const &value); -template void multi_map_remove (Map *h, HashKey const &key, MapEntry *e); -template void multi_map_remove_all(Map *h, HashKey const &key); -#endif - -template -gb_inline void map_init(Map *h, gbAllocator a, isize 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] = MAP_SENTINEL; - } -} - -template -gb_inline void map_destroy(Map *h) { - slice_free(&h->hashes, h->entries.allocator); - array_free(&h->entries); -} - -template -gb_internal MapIndex map__add_entry(Map *h, HashKey const &key) { - MapEntry e = {}; - e.key = key; - e.next = MAP_SENTINEL; - array_add(&h->entries, e); - return cast(MapIndex)(h->entries.count-1); -} - -template -gb_internal MapFindResult map__find(Map *h, HashKey const &key) { - MapFindResult fr = {MAP_SENTINEL, MAP_SENTINEL, MAP_SENTINEL}; - if (h->hashes.count == 0) { - return fr; - } - fr.hash_index = cast(MapIndex)(key.key & (h->hashes.count-1)); - fr.entry_index = h->hashes.data[fr.hash_index]; - while (fr.entry_index != MAP_SENTINEL) { - if (hash_key_equal(h->entries.data[fr.entry_index].key, key)) { - return fr; - } - fr.entry_prev = fr.entry_index; - fr.entry_index = h->entries.data[fr.entry_index].next; - } - return fr; -} - -template -gb_internal MapFindResult map__find_from_entry(Map *h, MapEntry *e) { - MapFindResult fr = {MAP_SENTINEL, MAP_SENTINEL, MAP_SENTINEL}; - if (h->hashes.count == 0) { - return fr; - } - fr.hash_index = cast(MapIndex)(e->key.key & (h->hashes.count-1)); - fr.entry_index = h->hashes.data[fr.hash_index]; - while (fr.entry_index != MAP_SENTINEL) { - if (&h->entries.data[fr.entry_index] == e) { - return fr; - } - fr.entry_prev = fr.entry_index; - fr.entry_index = h->entries.data[fr.entry_index].next; - } - return fr; -} - -template -gb_internal b32 map__full(Map *h) { - return 0.75f * h->hashes.count <= h->entries.count; -} - -template -gb_inline void map_grow(Map *h) { - isize new_count = gb_max(h->hashes.count<<1, 16); - map_rehash(h, new_count); -} - -template -void map_reset_entries(Map *h) { - for (isize i = 0; i < h->hashes.count; i++) { - h->hashes.data[i] = MAP_SENTINEL; - } - for (isize i = 0; i < h->entries.count; i++) { - MapFindResult fr; - MapEntry *e = &h->entries.data[i]; - e->next = MAP_SENTINEL; - fr = map__find_from_entry(h, e); - if (fr.entry_prev == MAP_SENTINEL) { - h->hashes[fr.hash_index] = cast(MapIndex)i; - } else { - h->entries[fr.entry_prev].next = cast(MapIndex)i; - } - } -} - -template -void map_reserve(Map *h, isize cap) { - array_reserve(&h->entries, cap); - if (h->entries.count*2 < h->hashes.count) { - return; - } - slice_resize(&h->hashes, h->entries.allocator, cap*2); - map_reset_entries(h); -} - - -template -void map_rehash(Map *h, isize new_count) { - map_reserve(h, new_count); -} - -template -T *map_get(Map *h, HashKey const &key) { - isize index = map__find(h, key).entry_index; - if (index != MAP_SENTINEL) { - return &h->entries.data[index].value; - } - return nullptr; -} - -template -T &map_must_get(Map *h, HashKey const &key) { - isize index = map__find(h, key).entry_index; - GB_ASSERT(index != MAP_SENTINEL); - return h->entries.data[index].value; -} - -template -void map_set(Map *h, HashKey const &key, T const &value) { - MapIndex index; - MapFindResult fr; - if (h->hashes.count == 0) { - map_grow(h); - } - fr = map__find(h, key); - if (fr.entry_index != MAP_SENTINEL) { - index = fr.entry_index; - } else { - index = map__add_entry(h, key); - if (fr.entry_prev != MAP_SENTINEL) { - h->entries.data[fr.entry_prev].next = index; - } else { - h->hashes.data[fr.hash_index] = index; - } - } - h->entries.data[index].value = value; - - if (map__full(h)) { - map_grow(h); - } -} - - -template -void map__erase(Map *h, MapFindResult const &fr) { - MapFindResult last; - if (fr.entry_prev == MAP_SENTINEL) { - h->hashes.data[fr.hash_index] = h->entries.data[fr.entry_index].next; - } else { - h->entries.data[fr.entry_prev].next = h->entries.data[fr.entry_index].next; - } - if (fr.entry_index == h->entries.count-1) { - array_pop(&h->entries); - return; - } - h->entries.data[fr.entry_index] = h->entries.data[h->entries.count-1]; - array_pop(&h->entries); - - last = map__find(h, h->entries.data[fr.entry_index].key); - if (last.entry_prev != MAP_SENTINEL) { - h->entries.data[last.entry_prev].next = fr.entry_index; - } else { - h->hashes.data[last.hash_index] = fr.entry_index; - } -} - -template -void map_remove(Map *h, HashKey const &key) { - MapFindResult fr = map__find(h, key); - if (fr.entry_index != MAP_SENTINEL) { - map__erase(h, fr); - } -} - -template -gb_inline void map_clear(Map *h) { - array_clear(&h->entries); - for (isize i = 0; i < h->hashes.count; i++) { - h->hashes.data[i] = MAP_SENTINEL; - } -} - - -#if MAP_ENABLE_MULTI_MAP -template -MapEntry *multi_map_find_first(Map *h, HashKey const &key) { - isize i = map__find(h, key).entry_index; - if (i == MAP_SENTINEL) { - return nullptr; - } - return &h->entries.data[i]; -} - -template -MapEntry *multi_map_find_next(Map *h, MapEntry *e) { - isize i = e->next; - while (i != MAP_SENTINEL) { - if (hash_key_equal(h->entries.data[i].key, e->key)) { - return &h->entries.data[i]; - } - i = h->entries.data[i].next; - } - return nullptr; -} - -template -isize multi_map_count(Map *h, HashKey const &key) { - isize count = 0; - MapEntry *e = multi_map_find_first(h, key); - while (e != nullptr) { - count++; - e = multi_map_find_next(h, e); - } - return count; -} - -template -void multi_map_get_all(Map *h, HashKey const &key, T *items) { - isize i = 0; - MapEntry *e = multi_map_find_first(h, key); - while (e != nullptr) { - items[i++] = e->value; - e = multi_map_find_next(h, e); - } -} - -template -void multi_map_insert(Map *h, HashKey const &key, T const &value) { - MapFindResult fr; - MapIndex i; - if (h->hashes.count == 0) { - map_grow(h); - } - // Make - fr = map__find(h, key); - i = map__add_entry(h, key); - if (fr.entry_prev == MAP_SENTINEL) { - h->hashes.data[fr.hash_index] = i; - } else { - h->entries.data[fr.entry_prev].next = i; - } - h->entries.data[i].next = fr.entry_index; - h->entries.data[i].value = value; - // Grow if needed - if (map__full(h)) { - map_grow(h); - } -} - -template -void multi_map_remove(Map *h, HashKey const &key, MapEntry *e) { - MapFindResult fr = map__find_from_entry(h, e); - if (fr.entry_index != MAP_SENTINEL) { - map__erase(h, fr); - } -} - -template -void multi_map_remove_all(Map *h, HashKey const &key) { - while (map_get(h, key) != nullptr) { - map_remove(h, key); - } -} -#endif diff --git a/src/ptr_map.cpp b/src/ptr_map.cpp index 0a61d300f..19443d8a1 100644 --- a/src/ptr_map.cpp +++ b/src/ptr_map.cpp @@ -1,5 +1,14 @@ #define PTR_MAP_ENABLE_MULTI_MAP 1 +typedef u32 MapIndex; + +struct MapFindResult { + MapIndex hash_index; + MapIndex entry_prev; + MapIndex entry_index; +}; + +enum : MapIndex { MAP_SENTINEL = ~(MapIndex)0 }; template struct PtrMapEntry { -- cgit v1.2.3 From 26e3daf5adc6c59f7bf7c621abc4640ba7a8bda0 Mon Sep 17 00:00:00 2001 From: gingerBill Date: Fri, 5 Nov 2021 17:24:19 +0000 Subject: Unify `MapFindResult` types --- src/common.cpp | 3 +- src/ptr_map.cpp | 4 +-- src/ptr_set.cpp | 85 ++++++++++++++++++++++---------------------------- src/string_map.cpp | 91 ++++++++++++++++++++++-------------------------------- src/string_set.cpp | 64 ++++++++++++++++++-------------------- 5 files changed, 107 insertions(+), 140 deletions(-) (limited to 'src/ptr_map.cpp') diff --git a/src/common.cpp b/src/common.cpp index f7a0653ac..cca478421 100644 --- a/src/common.cpp +++ b/src/common.cpp @@ -275,10 +275,9 @@ gb_global String global_module_path = {0}; gb_global bool global_module_path_set = false; -#include "string_map.cpp" -#include "map.cpp" #include "ptr_map.cpp" #include "ptr_set.cpp" +#include "string_map.cpp" #include "string_set.cpp" #include "priority_queue.cpp" #include "thread_pool.cpp" diff --git a/src/ptr_map.cpp b/src/ptr_map.cpp index 19443d8a1..7937e6968 100644 --- a/src/ptr_map.cpp +++ b/src/ptr_map.cpp @@ -29,11 +29,11 @@ struct PtrMap { u32 ptr_map_hash_key(void const *key) { // TODO(bill): Improve ptr_map_hash_key - return gb_fnv32a(&key, gb_size_of(key)); + return fnv32a(&key, gb_size_of(key)); } u32 ptr_map_hash_key(uintptr key) { // TODO(bill): Improve ptr_map_hash_key - return gb_fnv32a(&key, gb_size_of(key)); + return fnv32a(&key, gb_size_of(key)); } template void map_init (PtrMap *h, gbAllocator a, isize capacity = 16); diff --git a/src/ptr_set.cpp b/src/ptr_set.cpp index 0ca1921e8..4ab3d3259 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 struct PtrSetEntry { - T ptr; - PtrSetIndex next; + T ptr; + MapIndex next; }; template struct PtrSet { - Slice hashes; + Slice hashes; Array> entries; }; @@ -40,7 +29,7 @@ void ptr_set_init(PtrSet *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,24 @@ void ptr_set_destroy(PtrSet *s) { } template -gb_internal PtrSetIndex ptr_set__add_entry(PtrSet *s, T ptr) { +gb_internal MapIndex ptr_set__add_entry(PtrSet *s, T ptr) { PtrSetEntry 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 -gb_internal PtrSetFindResult ptr_set__find(PtrSet *s, T ptr) { - PtrSetFindResult fr = {PTR_SET_SENTINEL, PTR_SET_SENTINEL, PTR_SET_SENTINEL}; +gb_internal MapFindResult ptr_set__find(PtrSet *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)); + fr.hash_index = cast(MapIndex)(hash & (n-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 +69,14 @@ gb_internal PtrSetFindResult ptr_set__find(PtrSet *s, T ptr) { } template -gb_internal PtrSetFindResult ptr_set__find_from_entry(PtrSet *s, PtrSetEntry *e) { - PtrSetFindResult fr = {PTR_SET_SENTINEL, PTR_SET_SENTINEL, PTR_SET_SENTINEL}; +gb_internal MapFindResult ptr_set__find_from_entry(PtrSet *s, PtrSetEntry *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)); + fr.hash_index = cast(MapIndex)(hash & (n-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; } @@ -112,17 +101,17 @@ gb_inline void ptr_set_grow(PtrSet *s) { template void ptr_set_reset_entries(PtrSet *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 *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 +135,21 @@ void ptr_set_rehash(PtrSet *s, isize new_count) { template gb_inline bool ptr_set_exists(PtrSet *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 T ptr_set_add(PtrSet *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 +164,17 @@ T ptr_set_add(PtrSet *s, T ptr) { template bool ptr_set_update(PtrSet *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 +189,9 @@ bool ptr_set_update(PtrSet *s, T ptr) { // returns true if it previously exis template -void ptr_set__erase(PtrSet *s, PtrSetFindResult fr) { - PtrSetFindResult last; - if (fr.entry_prev == PTR_SET_SENTINEL) { +void ptr_set__erase(PtrSet *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 +202,7 @@ void ptr_set__erase(PtrSet *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 +211,8 @@ void ptr_set__erase(PtrSet *s, PtrSetFindResult fr) { template void ptr_set_remove(PtrSet *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 +221,6 @@ template gb_inline void ptr_set_clear(PtrSet *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; } } diff --git a/src/string_map.cpp b/src/string_map.cpp index 448af624d..218a45482 100644 --- a/src/string_map.cpp +++ b/src/string_map.cpp @@ -1,28 +1,11 @@ -// NOTE(bill): This util stuff is the same for every `Map` - -typedef u32 StringMapIndex; - -struct StringMapFindResult { - StringMapIndex hash_index; - StringMapIndex entry_prev; - StringMapIndex entry_index; -}; - -enum : StringMapIndex { STRING_MAP_SENTINEL = ~(StringMapIndex)0 }; - - struct StringHashKey { - u64 hash; + u32 hash; String string; }; -u64 string_hashing_proc(void const *data, isize len) { - return fnv64a(data, len); -} - gb_inline StringHashKey string_hash_string(String const &s) { StringHashKey hash_key = {}; - hash_key.hash = string_hashing_proc(s.text, s.len); + hash_key.hash = fnv32a(s.text, s.len); hash_key.string = s; return hash_key; } @@ -40,14 +23,14 @@ bool operator!=(StringHashKey const &a, StringHashKey const &b) { return !string template struct StringMapEntry { - StringHashKey key; - StringMapIndex next; - T value; + StringHashKey key; + MapIndex next; + T value; }; template struct StringMap { - Slice hashes; + Slice hashes; Array > entries; }; @@ -79,7 +62,7 @@ gb_inline void string_map_init(StringMap *h, gbAllocator a, 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] = STRING_MAP_SENTINEL; + h->hashes.data[i] = MAP_SENTINEL; } } @@ -90,21 +73,21 @@ gb_inline void string_map_destroy(StringMap *h) { } template -gb_internal StringMapIndex string_map__add_entry(StringMap *h, StringHashKey const &key) { +gb_internal MapIndex string_map__add_entry(StringMap *h, StringHashKey const &key) { StringMapEntry e = {}; e.key = key; - e.next = STRING_MAP_SENTINEL; + e.next = MAP_SENTINEL; array_add(&h->entries, e); - return cast(StringMapIndex)(h->entries.count-1); + return cast(MapIndex)(h->entries.count-1); } template -gb_internal StringMapFindResult string_map__find(StringMap *h, StringHashKey const &key) { - StringMapFindResult fr = {STRING_MAP_SENTINEL, STRING_MAP_SENTINEL, STRING_MAP_SENTINEL}; +gb_internal MapFindResult string_map__find(StringMap *h, StringHashKey const &key) { + MapFindResult fr = {MAP_SENTINEL, MAP_SENTINEL, MAP_SENTINEL}; if (h->hashes.count != 0) { - fr.hash_index = cast(StringMapIndex)(key.hash & (h->hashes.count-1)); + fr.hash_index = cast(MapIndex)(key.hash & (h->hashes.count-1)); fr.entry_index = h->hashes.data[fr.hash_index]; - while (fr.entry_index != STRING_MAP_SENTINEL) { + while (fr.entry_index != MAP_SENTINEL) { if (string_hash_key_equal(h->entries.data[fr.entry_index].key, key)) { return fr; } @@ -116,12 +99,12 @@ gb_internal StringMapFindResult string_map__find(StringMap *h, StringHashKey } template -gb_internal StringMapFindResult string_map__find_from_entry(StringMap *h, StringMapEntry *e) { - StringMapFindResult fr = {STRING_MAP_SENTINEL, STRING_MAP_SENTINEL, STRING_MAP_SENTINEL}; +gb_internal MapFindResult string_map__find_from_entry(StringMap *h, StringMapEntry *e) { + MapFindResult fr = {MAP_SENTINEL, MAP_SENTINEL, MAP_SENTINEL}; if (h->hashes.count != 0) { - fr.hash_index = cast(StringMapIndex)(e->key.hash & (h->hashes.count-1)); + fr.hash_index = cast(MapIndex)(e->key.hash & (h->hashes.count-1)); fr.entry_index = h->hashes.data[fr.hash_index]; - while (fr.entry_index != STRING_MAP_SENTINEL) { + while (fr.entry_index != MAP_SENTINEL) { if (&h->entries.data[fr.entry_index] == e) { return fr; } @@ -147,17 +130,17 @@ gb_inline void string_map_grow(StringMap *h) { template void string_map_reset_entries(StringMap *h) { for (isize i = 0; i < h->hashes.count; i++) { - h->hashes.data[i] = STRING_MAP_SENTINEL; + h->hashes.data[i] = MAP_SENTINEL; } for (isize i = 0; i < h->entries.count; i++) { - StringMapFindResult fr; + MapFindResult fr; StringMapEntry *e = &h->entries.data[i]; - e->next = STRING_MAP_SENTINEL; + e->next = MAP_SENTINEL; fr = string_map__find_from_entry(h, e); - if (fr.entry_prev == STRING_MAP_SENTINEL) { - h->hashes[fr.hash_index] = cast(StringMapIndex)i; + if (fr.entry_prev == MAP_SENTINEL) { + h->hashes[fr.hash_index] = cast(MapIndex)i; } else { - h->entries[fr.entry_prev].next = cast(StringMapIndex)i; + h->entries[fr.entry_prev].next = cast(MapIndex)i; } } } @@ -181,7 +164,7 @@ void string_map_rehash(StringMap *h, isize new_count) { template T *string_map_get(StringMap *h, StringHashKey const &key) { isize index = string_map__find(h, key).entry_index; - if (index != STRING_MAP_SENTINEL) { + if (index != MAP_SENTINEL) { return &h->entries.data[index].value; } return nullptr; @@ -200,7 +183,7 @@ gb_inline T *string_map_get(StringMap *h, char const *key) { template T &string_map_must_get(StringMap *h, StringHashKey const &key) { isize index = string_map__find(h, key).entry_index; - GB_ASSERT(index != STRING_MAP_SENTINEL); + GB_ASSERT(index != MAP_SENTINEL); return h->entries.data[index].value; } @@ -216,17 +199,17 @@ gb_inline T &string_map_must_get(StringMap *h, char const *key) { template void string_map_set(StringMap *h, StringHashKey const &key, T const &value) { - StringMapIndex index; - StringMapFindResult fr; + MapIndex index; + MapFindResult fr; if (h->hashes.count == 0) { string_map_grow(h); } fr = string_map__find(h, key); - if (fr.entry_index != STRING_MAP_SENTINEL) { + if (fr.entry_index != MAP_SENTINEL) { index = fr.entry_index; } else { index = string_map__add_entry(h, key); - if (fr.entry_prev != STRING_MAP_SENTINEL) { + if (fr.entry_prev != MAP_SENTINEL) { h->entries.data[fr.entry_prev].next = index; } else { h->hashes.data[fr.hash_index] = index; @@ -251,9 +234,9 @@ gb_inline void string_map_set(StringMap *h, char const *key, T const &value) template -void string_map__erase(StringMap *h, StringMapFindResult const &fr) { - StringMapFindResult last; - if (fr.entry_prev == STRING_MAP_SENTINEL) { +void string_map__erase(StringMap *h, MapFindResult const &fr) { + MapFindResult last; + if (fr.entry_prev == MAP_SENTINEL) { h->hashes.data[fr.hash_index] = h->entries.data[fr.entry_index].next; } else { h->entries.data[fr.entry_prev].next = h->entries.data[fr.entry_index].next; @@ -264,7 +247,7 @@ void string_map__erase(StringMap *h, StringMapFindResult const &fr) { } h->entries.data[fr.entry_index] = h->entries.data[h->entries.count-1]; last = string_map__find(h, h->entries.data[fr.entry_index].key); - if (last.entry_prev != STRING_MAP_SENTINEL) { + if (last.entry_prev != MAP_SENTINEL) { h->entries.data[last.entry_prev].next = fr.entry_index; } else { h->hashes.data[last.hash_index] = fr.entry_index; @@ -273,8 +256,8 @@ void string_map__erase(StringMap *h, StringMapFindResult const &fr) { template void string_map_remove(StringMap *h, StringHashKey const &key) { - StringMapFindResult fr = string_map__find(h, key); - if (fr.entry_index != STRING_MAP_SENTINEL) { + MapFindResult fr = string_map__find(h, key); + if (fr.entry_index != MAP_SENTINEL) { string_map__erase(h, fr); } } @@ -283,7 +266,7 @@ template gb_inline void string_map_clear(StringMap *h) { array_clear(&h->entries); for (isize i = 0; i < h->hashes.count; i++) { - h->hashes.data[i] = STRING_MAP_SENTINEL; + h->hashes.data[i] = MAP_SENTINEL; } } diff --git a/src/string_set.cpp b/src/string_set.cpp index 671b2c9ff..1f2ea96a4 100644 --- a/src/string_set.cpp +++ b/src/string_set.cpp @@ -1,17 +1,11 @@ -struct StringSetFindResult { - isize hash_index; - isize entry_prev; - isize entry_index; -}; - struct StringSetEntry { - u64 hash; - isize next; - String value; + u32 hash; + MapIndex next; + String value; }; struct StringSet { - Array hashes; + Array hashes; Array entries; }; @@ -36,22 +30,22 @@ gb_inline void string_set_destroy(StringSet *s) { array_free(&s->hashes); } -gb_internal isize string_set__add_entry(StringSet *s, StringHashKey const &key) { +gb_internal MapIndex string_set__add_entry(StringSet *s, StringHashKey const &key) { StringSetEntry e = {}; e.hash = key.hash; - e.next = -1; + e.next = MAP_SENTINEL; e.value = key.string; array_add(&s->entries, e); - return s->entries.count-1; + return cast(MapIndex)(s->entries.count-1); } -gb_internal StringSetFindResult string_set__find(StringSet *s, StringHashKey const &key) { - StringSetFindResult fr = {-1, -1, -1}; +gb_internal MapFindResult string_set__find(StringSet *s, StringHashKey const &key) { + MapFindResult fr = {MAP_SENTINEL, MAP_SENTINEL, MAP_SENTINEL}; if (s->hashes.count > 0) { // fr.hash_index = u128_to_i64(key.key % u128_from_i64(s->hashes.count)); - fr.hash_index = key.hash % s->hashes.count; + fr.hash_index = cast(MapIndex)(((u64)key.hash) % s->hashes.count); fr.entry_index = s->hashes[fr.hash_index]; - while (fr.entry_index >= 0) { + while (fr.entry_index != MAP_SENTINEL) { auto const &entry = s->entries[fr.entry_index]; if (entry.hash == key.hash && entry.value == key.string) { return fr; @@ -79,21 +73,21 @@ void string_set_rehash(StringSet *s, isize new_count) { array_resize(&ns.hashes, new_count); array_reserve(&ns.entries, s->entries.count); for (i = 0; i < new_count; i++) { - ns.hashes[i] = -1; + ns.hashes[i] = MAP_SENTINEL; } for (i = 0; i < s->entries.count; i++) { StringSetEntry *e = &s->entries[i]; - StringSetFindResult fr; + MapFindResult fr; if (ns.hashes.count == 0) { string_set_grow(&ns); } StringHashKey key = {e->hash, e->value}; fr = string_set__find(&ns, key); j = string_set__add_entry(&ns, key); - if (fr.entry_prev < 0) { - ns.hashes[fr.hash_index] = j; + if (fr.entry_prev == MAP_SENTINEL) { + ns.hashes[fr.hash_index] = cast(MapIndex)j; } else { - ns.entries[fr.entry_prev].next = j; + ns.entries[fr.entry_prev].next = cast(MapIndex)j; } ns.entries[j].next = fr.entry_index; ns.entries[j].value = e->value; @@ -108,22 +102,22 @@ void string_set_rehash(StringSet *s, isize new_count) { gb_inline bool string_set_exists(StringSet *s, String const &str) { StringHashKey key = string_hash_string(str); isize index = string_set__find(s, key).entry_index; - return index >= 0; + return index != MAP_SENTINEL; } void string_set_add(StringSet *s, String const &str) { - isize index; - StringSetFindResult fr; + MapIndex index; + MapFindResult fr; StringHashKey key = string_hash_string(str); if (s->hashes.count == 0) { string_set_grow(s); } fr = string_set__find(s, key); - if (fr.entry_index >= 0) { + if (fr.entry_index != MAP_SENTINEL) { index = fr.entry_index; } else { index = string_set__add_entry(s, key); - if (fr.entry_prev >= 0) { + if (fr.entry_prev != MAP_SENTINEL) { s->entries[fr.entry_prev].next = index; } else { s->hashes[fr.hash_index] = index; @@ -137,9 +131,9 @@ void string_set_add(StringSet *s, String const &str) { } -void string_set__erase(StringSet *s, StringSetFindResult fr) { - StringSetFindResult last; - if (fr.entry_prev < 0) { +void string_set__erase(StringSet *s, MapFindResult fr) { + MapFindResult last; + if (fr.entry_prev == MAP_SENTINEL) { s->hashes[fr.hash_index] = s->entries[fr.entry_index].next; } else { s->entries[fr.entry_prev].next = s->entries[fr.entry_index].next; @@ -152,7 +146,7 @@ void string_set__erase(StringSet *s, StringSetFindResult fr) { *entry = s->entries[s->entries.count-1]; StringHashKey key = {entry->hash, entry->value}; last = string_set__find(s, key); - if (last.entry_prev >= 0) { + if (last.entry_prev != MAP_SENTINEL) { s->entries[last.entry_prev].next = fr.entry_index; } else { s->hashes[last.hash_index] = fr.entry_index; @@ -161,13 +155,15 @@ void string_set__erase(StringSet *s, StringSetFindResult fr) { void string_set_remove(StringSet *s, String const &str) { StringHashKey key = string_hash_string(str); - StringSetFindResult fr = string_set__find(s, key); - if (fr.entry_index >= 0) { + MapFindResult fr = string_set__find(s, key); + if (fr.entry_index != MAP_SENTINEL) { string_set__erase(s, fr); } } gb_inline void string_set_clear(StringSet *s) { - array_clear(&s->hashes); array_clear(&s->entries); + for_array(i, s->hashes) { + s->hashes.data[i] = MAP_SENTINEL; + } } -- cgit v1.2.3 From 7be18b4a80ea1a52bb6d9d01d158d3eada9ca40e Mon Sep 17 00:00:00 2001 From: gingerBill Date: Fri, 5 Nov 2021 17:36:00 +0000 Subject: Be more correct with `MapIndex` usage --- src/ptr_map.cpp | 8 ++++---- 1 file changed, 4 insertions(+), 4 deletions(-) (limited to 'src/ptr_map.cpp') diff --git a/src/ptr_map.cpp b/src/ptr_map.cpp index 7937e6968..ac74dcfbc 100644 --- a/src/ptr_map.cpp +++ b/src/ptr_map.cpp @@ -168,7 +168,7 @@ void map_rehash(PtrMap *h, isize new_count) { template V *map_get(PtrMap *h, K key) { - isize index = map__find(h, key).entry_index; + MapIndex index = map__find(h, key).entry_index; if (index != MAP_SENTINEL) { return &h->entries.data[index].value; } @@ -177,7 +177,7 @@ V *map_get(PtrMap *h, K key) { template V &map_must_get(PtrMap *h, K key) { - isize index = map__find(h, key).entry_index; + MapIndex index = map__find(h, key).entry_index; GB_ASSERT(index != MAP_SENTINEL); return h->entries.data[index].value; } @@ -251,7 +251,7 @@ gb_inline void map_clear(PtrMap *h) { #if PTR_MAP_ENABLE_MULTI_MAP template PtrMapEntry *multi_map_find_first(PtrMap *h, K key) { - isize i = map__find(h, key).entry_index; + MapIndex i = map__find(h, key).entry_index; if (i == MAP_SENTINEL) { return nullptr; } @@ -260,7 +260,7 @@ PtrMapEntry *multi_map_find_first(PtrMap *h, K key) { template PtrMapEntry *multi_map_find_next(PtrMap *h, PtrMapEntry *e) { - isize i = e->next; + MapIndex i = e->next; while (i != MAP_SENTINEL) { if (h->entries.data[i].key == e->key) { return &h->entries.data[i]; -- cgit v1.2.3 From 899cc719905b1b2f261c74867a322e8db9c1ac44 Mon Sep 17 00:00:00 2001 From: gingerBill Date: Fri, 5 Nov 2021 17:55:09 +0000 Subject: Improve `ptr_map_hash_key` --- src/ptr_map.cpp | 36 +++++++++++++++++++++++++++--------- 1 file changed, 27 insertions(+), 9 deletions(-) (limited to 'src/ptr_map.cpp') diff --git a/src/ptr_map.cpp b/src/ptr_map.cpp index ac74dcfbc..66a6f0fc5 100644 --- a/src/ptr_map.cpp +++ b/src/ptr_map.cpp @@ -14,10 +14,9 @@ template struct PtrMapEntry { static_assert(sizeof(K) == sizeof(void *), "Key size must be pointer size"); - u32 hash; - MapIndex next; K key; V value; + MapIndex next; }; template @@ -27,14 +26,33 @@ struct PtrMap { }; -u32 ptr_map_hash_key(void const *key) { - // TODO(bill): Improve ptr_map_hash_key - return fnv32a(&key, gb_size_of(key)); -} u32 ptr_map_hash_key(uintptr key) { +#if defined(GB_ARCH_64_BIT) // TODO(bill): Improve ptr_map_hash_key - return fnv32a(&key, gb_size_of(key)); + u32 key0 = (u32)(key & 0xffffffff); + u32 key1 = (u32)(key >> 32); + + u32 word; + u32 state = 0; + + state += key0 * 747796405u + 2891336453u; + word = ((state >> ((state >> 28u) + 4u)) ^ state) * 277803737u; + state = (word >> 22u) ^ word; + state += key1 * 747796405u + 2891336453u; + word = ((state >> ((state >> 28u) + 4u)) ^ state) * 277803737u; + state = (word >> 22u) ^ word; + return state; + +#elif defined(GB_ARCH_32_BIT) + u32 state = ((u32)key) * 747796405u + 2891336453u; + u32 word = ((state >> ((state >> 28u) + 4u)) ^ state) * 277803737u; + return (word >> 22u) ^ word; +#endif } +u32 ptr_map_hash_key(void const *key) { + return ptr_map_hash_key((uintptr)key); +} + template void map_init (PtrMap *h, gbAllocator a, isize capacity = 16); template void map_destroy (PtrMap *h); @@ -77,7 +95,6 @@ gb_inline void map_destroy(PtrMap *h) { template gb_internal MapIndex map__add_entry(PtrMap *h, K key) { PtrMapEntry e = {}; - e.hash = ptr_map_hash_key(key); e.key = key; e.next = MAP_SENTINEL; array_add(&h->entries, e); @@ -109,7 +126,8 @@ gb_internal MapFindResult map__find_from_entry(PtrMap *h, PtrMapEntryhashes.count == 0) { return fr; } - fr.hash_index = cast(MapIndex)(e->hash & (h->hashes.count-1)); + u32 hash = ptr_map_hash_key(e->key); + fr.hash_index = cast(MapIndex)(hash & (h->hashes.count-1)); fr.entry_index = h->hashes.data[fr.hash_index]; while (fr.entry_index != MAP_SENTINEL) { if (&h->entries.data[fr.entry_index] == e) { -- cgit v1.2.3 From 36985f8da0cea59cb1912f62ae4e700983159b6a Mon Sep 17 00:00:00 2001 From: gingerBill Date: Fri, 5 Nov 2021 18:04:18 +0000 Subject: Simplification to `ptr_map_hash_key` --- src/ptr_map.cpp | 20 +++++--------------- 1 file changed, 5 insertions(+), 15 deletions(-) (limited to 'src/ptr_map.cpp') diff --git a/src/ptr_map.cpp b/src/ptr_map.cpp index 66a6f0fc5..3d6be1d44 100644 --- a/src/ptr_map.cpp +++ b/src/ptr_map.cpp @@ -28,21 +28,11 @@ struct PtrMap { u32 ptr_map_hash_key(uintptr key) { #if defined(GB_ARCH_64_BIT) - // TODO(bill): Improve ptr_map_hash_key - u32 key0 = (u32)(key & 0xffffffff); - u32 key1 = (u32)(key >> 32); - - u32 word; - u32 state = 0; - - state += key0 * 747796405u + 2891336453u; - word = ((state >> ((state >> 28u) + 4u)) ^ state) * 277803737u; - state = (word >> 22u) ^ word; - state += key1 * 747796405u + 2891336453u; - word = ((state >> ((state >> 28u) + 4u)) ^ state) * 277803737u; - state = (word >> 22u) ^ word; - return state; - + u64 x = (u64)key; + u8 count = (u8)(x >> 59); + x ^= x >> (5 + count); + x *= 12605985483714917081ull; + return (u32)(x ^ (x >> 43)); #elif defined(GB_ARCH_32_BIT) u32 state = ((u32)key) * 747796405u + 2891336453u; u32 word = ((state >> ((state >> 28u) + 4u)) ^ state) * 277803737u; -- cgit v1.2.3