cube-game-plus-plus/common/utils/HashMap.h

#ifndef HASHMAP_H
#define HASHMAP_H

#include "common/utils/Types.h"

template<typename K, typename V, uint L>
class HashMap final {
public:

    HashMap(K emptyKey, V emptyValue) : entries(0), emptyKey(emptyKey), emptyValue(emptyValue) {
        for(uint i = 0; i < LENGTH; i++) {
            data[i].key = emptyKey;
            data[i].value = emptyValue;
        }
    }

    static constexpr uint getCapacity() {
        return LENGTH;
    }

    void add(const K key, const V value) {
        if(entries >= L) {
            return;
        }
        uint hash = hashCode(key) % LENGTH;
        while(true) {
            if(data[hash].key == key) {
                data[hash].value = value;
                return;
            } else if(data[hash].key == emptyKey) {
                data[hash].key = key;
                data[hash].value = value;
                entries++;
                return;
            }
            hash = (hash + 1) % LENGTH;
        }
    }

    V search(const K key) const {
        uint hash = hashCode(key) % LENGTH;
        while(true) {
            if(data[hash].key == key) {
                return data[hash].value;
            } else if(data[hash].key == emptyKey) {
                return emptyValue;
            }
            hash = (hash + 1) % LENGTH;
        }
    }

    void forEach(void (*f)(const K&, V&)) {
        for(uint i = 0; i < LENGTH; i++) {
            if(data[i].key != emptyKey) {
                f(data[i].key, data[i].value);
            }
        }
    }

private:

    static constexpr uint getLength() {
        constexpr uint SIZE_TABLE[] = {
            2, 3, 7, 11, 23, 43, 89, 173, 347, 683, 1367, 2731, 5471, 10937, 21851, 43691, 87383, 174763, 349529, 699053,
            1398107, 2796203, 5592407, 11184829, 22369661, 44739259, 89478503, 178956983, 357913951, 715827883, 1431655777,
            2863311551
        };
        uint i = 0;
        while(SIZE_TABLE[i] < L) {
            i++;
        }
        return SIZE_TABLE[i];
    }

    template<typename H>
    uint hashCode(const H& h) const {
        return h.hashCode();
    }

    uint hashCode(const uint& h) const {
        return h;
    }

    static constexpr uint LENGTH = getLength();

    uint entries;
    K emptyKey;
    V emptyValue;

    struct KeyValuePair {
        K key;
        V value;
    };
    KeyValuePair data[LENGTH];
};

#endif