nserver: Add hashmap.h

2 files changed, 290 insertions, 0 deletions

diff --git a/nserver/src/hashmap.c b/nserver/src/hashmap.c
new file mode 100644
index 0000000..71d20ba
--- /dev/null
+++ b/nserver/src/hashmap.c
@@ -0,0 +1,251 @@
+#undef NDEBUG
+#include <stdint.h>
+#include <darray_algos.h>
+#include <hashmap.h>
+#include <dbg.h>
+#include <bstrlib.h>
+
+static int default_compare(void *a, void *b)
+{
+    return bstrcmp((bstring) a, (bstring) b);
+}
+
+/**
+ * Simple Bob Jenkin's hash algorithm taken from the wikipedia
+ * description.
+ */
+static uint32_t default_hash(void *a)
+{
+    size_t len = blength((bstring) a);
+    char *key = bdata((bstring) a);
+    uint32_t hash = 0;
+    uint32_t i = 0;
+
+    for (hash = i = 0; i < len; ++i) {
+        hash += key[i];
+        hash += (hash << 10);
+        hash ^= (hash >> 6);
+    }
+
+    hash += (hash << 3);
+    hash ^= (hash >> 11);
+    hash += (hash << 15);
+
+    return hash;
+}
+
+
+Hashmap *Hashmap_create(Hashmap_compare compare, Hashmap_hash hash)
+{
+    Hashmap *map = calloc(1, sizeof(Hashmap));
+    check_mem(map);
+
+    map->compare = compare == NULL ? default_compare : compare;
+    map->hash = hash == NULL ? default_hash : hash;
+    map->salt = rand() >> 16;
+    map->buckets = DArray_create(
+                                 sizeof(DArray *), DEFAULT_NUMBER_OF_BUCKETS);
+    map->buckets->end = map->buckets->max; // fake out expanding it.
+    check_mem(map->buckets);
+
+    return map;
+
+ error:
+    if (map) {
+        Hashmap_destroy(map);
+    }
+
+    return NULL;
+}
+
+void Hashmap_destroy(Hashmap *map)
+{
+    int i = 0;
+    int j = 0;
+
+    if (map) {
+        if (map->buckets) {
+            for (i = 0; i < DArray_count(map->buckets); i++) {
+                DArray *bucket = DArray_get(map->buckets, i);
+                if (bucket) {
+                    for (j = 0; j < DArray_count(bucket); j++) {
+                        free(DArray_get(bucket, j));
+                    }
+                    DArray_destroy(bucket);
+                }
+            }
+            DArray_destroy(map->buckets);
+        }
+
+        free(map);
+    }
+}
+
+static inline HashmapNode *Hashmap_node_create(int hash, void *key,
+                                               void *data)
+{
+    HashmapNode *node = calloc(1, sizeof(HashmapNode));
+    check_mem(node);
+
+    node->key = key;
+    node->data = data;
+    node->hash = hash;
+
+    return node;
+
+ error:
+    return NULL;
+}
+
+static inline DArray *Hashmap_find_bucket(Hashmap *map, void *key,
+                                          int create,
+                                          uint32_t *hash_out)
+{
+    uint32_t hash = map->hash(key) + map->salt;
+    int bucket_n = hash % DEFAULT_NUMBER_OF_BUCKETS;
+    check(bucket_n >= 0, "Invalid bucket found %d", bucket_n);
+    // store it for the return so the caller can use it
+    *hash_out = hash;
+
+    DArray *bucket = DArray_get(map->buckets, bucket_n);
+
+    if (!bucket && create) {
+        // new bucket, set it up
+        bucket = DArray_create(
+                               sizeof(void *), DEFAULT_NUMBER_OF_BUCKETS);
+        check_mem(bucket);
+        DArray_set(map->buckets, bucket_n, bucket);
+    }
+
+    return bucket;
+
+ error:
+    return NULL;
+}
+
+int Hashmap_delete_bucket(Hashmap *map, uint32_t hash)
+{
+    int bucket_n = hash % DEFAULT_NUMBER_OF_BUCKETS;
+    check(bucket_n >= 0, "Invalid bucket found %d", bucket_n);
+
+    // Get bucket.
+    DArray *bucket = DArray_get(map->buckets, bucket_n);
+    if(bucket) {
+        // Remove bucket.
+        DArray_clear_destroy(bucket);
+        DArray_remove(map->buckets, bucket_n);
+    }
+
+    return 0;
+ error:
+    return -1;
+}
+
+int Hashmap_set(Hashmap *map, void *key, void *data)
+{
+    uint32_t hash = 0;
+    DArray *bucket = Hashmap_find_bucket(map, key, 1, &hash);
+    check(bucket, "Error can't create bucket");
+
+    HashmapNode *node = Hashmap_node_create(hash, key, data);
+    check_mem(node);
+
+    DArray_push(bucket, node);
+
+    // Sort the bucket.
+    int rc = DArray_heapsort(bucket, (DArray_compare) map->compare);
+    check(rc == 0, "Error sorting bucket");
+
+    return 0;
+
+ error:
+    return -1;
+}
+
+static inline int Hashmap_get_node(Hashmap *map, uint32_t hash,
+                                   DArray *bucket, void *key)
+{
+    int i = 0;
+
+    for (i = 0; i < DArray_end(bucket); i++) {
+        debug("TRY: %d", i);
+        HashmapNode *node = DArray_get(bucket, i);
+        if (node->hash == hash && map->compare(node->key, key) == 0) {
+            return i;
+        }
+    }
+
+    return -1;
+}
+
+void *Hashmap_get(Hashmap *map, void *key)
+{
+    uint32_t hash = 0;
+    DArray *bucket = Hashmap_find_bucket(map, key, 0, &hash);
+    if (!bucket) return NULL;
+
+    int i = Hashmap_get_node(map, hash, bucket, key);
+    if (i == -1) return NULL;
+
+    HashmapNode *node = DArray_get(bucket, i);
+    check(node != NULL,
+          "Failed to get node from bucket when it should exist.");
+
+    return node->data;
+
+ error:
+    return NULL;
+}
+
+
+int Hashmap_traverse(Hashmap *map, Hashmap_traverse_cb traverse_cb)
+{
+    int i = 0;
+    int j = 0;
+    int rc = 0;
+
+    for (i = 0; i < DArray_count(map->buckets); i++) {
+        DArray *bucket = DArray_get(map->buckets, i);
+        if (bucket) {
+            for (j = 0; j < DArray_count(bucket); j++) {
+                HashmapNode *node = DArray_get(bucket, j);
+                rc = traverse_cb(node);
+                if (rc != 0)
+                    return rc;
+            }
+        }
+    }
+
+    return 0;
+}
+
+void *Hashmap_delete(Hashmap *map, void *key)
+{
+    uint32_t hash = 0;
+    DArray *bucket = Hashmap_find_bucket(map, key, 0, &hash);
+    if (!bucket)
+        return NULL;
+
+    int i = Hashmap_get_node(map, hash, bucket, key);
+    if (i == -1)
+        return NULL;
+
+    HashmapNode *node = DArray_get(bucket, i);
+    void *data = node->data;
+    free(node);
+
+    HashmapNode *ending = DArray_pop(bucket);
+
+    if (ending != node) {
+        // alright looks like it's not the last one, swap it.
+        DArray_set(bucket, i, ending);
+    } else {
+        // alright looks like it's the last one, destroy bucket.
+        check(Hashmap_delete_bucket(map, hash) == 0,
+              "Error destroy bucket");
+    }
+
+    return data;
+ error:
+    return NULL;
+}
diff --git a/nserver/src/hashmap.h b/nserver/src/hashmap.h
new file mode 100644
index 0000000..4717391
--- /dev/null
+++ b/nserver/src/hashmap.h
@@ -0,0 +1,39 @@
+#ifndef _lcthw_Hashmap_h
+#define _lcthw_Hashmap_h
+
+#include <stdint.h>
+#include <darray.h>
+
+#define DEFAULT_NUMBER_OF_BUCKETS 100
+
+typedef int (*Hashmap_compare) (void *a, void *b);
+typedef uint32_t(*Hashmap_hash) (void *key);
+
+typedef struct Hashmap {
+    DArray *buckets;
+    Hashmap_compare compare;
+    Hashmap_hash hash;
+    int salt;
+} Hashmap;
+
+
+typedef struct HashmapNode {
+    void *key;
+    void *data;
+    uint32_t hash;
+} HashmapNode;
+
+typedef int (*Hashmap_traverse_cb) (HashmapNode *node);
+
+Hashmap *Hashmap_create(Hashmap_compare, Hashmap_hash);
+void Hashmap_destroy(Hashmap *map);
+
+int Hashmap_set(Hashmap *map, void *key, void *data);
+void *Hashmap_get(Hashmap *map, void *key);
+
+int Hashmap_traverse(Hashmap *map, Hashmap_traverse_cb travers_cb);
+
+void *Hashmap_delete(Hashmap *map, void *key);
+
+uint32_t fnv_hash(void *a);
+#endif