From 252be0fb417f9cdde5e9c4b348cd995a20433aea Mon Sep 17 00:00:00 2001 From: gingerBill Date: Tue, 3 Jan 2023 11:59:52 +0000 Subject: Make all maps use heap allocator implicitly --- src/string_map.cpp | 18 ++++++++++++++---- 1 file changed, 14 insertions(+), 4 deletions(-) (limited to 'src/string_map.cpp') diff --git a/src/string_map.cpp b/src/string_map.cpp index 9f9374ece..b5db63e90 100644 --- a/src/string_map.cpp +++ b/src/string_map.cpp @@ -35,7 +35,7 @@ struct StringMap { }; -template gb_internal void string_map_init (StringMap *h, gbAllocator a, isize capacity = 16); +template gb_internal void string_map_init (StringMap *h, isize capacity = 16); template gb_internal void string_map_destroy (StringMap *h); template gb_internal T * string_map_get (StringMap *h, char const *key); @@ -56,11 +56,15 @@ template gb_internal void string_map_grow (StringMap template gb_internal void string_map_rehash (StringMap *h, isize new_count); template gb_internal void string_map_reserve (StringMap *h, isize cap); +gb_internal gbAllocator string_map_allocator(void) { + return heap_allocator(); +} + template -gb_internal gb_inline void string_map_init(StringMap *h, gbAllocator a, isize capacity) { +gb_internal gb_inline void string_map_init(StringMap *h, isize capacity) { capacity = next_pow2_isize(capacity); - slice_init(&h->hashes, a, capacity); - array_init(&h->entries, a, 0, capacity); + slice_init(&h->hashes, string_map_allocator(), capacity); + array_init(&h->entries, string_map_allocator(), 0, capacity); for (isize i = 0; i < capacity; i++) { h->hashes.data[i] = MAP_SENTINEL; } @@ -68,6 +72,9 @@ gb_internal gb_inline void string_map_init(StringMap *h, gbAllocator a, isize template gb_internal gb_inline void string_map_destroy(StringMap *h) { + if (h->entries.allocator.proc == nullptr) { + h->entries.allocator = string_map_allocator(); + } slice_free(&h->hashes, h->entries.allocator); array_free(&h->entries); } @@ -147,6 +154,9 @@ gb_internal void string_map_reset_entries(StringMap *h) { template gb_internal void string_map_reserve(StringMap *h, isize cap) { + if (h->entries.allocator.proc == nullptr) { + h->entries.allocator = string_map_allocator(); + } array_reserve(&h->entries, cap); if (h->entries.count*2 < h->hashes.count) { return; -- 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/string_map.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 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/string_map.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