aboutsummaryrefslogtreecommitdiff
path: root/src
diff options
context:
space:
mode:
authordec05eba <dec05eba@protonmail.com>2020-01-21 01:01:32 +0100
committerdec05eba <dec05eba@protonmail.com>2020-01-21 01:01:32 +0100
commita79a3ec573955d073c872cbe112b60d017152a37 (patch)
tree19caf9a5590d5870225eea0b7cda4bd6da7f7354 /src
parent108018e3e7326dabbbef568ab08bc5cebf5d427b (diff)
Fix hash map issues
Diffstat (limited to 'src')
-rw-r--r--src/parser.c30
-rw-r--r--src/std/buffer.c2
-rw-r--r--src/std/hash_map.c48
3 files changed, 62 insertions, 18 deletions
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 <stdio.h>
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;