util: Create hashmap data structure with FNV-1a 32-bit hashingHEADmaster

This path implements a hashmap data structure using the FNV-1a hashing
function of 32 bits.  However, there are a few limitations to consider:

    a) The table does not automatically expand when it becomes too large.

    b) The capacity of the hashmap must be a power of 2 to optimize
       performance, as we utilize bitwise shifting instead of modulus
       calculations.

    c) Currently, there are no functions available to destroy hashmap
       entries.

Collisions are handled using a linked list, which is not the most
optimal solution in terms of performance. However, it serves our current
needs adequately.

Signed-off-by: Johnny Richard <johnny@johnnyrichard.com>

4 files changed, 275 insertions, 0 deletions

diff --git a/src/hashmap.c b/src/hashmap.c
new file mode 100644
index 0000000..038678a
--- /dev/null
+++ b/src/hashmap.c
@@ -0,0 +1,132 @@
+/*
+ * Copyright (C) 2023 Johnny Richard
+ *
+ * This program is free software: you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation, either version 3 of the License, or
+ * (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program.  If not, see <https://www.gnu.org/licenses/>.
+ */
+#include "hashmap.h"
+
+#include <assert.h>
+#include <errno.h>
+#include <stdbool.h>
+#include <stdint.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+
+static uint32_t
+u32_fnv1a_hash(const char *s);
+static void
+hashmap_init(hashmap_t *map);
+static char *
+__strdup(const char *s);
+
+hashmap_t *
+hashmap_new(void)
+{
+  hashmap_t *map = (hashmap_t *)malloc(sizeof(hashmap_t));
+  if (map == NULL) {
+    fprintf(stderr, "[FATAL] Out of memory: hashmap_new: %s\n", strerror(errno));
+    exit(EXIT_FAILURE);
+  }
+
+  hashmap_init(map);
+  return map;
+}
+
+static void
+hashmap_init(hashmap_t *map)
+{
+  assert(map);
+  map->entries = (hashmap_entry_t *)calloc(HASHMAP_INITIAL_CAPACITY, sizeof(hashmap_entry_t));
+  if (map->entries == NULL) {
+    fprintf(stderr, "[FATAL] Out of memory: hashmap_init: %s\n", strerror(errno));
+    exit(EXIT_FAILURE);
+  }
+  map->capacity = HASHMAP_INITIAL_CAPACITY;
+}
+
+static uint32_t
+u32_fnv1a_hash(const char *s)
+{
+  uint32_t hash = U32_FNV1A_OFFSET_BASIS;
+  size_t len = strlen(s);
+  for (size_t i = 0; i < len; ++i) {
+    hash ^= s[i];
+    hash *= U32_FNV1A_PRIME;
+  }
+  return hash;
+}
+
+bool
+hashmap_put(hashmap_t *map, char *key, void *value)
+{
+  assert(map && key);
+  uint32_t hash = u32_fnv1a_hash(key);
+  hashmap_entry_t *entry = &(map->entries[hash & (map->capacity - 1)]);
+
+  while (entry != NULL) {
+    if (entry->hash == hash && strcmp(entry->key, key) == 0) {
+      entry->value = value;
+      return true;
+    }
+    if (entry->next == NULL)
+      break;
+    entry = entry->next;
+  }
+  entry->next = (hashmap_entry_t *)malloc(sizeof(hashmap_entry_t));
+  *entry->next = (hashmap_entry_t){ .key = __strdup(key), .hash = hash, .value = value, .next = NULL };
+  return true;
+}
+
+void *
+hashmap_get(hashmap_t *map, char *key)
+{
+  uint32_t hash = u32_fnv1a_hash(key);
+  hashmap_entry_t *entry = &map->entries[hash & (map->capacity - 1)];
+  while (entry != NULL) {
+    if (entry->hash == hash && strcmp(entry->key, key) == 0) {
+      return entry->value;
+    }
+    entry = entry->next;
+  }
+  return NULL;
+}
+
+void
+hashmap_destroy(hashmap_t *map)
+{
+  for (size_t i = 0; i < map->capacity; ++i) {
+    hashmap_entry_t *entry = &map->entries[i];
+    while (entry != NULL) {
+      if (entry->key != NULL)
+        free(entry->key);
+      entry = entry->next;
+    }
+  }
+  free(map->entries);
+  free(map);
+}
+
+static char *
+__strdup(const char *s)
+{
+  size_t slen = strlen(s);
+  char *result = malloc(slen + 1);
+  if (result == NULL) {
+    return NULL;
+  }
+
+  memcpy(result, s, slen + 1);
+  return result;
+}
diff --git a/src/hashmap.h b/src/hashmap.h
new file mode 100644
index 0000000..6256548
--- /dev/null
+++ b/src/hashmap.h
@@ -0,0 +1,75 @@
+/*
+ * Copyright (C) 2023 Johnny Richard
+ *
+ * This program is free software: you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation, either version 3 of the License, or
+ * (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program.  If not, see <https://www.gnu.org/licenses/>.
+ */
+#ifndef HASHMAP_H
+#define HASHMAP_H
+
+#include <stdbool.h>
+#include <stdint.h>
+#include <string.h>
+
+#define HASHMAP_INITIAL_CAPACITY 32
+
+#define U32_FNV1A_PRIME 0x01000193
+#define U32_FNV1A_OFFSET_BASIS 0x811c9dc5
+
+typedef struct hashmap_t hashmap_t;
+typedef struct hashmap_bucket_t hashmap_bucket_t;
+typedef struct hashmap_entry_t hashmap_entry_t;
+
+typedef struct hashmap_t
+{
+  hashmap_entry_t *entries;
+  uint32_t capacity;
+} hashmap_t;
+
+typedef struct hashmap_entry_t
+{
+  char *key;
+  void *value;
+  uint32_t hash;
+  hashmap_entry_t *next;
+} hashmap_entry_t;
+
+/**
+ * @brief: Create a new hashmap with HASHMAP_INITIAL_CAPACITY
+ */
+hashmap_t *
+hashmap_new(void);
+
+/**
+ * @brief: Store a new entry into the hashmap.
+ *
+ * @param key:
+ *     The function copies the key in order to have his own key.
+ * @param value:
+ *     Value of the hashmap entry, the hashmap doesn't have the ownership.
+ * @return boolean
+ *     true if the object has been added to the hashmap otherwise false.
+ */
+bool
+hashmap_put(hashmap_t *map, char *key, void *value);
+
+void *
+hashmap_get(hashmap_t *map, char *key);
+
+/**
+ * @brief: Destroy the hashmap and entries. (including keys)
+ */
+void
+hashmap_destroy(hashmap_t *map);
+
+#endif /* HASHMAP_H */
diff --git a/test/Makefile b/test/Makefile
index 6bdec12..88a8481 100644
--- a/test/Makefile
+++ b/test/Makefile
@@ -31,6 +31,9 @@ vector_test: munit.o ../build/vector.o vector_test.o
 list_test: munit.o ../build/list.o list_test.o
 	$(CC) $? $(CFLAGS) -o $@
 
+hashmap_test: munit.o ../build/hashmap.o hashmap_test.o
+	$(CC) $? $(CFLAGS) -o $@
+
 lexer_test: munit.o ../build/string_view.o ../build/lexer.o lexer_test.o
 	$(CC) $? $(CFLAGS) -o $@
 
diff --git a/test/hashmap_test.c b/test/hashmap_test.c
new file mode 100644
index 0000000..df0101c
--- /dev/null
+++ b/test/hashmap_test.c
@@ -0,0 +1,65 @@
+/*
+ * Copyright (C) 2023 Johnny Richard
+ *
+ * This program is free software: you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation, either version 3 of the License, or
+ * (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program.  If not, see <https://www.gnu.org/licenses/>.
+ */
+#define MUNIT_ENABLE_ASSERT_ALIASES
+#include "hashmap.h"
+#include "munit.h"
+
+static MunitResult
+test_create_new(const MunitParameter params[], void *user_data_or_fixture)
+{
+  hashmap_t *map = hashmap_new();
+
+  assert_not_null(map);
+
+  hashmap_destroy(map);
+
+  return MUNIT_OK;
+}
+
+static MunitResult
+test_hashmap_put_and_get(const MunitParameter params[], void *user_data_or_fixture)
+{
+  hashmap_t *map = hashmap_new();
+
+  int n1 = 1;
+  int n2 = 2;
+
+  hashmap_put(map, "n1", (void *)&n1);
+  hashmap_put(map, "n2", (void *)&n2);
+
+  assert_int(*((int *)hashmap_get(map, "n1")), ==, n1);
+  assert_int(*((int *)hashmap_get(map, "n2")), ==, n2);
+
+  hashmap_destroy(map);
+
+  return MUNIT_OK;
+}
+
+static MunitTest tests[] = {
+  { "/test_create_new", test_create_new, NULL, NULL, MUNIT_TEST_OPTION_NONE, NULL },
+  { "/test_hashmap_put_and_get", test_hashmap_put_and_get, NULL, NULL, MUNIT_TEST_OPTION_NONE, NULL },
+  { NULL, NULL, NULL, NULL, MUNIT_TEST_OPTION_NONE, NULL }
+};
+
+static const MunitSuite suite = { "/hashmap", tests, NULL, 1, MUNIT_SUITE_OPTION_NONE };
+
+int
+main(int argc, char *argv[])
+{
+  return munit_suite_main(&suite, NULL, argc, argv);
+  return EXIT_SUCCESS;
+}