From 33a0828dbcbdbfbc7b3c6a41736403b8380df8ca Mon Sep 17 00:00:00 2001
From: dec05eba <dec05eba@protonmail.com>
Date: Thu, 7 Mar 2019 23:28:29 +0100
Subject: Fix hash map bug with reorder nodes

---
 src/std/hash_map.c | 29 ++++++++++++++++++++++-------
 tests/main.c       |  3 +++
 2 files changed, 25 insertions(+), 7 deletions(-)

diff --git a/src/std/hash_map.c b/src/std/hash_map.c
index 1ffca90..febb3fd 100644
--- a/src/std/hash_map.c
+++ b/src/std/hash_map.c
@@ -16,6 +16,7 @@ typedef struct {
 } HashMapBucket;
 
 static void bucket_node_set_next(HashMapBucketNode *self, HashMapBucketNode *next) {
+    assert(next != self);
     am_memcpy(self, &next, sizeof(next));
 }
 
@@ -83,7 +84,7 @@ static CHECK_RESULT int hash_map_bucket_add(HashMap *self, HashMapBucket *bucket
     return 0;
 }
 
-static void hash_map_reorder_buckets(HashMap *self, usize end_index) {
+static void hash_map_reorder_nodes(HashMap *self, usize end_index) {
     HashMapBucket *bucket;
     HashMapBucket *bucket_end;
     usize bucket_size;
@@ -97,29 +98,43 @@ static void hash_map_reorder_buckets(HashMap *self, usize end_index) {
     for(; bucket != bucket_end; ++bucket, ++index) {
         HashMapBucketNode *prev_bucket_node;
         HashMapBucketNode *bucket_node;
+
         prev_bucket_node = NULL;
-        for(bucket_node = bucket->start; bucket_node; bucket_node_get_next(bucket_node)) {
+        bucket_node = bucket->start;
+        while(bucket_node) {
             BufferView bucket_key;
             usize bucket_index;
 
             /* Node between current and previous has been removed, chain previous and current */
             if(prev_bucket_node && !bucket_node_get_next(prev_bucket_node))
                 bucket_node_set_next(prev_bucket_node, bucket_node);
+            
+            if(!prev_bucket_node)
+                bucket->start = bucket_node;
 
             bucket_key = bucket_node_get_key(bucket_node);
             bucket_index = self->hash_func((const u8*)bucket_key.data, bucket_key.size) % bucket_size;
             if(bucket_index != index) {
                 /* Add node to new bucket */
+                HashMapBucketNode *moved_node;
                 HashMapBucket *new_bucket;
                 new_bucket = ((HashMapBucket*)self->buckets.data) + bucket_index;
-                bucket_node_set_next(bucket_node, new_bucket->start);
-                new_bucket->start = bucket_node;
+                moved_node = bucket_node;
+                bucket_node = bucket_node_get_next(bucket_node);
+                bucket_node_set_next(moved_node, new_bucket->start);
+                new_bucket->start = moved_node;
                 /* Mark bucket node to be removed from previous bucket */
-                bucket_node_set_next(prev_bucket_node, NULL);
+                if(prev_bucket_node)
+                    bucket_node_set_next(prev_bucket_node, NULL);
             } else {
                 prev_bucket_node = bucket_node;
+                bucket_node = bucket_node_get_next(bucket_node);
             }
         }
+
+        /* All nodes removed in bucket */
+        if(!prev_bucket_node)
+            bucket->start = NULL;
     }
 }
 
@@ -129,8 +144,8 @@ static CHECK_RESULT int hash_map_increase_buckets(HashMap *self) {
     prev_size = buffer_get_size(&self->buckets, HashMapBucket);
     bytes_to_append = prev_size * 1.5;
     return_if_error(buffer_append(&self->buckets, NULL, bytes_to_append));
-    am_memset(self->buckets.data + prev_size, 0, prev_size + bytes_to_append);
-    hash_map_reorder_buckets(self, prev_size);
+    am_memset(((HashMapBucket*)self->buckets.data) + prev_size, 0, bytes_to_append);
+    hash_map_reorder_nodes(self, prev_size);
     return 0;
 }
 
diff --git a/tests/main.c b/tests/main.c
index 881866e..11719a8 100644
--- a/tests/main.c
+++ b/tests/main.c
@@ -18,12 +18,15 @@ static CHECK_RESULT int test_hash_map() {
     HashMap hash_map;
     int value;
     bool has_key;
+    unsigned char i;
 
     return_if_error(scoped_allocator_init(&scoped_allocator));
     cleanup_if_error(hash_map_init(&hash_map, &scoped_allocator, sizeof(int), hash_compare_string, amal_hash_string));
 
     value = 34;
     return_if_error(hash_map_insert(&hash_map, create_buffer_view("hello", 5), &value));
+    for(i = 0; i < 128; ++i)
+        return_if_error(hash_map_insert(&hash_map, create_buffer_view((const char*)&i, 1), &value));
     return_if_error(hash_map_insert(&hash_map, create_buffer_view("hellp", 5), &value));
     has_key = hash_map_get(&hash_map, create_buffer_view("hello", 5), &value);
     if(!has_key) {
-- 
cgit v1.2.3