From 2b26384b89ed2b29f9d7db13f73c52029a2a2341 Mon Sep 17 00:00:00 2001 From: gingerBill Date: Fri, 26 Apr 2024 15:04:46 +0100 Subject: Implement dumb `PtrMap` --- src/ptr_map.cpp | 447 ++++++++++++++++++++++++++------------------------------ 1 file changed, 209 insertions(+), 238 deletions(-) (limited to 'src/ptr_map.cpp') diff --git a/src/ptr_map.cpp b/src/ptr_map.cpp index 23278014f..8fd627768 100644 --- a/src/ptr_map.cpp +++ b/src/ptr_map.cpp @@ -16,23 +16,21 @@ struct MapFindResult { }; enum : MapIndex { MAP_SENTINEL = ~(MapIndex)0 }; +static void *const MAP_TOMBSTONE = (void *)~(uintptr)0; template struct PtrMapEntry { static_assert(sizeof(K) == sizeof(void *), "Key size must be pointer size"); - K key; - V value; - MapIndex next; + K key; + V value; }; template struct PtrMap { - MapIndex * hashes; - usize hashes_count; PtrMapEntry *entries; u32 count; - u32 entries_capacity; + u32 capacity; }; @@ -69,7 +67,6 @@ template gb_internal void map_grow (PtrMap< template gb_internal void map_rehash (PtrMap *h, isize new_count); template gb_internal void map_reserve (PtrMap *h, isize cap); -#if PTR_MAP_ENABLE_MULTI_MAP // Mutlivalued map procedure template gb_internal PtrMapEntry * multi_map_find_first(PtrMap *h, K key); template gb_internal PtrMapEntry * multi_map_find_next (PtrMap *h, PtrMapEntry *e); @@ -79,7 +76,6 @@ template gb_internal void multi_map_get_all (PtrMap< template gb_internal void multi_map_insert (PtrMap *h, K key, V const &value); template gb_internal void multi_map_remove (PtrMap *h, K key, PtrMapEntry *e); template gb_internal void multi_map_remove_all(PtrMap *h, K key); -#endif gb_internal gbAllocator map_allocator(void) { return heap_allocator(); @@ -94,170 +90,141 @@ gb_internal gb_inline void map_init(PtrMap *h, isize capacity) { template gb_internal gb_inline void map_destroy(PtrMap *h) { gbAllocator a = map_allocator(); - gb_free(a, h->hashes); gb_free(a, h->entries); } -template -gb_internal void map__resize_hashes(PtrMap *h, usize count) { - h->hashes_count = cast(u32)resize_array_raw(&h->hashes, map_allocator(), h->hashes_count, count, MAP_CACHE_LINE_SIZE); -} - -template -gb_internal void map__reserve_entries(PtrMap *h, usize capacity) { - h->entries_capacity = cast(u32)resize_array_raw(&h->entries, map_allocator(), h->entries_capacity, capacity, MAP_CACHE_LINE_SIZE); -} - template -gb_internal MapIndex map__add_entry(PtrMap *h, K key) { - PtrMapEntry e = {}; - e.key = key; - e.next = MAP_SENTINEL; - if (h->count+1 >= h->entries_capacity) { - map__reserve_entries(h, gb_max(h->entries_capacity*2, 4)); - } - h->entries[h->count++] = e; - return cast(MapIndex)(h->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; +gb_internal void map__insert(PtrMap *h, K key, V const &value) { + if (h->count+1 >= h->capacity) { + map_grow(h); } u32 hash = ptr_map_hash_key(key); - fr.hash_index = cast(MapIndex)(hash & (h->hashes_count-1)); - fr.entry_index = h->hashes[fr.hash_index]; - while (fr.entry_index != MAP_SENTINEL) { - auto *entry = &h->entries[fr.entry_index]; - if (entry->key == key) { - return fr; + u32 mask = h->capacity-1; + MapIndex index = hash & mask; + MapIndex original_index = index; + do { + auto *entry = h->entries+index; + if (!entry->key || entry->key == cast(K)MAP_TOMBSTONE) { + entry->key = key; + entry->value = value; + h->count += 1; + return; } - fr.entry_prev = fr.entry_index; - fr.entry_index = entry->next; - } - return fr; -} + index = (index+1)&mask; + } while (index != original_index); -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; - } - u32 hash = ptr_map_hash_key(e->key); - fr.hash_index = cast(MapIndex)(hash & (h->hashes_count-1)); - fr.entry_index = h->hashes[fr.hash_index]; - while (fr.entry_index != MAP_SENTINEL) { - if (&h->entries[fr.entry_index] == e) { - return fr; - } - fr.entry_prev = fr.entry_index; - fr.entry_index = h->entries[fr.entry_index].next; - } - return fr; + GB_PANIC("FAILED TO INSERT"); } template gb_internal b32 map__full(PtrMap *h) { - return 0.75f * h->hashes_count <= h->count; + return 0.75f * h->capacity <= h->count; } template gb_internal gb_inline void map_grow(PtrMap *h) { - isize new_count = gb_max(h->hashes_count<<1, 16); - map_rehash(h, new_count); + isize new_capacity = gb_max(h->capacity<<1, 16); + map_reserve(h, new_capacity); } template -gb_internal void map_reset_entries(PtrMap *h) { - for (usize i = 0; i < h->hashes_count; i++) { - h->hashes[i] = MAP_SENTINEL; - } - for (usize i = 0; i < h->count; i++) { - MapFindResult fr; - PtrMapEntry *e = &h->entries[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; - } +gb_internal void try_map_grow(PtrMap *h) { + if (h->capacity == 0 || map__full(h)) { + map_grow(h); } } + template gb_internal void map_reserve(PtrMap *h, isize cap) { - if (h->count*2 < h->hashes_count) { + if (cap < h->capacity) { return; } - map__reserve_entries(h, cap); - map__resize_hashes(h, cap*2); - map_reset_entries(h); -} + cap = next_pow2_isize(cap); + typedef PtrMapEntry EntryType; + PtrMap new_h = {}; + new_h.count = 0; + new_h.capacity = cast(u32)cap; + new_h.entries = gb_alloc_array(string_map_allocator(), EntryType, new_h.capacity); -template -gb_internal void map_rehash(PtrMap *h, isize new_count) { - map_reserve(h, new_count); + if (h->count) { + for (u32 i = 0; i < h->capacity; i++) { + auto *entry = h->entries+i; + if (entry->key && + entry->key != cast(K)MAP_TOMBSTONE) { + map__insert(&new_h, entry->key, entry->value); + } + } + } + map_destroy(h); + *h = new_h; } template gb_internal V *map_get(PtrMap *h, K key) { - MapIndex hash_index = MAP_SENTINEL; - MapIndex entry_prev = MAP_SENTINEL; - MapIndex entry_index = MAP_SENTINEL; - if (h->hashes_count != 0) { - u32 hash = ptr_map_hash_key(key); - hash_index = cast(MapIndex)(hash & (h->hashes_count-1)); - entry_index = h->hashes[hash_index]; - while (entry_index != MAP_SENTINEL) { - auto *entry = &h->entries[entry_index]; - if (entry->key == key) { - return &entry->value; - } - entry_prev = entry_index; - entry_index = entry->next; - } + if (h->count == 0) { + return nullptr; + } + if (key == 0) { + GB_PANIC("0 key"); } + + u32 hash = ptr_map_hash_key(key); + u32 mask = (h->capacity-1); + u32 index = hash & mask; + u32 original_index = index; + do { + auto *entry = h->entries+index; + if (!entry->key) { + // NOTE(bill): no found, but there isn't any key removal for this hash map + return nullptr; + } else if (entry->key == key) { + return &entry->value; + } + index = (index+1) & mask; + } while (original_index != index); return nullptr; } template -gb_internal V *map_try_get(PtrMap *h, K key, MapFindResult *fr_) { - 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[fr.hash_index]; - while (fr.entry_index != MAP_SENTINEL) { - auto *entry = &h->entries[fr.entry_index]; - if (entry->key == key) { - return &entry->value; - } - fr.entry_prev = fr.entry_index; - fr.entry_index = entry->next; - } +gb_internal V *map_try_get(PtrMap *h, K key, MapIndex *found_index_) { + if (found_index_) *found_index_ = ~(MapIndex)0; + + if (h->count == 0) { + return nullptr; } - if (h->hashes_count == 0 || map__full(h)) { - map_grow(h); + if (key == 0) { + GB_PANIC("0 key"); } - if (fr_) *fr_ = fr; + + u32 hash = ptr_map_hash_key(key); + u32 mask = (h->capacity-1); + u32 index = hash & mask; + u32 original_index = index; + do { + auto *entry = h->entries+index; + if (!entry->key) { + // NOTE(bill): no found, but there isn't any key removal for this hash map + return nullptr; + } else if (entry->key == key) { + if (found_index_) *found_index_ = index; + return &entry->value; + } + index = (index+1) & mask; + } while (original_index != index); return nullptr; } template -gb_internal void map_set_internal_from_try_get(PtrMap *h, K key, V const &value, MapFindResult const &fr) { - MapIndex index = map__add_entry(h, key); - if (fr.entry_prev != MAP_SENTINEL) { - h->entries[fr.entry_prev].next = index; +gb_internal void map_set_internal_from_try_get(PtrMap *h, K key, V const &value, MapIndex found_index) { + if (found_index != MAP_SENTINEL) { + GB_ASSERT(h->entries[found_index].key == key); + h->entries[found_index].value = value; } else { - h->hashes[fr.hash_index] = index; + map_set(h, key, value); } - h->entries[index].value = value; } template @@ -269,116 +236,83 @@ gb_internal V &map_must_get(PtrMap *h, K key) { template gb_internal 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[fr.entry_prev].next = index; - } else { - h->hashes[fr.hash_index] = index; - } - } - h->entries[index].value = value; - - if (map__full(h)) { - map_grow(h); + GB_ASSERT(key != 0); + try_map_grow(h); + auto *found = map_get(h, key); + if (found) { + *found = value; + return; } + map__insert(h, key, value); } // returns true if it previously existed template gb_internal bool map_set_if_not_previously_exists(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) { + try_map_grow(h); + auto *found = map_get(h, key); + if (found) { return true; - } else { - index = map__add_entry(h, key); - if (fr.entry_prev != MAP_SENTINEL) { - h->entries[fr.entry_prev].next = index; - } else { - h->hashes[fr.hash_index] = index; - } - } - h->entries[index].value = value; - - if (map__full(h)) { - map_grow(h); } + map__insert(h, key, value); return false; } -template -gb_internal void map__erase(PtrMap *h, MapFindResult const &fr) { - MapFindResult last; - if (fr.entry_prev == MAP_SENTINEL) { - h->hashes[fr.hash_index] = h->entries[fr.entry_index].next; - } else { - h->entries[fr.entry_prev].next = h->entries[fr.entry_index].next; - } - if (fr.entry_index == h->count-1) { - h->count--; - return; - } - h->entries[fr.entry_index] = h->entries[h->count-1]; - h->count--; - - last = map__find(h, h->entries[fr.entry_index].key); - if (last.entry_prev != MAP_SENTINEL) { - h->entries[last.entry_prev].next = fr.entry_index; - } else { - h->hashes[last.hash_index] = fr.entry_index; - } -} - template gb_internal void map_remove(PtrMap *h, K key) { - MapFindResult fr = map__find(h, key); - if (fr.entry_index != MAP_SENTINEL) { - map__erase(h, fr); + MapIndex found_index = 0; + if (map_try_get(h, key, &found_index)) { + h->entries[found_index].key = cast(K)MAP_TOMBSTONE; + h->count -= 1; } } template gb_internal gb_inline void map_clear(PtrMap *h) { h->count = 0; - for (usize i = 0; i < h->hashes_count; i++) { - h->hashes[i] = MAP_SENTINEL; - } + gb_zero_array(h->entries, h->capacity); } #if PTR_MAP_ENABLE_MULTI_MAP template gb_internal PtrMapEntry *multi_map_find_first(PtrMap *h, K key) { - MapIndex i = map__find(h, key).entry_index; - if (i == MAP_SENTINEL) { + if (h->count == 0) { return nullptr; } - return &h->entries[i]; + u32 hash = ptr_map_hash_key(key); + u32 mask = (h->capacity-1); + u32 index = hash & mask; + u32 original_index = index; + do { + auto *entry = h->entries+index; + if (!entry->key) { + // NOTE(bill): no found, but there isn't any key removal for this hash map + return nullptr; + } else if (entry->key == key) { + return entry; + } + index = (index+1) & mask; + } while (original_index != index); + return nullptr; } template gb_internal PtrMapEntry *multi_map_find_next(PtrMap *h, PtrMapEntry *e) { - MapIndex i = e->next; - while (i != MAP_SENTINEL) { - if (h->entries[i].key == e->key) { - return &h->entries[i]; + u32 mask = h->capacity-1; + MapIndex index = cast(MapIndex)(e - h->entries); + MapIndex original_index = index; + do { + index = (index+1)&mask; + auto *entry = h->entries+index; + if (!entry->key) { + return nullptr; } - i = h->entries[i].next; - } + if (entry->key == e->key) { + return entry; + } + } while (original_index != index); return nullptr; } @@ -405,34 +339,16 @@ gb_internal void multi_map_get_all(PtrMap *h, K key, V *items) { template gb_internal 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[fr.hash_index] = i; - } else { - h->entries[fr.entry_prev].next = i; - } - h->entries[i].next = fr.entry_index; - h->entries[i].value = value; - // Grow if needed - if (map__full(h)) { - map_grow(h); - } + try_map_grow(h); + map__insert(h, key, value); } -template -gb_internal 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); - } -} +// template +// gb_internal void multi_map_remove(PtrMap *h, K key, PtrMapEntry *e) { +// if (fr.entry_index != MAP_SENTINEL) { +// map__erase(h, fr); +// } +// } template gb_internal void multi_map_remove_all(PtrMap *h, K key) { @@ -443,22 +359,77 @@ gb_internal void multi_map_remove_all(PtrMap *h, K key) { #endif + + +template +struct PtrMapIterator { + PtrMap *map; + MapIndex index; + + PtrMapIterator &operator++() noexcept { + for (;;) { + ++index; + if (map->capacity == index) { + return *this; + } + PtrMapEntry *entry = map->entries+index; + if (entry->key && entry->key != cast(K)MAP_TOMBSTONE) { + return *this; + } + } + } + + bool operator==(PtrMapIterator const &other) const noexcept { + return this->map == other->map && this->index == other->index; + } + + operator PtrMapEntry *() const { + return map->entries+index; + } +}; + + template -gb_internal PtrMapEntry *begin(PtrMap &m) { - return m.entries; +gb_internal PtrMapIterator end(PtrMap &m) noexcept { + return PtrMapIterator{&m, m.capacity}; } + template -gb_internal PtrMapEntry const *begin(PtrMap const &m) { - return m.entries; +gb_internal PtrMapIterator const end(PtrMap const &m) noexcept { + return PtrMapIterator{&m, m.capacity}; } + template -gb_internal PtrMapEntry *end(PtrMap &m) { - return m.entries + m.count; -} +gb_internal PtrMapIterator begin(PtrMap &m) noexcept { + if (m.count == 0) { + return end(m); + } + MapIndex index = 0; + while (index < m.capacity) { + auto key = m.entries[index].key; + if (key && key != cast(K)MAP_TOMBSTONE) { + break; + } + index++; + } + return PtrMapIterator{&m, index}; +} template -gb_internal PtrMapEntry const *end(PtrMap const &m) { - return m.entries + m.count; +gb_internal PtrMapIterator const begin(PtrMap const &m) noexcept { + if (m.count == 0) { + return end(m); + } + + MapIndex index = 0; + while (index < m.capacity) { + auto key = m.entries[index].key; + if (key && key != cast(K)MAP_TOMBSTONE) { + break; + } + index++; + } + return PtrMapIterator{&m, index}; } -- cgit v1.2.3 From 652079476489b2539c77824ec2719847f28c352d Mon Sep 17 00:00:00 2001 From: gingerBill Date: Sat, 27 Apr 2024 08:50:05 +0100 Subject: Fix wrong allocator usage --- src/ptr_map.cpp | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'src/ptr_map.cpp') diff --git a/src/ptr_map.cpp b/src/ptr_map.cpp index 8fd627768..362e412ba 100644 --- a/src/ptr_map.cpp +++ b/src/ptr_map.cpp @@ -147,7 +147,7 @@ gb_internal void map_reserve(PtrMap *h, isize cap) { PtrMap new_h = {}; new_h.count = 0; new_h.capacity = cast(u32)cap; - new_h.entries = gb_alloc_array(string_map_allocator(), EntryType, new_h.capacity); + new_h.entries = gb_alloc_array(map_allocator(), EntryType, new_h.capacity); if (h->count) { for (u32 i = 0; i < h->capacity; i++) { -- cgit v1.2.3 From ad0053b7982d38212d4c2f3f1bf97d10ac52a28b Mon Sep 17 00:00:00 2001 From: gingerBill Date: Sat, 11 May 2024 16:24:37 +0100 Subject: Make doc writer use the old "Ordered Insertion" based `PtrMap` --- src/docs_writer.cpp | 34 ++-- src/ptr_map.cpp | 438 +++++++++++++++++++++++++++++++++++++++++++++++++++- 2 files changed, 449 insertions(+), 23 deletions(-) (limited to 'src/ptr_map.cpp') diff --git a/src/docs_writer.cpp b/src/docs_writer.cpp index ba71eae4d..ad8d9d245 100644 --- a/src/docs_writer.cpp +++ b/src/docs_writer.cpp @@ -26,11 +26,11 @@ struct OdinDocWriter { StringMap string_cache; - PtrMap file_cache; - PtrMap pkg_cache; - PtrMap entity_cache; - PtrMap type_cache; - PtrMap stable_type_cache; + OrderedInsertPtrMap file_cache; + OrderedInsertPtrMap pkg_cache; + OrderedInsertPtrMap entity_cache; + OrderedInsertPtrMap type_cache; + OrderedInsertPtrMap stable_type_cache; OdinDocWriterItemTracker files; OdinDocWriterItemTracker pkgs; @@ -57,11 +57,11 @@ gb_internal void odin_doc_writer_prepare(OdinDocWriter *w) { string_map_init(&w->string_cache); - map_init(&w->file_cache); - map_init(&w->pkg_cache); - map_init(&w->entity_cache); - map_init(&w->type_cache); - map_init(&w->stable_type_cache); + map_init(&w->file_cache, 1<<10); + map_init(&w->pkg_cache, 1<<10); + map_init(&w->entity_cache, 1<<18); + map_init(&w->type_cache, 1<<18); + map_init(&w->stable_type_cache, 1<<18); odin_doc_writer_item_tracker_init(&w->files, 1); odin_doc_writer_item_tracker_init(&w->pkgs, 1); @@ -485,6 +485,13 @@ gb_internal OdinDocTypeIndex odin_doc_type(OdinDocWriter *w, Type *type) { return 0; } + if (type->kind == Type_Named) { + Entity *e = type->Named.type_name; + if (e->TypeName.is_type_alias) { + type = type->Named.base; + } + } + // Type **mapped_type = map_get(&w->stable_type_cache, type); // may map to itself // if (mapped_type && *mapped_type) { // type = *mapped_type; @@ -506,13 +513,6 @@ gb_internal OdinDocTypeIndex odin_doc_type(OdinDocWriter *w, Type *type) { if (!x | !y) { continue; } - - if (x->kind == Type_Named) { - Entity *e = x->Named.type_name; - if (e->TypeName.is_type_alias) { - x = x->Named.base; - } - } if (y->kind == Type_Named) { Entity *e = y->Named.type_name; if (e->TypeName.is_type_alias) { diff --git a/src/ptr_map.cpp b/src/ptr_map.cpp index 362e412ba..1c157c386 100644 --- a/src/ptr_map.cpp +++ b/src/ptr_map.cpp @@ -9,12 +9,6 @@ enum { }; -struct MapFindResult { - MapIndex hash_index; - MapIndex entry_prev; - MapIndex entry_index; -}; - enum : MapIndex { MAP_SENTINEL = ~(MapIndex)0 }; static void *const MAP_TOMBSTONE = (void *)~(uintptr)0; @@ -433,3 +427,435 @@ gb_internal PtrMapIterator const begin(PtrMap const &m) noexcept { } return PtrMapIterator{&m, index}; } + + +/////////////////////////////////////////////////////////////////////////////// +/////////////////////////////////////////////////////////////////////////////// +/////////////////////////////////////////////////////////////////////////////// +/////////////////////////////////////////////////////////////////////////////// +/////////////////////////////////////////////////////////////////////////////// +/////////////////////////////////////////////////////////////////////////////// +/////////////////////////////////////////////////////////////////////////////// +/////////////////////////////////////////////////////////////////////////////// +/////////////////////////////////////////////////////////////////////////////// + +struct MapFindResult { + MapIndex hash_index; + MapIndex entry_prev; + MapIndex entry_index; +}; + +template +struct OrderedInsertPtrMapEntry { + static_assert(sizeof(K) == sizeof(void *), "Key size must be pointer size"); + + K key; + V value; + MapIndex next; +}; + +template +struct OrderedInsertPtrMap { + MapIndex *hashes; + usize hashes_count; + OrderedInsertPtrMapEntry *entries; + u32 count; + u32 entries_capacity; +}; + + +template gb_internal void map_destroy (OrderedInsertPtrMap *h); +template gb_internal V * map_get (OrderedInsertPtrMap *h, K key); +template gb_internal void map_set (OrderedInsertPtrMap *h, K key, V const &value); +template gb_internal bool map_set_if_not_previously_exists(OrderedInsertPtrMap *h, K key, V const &value); // returns true if it previously existed +template gb_internal void map_remove (OrderedInsertPtrMap *h, K key); +template gb_internal void map_clear (OrderedInsertPtrMap *h); +template gb_internal void map_grow (OrderedInsertPtrMap *h); +template gb_internal void map_rehash (OrderedInsertPtrMap *h, isize new_count); +template gb_internal void map_reserve (OrderedInsertPtrMap *h, isize cap); + +// Mutlivalued map procedure +template gb_internal OrderedInsertPtrMapEntry * multi_map_find_first(OrderedInsertPtrMap *h, K key); +template gb_internal OrderedInsertPtrMapEntry * multi_map_find_next (OrderedInsertPtrMap *h, OrderedInsertPtrMapEntry *e); + +template gb_internal isize multi_map_count (OrderedInsertPtrMap *h, K key); +template gb_internal void multi_map_get_all (OrderedInsertPtrMap *h, K key, V *items); +template gb_internal void multi_map_insert (OrderedInsertPtrMap *h, K key, V const &value); +template gb_internal void multi_map_remove (OrderedInsertPtrMap *h, K key, OrderedInsertPtrMapEntry *e); +template gb_internal void multi_map_remove_all(OrderedInsertPtrMap *h, K key); + +template +gb_internal gb_inline void map_init(OrderedInsertPtrMap *h, isize capacity) { + capacity = next_pow2_isize(capacity); + map_reserve(h, capacity); +} + +template +gb_internal gb_inline void map_destroy(OrderedInsertPtrMap *h) { + gbAllocator a = map_allocator(); + gb_free(a, h->hashes); + gb_free(a, h->entries); +} + +template +gb_internal void map__resize_hashes(OrderedInsertPtrMap *h, usize count) { + h->hashes_count = cast(u32)resize_array_raw(&h->hashes, map_allocator(), h->hashes_count, count, MAP_CACHE_LINE_SIZE); +} + +template +gb_internal void map__reserve_entries(OrderedInsertPtrMap *h, usize capacity) { + h->entries_capacity = cast(u32)resize_array_raw(&h->entries, map_allocator(), h->entries_capacity, capacity, MAP_CACHE_LINE_SIZE); +} + + +template +gb_internal MapIndex map__add_entry(OrderedInsertPtrMap *h, K key) { + OrderedInsertPtrMapEntry e = {}; + e.key = key; + e.next = MAP_SENTINEL; + if (h->count+1 >= h->entries_capacity) { + map__reserve_entries(h, gb_max(h->entries_capacity*2, 4)); + } + h->entries[h->count++] = e; + return cast(MapIndex)(h->count-1); +} + +template +gb_internal MapFindResult map__find(OrderedInsertPtrMap *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[fr.hash_index]; + while (fr.entry_index != MAP_SENTINEL) { + auto *entry = &h->entries[fr.entry_index]; + if (entry->key == key) { + return fr; + } + fr.entry_prev = fr.entry_index; + fr.entry_index = entry->next; + } + return fr; +} + +template +gb_internal MapFindResult map__find_from_entry(OrderedInsertPtrMap *h, OrderedInsertPtrMapEntry *e) { + MapFindResult fr = {MAP_SENTINEL, MAP_SENTINEL, MAP_SENTINEL}; + if (h->hashes_count == 0) { + return fr; + } + u32 hash = ptr_map_hash_key(e->key); + fr.hash_index = cast(MapIndex)(hash & (h->hashes_count-1)); + fr.entry_index = h->hashes[fr.hash_index]; + while (fr.entry_index != MAP_SENTINEL) { + if (&h->entries[fr.entry_index] == e) { + return fr; + } + fr.entry_prev = fr.entry_index; + fr.entry_index = h->entries[fr.entry_index].next; + } + return fr; +} + +template +gb_internal b32 map__full(OrderedInsertPtrMap *h) { + return 0.75f * h->hashes_count <= h->count; +} + +template +gb_internal gb_inline void map_grow(OrderedInsertPtrMap *h) { + isize new_count = gb_max(h->hashes_count<<1, 16); + map_rehash(h, new_count); +} + +template +gb_internal void map_reset_entries(OrderedInsertPtrMap *h) { + for (usize i = 0; i < h->hashes_count; i++) { + h->hashes[i] = MAP_SENTINEL; + } + for (usize i = 0; i < h->count; i++) { + MapFindResult fr; + OrderedInsertPtrMapEntry *e = &h->entries[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 +gb_internal void map_reserve(OrderedInsertPtrMap *h, isize cap) { + if (h->count*2 < h->hashes_count) { + return; + } + map__reserve_entries(h, cap); + map__resize_hashes(h, cap*2); + map_reset_entries(h); +} + + +template +gb_internal void map_rehash(OrderedInsertPtrMap *h, isize new_count) { + map_reserve(h, new_count); +} + +template +gb_internal V *map_get(OrderedInsertPtrMap *h, K key) { + MapIndex hash_index = MAP_SENTINEL; + MapIndex entry_prev = MAP_SENTINEL; + MapIndex entry_index = MAP_SENTINEL; + if (h->hashes_count != 0) { + u32 hash = ptr_map_hash_key(key); + hash_index = cast(MapIndex)(hash & (h->hashes_count-1)); + entry_index = h->hashes[hash_index]; + while (entry_index != MAP_SENTINEL) { + auto *entry = &h->entries[entry_index]; + if (entry->key == key) { + return &entry->value; + } + entry_prev = entry_index; + entry_index = entry->next; + } + } + return nullptr; +} +template +gb_internal V *map_try_get(OrderedInsertPtrMap *h, K key, MapFindResult *fr_) { + 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[fr.hash_index]; + while (fr.entry_index != MAP_SENTINEL) { + auto *entry = &h->entries[fr.entry_index]; + if (entry->key == key) { + return &entry->value; + } + fr.entry_prev = fr.entry_index; + fr.entry_index = entry->next; + } + } + if (h->hashes_count == 0 || map__full(h)) { + map_grow(h); + } + if (fr_) *fr_ = fr; + return nullptr; +} + + +template +gb_internal void map_set_internal_from_try_get(OrderedInsertPtrMap *h, K key, V const &value, MapFindResult const &fr) { + MapIndex index = map__add_entry(h, key); + if (fr.entry_prev != MAP_SENTINEL) { + h->entries[fr.entry_prev].next = index; + } else { + h->hashes[fr.hash_index] = index; + } + h->entries[index].value = value; +} + +template +gb_internal V &map_must_get(OrderedInsertPtrMap *h, K key) { + V *ptr = map_get(h, key); + GB_ASSERT(ptr != nullptr); + return *ptr; +} + +template +gb_internal void map_set(OrderedInsertPtrMap *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[fr.entry_prev].next = index; + } else { + h->hashes[fr.hash_index] = index; + } + } + h->entries[index].value = value; + + if (map__full(h)) { + map_grow(h); + } +} + +// returns true if it previously existed +template +gb_internal bool map_set_if_not_previously_exists(OrderedInsertPtrMap *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) { + return true; + } else { + index = map__add_entry(h, key); + if (fr.entry_prev != MAP_SENTINEL) { + h->entries[fr.entry_prev].next = index; + } else { + h->hashes[fr.hash_index] = index; + } + } + h->entries[index].value = value; + + if (map__full(h)) { + map_grow(h); + } + return false; +} + + +template +gb_internal void map__erase(OrderedInsertPtrMap *h, MapFindResult const &fr) { + MapFindResult last; + if (fr.entry_prev == MAP_SENTINEL) { + h->hashes[fr.hash_index] = h->entries[fr.entry_index].next; + } else { + h->entries[fr.entry_prev].next = h->entries[fr.entry_index].next; + } + if (fr.entry_index == h->count-1) { + h->count--; + return; + } + h->entries[fr.entry_index] = h->entries[h->count-1]; + h->count--; + + last = map__find(h, h->entries[fr.entry_index].key); + if (last.entry_prev != MAP_SENTINEL) { + h->entries[last.entry_prev].next = fr.entry_index; + } else { + h->hashes[last.hash_index] = fr.entry_index; + } +} + +template +gb_internal void map_remove(OrderedInsertPtrMap *h, K key) { + MapFindResult fr = map__find(h, key); + if (fr.entry_index != MAP_SENTINEL) { + map__erase(h, fr); + } +} + +template +gb_internal gb_inline void map_clear(OrderedInsertPtrMap *h) { + h->count = 0; + for (usize i = 0; i < h->hashes_count; i++) { + h->hashes[i] = MAP_SENTINEL; + } +} + + +template +gb_internal OrderedInsertPtrMapEntry *multi_map_find_first(OrderedInsertPtrMap *h, K key) { + MapIndex i = map__find(h, key).entry_index; + if (i == MAP_SENTINEL) { + return nullptr; + } + return &h->entries[i]; +} + +template +gb_internal OrderedInsertPtrMapEntry *multi_map_find_next(OrderedInsertPtrMap *h, OrderedInsertPtrMapEntry *e) { + MapIndex i = e->next; + while (i != MAP_SENTINEL) { + if (h->entries[i].key == e->key) { + return &h->entries[i]; + } + i = h->entries[i].next; + } + return nullptr; +} + +template +gb_internal isize multi_map_count(OrderedInsertPtrMap *h, K key) { + isize count = 0; + OrderedInsertPtrMapEntry *e = multi_map_find_first(h, key); + while (e != nullptr) { + count++; + e = multi_map_find_next(h, e); + } + return count; +} + +template +gb_internal void multi_map_get_all(OrderedInsertPtrMap *h, K key, V *items) { + usize i = 0; + OrderedInsertPtrMapEntry *e = multi_map_find_first(h, key); + while (e != nullptr) { + items[i++] = e->value; + e = multi_map_find_next(h, e); + } +} + +template +gb_internal void multi_map_insert(OrderedInsertPtrMap *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[fr.hash_index] = i; + } else { + h->entries[fr.entry_prev].next = i; + } + h->entries[i].next = fr.entry_index; + h->entries[i].value = value; + // Grow if needed + if (map__full(h)) { + map_grow(h); + } +} + +template +gb_internal void multi_map_remove(OrderedInsertPtrMap *h, K key, OrderedInsertPtrMapEntry *e) { + MapFindResult fr = map__find_from_entry(h, e); + if (fr.entry_index != MAP_SENTINEL) { + map__erase(h, fr); + } +} + +template +gb_internal void multi_map_remove_all(OrderedInsertPtrMap *h, K key) { + while (map_get(h, key) != nullptr) { + map_remove(h, key); + } +} + + +template +gb_internal OrderedInsertPtrMapEntry *begin(OrderedInsertPtrMap &m) { + return m.entries; +} +template +gb_internal OrderedInsertPtrMapEntry const *begin(OrderedInsertPtrMap const &m) { + return m.entries; +} + + +template +gb_internal OrderedInsertPtrMapEntry *end(OrderedInsertPtrMap &m) { + return m.entries + m.count; +} + +template +gb_internal OrderedInsertPtrMapEntry const *end(OrderedInsertPtrMap const &m) { + return m.entries + m.count; +} \ No newline at end of file -- cgit v1.2.3