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/ast.c | 30 ++++++++- src/compiler.c | 1 + src/main.c | 27 -------- src/std/buffer.c | 7 +- src/std/hash.c | 14 ++++ src/std/hash_map.c | 191 +++++++++++++++++++++++++++++++++++++++++++++++++++++ src/std/mem.c | 6 +- src/std/thread.c | 4 ++ src/tokenizer.c | 2 +- 9 files changed, 247 insertions(+), 35 deletions(-) delete mode 100644 src/main.c create mode 100644 src/std/hash.c create mode 100644 src/std/hash_map.c (limited to 'src') diff --git a/src/ast.c b/src/ast.c index 1db114a..c28b314 100644 --- a/src/ast.c +++ b/src/ast.c @@ -1,4 +1,8 @@ #include "../include/ast.h" +#include "../include/std/log.h" +#include + +static void ast_resolve(Ast *self); Ast ast_none() { Ast ast; @@ -51,6 +55,26 @@ int scope_init(Scope *self, ScopedAllocator *allocator) { } void scope_resolve(Scope *self) { - /* TODO: Implement. Also use longjmp to jump back to compiler on error */ - (void)self; -} \ No newline at end of file + Ast *ast; + Ast *ast_end; + ast = buffer_start(&self->ast_objects); + ast_end = buffer_end(&self->ast_objects); + for(; ast != ast_end; ++ast) { + ast_resolve(ast); + } +} + +static void lhs_resolve(LhsExpr *self) { + amal_log_debug("Lhs resolve var name: %.*s", self->var_name.size, self->var_name.data); +} + +void ast_resolve(Ast *self) { + switch(self->type) { + case AST_LHS: + lhs_resolve(self->value.lhs_expr); + break; + default: + assert(bool_false && "ast_resolve not implemented for type"); + break; + } +} diff --git a/src/compiler.c b/src/compiler.c index e44ba6a..bcb36c3 100644 --- a/src/compiler.c +++ b/src/compiler.c @@ -70,6 +70,7 @@ int amal_compiler_deinit(amal_compiler *self) { result = r; } + amal_mutex_deinit(&self->mutex); scoped_allocator_deinit(&self->allocator); scoped_allocator_deinit(&self->main_thread_allocator); return result; diff --git a/src/main.c b/src/main.c deleted file mode 100644 index c016892..0000000 --- a/src/main.c +++ /dev/null @@ -1,27 +0,0 @@ -#include -#include -#include "../include/compiler.h" - -int main() { - amal_compiler compiler; - int result; - const char *filepath; - filepath = "tests/main.amal"; - - result = amal_compiler_init(&compiler); - if(result != AMAL_COMPILER_OK) { - fprintf(stderr, "Failed to initialize compiler, error code: %d\n", result); - return 1; - } - - result = amal_compiler_load_file(&compiler, create_buffer_view(filepath, strlen(filepath))); - if(result != AMAL_COMPILER_OK) { - fprintf(stderr, "Failed to load file, error code: %d\n", result); - return 1; - } - -#ifdef DEBUG - return amal_compiler_deinit(&compiler); -#endif - return 0; -} diff --git a/src/std/buffer.c b/src/std/buffer.c index 1fdcfd4..e631153 100644 --- a/src/std/buffer.c +++ b/src/std/buffer.c @@ -39,9 +39,10 @@ static CHECK_RESULT int buffer_ensure_capacity(Buffer *self, usize new_capacity) return BUFFER_OK; } -int buffer_append(Buffer *self, void *data, usize size) { +int buffer_append(Buffer *self, const void *data, usize size) { return_if_error(buffer_ensure_capacity(self, self->size + size)); - am_memcpy(self->data + self->size, data, size); + if(data) + am_memcpy(self->data + self->size, data, size); self->size += size; return BUFFER_OK; } @@ -72,4 +73,4 @@ void *buffer_end(Buffer *self) { usize __buffer_get_size(Buffer *self, usize type_size) { assert(type_size != 0); return self->size / type_size; -} \ No newline at end of file +} diff --git a/src/std/hash.c b/src/std/hash.c new file mode 100644 index 0000000..603149a --- /dev/null +++ b/src/std/hash.c @@ -0,0 +1,14 @@ +#include "../../include/std/hash.h" + +usize amal_hash_string(const u8 *data, usize size) { + usize result; + result = 0xdec05eba; + + while(size) { + result ^= *data; + ++data; + --size; + } + + return result; +} 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; +} diff --git a/src/std/mem.c b/src/std/mem.c index ec7520c..f406176 100644 --- a/src/std/mem.c +++ b/src/std/mem.c @@ -5,8 +5,12 @@ void am_memcpy(void *dest, const void *src, usize size) { memcpy(dest, src, size); } +int am_memcmp(const void *lhs, const void *rhs, usize size) { + return memcmp(lhs, rhs, size); +} + bool am_memeql(const void *lhs, const void *rhs, usize size) { - return memcmp(lhs, rhs, size) == 0; + return am_memcmp(lhs, rhs, size) == 0; } void am_memset(void *dest, int value, usize size) { diff --git a/src/std/thread.c b/src/std/thread.c index c8dba9a..64a7f1b 100644 --- a/src/std/thread.c +++ b/src/std/thread.c @@ -89,6 +89,10 @@ void amal_mutex_init(amal_mutex *self) { self->lock_identifier = NULL; } +void amal_mutex_deinit(amal_mutex *self) { + pthread_mutex_destroy(&self->mutex); +} + static long amal_process_get_id() { return getpid(); } diff --git a/src/tokenizer.c b/src/tokenizer.c index 152aec4..04e9d27 100644 --- a/src/tokenizer.c +++ b/src/tokenizer.c @@ -558,4 +558,4 @@ TokenizerError tokenizer_create_error(Tokenizer *tokenizer, const char *err_str) result.index = tokenizer->prev_index; result.str = err_str; return result; -} \ No newline at end of file +} -- cgit v1.2.3