From 1dd53ce54c2008e3a11a636a496853cf6f9a5d65 Mon Sep 17 00:00:00 2001 From: dec05eba Date: Fri, 24 Jan 2020 09:11:53 +0100 Subject: Convert hash map to gc, implement more instructions and call command --- src/command.c | 90 ++++++++++++++++++ src/main.c | 19 ++-- src/parser.c | 13 ++- src/program.c | 162 ++++++++++++++++++++++++++------- src/std/buffer.c | 25 +++-- src/std/hash_map.c | 247 -------------------------------------------------- src/std_gc/hash_map.c | 194 +++++++++++++++++++++++++++++++++++++++ src/tokenizer.c | 2 +- src/value.c | 45 +++++++++ 9 files changed, 497 insertions(+), 300 deletions(-) create mode 100644 src/command.c delete mode 100644 src/std/hash_map.c create mode 100644 src/std_gc/hash_map.c create mode 100644 src/value.c (limited to 'src') diff --git a/src/command.c b/src/command.c new file mode 100644 index 0000000..c413502 --- /dev/null +++ b/src/command.c @@ -0,0 +1,90 @@ +#include "../include/command.h" +#include +#include +#include +#include +#include +#include + +#define READ_END 0 +#define WRITE_END 1 + +int tsl_command_exec(char **args, ProgramOutputCallback output_callback, void *userdata) { + int fd[2]; + pid_t pid; + + /* 1 arguments */ + if(args[0] == NULL) + return -1; + + if(pipe(fd) == -1) { + perror("Failed to open pipe"); + return -2; + } + + pid = fork(); + if(pid == -1) { + perror("Failed to fork"); + return -3; + } else if(pid == 0) { /* child */ + dup2(fd[WRITE_END], STDOUT_FILENO); + close(fd[READ_END]); + close(fd[WRITE_END]); + + execvp(args[0], args); + return 0; + } else { /* parent */ + int result = 0; + int status; + char buffer[2048]; + int exit_status; + + close(fd[WRITE_END]); + for(;;) { + ssize_t bytes_read = read(fd[READ_END], buffer, sizeof(buffer) - 1); + if(bytes_read == 0) { + break; + } else if(bytes_read == -1) { + int err = errno; + fprintf(stderr, "Failed to read from pipe to program %s, error: %s\n", args[0], strerror(err)); + result = -err; + goto cleanup; + } + + buffer[bytes_read] = '\0'; + if(output_callback && !output_callback(buffer, bytes_read, userdata)) + break; + } + + if(waitpid(pid, &status, 0) == -1) { + perror("waitpid failed"); + result = -5; + goto cleanup; + } + + if(!WIFEXITED(status)) { + result = -4; + goto cleanup; + } + + exit_status = WEXITSTATUS(status); + if(exit_status != 0) { + char **arg = args; + fprintf(stderr, "Failed to execute program ("); + + while(*arg) { + if(arg != args) + fputc(' ', stderr); + fprintf(stderr, "'%s'", *arg); + ++arg; + } + fprintf(stderr, "), exit status %d\n", exit_status); + result = -exit_status; + goto cleanup; + } + + cleanup: + close(fd[READ_END]); + return result; + } +} diff --git a/src/main.c b/src/main.c index 2166ff5..e36d912 100644 --- a/src/main.c +++ b/src/main.c @@ -56,6 +56,7 @@ int main(int argc, char **argv) { char *file_content; size_t filesize; TslProgram program; + int result = 0; if(argc != 2) { usage(); @@ -64,16 +65,22 @@ int main(int argc, char **argv) { file_content = file_get_content(argv[1], &filesize); if(!file_content) - return 1; + return 2; tsl_program_init(&program); - if(!tsl_parse(file_content, filesize, &program)) - return 2; - if(!tsl_program_run(&program)) - return 3; + if(!tsl_parse(file_content, filesize, &program)) { + result = 3; + goto cleanup; + } + + if(!tsl_program_run(&program)) { + result = 4; + goto cleanup; + } + cleanup: free(file_content); tsl_program_deinit(&program); - return 0; + return result; } diff --git a/src/parser.c b/src/parser.c index 098962a..a6f340f 100644 --- a/src/parser.c +++ b/src/parser.c @@ -26,7 +26,7 @@ static int tsl_parser_get_current_function_index(TslParser *self) { static TslParseResult tsl_parser_parse_rhs(TslParser *self); static TslParseResult tsl_parser_parse_expressions(TslParser *self, TslToken end_token); -static int tsl_parser_init(TslParser *self, const char *code, size_t code_size) { +static int tsl_parser_init(TslParser *self, char *code, size_t code_size) { TslBytecode bytecode_writer; int result1 = 1; int result2 = 1; @@ -216,7 +216,6 @@ static TslParseResult tsl_parser_parse_func_call(TslParser *self, int *num_args) } } -/* TODO: Do not allow empty command */ /* TODO: Allow command inside another command */ /* COMMAND = '(' TSL_COMMAND_TOKEN_ARG* ')' */ static TslParseResult tsl_parser_parse_command(TslParser *self, int *num_args) { @@ -328,8 +327,12 @@ TslParseResult tsl_parser_parse_rhs(TslParser *self) { } case TSL_TOKEN_DOLLAR_SIGN: { int num_args; - return tsl_parser_parse_command(self, &num_args) && - tsl_bytecode_add_ins1(get_function_bytecode(self), TSL_OPCODE_CALLC, num_args); + return_if_error(tsl_parser_parse_command(self, &num_args)) + if(num_args == 0) { + fprintf(stderr, "Error: Command can't be empty\n"); + return TSL_PARSE_RESULT_ERR; + } + return tsl_bytecode_add_ins1(get_function_bytecode(self), TSL_OPCODE_CALLC, num_args); } default: fprintf(stderr, "Error: Expected variable, number, bool, null, map, list, function or command, got TODO (%d) (line: %d)\n", token, tsl_tokenizer_get_line_by_index(&self->tokenizer, self->tokenizer.prev_code_index)); @@ -365,7 +368,7 @@ TslParseResult tsl_parser_parse_expressions(TslParser *self, TslToken end_token) return TSL_PARSE_RESULT_OK; } -TslParseResult tsl_parse(const char *code, size_t code_size, TslProgram *program_output) { +TslParseResult tsl_parse(char *code, size_t code_size, TslProgram *program_output) { TslParseResult result; TslParser parser; diff --git a/src/program.c b/src/program.c index 3ec6f85..0a0027b 100644 --- a/src/program.c +++ b/src/program.c @@ -1,12 +1,26 @@ #include "../include/program.h" #include "../include/bytecode.h" +#include "../include/command.h" +#ifdef DEBUG +#define GC_DEBUG +#endif +#include #include #include +#include +#include + +#define return_if_error(expr) \ + { \ + if(!(expr)) { \ + result = TSL_PROGRAM_RESULT_ERR; \ + goto cleanup; \ + } \ + } void tsl_program_init(TslProgram *self) { + GC_INIT(); /* TODO: Remove this */ tsl_buffer_init(&self->function_bytecode_list); - tsl_hash_map_init(&self->variables); - self->stack_index = 0; } void tsl_program_deinit(TslProgram *self) { @@ -17,34 +31,31 @@ void tsl_program_deinit(TslProgram *self) { ++bytecode_writer; } tsl_buffer_deinit(&self->function_bytecode_list); - 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 program_output_temp(char *data, int size, void *userdata) { + (void)size; + (void)userdata; + fputs(data, stdout); + return 1; } TslProgramResult tsl_program_run(TslProgram *self) { - #define push(value, type_enum, value_field) \ - do { \ - if(self->stack_index == TSL_STACK_MAX_SIZE) \ - return TSL_PROGRAM_RESULT_ERR; \ - self->stack_values[self->stack_index].data.value_field = (value); \ - self->stack_values[self->stack_index].type = (type_enum); \ - ++self->stack_index; \ - } while(0) - + TslProgramResult result = TSL_PROGRAM_RESULT_OK; TslBytecode *file_scope_bytecode = tsl_buffer_begin(&self->function_bytecode_list); char *instruction = tsl_buffer_begin(&file_scope_bytecode->buffer); char *instruction_end = tsl_buffer_end(&file_scope_bytecode->buffer); - printf("#############################\n"); + + self->variables = GC_MALLOC_UNCOLLECTABLE(sizeof(TslHashMap)); + if(!self->variables) { + fprintf(stderr, "Error: Failed to allocate root object\n"); + return TSL_PROGRAM_RESULT_ERR; + } + tsl_hash_map_init(self->variables); + tsl_buffer_init(&self->stack_values); + + printf("###########################\n"); + /* TODO: Verify if these don't cause unaligned memory access on non-x86 platforms */ while(instruction != instruction_end) { TslOpcode opcode = *(TslOpcode*)instruction; @@ -54,46 +65,84 @@ TslProgramResult tsl_program_run(TslProgram *self) { TslInstructionType4 *instruction_type4 = (TslInstructionType4*)instruction; switch(opcode) { case TSL_OPCODE_LOADN: { + TslStackValue stack_value; + stack_value.data.number = instruction_type2->value; + stack_value.type = TSL_STACK_VALUE_TYPE_NUMBER; + return_if_error(tsl_buffer_append(&self->stack_values, &stack_value, sizeof(stack_value))); printf("loadn %f\n", instruction_type2->value); - push(instruction_type2->value, TSL_TYPE_NUMBER, number); instruction += sizeof(TslInstructionType2); break; } case TSL_OPCODE_LOADB: { + TslStackValue stack_value; + stack_value.data.boolean = instruction_type3->value; + stack_value.type = TSL_STACK_VALUE_TYPE_BOOL; + return_if_error(tsl_buffer_append(&self->stack_values, &stack_value, sizeof(stack_value))); printf("loadb %s\n", instruction_type3->value ? "true" : "false"); - push(instruction_type3->value, TSL_TYPE_BOOL, boolean); instruction += sizeof(TslInstructionType3); break; } case TSL_OPCODE_LOADS: { + #if 0 + TslString *str = GC_MALLOC(sizeof(TslString)); + char *str_data = GC_MALLOC_ATOMIC(instruction_type4->value.size + 1); + if(!str) { + fprintf(stderr, "Error: out of memory\n"); + return TSL_PROGRAM_RESULT_ERR; + } + if(!str_data) { + fprintf(stderr, "Error: out of memory\n"); + return TSL_PROGRAM_RESULT_ERR; + } + memcpy(str->data, instruction_type4->value.data, instruction_type4->value.size); + str->data[instruction_type4->value.size] = '\0'; + str->size = instruction_type4->value.size; + #endif + TslStackValue stack_value; + stack_value.data.str = instruction_type4->value; + stack_value.type = TSL_STACK_VALUE_TYPE_STRING; + return_if_error(tsl_buffer_append(&self->stack_values, &stack_value, sizeof(stack_value))); printf("loads \"%.*s\"\n", (int)instruction_type4->value.size, instruction_type4->value.data); instruction += sizeof(TslInstructionType4); break; } case TSL_OPCODE_LOADF: { + TslStackValue stack_value; + stack_value.data.integer = instruction_type1->value; + stack_value.type = TSL_STACK_VALUE_TYPE_FUNCTION; + return_if_error(tsl_buffer_append(&self->stack_values, &stack_value, sizeof(stack_value))); printf("loadf %d\n", instruction_type1->value); instruction += sizeof(TslInstructionType1); break; } case TSL_OPCODE_LOADV: { + TslStackValue stack_value; + stack_value.data.str = instruction_type4->value; + stack_value.type = TSL_STACK_VALUE_TYPE_VARIABLE; + return_if_error(tsl_buffer_append(&self->stack_values, &stack_value, sizeof(stack_value))); printf("loadv \"%.*s\"\n", (int)instruction_type4->value.size, instruction_type4->value.data); instruction += sizeof(TslInstructionType4); break; } case TSL_OPCODE_LOADNULL: { + TslStackValue stack_value; + stack_value.type = TSL_STACK_VALUE_TYPE_NULL; + return_if_error(tsl_buffer_append(&self->stack_values, &stack_value, sizeof(stack_value))); printf("loadnull\n"); instruction += sizeof(TslInstructionType5); break; } case TSL_OPCODE_SETV: { - TslValue stack_value; - TslValue *value; + TslValue map_key; + TslValue *stack_value; + TslValue *map_value; + map_key.type = TSL_TYPE_STRING_VIEW; + map_key.data.string_view = instruction_type4->value; + stack_value = tsl_buffer_pop(&self->stack_values, sizeof(TslStackValue)); + map_value = tsl_hash_map_get_or_create(self->variables, &map_key); + return_if_error(map_value); + *map_value = *stack_value; printf("setv \"%.*s\"\n", (int)instruction_type4->value.size, instruction_type4->value.data); - assert(self->stack_index > 0); - stack_value = self->stack_values[--self->stack_index]; - if(!tsl_hash_map_get_or_create(&self->variables, &instruction_type4->value, sizeof(TslValue), hash_string_view, (void**)&value)) - return TSL_PROGRAM_RESULT_ERR; - *value = stack_value; instruction += sizeof(TslInstructionType4); break; } @@ -138,16 +187,65 @@ TslProgramResult tsl_program_run(TslProgram *self) { break; } case TSL_OPCODE_LOADCA: { + TslStackValue stack_value; + stack_value.data.str = instruction_type4->value; + stack_value.type = TSL_STACK_VALUE_TYPE_COMMAND_ARG; + return_if_error(tsl_buffer_append(&self->stack_values, &stack_value, sizeof(stack_value))); printf("loadca \"%.*s\"\n", (int)instruction_type4->value.size, instruction_type4->value.data); instruction += sizeof(TslInstructionType4); break; } case TSL_OPCODE_CALLC: { + TslStackValue *args_begin = tsl_buffer_pop(&self->stack_values, sizeof(TslStackValue) * instruction_type1->value); + TslStackValue *args_end = args_begin + instruction_type1->value; + TslStackValue *args = args_begin; + char *command_args[255]; + char temp_null_save[255]; + size_t arg_index = 0; + assert(instruction_type1->value > 0); + { + /* TODO: Support infinite amount of args */ + assert(args_end - args_begin < 255); + printf("Running command: "); + while(args != args_end) { + assert(args->type == TSL_STACK_VALUE_TYPE_COMMAND_ARG); + temp_null_save[arg_index] = args->data.str.data[args->data.str.size]; + args->data.str.data[args->data.str.size] = '\0'; + + command_args[arg_index] = args->data.str.data; + printf("%s ", command_args[arg_index]); + ++arg_index; + ++args; + } + command_args[arg_index] = NULL; + printf("\n"); + } + + tsl_command_exec(command_args, program_output_temp, NULL); + + { + args = args_begin; + arg_index = 0; + /* TODO: Support infinite amount of args */ + while(args != args_end) { + args->data.str.data[args->data.str.size] = temp_null_save[arg_index]; + ++arg_index; + ++args; + } + command_args[arg_index] = NULL; + } + printf("callc %d\n", instruction_type1->value); instruction += sizeof(TslInstructionType1); break; } } } - return TSL_PROGRAM_RESULT_OK; + + cleanup: + assert(self->stack_values.size == 0); /* All push instructions (mostly load) haven't been handled yet. This is a bug in tsl */ + tsl_buffer_deinit(&self->stack_values); + GC_FREE(self->variables); /* Free the root object, resulting in all objects in the program being free'd */ + self->variables = NULL; + return result; } diff --git a/src/std/buffer.c b/src/std/buffer.c index 343173a..b0099bb 100644 --- a/src/std/buffer.c +++ b/src/std/buffer.c @@ -18,24 +18,25 @@ void tsl_buffer_deinit(TslBuffer *self) { static int tsl_buffer_ensure_capacity(TslBuffer *self, size_t new_size) { void *new_ptr; + size_t new_capacity = self->capacity; if(new_size <= self->capacity) return 1; + + if(new_capacity == 0) + new_capacity = 8; - if(self->capacity != 0) { - size_t new_capacity = self->capacity; - while(new_capacity < new_size) { - new_capacity <<= 1; - } - new_size = new_capacity; + while(new_capacity < new_size) { + new_capacity <<= 1; } - new_ptr = realloc(self->data, new_size); + + new_ptr = realloc(self->data, new_capacity); if(!new_ptr) { fprintf(stderr, "Error: buffer append failed. Reason: out of memory\n"); return 0; } self->data = new_ptr; - self->capacity = new_size; + self->capacity = new_capacity; return 1; } @@ -47,9 +48,15 @@ int tsl_buffer_append(TslBuffer *self, const void *data, size_t size) { return 1; } -void tsl_buffer_pop(TslBuffer *self, size_t size) { +void* tsl_buffer_pop(TslBuffer *self, size_t size) { assert(self->size >= size); self->size -= size; + return (char*)self->data + self->size; +} + +void* tsl_buffer_top(TslBuffer *self, size_t data_size) { + tsl_buffer_pop(self, data_size); + return (char*)self->data + self->size; } void* tsl_buffer_begin(TslBuffer *self) { diff --git a/src/std/hash_map.c b/src/std/hash_map.c deleted file mode 100644 index 9d8b4c4..0000000 --- a/src/std/hash_map.c +++ /dev/null @@ -1,247 +0,0 @@ -#include "../../include/std/hash_map.h" -#include -#include -#include -#include - -typedef struct TslHashMapNode TslHashMapNode; -struct TslHashMapNode { - void *data; - TslHashMapNode *next; -}; - -static void hash_map_node_get(TslHashMapNode *self, uint64_t *hash, TslStringView *key, size_t *size, uint8_t **data) { - memcpy(hash, (uint8_t*)self->data, sizeof(uint64_t)); - memcpy(&key->size, (uint8_t*)self->data + sizeof(uint64_t), sizeof(key->size)); - key->data = (const char*)self->data + sizeof(uint64_t) + sizeof(key->size); - memcpy(size, (uint8_t*)self->data + sizeof(uint64_t) + sizeof(key->size) + key->size, sizeof(size_t)); - *data = (uint8_t*)self->data + sizeof(uint64_t) + sizeof(key->size) + key->size + sizeof(size_t); -} - -void tsl_hash_map_init(TslHashMap *self) { - self->buckets_data = NULL; - self->buckets_size = 0; - self->buckets_capacity = 0; -} - -void tsl_hash_map_deinit(TslHashMap *self) { - TslHashMapNode **bucket = (TslHashMapNode**)self->buckets_data; - TslHashMapNode **bucket_end = (TslHashMapNode**)((char*)self->buckets_data + self->buckets_capacity); - while(bucket != bucket_end) { - TslHashMapNode *node = *bucket; - while(node) { - TslHashMapNode *prev_node = node; - node = node->next; - free(prev_node->data); - free(prev_node); - } - ++bucket; - } - free(self->buckets_data); -} - -/* TODO: Remove if (data) and if (output) */ -static int tsl_hash_map_append_bucket(TslHashMapNode **head_node, uint64_t hash, const TslStringView *key, size_t size, const void *data, void **output) { - TslHashMapNode *next_node; - uint8_t *node_data = malloc(sizeof(hash) + sizeof(key->size) + key->size + sizeof(size) + size); - - if(output) - *output = NULL; - - if(!node_data) { - fprintf(stderr, "Error: hash map append failed. Reason: out of memory\n"); - return 0; - } - - next_node = malloc(sizeof(TslHashMapNode)); - if(!next_node) { - free(node_data); - fprintf(stderr, "Error: hash map append failed. Reason: out of memory\n"); - return 0; - } - - memcpy(node_data, &hash, sizeof(hash)); - /* TODO: Instead of allocating space for the key, use the key data pointer and size directly. */ - memcpy(node_data + sizeof(hash), &key->size, sizeof(key->size)); - memcpy(node_data + sizeof(hash) + sizeof(key->size), key->data, key->size); - /* - TODO: Instead of allocating space for the data, allow the user to pass a pointer in the insert - method and use that directly. - */ - memcpy(node_data + sizeof(hash) + sizeof(key->size) + key->size, &size, sizeof(size)); - if(data) - memcpy(node_data + sizeof(hash) + sizeof(key->size) + key->size + sizeof(size), data, size); - - if(output) - *output = node_data + sizeof(hash) + sizeof(key->size) + key->size + sizeof(size); - - next_node->data = node_data; - if(*head_node) { - next_node->next = (*head_node)->next; - (*head_node)->next = next_node; - } else { - next_node->next = NULL; - *head_node = next_node; - } - return 1; -} - -static size_t tsl_hash_map_get_index(TslHashMap *self, uint64_t hash) { - assert((self->buckets_capacity >> 3) > 0); - /* >>3 = 8 = sizeof(TslHashMapNode*) */ - return hash & ((self->buckets_capacity >> 3) - 1); -} - -static void tsl_hash_map_reorder_nodes(TslHashMap *self, size_t old_capacity) { - TslHashMapNode **bucket = (TslHashMapNode**)self->buckets_data; - TslHashMapNode **bucket_end = (TslHashMapNode**)((char*)self->buckets_data + old_capacity); - size_t bucket_index = 0; - 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; - size_t size; - uint8_t *data; - size_t index; - hash_map_node_get(node, &hash, &key, &size, &data); - - 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; - if(*new_bucket) { - node->next = (*new_bucket)->next; - (*new_bucket)->next = node; - } else { - 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; - } -} - -static int tsl_hash_map_ensure_bucket_capacity_for_one_new_item(TslHashMap *self) { - void *new_ptr; - size_t new_capacity = self->buckets_capacity; - size_t new_size = self->buckets_size + sizeof(TslHashMapNode*); - size_t old_capacity = self->buckets_capacity; - self->buckets_size = new_size; - if(new_size <= self->buckets_capacity) - return 1; - - if(new_capacity == 0) - new_capacity = sizeof(TslHashMapNode*) << 3; - - while(new_capacity < new_size) { - new_capacity <<= 1; - } - - new_ptr = realloc(self->buckets_data, new_capacity); - if(!new_ptr) { - fprintf(stderr, "Error: hash map realloc failed. Reason: out of memory\n"); - return 0; - } - - self->buckets_data = new_ptr; - self->buckets_capacity = new_capacity; - { - TslHashMapNode **bucket = (TslHashMapNode**)((char*)self->buckets_data + old_capacity); - TslHashMapNode **bucket_end = (TslHashMapNode**)((char*)self->buckets_data + new_capacity); - while(bucket != bucket_end) { - *bucket = NULL; - ++bucket; - } - } - - if(old_capacity == 0) - return 1; - - tsl_hash_map_reorder_nodes(self, old_capacity); - return 1; -} - -int tsl_hash_map_insert(TslHashMap *self, const TslStringView *key, const void *data, size_t size, TslHashFunc hash_func) { - uint64_t hash = hash_func(key->data, key->size); - size_t index; - TslHashMapNode **bucket; - assert(!tsl_hash_map_get(self, key, hash_func)); - assert(size > 0); - if(!tsl_hash_map_ensure_bucket_capacity_for_one_new_item(self)) - return 0; - - 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, NULL); -} - -void* tsl_hash_map_get(TslHashMap *self, const TslStringView *key, TslHashFunc hash_func) { - uint64_t hash; - size_t index; - TslHashMapNode *node; - if(self->buckets_capacity == 0) - return NULL; - - hash = hash_func(key->data, key->size); - index = tsl_hash_map_get_index(self, hash); - node = *((TslHashMapNode**)self->buckets_data + index); - while(node) { - uint64_t node_hash; - TslStringView node_key; - size_t node_size; - uint8_t *node_data; - hash_map_node_get(node, &node_hash, &node_key, &node_size, &node_data); - if(hash == node_hash && key->size == node_key.size && memcmp(key->data, node_key.data, node_key.size) == 0) - return node_data; - node = node->next; - } - - return NULL; -} - -int tsl_hash_map_get_or_create(TslHashMap *self, const TslStringView *key, size_t size, TslHashFunc hash_func, void **output) { - uint64_t hash; - size_t index; - TslHashMapNode **bucket; - TslHashMapNode *node; - assert(size > 0); - if(self->buckets_capacity == 0) { - if(!tsl_hash_map_ensure_bucket_capacity_for_one_new_item(self)) { - *output = NULL; - return 0; - } - } - - hash = hash_func(key->data, key->size); - index = tsl_hash_map_get_index(self, hash); - bucket = (TslHashMapNode**)self->buckets_data + index; - node = *bucket; - while(node) { - uint64_t node_hash; - TslStringView node_key; - size_t node_size; - uint8_t *node_data; - hash_map_node_get(node, &node_hash, &node_key, &node_size, &node_data); - if(hash == node_hash && key->size == node_key.size && memcmp(key->data, node_key.data, node_key.size) == 0) { - *output = node_data; - return 1; - } - node = node->next; - } - - return tsl_hash_map_append_bucket(bucket, hash, key, size, NULL, output); -} diff --git a/src/std_gc/hash_map.c b/src/std_gc/hash_map.c new file mode 100644 index 0000000..1960ffc --- /dev/null +++ b/src/std_gc/hash_map.c @@ -0,0 +1,194 @@ +#include "../../include/std_gc/hash_map.h" +#include +#include +#include +#include + +typedef struct TslHashMapNode TslHashMapNode; +struct TslHashMapNode { + uint64_t hash; + TslValue key; + TslValue value; + TslHashMapNode *next; +}; + +void tsl_hash_map_init(TslHashMap *self) { + self->buckets_data = NULL; + self->buckets_size = 0; + self->buckets_capacity = 0; +} + +/* TODO: Remove if (data) and if (output) */ +static int tsl_hash_map_append_bucket(TslHashMapNode **head_node, uint64_t hash, const TslValue *key, TslValue *value, TslValue **output) { + TslHashMapNode *next_node; + + if(output) + *output = NULL; + + next_node = GC_MALLOC(sizeof(TslHashMapNode)); + if(!next_node) { + fprintf(stderr, "Error: hash map insert failed. Reason: out of memory\n"); + return 0; + } + + next_node->hash = hash; + next_node->key = *key; + if(value) + next_node->value = *value; + + if(output) + *output = &next_node->value; + + if(*head_node) { + next_node->next = (*head_node)->next; + (*head_node)->next = next_node; + } else { + next_node->next = NULL; + *head_node = next_node; + } + + return 1; +} + +static size_t tsl_hash_map_get_index(TslHashMap *self, uint64_t hash) { + assert((self->buckets_capacity >> 3) > 0); + /* >>3 = 8 = sizeof(TslHashMapNode*) */ + return hash & ((self->buckets_capacity >> 3) - 1); +} + +static void tsl_hash_map_reorder_nodes(TslHashMap *self, size_t old_capacity) { + TslHashMapNode **bucket = (TslHashMapNode**)self->buckets_data; + TslHashMapNode **bucket_end = (TslHashMapNode**)((char*)self->buckets_data + old_capacity); + size_t bucket_index = 0; + 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) { + size_t index = tsl_hash_map_get_index(self, node->hash); + if(index != bucket_index) { + TslHashMapNode **new_bucket = (TslHashMapNode**)self->buckets_data + index; + prev_node->next = node->next; + if(*new_bucket) { + node->next = (*new_bucket)->next; + (*new_bucket)->next = node; + } else { + 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; + } +} + +static int tsl_hash_map_ensure_bucket_capacity_for_one_new_item(TslHashMap *self) { + void *new_ptr; + size_t new_capacity = self->buckets_capacity; + size_t new_size = self->buckets_size + sizeof(TslHashMapNode*); + size_t old_capacity = self->buckets_capacity; + self->buckets_size = new_size; + if(new_size <= self->buckets_capacity) + return 1; + + if(new_capacity == 0) + new_capacity = sizeof(TslHashMapNode*) << 3; + + while(new_capacity < new_size) { + new_capacity <<= 1; + } + + new_ptr = GC_REALLOC(self->buckets_data, new_capacity); + if(!new_ptr) { + fprintf(stderr, "Error: hash map realloc failed. Reason: out of memory\n"); + return 0; + } + + self->buckets_data = new_ptr; + self->buckets_capacity = new_capacity; + { + /* TODO: Remove this. This is not needed since GC_REALLOC sets the data to 0 */ + TslHashMapNode **bucket = (TslHashMapNode**)((char*)self->buckets_data + old_capacity); + TslHashMapNode **bucket_end = (TslHashMapNode**)((char*)self->buckets_data + new_capacity); + while(bucket != bucket_end) { + *bucket = NULL; + ++bucket; + } + } + + if(old_capacity == 0) + return 1; + + tsl_hash_map_reorder_nodes(self, old_capacity); + return 1; +} + +int tsl_hash_map_insert(TslHashMap *self, const TslValue *key, TslValue *value) { + uint64_t hash = tsl_value_hash(key); + size_t index; + TslHashMapNode **bucket; + assert(!tsl_hash_map_get(self, key)); + if(!tsl_hash_map_ensure_bucket_capacity_for_one_new_item(self)) + return 0; + + index = tsl_hash_map_get_index(self, hash); + bucket = (TslHashMapNode**)self->buckets_data + index; + return tsl_hash_map_append_bucket(bucket, hash, key, value, NULL); +} + +TslValue* tsl_hash_map_get(TslHashMap *self, const TslValue *key) { + uint64_t hash; + size_t index; + TslHashMapNode *node; + if(self->buckets_capacity == 0) + return NULL; + + hash = tsl_value_hash(key); + index = tsl_hash_map_get_index(self, hash); + node = *((TslHashMapNode**)self->buckets_data + index); + while(node) { + if(hash == node->hash && tsl_value_equals(key, &node->key)) + return &node->value; + node = node->next; + } + + return NULL; +} + +TslValue* tsl_hash_map_get_or_create(TslHashMap *self, const TslValue *key) { + uint64_t hash; + size_t index; + TslHashMapNode **bucket; + TslHashMapNode *node; + TslValue *value; + if(self->buckets_capacity == 0) { + if(!tsl_hash_map_ensure_bucket_capacity_for_one_new_item(self)) + return NULL; + } + + hash = tsl_value_hash(key); + index = tsl_hash_map_get_index(self, hash); + bucket = (TslHashMapNode**)self->buckets_data + index; + node = *bucket; + while(node) { + if(hash == node->hash && tsl_value_equals(key, &node->key)) + return &node->value; + node = node->next; + } + + if(!tsl_hash_map_append_bucket(bucket, hash, key, NULL, &value)) + return NULL; + + return value; +} diff --git a/src/tokenizer.c b/src/tokenizer.c index 02592a9..a990052 100644 --- a/src/tokenizer.c +++ b/src/tokenizer.c @@ -4,7 +4,7 @@ #include #include -void tsl_tokenizer_init(TslTokenizer *self, const char *code, size_t code_size) { +void tsl_tokenizer_init(TslTokenizer *self, char *code, size_t code_size) { self->code = code; self->code_size = code_size; self->code_index = 0; diff --git a/src/value.c b/src/value.c new file mode 100644 index 0000000..690527f --- /dev/null +++ b/src/value.c @@ -0,0 +1,45 @@ +#include "../include/value.h" +#include + +static uint64_t hash_range(const uint8_t *data, size_t size) { + uint64_t result = 0xdec05eba; + while(size) { + result = ((result << 5) + result) + *data; + ++data; + --size; + } + return result; +} + +uint64_t tsl_value_hash(const TslValue *key) { + switch(key->type) { + case TSL_TYPE_NULL: + return 0; + case TSL_TYPE_NUMBER: + return *(uint64_t*)&key->data.number; + case TSL_TYPE_STRING: + return hash_range(key->data.string->data, key->data.string->size); + case TSL_TYPE_BOOL: + return key->data.boolean; + case TSL_TYPE_LIST: + return (uint64_t)key->data.list; + case TSL_TYPE_MAP: + return (uint64_t)key->data.map; + case TSL_TYPE_USERDATA: + return (uint64_t)key->data.userdata; + } + return 0; +} + +int tsl_value_equals(const TslValue *lhs, const TslValue *rhs) { + if(lhs->type == rhs->type) { + if(lhs->type == TSL_TYPE_STRING) { + return lhs->data.string->size == rhs->data.string->size + && memcmp(lhs->data.string->data, rhs->data.string->data, lhs->data.string->size) == 0; + } else { + return *(uint64_t*)&lhs->data == *(uint64_t*)&rhs->data; + } + } else { + return 0; + } +} -- cgit v1.2.3