From 27718f093689dbd3decd7021eaa97327f578c8f3 Mon Sep 17 00:00:00 2001 From: dec05eba Date: Thu, 7 Mar 2019 22:19:57 +0100 Subject: Add hash map --- src/std/hash_map.c | 191 +++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 191 insertions(+) create mode 100644 src/std/hash_map.c (limited to 'src/std/hash_map.c') diff --git a/src/std/hash_map.c b/src/std/hash_map.c new file mode 100644 index 0000000..1ffca90 --- /dev/null +++ b/src/std/hash_map.c @@ -0,0 +1,191 @@ +#include "../../include/std/hash_map.h" +#include "../../include/std/scoped_allocator.h" +#include "../../include/std/mem.h" +#include + +/* +Basic hash map implementation. TODO: Improve performance +*/ + +#define HASH_MAP_INITIAL_SIZE 16 + +typedef struct HashMapBucketNode HashMapBucketNode; + +typedef struct { + HashMapBucketNode *start; +} HashMapBucket; + +static void bucket_node_set_next(HashMapBucketNode *self, HashMapBucketNode *next) { + am_memcpy(self, &next, sizeof(next)); +} + +static HashMapBucketNode* bucket_node_get_next(HashMapBucketNode *self) { + HashMapBucketNode *next; + am_memcpy(&next, self, sizeof(HashMapBucketNode*)); + return next; +} + +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); +} + +static BufferView bucket_node_get_key(HashMapBucketNode *self) { + BufferView key; + u32 key_size; + am_memcpy(&key_size, (char*)self + sizeof(HashMapBucketNode*), sizeof(u32)); + key.size = key_size; + key.data = (char*)self + sizeof(HashMapBucketNode*) + sizeof(u32); + return key; +} + +static void bucket_node_set_value(HashMapBucketNode *self, void *value, usize 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, 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; + return value; +} + +int hash_map_init(HashMap *self, ScopedAllocator *allocator, usize type_size, + HashMapCompare compare_func, HashMapHash hash_func) { + assert(compare_func); + assert(hash_func); + self->allocator = allocator; + self->type_size = type_size; + self->num_elements = 0; + self->compare_func = compare_func; + self->hash_func = hash_func; + return_if_error(buffer_init(&self->buckets, self->allocator)); + assert(self->buckets.size == 0); + return_if_error(buffer_append(&self->buckets, NULL, sizeof(HashMapBucket) * HASH_MAP_INITIAL_SIZE)); + am_memset(self->buckets.data, 0, self->buckets.size); + return 0; +} + +static CHECK_RESULT int hash_map_bucket_add(HashMap *self, HashMapBucket *bucket, BufferView key, void *value) { + HashMapBucketNode *new_bucket_node; + return_if_error(scoped_allocator_alloc(self->allocator, + sizeof(HashMapBucketNode*) + sizeof(u32) + key.size + self->type_size, + (void**)&new_bucket_node)); + bucket_node_set_next(new_bucket_node, bucket->start); + bucket_node_set_key(new_bucket_node, key); + bucket_node_set_value(new_bucket_node, value, self->type_size); + bucket->start = new_bucket_node; + return 0; +} + +static void hash_map_reorder_buckets(HashMap *self, usize end_index) { + HashMapBucket *bucket; + HashMapBucket *bucket_end; + usize bucket_size; + usize index; + + bucket = (HashMapBucket*)self->buckets.data; + bucket_end = ((HashMapBucket*)self->buckets.data) + end_index; + bucket_size = buffer_get_size(&self->buckets, HashMapBucket); + index = 0; + + 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)) { + 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); + + 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 */ + 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; + /* Mark bucket node to be removed from previous bucket */ + bucket_node_set_next(prev_bucket_node, NULL); + } else { + prev_bucket_node = bucket_node; + } + } + } +} + +static CHECK_RESULT int hash_map_increase_buckets(HashMap *self) { + usize prev_size; + usize bytes_to_append; + 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); + return 0; +} + +int hash_map_insert(HashMap *self, BufferView key, void *value) { + usize bucket_index; + usize bucket_size; + HashMapBucket *bucket; + + bucket_size = buffer_get_size(&self->buckets, HashMapBucket); + if(self->num_elements == bucket_size) { + return_if_error(hash_map_increase_buckets(self)); + bucket_size = buffer_get_size(&self->buckets, HashMapBucket); + } + + bucket_index = self->hash_func((const u8*)key.data, key.size) % bucket_size; + bucket = ((HashMapBucket*)self->buckets.data) + bucket_index; + return_if_error(hash_map_bucket_add(self, bucket, key, value)); + ++self->num_elements; + return 0; +} + +bool hash_map_get(HashMap *self, BufferView key, void *value) { + usize bucket_size; + usize bucket_index; + 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; + + bucket = ((HashMapBucket*)self->buckets.data) + bucket_index; + for(bucket_node = bucket->start; bucket_node; bucket_node_get_next(bucket_node)) { + BufferView bucket_key; + 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_size; + if(self->compare_func(value, bucket_node_get_value(bucket_node)) == 0) + return bool_true; + } + + return bool_false; +} + +#define MIN(a, b) ((a) < (b) ? (a) : (b)) + +int hash_compare_string(const void *a, const void *b) { + const BufferView *lhs; + const BufferView *rhs; + int mem_diff; + + lhs = a; + rhs = b; + mem_diff = am_memcmp(lhs->data, rhs->data, MIN(lhs->size, rhs->size)); + if(mem_diff == 0) + return (int)lhs->size - (int)rhs->size; + else + return mem_diff; +} -- cgit v1.2.3