Convert hash map to gc, implement more instructions and call command

1 files changed, 194 insertions, 0 deletions

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 <assert.h>
+#include <string.h>
+#include <stdio.h>
+#include <gc.h>
+
+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;
+}