add ihash

2 files changed, 110 insertions, 0 deletions

diff --git a/ihash.h b/ihash.h
new file mode 100644
index 0000000..242e97c
--- /dev/null
+++ b/ihash.h
@@ -0,0 +1,109 @@
+#ifndef IHASH_H
+#define IHASH_H
+
+#include <stdlib.h>
+#include <stdint.h>
+#include <ctype.h>
+
+#include "dynarr.h"
+#include "str.h"
+
+#ifndef IHASH_SLOTS
+#define IHASH_SLOTS 8192
+#endif
+
+typedef uint64_t hash_t;
+
+typedef struct {
+	intptr_t key;
+	void *value;
+	hash_t hash;
+} IntHashEntry;
+
+typedef struct {
+	DYNARR(IntHashEntry) entries;
+} IntHashSlot;
+
+typedef struct {
+	IntHashSlot slots[IHASH_SLOTS];
+} IntHashTable;
+
+hash_t ihash(intptr_t s);
+void ihash_init(IntHashTable *h);
+void ihash_free(IntHashTable *h);
+void *ihash_get(IntHashTable *h, intptr_t key);
+void ihash_put(IntHashTable *h, intptr_t key, void *value);
+IntHashEntry *ihash_find(IntHashTable *h, intptr_t key);
+
+#ifdef IHASH_IMPL
+
+/* murmur64 integer hash */
+
+hash_t ihash(intptr_t h) {
+	h *= h >> 33;
+	h *= 0xff51afd7ed558ccdL;
+	h *= h >> 33;
+	h *= 0xc4ceb9fe1a85ec53L;
+	h *= h >> 33;
+	return h;
+}
+
+/* hash table */
+
+void ihash_init(IntHashTable *h) {
+	*h = (IntHashTable) { 0 };
+}
+
+void ihash_free(IntHashTable *h) {
+	for (unsigned i = 0; i < IHASH_SLOTS; i++) {
+		IntHashSlot *s = &h->slots[i];
+		if (!s->entries) continue;
+		DA_FREE(s->entries);
+	}
+}
+
+static inline int ihash_entry_match(IntHashEntry *h, intptr_t s, hash_t ihash) {
+	return s == ihash;
+}
+
+static inline IntHashEntry *ihash_find_hashed(IntHashTable *h, intptr_t key, hash_t k) {
+	size_t i = k & (IHASH_SLOTS - 1);
+	if (h->slots[i].entries) {
+		DA_FOR(h->slots[i].entries, e) {
+			if (ihash_entry_match(e, key, k)) {
+				return e;
+			}
+		}
+	}
+	return NULL;
+}
+
+IntHashEntry *ihash_find(IntHashTable *h, intptr_t key) {
+	return ihash_find_hashed(h, key, ihash(key));
+}
+
+void *ihash_get(IntHashTable *h, intptr_t key) {
+	IntHashEntry *e = ihash_find(h, key);
+	return e ? e->value : NULL;
+}
+
+void ihash_put(IntHashTable *h, intptr_t key, void *value) {
+	hash_t keyh = ihash(key);
+	IntHashEntry *e = ihash_find_hashed(h, key, keyh);
+	if (e) {
+		e->value = value;
+	} else {
+		hash_t keyi = keyh & (IHASH_SLOTS - 1);
+		if (!h->slots[keyi].entries) {
+			DA_INIT(h->slots[keyi].entries);
+		}
+		DA_PUSH(h->slots[keyi].entries, (IntHashEntry) {
+			.key = key,
+			.value = value,
+			.hash = keyh
+		});
+	}
+}
+
+#endif
+#endif
diff --git a/stdwrm.h b/stdwrm.h
index a1f9d0d..46992c3 100644
--- a/stdwrm.h
+++ b/stdwrm.h
@@ -3,6 +3,7 @@
 
 #ifdef STDWRM_IMPL
 #define SHASH_IMPL
+#define IHASH_IMPL
 #define ZONE_IMPL
 #define STR_IMPL
 #endif