ccore/include/core/HashMap.h

#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);                \
    size_t toStringHashMap##N(const HashMap##N* m, char* buffer, size_t n,     \
                              CoreToString keyString,                          \
                              CoreToString 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(coreMaxSize(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];         \
            }                                                                  \
        }                                                                      \
        coreSwap(&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;                                                      \
            }                                                                  \
        }                                                                      \
        coreSwap(&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,     \
                              CoreToString keyString,                          \
                              CoreToString valueString) {                      \
        size_t w = 0;                                                          \
        coreStringAdd(&w, &buffer, &n, coreToString(buffer, n, "["));          \
        bool notFirst = false;                                                 \
        HashMapIterator##N i;                                                  \
        initHashMapIterator##N(&i, m);                                         \
        while(hasNextHashMapNode##N(&i)) {                                     \
            HashMapNode##N* node = nextHashMapNode##N(&i);                     \
            if(notFirst) {                                                     \
                coreStringAdd(&w, &buffer, &n, coreToString(buffer, n, ", ")); \
            }                                                                  \
            notFirst = true;                                                   \
            coreStringAdd(&w, &buffer, &n, keyString(node->key, buffer, n));   \
            coreStringAdd(&w, &buffer, &n, coreToString(buffer, n, " = "));    \
            coreStringAdd(&w, &buffer, &n,                                     \
                          valueString(node->value, buffer, n));                \
        }                                                                      \
        stringAdd(&w, &buffer, &n, coreToString(buffer, n, "]"));              \
        return w;                                                              \
    }

#endif