From 5df7f92e715ba764ee57f65d78e73111492bb64c Mon Sep 17 00:00:00 2001 From: dec05eba Date: Wed, 20 Mar 2019 18:53:47 +0100 Subject: Add pub keyword, more import stuff, optimize hash map Hash map now stores hash of keys to reduce the number of hash operations. Positive: faster insert/get. Negative: more space required (to store usize hash). --- src/std/hash_map.c | 58 ++++++++++++++++++++++++++++++++++++------------------ 1 file changed, 39 insertions(+), 19 deletions(-) (limited to 'src/std') diff --git a/src/std/hash_map.c b/src/std/hash_map.c index 61030da..ab580ba 100644 --- a/src/std/hash_map.c +++ b/src/std/hash_map.c @@ -9,6 +9,13 @@ Basic hash map implementation. TODO: Improve performance #define HASH_MAP_INITIAL_SIZE 8 +/* Structure: +HashMapBucketNode *next; +usize hash; +u32 key_size; +u8[..] key; +u8[..] value; +*/ typedef struct HashMapBucketNode HashMapBucketNode; typedef struct { @@ -22,37 +29,47 @@ static void bucket_node_set_next(HashMapBucketNode *self, HashMapBucketNode *nex static HashMapBucketNode* bucket_node_get_next(HashMapBucketNode *self) { HashMapBucketNode *next; - am_memcpy(&next, self, sizeof(HashMapBucketNode*)); + am_memcpy(&next, self, sizeof(next)); return next; } +static void bucket_node_set_hash(HashMapBucketNode *self, usize hash) { + am_memcpy((char*)self + sizeof(HashMapBucketNode*), &hash, sizeof(hash)); +} + +static usize bucket_node_get_hash(HashMapBucketNode *self) { + usize hash; + am_memcpy(&hash, (char*)self + sizeof(HashMapBucketNode*), sizeof(hash)); + return hash; +} + static void bucket_node_set_key(HashMapBucketNode *self, BufferView key) { u32 key_size; key_size = (u32)key.size; - am_memcpy((char*)self + sizeof(HashMapBucketNode*), &key_size, sizeof(u32)); - am_memcpy((char*)self + sizeof(HashMapBucketNode*) + sizeof(u32), key.data, key_size); + am_memcpy((char*)self + sizeof(HashMapBucketNode*) + sizeof(usize), &key_size, sizeof(u32)); + am_memcpy((char*)self + sizeof(HashMapBucketNode*) + sizeof(usize) + sizeof(u32), key.data, key_size); } static BufferView bucket_node_get_key(HashMapBucketNode *self) { BufferView key; u32 key_size; - am_memcpy(&key_size, (char*)self + sizeof(HashMapBucketNode*), sizeof(u32)); + am_memcpy(&key_size, (char*)self + sizeof(HashMapBucketNode*) + sizeof(usize), sizeof(u32)); key.size = key_size; - key.data = (char*)self + sizeof(HashMapBucketNode*) + sizeof(u32); + key.data = (char*)self + sizeof(HashMapBucketNode*) + sizeof(usize) + sizeof(u32); return key; } static void bucket_node_set_value(HashMapBucketNode *self, void *value, usize value_type_size) { u32 key_size; - am_memcpy(&key_size, (char*)self + sizeof(HashMapBucketNode*), sizeof(key_size)); - am_memcpy((char*)self + sizeof(HashMapBucketNode*) + sizeof(u32) + key_size, value, value_type_size); + am_memcpy(&key_size, (char*)self + sizeof(HashMapBucketNode*) + sizeof(usize), sizeof(key_size)); + am_memcpy((char*)self + sizeof(HashMapBucketNode*) + sizeof(usize) + sizeof(u32) + key_size, value, value_type_size); } static void* bucket_node_get_value(HashMapBucketNode *self) { u32 key_size; void *value; - am_memcpy(&key_size, (char*)self + sizeof(HashMapBucketNode*), sizeof(key_size)); - value = (char*)self + sizeof(HashMapBucketNode*) + sizeof(u32) + key_size; + am_memcpy(&key_size, (char*)self + sizeof(HashMapBucketNode*) + sizeof(usize), sizeof(key_size)); + value = (char*)self + sizeof(HashMapBucketNode*) + sizeof(usize) + sizeof(u32) + key_size; return value; } @@ -72,12 +89,13 @@ int hash_map_init(HashMap *self, ScopedAllocator *allocator, usize value_type_si return 0; } -static CHECK_RESULT int hash_map_bucket_add(HashMap *self, HashMapBucket *bucket, BufferView key, void *value) { +static CHECK_RESULT int hash_map_bucket_add(HashMap *self, HashMapBucket *bucket, BufferView key, void *value, usize hash) { HashMapBucketNode *new_bucket_node; return_if_error(scoped_allocator_alloc(self->allocator, - sizeof(HashMapBucketNode*) + sizeof(u32) + key.size + self->value_type_size, + sizeof(HashMapBucketNode*) + sizeof(hash) + sizeof(u32) + key.size + self->value_type_size, (void**)&new_bucket_node)); bucket_node_set_next(new_bucket_node, bucket->start); + bucket_node_set_hash(new_bucket_node, hash); bucket_node_set_key(new_bucket_node, key); bucket_node_set_value(new_bucket_node, value, self->value_type_size); bucket->start = new_bucket_node; @@ -102,11 +120,9 @@ static void hash_map_reorder_nodes(HashMap *self, usize end_index) { prev_bucket_node = NULL; bucket_node = bucket->start; while(bucket_node) { - BufferView bucket_key; usize bucket_index; - - bucket_key = bucket_node_get_key(bucket_node); - bucket_index = self->hash_func((const u8*)bucket_key.data, bucket_key.size) % bucket_size; + bucket_index = bucket_node_get_hash(bucket_node) % bucket_size; + if(bucket_index != index) { /* Add node to new bucket */ HashMapBucketNode *moved_node; @@ -145,6 +161,7 @@ static CHECK_RESULT int hash_map_increase_buckets(HashMap *self) { } int hash_map_insert(HashMap *self, BufferView key, void *value) { + usize hash; usize bucket_index; usize bucket_size; HashMapBucket *bucket; @@ -155,9 +172,10 @@ int hash_map_insert(HashMap *self, BufferView key, void *value) { bucket_size = buffer_get_size(&self->buckets, HashMapBucket); } - bucket_index = self->hash_func((const u8*)key.data, key.size) % bucket_size; + hash = self->hash_func((const u8*)key.data, key.size); + bucket_index = hash % bucket_size; bucket = ((HashMapBucket*)self->buckets.data) + bucket_index; - return_if_error(hash_map_bucket_add(self, bucket, key, value)); + return_if_error(hash_map_bucket_add(self, bucket, key, value, hash)); ++self->num_elements; return 0; } @@ -165,17 +183,19 @@ int hash_map_insert(HashMap *self, BufferView key, void *value) { bool hash_map_get(HashMap *self, BufferView key, void *value) { usize bucket_size; usize bucket_index; + usize hash; HashMapBucket *bucket; HashMapBucketNode *bucket_node; bucket_size = buffer_get_size(&self->buckets, HashMapBucket); - bucket_index = self->hash_func((const u8*)key.data, key.size) % bucket_size; + hash = self->hash_func((const u8*)key.data, key.size); + bucket_index = hash % bucket_size; bucket = ((HashMapBucket*)self->buckets.data) + bucket_index; for(bucket_node = bucket->start; bucket_node; bucket_node = bucket_node_get_next(bucket_node)) { BufferView bucket_key; bucket_key = bucket_node_get_key(bucket_node); - if(self->compare_func(&key, &bucket_key) == 0) { + if(hash == bucket_node_get_hash(bucket_node) && self->compare_func(&key, &bucket_key) == 0) { am_memcpy(value, bucket_node_get_value(bucket_node), self->value_type_size); return bool_true; } -- cgit v1.2.3