From 9b61adb97dd78e1cf04ad410e72166f684f97925 Mon Sep 17 00:00:00 2001 From: Ginger Bill Date: Thu, 8 Jun 2017 12:03:40 +0100 Subject: Build as C++ --- src/map.cpp | 364 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 364 insertions(+) create mode 100644 src/map.cpp (limited to 'src/map.cpp') diff --git a/src/map.cpp b/src/map.cpp new file mode 100644 index 000000000..d616490e2 --- /dev/null +++ b/src/map.cpp @@ -0,0 +1,364 @@ +/* + Example of usage: + + #define MAP_TYPE String + #define MAP_PROC map_string_ + #define MAP_NAME MapString + #include "map.cpp" +*/ +// 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_*` stuff to be #ifdefed out + +#ifndef MAP_UTIL_STUFF +#define MAP_UTIL_STUFF +// NOTE(bill): This util stuff is the same for every `Map` +typedef struct MapFindResult { + isize hash_index; + isize entry_prev; + isize entry_index; +} MapFindResult; + +typedef enum HashKeyKind { + HashKey_Default, + HashKey_String, + HashKey_Pointer, +} HashKeyKind; + +typedef struct HashKey { + HashKeyKind kind; + u64 key; + union { + String string; // if String, s.len > 0 + void * ptr; + }; +} HashKey; + +gb_inline HashKey hashing_proc(void const *data, isize len) { + HashKey h = {HashKey_Default}; + h.kind = HashKey_Default; + // h.key = gb_murmur64(data, len); + h.key = gb_fnv64a(data, len); + // h.key = MurmurHash3_128(data, len, 0x3803cb8e); + + return h; +} + +gb_inline HashKey hash_string(String s) { + HashKey h = hashing_proc(s.text, s.len); + h.kind = HashKey_String; + h.string = s; + return h; +} + +gb_inline HashKey hash_pointer(void *ptr) { + HashKey h = {HashKey_Default}; + // h.key = u128_from_u64(cast(u64)cast(uintptr)ptr); + h.key = cast(u64)cast(uintptr)ptr; + h.ptr = ptr; + h.kind = HashKey_Default; + return h; +} + +bool hash_key_equal(HashKey a, HashKey b) { + if (a.key == b.key) { + // NOTE(bill): If two string's hashes collide, compare the strings themselves + if (a.kind == HashKey_String) { + if (b.kind == HashKey_String) { + return str_eq(a.string, b.string); + } + return false; + } + return true; + } + return false; +} +#endif + +#define _J2_IND(a, b) a##b +#define _J2(a, b) _J2_IND(a, b) + +/* +MAP_TYPE - Entry type +MAP_PROC - Function prefix (e.g. entity_map_) +MAP_NAME - Name of Map (e.g. EntityMap) +*/ +#define MAP_ENTRY _J2(MAP_NAME,Entry) + +typedef struct MAP_ENTRY { + HashKey key; + isize next; + MAP_TYPE value; +} MAP_ENTRY; + +typedef struct MAP_NAME { + Array(isize) hashes; + Array(MAP_ENTRY) entries; +} MAP_NAME; + +void _J2(MAP_PROC,init) (MAP_NAME *h, gbAllocator a); +void _J2(MAP_PROC,init_with_reserve)(MAP_NAME *h, gbAllocator a, isize capacity); +void _J2(MAP_PROC,destroy) (MAP_NAME *h); +MAP_TYPE *_J2(MAP_PROC,get) (MAP_NAME *h, HashKey key); +void _J2(MAP_PROC,set) (MAP_NAME *h, HashKey key, MAP_TYPE value); +void _J2(MAP_PROC,remove) (MAP_NAME *h, HashKey key); +void _J2(MAP_PROC,clear) (MAP_NAME *h); +void _J2(MAP_PROC,grow) (MAP_NAME *h); +void _J2(MAP_PROC,rehash) (MAP_NAME *h, isize new_count); + +// Mutlivalued map procedure +MAP_ENTRY *_J2(MAP_PROC,multi_find_first)(MAP_NAME *h, HashKey key); +MAP_ENTRY *_J2(MAP_PROC,multi_find_next) (MAP_NAME *h, MAP_ENTRY *e); + +isize _J2(MAP_PROC,multi_count) (MAP_NAME *h, HashKey key); +void _J2(MAP_PROC,multi_get_all) (MAP_NAME *h, HashKey key, MAP_TYPE *items); +void _J2(MAP_PROC,multi_insert) (MAP_NAME *h, HashKey key, MAP_TYPE value); +void _J2(MAP_PROC,multi_remove) (MAP_NAME *h, HashKey key, MAP_ENTRY *e); +void _J2(MAP_PROC,multi_remove_all)(MAP_NAME *h, HashKey key); + + + +gb_inline void _J2(MAP_PROC,init)(MAP_NAME *h, gbAllocator a) { + array_init(&h->hashes, a); + array_init(&h->entries, a); +} + +gb_inline void _J2(MAP_PROC,init_with_reserve)(MAP_NAME *h, gbAllocator a, isize capacity) { + array_init_reserve(&h->hashes, a, capacity); + array_init_reserve(&h->entries, a, capacity); +} + +gb_inline void _J2(MAP_PROC,destroy)(MAP_NAME *h) { + array_free(&h->entries); + array_free(&h->hashes); +} + +gb_internal isize _J2(MAP_PROC,_add_entry)(MAP_NAME *h, HashKey key) { + MAP_ENTRY e = {}; + e.key = key; + e.next = -1; + array_add(&h->entries, e); + return h->entries.count-1; +} + +gb_internal MapFindResult _J2(MAP_PROC,_find)(MAP_NAME *h, HashKey key) { + MapFindResult fr = {-1, -1, -1}; + if (h->hashes.count > 0) { + fr.hash_index = key.key % h->hashes.count; + fr.entry_index = h->hashes.e[fr.hash_index]; + while (fr.entry_index >= 0) { + if (hash_key_equal(h->entries.e[fr.entry_index].key, key)) { + return fr; + } + fr.entry_prev = fr.entry_index; + fr.entry_index = h->entries.e[fr.entry_index].next; + } + } + return fr; +} + +gb_internal MapFindResult _J2(MAP_PROC,_find_from_entry)(MAP_NAME *h, MAP_ENTRY *e) { + MapFindResult fr = {-1, -1, -1}; + if (h->hashes.count > 0) { + fr.hash_index = e->key.key % h->hashes.count; + fr.entry_index = h->hashes.e[fr.hash_index]; + while (fr.entry_index >= 0) { + if (&h->entries.e[fr.entry_index] == e) { + return fr; + } + fr.entry_prev = fr.entry_index; + fr.entry_index = h->entries.e[fr.entry_index].next; + } + } + return fr; +} + + +gb_internal b32 _J2(MAP_PROC,_full)(MAP_NAME *h) { + return 0.75f * h->hashes.count <= h->entries.count; +} + +gb_inline void _J2(MAP_PROC,grow)(MAP_NAME *h) { + isize new_count = ARRAY_GROW_FORMULA(h->entries.count); + _J2(MAP_PROC,rehash)(h, new_count); +} + +void _J2(MAP_PROC,rehash)(MAP_NAME *h, isize new_count) { + isize i, j; + MAP_NAME nh = {}; + _J2(MAP_PROC,init)(&nh, h->hashes.allocator); + array_resize(&nh.hashes, new_count); + array_reserve(&nh.entries, h->entries.count); + for (i = 0; i < new_count; i++) { + nh.hashes.e[i] = -1; + } + for (i = 0; i < h->entries.count; i++) { + MAP_ENTRY *e = &h->entries.e[i]; + MapFindResult fr; + if (nh.hashes.count == 0) { + _J2(MAP_PROC,grow)(&nh); + } + fr = _J2(MAP_PROC,_find)(&nh, e->key); + j = _J2(MAP_PROC,_add_entry)(&nh, e->key); + if (fr.entry_prev < 0) { + nh.hashes.e[fr.hash_index] = j; + } else { + nh.entries.e[fr.entry_prev].next = j; + } + nh.entries.e[j].next = fr.entry_index; + nh.entries.e[j].value = e->value; + if (_J2(MAP_PROC,_full)(&nh)) { + _J2(MAP_PROC,grow)(&nh); + } + } + _J2(MAP_PROC,destroy)(h); + *h = nh; +} + +gb_inline MAP_TYPE *_J2(MAP_PROC,get)(MAP_NAME *h, HashKey key) { + isize index = _J2(MAP_PROC,_find)(h, key).entry_index; + if (index >= 0) { + return &h->entries.e[index].value; + } + return NULL; +} + +void _J2(MAP_PROC,set)(MAP_NAME *h, HashKey key, MAP_TYPE value) { + isize index; + MapFindResult fr; + if (h->hashes.count == 0) + _J2(MAP_PROC,grow)(h); + fr = _J2(MAP_PROC,_find)(h, key); + if (fr.entry_index >= 0) { + index = fr.entry_index; + } else { + index = _J2(MAP_PROC,_add_entry)(h, key); + if (fr.entry_prev >= 0) { + h->entries.e[fr.entry_prev].next = index; + } else { + h->hashes.e[fr.hash_index] = index; + } + } + h->entries.e[index].value = value; + + if (_J2(MAP_PROC,_full)(h)) { + _J2(MAP_PROC,grow)(h); + } +} + + + +void _J2(MAP_PROC,_erase)(MAP_NAME *h, MapFindResult fr) { + MapFindResult last; + if (fr.entry_prev < 0) { + h->hashes.e[fr.hash_index] = h->entries.e[fr.entry_index].next; + } else { + h->entries.e[fr.entry_prev].next = h->entries.e[fr.entry_index].next; + } + if (fr.entry_index == h->entries.count-1) { + array_pop(&h->entries); + return; + } + h->entries.e[fr.entry_index] = h->entries.e[h->entries.count-1]; + last = _J2(MAP_PROC,_find)(h, h->entries.e[fr.entry_index].key); + if (last.entry_prev >= 0) { + h->entries.e[last.entry_prev].next = fr.entry_index; + } else { + h->hashes.e[last.hash_index] = fr.entry_index; + } +} + +void _J2(MAP_PROC,remove)(MAP_NAME *h, HashKey key) { + MapFindResult fr = _J2(MAP_PROC,_find)(h, key); + if (fr.entry_index >= 0) { + _J2(MAP_PROC,_erase)(h, fr); + } +} + +gb_inline void _J2(MAP_PROC,clear)(MAP_NAME *h) { + array_clear(&h->hashes); + array_clear(&h->entries); +} + + +#if 1 +MAP_ENTRY *_J2(MAP_PROC,multi_find_first)(MAP_NAME *h, HashKey key) { + isize i = _J2(MAP_PROC,_find)(h, key).entry_index; + if (i < 0) { + return NULL; + } + return &h->entries.e[i]; +} + +MAP_ENTRY *_J2(MAP_PROC,multi_find_next)(MAP_NAME *h, MAP_ENTRY *e) { + isize i = e->next; + while (i >= 0) { + if (hash_key_equal(h->entries.e[i].key, e->key)) { + return &h->entries.e[i]; + } + i = h->entries.e[i].next; + } + return NULL; +} + +isize _J2(MAP_PROC,multi_count)(MAP_NAME *h, HashKey key) { + isize count = 0; + MAP_ENTRY *e = _J2(MAP_PROC,multi_find_first)(h, key); + while (e != NULL) { + count++; + e = _J2(MAP_PROC,multi_find_next)(h, e); + } + return count; +} + +void _J2(MAP_PROC,multi_get_all)(MAP_NAME *h, HashKey key, MAP_TYPE *items) { + isize i = 0; + MAP_ENTRY *e = _J2(MAP_PROC,multi_find_first)(h, key); + while (e != NULL) { + items[i++] = e->value; + e = _J2(MAP_PROC,multi_find_next)(h, e); + } +} + +void _J2(MAP_PROC,multi_insert)(MAP_NAME *h, HashKey key, MAP_TYPE value) { + MapFindResult fr; + isize i; + if (h->hashes.count == 0) { + _J2(MAP_PROC,grow)(h); + } + // Make + fr = _J2(MAP_PROC,_find)(h, key); + i = _J2(MAP_PROC,_add_entry)(h, key); + if (fr.entry_prev < 0) { + h->hashes.e[fr.hash_index] = i; + } else { + h->entries.e[fr.entry_prev].next = i; + } + h->entries.e[i].next = fr.entry_index; + h->entries.e[i].value = value; + // Grow if needed + if (_J2(MAP_PROC,_full)(h)) { + _J2(MAP_PROC,grow)(h); + } +} + +void _J2(MAP_PROC,multi_remove)(MAP_NAME *h, HashKey key, MAP_ENTRY *e) { + MapFindResult fr = _J2(MAP_PROC,_find_from_entry)(h, e); + if (fr.entry_index >= 0) { + _J2(MAP_PROC,_erase)(h, fr); + } +} + +void _J2(MAP_PROC,multi_remove_all)(MAP_NAME *h, HashKey key) { + while (_J2(MAP_PROC,get)(h, key) != NULL) { + _J2(MAP_PROC,remove)(h, key); + } +} +#endif + + +#undef _J2 +#undef MAP_TYPE +#undef MAP_PROC +#undef MAP_NAME +#undef MAP_ENTRY -- cgit v1.2.3