From 528bcf1eaf7ec6a4441ce792733c9c5a649f61f9 Mon Sep 17 00:00:00 2001
From: Bad Diode <bd@badd10de.dev>
Date: Thu, 21 Oct 2021 15:18:32 +0200
Subject: Make the hash table growable

---
 src/bootstrap/hashtable.h | 60 ++++++++++++++++++++++++++++++++++++++++-------
 1 file changed, 51 insertions(+), 9 deletions(-)

diff --git a/src/bootstrap/hashtable.h b/src/bootstrap/hashtable.h
index baffec0..59f0660 100644
--- a/src/bootstrap/hashtable.h
+++ b/src/bootstrap/hashtable.h
@@ -5,8 +5,8 @@
 #include "objects.h"
 
 // Minimum table capacity.
-#define HT_MIN_CAP   4
-#define HT_MIN_SHIFT 2
+#define HT_MIN_CAP   2
+#define HT_MIN_SHIFT 1
 
 // Adjust the load factor threshold at which the table will grow on insertion.
 #define HT_LOAD_THRESHOLD 0.75
@@ -44,9 +44,9 @@ ht_hash(const HashTable *table, const Object *key) {
     return 0;
 }
 
-static inline size_t
+static inline float
 ht_load_factor(const HashTable *table) {
-    return array_size(table->pairs) / array_cap(table->pairs);
+    return (float)array_size(table->pairs) / (float)array_cap(table->pairs);
 }
 
 HashTable *
@@ -54,7 +54,6 @@ ht_init(void) {
     HashTable *table = malloc(sizeof(HashTable));
     table->pairs = NULL;
     array_init(table->pairs, HT_MIN_CAP);
-    // Clear the table ensuring all references point to NULL.
     for (size_t i = 0; i < array_cap(table->pairs); i++) {
         table->pairs[i] = (HashTablePair){NULL, NULL};
     }
@@ -63,8 +62,7 @@ ht_init(void) {
 }
 
 void
-ht_insert(HashTable *table, const Object *key, const Object *value) {
-    // TODO: Grow if needed.
+_ht_insert(HashTable *table, const Object *key, const Object *value) {
     size_t position = ht_hash(table, key);
     size_t probe_position = position;
 
@@ -73,12 +71,13 @@ ht_insert(HashTable *table, const Object *key, const Object *value) {
     HashTablePair *pairs = table->pairs;
     while (true) {
         if (pairs[probe_position].key == NULL) {
+            array_head(pairs)->size++;
             break;
         }
         if (obj_eq(pairs[probe_position].key, key)) {
             break;
         }
-        if (probe_position == array_cap(pairs)) {
+        if (probe_position == array_cap(pairs) - 1) {
             probe_position = 0;
         } else {
             probe_position++;
@@ -86,6 +85,37 @@ ht_insert(HashTable *table, const Object *key, const Object *value) {
     }
     pairs[probe_position].key = (Object *)key;
     pairs[probe_position].value = (Object *)value;
+}
+
+void
+ht_maybe_grow(HashTable *table) {
+    HashTablePair *pairs = table->pairs;
+    if (ht_load_factor(table) < HT_LOAD_THRESHOLD) {
+        return;
+    }
+
+    // Create a new array with 2x capacity.
+    table->pairs = NULL;
+    array_init(table->pairs, array_cap(pairs) * 2);
+    for (size_t i = 0; i < array_cap(table->pairs); i++) {
+        table->pairs[i] = (HashTablePair){NULL, NULL};
+    }
+
+    // Hash everything in the table for the new array capacity.
+    for (size_t i = 0; i < array_cap(pairs); i++) {
+        if (pairs[i].key != NULL) {
+            _ht_insert(table, pairs[i].key, pairs[i].value);
+        }
+    }
+
+    // Free the old array.
+    array_free(pairs);
+}
+
+void
+ht_insert(HashTable *table, const Object *key, const Object *value) {
+    ht_maybe_grow(table);
+    _ht_insert(table, key, value);
     return;
 }
 
@@ -104,7 +134,7 @@ ht_lookup(const HashTable *table, const Object *key) {
         if (obj_eq(pairs[probe_position].key, key)) {
             break;
         }
-        if (probe_position == array_cap(pairs)) {
+        if (probe_position == array_cap(pairs) - 1) {
             probe_position = 0;
         } else {
             probe_position++;
@@ -130,6 +160,18 @@ ht_debug(HashTable *table) {
     }
 }
 
+void
+ht_free(HashTable *table) {
+    if (table == NULL) {
+        return;
+    }
+    if (table->pairs == NULL) {
+        return;
+    }
+    array_free(table->pairs);
+    free(table);
+}
+
 // // Use Fibonacci hashing to map a hash to a value in range of the table.
 // static inline
 // uint64_t _fibonacci_hash(uint64_t hash, size_t shift_amount) {
-- 
cgit v1.2.1