1 files changed, 137 insertions, 0 deletions
diff --git a/map.c b/map.c
new file mode 100644
index 0000000..736233b
--- /dev/null
+++ b/map.c
@@ -0,0 +1,137 @@
+#include <assert.h>
+#include <stdbool.h>
+#include <stdint.h>
+#include <stdlib.h>
+#include <string.h>
+#include "util.h"
+#include "map.h"
+
+struct map {
+	size_t len, cap;
+	struct mapkey *keys;
+	void **vals;
+};
+
+static uint64_t
+hash(const void *ptr, size_t len)
+{
+	extern int siphash(const uint8_t *, const size_t, const uint8_t *, uint8_t *, const size_t);
+	static const uint8_t k[16] = {0};  // XXX: we don't have a way to get entropy in standard C
+	uint64_t r;
+
+	siphash(ptr, len, k, (uint8_t *)&r, sizeof(r));
+
+	return r;
+}
+
+void
+mapbufkey(struct mapkey *k, const char *s, size_t n)
+{
+	k->str = s;
+	k->len = n;
+	k->hash = hash(s, n);
+}
+
+void
+mapstrkey(struct mapkey *k, const char *s)
+{
+	mapbufkey(k, s, strlen(s));
+}
+
+struct map *
+mkmap(size_t cap)
+{
+	struct map *h;
+	size_t i;
+
+	assert(!(cap & cap - 1));
+	h = xmalloc(sizeof(*h));
+	h->len = 0;
+	h->cap = cap;
+	h->keys = xreallocarray(NULL, cap, sizeof(h->keys[0]));
+	h->vals = xreallocarray(NULL, cap, sizeof(h->vals[0]));
+	for (i = 0; i < cap; ++i)
+		h->keys[i].str = NULL;
+
+	return h;
+}
+
+void
+delmap(struct map *h, void del(void *))
+{
+	size_t i;
+
+	if (!h)
+		return;
+	if (del) {
+		for (i = 0; i < h->cap; ++i) {
+			if (h->keys[i].str)
+				del(h->vals[i]);
+		}
+	}
+	free(h->keys);
+	free(h->vals);
+	free(h);
+}
+
+static bool
+keyequal(struct mapkey *k1, struct mapkey *k2)
+{
+	if (k1->hash != k2->hash || k1->len != k2->len)
+		return false;
+	return memcmp(k1->str, k2->str, k1->len) == 0;
+}
+
+static size_t
+keyindex(struct map *h, struct mapkey *k)
+{
+	size_t i;
+
+	i = k->hash & h->cap - 1;
+	while (h->keys[i].str && !keyequal(&h->keys[i], k))
+		i = i + 1 & h->cap - 1;
+	return i;
+}
+
+void **
+mapput(struct map *h, struct mapkey *k)
+{
+	struct mapkey *oldkeys;
+	void **oldvals;
+	size_t i, j, oldcap;
+
+	if (h->cap / 2 < h->len) {
+		oldkeys = h->keys;
+		oldvals = h->vals;
+		oldcap = h->cap;
+		h->cap *= 2;
+		h->keys = xreallocarray(NULL, h->cap, sizeof(h->keys[0]));
+		h->vals = xreallocarray(NULL, h->cap, sizeof(h->vals[0]));
+		for (i = 0; i < h->cap; ++i)
+			h->keys[i].str = NULL;
+		for (i = 0; i < oldcap; ++i) {
+			if (oldkeys[i].str) {
+				j = keyindex(h, &oldkeys[i]);
+				h->keys[j] = oldkeys[i];
+				h->vals[j] = oldvals[i];
+			}
+		}
+	}
+	i = keyindex(h, k);
+	if (!h->keys[i].str) {
+		h->keys[i] = *k;
+		h->vals[i] = NULL;
+		++h->len;
+	}
+
+	return &h->vals[i];
+}
+
+void *
+mapget(struct map *h, struct mapkey *k)
+{
+	size_t i;
+
+	i = keyindex(h, k);
+	return h->keys[i].str ? h->vals[i] : NULL;
+}