path: root/HashTable.c

#include "HashTable.h"
#include "Types.h"
#include <stdio.h>
#include <string.h>

/** Hashing function **/

// Fowler/Noll/Vo 32-bit hash implementation
// http://www.isthe.com/chongo/tech/comp/fnv/index.html
// https://en.wikipedia.org/wiki/Fowler%E2%80%93Noll%E2%80%93Vo_hash_function#FNV-1_hash

#define FNV_OFFSET_BASIS 2166136261
#define FNV_PRIME        16777619
typedef u32 fnv_int;

static fnv_int fnv1_hash(const char* str) {
    fnv_int hash = FNV_OFFSET_BASIS;
    while (*str != '\0') {
        hash *= FNV_PRIME;
        hash ^= *(str++);
    }
    return hash;
}

/** Metadata **/

struct HashTableMeta {
    MemoryManager *mm;
    usize size;
    usize count;
};

static inline struct HashTableMeta*
H_metadata(HashTable ht) {
    return ht - sizeof(struct HashTableMeta);
}

/** Helpers **/

static inline const char**
H_keys(HashTable ht) {
    return ht;
}

static inline void**
H_vals(HashTable ht) {
    return ht + H_metadata(ht)->size * sizeof(const char*);
}

static inline Result
H_find_hash(HashTable ht, const char *key, fnv_int *hash) {
    if (NULL == ht || NULL == key)
        return R_NullArgument;

    struct HashTableMeta *htm = H_metadata(ht);

    *hash = fnv1_hash(key) % htm->size;
    fnv_int hash_orig = *hash;

    do {
        if (H_keys(ht)[*hash] == NULL)
            return R_NotFound;

        if (0 == strcmp(H_keys(ht)[*hash], key))
            return R_Ok;

        *hash = (*hash + 1) % htm->size;
    } while (*hash != hash_orig);

    return R_NotFound;
}

/* Create */

HashTable
H_new(MemoryManager *mm, usize size) {
    if (NULL == mm)
        return NULL;

    struct HashTableMeta htm = {
        .mm = mm,
        .size = size,
        .count = 0,
    };

    void* start = NULL;
    if (R_Ok != mm->alloc(*mm, &start, sizeof(htm) + size * sizeof(const char*) + size * sizeof(void*)) ||
        NULL == start)
    {
        return NULL;
    }

    memcpy(start, &htm, sizeof(htm));
    start += sizeof(htm);
    memset(start, 0, size * sizeof(const char*) + size * sizeof(void*));

    return start;
}

/* Free */

Result
H_free(HashTable* ht) {
    if (NULL == ht || NULL == *ht)
        return R_NullArgument;

    struct HashTableMeta *htm = H_metadata(*ht);

    for (usize i = 0; i < htm->size; ++i) {
        if (NULL != H_keys(*ht)[i])
            RETURN_NOTOK(htm->mm->free(*htm->mm, (void**)(H_keys(*ht) + i)));
    }

    *ht = htm;
    return htm->mm->free(*htm->mm, ht);
}

Result
H_freeat(HashTable ht, const char* key) {
    if (NULL == ht || NULL == key)
        return R_NullArgument;

    fnv_int hash = 0;
    RETURN_NOTOK(H_find_hash(ht, key, &hash));

    struct HashTableMeta *htm = H_metadata(ht);

    RETURN_NOTOK(htm->mm->free(*htm->mm, H_vals(ht) + hash));
    RETURN_NOTOK(htm->mm->free(*htm->mm, (void**)(H_keys(ht) + hash)));
    --htm->count;

    return R_Ok;
}

Result
H_freevals(HashTable* ht) {
    if (NULL == ht || NULL == *ht)
        return R_NullArgument;

    struct HashTableMeta *htm = H_metadata(*ht);

    for (usize i = 0; i < htm->size; ++i) {
        htm->mm->free(*htm->mm, (void**)(H_vals(*ht) + i));
    }

    return R_Ok;
}

/* Modify */

Result
H_insert(HashTable ht, const char *key, void *value) {
    if (NULL == ht || NULL == key)
        return R_NullArgument;

    struct HashTableMeta *htm = H_metadata(ht);

    if (htm->count >= htm->size)
        return R_OutOfMemory;

    fnv_int hash = fnv1_hash(key) % htm->size;
    while (NULL != H_keys(ht)[hash]) {
        hash = (hash + 1) % htm->size;
    }

    H_keys(ht)[hash] = M_strdup(*htm->mm, key);
    H_vals(ht)[hash] = value;
    ++htm->count;

    return R_Ok;
}

Result
H_insertstr(HashTable ht, const char *key, const char *value) {
    if (NULL == ht || NULL == key)
        return R_NullArgument;

    MemoryManager *mm = H_metadata(ht)->mm;

    char* copy = M_strdup(*mm, value);
    Result r = H_insert(ht, key, copy);

    if (R_Ok != r) {
        mm->free(*mm, (void**)&copy);
    }
    return r;
}

Result
H_inserti(HashTable ht, const char *key, int value) {
    if (NULL == ht || NULL == key)
        return R_NullArgument;

    MemoryManager *mm = H_metadata(ht)->mm;

    int* copy = NULL;
    RETURN_NOTOK(
        mm->alloc(*mm, (void**)&copy, sizeof(int)));
    memcpy(copy, &value, sizeof(int));

    Result r = H_insert(ht, key, copy);

    if (R_Ok != r) {
        mm->free(*mm, (void**)&copy);
    }

    return r;
}

Result
H_insertf(HashTable ht, const char *key, double value) {
    if (NULL == ht || NULL == key)
        return R_NullArgument;

    MemoryManager *mm = H_metadata(ht)->mm;

    float* copy = NULL;
    RETURN_NOTOK(
        mm->alloc(*mm, (void**)&copy, sizeof(double)));
    memcpy(copy, &value, sizeof(double));

    Result r = H_insert(ht, key, copy);

    if (R_Ok != r) {
        mm->free(*mm, (void**)&copy);
    }
    return r;
}

/* Get */

usize
H_size(HashTable ht) {
    if (NULL == ht)
        return 0;
    return H_metadata(ht)->size;
}

usize
H_count(HashTable ht) {
    if (NULL == ht)
        return 0;
    return H_metadata(ht)->count;
}

void*
H_get(HashTable ht, const char* key) {
    if (NULL == ht || NULL == key)
        return NULL;

    struct HashTableMeta *htm = H_metadata(ht);

    fnv_int hash = 0;
    if (R_Ok != H_find_hash(ht, key, &hash))
        return NULL;

    return H_vals(ht)[hash];
}

inline char*
H_getstr(HashTable ht, const char* key) {
    return H_get(ht, key);
}

inline int*
H_geti(HashTable ht, const char* key) {
    return H_get(ht, key);
}

inline double*
H_getf(HashTable ht, const char* key) {
    return H_get(ht, key);
}