ccore/src/HashMap.c

#include "core/HashMap.h"

#include <stdio.h>
#include <string.h>

#include "core/Utility.h"

static bool isInvalidKey(const CoreHashMap* m, const void* key) {
    const char* c = key;
    for(size_t i = m->keySize; i > 0; i--) {
        if(*(c++) != 0) {
            return false;
        }
    }
    return true;
}

static void* getKey(const CoreHashMap* m, size_t index) {
    return (char*)m->keys + m->keySize * index;
}

static void* getValue(const CoreHashMap* m, size_t index) {
    return (char*)m->values + m->valueSize * index;
}

static size_t searchSlot(CoreHashMap* m, const void* key) {
    size_t rehashFactor = 2;
    while(true) {
        coreRehashHashMap(m, m->entries * rehashFactor + 1);
        if(isInvalidKey(m, key)) {
            return m->capacity - 1;
        }
        size_t baseHash = m->hasher(key, m->keySize) * 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;
            void* keyEntry = getKey(m, hash);
            if(isInvalidKey(m, keyEntry) ||
               m->equal(keyEntry, key, m->keySize)) {
                return hash;
            }
        }
        rehashFactor *= 2;
    }
}

#define SEARCH_VALUE(type, Type)                                               \
    static void* searchValue##Type(const CoreHashMap* m, const void* rawKey) { \
        type key = *(const type*)rawKey;                                       \
        if(m->capacity != 0) {                                                 \
            if(key == 0) {                                                     \
                size_t i = m->capacity - 1;                                    \
                return ((type*)m->keys)[i] == 0 ? getValue(m, i) : nullptr;    \
            }                                                                  \
            size_t baseHash = ((size_t)key) * 514685581u;                      \
            size_t end = m->capacity - 2;                                      \
            for(size_t i = 0; i <= end; i++) {                                 \
                size_t hash = (baseHash + i) & end;                            \
                type keyEntry = *(type*)getKey(m, hash);                       \
                if(keyEntry == key) {                                          \
                    return getValue(m, hash);                                  \
                } else if(keyEntry == 0) {                                     \
                    return nullptr;                                            \
                }                                                              \
            }                                                                  \
        }                                                                      \
        return nullptr;                                                        \
    }
SEARCH_VALUE(u32, U32)
SEARCH_VALUE(u64, U64)

static void* searchValue(const CoreHashMap* m, const void* key) {
    if(m->capacity != 0) {
        if(isInvalidKey(m, key)) {
            size_t i = m->capacity - 1;
            return isInvalidKey(m, getKey(m, i)) ? getValue(m, i) : nullptr;
        }
        size_t baseHash = m->hasher(key, m->keySize) * 514685581u;
        size_t end = m->capacity - 2;
        for(size_t i = 0; i <= end; i++) {
            size_t hash = (baseHash + i) & end;
            void* keyEntry = getKey(m, hash);
            if(m->equal(keyEntry, key, m->keySize)) {
                return getValue(m, hash);
            } else if(isInvalidKey(m, keyEntry)) {
                return nullptr;
            }
        }
    }
    return nullptr;
}

static size_t roundUp2(size_t n) {
    size_t w = 1;
    while(w < n) {
        w *= 2;
    }
    return w;
}

CoreHashMap coreInitHashMap(size_t keySize, size_t valueSize, CoreHasher hasher,
                            CoreEqual equal) {
    CoreSearchValue search = searchValue;
    if(hasher == coreHash && equal == coreEqual) {
        switch(keySize) {
            case sizeof(u32): search = searchValueU32; break;
            case sizeof(u64): search = searchValueU64; break;
        }
    }
    return (CoreHashMap){nullptr, nullptr, keySize, valueSize, 0,
                         0,       hasher,  equal,   search};
}

void coreDestroyHashMap(CoreHashMap* m) {
    coreFree(m->keys);
    coreFree(m->values);
    *m = (CoreHashMap){0};
}

void coreRehashHashMap(CoreHashMap* m, size_t minCapacity) {
    if(minCapacity <= m->capacity) {
        return;
    }
    size_t l = roundUp2(coreMaxSize(minCapacity, 8lu)) + 1;
    CoreHashMap map =
        CORE_HASH_MAP(m->keySize, m->valueSize, m->hasher, m->equal);
    size_t keyBytes = l * m->keySize;
    map.keys = coreAllocate(keyBytes);
    memset(map.keys, 0, keyBytes);
    memset(getKey(&map, l - 1), 1, m->keySize);
    map.values = coreAllocate(l * m->valueSize);
    map.capacity = l;

    size_t length = m->capacity;
    if(length > 0) {
        length--;
        for(size_t i = 0; i < length; i++) {
            void* keyEntry = getKey(m, i);
            if(!isInvalidKey(m, keyEntry)) {
                coreHashMapPutPointer(&map, keyEntry, getValue(m, i));
            }
        }
        void* keyEntry = getKey(m, length);
        if(isInvalidKey(m, keyEntry)) {
            coreHashMapPutPointer(&map, keyEntry, getValue(m, length));
        }
    }
    coreSwapHashMap(&map, m);
    coreDestroyHashMap(&map);
}

void* coreHashMapPutPointer(CoreHashMap* m, const void* key,
                            const void* value) {
    size_t index = searchSlot(m, key);
    void* keyEntry = getKey(m, index);
    if(m->equal(keyEntry, key, m->keySize)) {
        void* v = getValue(m, index);
        memcpy(v, value, m->valueSize);
        return v;
    }
    void* v = getValue(m, index);
    memcpy(v, value, m->valueSize);
    m->entries++;
    memcpy(keyEntry, key, m->keySize);
    return v;
}

void* coreHashMapSearchPointer(CoreHashMap* m, const void* key) {
    return m->search(m, key);
}

const void* coreHashMapSearchPointerC(const CoreHashMap* m, const void* key) {
    return m->search(m, key);
}

bool coreHashMapContainsPointer(const CoreHashMap* m, const void* key) {
    return coreHashMapSearchPointerC(m, key) != nullptr;
}

void coreClearHashMap(CoreHashMap* m) {
    if(m->keys == nullptr) {
        return;
    }
    m->entries = 0;
    memset(m->keys, 0, m->capacity * m->keySize);
    memset(getKey(m, m->capacity - 1), 1, m->keySize);
}

bool coreHashMapRemovePointer(CoreHashMap* m, const void* key) {
    // ToDo: This is a very slow remove
    CoreHashMap n =
        CORE_HASH_MAP(m->keySize, m->valueSize, m->hasher, m->equal);
    CoreHashMapIterator i = CORE_HASH_MAP_ITERATOR(m);
    bool r = false;
    while(true) {
        CoreHashMapNode* node = coreHashMapNext(&i);
        if(node == nullptr) {
            break;
        }
        if(!m->equal(key, node->key, n.keySize)) {
            coreHashMapPutPointer(&n, node->key, node->value);
        } else {
            r = true;
        }
    }
    coreSwapHashMap(&n, m);
    coreDestroyHashMap(&n);
    return r;
}

size_t coreToStringHashMap(const CoreHashMap* m, char* buffer, size_t n,
                           CoreToString keyString, CoreToString valueString) {
    size_t w = 0;
    coreStringAddI(&w, &buffer, &n, snprintf(buffer, n, "["));
    char* end = getKey(m, m->capacity);
    char* key = m->keys;
    char* value = m->values;
    bool notFirst = false;
    while(key != end) {
        if(isInvalidKey(m, key) == (key + m->keySize == end)) {
            if(notFirst) {
                coreStringAddI(&w, &buffer, &n, snprintf(buffer, n, ", "));
            }
            notFirst = true;
            coreStringAdd(&w, &buffer, &n, keyString(key, buffer, n));
            coreStringAddI(&w, &buffer, &n, snprintf(buffer, n, " = "));
            coreStringAdd(&w, &buffer, &n, valueString(value, buffer, n));
        }
        key += m->keySize;
        value += m->valueSize;
    }
    coreStringAddI(&w, &buffer, &n, snprintf(buffer, n, "]"));
    return w;
}

void coreSwapHashMap(CoreHashMap* a, CoreHashMap* b) {
    CoreHashMap tmp = *a;
    *a = *b;
    *b = tmp;
}

size_t coreHashString(const void* key, size_t n) {
    if(n != sizeof(char*)) {
        return 0;
    }
    const char* s = *(const char* const*)key;
    size_t h = 0;
    while(*s != '\0') {
        h = 2120251889lu * h + (size_t)(*(s++));
    }
    return h;
}

size_t coreHash(const void* key, size_t n) {
    size_t h = 0;
    if(n <= sizeof(size_t)) {
        memcpy(&h, key, n);
        return h;
    }
    const char* cKey = key;
    while(n > 0) {
        size_t m = 0;
        if(n >= sizeof(size_t)) {
            memcpy(&m, cKey, sizeof(size_t));
            cKey += sizeof(size_t);
            n -= sizeof(size_t);
        } else {
            memcpy(&m, cKey, n);
            cKey += n;
            n = 0;
        }
        h ^= m;
    }
    return h;
}

bool coreEqual(const void* keyA, const void* keyB, size_t n) {
    return memcmp(keyA, keyB, n) == 0;
}

CoreHashMapNode* coreHashMapNext(CoreHashMapIterator* mi) {
    const CoreHashMap* m = mi->map;
    mi->index++;
    size_t end = m->capacity - 1;
    while(mi->index < m->capacity) {
        void* key = getKey(m, mi->index);
        if(isInvalidKey(m, key) == (mi->index == end)) {
            mi->node.key = key;
            mi->node.value = getValue(m, mi->index);
            return &mi->node;
        }
        mi->index++;
    }
    return nullptr;
}