initial commit (lol)

3 files changed, 193 insertions, 0 deletions

diff --git a/mons_collections/CMakeLists.txt b/mons_collections/CMakeLists.txt
new file mode 100644
index 0000000..9391863
--- /dev/null
+++ b/mons_collections/CMakeLists.txt
@@ -0,0 +1,29 @@
+cmake_minimum_required(VERSION 3.14)
+project(mons_collections LANGUAGES C)
+set(CMAKE_C_STANDARD 99)
+set(CMAKE_EXPORT_COMPILE_COMMANDS true)
+set(CMAKE_BUILD_TYPE "Debug")
+
+add_library(mons_collections
+    SHARED
+    ./src/hashmap.c
+)
+
+target_include_directories(mons_collections PUBLIC
+    "$<BUILD_INTERFACE:${CMAKE_CURRENT_SOURCE_DIR}>/include"
+    "$<INSTALL_INTERFACE:${CMAKE_INSTALL_INCLUDEDIR}>"
+)
+target_compile_options(mons_collections PRIVATE -coverage)
+target_link_options(mons_collections PRIVATE -coverage)
+
+include(CTest)
+
+function(TESTCASE NAME)
+    add_executable(test_${NAME} ./tests/${NAME}.c)
+    target_link_libraries(test_${NAME} PUBLIC mons_collections)
+    add_test(
+        NAME ${NAME}
+        COMMAND $<TARGET_FILE:test_${NAME}>
+    )
+endfunction()
+
diff --git a/mons_collections/include/hashmap.h b/mons_collections/include/hashmap.h
new file mode 100644
index 0000000..e5e59c4
--- /dev/null
+++ b/mons_collections/include/hashmap.h
@@ -0,0 +1,23 @@
+#ifndef MONS_HASHMAP_H
+#define MONS_HASHMAP_H
+
+typedef struct mons_hashmap_pair {
+    char *key;
+    void *value;
+    struct mons_hashmap_pair *next;
+} mons_hashmap_pair;
+
+typedef struct mons_hashmap {
+    mons_hashmap_pair **data;
+    unsigned int bucket_count;
+    unsigned int member_size;
+    unsigned int len;
+} mons_hashmap;
+
+mons_hashmap mons_hashmap_new(unsigned int member_size, unsigned int buckets);
+void mons_hashmap_free(mons_hashmap *hashmap);
+int mons_hashmap_insert(mons_hashmap *map, char *key, void *value);
+int mons_hashmap_get(mons_hashmap map, char *key, void *out);
+int mons_hashmap_remove(mons_hashmap *map, char *key);
+int mons_hashmap_at(mons_hashmap map, unsigned int index, mons_hashmap_pair *out);
+#endif
diff --git a/mons_collections/src/hashmap.c b/mons_collections/src/hashmap.c
new file mode 100644
index 0000000..c2ff172
--- /dev/null
+++ b/mons_collections/src/hashmap.c
@@ -0,0 +1,141 @@
+#include "hashmap.h"
+#include <stdlib.h>
+#include <string.h>
+#include <stdio.h>
+
+#define MONS_HASHMAP_MAX_LOAD_FACTOR 3.0f
+
+unsigned int djb2_hash(unsigned char *str, unsigned int bucket_count) {
+    unsigned long hash = 5381;
+    int c;
+
+    while ((c = *str++)) {
+        hash = ((hash << 5) + hash) + c;
+    }
+
+    return hash % bucket_count;
+}
+
+mons_hashmap mons_hashmap_new(unsigned int member_size, unsigned int buckets) {
+    mons_hashmap result = {
+        .member_size = member_size,
+        .bucket_count = buckets,
+        .data = calloc(buckets, sizeof(mons_hashmap_pair *)),
+    };
+    return result;
+}
+
+int mons_hashmap_rehash(mons_hashmap *map) {
+    // TODO: Expand number of buckets, re-hash all entries
+    return EXIT_SUCCESS;
+}
+
+int mons_hashmap_insert(mons_hashmap *map, char *key, void *value) {
+    unsigned int bucket = djb2_hash((unsigned char*)key, map->bucket_count);
+    mons_hashmap_pair *tail = map->data[bucket];
+    if (tail == NULL) {
+        map->data[bucket] = calloc(1, sizeof(mons_hashmap_pair *));
+        tail = map->data[bucket];       
+    } else {
+        mons_hashmap_pair *node = tail;
+        while(1) {
+            if(strcmp(key, node->key) == 0) {
+                memcpy(node->value, value, map->member_size);
+                return EXIT_SUCCESS;
+            }
+            if(node->next == NULL) {
+                tail = node;
+                break;
+            }
+            node = node->next;
+        }
+        tail->next = calloc(1, sizeof(mons_hashmap_pair *));
+        tail = tail->next;
+    }
+    tail->key = calloc(strlen(key) + 1, 1);
+    strcpy(tail->key, key);
+    tail->value = calloc(1, map->member_size);
+    memcpy(tail->value, value, map->member_size);
+    map->len++;
+    if (map->len / map->bucket_count > MONS_HASHMAP_MAX_LOAD_FACTOR) {
+        mons_hashmap_rehash(map);
+    }
+    return EXIT_SUCCESS;
+}
+
+int mons_hashmap_get(mons_hashmap map, char *key, void *out) {
+    unsigned int bucket = djb2_hash((unsigned char*)key, map.bucket_count);
+    mons_hashmap_pair *tail = map.data[bucket];
+    while(tail != NULL) {
+        if(strcmp(key, tail->key) == 0) {
+            memcpy(out, tail->value, map.member_size);
+            return EXIT_SUCCESS;
+        }
+        tail = tail->next;
+    }
+    return EXIT_FAILURE;
+}
+
+int mons_hashmap_remove(mons_hashmap *map, char *key) {
+    unsigned int bucket = djb2_hash((unsigned char*)key, map->bucket_count);
+    mons_hashmap_pair *tail = map->data[bucket];
+    mons_hashmap_pair *prev = NULL;
+    while(tail != NULL) {
+        if(strcmp(key, tail->key) == 0) {
+            if (prev == NULL) {
+                map->data[bucket] = tail->next;
+            } else {
+                prev->next = tail->next;
+            }
+            free(tail->key);
+            free(tail->value);
+            free(tail);
+            map->len--;
+            return EXIT_SUCCESS;
+        }
+        prev = tail;
+        tail = tail->next;
+    }
+    return EXIT_FAILURE;
+}
+
+void mons_hashmap_free(mons_hashmap *hashmap) {
+    for (int i = 0; i < hashmap->bucket_count; i++) {
+        mons_hashmap_pair *node = hashmap->data[i];
+        while(node != NULL) {
+            mons_hashmap_pair *next = node->next;
+            free(node->key);
+            free(node->value);
+            free(node);
+            node = next;
+        }
+    }
+    free(hashmap->data);
+    hashmap->data = NULL;
+    hashmap->bucket_count = 0;
+    hashmap->member_size = 0;
+    hashmap->len = 0;
+}
+
+int mons_hashmap_at(mons_hashmap map, unsigned int index, mons_hashmap_pair *out) {
+    mons_hashmap_pair **bucket = map.data;
+    mons_hashmap_pair *node = *bucket;
+    while(node == NULL) {
+        bucket++;
+        node = *bucket;
+    }
+    for(int i = 0; i < index; i++) {
+        if (node == NULL || node->next == NULL) {
+            bucket++;
+            node = *bucket;
+            while(node == NULL) {
+                bucket++;
+                node = *bucket;
+            }
+        } else {
+            node = node->next;
+        }
+    }
+    *out = *node;
+    return EXIT_SUCCESS;
+}