th

1 files changed, 78 insertions, 0 deletions

diff --git a/ht.c b/ht.c
new file mode 100644
index 0000000..44132f5
--- /dev/null
+++ b/ht.c
@@ -0,0 +1,78 @@
+#include "ht.h"
+
+#include <stdint.h>
+#include <stdio.h>
+#include <string.h>
+
+#define FNV_BASIS 0x811c9dc5 
+#define FNV_PRIME 0x01000193
+
+// fnv-1a
+static uint32_t hash(char *s) {
+	uint32_t h = FNV_BASIS;
+	for(;;) {
+		h ^= *s;
+		h *= FNV_PRIME;
+		if (*s == '\0') break;
+		s++;
+	}
+	return h;
+}
+
+Ht ht_new() {
+	Ht h;
+	h.len = 0;
+	for (int i = 0; i < HT_SIZE; i++) {
+		h.b[i] = (HtEntry){ .k = NULL, .v=0 };
+	}
+	return h;
+}
+
+void ht_put(Ht *h, char *k, int v) {
+	uint32_t hv = hash(k);
+	int start = hv%HT_SIZE;
+	for (int cur = start; cur != start - 1; cur = (cur+1)%HT_SIZE) {
+		HtEntry *ent = &h->b[cur];
+		if (ent->k == NULL)  {
+			printf(" p %d\n",cur);
+			ent->k = strdup(k);
+			ent->v = v;
+			h->len++;
+			break;
+		} else if (0 == strcmp(k, ent->k)) {
+			printf(" r %d\n",cur);
+			ent->v = v;
+			break;
+		} else {
+			printf(" n %d\n",cur);
+		}
+	}
+}
+
+int ht_get(Ht *h, char *k, int *v) {
+	uint32_t hv = hash(k);
+	int start = hv%HT_SIZE;
+	for (int cur = start; cur != start - 1; cur = (cur+1)%HT_SIZE) {
+		HtEntry *ent = &h->b[cur];
+		if (ent->k == NULL) {
+			return 0; // not found
+		} else if (0 == strncmp(ent->k, k, 80)) {
+			*v = ent->v;
+			return 1;
+		}
+	}
+	return 0; // exhausted
+}
+
+void ht_dump(Ht *h) {
+	printf("#%d:\n",h->len);
+	for (int i = 0; i < HT_SIZE; i++) {
+		HtEntry ent = h->b[i];
+		if (ent.k != NULL) {
+			printf(" %s:%d\n",ent.k,ent.v);
+		}
+	}
+}
+
+
+