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

typedef struct linked_list_node
{
    int key;
    int value;
    struct linked_list_node *next;
} linked_list_node_t;

typedef struct hash_table
{
    linked_list_node_t **heads;
    size_t capacity;
    unsigned int (*hash_func)(int);
} hash_table_t;

//
// hashtable
//

void
ht_init (
    hash_table_t * const ht,
    unsigned int (*hash_func)(int),
    size_t capacity
)
{
    ht->heads = malloc(capacity * sizeof(linked_list_node_t *));
    ht->capacity = capacity;
    ht->hash_func = hash_func;

    for (size_t i = 0; i < capacity; ++i)
    {
        ht->heads[i] = NULL;
    }
}

int ht_contains_key(
    hash_table_t *ht,
    int key,
    int *out_value,
    int *out_index
)
{
    const int hash = ht->hash_func(key);
    const int index = hash % ht->capacity;

    if (ht->heads[index] == NULL)
    {
        return 0;
    }

    linked_list_node_t *head = ht->heads[index];

    while (head != NULL)
    {
        if (head->key == key)
        {
            if (out_value != NULL)
            {
                *out_value = head->value;
            }

            if (out_index != NULL)
            {
                *out_index = index;
            }

            return 1;
        }

        head = head->next;
    }

    return 0;
}

void
ht_add (
    hash_table_t *ht,
    int key,
    int value
)
{
    int index;

    if (ht_contains_key(ht, key, NULL, &index))
    {
        ht->heads[index]->value = value;
        return;
    }

    const int hash = ht->hash_func(key);
    index = hash % ht->capacity;

    linked_list_node_t *new_node = malloc(sizeof(linked_list_node_t));
    new_node->key = key;
    new_node->value = value;

    if (ht->heads[index] == NULL)
    {
        new_node->next = NULL;
    }
    else
    {
        linked_list_node_t *head = ht->heads[index];
        new_node->next = ht->heads[index];
    }

    ht->heads[index] = new_node;
}

unsigned int
hash_function (
    int key
)
{
    key = ((key >> 16) ^ key) * 0x45d9f3b;
    key = ((key >> 16) ^ key) * 0x45d9f3b;
    key = (key >> 16) ^ key;
    return key;
}

int main()
{
    hash_table_t ht;

    ht_init(&ht, &hash_function, 128);

    ht_add(&ht, 10, 1);
    ht_add(&ht, 10, 2);
    ht_add(&ht, 10, 3);
    ht_add(&ht, 20, 2);
    ht_add(&ht, 30, 3);
    ht_add(&ht, 40, 4);
    ht_add(&ht, 50, 5);
    ht_add(&ht, 60, 6);
    ht_add(&ht, 70, 7);
    ht_add(&ht, 80, 8);
    ht_add(&ht, 90, 9);
    ht_add(&ht, 100, 10);

    for (int key = 0; key < 200; ++key)
    {
        int value;
        int index;

        if (ht_contains_key(&ht, key, &value, &index))
        {
            printf("[contains] key: %d, value: %d, at index: %d\n", key, value, index);
        }
    }

    return 0;
}