From 61f617fe39f891f3dfc5b4815e20ef70a0497a64 Mon Sep 17 00:00:00 2001
From: Bad Diode <bd@badd10de.dev>
Date: Thu, 21 Oct 2021 17:55:04 +0200
Subject: Finalize initial hash table implementation for Objects

---
 src/bootstrap/hashtable.h | 73 ++++++++++++++++++++++++++---------------------
 1 file changed, 41 insertions(+), 32 deletions(-)

(limited to 'src')

diff --git a/src/bootstrap/hashtable.h b/src/bootstrap/hashtable.h
index 59f0660..ca4ced8 100644
--- a/src/bootstrap/hashtable.h
+++ b/src/bootstrap/hashtable.h
@@ -29,6 +29,19 @@ typedef struct HashTable {
     uint8_t shift_amount;
 } HashTable;
 
+// Hash a byte stream using a circular shift + XOR hash function.
+static inline uint64_t
+_xor_shift_hash(const char *key, size_t n) {
+    uint64_t hash = 0x65d9d65f6a19574f;
+    char *last = (char *)key + n;
+    while (key != last) {
+        putchar(*key);
+        hash ^= (uint64_t)*key++;
+        hash = (hash << 8) | (hash >> (64 - 8));
+    }
+    return hash;
+}
+
 // 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) {
@@ -37,11 +50,28 @@ _fibonacci_hash(uint64_t hash, size_t shift_amount) {
 
 uint64_t
 ht_hash(const HashTable *table, const Object *key) {
-    uint64_t hash = 0x65d9d65f6a19574f;
-    // printf("HASHING: ");
-    // display(key);
-    // printf("\n");
-    return 0;
+    uint64_t hash;
+    switch (key->type) {
+        case OBJ_TYPE_FIXNUM: {
+            hash = key->fixnum;
+        } break;
+        case OBJ_TYPE_STRING: {
+            hash = _xor_shift_hash(key->string, array_size(key->string));
+        } break;
+        case OBJ_TYPE_SYMBOL: {
+            hash = _xor_shift_hash(key->symbol, array_size(key->symbol));
+        } break;
+        case OBJ_TYPE_BOOL:
+        case OBJ_TYPE_NIL:
+        case OBJ_TYPE_PAIR:
+        case OBJ_TYPE_LAMBDA:
+        case OBJ_TYPE_PROCEDURE:
+        case OBJ_TYPE_ERR: {
+            hash = (uintptr_t)key;
+        } break;
+    }
+    hash = _fibonacci_hash(hash, table->shift_amount);
+    return hash;
 }
 
 static inline float
@@ -88,7 +118,7 @@ _ht_insert(HashTable *table, const Object *key, const Object *value) {
 }
 
 void
-ht_maybe_grow(HashTable *table) {
+_ht_maybe_grow(HashTable *table) {
     HashTablePair *pairs = table->pairs;
     if (ht_load_factor(table) < HT_LOAD_THRESHOLD) {
         return;
@@ -100,6 +130,7 @@ ht_maybe_grow(HashTable *table) {
     for (size_t i = 0; i < array_cap(table->pairs); i++) {
         table->pairs[i] = (HashTablePair){NULL, NULL};
     }
+    table->shift_amount++;
 
     // Hash everything in the table for the new array capacity.
     for (size_t i = 0; i < array_cap(pairs); i++) {
@@ -114,7 +145,7 @@ ht_maybe_grow(HashTable *table) {
 
 void
 ht_insert(HashTable *table, const Object *key, const Object *value) {
-    ht_maybe_grow(table);
+    _ht_maybe_grow(table);
     _ht_insert(table, key, value);
     return;
 }
@@ -139,6 +170,9 @@ ht_lookup(const HashTable *table, const Object *key) {
         } else {
             probe_position++;
         }
+        if (probe_position == position) {
+            return NULL;
+        }
     }
     return pairs[probe_position].value;
 }
@@ -172,29 +206,4 @@ ht_free(HashTable *table) {
     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) {
-//     return (hash * UINT64_C(11400714819323198485)) >> (64 - shift_amount);
-// }
-
-// // Hash a null terminated string using a circular shift + XOR hash function.
-// static inline
-// uint64_t _string_hash(const HashStash *table, const char *key) {
-//     uint64_t hash = 0x65d9d65f6a19574f;
-//     while (*key) {
-//         hash ^= (uint64_t)*key++;
-//         hash = (hash << 8) | (hash >> (64 - 8));
-//     }
-//     return _fibonacci_hash(hash, table->shift_amount);
-// }
-
-// // Return the key as an unsigned integer.
-// static inline
-// uint64_t _number_hash(const HashStash *table, const char *key) {
-//     uint64_t hash = 0;
-//     memcpy(&hash, key, table->key_length);
-//     return _fibonacci_hash(hash, table->shift_amount);
-// }
-
 #endif // BDL_HASHTABLE_H
-- 
cgit v1.2.1