Add arithmetic, implement hash map

1 files changed, 170 insertions, 0 deletions

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;
+}