#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;
}