From 600f2b7284b8974a18827242c18e790dab0cf06a Mon Sep 17 00:00:00 2001 From: gingerBill Date: Tue, 3 Jan 2023 11:53:59 +0000 Subject: Use heap_allocator for all hash set types --- src/ptr_set.cpp | 21 +++++++++++++++------ 1 file changed, 15 insertions(+), 6 deletions(-) (limited to 'src/ptr_set.cpp') diff --git a/src/ptr_set.cpp b/src/ptr_set.cpp index 9ecf1043e..affde5c2f 100644 --- a/src/ptr_set.cpp +++ b/src/ptr_set.cpp @@ -6,11 +6,11 @@ struct PtrSetEntry { template struct PtrSet { - Slice hashes; + Slice hashes; Array> entries; }; -template gb_internal void ptr_set_init (PtrSet *s, gbAllocator a, isize capacity = 16); +template gb_internal void ptr_set_init (PtrSet *s, isize capacity = 16); template gb_internal void ptr_set_destroy(PtrSet *s); template gb_internal T ptr_set_add (PtrSet *s, T ptr); template gb_internal bool ptr_set_update (PtrSet *s, T ptr); // returns true if it previously existed @@ -21,15 +21,18 @@ template gb_internal void ptr_set_grow (PtrSet *s); template gb_internal void ptr_set_rehash (PtrSet *s, isize new_count); template gb_internal void ptr_set_reserve(PtrSet *h, isize cap); +gb_internal gbAllocator ptr_set_allocator(void) { + return heap_allocator(); +} template -gb_internal void ptr_set_init(PtrSet *s, gbAllocator a, isize capacity) { +gb_internal void ptr_set_init(PtrSet *s, isize capacity) { if (capacity != 0) { capacity = next_pow2_isize(gb_max(16, capacity)); } - slice_init(&s->hashes, a, capacity); - array_init(&s->entries, a, 0, capacity); + slice_init(&s->hashes, ptr_set_allocator(), capacity); + array_init(&s->entries, ptr_set_allocator(), 0, capacity); for (isize i = 0; i < capacity; i++) { s->hashes.data[i] = MAP_SENTINEL; } @@ -37,6 +40,9 @@ gb_internal void ptr_set_init(PtrSet *s, gbAllocator a, isize capacity) { template gb_internal void ptr_set_destroy(PtrSet *s) { + if (s->entries.allocator.proc == nullptr) { + s->entries.allocator = ptr_set_allocator(); + } slice_free(&s->hashes, s->entries.allocator); array_free(&s->entries); } @@ -118,6 +124,9 @@ gb_internal void ptr_set_reset_entries(PtrSet *s) { template gb_internal void ptr_set_reserve(PtrSet *s, isize cap) { + if (s->entries.allocator.proc == nullptr) { + s->entries.allocator = ptr_set_allocator(); + } array_reserve(&s->entries, cap); if (s->entries.count*2 < s->hashes.count) { return; @@ -139,7 +148,7 @@ gb_internal gb_inline bool ptr_set_exists(PtrSet *s, T ptr) { } template -gb_internal gb_inline isize ptr_entry_index(PtrSet *s, T ptr) { +gb_internal gb_inline isize ptr_set_entry_index(PtrSet *s, T ptr) { isize index = ptr_set__find(s, ptr).entry_index; if (index != MAP_SENTINEL) { return index; -- cgit v1.2.3 From 747a11a954824da7960a247299986f56d1316773 Mon Sep 17 00:00:00 2001 From: gingerBill Date: Tue, 3 Jan 2023 12:18:35 +0000 Subject: Allow all set entry types to be implicitly cast to their key/value type to allow for easier iteration --- src/build_settings.cpp | 6 ++---- src/check_decl.cpp | 6 ++---- src/check_expr.cpp | 7 +++---- src/checker.cpp | 38 +++++++++++++------------------------- src/ptr_set.cpp | 12 ++++++++---- src/string_map.cpp | 13 ++++++++++--- src/string_set.cpp | 15 +++++++++++---- src/types.cpp | 3 +-- 8 files changed, 50 insertions(+), 50 deletions(-) (limited to 'src/ptr_set.cpp') diff --git a/src/build_settings.cpp b/src/build_settings.cpp index 75615a901..1dff5f43e 100644 --- a/src/build_settings.cpp +++ b/src/build_settings.cpp @@ -1332,11 +1332,10 @@ gb_internal void enable_target_feature(TokenPos pos, String const &target_featur gb_internal char const *target_features_set_to_cstring(gbAllocator allocator, bool with_quotes) { isize len = 0; isize i = 0; - for (auto const &entry : build_context.target_features_set) { + for (String const &feature : build_context.target_features_set) { if (i != 0) { len += 1; } - String feature = entry.value; len += feature.len; if (with_quotes) len += 2; i += 1; @@ -1344,13 +1343,12 @@ gb_internal char const *target_features_set_to_cstring(gbAllocator allocator, bo char *features = gb_alloc_array(allocator, char, len+1); len = 0; i = 0; - for (auto const &entry : build_context.target_features_set) { + for (String const &feature : build_context.target_features_set) { if (i != 0) { features[len++] = ','; } if (with_quotes) features[len++] = '"'; - String feature = entry.value; gb_memmove(features + len, feature.text, feature.len); len += feature.len; if (with_quotes) features[len++] = '"'; diff --git a/src/check_decl.cpp b/src/check_decl.cpp index 0c1a7c325..7b229db08 100644 --- a/src/check_decl.cpp +++ b/src/check_decl.cpp @@ -1587,16 +1587,14 @@ gb_internal bool check_proc_body(CheckerContext *ctx_, Token token, DeclInfo *de MUTEX_GUARD_BLOCK(decl->deps_mutex) MUTEX_GUARD_BLOCK(decl->parent->deps_mutex) { - for (auto const &entry : decl->deps) { - Entity *e = entry.ptr; + for (Entity *e : decl->deps) { ptr_set_add(&decl->parent->deps, e); } } MUTEX_GUARD_BLOCK(decl->type_info_deps_mutex) MUTEX_GUARD_BLOCK(decl->parent->type_info_deps_mutex) { - for (auto const &entry : decl->type_info_deps) { - Type *t = entry.ptr; + for (Type *t : decl->type_info_deps) { ptr_set_add(&decl->parent->type_info_deps, t); } } diff --git a/src/check_expr.cpp b/src/check_expr.cpp index 030bfb8e6..2924f9d13 100644 --- a/src/check_expr.cpp +++ b/src/check_expr.cpp @@ -202,8 +202,8 @@ gb_internal void check_did_you_mean_objc_entity(String const &name, Entity *e, b DidYouMeanAnswers d = did_you_mean_make(heap_allocator(), set.entries.count, name); defer (did_you_mean_destroy(&d)); - for (auto const &entry : set) { - did_you_mean_append(&d, entry.value); + for (String const &target : set) { + did_you_mean_append(&d, target); } check_did_you_mean_print(&d, prefix); } @@ -4942,8 +4942,7 @@ gb_internal isize add_dependencies_from_unpacking(CheckerContext *c, Entity **lh if (e != nullptr) { DeclInfo *decl = decl_info_of_entity(e); if (decl != nullptr) { - for (auto const &entry : decl->deps) { - Entity *dep = entry.ptr; + for (Entity *dep : decl->deps) { ptr_set_add(&c->decl->deps, dep); } } diff --git a/src/checker.cpp b/src/checker.cpp index 8779d9d45..0075fa543 100644 --- a/src/checker.cpp +++ b/src/checker.cpp @@ -2222,12 +2222,11 @@ gb_internal void add_dependency_to_set(Checker *c, Entity *entity) { return; } - for (auto const &entry : decl->type_info_deps) { - add_min_dep_type_info(c, entry.ptr); + for (Type *t : decl->type_info_deps) { + add_min_dep_type_info(c, t); } - for (auto const &entry : decl->deps) { - Entity *e = entry.ptr; + for (Entity *e : decl->deps) { add_dependency_to_set(c, e); if (e->kind == Entity_Procedure && e->Procedure.is_foreign) { Entity *fl = e->Procedure.foreign_library; @@ -2510,8 +2509,7 @@ gb_internal Array generate_entity_dependency_graph(CheckerInf DeclInfo *decl = decl_info_of_entity(e); GB_ASSERT(decl != nullptr); - for (auto const &entry : decl->deps) { - Entity *dep = entry.ptr; + for (Entity *dep : decl->deps) { if (dep->flags & EntityFlag_Field) { continue; } @@ -2537,15 +2535,12 @@ gb_internal Array generate_entity_dependency_graph(CheckerInf if (e->kind == Entity_Procedure) { // Connect each pred 'p' of 'n' with each succ 's' and from // the procedure node - for (auto const &p_entry : n->pred) { - EntityGraphNode *p = p_entry.ptr; - + for (EntityGraphNode *p : n->pred) { // Ignore self-cycles if (p != n) { // Each succ 's' of 'n' becomes a succ of 'p', and // each pred 'p' of 'n' becomes a pred of 's' - for (auto const &s_entry : n->succ) { - EntityGraphNode *s = s_entry.ptr; + for (EntityGraphNode *s : n->succ) { // Ignore self-cycles if (s != n) { if (p->entity->kind == Entity_Procedure && @@ -4784,8 +4779,7 @@ gb_internal void check_import_entities(Checker *c) { } } - for (auto const &entry : n->pred) { - ImportGraphNode *p = entry.ptr; + for (ImportGraphNode *p : n->pred) { p->dep_count = gb_max(p->dep_count-1, 0); priority_queue_fix(&pq, p->index); } @@ -4893,8 +4887,7 @@ gb_internal bool find_entity_path_tuple(Type *tuple, Entity *end, PtrSetdeps) { - Entity *dep = entry.ptr; + for (Entity *dep : var_decl->deps) { if (dep == end) { auto path = array_make(heap_allocator()); array_add(&path, dep); @@ -4944,8 +4937,7 @@ gb_internal Array find_entity_path(Entity *start, Entity *end, PtrSet< return path; } } else { - for (auto const &entry : decl->deps) { - Entity *dep = entry.ptr; + for (Entity *dep : decl->deps) { if (dep == end) { auto path = array_make(heap_allocator()); array_add(&path, dep); @@ -5002,8 +4994,7 @@ gb_internal void calculate_global_init_order(Checker *c) { } } - for (auto const &entry : n->pred) { - EntityGraphNode *p = entry.ptr; + for (EntityGraphNode *p : n->pred) { p->dep_count -= 1; p->dep_count = gb_max(p->dep_count, 0); priority_queue_fix(&pq, p->index); @@ -5163,8 +5154,7 @@ gb_internal void check_unchecked_bodies(Checker *c) { // use the `procs_to_check` array global_procedure_body_in_worker_queue = false; - for (auto const &entry : c->info.minimum_dependency_set) { - Entity *e = entry.ptr; + for (Entity *e : c->info.minimum_dependency_set) { if (e == nullptr || e->kind != Entity_Procedure) { continue; } @@ -5239,8 +5229,7 @@ gb_internal void check_test_procedures(Checker *c) { AstPackage *pkg = c->info.init_package; Scope *s = pkg->scope; - for (auto const &entry : build_context.test_names) { - String name = entry.value; + for (String const &name : build_context.test_names) { Entity *e = scope_lookup(s, name); if (e == nullptr) { Token tok = {}; @@ -5744,8 +5733,7 @@ gb_internal void check_parsed_files(Checker *c) { DeclInfo *decl = e->decl_info; ast_node(pl, ProcLit, decl->proc_lit); if (pl->inlining == ProcInlining_inline) { - for (auto const &entry : decl->deps) { - Entity *dep = entry.ptr; + for (Entity *dep : decl->deps) { if (dep == e) { error(e->token, "Cannot inline recursive procedure '%.*s'", LIT(e->token.string)); break; diff --git a/src/ptr_set.cpp b/src/ptr_set.cpp index affde5c2f..303bde07e 100644 --- a/src/ptr_set.cpp +++ b/src/ptr_set.cpp @@ -2,6 +2,10 @@ template struct PtrSetEntry { T ptr; MapIndex next; + + operator T() const noexcept { + return this->ptr; + } }; template @@ -245,21 +249,21 @@ gb_internal gb_inline void ptr_set_clear(PtrSet *s) { template -gb_internal PtrSetEntry *begin(PtrSet &m) { +gb_internal PtrSetEntry *begin(PtrSet &m) noexcept { return m.entries.data; } template -gb_internal PtrSetEntry const *begin(PtrSet const &m) { +gb_internal PtrSetEntry const *begin(PtrSet const &m) noexcept { return m.entries.data; } template -gb_internal PtrSetEntry *end(PtrSet &m) { +gb_internal PtrSetEntry *end(PtrSet &m) noexcept { return m.entries.data + m.entries.count; } template -gb_internal PtrSetEntry const *end(PtrSet const &m) { +gb_internal PtrSetEntry const *end(PtrSet const &m) noexcept { return m.entries.data + m.entries.count; } \ No newline at end of file diff --git a/src/string_map.cpp b/src/string_map.cpp index b5db63e90..74a16de73 100644 --- a/src/string_map.cpp +++ b/src/string_map.cpp @@ -1,6 +1,13 @@ struct StringHashKey { u32 hash; String string; + + operator String() const noexcept { + return this->string; + } + operator String const &() const noexcept { + return this->string; + } }; gb_internal gb_inline StringHashKey string_hash_string(String const &s) { @@ -283,11 +290,11 @@ gb_internal gb_inline void string_map_clear(StringMap *h) { template -gb_internal StringMapEntry *begin(StringMap &m) { +gb_internal StringMapEntry *begin(StringMap &m) noexcept { return m.entries.data; } template -gb_internal StringMapEntry const *begin(StringMap const &m) { +gb_internal StringMapEntry const *begin(StringMap const &m) noexcept { return m.entries.data; } @@ -298,6 +305,6 @@ gb_internal StringMapEntry *end(StringMap &m) { } template -gb_internal StringMapEntry const *end(StringMap const &m) { +gb_internal StringMapEntry const *end(StringMap const &m) noexcept { return m.entries.data + m.entries.count; } \ No newline at end of file diff --git a/src/string_set.cpp b/src/string_set.cpp index 753afa9bf..fb4640c20 100644 --- a/src/string_set.cpp +++ b/src/string_set.cpp @@ -2,6 +2,13 @@ struct StringSetEntry { u32 hash; MapIndex next; String value; + + operator String const() const noexcept { + return this->value; + } + operator String const &() const noexcept { + return this->value; + } }; struct StringSet { @@ -226,18 +233,18 @@ gb_internal gb_inline void string_set_clear(StringSet *s) { } -gb_internal StringSetEntry *begin(StringSet &m) { +gb_internal StringSetEntry *begin(StringSet &m) noexcept { return m.entries.data; } -gb_internal StringSetEntry const *begin(StringSet const &m) { +gb_internal StringSetEntry const *begin(StringSet const &m) noexcept { return m.entries.data; } -gb_internal StringSetEntry *end(StringSet &m) { +gb_internal StringSetEntry *end(StringSet &m) noexcept { return m.entries.data + m.entries.count; } -gb_internal StringSetEntry const *end(StringSet const &m) { +gb_internal StringSetEntry const *end(StringSet const &m) noexcept { return m.entries.data + m.entries.count; } \ No newline at end of file diff --git a/src/types.cpp b/src/types.cpp index 1e2d85ac6..d33c36e94 100644 --- a/src/types.cpp +++ b/src/types.cpp @@ -823,8 +823,7 @@ gb_internal bool type_ptr_set_exists(PtrSet *s, Type *t) { // TODO(bill, 2019-10-05): This is very slow and it's probably a lot // faster to cache types correctly - for (auto const &entry : *s) { - Type *f = entry.ptr; + for (Type *f : *s) { if (are_types_identical(t, f)) { ptr_set_add(s, t); return true; -- cgit v1.2.3 From 17fa8cb6ef4424e4c7cff2439e2d52220f440660 Mon Sep 17 00:00:00 2001 From: gingerBill Date: Tue, 3 Jan 2023 18:21:42 +0000 Subject: Add extra mutex to TypePth just in case --- src/ptr_set.cpp | 3 +++ src/types.cpp | 16 ++++++++++++++-- 2 files changed, 17 insertions(+), 2 deletions(-) (limited to 'src/ptr_set.cpp') diff --git a/src/ptr_set.cpp b/src/ptr_set.cpp index 303bde07e..9b8b678f8 100644 --- a/src/ptr_set.cpp +++ b/src/ptr_set.cpp @@ -1,5 +1,7 @@ template struct PtrSetEntry { + static_assert(sizeof(T) == sizeof(void *), "Key size must be pointer size"); + T ptr; MapIndex next; @@ -10,6 +12,7 @@ struct PtrSetEntry { template struct PtrSet { + Slice hashes; Array> entries; }; diff --git a/src/types.cpp b/src/types.cpp index fa7c1d7f7..ec7adab5a 100644 --- a/src/types.cpp +++ b/src/types.cpp @@ -748,6 +748,7 @@ gb_internal i64 type_align_of_internal(Type *t, TypePath *path); // IMPORTANT TODO(bill): SHould this TypePath code be removed since type cycle checking is handled much earlier on? struct TypePath { + RecursiveMutex mutex; Array path; // Entity_TypeName; bool failure; }; @@ -758,7 +759,9 @@ gb_internal void type_path_init(TypePath *tp) { } gb_internal void type_path_free(TypePath *tp) { + mutex_lock(&tp->mutex); array_free(&tp->path); + mutex_unlock(&tp->mutex); } gb_internal void type_path_print_illegal_cycle(TypePath *tp, isize start_index) { @@ -787,6 +790,8 @@ gb_internal bool type_path_push(TypePath *tp, Type *t) { } Entity *e = t->Named.type_name; + mutex_lock(&tp->mutex); + for (isize i = 0; i < tp->path.count; i++) { Entity *p = tp->path[i]; if (p == e) { @@ -795,12 +800,19 @@ gb_internal bool type_path_push(TypePath *tp, Type *t) { } array_add(&tp->path, e); + + mutex_unlock(&tp->mutex); + return true; } gb_internal void type_path_pop(TypePath *tp) { - if (tp != nullptr && tp->path.count > 0) { - array_pop(&tp->path); + if (tp != nullptr) { + mutex_lock(&tp->mutex); + if (tp->path.count > 0) { + array_pop(&tp->path); + } + mutex_unlock(&tp->mutex); } } -- cgit v1.2.3 From ec69101101d56e90ee183e449eb5bb3605e3afbe Mon Sep 17 00:00:00 2001 From: gingerBill Date: Tue, 3 Jan 2023 18:39:37 +0000 Subject: Convert `minimum_dependency_type_info_set` to use a `PtrMap` --- src/checker.cpp | 19 +++++++------------ src/checker.hpp | 2 +- src/llvm_backend_type.cpp | 7 ++++--- src/ptr_map.cpp | 1 - src/ptr_set.cpp | 10 ---------- 5 files changed, 12 insertions(+), 27 deletions(-) (limited to 'src/ptr_set.cpp') diff --git a/src/checker.cpp b/src/checker.cpp index 11e0dfa47..78f96e47f 100644 --- a/src/checker.cpp +++ b/src/checker.cpp @@ -1153,6 +1153,9 @@ gb_internal void init_checker_info(CheckerInfo *i) { array_init(&i->init_procedures, a, 0, 0); array_init(&i->required_foreign_imports_through_force, a, 0, 0); + map_init(&i->objc_msgSend_types); + string_map_init(&i->load_file_cache); + array_init(&i->all_procedures, heap_allocator()); TIME_SECTION("checker info: mpmc queues"); @@ -1160,16 +1163,7 @@ gb_internal void init_checker_info(CheckerInfo *i) { mpmc_init(&i->definition_queue, a, 1<<20); mpmc_init(&i->required_global_variable_queue, a, 1<<10); mpmc_init(&i->required_foreign_imports_through_force_queue, a, 1<<10); - - TIME_SECTION("checker info: mutexes"); - mpmc_init(&i->intrinsics_entry_point_usage, a, 1<<10); // just waste some memory here, even if it probably never used - - map_init(&i->objc_msgSend_types); - string_map_init(&i->load_file_cache); - - array_init(&i->all_procedures, heap_allocator()); - } gb_internal void destroy_checker_info(CheckerInfo *i) { @@ -2031,10 +2025,11 @@ gb_internal void add_min_dep_type_info(Checker *c, Type *t) { ti_index = type_info_index(&c->info, t, false); } GB_ASSERT(ti_index >= 0); - if (ptr_set_update(set, ti_index)) { - // Type Already exists + if (map_get(set, ti_index)) { + // Type already exists; return; } + map_set(set, ti_index, set->entries.count); // Add nested types if (t->kind == Type_Named) { @@ -2275,7 +2270,7 @@ gb_internal void generate_minimum_dependency_set(Checker *c, Entity *start) { isize min_dep_set_cap = next_pow2_isize(entity_count*4); // empirically determined factor ptr_set_init(&c->info.minimum_dependency_set, min_dep_set_cap); - ptr_set_init(&c->info.minimum_dependency_type_info_set); + map_init(&c->info.minimum_dependency_type_info_set); #define FORCE_ADD_RUNTIME_ENTITIES(condition, ...) do { \ if (condition) { \ diff --git a/src/checker.hpp b/src/checker.hpp index 60800349b..bb870e077 100644 --- a/src/checker.hpp +++ b/src/checker.hpp @@ -336,7 +336,7 @@ struct CheckerInfo { Scope * init_scope; Entity * entry_point; PtrSet minimum_dependency_set; - PtrSet minimum_dependency_type_info_set; + PtrMap minimum_dependency_type_info_set; diff --git a/src/llvm_backend_type.cpp b/src/llvm_backend_type.cpp index c306cdead..b9b450404 100644 --- a/src/llvm_backend_type.cpp +++ b/src/llvm_backend_type.cpp @@ -2,9 +2,10 @@ gb_internal isize lb_type_info_index(CheckerInfo *info, Type *type, bool err_on_ auto *set = &info->minimum_dependency_type_info_set; isize index = type_info_index(info, type, err_on_not_found); if (index >= 0) { - isize i = ptr_set_entry_index(set, index); - if (i >= 0) { - return i+1; + auto *found = map_get(set, index); + if (found) { + GB_ASSERT(*found >= 0); + return *found + 1; } } if (err_on_not_found) { diff --git a/src/ptr_map.cpp b/src/ptr_map.cpp index 264136881..ae3cd4b40 100644 --- a/src/ptr_map.cpp +++ b/src/ptr_map.cpp @@ -229,7 +229,6 @@ gb_internal void map_set(PtrMap *h, K key, V const &value) { } } - template gb_internal void map__erase(PtrMap *h, MapFindResult const &fr) { MapFindResult last; diff --git a/src/ptr_set.cpp b/src/ptr_set.cpp index 9b8b678f8..f730a47ff 100644 --- a/src/ptr_set.cpp +++ b/src/ptr_set.cpp @@ -12,7 +12,6 @@ struct PtrSetEntry { template struct PtrSet { - Slice hashes; Array> entries; }; @@ -154,15 +153,6 @@ gb_internal gb_inline bool ptr_set_exists(PtrSet *s, T ptr) { return index != MAP_SENTINEL; } -template -gb_internal gb_inline isize ptr_set_entry_index(PtrSet *s, T ptr) { - isize index = ptr_set__find(s, ptr).entry_index; - if (index != MAP_SENTINEL) { - return index; - } - return -1; -} - // Returns true if it already exists template gb_internal T ptr_set_add(PtrSet *s, T ptr) { -- cgit v1.2.3 From b3a55b8b6f54b71bb527c2b2b1cbe8b01e28d8a2 Mon Sep 17 00:00:00 2001 From: gingerBill Date: Tue, 3 Jan 2023 18:42:13 +0000 Subject: Remove unused procedures --- src/ptr_set.cpp | 14 +++----------- 1 file changed, 3 insertions(+), 11 deletions(-) (limited to 'src/ptr_set.cpp') diff --git a/src/ptr_set.cpp b/src/ptr_set.cpp index f730a47ff..e2b3f2372 100644 --- a/src/ptr_set.cpp +++ b/src/ptr_set.cpp @@ -23,9 +23,6 @@ template gb_internal bool ptr_set_update (PtrSet *s, T ptr); // template gb_internal bool ptr_set_exists (PtrSet *s, T ptr); template gb_internal void ptr_set_remove (PtrSet *s, T ptr); template gb_internal void ptr_set_clear (PtrSet *s); -template gb_internal void ptr_set_grow (PtrSet *s); -template gb_internal void ptr_set_rehash (PtrSet *s, isize new_count); -template gb_internal void ptr_set_reserve(PtrSet *h, isize cap); gb_internal gbAllocator ptr_set_allocator(void) { return heap_allocator(); @@ -104,12 +101,6 @@ gb_internal bool ptr_set__full(PtrSet *s) { return 0.75f * s->hashes.count <= s->entries.count; } -template -gb_internal gb_inline void ptr_set_grow(PtrSet *s) { - isize new_count = gb_max(s->hashes.count<<1, 16); - ptr_set_rehash(s, new_count); -} - template gb_internal void ptr_set_reset_entries(PtrSet *s) { for (isize i = 0; i < s->hashes.count; i++) { @@ -141,12 +132,13 @@ gb_internal void ptr_set_reserve(PtrSet *s, isize cap) { ptr_set_reset_entries(s); } - template -gb_internal void ptr_set_rehash(PtrSet *s, isize new_count) { +gb_internal gb_inline void ptr_set_grow(PtrSet *s) { + isize new_count = gb_max(s->hashes.count<<1, 16); ptr_set_reserve(s, new_count); } + template gb_internal gb_inline bool ptr_set_exists(PtrSet *s, T ptr) { isize index = ptr_set__find(s, ptr).entry_index; -- cgit v1.2.3 From d06a0e7093c3f06a474a040385f1b9dfdfce29ad Mon Sep 17 00:00:00 2001 From: gingerBill Date: Wed, 4 Jan 2023 13:30:27 +0000 Subject: Improve the `PtrSet` to be as simple and small as possible --- src/check_stmt.cpp | 1 + src/checker.cpp | 33 +++--- src/ptr_map.cpp | 2 +- src/ptr_set.cpp | 303 +++++++++++++++++++++++------------------------------ src/threading.cpp | 20 ++-- 5 files changed, 157 insertions(+), 202 deletions(-) (limited to 'src/ptr_set.cpp') diff --git a/src/check_stmt.cpp b/src/check_stmt.cpp index 9547035d0..b4dd4cd7d 100644 --- a/src/check_stmt.cpp +++ b/src/check_stmt.cpp @@ -1289,6 +1289,7 @@ gb_internal void check_type_switch_stmt(CheckerContext *ctx, Ast *node, u32 mod_ for (Type *t : variants) { if (!type_ptr_set_exists(&seen, t)) { array_add(&unhandled, t); + gb_printf_err("HERE: %p %s\n", t, type_to_string(t)); } } diff --git a/src/checker.cpp b/src/checker.cpp index 78f96e47f..b8709f15e 100644 --- a/src/checker.cpp +++ b/src/checker.cpp @@ -66,15 +66,10 @@ gb_internal void scope_reserve(Scope *scope, isize capacity) { } gb_internal void entity_graph_node_set_destroy(EntityGraphNodeSet *s) { - if (s->hashes.data != nullptr) { - ptr_set_destroy(s); - } + ptr_set_destroy(s); } gb_internal void entity_graph_node_set_add(EntityGraphNodeSet *s, EntityGraphNode *n) { - if (s->hashes.data == nullptr) { - ptr_set_init(s); - } ptr_set_add(s, n); } @@ -2556,7 +2551,6 @@ gb_internal Array generate_entity_dependency_graph(CheckerInf } // IMPORTANT NOTE/TODO(bill, 2020-11-15): These three calls take the majority of the // the time to process - entity_graph_node_set_add(&p->succ, s); entity_graph_node_set_add(&s->pred, p); // Remove edge to 'n' @@ -2577,7 +2571,7 @@ gb_internal Array generate_entity_dependency_graph(CheckerInf for_array(i, G) { EntityGraphNode *n = G[i]; n->index = i; - n->dep_count = n->succ.entries.count; + n->dep_count = n->succ.count; GB_ASSERT(n->dep_count >= 0); } @@ -4228,7 +4222,7 @@ gb_internal Array generate_import_dependency_graph(Checker *c for (auto const &entry : M) { auto n = entry.value; n->index = i++; - n->dep_count = n->succ.entries.count; + n->dep_count = n->succ.count; GB_ASSERT(n->dep_count >= 0); array_add(&G, n); } @@ -5706,17 +5700,6 @@ gb_internal void check_parsed_files(Checker *c) { check_scope_usage(c, f->scope); } - TIME_SECTION("add untyped expression values"); - // Add untyped expression values - for (UntypedExprInfo u = {}; mpmc_dequeue(&c->global_untyped_queue, &u); /**/) { - GB_ASSERT(u.expr != nullptr && u.info != nullptr); - if (is_type_typed(u.info->type)) { - compiler_error("%s (type %s) is typed!", expr_to_string(u.expr), type_to_string(u.info->type)); - } - add_type_and_value(&c->builtin_ctx, u.expr, u.info->mode, u.info->type, u.info->value); - } - - TIME_SECTION("add basic type information"); // Add "Basic" type information for (isize i = 0; i < Basic_COUNT; i++) { @@ -5810,6 +5793,16 @@ gb_internal void check_parsed_files(Checker *c) { GB_ASSERT(c->info.entity_queue.count.load(std::memory_order_relaxed) == 0); GB_ASSERT(c->info.definition_queue.count.load(std::memory_order_relaxed) == 0); + TIME_SECTION("add untyped expression values"); + // Add untyped expression values + for (UntypedExprInfo u = {}; mpmc_dequeue(&c->global_untyped_queue, &u); /**/) { + GB_ASSERT(u.expr != nullptr && u.info != nullptr); + if (is_type_typed(u.info->type)) { + compiler_error("%s (type %s) is typed!", expr_to_string(u.expr), type_to_string(u.info->type)); + } + add_type_and_value(&c->builtin_ctx, u.expr, u.info->mode, u.info->type, u.info->value); + } + TIME_SECTION("sort init procedures"); check_sort_init_procedures(c); diff --git a/src/ptr_map.cpp b/src/ptr_map.cpp index ae3cd4b40..8869bf3fe 100644 --- a/src/ptr_map.cpp +++ b/src/ptr_map.cpp @@ -41,7 +41,7 @@ gb_internal gb_inline u32 ptr_map_hash_key(uintptr key) { u32 word = ((state >> ((state >> 28u) + 4u)) ^ state) * 277803737u; res = (word >> 22u) ^ word; #endif - return res ^ (res == MAP_SENTINEL); + return res; } gb_internal gb_inline u32 ptr_map_hash_key(void const *key) { return ptr_map_hash_key((uintptr)key); diff --git a/src/ptr_set.cpp b/src/ptr_set.cpp index e2b3f2372..8be2b0524 100644 --- a/src/ptr_set.cpp +++ b/src/ptr_set.cpp @@ -1,19 +1,22 @@ template -struct PtrSetEntry { - static_assert(sizeof(T) == sizeof(void *), "Key size must be pointer size"); - - T ptr; - MapIndex next; +struct TypeIsPointer { + enum {value = false}; +}; - operator T() const noexcept { - return this->ptr; - } +template +struct TypeIsPointer { + enum {value = true}; }; + template struct PtrSet { - Slice hashes; - Array> entries; + static_assert(TypeIsPointer::value, "PtrSet::T must be a pointer"); + static constexpr T TOMBSTONE = (T)(~uintptr(0)); + + T * keys; + usize count; + usize capacity; }; template gb_internal void ptr_set_init (PtrSet *s, isize capacity = 16); @@ -30,225 +33,183 @@ gb_internal gbAllocator ptr_set_allocator(void) { template gb_internal void ptr_set_init(PtrSet *s, isize capacity) { + GB_ASSERT(s->keys == nullptr); if (capacity != 0) { capacity = next_pow2_isize(gb_max(16, capacity)); + s->keys = gb_alloc_array(ptr_set_allocator(), T, capacity); + // This memory will be zeroed, no need to explicitly zero it } - - slice_init(&s->hashes, ptr_set_allocator(), capacity); - array_init(&s->entries, ptr_set_allocator(), 0, capacity); - for (isize i = 0; i < capacity; i++) { - s->hashes.data[i] = MAP_SENTINEL; - } + s->count = 0; + s->capacity = capacity; } template gb_internal void ptr_set_destroy(PtrSet *s) { - if (s->entries.allocator.proc == nullptr) { - s->entries.allocator = ptr_set_allocator(); - } - slice_free(&s->hashes, s->entries.allocator); - array_free(&s->entries); + gb_free(ptr_set_allocator(), s->keys); + s->keys = nullptr; + s->count = 0; + s->capacity = 0; } template -gb_internal MapIndex ptr_set__add_entry(PtrSet *s, T ptr) { - PtrSetEntry e = {}; - e.ptr = ptr; - e.next = MAP_SENTINEL; - array_add(&s->entries, e); - return cast(MapIndex)(s->entries.count-1); -} - - -template -gb_internal MapFindResult ptr_set__find(PtrSet *s, T ptr) { - MapFindResult fr = {MAP_SENTINEL, MAP_SENTINEL, MAP_SENTINEL}; - if (s->hashes.count != 0) { - 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 != MAP_SENTINEL) { - if (s->entries.data[fr.entry_index].ptr == ptr) { - return fr; +gb_internal isize ptr_set__find(PtrSet *s, T ptr) { + GB_ASSERT(ptr != nullptr); + if (s->count != 0) { + #if 0 + for (usize i = 0; i < s->capacity; i++) { + if (s->keys[i] == ptr) { + return i; } - fr.entry_prev = fr.entry_index; - fr.entry_index = s->entries.data[fr.entry_index].next; } - } - return fr; -} - -template -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) { - 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 != MAP_SENTINEL) { - if (&s->entries.data[fr.entry_index] == e) { - return fr; + #else + u32 hash = ptr_map_hash_key(ptr); + usize mask = s->capacity-1; + usize hash_index = cast(usize)hash & mask; + for (usize i = 0; i < s->capacity; i++) { + T key = s->keys[hash_index]; + if (key == ptr) { + return hash_index; + } else if (key == nullptr) { + return -1; } - fr.entry_prev = fr.entry_index; - fr.entry_index = s->entries.data[fr.entry_index].next; + hash_index = (hash_index+1)&mask; } + #endif } - return fr; + return -1; } template gb_internal bool ptr_set__full(PtrSet *s) { - return 0.75f * s->hashes.count <= s->entries.count; + return 0.75f * s->capacity <= s->count; } template -gb_internal void ptr_set_reset_entries(PtrSet *s) { - for (isize i = 0; i < s->hashes.count; i++) { - s->hashes.data[i] = MAP_SENTINEL; - } - for (isize i = 0; i < s->entries.count; i++) { - MapFindResult fr; - PtrSetEntry *e = &s->entries.data[i]; - e->next = MAP_SENTINEL; - fr = ptr_set__find_from_entry(s, e); - if (fr.entry_prev == MAP_SENTINEL) { - s->hashes[fr.hash_index] = cast(MapIndex)i; - } else { - s->entries[fr.entry_prev].next = cast(MapIndex)i; - } +gb_internal gb_inline void ptr_set_grow(PtrSet *old_set) { + if (old_set->capacity == 0) { + ptr_set_init(old_set); + return; } -} -template -gb_internal void ptr_set_reserve(PtrSet *s, isize cap) { - if (s->entries.allocator.proc == nullptr) { - s->entries.allocator = ptr_set_allocator(); - } - array_reserve(&s->entries, cap); - if (s->entries.count*2 < s->hashes.count) { - return; + PtrSet new_set = {}; + ptr_set_init(&new_set, gb_max(old_set->capacity<<1, 16)); + + for (T ptr : *old_set) { + bool was_new = ptr_set_update(&new_set, ptr); + GB_ASSERT(!was_new); } - slice_resize(&s->hashes, s->entries.allocator, cap*2); - ptr_set_reset_entries(s); -} + GB_ASSERT(old_set->count == new_set.count); -template -gb_internal gb_inline void ptr_set_grow(PtrSet *s) { - isize new_count = gb_max(s->hashes.count<<1, 16); - ptr_set_reserve(s, new_count); + ptr_set_destroy(old_set); + + *old_set = new_set; } template gb_internal gb_inline bool ptr_set_exists(PtrSet *s, T ptr) { - isize index = ptr_set__find(s, ptr).entry_index; - return index != MAP_SENTINEL; + return ptr_set__find(s, ptr) >= 0; } -// Returns true if it already exists -template -gb_internal T ptr_set_add(PtrSet *s, T ptr) { - MapIndex index; - MapFindResult fr; - if (s->hashes.count == 0) { - ptr_set_grow(s); - } - fr = ptr_set__find(s, ptr); - if (fr.entry_index == MAP_SENTINEL) { - index = ptr_set__add_entry(s, ptr); - if (fr.entry_prev != MAP_SENTINEL) { - s->entries.data[fr.entry_prev].next = index; - } else { - s->hashes.data[fr.hash_index] = index; - } - } - if (ptr_set__full(s)) { - ptr_set_grow(s); - } - return ptr; -} template gb_internal bool ptr_set_update(PtrSet *s, T ptr) { // returns true if it previously existsed - bool exists = false; - MapIndex index; - MapFindResult fr; - if (s->hashes.count == 0) { + if (ptr_set_exists(s, ptr)) { + return true; + } + + if (s->keys == nullptr) { + ptr_set_init(s); + } else if (ptr_set__full(s)) { ptr_set_grow(s); } - fr = ptr_set__find(s, ptr); - if (fr.entry_index != MAP_SENTINEL) { - exists = true; - } else { - index = ptr_set__add_entry(s, ptr); - if (fr.entry_prev != MAP_SENTINEL) { - s->entries.data[fr.entry_prev].next = index; - } else { - s->hashes.data[fr.hash_index] = index; + GB_ASSERT(s->count < s->capacity); + GB_ASSERT(s->capacity >= 0); + + usize mask = s->capacity-1; + u32 hash = ptr_map_hash_key(ptr); + usize hash_index = (cast(usize)hash) & mask; + GB_ASSERT(hash_index < s->capacity); + for (usize i = 0; i < s->capacity; i++) { + T *key = &s->keys[hash_index]; + GB_ASSERT(*key != ptr); + if (*key == PtrSet::TOMBSTONE || *key == nullptr) { + *key = ptr; + s->count++; + return false; } + hash_index = (hash_index+1)&mask; } - if (ptr_set__full(s)) { - ptr_set_grow(s); - } - return exists; -} - + GB_PANIC("ptr set out of memory"); + return false; +} template -gb_internal 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; - } - if (cast(isize)fr.entry_index == s->entries.count-1) { - array_pop(&s->entries); - return; - } - 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 != MAP_SENTINEL) { - s->entries.data[last.entry_prev].next = fr.entry_index; - } else { - s->hashes.data[last.hash_index] = fr.entry_index; - } +gb_internal T ptr_set_add(PtrSet *s, T ptr) { + ptr_set_update(s, ptr); + return ptr; } + template gb_internal void ptr_set_remove(PtrSet *s, T ptr) { - MapFindResult fr = ptr_set__find(s, ptr); - if (fr.entry_index != MAP_SENTINEL) { - ptr_set__erase(s, fr); + isize index = ptr_set__find(s, ptr); + if (index >= 0) { + GB_ASSERT(s->count > 0); + s->keys[index] = PtrSet::TOMBSTONE; + s->count--; } } template gb_internal 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] = MAP_SENTINEL; - } + s->count = 0; + gb_zero_size(s->keys, s->capacity*gb_size_of(T)); } - -template -gb_internal PtrSetEntry *begin(PtrSet &m) noexcept { - return m.entries.data; -} template -gb_internal PtrSetEntry const *begin(PtrSet const &m) noexcept { - return m.entries.data; -} +struct PtrSetIterator { + PtrSet *set; + usize index; + + PtrSetIterator &operator++() noexcept { + for (;;) { + ++index; + if (set->capacity == index) { + return *this; + } + T key = set->keys[index]; + if (key != nullptr && key != PtrSet::TOMBSTONE) { + return *this; + } + } + } + + bool operator==(PtrSetIterator const &other) const noexcept { + return this->set == other.set && this->index == other.index; + } + + + operator T *() const { + return &set->keys[index]; + } +}; template -gb_internal PtrSetEntry *end(PtrSet &m) noexcept { - return m.entries.data + m.entries.count; +gb_internal PtrSetIterator begin(PtrSet &set) noexcept { + usize index = 0; + while (index < set.capacity) { + T key = set.keys[index]; + if (key != nullptr && key != PtrSet::TOMBSTONE) { + break; + } + index++; + } + return PtrSetIterator{&set, index}; } - template -gb_internal PtrSetEntry const *end(PtrSet const &m) noexcept { - return m.entries.data + m.entries.count; +gb_internal PtrSetIterator end(PtrSet &set) noexcept { + return PtrSetIterator{&set, set.capacity}; } \ No newline at end of file diff --git a/src/threading.cpp b/src/threading.cpp index 27a17112e..bf298e024 100644 --- a/src/threading.cpp +++ b/src/threading.cpp @@ -699,13 +699,13 @@ extern "C" int __ulock_wake(uint32_t operation, void *addr, uint64_t wake_value) gb_internal void futex_signal(Futex *f) { for (;;) { int ret = __ulock_wake(UL_COMPARE_AND_WAIT | ULF_NO_ERRNO, f, 0); - if (ret >= 0) { + if (ret == 0) { return; } - if (ret == EINTR || ret == EFAULT) { + if (ret == -EINTR || ret == -EFAULT) { continue; } - if (ret == ENOENT) { + if (ret == -ENOENT) { return; } GB_PANIC("Failed in futex wake!\n"); @@ -716,13 +716,13 @@ gb_internal void futex_broadcast(Futex *f) { for (;;) { enum { ULF_WAKE_ALL = 0x00000100 }; int ret = __ulock_wake(UL_COMPARE_AND_WAIT | ULF_NO_ERRNO | ULF_WAKE_ALL, f, 0); - if (ret >= 0) { + if (ret == 0) { return; } - if (ret == EINTR || ret == EFAULT) { + if (ret == -EINTR || ret == -EFAULT) { continue; } - if (ret == ENOENT) { + if (ret == -ENOENT) { return; } GB_PANIC("Failed in futex wake!\n"); @@ -732,16 +732,16 @@ gb_internal void futex_broadcast(Futex *f) { gb_internal void futex_wait(Futex *f, Footex val) { for (;;) { int ret = __ulock_wait(UL_COMPARE_AND_WAIT | ULF_NO_ERRNO, f, val, 0); - if (ret >= 0) { + if (ret == 0) { if (*f != val) { return; } continue; } - if (ret == EINTR || ret == EFAULT) { - continue; + if (ret == -EINTR || ret == -EFAULT) { + -continue; } - if (ret == ENOENT) { + if (ret == -ENOENT) { return; } -- cgit v1.2.3 From bbb2164e38e3930cb79c5e7bc61b421e38131361 Mon Sep 17 00:00:00 2001 From: gingerBill Date: Thu, 5 Jan 2023 01:25:37 +0000 Subject: Inline map gets; cast explicitly on TOMBSTONE checking --- src/ptr_map.cpp | 27 +++++++++++++++++++-------- src/ptr_set.cpp | 10 +++++----- src/string_map.cpp | 15 ++++++++++++--- 3 files changed, 36 insertions(+), 16 deletions(-) (limited to 'src/ptr_set.cpp') diff --git a/src/ptr_map.cpp b/src/ptr_map.cpp index 8869bf3fe..c33bf9ffb 100644 --- a/src/ptr_map.cpp +++ b/src/ptr_map.cpp @@ -112,11 +112,12 @@ gb_internal MapFindResult map__find(PtrMap *h, K 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) { + auto *entry = &h->entries.data[fr.entry_index]; + if (entry->key == key) { return fr; } fr.entry_prev = fr.entry_index; - fr.entry_index = h->entries.data[fr.entry_index].next; + fr.entry_index = entry->next; } return fr; } @@ -190,18 +191,28 @@ gb_internal void map_rehash(PtrMap *h, isize new_count) { template gb_internal V *map_get(PtrMap *h, K key) { - MapIndex index = map__find(h, key).entry_index; - if (index != MAP_SENTINEL) { - return &h->entries.data[index].value; + MapFindResult fr = {MAP_SENTINEL, MAP_SENTINEL, MAP_SENTINEL}; + if (h->hashes.count != 0) { + 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) { + auto *entry = &h->entries.data[fr.entry_index]; + if (entry->key == key) { + return &entry->value; + } + fr.entry_prev = fr.entry_index; + fr.entry_index = entry->next; + } } return nullptr; } template gb_internal V &map_must_get(PtrMap *h, K key) { - MapIndex index = map__find(h, key).entry_index; - GB_ASSERT(index != MAP_SENTINEL); - return h->entries.data[index].value; + V *ptr = map_get(h, key); + GB_ASSERT(ptr != nullptr); + return *ptr; } template diff --git a/src/ptr_set.cpp b/src/ptr_set.cpp index 8be2b0524..019ede8a5 100644 --- a/src/ptr_set.cpp +++ b/src/ptr_set.cpp @@ -12,7 +12,7 @@ struct TypeIsPointer { template struct PtrSet { static_assert(TypeIsPointer::value, "PtrSet::T must be a pointer"); - static constexpr T TOMBSTONE = (T)(~uintptr(0)); + static constexpr uintptr TOMBSTONE = ~(uintptr)(0ull); T * keys; usize count; @@ -133,7 +133,7 @@ gb_internal bool ptr_set_update(PtrSet *s, T ptr) { // returns true if it pre for (usize i = 0; i < s->capacity; i++) { T *key = &s->keys[hash_index]; GB_ASSERT(*key != ptr); - if (*key == PtrSet::TOMBSTONE || *key == nullptr) { + if (*key == (T)PtrSet::TOMBSTONE || *key == nullptr) { *key = ptr; s->count++; return false; @@ -157,7 +157,7 @@ gb_internal void ptr_set_remove(PtrSet *s, T ptr) { isize index = ptr_set__find(s, ptr); if (index >= 0) { GB_ASSERT(s->count > 0); - s->keys[index] = PtrSet::TOMBSTONE; + s->keys[index] = (T)PtrSet::TOMBSTONE; s->count--; } } @@ -180,7 +180,7 @@ struct PtrSetIterator { return *this; } T key = set->keys[index]; - if (key != nullptr && key != PtrSet::TOMBSTONE) { + if (key != nullptr && key != (T)PtrSet::TOMBSTONE) { return *this; } } @@ -202,7 +202,7 @@ gb_internal PtrSetIterator begin(PtrSet &set) noexcept { usize index = 0; while (index < set.capacity) { T key = set.keys[index]; - if (key != nullptr && key != PtrSet::TOMBSTONE) { + if (key != nullptr && key != (T)PtrSet::TOMBSTONE) { break; } index++; diff --git a/src/string_map.cpp b/src/string_map.cpp index 74a16de73..facd00bb0 100644 --- a/src/string_map.cpp +++ b/src/string_map.cpp @@ -180,9 +180,18 @@ gb_internal void string_map_rehash(StringMap *h, isize new_count) { template gb_internal T *string_map_get(StringMap *h, StringHashKey const &key) { - isize index = string_map__find(h, key).entry_index; - if (index != MAP_SENTINEL) { - return &h->entries.data[index].value; + MapFindResult fr = {MAP_SENTINEL, MAP_SENTINEL, MAP_SENTINEL}; + if (h->hashes.count != 0) { + fr.hash_index = cast(MapIndex)(key.hash & (h->hashes.count-1)); + fr.entry_index = h->hashes.data[fr.hash_index]; + while (fr.entry_index != MAP_SENTINEL) { + auto *entry = &h->entries.data[fr.entry_index]; + if (string_hash_key_equal(entry->key, key)) { + return &entry->value; + } + fr.entry_prev = fr.entry_index; + fr.entry_index = entry->next; + } } return nullptr; } -- cgit v1.2.3