From a79a3ec573955d073c872cbe112b60d017152a37 Mon Sep 17 00:00:00 2001 From: dec05eba Date: Tue, 21 Jan 2020 01:01:32 +0100 Subject: Fix hash map issues --- .gitignore | 3 ++- example.tsl | 1 + include/std/hash_map.h | 1 - src/parser.c | 30 +++++++++++++++++++++++++++++- src/std/buffer.c | 2 +- src/std/hash_map.c | 48 ++++++++++++++++++++++++++++++++---------------- 6 files changed, 65 insertions(+), 20 deletions(-) diff --git a/.gitignore b/.gitignore index 5d6847a..14dee4b 100644 --- a/.gitignore +++ b/.gitignore @@ -1,2 +1,3 @@ build/* -compile_commands.json \ No newline at end of file +compile_commands.json +.gdb_history diff --git a/example.tsl b/example.tsl index b81af3d..629cf46 100644 --- a/example.tsl +++ b/example.tsl @@ -1,4 +1,5 @@ value1 = 1 +value1 = 2 value2 = true value3 = null value4 = "hello world" diff --git a/include/std/hash_map.h b/include/std/hash_map.h index f3a3a6d..986576d 100644 --- a/include/std/hash_map.h +++ b/include/std/hash_map.h @@ -11,7 +11,6 @@ typedef struct { void *buckets_data; /* value=TslHashMapNode, data=|hash(uint64_t) + key_size(size_t) + key_data(...) data_size(size_t) + data_data(...)| */ size_t buckets_size; size_t buckets_capacity; - size_t num_items; } TslHashMap; void tsl_hash_map_init(TslHashMap *self); diff --git a/src/parser.c b/src/parser.c index 45b4412..be3461c 100644 --- a/src/parser.c +++ b/src/parser.c @@ -1,10 +1,12 @@ #include "../include/parser.h" #include "../include/bytecode.h" +#include "../include/std/hash_map.h" #include typedef struct { TslTokenizer tokenizer; TslBytecodeWriter bytecode_writer; + TslHashMap variables; } TslParser; static int tsl_parser_parse_rhs(TslParser *self); @@ -13,6 +15,23 @@ static int tsl_parser_parse_expressions(TslParser *self, TslToken end_token); static void tsl_parser_init(TslParser *self, const char *code, size_t code_size) { tsl_tokenizer_init(&self->tokenizer, code, code_size); tsl_bytecode_writer_init(&self->bytecode_writer); + tsl_hash_map_init(&self->variables); +} + +static void tsl_parser_deinit(TslParser *self) { + tsl_bytecode_writer_deinit(&self->bytecode_writer); + tsl_hash_map_deinit(&self->variables); +} + +static uint64_t hash_string_view(const void *data, size_t size) { + uint64_t result = 0xdec05eba; + const uint8_t *p = data; + while(size) { + result = ((result << 5) + result) + *p; + ++p; + --size; + } + return result; } static int tsl_parser_parse_map(TslParser *self) { @@ -280,6 +299,12 @@ int tsl_parser_parse_expressions(TslParser *self, TslToken end_token) { TslStringView identifier = self->tokenizer.identifier; printf("identifier: %.*s\n", identifier.size, identifier.data); if(tsl_tokenizer_peek(&self->tokenizer) == TSL_TOKEN_EQUAL) { + void *existing_variable = tsl_hash_map_get(&self->variables, &identifier, hash_string_view); + if(!existing_variable) { + fprintf(stderr, "Variable declaration: %.*s\n", identifier.size, identifier.data); + if(!tsl_hash_map_insert(&self->variables, &identifier, "a", 1, hash_string_view)) + return -1; + } tsl_tokenizer_consume_peek(&self->tokenizer); /* consume previous TSL_TOKEN_EQUAL */ if(tsl_parser_parse_rhs(self) != 0) return -1; @@ -298,7 +323,10 @@ int tsl_parser_parse_expressions(TslParser *self, TslToken end_token) { } int tsl_parse(const char *code, size_t code_size) { + int result; TslParser parser; tsl_parser_init(&parser, code, code_size); - return tsl_parser_parse_expressions(&parser, TSL_TOKEN_END_OF_FILE); + result = tsl_parser_parse_expressions(&parser, TSL_TOKEN_END_OF_FILE); + tsl_parser_deinit(&parser); + return result; } 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; -- cgit v1.2.3