From 27718f093689dbd3decd7021eaa97327f578c8f3 Mon Sep 17 00:00:00 2001 From: dec05eba Date: Thu, 7 Mar 2019 22:19:57 +0100 Subject: Add hash map --- .gitignore | 2 + build.sh | 8 +- include/binop_type.h | 2 +- include/std/buffer.h | 3 +- include/std/defs.h | 3 + include/std/hash.h | 8 ++ include/std/hash_map.h | 38 ++++++++ include/std/mem.h | 1 + include/std/scoped_allocator.h | 4 +- include/std/thread.h | 1 + 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 +- tests/main.c | 61 +++++++++++++ 20 files changed, 372 insertions(+), 41 deletions(-) create mode 100644 include/std/hash.h create mode 100644 include/std/hash_map.h delete mode 100644 src/main.c create mode 100644 src/std/hash.c create mode 100644 src/std/hash_map.c create mode 100644 tests/main.c diff --git a/.gitignore b/.gitignore index c551744..06e9210 100644 --- a/.gitignore +++ b/.gitignore @@ -1,3 +1,5 @@ .vscode/ .gdb_history amalgam +test +libamalgam.so diff --git a/build.sh b/build.sh index b3dfc9f..5ca2ea6 100755 --- a/build.sh +++ b/build.sh @@ -21,4 +21,10 @@ CFLAGS+="-Wall -Wextra -Werror -g -O0 -DDEBUG -std=c89 -pedantic -D_GNU_SOURCE" LIBS+="-pthread" set -x -time "$CC" $source_files $CFLAGS $LIBS -o amalgam +time "$CC" $source_files $CFLAGS $LIBS -shared -fpic -o libamalgam.so +set +x +if [ -z "$NO_TEST" ]; then + source_files_tests=$(readlink -f $(find "$this_script_dir/tests" -name "*.c")) + set -x + time "$CC" $source_files_tests $CFLAGS $LIBS -o test "$this_script_dir/libamalgam.so" +fi \ No newline at end of file diff --git a/include/binop_type.h b/include/binop_type.h index d04f9d7..e747102 100644 --- a/include/binop_type.h +++ b/include/binop_type.h @@ -9,4 +9,4 @@ typedef enum { BINOP_DOT } BinopType; -#endif \ No newline at end of file +#endif diff --git a/include/std/buffer.h b/include/std/buffer.h index a60def9..688f18a 100644 --- a/include/std/buffer.h +++ b/include/std/buffer.h @@ -16,7 +16,8 @@ typedef struct { struct ScopedAllocator; CHECK_RESULT int buffer_init(Buffer *self, struct ScopedAllocator *allocator); -CHECK_RESULT int buffer_append(Buffer *self, void *data, usize size); +/* @data can be NULL */ +CHECK_RESULT int buffer_append(Buffer *self, const void *data, usize size); void* buffer_get(Buffer *self, usize index, usize type_size); CHECK_RESULT int buffer_pop(Buffer *self, void *data, usize size); void* buffer_start(Buffer *self); diff --git a/include/std/defs.h b/include/std/defs.h index 653bf73..ee049d4 100644 --- a/include/std/defs.h +++ b/include/std/defs.h @@ -4,4 +4,7 @@ typedef struct amal_thread amal_thread; typedef struct amal_mutex amal_mutex; +typedef struct ScopedAllocatorNode ScopedAllocatorNode; +typedef struct ScopedAllocator ScopedAllocator; + #endif diff --git a/include/std/hash.h b/include/std/hash.h new file mode 100644 index 0000000..f7a807d --- /dev/null +++ b/include/std/hash.h @@ -0,0 +1,8 @@ +#ifndef AMALGAM_HASH_H +#define AMALGAM_HASH_H + +#include "types.h" + +usize amal_hash_string(const u8 *data, usize size); + +#endif diff --git a/include/std/hash_map.h b/include/std/hash_map.h new file mode 100644 index 0000000..c36ecc4 --- /dev/null +++ b/include/std/hash_map.h @@ -0,0 +1,38 @@ +#ifndef AMALGAM_HASH_MAP_H +#define AMALGAM_HASH_MAP_H + +#include "defs.h" +#include "misc.h" +#include "types.h" +#include "buffer.h" +#include "buffer_view.h" + +typedef struct HashMap HashMap; + +typedef int(*HashMapCompare)(const void *a, const void *b); +typedef usize(*HashMapHash)(const u8 *data, usize size); + +struct HashMap { + ScopedAllocator *allocator; /* borrowed */ + Buffer/*HashMapBucket*/ buckets; + usize type_size; + usize num_elements; + HashMapCompare compare_func; + HashMapHash hash_func; +}; + +CHECK_RESULT int hash_map_init(HashMap *self, ScopedAllocator *allocator, usize type_size, HashMapCompare compare_func, HashMapHash hash_func); +/* +Not thread-safe. +Expected @value size to be @self->type_size. +*/ +CHECK_RESULT int hash_map_insert(HashMap *self, BufferView key, void *value); +/* +Thread-safe unless @hash_map_insert is used in another thread at the same time. +Expected @value size to be @self->type_size. +*/ +CHECK_RESULT bool hash_map_get(HashMap *self, BufferView key, void *value); + +int hash_compare_string(const void *a, const void *b); + +#endif diff --git a/include/std/mem.h b/include/std/mem.h index 8d91a5a..ddd2b31 100644 --- a/include/std/mem.h +++ b/include/std/mem.h @@ -5,6 +5,7 @@ #include "misc.h" void am_memcpy(void *dest, const void *src, usize size); +int am_memcmp(const void *lhs, const void *rhs, usize size); bool am_memeql(const void *lhs, const void *rhs, usize size); void am_memset(void *dest, int value, usize size); diff --git a/include/std/scoped_allocator.h b/include/std/scoped_allocator.h index ad6e2dd..0de4f04 100644 --- a/include/std/scoped_allocator.h +++ b/include/std/scoped_allocator.h @@ -1,13 +1,11 @@ #ifndef AMALGAM_SCOPED_ALLOCATOR_H #define AMALGAM_SCOPED_ALLOCATOR_H +#include "defs.h" #include "misc.h" #include "types.h" #include "buffer.h" -typedef struct ScopedAllocatorNode ScopedAllocatorNode; -typedef struct ScopedAllocator ScopedAllocator; - struct ScopedAllocatorNode { char *data; usize size; diff --git a/include/std/thread.h b/include/std/thread.h index 972ce3a..915d6a9 100644 --- a/include/std/thread.h +++ b/include/std/thread.h @@ -38,6 +38,7 @@ CHECK_RESULT int amal_thread_detach(amal_thread *self); CHECK_RESULT int amal_thread_join(amal_thread *self, void **result); void amal_mutex_init(amal_mutex *self); +void amal_mutex_deinit(amal_mutex *self); CHECK_RESULT int amal_mutex_lock(amal_mutex *self, const char *lock_identifier); CHECK_RESULT int amal_mutex_unlock(amal_mutex *self); void amal_mutex_tryunlock(amal_mutex *self); 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 +} diff --git a/tests/main.c b/tests/main.c new file mode 100644 index 0000000..881866e --- /dev/null +++ b/tests/main.c @@ -0,0 +1,61 @@ +#include +#include +#include "../include/compiler.h" +#include "../include/std/hash_map.h" +#include "../include/std/hash.h" +#include +#include + +#define REQUIRE_EQ_INT(expected, actual) do{\ + if((expected) != (actual)) {\ + fprintf(stderr, "%s:%d: Assert failed (%s vs %s).\nExpected %d, got %d.\n", __FILE__, __LINE__, #expected, #actual, (expected), (actual));\ + exit(1);\ + }\ +}while(0) + +static CHECK_RESULT int test_hash_map() { + ScopedAllocator scoped_allocator; + HashMap hash_map; + int value; + bool has_key; + + return_if_error(scoped_allocator_init(&scoped_allocator)); + cleanup_if_error(hash_map_init(&hash_map, &scoped_allocator, sizeof(int), hash_compare_string, amal_hash_string)); + + value = 34; + return_if_error(hash_map_insert(&hash_map, create_buffer_view("hello", 5), &value)); + return_if_error(hash_map_insert(&hash_map, create_buffer_view("hellp", 5), &value)); + has_key = hash_map_get(&hash_map, create_buffer_view("hello", 5), &value); + if(!has_key) { + fprintf(stderr, "Missing value for key \"hello\" in hash map\n"); + exit(1); + } + REQUIRE_EQ_INT(34, value); + + cleanup: + scoped_allocator_deinit(&scoped_allocator); + return 0; +} + +int main() { + amal_compiler compiler; + int result; + const char *filepath; + filepath = "tests/main.amal"; + + return_if_error(test_hash_map()); + + 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; + } + + return amal_compiler_deinit(&compiler); +} -- cgit v1.2.3