Hashmap improvements and include guards

Hashmap capacity can be set programmatically and it grows/shrinks in
size when the load increases/decreases to avoid collisions/save memory.

1 files changed, 139 insertions, 32 deletions

diff --git a/src/hashmap.c b/src/hashmap.c
index 16a950f..fa9a295 100644
--- a/src/hashmap.c
+++ b/src/hashmap.c
@@ -1,41 +1,130 @@
+#include "hashmap.h"
+
+#include <inttypes.h>
 #include <string.h>
 #include <stdlib.h>
 #include <err.h>
-#include "hashmap.h"
+
+#if SIZE_MAX == 0xFFFFFFFF
+/* If size_t is 32bit */
+static const size_t fnv_prime = 16777619u;
+static const size_t fnv_offsetb = 2166136261u;
+#elif SIZE_MAX == 0xFFFFFFFFFFFFFFFF
+/* If size_t is 64bit */
+static const size_t fnv_prime = 1099511628211u;
+static const size_t fnv_offsetb = 14695981039346656037u;
+#else
+/* If size_t is 128bit. Maybe this is overdoing it? */
+static const size_t fnv_prime = 309485009821345068724781371u;
+static const size_t fnv_offsetb = 144066263297769815596495629667062367629u;
+#endif
 
 struct node {
-    char *key;
+    const char *key;
     void *value;
     struct node *next;
 };
 
-unsigned long
-hash(char *str)
+/* FNV1a */
+static size_t
+hash(const char *str)
 {
-    unsigned long hash = 5381;
-    int c;
+	size_t hash = fnv_offsetb;
+	size_t i = 0;
+	while (str[i] != '\0') {
+		hash ^= str[i];
+		hash *= fnv_prime;
+		i++;
+	}
 
-    while ((c = *str++)) {
-        hash = ((hash << 5) + hash) + c; /* hash * 33 + c */
-    }
+	return hash;
+}
 
-    return hash;
+static void
+htable_realloc(struct hashmap *hm, struct node **oldbucks, size_t oldcap)
+{
+	for (size_t i = 0; i < oldcap; i++) {
+		struct node *node = oldbucks[i];
+		while (node) {
+			size_t pos = hash(node->key) % hm->cur_cap;
+			if (hm->buckets[pos]) {
+				struct node *newnext = hm->buckets[pos],
+							*newprev;
+				do {
+					newprev = newnext;
+					newnext = newprev->next;
+				} while (newnext);
+				newprev->next = node;
+			} else {
+				hm->buckets[pos] = node;
+			}
+			struct node *prev = node;
+			node = prev->next;
+			prev->next = NULL;
+		}
+	}
+	free(oldbucks);
 }
 
-/* allocate a new hashmap */
-struct hashmap *hashmap_new() {
-    struct hashmap *hm = malloc(sizeof *hm);
-    if (!hm) err(EXIT_FAILURE, "out of memory");
-    for (int i=0; i < HASHMAP_CAP; i++) {
-        hm->buckets[i] = NULL;
-    }
+static bool
+htable_grow(struct hashmap *hm)
+{
+	float load = (float)hm->size / (float)hm->cur_cap;
+	if (load <= HASHMAP_MAX_LOAD) return true;
 
-    return hm;
+	size_t oldcap = hm->cur_cap;
+	hm->cur_cap = hm->cur_cap * HASHMAP_GROW_RATE;
+	struct node **oldbucks = hm->buckets;
+	hm->buckets = calloc(hm->cur_cap, sizeof(**hm->buckets));
+	if (!hm->buckets) return false;
+
+	htable_realloc(hm, oldbucks, oldcap);
+
+	return true;
+}
+
+static bool
+htable_shrink(struct hashmap *hm)
+{
+	if (hm->cur_cap <= hm->init_cap) return true;
+
+	float load = (float)hm->size / (float)hm->cur_cap;
+	if (load >= HASHMAP_MIN_LOAD) return true;
+
+	size_t oldcap = hm->cur_cap;
+	hm->cur_cap = hm->cur_cap / HASHMAP_GROW_RATE;
+	struct node **oldbucks = hm->buckets;
+	hm->buckets = calloc(hm->cur_cap, sizeof(**hm->buckets));
+	if (!hm->buckets) return false;
+	htable_realloc(hm, oldbucks, oldcap);
+	return true;
+}
+
+struct hashmap *
+hashmap_new_with_cap(size_t cap)
+{
+	struct hashmap *hm = malloc(sizeof *hm);
+	hm->init_cap = cap;
+	hm->cur_cap = cap;
+	hm->size = 0;
+	if (hm == NULL) return NULL;
+	hm->buckets = calloc(cap, sizeof hm->buckets);
+	if (hm->buckets == NULL) {
+		free(hm);
+		return NULL;
+	}
+
+	return hm;
 }
 
-/* Inserts a key-value pair into the map. Returns NULL if map did not have key, old value if it did. */
-void *hashmap_insert(struct hashmap *hm, char *key, void *value) {
-    int pos = hash(key) % HASHMAP_CAP;
+/* 
+ * Inserts a key-value pair into the map. Returns NULL if map did not have key,
+ * old value if it did. 
+ */
+void *
+hashmap_insert(struct hashmap *hm, const char *key, void *value)
+{
+    int pos = hash(key) % hm->cur_cap;
     struct node *head = hm->buckets[pos];
     struct node *node = head;
     void *old_value;
@@ -54,12 +143,16 @@ void *hashmap_insert(struct hashmap *hm, char *key, void *value) {
     node->value = value;
     node->next = head;
     hm->buckets[pos] = node;
+    hm->size++;
+    htable_grow(hm);
     return NULL;
 }
 
 /* Returns a pointer to the value corresponding to the key. */
-void *hashmap_get(struct hashmap *hm, char *key) {
-    unsigned int pos = hash(key) % HASHMAP_CAP;
+void *
+hashmap_get(struct hashmap *hm, const char *key)
+{
+    size_t pos = hash(key) % hm->cur_cap;
     struct node *node = hm->buckets[pos];
     while (node != NULL) {
         if (strcmp(node->key, key) == 0) {
@@ -73,7 +166,9 @@ void *hashmap_get(struct hashmap *hm, char *key) {
 }
 
 /* Retrieve pointer to value by key, handles dot notation for nested hashmaps */
-void *hashmap_resolve(struct hashmap *hm, char *key) {
+void *
+hashmap_resolve(struct hashmap *hm, const char *key)
+{
     char tmp_key[64];
     int i = 0;
     int j = 0;
@@ -97,9 +192,14 @@ void *hashmap_resolve(struct hashmap *hm, char *key) {
     return hm;
 }
 
-/* Removes a key from the map, returning the value at the key if the key was previously in the map. */
-void *hashmap_remove(struct hashmap *hm, char *key) {
-    int pos = hash(key) % HASHMAP_CAP;
+/* 
+ * Removes a key from the map, returning the value at the key if the key was
+ * previously in the map.
+ */
+void *
+hashmap_remove(struct hashmap *hm, const char *key)
+{
+    int pos = hash(key) % hm->cur_cap;
     struct node *node = hm->buckets[pos];
     struct node *prev = NULL;
     void *old_value;
@@ -113,6 +213,8 @@ void *hashmap_remove(struct hashmap *hm, char *key) {
             }
             old_value = node->value;
             free(node);            
+    		hm->size--;
+    		htable_shrink(hm);
             return old_value;
         }
 
@@ -123,11 +225,13 @@ void *hashmap_remove(struct hashmap *hm, char *key) {
     return NULL;
 }
 
-void hashmap_walk(struct hashmap *hm, void (*fn)(void *value)) {
+void
+hashmap_walk(struct hashmap *hm, void (*fn)(void *value))
+{
     struct node *node;
     struct node *next;
 
-    for (int i=0; i < HASHMAP_CAP; i++) {
+    for (int i=0; i < hm->cur_cap; i++) {
         node = hm->buckets[i];
         while (node) {
             next = node->next;
@@ -138,11 +242,13 @@ void hashmap_walk(struct hashmap *hm, void (*fn)(void *value)) {
 }
 
 /* free hashmap related memory */
-void hashmap_free(struct hashmap *hm) {
+void
+hashmap_free(struct hashmap *hm)
+{
     struct node *node;
     struct node *next;
 
-    for (int i=0; i < HASHMAP_CAP; i++) {
+    for (int i=0; i < hm->cur_cap; i++) {
         node = hm->buckets[i];
         while (node) {
             next = node->next;
@@ -151,5 +257,6 @@ void hashmap_free(struct hashmap *hm) {
         }
     }
 
+	free(hm->buckets);
     free(hm);
-}
\ No newline at end of file
+}