use half as much memory + go marginally faster

1 files changed, 44 insertions, 55 deletions

diff --git a/map.c b/map.c
index 41ab5ed..99c2c6f 100644
--- a/map.c
+++ b/map.c
@@ -35,7 +35,7 @@ void map_init_capacity(
     map->load_limit = load_limit;
     map->size = 0;
     map->__num_buckets = capacity / load_limit + 1;
-    map->__buckets = calloc(map->__num_buckets, sizeof(struct __map_entry));
+    map->__buckets = calloc(map->__num_buckets, sizeof(struct __map_entry*));
 
     if (map->__buckets == NULL)
         crash("Out of memory allocating %ld hash buckets\n");
@@ -43,7 +43,7 @@ void map_init_capacity(
 
 void map_destroy(map_t* map) {
     for (size_t i = 0; i < map->__num_buckets; i++) {
-        struct __map_entry* node = map->__buckets[i].next;
+        struct __map_entry* node = map->__buckets[i];
         while (node != NULL) {
             struct __map_entry* next = node->next;
             free(node);
@@ -54,19 +54,20 @@ void map_destroy(map_t* map) {
     free(map->__buckets);
 }
 
-/* impl detail: next is never null if the value is populated (put will alloc) */
-static struct __map_entry* fetch_entry(const map_t* map, const void* key) {
-    struct __map_entry* entry =
+static struct __map_entry** fetch_entry(const map_t* map, const void* key) {
+    struct __map_entry** bucket =
         &map->__buckets[map->hash_func(key) % map->__num_buckets];
+    struct __map_entry* cur = *bucket;
+    if (cur == NULL || map->eq_func(key, cur->key)) return bucket;
 
-    while (entry->next != NULL && !map->eq_func(key, entry->key)) {
-        entry = entry->next;
+    while (cur->next != NULL && !map->eq_func(key, cur->next->key)) {
+        cur = cur->next;
     }
-    return entry;
+    return &cur->next;
 }
 
 bool map_contains(const map_t* map, const void *key) {
-    return fetch_entry(map, key)->next != NULL;
+    return *fetch_entry(map, key) != NULL;
 }
 
 void* map_get(const map_t* map, const void* key) {
@@ -74,40 +75,25 @@ void* map_get(const map_t* map, const void* key) {
 }
 
 void* map_get_or_default(const map_t* map, const void* key, void* default_val) {
-    struct __map_entry* entry = fetch_entry(map, key);
-    return entry->next == NULL ? default_val : entry->value;
-}
-
-static void insert_entry(map_t* map, struct __map_entry* entry) {
-    struct __map_entry* slot = fetch_entry(map, entry->key);
-    if (slot->next != NULL) crash("Hash map internals are corrupted\n");
-    slot->key = entry->key;
-    slot->value = entry->value;
-    slot->next = entry;
-    entry->next = NULL;
+    struct __map_entry* entry = *fetch_entry(map, key);
+    return entry == NULL ? default_val : entry->value;
 }
 
 static void rehash(map_t* map) {
     size_t old_num_buckets = map->__num_buckets;
-    struct __map_entry* old_buckets = map->__buckets;
+    struct __map_entry** old_buckets = map->__buckets;
     map->__num_buckets <<= 1;
-    map->__buckets = calloc(map->__num_buckets, sizeof(struct __map_entry));
+    map->__buckets = calloc(map->__num_buckets, sizeof(struct __map_entry*));
 
     for (size_t i = 0; i < old_num_buckets; i++) {
-        struct __map_entry* old_entry = &old_buckets[i];
-        if (old_entry->next == NULL) continue;
-
-        struct __map_entry* cur = old_entry->next;
-        while (cur->next != NULL) {
-            struct __map_entry* next = cur->next;
-            insert_entry(map, cur);
-            cur = next;
+        struct __map_entry* entry = old_buckets[i];
+        while (entry != NULL) {
+            struct __map_entry* next = entry->next;
+            entry->next = NULL;
+            struct __map_entry** slot = fetch_entry(map, entry->key);
+            *slot = entry;
+            entry = next;
         }
-
-        struct __map_entry* new_entry = fetch_entry(map, old_entry->key);
-        new_entry->key = old_entry->key;
-        new_entry->value = old_entry->value;
-        new_entry->next = cur;
     }
 
     free(old_buckets);
@@ -115,58 +101,61 @@ static void rehash(map_t* map) {
 
 static void insert_allocating(
     map_t* map,
-    struct __map_entry* entry,
+    struct __map_entry** slot,
     void* key,
     void* val
 ) {
     if ((double) ++map->size / map->__num_buckets > map->load_limit) {
         rehash(map);
-        entry = fetch_entry(map, key);
+        slot = fetch_entry(map, key);
     }
 
-    struct __map_entry* next = calloc(1, sizeof(struct __map_entry));
-    if (next == NULL)
+    struct __map_entry* entry = calloc(1, sizeof(struct __map_entry));
+    if (entry == NULL)
         crash("Out of memory allocating hash entry\n");
 
     entry->key = key;
     entry->value = val;
-    entry->next = next;
+    entry->next = NULL;
+    *slot = entry;
 }
 
 void* map_compute_if_absent(map_t* map, void* key, void* default_val) {
-    struct __map_entry* entry = fetch_entry(map, key);
-    if (entry->next != NULL) return entry->value;
+    struct __map_entry** slot = fetch_entry(map, key);
+    struct __map_entry* entry = *slot;
+    if (entry != NULL) return entry->value;
 
-    insert_allocating(map, entry, key, default_val);
+    insert_allocating(map, slot, key, default_val);
     return default_val;
 }
 
 void map_put(map_t* map, void* key, void* val) {
-    struct __map_entry* entry = fetch_entry(map, key);
-    if (entry->next != NULL) {
+    struct __map_entry** slot = fetch_entry(map, key);
+    struct __map_entry* entry = *slot;
+    if (entry != NULL) {
         entry->value = val;
         return;
     }
 
-    insert_allocating(map, entry, key, val);
+    insert_allocating(map, slot, key, val);
 }
 
 void* map_remove(map_t* map, const void* key) {
-    struct __map_entry* entry = fetch_entry(map, key);
-    if (entry->next == NULL) return NULL;
+    struct __map_entry** slot = fetch_entry(map, key);
+    struct __map_entry* entry = *slot;
+    if (entry == NULL) return NULL;
 
     map->size--;
+    *slot = entry->next;
     void* rv = entry->value;
-    struct __map_entry* steal = entry->next;
-    *entry = *steal;
-    free(steal);
+    free(entry);
     return rv;
 }
 
 void map_foreach_readonly(map_t* map, foreach_func_t foreach_func, void* data) {
     for (size_t i = 0; i < map->size; i++) {
-        struct __map_entry* entry = &map->__buckets[i];
-        while (entry->next != NULL) {
+        struct __map_entry* entry = map->__buckets[i];
+        while (entry != NULL) {
             foreach_func(entry->key, entry->value, data);
             entry = entry->next;
         }
@@ -183,8 +172,8 @@ void map_foreach_readwrite(
     size_t idx = 0;
 
     for (size_t i = 0; i < map->__num_buckets; i++) {
-        struct __map_entry* entry = &map->__buckets[i];
-        while (entry->next != NULL) {
+        struct __map_entry* entry = map->__buckets[i];
+        while (entry != NULL) {
             keys[idx] = entry->key;
             vals[idx++] = entry->value;
             entry = entry->next;