--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/ploki/hash.c	Fri Dec 20 22:18:50 2013 +0000
@@ -0,0 +1,273 @@
+#include "config.h"
+#include "hash.h"
+#include "main.h"
+#include "main_opt.h"
+#include "random.h"
+#include "xmalloc.h"
+
+#include <errno.h>
+#include <stddef.h>
+#include <stdio.h>
+#include <assert.h>
+
+struct h_entry {
+	size_t hash;
+	void *key;
+	void *value;
+};
+
+struct h_node {
+	struct h_entry entry;
+	struct h_node *next;
+};
+
+enum {MAGIC = 112};
+
+void h_init(
+		Hash *h,
+		size_t (*hash)(const void *, size_t),
+		int (*cmp)(const void *, const void *),
+		void (*delk)(void *),
+		void (*delv)(void *)
+		) {
+	size_t i;
+
+	h->entries = 0;
+	h->brk = -1;
+	h->iter = -1;
+	h->iterptr = NULL;
+	h->seed = randval() * (size_t)-1;
+	h->delk = delk;
+	h->delv = delv;
+	assert(hash != NULL);
+	h->hash = hash;
+	assert(cmp != NULL);
+	h->cmp = cmp;
+	h->table = xmalloc(h->newsize = h->size = MAGIC, sizeof *h->table);
+	for (i = 0; i < h->size; ++i) {
+		h->table[i] = NULL;
+	}
+}
+
+#define DELKV(p)                   \
+do {                               \
+	if (h->delk) {                 \
+		h->delk((p)->entry.key);   \
+	}                              \
+	if (h->delv) {                 \
+		h->delv((p)->entry.value); \
+	}                              \
+} while (0)
+
+void h_end(Hash *h) {
+	size_t size, b;
+
+	if (!h->table)
+		return;
+
+	for (b = 0, size = h->newsize; h->newsize; h->newsize--) {
+		struct h_node *p;
+
+		if ((p = h->table[h->newsize - 1])) {
+			++b;
+			for (; p; p = h->table[h->newsize - 1]) {
+				h->table[h->newsize - 1] = p->next;
+				DELKV(p);
+				xfree(p);
+			}
+		}
+	}
+	xfree(h->table);
+	h->table = NULL;
+
+	if (Opt.debug & DBG_HASH) {
+		fprintf(stderr, "%s: hash[%lu/%lu/%lu]\n", Prog, (unsigned long)h->entries, (unsigned long)b, (unsigned long)size);
+	}
+}
+
+ATTR_PURE
+static size_t xclip(const Hash *h, const size_t hash_unc) {
+	size_t hash;
+
+	hash = hash_unc % h->size;
+	if (hash > h->brk) {
+		hash = hash_unc % h->newsize;
+	}
+
+	return hash;
+}
+
+#if 0
+ATTR_PURE
+static size_t xhash(const Hash *h, const void *key) {
+	return xclip(h, h->hash(key, h->seed));
+}
+#endif
+
+#define XRESIZN(h) ((h)->brk + 1u)
+#define XSTEP(h)   do { if (XRESIZN(h)) xstep(h); } while (0)
+
+static void xstep(Hash *h) {
+	struct h_node *rev = NULL;
+	struct h_node *p;
+	struct h_node *tmp;
+
+	assert(h->table != NULL);
+
+	for (p = h->table[h->brk]; p; p = tmp) {
+		tmp = p->next;
+		p->next = rev;
+		rev = p;
+	}
+	h->table[h->brk--] = NULL;
+
+	if (!XRESIZN(h)) {
+		h->size = h->newsize;
+	}
+
+	for (p = rev; p; p = tmp) {
+		const size_t i = xclip(h, p->entry.hash);
+		tmp = p->next;
+		p->next = h->table[i];
+		h->table[i] = p;
+	}
+}
+
+static void xincentries(Hash *h) {
+	h->entries++;
+	if (!(XRESIZN(h)) && h->entries / h->size > 3u) {
+		size_t i;
+		h->table = xrealloc(h->table, h->newsize = h->size * 2u + 1u);
+		for (i = h->size; i < h->newsize; ++i) {
+			h->table[i] = NULL;
+		}
+		h->brk = h->size - 1u;
+		xstep(h);
+	}
+}
+
+int h_get(Hash *h, const void *key, void **res) {
+	XSTEP(h);
+	{
+		const size_t hash_unc = h->hash(key, h->seed);
+		const size_t hash = xclip(h, hash_unc);
+		struct h_node *p;
+
+		for (p = h->table[hash]; p; p = p->next) {
+			if (hash_unc == p->entry.hash && h->cmp(p->entry.key, key) == 0) {
+				if (res) {
+					*res = p->entry.value;
+				}
+				return H_OK;
+			}
+		}
+	}
+	return H_NOENT;
+}
+
+int h_del(Hash *h, const void *key) {
+	XSTEP(h);
+	{
+		const size_t hash_unc = h->hash(key, h->seed);
+		const size_t hash = xclip(h, hash_unc);
+		struct h_node **p;
+
+		for (p = &h->table[hash]; *p; p = &(*p)->next) {
+			if (hash_unc == (*p)->entry.hash && h->cmp((*p)->entry.key, key) == 0) {
+				struct h_node *tmp = *p;
+				*p = (*p)->next;
+				DELKV(tmp);
+				xfree(tmp);
+				h->entries--;
+				return H_OK;
+			}
+		}
+	}
+
+	return H_NOENT;
+}
+
+#if 0
+void h_push(Hash *h, void *key, void *val) {
+	XSTEP(h);
+	{
+		const size_t hash_unc = h->hash(key, h->seed);
+		const size_t hash = xclip(h, hash_unc);
+		struct h_node *p;
+
+		p = xmalloc(1, sizeof *p);
+		p->entry.hash = hash_unc;
+		p->entry.key = key;
+		p->entry.value = val;
+		p->next = h->table[hash];
+		h->table[hash] = p;
+
+		xincentries(h);
+	}
+}
+#endif
+
+int h_put(Hash *h, void *key, void *val, int replace) {
+	XSTEP(h);
+	{
+		const size_t hash_unc = h->hash(key, h->seed);
+		const size_t hash = xclip(h, hash_unc);
+		struct h_node **p;
+
+		for (p = &h->table[hash]; *p; p = &(*p)->next) {
+			if (hash_unc == (*p)->entry.hash && h->cmp((*p)->entry.key, key) == 0) {
+				if (replace) {
+					DELKV(*p);
+					(*p)->entry.key = key;
+					(*p)->entry.value = val;
+					return H_OK;
+				} else {
+					return H_EXIST;
+				}
+			}
+		}
+
+		*p = xmalloc(1, sizeof **p);
+
+		(*p)->entry.hash = hash_unc;
+		(*p)->entry.key = key;
+		(*p)->entry.value = val;
+		(*p)->next = NULL;
+
+		xincentries(h);
+	}
+
+	return H_OK;
+}
+
+void h_reset(Hash *h) {
+	h->iter = -1;
+	h->iterptr = NULL;
+}
+
+int h_nextkv(Hash *h, void **k, void **v) {
+	if (h->iterptr) {
+		*k = h->iterptr->entry.key;
+		*v = h->iterptr->entry.value;
+		h->iterptr = h->iterptr->next;
+		return H_OK;
+	}
+
+	for (h->iter++; h->iter < h->newsize; h->iter++) {
+		if ((h->iterptr = h->table[h->iter])) {
+			*k = h->iterptr->entry.key;
+			*v = h->iterptr->entry.value;
+			h->iterptr = h->iterptr->next;
+			return H_OK;
+		}
+	}
+
+	h->iter = -1;
+	return H_NOENT;
+}
+
+#if 0
+size_t (h_entries)(const Hash *h) {
+	return h_entries(h);
+}
+#endif