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

#include "term.h"

#include "dict.h"

struct chain {
    struct chain *next;
    const struct term *value;
};

struct dict *dict_new(int num_buckets) {
    struct dict *d;
    int i;

    d = malloc(sizeof(struct dict));
    d->num_buckets = num_buckets;
    d->bucket = malloc(sizeof(struct chain *) * d->num_buckets);
    for (i = 0; i < d->num_buckets; i++) {
        d->bucket[i] = NULL;
    }

    return d;
}

/*** UTILITIES ***/

/*
 * Hash function, taken from "Compilers: Principles, Techniques, and Tools"
 * by Aho, Sethi, & Ullman (a.k.a. "The Dragon Book", 2nd edition.)
 */
static size_t hashpjw(const char *key, size_t key_size, size_t table_size) {
    int i;
    unsigned long int h = 0, g;

    for (i = 0; i < key_size; i++) {
        h = (h << 4) + (key[i]);
        if ((g = h & 0xf0000000)) {
            h = (h ^ (g >> 24)) ^ g;
        }
    }

    return h % table_size;
}

/*
 * Create a new chain for a bucket (not called directly by client code.)
 */
static struct chain *
chain_new(const struct term *value)
{
    struct chain *c = malloc(sizeof(struct chain));

    c->next = NULL;
    c->value = value;

    return c;
}

/*
 * Locate the bucket number a particular key would be located in, and the
 * chain link itself if such a key exists (or NULL if it could not be found.)
 */
static void
dict_locate(struct dict *d, const char *key, size_t key_size,
	    size_t *b_index, struct chain **c)
{
    *b_index = hashpjw(key, key_size, d->num_buckets);
    for (*c = d->bucket[*b_index]; *c != NULL; *c = (*c)->next) {
        if ((*c)->value->size == key_size &&
            memcmp(key, (*c)->value->atom, key_size) == 0)
            break;
    }
}

/*** OPERATIONS ***/

const struct term *
dict_fetch(struct dict *d, const char *key, size_t key_size)
{
    struct chain *c;
    size_t i;
    
    dict_locate(d, key, key_size, &i, &c);

    return c != NULL ? c->value : NULL;
}

void
dict_store(struct dict *d, const struct term *t)
{
    struct chain *c;
    size_t i;
    
    dict_locate(d, t->atom, t->size, &i, &c);
    if (c == NULL) {
        /* Chain does not exist, add a new one. */
        c = chain_new(t);
        c->next = d->bucket[i];
        d->bucket[i] = c;
    } else {
        assert("term already hash consed" == NULL);
        /* Chain already exists, replace the value. */
        c->value = t;
    }
}