#include "hash.h"

#include <stdlib.h>

#include <string.h>

#define HOEDOWN_HASH_ITEM_SIZE 255

#define HOEDOWN_HASH_FNV_PRIME 0x01000193

#define HOEDOWN_HASH_FNV_OFFSET_BASIS 0x811c9dc5

static char *

hoedown_hash_strndup(const char* str, size_t n)

{

    if (str) {

        char *s = (char *)malloc(sizeof(char) * (n + 1));

        if (s) {

            memcpy(s, str, n);

            s[n] = '\0';

        }

        return s;

    }

    return NULL;

}

static char *

hoedown_hash_strdup(const char* str)

{

    if (str) {

        return hoedown_hash_strndup(str, strlen(str));

    }

    return NULL;

}

static unsigned int

hoedown_hash_fnv(const char *key, const char *max, size_t limit)

{

    unsigned int hash = HOEDOWN_HASH_FNV_OFFSET_BASIS;

    if (max == NULL) {

        if (key) {

            max = key + strlen(key);

        } else {

            max = key;

        }

    }

    while (key < max) {

        hash *= HOEDOWN_HASH_FNV_PRIME;

        hash ^= *key;

        key++;

    }

    hash %= limit;

    return hash;

}

static hoedown_hash_item *

hoedown_hash_item_new(void)

{

    hoedown_hash_item *item;

    item = (hoedown_hash_item *)malloc(sizeof(hoedown_hash_item));

    if (!item) {

        return NULL;

    }

    item->key = NULL;

    item->value = NULL;

    item->destruct = NULL;

    item->next = NULL;

    item->tail = NULL;

    return item;

}

static void

hoedown_hash_item_free(hoedown_hash_item *item)

{

    if (item) {

        if (item->next) {

            hoedown_hash_item_free(item->next);

        }

        if (item->key) {

            free(item->key);

        }

        if (item->destruct) {

            (item->destruct)(item->value);

        }

        free(item);

    }

}

static int

hoedown_hash_item_push(hoedown_hash_item *item, const char *key, size_t key_len,

                       void *value, hoedown_hash_value_destruct *destruct)

{

    hoedown_hash_item *entry;

    if (!item || !key || !value) {

        return 1;

    }

    if (item->key != NULL) {

        entry = hoedown_hash_item_new();

        if (!entry) {

            return 1;

        }

    } else {

        entry = item;

    }

    if (key_len > 0) {

        entry->key = hoedown_hash_strndup(key, key_len);

    } else {

        entry->key = hoedown_hash_strdup(key);

    }

    entry->value = value;

    entry->destruct = destruct;

    if (item->tail) {

        item->tail->next = entry;

    } else if (item != entry) {

        item->next = entry;

    }

    item->tail = entry;

    return 0;

}

hoedown_hash *

hoedown_hash_new(size_t size)

{

    hoedown_hash *hash;

    size_t items_size;

    hash = (hoedown_hash *)malloc(sizeof(hoedown_hash));

    if (!hash) {

        return NULL;

    }

    if (size == 0) {

        size = HOEDOWN_HASH_ITEM_SIZE;

    }

    items_size = sizeof(hoedown_hash_item *) * size;

    hash->items = (hoedown_hash_item **)malloc(items_size);

    if (!hash->items) {

        free(hash);

        return NULL;

    }

    memset(hash->items, 0, items_size);

    hash->asize = size;

    return hash;

}

void

hoedown_hash_free(hoedown_hash *hash)

{

    if (hash) {

        if (hash->items) {

            size_t i = 0;

            while (i < hash->asize) {

                if (hash->items[i]) {

                    hoedown_hash_item_free(hash->items[i]);

                }

                ++i;

            }

            free(hash->items);

        }

        free(hash);

    }

}

int

hoedown_hash_add(hoedown_hash *hash, const char *key, size_t key_len,

                 void *value, hoedown_hash_value_destruct *destruct)

{

    unsigned int h;

    if (!hash || !key || !value) {

        return 1;

    }

    h = hoedown_hash_fnv(key, key + key_len, hash->asize);

    if (!hash->items[h]) {

        hash->items[h] = hoedown_hash_item_new();

        if (!hash->items[h]) {

            return 1;

        }

    }

    if (hoedown_hash_item_push(hash->items[h], key, key_len,

                               value, destruct) != 0) {

        return 1;

    }

    return 0;

}

void *

hoedown_hash_find(hoedown_hash *hash, char *key, size_t key_len)

{

    unsigned int h;

    if (!hash || !key) {

        return NULL;

    }

    h = hoedown_hash_fnv(key, key + key_len, hash->asize);

    if (hash->items[h]) {

        hoedown_hash_item *item = hash->items[h];

        while (item != NULL) {

            if (item->key && strncmp(item->key, key, key_len) == 0) {

                return item->value;

            }

            item = item->next;

        }

    }

    return NULL;

}