From 8f6dbe6d60a5425d7d21361d37c47d168a43d50a Mon Sep 17 00:00:00 2001 From: rsiddharth Date: Sun, 29 Sep 2019 19:08:09 -0400 Subject: nserver: Add hashmap.h --- nserver/src/hashmap.c | 251 ++++++++++++++++++++++++++++++++++++++++++++++++++ nserver/src/hashmap.h | 39 ++++++++ 2 files changed, 290 insertions(+) create mode 100644 nserver/src/hashmap.c create mode 100644 nserver/src/hashmap.h 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 +#include +#include +#include +#include + +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 +#include + +#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 -- cgit v1.2.3