aboutsummaryrefslogtreecommitdiff
path: root/src/hashmap.c
diff options
context:
space:
mode:
Diffstat (limited to 'src/hashmap.c')
-rw-r--r--src/hashmap.c171
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
+}
generated by cgit v1.2.3 (git 2.25.1) at 2024-04-29 05:05:10 +0000