#include <stdio.h>  /* printf */
#include <stdlib.h> /* malloc, free */
#include <string.h> /* strcmp */

/* type abbreviations for callbacks */
typedef unsigned (hashfunc_t) (const void*);
typedef int (comparefunc_t) (const void*, const void*);

/* entries in our hash table are key-value pairs,
 * just like in any other map
 */
typedef struct entry_t entry_t;

struct entry_t {
    const void *key;
    const void *value;
    entry_t    *next;
};

typedef struct {
    hashfunc_t *hash;       /* callback to get the hash value of a key */
    comparefunc_t *compare; /* callback to compare two keys */
    unsigned count;         /* number of entries */
    unsigned numbuckets;    /* size of our table */
    entry_t **buckets;      /* the actual table */
} hashtable_t;

hashtable_t* ht_create(hashfunc_t *hash, comparefunc_t *compare) {

    /* allocate container */
    hashtable_t *this = malloc(sizeof(hashtable_t));

    /* init all members */
    this->hash       = hash;
    this->compare    = compare;
    this->count      = 0;
    this->numbuckets = 2;

    /* allocate table of buckets -- all set to NULL pointer */
    this->buckets = malloc(sizeof(entry_t*) * this->numbuckets);
    memset(this->buckets, 0, sizeof(entry_t*) * this->numbuckets);

    return this;
}

void ht_destroy(hashtable_t *this) {

    /* first delete all entries */
    for (unsigned bid = 0; bid < this->numbuckets; bid++) {
        /* skip empty buckets */
        if (!this->buckets[bid]) continue;

        /* walk though bucket and delete entries */
        entry_t *entry = this->buckets[bid];
        while (entry) {
            entry_t *tmp = entry->next;
            free(entry);
            entry = tmp;
        }
    }

    /* then delete the table and the surrounding container */
    free(this->buckets);
    free(this);
}

const void* ht_get(hashtable_t *this, const void *key) {

    /* get the bucket id */
    unsigned khash = this->hash(key);
    unsigned bid   = khash % this->numbuckets;

    /* then search in bucket */
    entry_t *entry = this->buckets[bid];
    while (entry) {
        int cmpvalue = this->compare(entry->key, key);
        if (cmpvalue == 0) return entry->value; /* found it */
        entry = entry->next;
    }

    /* nothing found */
    return NULL;
}

void ht_put(hashtable_t *this, const void *key, const void *value) {

    /* get the bucket id */
    unsigned khash = this->hash(key);
    unsigned bid   = khash % this->numbuckets;

    /* then search in bucket */
    entry_t *entry = this->buckets[bid];
    while (entry) {
        int cmpvalue = this->compare(entry->key, key);
        if (cmpvalue == 0) {
            /* key is already there, just override value */
            entry->value = value;
            return;
        }
        entry = entry->next;
    }

    /* nothing found, so make new entry */
    entry_t *newentry = malloc(sizeof(entry_t));
    newentry->key   = key;
    newentry->value = value;
    newentry->next  = this->buckets[bid];

    this->buckets[bid] = newentry;
    this->count++;

    /* if our buckets are getting two full, make more buckets and redistribute */
    float fill = (float) this->count / (float) this->numbuckets;
    if (fill > 2.0f) {
        /* save old values */
        unsigned numbuckets = this->numbuckets;
        entry_t **buckets   = this->buckets;

        /* override with new ones */
        this->numbuckets *= 2;
        this->buckets = malloc(sizeof(entry_t*) * this->numbuckets);
        memset(this->buckets, 0, sizeof(entry_t*) * this->numbuckets);

        /* redistribute the old entries into the new table */
        for (unsigned obid = 0; obid < numbuckets; obid++) {
            /* skip empty buckets */
            if (!buckets[obid]) continue;

            /* walk through entries and redistribute each */
            entry_t *entry = buckets[obid];
            while (entry) {
                entry_t *tmp = entry->next;

                /* rehash */
                unsigned khash = this->hash(entry->key);
                unsigned bid   = khash % this->numbuckets;

                /* and insert into new bucket */
                entry->next = this->buckets[bid];
                this->buckets[bid] = entry;

                entry = tmp;
            }
        }
        free(buckets);
    }
}

/* a simple hash function that maps strings to a number
 * multiple strings can map to the same number, they will go into the same bucket
 */
unsigned strhash(const char *str) {
    unsigned h = 0;
    while (*str) h+= *(str++);
    return h;
}

int main() {
    hashtable_t *mytable = ht_create((hashfunc_t*)strhash, (comparefunc_t*)strcmp);

    printf("===========================\n");
    printf("  test put and get: \n");
    printf("===========================\n");

    ht_put(mytable, "one",   "1");
    ht_put(mytable, "two",   "2");
    ht_put(mytable, "three", "3");
    ht_put(mytable, "four",  "4");
    ht_put(mytable, "five",  "5");

    const char *keys[] = { "zero", "one", "two", "three", "four", "five", "six", NULL};

    for (int i = 0; keys[i]; i++) {
        const char *key   = keys[i];
        const char *value = ht_get(mytable, key);
        printf("[%5s] -> %s\n", key, value ? value : "[not found]");
    }

    printf("===========================\n");
    printf("  print buckets: \n");
    printf("===========================\n");

    for (unsigned bid = 0; bid < mytable->numbuckets; bid++) {
        printf("%2i: ", bid);
        if (mytable->buckets[bid]) {
            entry_t *entry = mytable->buckets[bid];
            while (entry) {
                printf("[%s, %s]; ", (const char*)entry->key, (const char*)entry->value);
                entry = entry->next;
            }
        }
        else {
            printf("EMPTY");
        }
        printf("\n");
    }

    ht_destroy(mytable);
    return 0;
}