From 9ee73a8459eb2bb58adc29da02de312b7e4e7dca Mon Sep 17 00:00:00 2001
From: ubq323 <ubq323@ubq323.website>
Date: Sat, 5 Aug 2023 04:15:17 +0100
Subject: refactor hashtables, and use objstrings for keys

doesn't yet work without string interning, which will require
further refactoring
---
 ht.c | 103 +++++++++++++++++++++++++++++++++++++------------------------------
 1 file changed, 57 insertions(+), 46 deletions(-)

(limited to 'ht.c')

diff --git a/ht.c b/ht.c
index 44132f5..ca93222 100644
--- a/ht.c
+++ b/ht.c
@@ -4,73 +4,84 @@
 #include <stdio.h>
 #include <string.h>
 
+#include "mem.h"
+
 #define FNV_BASIS 0x811c9dc5 
 #define FNV_PRIME 0x01000193
 
 // fnv-1a
-static uint32_t hash(char *s) {
+uint32_t hash(char *s, size_t len) {
 	uint32_t h = FNV_BASIS;
-	for(;;) {
-		h ^= *s;
+	for(int i = 0; i < len; i++) {
+		h ^= s[i];
 		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;
+	return (Ht){
+		.len = 0,
+		.cap = 0,
+		.b = NULL
+	};
 }
 
-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);
+static HtEntry *find(HtEntry *b, size_t cap, ObjString *k) {
+	size_t ix = k->hash % cap;
+	for (;;) {
+		HtEntry *ent = &b[ix];
+		if (ent->k == k || ent->k == NULL) {
+			return ent;
 		}
+		ix = (ix+1)%cap;
 	}
 }
 
-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;
+static void grow(Ht *h) {
+	HtEntry *old = h->b;
+	size_t newsz = h->cap == 0 ? 8 : h->cap * 2;
+	HtEntry *new = NEW_ARR(HtEntry, newsz);
+	for (int i = 0; i<newsz; i++) {
+		new[i].k = NULL;
+		new[i].v = VAL_NIL;
+	}
+
+	if (old != NULL) {
+		for (int i = 0; i < h->cap; i++) {
+			HtEntry *oldent = &old[i];
+			if (oldent->k == NULL) continue;
+
+			HtEntry *newent = find(new, newsz, oldent->k);
+			newent->k = oldent->k;
+			newent->v = oldent->v;
 		}
 	}
-	return 0; // exhausted
+
+	h->b = new;
+	FREE_ARR(old, HtEntry, h->cap);
+	h->cap = newsz;
 }
 
-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);
-		}
+
+void ht_put(Ht *h, ObjString *k, Val v) {
+	if (h->cap == 0 || h->len >= (h->cap/2)) {
+		grow(h);
+	}
+	HtEntry *ent = find(h->b, h->cap, k);
+	if (ent->k == NULL) {
+		ent->k = k;
+		h->len++;
+	}
+	ent->v = v;
+}
+
+Val ht_get(Ht *h, ObjString *k) {
+	HtEntry *ent = find(h->b, h->cap, k);
+	if (ent->k == NULL) {
+		return VAL_NIL;
+	} else {
+		return ent->v;
 	}
 }
 
-- 
cgit v1.2.3