#include "hashmap.h"

#include <inttypes.h>
#include <string.h>
#include <stdlib.h>
#include <err.h>

#if SIZE_MAX == 0xFFFFFFFF
/* If size_t is 32bit */
static const size_t fnv_prime = 16777619u;
static const size_t fnv_offsetb = 2166136261u;
#elif SIZE_MAX == 0xFFFFFFFFFFFFFFFF
/* If size_t is 64bit */
static const size_t fnv_prime = 1099511628211u;
static const size_t fnv_offsetb = 14695981039346656037u;
#else
/* If size_t is 128bit. Maybe this is overdoing it? */
static const size_t fnv_prime = 309485009821345068724781371u;
static const size_t fnv_offsetb = 144066263297769815596495629667062367629u;
#endif

struct node {
    const char *key;
    void *value;
    struct node *next;
};

/* FNV1a */
static size_t
hash(const char *str)
{
	size_t hash = fnv_offsetb;
	size_t i = 0;
	while (str[i] != '\0') {
		hash ^= str[i];
		hash *= fnv_prime;
		i++;
	}

	return hash;
}

static void
htable_realloc(struct hashmap *hm, struct node **oldbucks, size_t oldcap)
{
	for (size_t i = 0; i < oldcap; i++) {
		struct node *node = oldbucks[i];
		while (node) {
			size_t pos = hash(node->key) % hm->cur_cap;
			if (hm->buckets[pos]) {
				struct node *newnext = hm->buckets[pos],
							*newprev;
				do {
					newprev = newnext;
					newnext = newprev->next;
				} while (newnext);
				newprev->next = node;
			} else {
				hm->buckets[pos] = node;
			}
			struct node *prev = node;
			node = prev->next;
			prev->next = NULL;
		}
	}
	free(oldbucks);
}

static bool
htable_grow(struct hashmap *hm)
{
	float load = (float)hm->size / (float)hm->cur_cap;
	if (load <= HASHMAP_MAX_LOAD) return true;

	size_t oldcap = hm->cur_cap;
	hm->cur_cap = hm->cur_cap * HASHMAP_GROW_RATE;
	struct node **oldbucks = hm->buckets;
	hm->buckets = calloc(hm->cur_cap, sizeof(**hm->buckets));
	if (!hm->buckets) return false;

	htable_realloc(hm, oldbucks, oldcap);

	return true;
}

static bool
htable_shrink(struct hashmap *hm)
{
	if (hm->cur_cap <= hm->init_cap) return true;

	float load = (float)hm->size / (float)hm->cur_cap;
	if (load >= HASHMAP_MIN_LOAD) return true;

	size_t oldcap = hm->cur_cap;
	hm->cur_cap = hm->cur_cap / HASHMAP_GROW_RATE;
	struct node **oldbucks = hm->buckets;
	hm->buckets = calloc(hm->cur_cap, sizeof(**hm->buckets));
	if (!hm->buckets) return false;
	htable_realloc(hm, oldbucks, oldcap);
	return true;
}

struct hashmap *
hashmap_new_with_cap(size_t cap)
{
	struct hashmap *hm = malloc(sizeof *hm);
	hm->init_cap = cap;
	hm->cur_cap = cap;
	hm->size = 0;
	if (hm == NULL) return NULL;
	hm->buckets = calloc(cap, sizeof hm->buckets);
	if (hm->buckets == NULL) {
		free(hm);
		return NULL;
	}

	return hm;
}

void *
hashmap_insert(struct hashmap *hm, const char *key, void *value)
{
    int pos = hash(key) % hm->cur_cap;
    struct node *head = hm->buckets[pos];
    struct node *node = head;
    void *old_value;

    while (node) {
        if (strcmp(node->key, key) == 0) {
            old_value = node->value;
            node->value = value;
            return old_value;
        }
        node = node->next;
    }
    
    node = malloc(sizeof *node);
    node->key = key;
    node->value = value;
    node->next = head;
    hm->buckets[pos] = node;
    hm->size++;
    htable_grow(hm);
    return NULL;
}

void *
hashmap_get(struct hashmap *hm, const char *key)
{
    size_t pos = hash(key) % hm->cur_cap;
    struct node *node = hm->buckets[pos];
    while (node != NULL) {
        if (strcmp(node->key, key) == 0) {
            return node->value;
        }

        node = node->next;
    }

    return NULL;
}

void *
hashmap_resolve(struct hashmap *hm, const char *key)
{
    char tmp_key[64];
    int i = 0;
    int j = 0;

    while (1) {
        for (j=0; key[i] != '.' && key[i] != '\0'; i++, j++) {
            tmp_key[j] = key[i];
        }
        tmp_key[j] = '\0';
        hm = hashmap_get(hm, tmp_key);
        
        // stop if we read key to end of string
        if (key[i] == '\0') {
            break;
        }

        // otherwise, continue reading keys
        i++;
    }

    return hm;
}

void *
hashmap_remove(struct hashmap *hm, const char *key)
{
    int pos = hash(key) % hm->cur_cap;
    struct node *node = hm->buckets[pos];
    struct node *prev = NULL;
    void *old_value;

    while (node) {
        if (strcmp(node->key, key) == 0) {
            if (prev) {
                prev->next = node->next;
            } else {
                hm->buckets[pos] = node->next;
            }
            old_value = node->value;
            free(node);            
    		hm->size--;
    		htable_shrink(hm);
            return old_value;
        }

        prev = node;
        node = node->next;
    }

    return NULL;
}

#define HASHMAP_WALK(hm, ...) \
	struct node *node; \
	struct node *next; \
	for (size_t i = 0; i < hm->cur_cap; i++) { \
		node = hm->buckets[i]; \
		while (node) { \
			next = node->next; \
			__VA_ARGS__; \
			node = next; \
		} \
	}

void
hashmap_walk(struct hashmap *hm, hashmap_cb cb)
{
	HASHMAP_WALK(hm, cb(node->key, node->value));
}

void
hashmap_destroy(struct hashmap *hm, hashmap_cb cb)
{
	HASHMAP_WALK(hm, cb(node->key, node->value), free(node));

	free(hm->buckets);
	free(hm);
}

void
hashmap_free(struct hashmap *hm)
{
	HASHMAP_WALK(hm, free(node));

	free(hm->buckets);
	free(hm);
}