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

typedef struct Tuple Tuple;
typedef struct Htab Htab;
typedef unsigned long hash_t;

struct Tuple {
    int n;
    int p;
    int q;
};

struct Htab {
    size_t  sz;
    size_t  count;
    hash_t  *hashes;
    Tuple   *keys;
    int *vals;
};

void hput(Htab *ht, Tuple *k, int v);
int hget(Htab *ht, Tuple *k, int *v);
Htab *hnew(void);

static hash_t hash(Tuple *t)
{
    hash_t h;
    /* dumb, crappy hash function.
     * Something better is left as an
     * exercise to the reader */
    h = t->n ^ t->p << 8 ^ t->q << 16;
    if (!h)
        h++;
    return h;
}

static int eq(Tuple *a, Tuple *b)
{
    return a->n == b->n && a->p == b->p && a->q == b->q;
}

static void grow(Htab *ht)
{
    hash_t  *oldh;
    Tuple   *oldk;
    int *oldv;
    size_t  oldsz, i;

    oldh = ht->hashes;
    oldk = ht->keys;
    oldv = ht->vals;
    oldsz = ht->sz;

    ht->count = 0;
    ht->sz = oldsz * 2;
    ht->hashes = calloc(sizeof(hash_t), ht->sz);
    ht->keys = calloc(sizeof(Tuple), ht->sz);
    ht->vals = calloc(sizeof(int), ht->sz);
    assert(ht->hashes != NULL && ht->keys != NULL && ht->vals != NULL);

    for (i = 0; i < oldsz; i++)
        if (oldh[i] != 0)
            hput(ht, &oldk[i], oldv[i]);
    free(oldh);
    free(oldk);
    free(oldv);
}

Htab *hnew()
{
    Htab *ht;

    ht = malloc(sizeof(Htab));
    if (!ht)
        abort();
    ht->sz = 16; /* or some other reasonable size */
    ht->count = 0;
    ht->hashes = calloc(sizeof(hash_t), ht->sz);
    ht->keys = calloc(sizeof(Tuple), ht->sz);
    ht->vals = calloc(sizeof(int), ht->sz);
        assert(ht->hashes != NULL && ht->keys != NULL && ht->vals != NULL);

    return ht;
}

void hfree(Htab *ht)
{
    free(ht->hashes);
    free(ht->keys);
    free(ht->vals);
    free(ht);
}

void hput(Htab *ht, Tuple *k, int v)
{
    size_t i, di;
    hash_t h;

    di = 0;
    h = hash(k);
    i = h % ht->sz;
    while (ht->hashes[i]) {
        if (ht->hashes[i] == h && eq(k, &ht->keys[i]))
            break;
        di++;
        i = (h + di) % ht->sz;
    }

    ht->hashes[i] = h;
    ht->keys[i] = *k;
    ht->vals[i] = v;
    ht->count++;
    if (ht->sz < ht->count*2)
        grow(ht);
}

int hget(Htab *ht, Tuple *k, int *v)
{
    size_t i, di;
    hash_t h;

    di = 0;
    h = hash(k);
    i = h % ht->sz;
    do {
        while (ht->hashes[i] && ht->hashes[i] != h) {
            di++;
            i = (h + di) % ht->sz;
        }
        if (!ht->hashes[i])
            return 0;
    } while (!eq(k, &ht->keys[i]));
    *v = ht->vals[i];
    return 1;
}

int main(int argc, char **argv)
{
    Tuple tu[] = {
        {1,1,2},
        {2,1,3},
        {1,1,0},
        {1,1,1},
    };
    Htab *ht;
    int v;

    ht = hnew();
    hput(ht, &tu[0], 3);
    hput(ht, &tu[1], 2);
    hput(ht, &tu[2], 1);
    if (!hget(ht, &tu[0], &v))
        assert(v == 3);
    if (!hget(ht, &tu[1], &v))
        assert(v == 2);
    if (!hget(ht, &tu[2], &v))
        assert(v == 1);
    assert(!hget(ht, &tu[3], &v));
    return 0;
}