1 files changed, 32 insertions, 16 deletions

diff --git a/src/std/hash_map.c b/src/std/hash_map.c
index a0d656d..698c76f 100644
--- a/src/std/hash_map.c
+++ b/src/std/hash_map.c
@@ -8,7 +8,6 @@ void tsl_hash_map_init(TslHashMap *self) {
     self->buckets_data = NULL;
     self->buckets_size = 0;
     self->buckets_capacity = 0;
-    self->num_items = 0;
 }
 
 void tsl_hash_map_deinit(TslHashMap *self) {
@@ -48,7 +47,6 @@ static int tsl_hash_map_append_bucket(TslHashMapNode **head_node, uint64_t hash,
         fprintf(stderr, "Error: hash map append failed. Reason: out of memory\n");
         return 0;
     }
-    hash_map_node_init(next_node);
 
     memcpy(node_data, &hash, sizeof(hash));
     memcpy(node_data + sizeof(hash), &key->size, sizeof(key->size));
@@ -56,25 +54,35 @@ static int tsl_hash_map_append_bucket(TslHashMapNode **head_node, uint64_t hash,
     memcpy(node_data + sizeof(hash) + sizeof(key->size) + key->size, &size, sizeof(size));
     memcpy(node_data + sizeof(hash) + sizeof(key->size) + key->size + sizeof(size), data, size);
 
+    next_node->data = node_data;
     if(*head_node) {
-        (*head_node)->data = node_data;
+        next_node->next = (*head_node)->next;
         (*head_node)->next = next_node;
+    } else {
+        next_node->next = NULL;
+        *head_node = next_node;
     }
-    *head_node = next_node;
     return 1;
 }
 
-static int tsl_hash_map_ensure_bucket_capacity(TslHashMap *self, size_t new_size) {
-    size_t new_capacity = self->num_items;
+static size_t tsl_hash_map_get_index(TslHashMap *self, uint64_t hash) {
+    /* >> 3 = 8 = sizeof(TslHashMapNode*) */
+    return hash & ((self->buckets_capacity >> 3) - 1);
+}
+
+static int tsl_hash_map_ensure_bucket_capacity_for_one_new_item(TslHashMap *self) {
     void *new_ptr;
-    if(new_size <= self->num_items)
+    size_t new_capacity = self->buckets_capacity;
+    size_t new_size = self->buckets_size + sizeof(TslHashMapNode*);
+    self->buckets_size = new_size;
+    if(new_size <= self->buckets_capacity)
         return 1;
 
     if(new_capacity == 0)
-        new_capacity = 8;
+        new_capacity = sizeof(TslHashMapNode*) << 3;
 
     while(new_capacity < new_size) {
-        new_capacity *= 2;
+        new_capacity <<= 1;
     }
 
     new_ptr = realloc(self->buckets_data, new_capacity);
@@ -84,15 +92,15 @@ static int tsl_hash_map_ensure_bucket_capacity(TslHashMap *self, size_t new_size
     }
 
     self->buckets_data = new_ptr;
-    self->buckets_capacity = new_capacity;
     {
-        TslHashMapNode **bucket = (TslHashMapNode**)((char*)self->buckets_data + self->buckets_size);
-        TslHashMapNode **bucket_end = (TslHashMapNode**)((char*)self->buckets_data + self->buckets_capacity);
+        TslHashMapNode **bucket = (TslHashMapNode**)((char*)self->buckets_data + self->buckets_capacity);
+        TslHashMapNode **bucket_end = (TslHashMapNode**)((char*)self->buckets_data + new_capacity);
         while(bucket != bucket_end) {
             *bucket = NULL;
             ++bucket;
         }
     }
+    self->buckets_capacity = new_capacity;
 
     {
         TslHashMapNode **bucket = (TslHashMapNode**)self->buckets_data;
@@ -101,6 +109,7 @@ static int tsl_hash_map_ensure_bucket_capacity(TslHashMap *self, size_t new_size
         while(bucket != bucket_end) {
             TslHashMapNode *node = *bucket;
             TslHashMapNode *prev_node = node; /* Set to node for optimization reason, where prev_node->next = node->next; which becomes no-op */
+            int all_nodes_moved = 1;
             while(node) {
                 uint64_t hash;
                 TslStringView key;
@@ -109,7 +118,7 @@ static int tsl_hash_map_ensure_bucket_capacity(TslHashMap *self, size_t new_size
                 size_t index;
                 hash_map_node_get(node, &hash, &key, &size, &data);
 
-                index = hash & (self->buckets_capacity - 1);
+                index = tsl_hash_map_get_index(self, hash);
                 if(index != bucket_index) {
                     TslHashMapNode **new_bucket = (TslHashMapNode**)self->buckets_data + index;
                     prev_node->next = node->next;
@@ -120,11 +129,17 @@ static int tsl_hash_map_ensure_bucket_capacity(TslHashMap *self, size_t new_size
                         node->next = NULL;
                         *new_bucket = node;
                     }
+                } else {
+                    all_nodes_moved = 0;
                 }
 
                 prev_node = node;
                 node = node->next;
             }
+
+            if(all_nodes_moved)
+                *bucket = NULL;
+
             ++bucket_index;
             ++bucket;
         }
@@ -137,10 +152,11 @@ int tsl_hash_map_insert(TslHashMap *self, const TslStringView *key, const void *
     size_t index;
     TslHashMapNode **bucket;
     assert(!tsl_hash_map_get(self, key, hash_func));
-    if(!tsl_hash_map_ensure_bucket_capacity(self, self->buckets_size + size))
+    assert(size > 0);
+    if(!tsl_hash_map_ensure_bucket_capacity_for_one_new_item(self))
         return 0;
 
-    index = hash & (self->buckets_capacity - 1);
+    index = tsl_hash_map_get_index(self, hash);
     bucket = (TslHashMapNode**)self->buckets_data + index;
     return tsl_hash_map_append_bucket(bucket, hash, key, size, data);
 }
@@ -153,7 +169,7 @@ void* tsl_hash_map_get(TslHashMap *self, const TslStringView *key, TslHashFunc h
         return NULL;
 
     hash = hash_func(key->data, key->size);
-    index = hash & (self->buckets_capacity - 1);
+    index = tsl_hash_map_get_index(self, hash);
     node = *((TslHashMapNode**)self->buckets_data + index);
     while(node) {
         uint64_t node_hash;