aboutsummaryrefslogtreecommitdiff
path: root/src/std
diff options
context:
space:
mode:
authordec05eba <dec05eba@protonmail.com>2020-01-20 23:00:39 +0100
committerdec05eba <dec05eba@protonmail.com>2020-01-20 23:00:39 +0100
commit108018e3e7326dabbbef568ab08bc5cebf5d427b (patch)
tree7c9a522276aea7015638492592eba02615b78d43 /src/std
parent50c928d224bff0af322f23a7d2b842cd54aa2e68 (diff)
Add arithmetic, implement hash map
Diffstat (limited to 'src/std')
-rw-r--r--src/std/buffer.c19
-rw-r--r--src/std/hash_map.c170
2 files changed, 185 insertions, 4 deletions
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 <stdio.h>
#include <stdlib.h>
#include <string.h>
@@ -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 <assert.h>
+#include <string.h>
+#include <stdlib.h>
+#include <stdio.h>
+
+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;
+}