C Map/ArrayMap (O(n))

//
// Created by kettl on 28/01/2023.
//

#ifndef REGHZYLIBS_ARRAYMAP_H
#define REGHZYLIBS_ARRAYMAP_H

#define SIZEOF_NODE(count) (sizeof(ArrayMapNode) * (count))
#define AM_ENTRY_REPLACED 0
#define AM_ENTRY_INSERTED 1

typedef int32_t hash_t;

typedef hash_t (* hash_func)(const void*);
typedef int (* comp_func)(const void*, const void*);

typedef struct {
    hash_t hashCode;
    void* m_key;
    void* m_val;
} ArrayMapNode;

typedef struct {
    hash_func m_hash;    // The key hashing function
    comp_func m_comp;    // The key comparison function. Returns non-zero if two keys are equal
    size_t m_tab_cap;    // The current max capacity of this map (m_tab_cap * sizeof(ArrayMapNode) bytes)
    size_t m_tab_len;    // The number of entries in this map
    ArrayMapNode* m_tab; // A pointer to the start of the table
} ArrayMap;

static int def_comp_func(const void* a, const void* b) {
    return a == b;
}

ArrayMap* new_array_map(hash_func hash, comp_func comp) {
    auto* map = (ArrayMap*) malloc(sizeof(ArrayMap));
    memset(map, 0, sizeof(ArrayMap));
    map->m_hash = hash;
    map->m_comp = comp;
    return map;
}

ArrayMap* new_array_map(hash_func hash) {
    return new_array_map(hash, def_comp_func);
}

static int index_for_key(ArrayMap* map, void* key) {
    hash_t hash = map->m_hash(key);
    for(int i = 0; i < map->m_tab_len; i++) {
        ArrayMapNode* node = &map->m_tab[i];
        if (node->hashCode == hash) {
            if (map->m_comp(node->m_key, key)) {
                return i;
            }
        }
    }

    return -1;
}

static void insert_entry(ArrayMap* map, void* key, void* val) {
    if (map->m_tab_cap == 0 || map->m_tab_len >= map->m_tab_cap) {
        size_t new_cap = map->m_tab_cap + (map->m_tab_cap >> 1);
        if (new_cap < 1) {
            new_cap = 1;
        }
        else if (new_cap == map->m_tab_cap) {
            new_cap++;
        }

        auto* table = (ArrayMapNode*) malloc(SIZEOF_NODE(new_cap));
        if (table == nullptr) {
            return; // ??? what to do here
        }

        if (map->m_tab != nullptr) {
            memcpy(table, map->m_tab, SIZEOF_NODE(map->m_tab_cap));
            free(map->m_tab);
        }

        map->m_tab_cap = new_cap;
        map->m_tab = table;
    }

    map->m_tab[map->m_tab_len++] = {map->m_hash(key), key, val};
}


static void remove_at_index(ArrayMap* map, int index) {
    memmove(&map->m_tab[index], &map->m_tab[index + 1], SIZEOF_NODE(map->m_tab_len - index));
    memset(&map->m_tab[map->m_tab_len], 0, sizeof(ArrayMapNode));
    map->m_tab_len--;
}

int arraymap_put(ArrayMap* map, void* key, void* val) {
    int index = index_for_key(map, key);
    if (index == -1) {
        insert_entry(map, key, val);
        return AM_ENTRY_INSERTED;
    }

    ((ArrayMapNode*) &map->m_tab[index])->m_val = val;
    return AM_ENTRY_REPLACED;
}

int arraymap_get_node(ArrayMap* map, void* key, ArrayMapNode** out_node) {
    int index = index_for_key(map, key);
    if (index == -1)
        return 0;
    *out_node = &map->m_tab[index];
    return 1;
}

void* arraymap_get(ArrayMap* map, void* key) {
    ArrayMapNode* node;
    if (arraymap_get_node(map, key, &node))
        return node->m_val;
    return nullptr;
}

int arraymap_try_get(ArrayMap* map, void* key, void** val) {
    ArrayMapNode* node;
    if (!arraymap_get_node(map, key, &node))
        return 0;
    *val = node->m_val;
    return 1;
}

int arraymap_remove(ArrayMap* map, void* key) {
    int index = index_for_key(map, key);
    if (index == -1)
        return 0;
    remove_at_index(map, index);
    return 1;
}

void arraymap_clear(ArrayMap* map) {
    memset(map->m_tab, 0, SIZEOF_NODE(map->m_tab_len));
    map->m_tab_len = 0;
}

#undef SIZEOF_NODE
#endif //REGHZYLIBS_ARRAYMAP_H