diff options
Diffstat (limited to 'src/std')
| -rw-r--r-- | src/std/buffer.c | 2 | ||||
| -rw-r--r-- | src/std/hash_map.c | 48 |
2 files changed, 33 insertions, 17 deletions
diff --git a/src/std/buffer.c b/src/std/buffer.c index 42b1a0f..e311c8f 100644 --- a/src/std/buffer.c +++ b/src/std/buffer.c @@ -21,7 +21,7 @@ static int tsl_buffer_ensure_capacity(TslBuffer *self, size_t new_size) { if(self->capacity != 0) { size_t new_capacity = self->capacity; while(new_capacity < new_size) { - new_capacity *= 2; + new_capacity <<= 1; } new_size = new_capacity; } 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; |