#ifndef CORE_HASHMAP_H #define CORE_HASHMAP_H #include "core/ToString.h" #include "core/Types.h" #include "core/Utility.h" size_t hashString(const char* key); size_t roundUp2(size_t n); #define isInvalidKeyInt(key) ((key) == 0) #define equalInt(a, b) ((a) == (b)) #define hashInt(key) ((size_t)key) #define isInvalidKeySize(key) ((key) == 0) #define equalSize(a, b) ((a) == (b)) #define hashSize(key) (key) #define HASHMAP(K, V, N) \ typedef struct { \ K* keys; \ V* values; \ size_t capacity; \ size_t entries; \ } HashMap##N; \ \ void initHashMap##N(HashMap##N* m); \ void destroyHashMap##N(HashMap##N* m); \ void rehashHashMap##N(HashMap##N* m, size_t minCapacity); \ V* putHashMapKey##N(HashMap##N* m, K key); \ V* searchHashMapKey##N(const HashMap##N* m, K key); \ void clearHashMap##N(HashMap##N* m); \ bool removeHashMapKey##N(HashMap##N* m, K key); \ \ typedef struct { \ const K* key; \ V* value; \ } HashMapNode##N; \ \ typedef struct { \ K* key; \ K* endKey; \ V* value; \ V* endValue; \ const HashMap##N* map; \ HashMapNode##N node; \ } HashMapIterator##N; \ \ void initHashMapIterator##N(HashMapIterator##N* mi, const HashMap##N* m); \ bool hasNextHashMapNode##N(HashMapIterator##N* mi); \ HashMapNode##N* nextHashMapNode##N(HashMapIterator##N* mi); \ typedef size_t (*ToStringKey##N)(K const* const data, char* buffer, \ size_t n); \ typedef size_t (*ToStringValue##N)(V const* const data, char* buffer, \ size_t n); \ size_t toStringHashMap##N(const HashMap##N* m, char* buffer, size_t n, \ ToStringKey##N keyString, \ ToStringValue##N valueString); #define HASHMAP_SOURCE(K, V, N) \ static size_t searchSlot##N(HashMap##N* m, K key) { \ size_t rehashFactor = 2; \ while(true) { \ rehashHashMap##N(m, m->entries* rehashFactor + 1); \ if(isInvalidKey##N(key)) { \ return m->capacity - 1; \ } \ size_t baseHash = hash##N(key) * 514685581u; \ size_t end = m->capacity - 2; \ /* rehash on bad clustering */ \ for(size_t i = 0; i <= 5; i++) { \ size_t hash = (baseHash + i) & end; \ K keyEntry = m->keys[hash]; \ if(isInvalidKey##N(keyEntry) || equal##N(keyEntry, key)) { \ return hash; \ } \ } \ rehashFactor *= 2; \ } \ } \ \ void initHashMap##N(HashMap##N* m) { \ m->keys = nullptr; \ m->values = nullptr; \ m->capacity = 0; \ m->entries = 0; \ } \ \ void destroyHashMap##N(HashMap##N* m) { \ coreFree(m->keys); \ coreFree(m->values); \ *m = (HashMap##N){0}; \ } \ \ void rehashHashMap##N(HashMap##N* m, size_t minCapacity) { \ if(minCapacity <= m->capacity) { \ return; \ } \ size_t l = roundUp2(maxSize(minCapacity, 8lu)) + 1; \ HashMap##N map; \ initHashMap##N(&map); \ size_t keyBytes = l * sizeof(K); \ map.keys = coreAllocate(keyBytes); \ memset(map.keys, 0, keyBytes); \ memset(map.keys + (l - 1), 1, sizeof(K)); \ map.values = coreAllocate(l * sizeof(V)); \ map.capacity = l; \ \ size_t length = m->capacity; \ if(length > 0) { \ length--; \ for(size_t i = 0; i < length; i++) { \ K keyEntry = m->keys[i]; \ if(!isInvalidKey##N(keyEntry)) { \ *putHashMapKey##N(&map, keyEntry) = m->values[i]; \ } \ } \ K keyEntry = m->keys[length]; \ if(isInvalidKey##N(keyEntry)) { \ *putHashMapKey##N(&map, keyEntry) = m->values[length]; \ } \ } \ swap(&map, m); \ destroyHashMap##N(&map); \ } \ \ V* putHashMapKey##N(HashMap##N* m, K key) { \ size_t index = searchSlot##N(m, key); \ K* keyEntry = m->keys + index; \ if(equal##N(*keyEntry, key)) { \ return m->values + index; \ } \ m->entries++; \ *keyEntry = key; \ return m->values + index; \ } \ \ V* searchHashMapKey##N(const HashMap##N* m, K key) { \ if(m->capacity != 0) { \ if(isInvalidKey##N(key)) { \ size_t i = m->capacity - 1; \ return isInvalidKey##N(m->keys[i]) ? m->values + i : nullptr; \ } \ size_t baseHash = hash##N(key) * 514685581u; \ size_t end = m->capacity - 2; \ for(size_t i = 0; i <= end; i++) { \ size_t hash = (baseHash + i) & end; \ K keyEntry = m->keys[hash]; \ if(equal##N(keyEntry, key)) { \ return m->values + hash; \ } else if(isInvalidKey##N(keyEntry)) { \ return nullptr; \ } \ } \ } \ return nullptr; \ } \ \ void clearHashMap##N(HashMap##N* m) { \ if(m->keys == nullptr) { \ return; \ } \ m->entries = 0; \ memset(m->keys, 0, m->capacity * sizeof(K)); \ memset(m->keys + (m->capacity - 1), 1, sizeof(K)); \ } \ \ bool removeHashMapKey##N(HashMap##N* m, K key) { \ /* ToDo: This is a very slow remove */ \ HashMap##N n; \ initHashMap##N(&n); \ HashMapIterator##N i; \ initHashMapIterator##N(&i, m); \ bool r = false; \ while(hasNextHashMapNode##N(&i)) { \ HashMapNode##N* node = nextHashMapNode##N(&i); \ if(!equal##N(key, *node->key)) { \ *putHashMapKey##N(&n, *node->key) = *node->value; \ } else { \ r = true; \ } \ } \ swap(&n, m); \ destroyHashMap##N(&n); \ return r; \ } \ \ void initHashMapIterator##N(HashMapIterator##N* mi, const HashMap##N* m) { \ mi->key = m->keys; \ mi->endKey = mi->key + m->capacity; \ mi->value = m->values; \ mi->endValue = mi->value + m->capacity; \ mi->map = m; \ } \ \ bool hasNextHashMapNode##N(HashMapIterator##N* mi) { \ while(mi->key != mi->endKey) { \ K* nextKey = mi->key + 1; \ if(isInvalidKey##N(*mi->key) == (nextKey == mi->endKey)) { \ break; \ } \ mi->key = nextKey; \ mi->value++; \ } \ return mi->key != mi->endKey; \ } \ \ HashMapNode##N* nextHashMapNode##N(HashMapIterator##N* mi) { \ mi->node.key = mi->key; \ mi->node.value = mi->value; \ mi->key++; \ mi->value++; \ return &mi->node; \ } \ \ size_t toStringHashMap##N(const HashMap##N* m, char* buffer, size_t n, \ ToStringKey##N keyString, \ ToStringValue##N valueString) { \ size_t w = 0; \ stringAdd(&w, &buffer, &n, toString(buffer, n, "[")); \ bool notFirst = false; \ HashMapIterator##N i; \ initHashMapIterator##N(&i, m); \ while(hasNextHashMapNode##N(&i)) { \ HashMapNode##N* node = nextHashMapNode##N(&i); \ if(notFirst) { \ stringAdd(&w, &buffer, &n, toString(buffer, n, ", ")); \ } \ notFirst = true; \ stringAdd(&w, &buffer, &n, keyString(node->key, buffer, n)); \ stringAdd(&w, &buffer, &n, toString(buffer, n, " = ")); \ stringAdd(&w, &buffer, &n, valueString(node->value, buffer, n)); \ } \ stringAdd(&w, &buffer, &n, toString(buffer, n, "]")); \ return w; \ } #endif