hash_table: Implement hash_table data struct

3 files changed, 333 insertions, 12 deletions

diff --git a/hash_table.c b/hash_table.c
index 0fc28c7..36fbe86 100644
--- a/hash_table.c
+++ b/hash_table.c
@@ -17,11 +17,27 @@
  */
 #include "hash_table.h"
 
+#include <assert.h>
+#include <stdbool.h>
+#include <stdint.h>
 #include <stdio.h>
 #include <stdlib.h>
+#include <string.h>
 
 #define INITAL_CAPACITY 16
 
+#define FNV_OFFSET 14695981039346656037UL
+#define FNV_PRIME 1099511628211UL
+
+
+static uint64_t    hash_key(const char *key);
+static const char *hash_table_set_entry(hash_table_entry_t *entries,
+                                        size_t              capacity,
+                                        const char         *key,
+                                        void               *value,
+                                        size_t             *plength);
+static bool        hash_table_expand(hash_table_t *ht);
+
 hash_table_t*
 hash_table_new(void)
 {
@@ -30,5 +46,187 @@ hash_table_new(void)
     fprintf(stderr, "could not create hash_table: out of memory\n");
     return NULL;
   }
+  ht->capacity = INITAL_CAPACITY;
+  ht->length = 0;
+
+  ht->entries = calloc(ht->capacity, sizeof(hash_table_entry_t));
+  if (ht->entries == NULL) {
+    fprintf(stderr, "could not create hash_entry: out of memory\n");
+    free(ht);
+    return NULL;
+  }
+
   return ht;
 }
+
+void
+hash_table_destroy(hash_table_t *ht)
+{
+  for (size_t i = 0; i < ht->capacity; ++i) {
+    if (ht->entries[i].key != NULL) {
+      free((void*) ht->entries[i].key);
+    }
+  }
+  free(ht->entries);
+  free(ht);
+}
+
+void
+hash_table_insert(hash_table_t *ht, const char *key, void *value)
+{
+  assert(value != NULL);
+  
+  if (ht->length >= ht->capacity / 2) {
+    if (!hash_table_expand(ht)) {
+      return;
+    }
+  }
+
+  hash_table_set_entry(ht->entries, ht->capacity, key, value, &ht->length);
+}
+
+
+void*
+hash_table_get(hash_table_t *ht,
+               const char   *key)
+{
+  uint64_t hash = hash_key(key);
+  size_t index = (size_t)(hash & (uint64_t)(ht->capacity - 1));
+
+  while (ht->entries[index].key != NULL) {
+    if (strcmp(key, ht->entries[index].key) == 0) {
+      return ht->entries[index].value;
+    }
+    index++;
+    if (index >= ht->capacity) {
+      index = 0;
+    }
+  }
+  return NULL;
+}
+
+bool
+hash_table_remove(hash_table_t *ht,
+                  const char   *key)
+{
+  uint64_t hash = hash_key(key);
+  size_t index = (size_t)(hash & (uint64_t)(ht->capacity - 1));
+
+  while (ht->entries[index].key != NULL) {
+    if (strcmp(key, ht->entries[index].key) == 0) {
+      free(ht->entries[index].key);
+      ht->entries[index] = (hash_table_entry_t) { NULL, NULL };
+      ht->length--;
+      return true;
+    }
+    index++;
+    if (index >= ht->capacity) {
+      index = 0;
+    }
+  }
+  return false;
+}
+
+size_t
+hash_table_length(hash_table_t *ht)
+{
+  return ht->length;
+}
+
+static uint64_t
+hash_key(const char *key)
+{
+  uint64_t hash = FNV_OFFSET;
+  for (const char* p = key; *p; ++p) {
+    hash ^= (uint64_t) (unsigned char) (*p);
+    hash *= FNV_PRIME;
+  }
+  return hash;
+}
+
+static const char*
+hash_table_set_entry(hash_table_entry_t *entries,
+                     size_t              capacity,
+                     const char         *key,
+                     void               *value,
+                     size_t             *plength)
+{
+    uint64_t hash = hash_key(key);
+    size_t index = (size_t)(hash & (uint64_t)(capacity - 1));
+
+    while (entries[index].key != NULL) {
+        if (strcmp(key, entries[index].key) == 0) {
+            entries[index].value = value;
+            return entries[index].key;
+        }
+        index++;
+        if (index >= capacity) {
+            index = 0;
+        }
+    }
+
+    if (plength != NULL) {
+        key = strdup(key);
+        if (key == NULL) {
+            return NULL;
+        }
+        (*plength)++;
+    }
+    entries[index].key = (char*)key;
+    entries[index].value = value;
+    return key;
+}
+
+static bool
+hash_table_expand(hash_table_t *ht)
+{
+    size_t new_capacity = ht->capacity * 2;
+    if (new_capacity < ht->capacity) {
+        return false;
+    }
+    hash_table_entry_t* new_entries = calloc(new_capacity, sizeof(hash_table_entry_t));
+    if (new_entries == NULL) {
+        return false;
+    }
+
+    for (size_t i = 0; i < ht->capacity; ++i) {
+        hash_table_entry_t entry = ht->entries[i];
+        if (entry.key != NULL) {
+            hash_table_set_entry(
+                new_entries,
+                new_capacity,
+                entry.key,
+                entry.value,
+                NULL
+            );
+        }
+    }
+
+    free(ht->entries);
+    ht->entries = new_entries;
+    ht->capacity = new_capacity;
+    return true;
+}
+
+hash_table_iterator_t hash_table_get_iterator(hash_table_t *ht) {
+    hash_table_iterator_t it;
+    it._table = ht;
+    it._index = 0;
+    return it;
+}
+
+bool hash_table_iterator_next(hash_table_iterator_t *it) {
+    hash_table_t* ht = it->_table;
+    while (it->_index < ht->capacity) {
+        size_t i = it->_index;
+        it->_index++;
+        if (ht->entries[i].key != NULL) {
+            hash_table_entry_t entry = ht->entries[i];
+            it->key = entry.key;
+            it->value = entry.value;
+            return true;
+        }
+    }
+    return false;
+}
+
diff --git a/hash_table.h b/hash_table.h
index 5ac3cfd..66731b5 100644
--- a/hash_table.h
+++ b/hash_table.h
@@ -16,21 +16,45 @@
  * along with this program.  If not, see <https://www.gnu.org/licenses/>.
  */
 #ifndef HASH_TABLE_H
-#define HASH_TABLE
+#define HASH_TABLE_H
 
 #include <stdio.h>
+#include <stdbool.h>
 
-typedef struct hash_entry {
-  const char* key;
-  void* value;
-} hash_entry_t;
+typedef struct hash_table hash_table_t;
+typedef struct hash_table_entry hash_table_entry_t;
+typedef struct hash_table_iterator hash_table_iterator_t;
 
-typedef struct hash_table {
-  hash_entry_t* entries;
+struct hash_table {
+  hash_table_entry_t* entries;
   size_t capacity;
   size_t length;
-} hash_table_t;
+};
+
+struct hash_table_entry {
+  const char* key;
+  void* value;
+};
+
+struct hash_table_iterator {
+  const char* key;
+  void* value;
+  hash_table_t *_table;
+  size_t _index;
+};
+
+hash_table_t* hash_table_new     ();
+void          hash_table_destroy (hash_table_t *ht);
+void          hash_table_insert  (hash_table_t *ht,
+                                  const char   *key,
+                                  void         *value);
+bool          hash_table_remove  (hash_table_t *ht,
+                                  const char   *key);
+void*         hash_table_get     (hash_table_t *ht,
+                                  const char   *key);
+size_t        hash_table_length  (hash_table_t *ht);
 
-hash_table_t* hash_table_new();
+hash_table_iterator_t hash_table_get_iterator(hash_table_t *ht);
+bool hash_table_iterator_next(hash_table_iterator_t *it);
 
 #endif /* HASH_TABLE_H */
diff --git a/test/hash_table_test.c b/test/hash_table_test.c
index 075c9d2..e2f7027 100644
--- a/test/hash_table_test.c
+++ b/test/hash_table_test.c
@@ -21,24 +21,123 @@
 
 #include <stdlib.h>
 
-static MunitResult 
-test_create_new(const  MunitParameter params[], 
+static MunitResult
+test_create_new(const  MunitParameter params[],
                 void  *user_data_or_fixture)
 {
   hash_table_t* table = hash_table_new();
 
   assert_not_null(table);
+  assert_int(table->capacity, >, 0);
+  assert_int(table->length, ==, 0);
 
+  hash_table_destroy(table);
+  return MUNIT_OK;
+}
+
+static MunitResult
+test_insert_and_get(const  MunitParameter params[],
+                    void  *user_data_or_fixture)
+{
+  hash_table_t* table = hash_table_new();
+
+  hash_table_insert(table, "key1", "value1");
+  hash_table_insert(table, "key2", "value2");
+
+  char* value = hash_table_get(table, "key1");
+  assert_string_equal("value1", value);
+
+  value = hash_table_get(table, "key2");
+  assert_string_equal("value2", value);
+
+  value = hash_table_get(table, "invalid_key");
+  assert_null(value);
+
+  hash_table_destroy(table);
+  return MUNIT_OK;
+}
+
+static MunitResult
+test_remove(const  MunitParameter params[],
+            void  *user_data_or_fixture)
+{
+  hash_table_t* table = hash_table_new();
+
+  hash_table_insert(table, "key", "value");
+
+  char* value = hash_table_get(table, "key");
+  assert_string_equal("value", value);
+
+  bool removed = hash_table_remove(table, "key");
+
+  assert_int(hash_table_length(table), ==, 0);
+  assert_null(hash_table_get(table, "key"));
+  assert_true(removed);
+
+  hash_table_destroy(table);
+  return MUNIT_OK;
+}
+
+static MunitResult
+test_length(const  MunitParameter params[],
+            void  *user_data_or_fixture)
+{
+  hash_table_t* table = hash_table_new();
+
+  hash_table_insert(table, "key1", "value1");
+  hash_table_insert(table, "key2", "value2");
+
+  assert_int(2, ==, hash_table_length(table));
+
+  hash_table_destroy(table);
+  return MUNIT_OK;
+}
+
+static MunitResult
+test_iterator(const  MunitParameter params[],
+              void  *user_data_or_fixture)
+{
+  hash_table_t* table = hash_table_new();
+
+  hash_table_insert(table, "key1", "value1");
+  hash_table_insert(table, "key2", "value2");
+
+  hash_table_iterator_t it = hash_table_get_iterator(table);
+
+  size_t count;
+  for (count = 0; hash_table_iterator_next(&it); ++count) {
+    if (strcmp(it.key, "key1") != 0 &&
+        strcmp(it.key, "key2") != 0) {
+      fprintf(stderr, "key not found: %s\n", it.key);
+      hash_table_destroy(table);
+      return MUNIT_FAIL;
+    }
+
+    if (strcmp(it.value, "value1") != 0 &&
+        strcmp(it.value, "value2") != 0) {
+      fprintf(stderr, "value not found: %s\n", it.value);
+      hash_table_destroy(table);
+      return MUNIT_FAIL;
+    }
+  }
+
+  assert_int(hash_table_length(table), ==, count);
+
+  hash_table_destroy(table);
   return MUNIT_OK;
 }
 
 static MunitTest tests[] = {
   { "/test_create_new", test_create_new, NULL, NULL, MUNIT_TEST_OPTION_NONE, NULL },
+  { "/test_insert_and_get", test_insert_and_get, NULL, NULL, MUNIT_TEST_OPTION_NONE, NULL },
+  { "/test_remove", test_remove, NULL, NULL, MUNIT_TEST_OPTION_NONE, NULL },
+  { "/test_length", test_length, NULL, NULL, MUNIT_TEST_OPTION_NONE, NULL },
+  { "/test_iterator", test_iterator, NULL, NULL, MUNIT_TEST_OPTION_NONE, NULL },
   { NULL, NULL, NULL, NULL, MUNIT_TEST_OPTION_NONE, NULL }
 };
 
 static const MunitSuite suite = {
-  "/hash_table", tests, NULL, 1, MUNIT_SUITE_OPTION_NONE 
+  "/hash_table", tests, NULL, 1, MUNIT_SUITE_OPTION_NONE
 };
 
 int