aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--src/std/hash_map.c94
1 files 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;
}