From 108018e3e7326dabbbef568ab08bc5cebf5d427b Mon Sep 17 00:00:00 2001 From: dec05eba Date: Mon, 20 Jan 2020 23:00:39 +0100 Subject: Add arithmetic, implement hash map --- src/std/buffer.c | 19 ++++-- src/std/hash_map.c | 170 +++++++++++++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 185 insertions(+), 4 deletions(-) create mode 100644 src/std/hash_map.c (limited to 'src/std') diff --git a/src/std/buffer.c b/src/std/buffer.c index 3fc5184..42b1a0f 100644 --- a/src/std/buffer.c +++ b/src/std/buffer.c @@ -1,4 +1,5 @@ #include "../../include/std/buffer.h" +#include #include #include @@ -25,18 +26,28 @@ static int tsl_buffer_ensure_capacity(TslBuffer *self, size_t new_size) { new_size = new_capacity; } new_ptr = realloc(self->data, new_size); - if(!new_ptr) + if(!new_ptr) { + fprintf(stderr, "Error: buffer append failed. Reason: out of memory\n"); return 0; + } self->data = new_ptr; self->capacity = new_size; return 1; } -int tsl_buffer_append(TslBuffer *self, void *data, size_t size) { +int tsl_buffer_append(TslBuffer *self, const void *data, size_t size) { if(!tsl_buffer_ensure_capacity(self, self->size + size)) - return 1; + return 0; memcpy((char*)self->data + self->size, data, size); self->size += size; - return 0; + return 1; +} + +void* tsl_buffer_begin(TslBuffer *self) { + return self->data; +} + +void* tsl_buffer_end(TslBuffer *self) { + return (char*)self->data + self->size; } diff --git a/src/std/hash_map.c b/src/std/hash_map.c new file mode 100644 index 0000000..a0d656d --- /dev/null +++ b/src/std/hash_map.c @@ -0,0 +1,170 @@ +#include "../../include/std/hash_map.h" +#include +#include +#include +#include + +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) { + free(self->buckets_data); +} + +typedef struct TslHashMapNode TslHashMapNode; +struct TslHashMapNode { + void *data; + TslHashMapNode *next; +}; + +static void hash_map_node_init(TslHashMapNode *self) { + self->data = NULL; + self->next = NULL; +} + +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); +} + +static int tsl_hash_map_append_bucket(TslHashMapNode **head_node, uint64_t hash, const TslStringView *key, size_t size, const void *data) { + TslHashMapNode *next_node; + uint8_t *node_data = malloc(sizeof(hash) + sizeof(size) + size); + 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; + } + hash_map_node_init(next_node); + + memcpy(node_data, &hash, sizeof(hash)); + memcpy(node_data + sizeof(hash), &key->size, sizeof(key->size)); + memcpy(node_data + sizeof(hash) + sizeof(key->size), key->data, key->size); + 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); + + if(*head_node) { + (*head_node)->data = node_data; + (*head_node)->next = 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; + void *new_ptr; + if(new_size <= self->num_items) + return 1; + + if(new_capacity == 0) + new_capacity = 8; + + while(new_capacity < new_size) { + new_capacity *= 2; + } + + 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 + self->buckets_size); + TslHashMapNode **bucket_end = (TslHashMapNode**)((char*)self->buckets_data + self->buckets_capacity); + while(bucket != bucket_end) { + *bucket = NULL; + ++bucket; + } + } + + { + TslHashMapNode **bucket = (TslHashMapNode**)self->buckets_data; + TslHashMapNode **bucket_end = (TslHashMapNode**)((char*)self->buckets_data + self->buckets_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 */ + 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 = hash & (self->buckets_capacity - 1); + 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; + } + } + + prev_node = node; + node = node->next; + } + ++bucket_index; + ++bucket; + } + } + 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)); + if(!tsl_hash_map_ensure_bucket_capacity(self, self->buckets_size + size)) + return 0; + + index = hash & (self->buckets_capacity - 1); + bucket = (TslHashMapNode**)self->buckets_data + index; + return tsl_hash_map_append_bucket(bucket, hash, key, size, data); +} + +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 = hash & (self->buckets_capacity - 1); + 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; +} -- cgit v1.2.3