/**
 * A very simple dynamically-resized HashTable implementation in C.
 */

#include <assert.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>

#define GROWTH_FACTOR 3
#define INITIAL_BUCKET_AMOUNT 50
#define LOAD_FACTOR_THRESHOLD 0.75

typedef int (*ComparisonFunction)(const void *, const void *);
typedef uint64_t Hash;

struct BucketNode {
    const void *key;
    void *value;

    Hash key_hash;

    struct BucketNode *previous;
};

struct HashTable {
    // public
    size_t entries;

    // private
    size_t bucket_amount;
    struct BucketNode **buckets;
    ComparisonFunction cmp_func;
};

struct HashTable *hashtable_new(ComparisonFunction cmp_func) {
    struct HashTable *ht = malloc(sizeof *ht);
    ht->entries = 0;
    ht->bucket_amount = INITIAL_BUCKET_AMOUNT;
    ht->buckets = calloc(ht->bucket_amount, sizeof(struct BucketNode *));
    ht->cmp_func = cmp_func;
    return ht;
}

static int should_grow(struct HashTable *ht) {
    double load_factor = ((double)(ht->entries)) / ((double)(ht->bucket_amount));
    return load_factor >= LOAD_FACTOR_THRESHOLD;
}

static void prune(struct HashTable *ht) {
    (void)(ht);
    // TODO: Remove all useless entries in the hash-table.
}

static void grow(struct HashTable *ht) {
    // XXX: This is a very dumb growing algorithm.
    prune(ht);
    size_t new_bucket_amount = ht->bucket_amount * GROWTH_FACTOR;
    struct BucketNode **new_buckets =
        calloc(new_bucket_amount, sizeof(struct BucketNode *));

    for (size_t old_index = 0; old_index < ht->bucket_amount; ++old_index) {
        struct BucketNode *bucket = ht->buckets[old_index];
        if (!bucket)
            continue;

        size_t new_index = bucket->key_hash % new_bucket_amount;

        struct BucketNode *previous;
        while (bucket) {
            previous = bucket->previous;
            bucket->previous = new_buckets[new_index];
            new_buckets[new_index] = bucket;
            bucket = previous;
        }
    }

    ht->bucket_amount = new_bucket_amount;
    ht->buckets = new_buckets;
}

void hashtable_set(struct HashTable *ht, const void *key, Hash key_hash,
        void *value) {
    if (should_grow(ht)) {
        grow(ht);
    }

    size_t bucket_index = key_hash % ht->bucket_amount;
    struct BucketNode *previous_bucket = ht->buckets[bucket_index];
    struct BucketNode *bucket = malloc(sizeof *bucket);
    assert(bucket != NULL);

    bucket->key = key;
    bucket->value = value;

    bucket->key_hash = key_hash;
    bucket->previous = previous_bucket;

    ht->buckets[bucket_index] = bucket;
    ht->entries += 1;
}

void *hashtable_get(struct HashTable *ht, const void *key, Hash key_hash) {
    size_t bucket_index = key_hash % ht->bucket_amount;
    struct BucketNode *bucket = ht->buckets[bucket_index];

    while (bucket != NULL) {
        if (ht->cmp_func(key, bucket->key)) {
            return bucket->value;
        }

        bucket = bucket->previous;
    }

    return NULL;
}

void hashtable_free(struct HashTable *ht) {
    for (size_t i = 0; i < ht->bucket_amount; ++i) {
        struct BucketNode *bucket = ht->buckets[i];
        while (bucket) {
            struct BucketNode *previous = bucket->previous;
            free(bucket);
            bucket = previous;
        }
    }

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

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

int main(void) {
    struct HashTable *ht = hashtable_new(int_cmp_func);

    for (int i = 0; i < 100; ++i) {
        int *key = malloc(sizeof *key);
        int *value = malloc(sizeof *value);

        *key = 0xDEAD + i;
        *value = 0xBEEF + i;
        Hash key_hash = *key;

        hashtable_set(ht, key, key_hash, value);
    }

    for (int i = 0; i < 100; ++i) {
        int *key = malloc(sizeof *key);
        *key = 0xDEAD + i;
        Hash key_hash = *key;
        void *retrieved_value = hashtable_get(ht, key, key_hash);
        assert(retrieved_value != NULL);
        assert(*((int *)retrieved_value) == (0xBEEF + i));
    }

    hashtable_free(ht);
    puts("Everything is ok.");

    // NB: We leak the keys and values.
}