Use linked list to back a hash table to handle collisions

3 files changed, 56 insertions, 17 deletions

diff --git a/src/02/04/hash.c b/src/02/04/hash.c
index 9986173..01942ed 100644
--- a/src/02/04/hash.c
+++ b/src/02/04/hash.c
@@ -8,24 +8,64 @@ static int to_hash(int key)
   return key % 13;
 }
 
-Hash *hash_init(int size)
+Node *node_init()
+{
+  Node *node = malloc(sizeof(Node));
+  node->next = NULL;
+  node->value = NULL;
+  return node;
+}
+
+Node *node_at(Node *head, int index)
+{
+  Node *current = head;
+
+  for (int i = 0; i < index; i++)
+    current = current->next;
+
+  return current;
+}
+
+void node_inspect(Node *node)
+{
+  if (!node)
+    return;
+
+  int i = 0;
+  while (node) {
+    printf("[%d: %3d]", i, node->value);
+    node = node->next;
+    i++;
+  }
+  printf("\n");
+}
+
+Hash *hash_init(int buckets)
 {
   Hash *hash = malloc(sizeof(Hash));
-  hash->size = size;
+  hash->head = node_init();
+  Node *current = hash->head;
+
+  for (int i = 1; i < buckets; i++) {
+    current->next = node_init();
+    current = current->next;
+  }
   return hash;
 }
 
-int hash_get(Hash *hash, int key)
+void *hash_get(Hash *hash, int key)
 {
   int bucket = to_hash(key);
-  Node node = hash->buckets[bucket];
-  return node.data;
+  Node *node = node_at(hash->head, bucket);
+  node_inspect(hash->head);
+  return node->value;
 }
 
-void hash_set(Hash *hash, int key, int value)
+void hash_set(Hash *hash, int key, void *value)
 {
+  node_inspect(hash->head);
   int bucket = to_hash(key);
-  Node node = hash->buckets[bucket];
-  node.data = value;
-  return;
+  Node *node = node_at(hash->head, bucket);
+  node->value = value;
+  node_inspect(hash->head);
 }
diff --git a/src/02/04/hash.h b/src/02/04/hash.h
index b87f06c..24ae331 100644
--- a/src/02/04/hash.h
+++ b/src/02/04/hash.h
@@ -1,13 +1,12 @@
 typedef struct node {
   struct node *next;
-  int data;
+  void *value;
 } Node;
 
 typedef struct {
-  Node buckets[13];
-  int size;
+  Node *head;
 } Hash;
 
-Hash *hash_init(int size);
-int hash_get(Hash *hash, int key);
-void hash_set(Hash *hash, int key, int value);
+Hash *hash_init(int buckets);
+void *hash_get(Hash *hash, int key);
+void hash_set(Hash *hash, int key, void *value);
diff --git a/src/02/04/hash_test.c b/src/02/04/hash_test.c
index 9073897..4579102 100644
--- a/src/02/04/hash_test.c
+++ b/src/02/04/hash_test.c
@@ -23,8 +23,8 @@ Ensure(HashTable, when_getting_a_values_for_a_key_that_has_been_inserted) {
   int value = 100;
   Hash *hash = hash_init(13);
 
-  hash_set(hash, key, value);
-  assert_that(hash_get(hash, key), is_equal_to(value));
+  hash_set(hash, key, &value);
+  assert_that(*(int *)hash_get(hash, key), is_equal_to(value));
 }
 
 TestSuite *hash_table_tests() {