From 5ead0694ba2817057804848fb9b913eb83ef81e8 Mon Sep 17 00:00:00 2001
From: dec05eba <dec05eba@protonmail.com>
Date: Tue, 21 Jan 2020 01:24:04 +0100
Subject: Optimize hash map reorder (dont reorder new buckets)

---
 src/std/hash_map.c | 94 +++++++++++++++++++++++++++++-------------------------
 1 file changed, 50 insertions(+), 44 deletions(-)

diff --git a/src/std/hash_map.c b/src/std/hash_map.c
index 698c76f..1270514 100644
--- a/src/std/hash_map.c
+++ b/src/std/hash_map.c
@@ -66,14 +66,58 @@ static int tsl_hash_map_append_bucket(TslHashMapNode **head_node, uint64_t hash,
 }
 
 static size_t tsl_hash_map_get_index(TslHashMap *self, uint64_t hash) {
-    /* >> 3 = 8 = sizeof(TslHashMapNode*) */
+    /* >>3 = 8 = sizeof(TslHashMapNode*) */
     return hash & ((self->buckets_capacity >> 3) - 1);
 }
 
+static void tsl_hash_map_reorder_nodes(TslHashMap *self, size_t old_capacity) {
+    TslHashMapNode **bucket = (TslHashMapNode**)self->buckets_data;
+    TslHashMapNode **bucket_end = (TslHashMapNode**)((char*)self->buckets_data + old_capacity);
+    size_t bucket_index = 0;
+    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;
+            size_t size;
+            uint8_t *data;
+            size_t index;
+            hash_map_node_get(node, &hash, &key, &size, &data);
+
+            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;
+                if(*new_bucket) {
+                    node->next = (*new_bucket)->next;
+                    (*new_bucket)->next = node;
+                } else {
+                    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;
+    }
+}
+
 static int tsl_hash_map_ensure_bucket_capacity_for_one_new_item(TslHashMap *self) {
     void *new_ptr;
     size_t new_capacity = self->buckets_capacity;
     size_t new_size = self->buckets_size + sizeof(TslHashMapNode*);
+    size_t old_capacity = self->buckets_capacity;
     self->buckets_size = new_size;
     if(new_size <= self->buckets_capacity)
         return 1;
@@ -92,58 +136,20 @@ static int tsl_hash_map_ensure_bucket_capacity_for_one_new_item(TslHashMap *self
     }
 
     self->buckets_data = new_ptr;
+    self->buckets_capacity = new_capacity;
     {
-        TslHashMapNode **bucket = (TslHashMapNode**)((char*)self->buckets_data + self->buckets_capacity);
+        TslHashMapNode **bucket = (TslHashMapNode**)((char*)self->buckets_data + old_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;
-        TslHashMapNode **bucket_end = (TslHashMapNode**)((char*)self->buckets_data + self->buckets_capacity);
-        size_t bucket_index = 0;
-        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;
-                size_t size;
-                uint8_t *data;
-                size_t index;
-                hash_map_node_get(node, &hash, &key, &size, &data);
-
-                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;
-                    if(*new_bucket) {
-                        node->next = (*new_bucket)->next;
-                        (*new_bucket)->next = node;
-                    } else {
-                        node->next = NULL;
-                        *new_bucket = node;
-                    }
-                } else {
-                    all_nodes_moved = 0;
-                }
 
-                prev_node = node;
-                node = node->next;
-            }
-
-            if(all_nodes_moved)
-                *bucket = NULL;
+    if(old_capacity == 0)
+        return 1;
 
-            ++bucket_index;
-            ++bucket;
-        }
-    }
+    tsl_hash_map_reorder_nodes(self, old_capacity);
     return 1;
 }
 
-- 
cgit v1.2.3