2 files changed, 112 insertions, 1 deletions
diff --git a/shash.h b/shash.h
new file mode 100644
index 0000000..604b1e0
--- /dev/null
+++ b/shash.h
@@ -0,0 +1,110 @@
+#ifndef SHASH_H
+#define SHASH_H
+
+#include <stdlib.h>
+#include <stdint.h>
+#include <ctype.h>
+
+#include "stdwrm.h"
+#include "dynarr.h"
+#include "str.h"
+
+#define SHASH_SLOTS 8192
+
+typedef uint64_t hash_t;
+
+typedef struct {
+	string key;
+	void *value;
+	hash_t hash;
+} StrHashEntry;
+
+typedef struct {
+	DYNARR(StrHashEntry) entries;
+} StrHashSlot;
+
+typedef struct {
+	StrHashSlot slots[SHASH_SLOTS];
+} StrHashTable;
+
+hash_t shash(strv_t s);
+void shash_init(StrHashTable *h);
+void shash_free(StrHashTable *h);
+void *shash_get(StrHashTable *h, strv_t key);
+void shash_put(StrHashTable *h, strv_t key, void *value);
+StrHashEntry *shash_find(StrHashTable *h, strv_t key);
+
+#ifdef STDWRM_IMPL_SHASH
+
+/* hacky FNV-1a hash */
+
+#define FNV_64_PRIME (hash_t)1099511628211LU
+#define FNV_OFFSET_BASIS (hash_t)14695981039346656037LU
+hash_t shash(strv_t s) {
+	hash_t h = FNV_OFFSET_BASIS;
+	for (size_t i = 0; i < s.n; i++) h = (h ^ s.s[i]) * FNV_64_PRIME;
+	return h;
+}
+
+/* hash table */
+
+void shash_init(StrHashTable *h) {
+	*h = (StrHashTable) { 0 };
+}
+
+void shash_free(StrHashTable *h) {
+	for (unsigned i = 0; i < SHASH_SLOTS; i++) {
+		StrHashSlot *s = &h->slots[i];
+		if (!s->entries) continue;
+		DA_FOR(s->entries, e) sfree(e->key);
+		DA_FREE(s->entries);
+	}
+}
+
+static inline int shash_entry_match(StrHashEntry *h, strv_t s, hash_t shash) {
+	return h->hash == shash && slen(h->key) == s.n && !strncmp(h->key, s.s, s.n);
+}
+
+static inline StrHashEntry *shash_find_hashed(StrHashTable *h, strv_t key, hash_t k) {
+	size_t i = k & (SHASH_SLOTS - 1);
+	if (h->slots[i].entries) {
+		DA_FOR(h->slots[i].entries, e) {
+			if (shash_entry_match(e, key, k)) {
+				return e;
+			}
+		}
+	}
+	return NULL;
+}
+
+StrHashEntry *shash_find(StrHashTable *h, strv_t key) {
+	return shash_find_hashed(h, key, shash(key));
+}
+
+void *shash_get(StrHashTable *h, strv_t key) {
+	StrHashEntry *e = shash_find(h, key);
+	return e ? e->value : NULL;
+}
+
+void shash_put(StrHashTable *h, strv_t key, void *value) {
+	hash_t keyh = shash(key);
+	StrHashEntry *e = shash_find_hashed(h, key, keyh);
+	if (e) {
+		e->value = value;
+	} else {
+		hash_t keyi = keyh & (SHASH_SLOTS - 1);
+		if (!h->slots[keyi].entries) {
+			DA_INIT(h->slots[keyi].entries);
+		}
+		string s = snew();
+		scats(&s, key);
+		DA_PUSH(h->slots[keyi].entries, (StrHashEntry) {
+			.key = s,
+			.value = value,
+			.hash = keyh
+		});
+	}
+}
+
+#endif
+#endif
diff --git a/stdwrm.h b/stdwrm.h
index 0b44a2b..1ee7281 100644
--- a/stdwrm.h
+++ b/stdwrm.h
@@ -2,7 +2,8 @@
 #define STDWRM_H
 
 #ifdef STDWRM_IMPL
-#define STDWRM_STR_IMPL
+#define STDWRM_IMPL_SHASH
+#define STDWRM_IMPL_STR
 #endif
 
 #endif