7 files changed, 233 insertions, 43 deletions

diff --git a/README.md b/README.md
index 1978ea5..b36913f 100644
--- a/README.md
+++ b/README.md
@@ -8,7 +8,7 @@ Defnitely not the best implementations ever made, but they're mine, so idc.
 - testing framework
 - dynamic array implementation
 - length aware string slices
+- hashmap implementation
 
 ## Planned:
-- hashmap implementation
-- a bunch of other stuff most certainly
+- heap implementation
diff --git a/include/moslib/ds/hashmap.h b/include/moslib/ds/hashmap.h
index c4af82d..b727c6c 100644
--- a/include/moslib/ds/hashmap.h
+++ b/include/moslib/ds/hashmap.h
@@ -54,6 +54,12 @@
 //
 // ----------------------------------------------------------------------------------------------------
 //
+// To set the hashmap load factor, define (before including the header):
+//
+//      #define MOS_HM_LOAD_FACTOR <desired_load_factor_in_%>
+//
+// ----------------------------------------------------------------------------------------------------
+//
 // To put a key/value pair or an entry into a hashmap use:
 //
 //      hm_put(hm, key, val);
@@ -105,6 +111,11 @@
 #ifndef MOSLIB_DS_HASHMAP_H
 #define MOSLIB_DS_HASHMAP_H
 
+// Load factor (in %) to use in hashmap
+#ifndef MOS_HM_LOAD_FACTOR
+#define MOS_HM_LOAD_FACTOR 50
+#endif // MOS_HM_LOAD_FACTOR
+
 #ifndef MOS_FORCE_PREFIXES
 
 #define HM_DEF MOS_HM_DEF
@@ -163,7 +174,7 @@ typedef struct {
 //   ...
 //     value of the entry to put
 //     variadic to make things like (struct Val){1,1} work properly
-#define mos_hm_put(hm, key, ...)
+#define mos_hm_put(hm, k, ...) (mos_hm_ini, (hm)->key = k, (hm)->val = __VA_ARGS__, mos_hm_put_fn(&(hm), mos_hm_fn_args))
 
 // Put a given entry in the hashmap
 // If entry of the same key exists - overwrites it
@@ -175,7 +186,7 @@ typedef struct {
 //   ...
 //     entry to put into hashmap
 //     variadic to make things like (struct Entry){"key","val"} work properly
-#define mos_hm_put_e(hm, ...)
+#define mos_hm_put_e(hm, ...) (mos_hm_ini, (hm)[0] = __VA_ARGS__, mos_hm_put_fn(&(hm), mos_hm_fn_args))
 
 // Get the value of entry with specific key
 //
@@ -183,12 +194,12 @@ typedef struct {
 //   hm
 //     hashmap to get value from
 //
-//   key
+//   k
 //     key of the entry to get the value of
 //
 // Returns:
 //   value of the entry with given key or 0 if no such entry exist
-#define mos_hm_get(hm, key) 0
+#define mos_hm_get(hm, k) (mos_hm_ini, (hm)->key = k, (hm)[mos_hm_get_fn(hm, mos_hm_fn_args)].val)
 
 // Get a pointer to an entry with specific key in hashmap
 //
@@ -196,12 +207,12 @@ typedef struct {
 //   hm
 //     hashmap to get an entry from
 //
-//   key
+//   k
 //     key of the entry to get
 //
 // Returns:
 //   pointer to the entry or NULL if no entry with such key exists
-#define mos_hm_get_e(hm, key) NULL
+#define mos_hm_get_e(hm, k) (mos_hm_ini, (hm)->key = k, mos_hm_get_e_fn(hm, mos_hm_fn_args))
 
 // Get a pointer to the first entry in the hashmap
 //
@@ -211,7 +222,7 @@ typedef struct {
 //
 // Returns:
 //   pointer to the first entry or NULL if hashmap is empty
-#define mos_hm_first(hm) NULL
+#define mos_hm_first(hm) mos_hm_first_fn(hm, sizeof(*(hm)))
 
 // Get the pointer to the next entry in the hashmap from the pointer to the current one
 // If pointer is NULL - gets the first entry from the hashmap
@@ -225,7 +236,7 @@ typedef struct {
 //
 // Returns:
 //   pointer to the next entry or NULL if there's no more entries
-#define mos_hm_next(hm, curr) NULL
+#define mos_hm_next(hm, curr) mos_hm_next_fn(hm, curr, sizeof(*(hm)))
 
 // Free the hashmap
 //
@@ -234,7 +245,17 @@ typedef struct {
 //     hashmap to free
 extern void mos_hm_free(void *hm);
 
+#define mos_hm_ini mos_hm_init(&(hm), sizeof(*(hm)))
+extern void mos_hm_init(void *p_hm, size_t entry_size);
+
+#define mos_hm_fn_args &(hm)->key, sizeof(*(hm)), sizeof((hm)->key)
+
 // Function prototypes for macros
 extern void *mos_hm_new_fn(MosHmInitArgs args);
+extern void mos_hm_put_fn(void *p_hm, void *key, size_t entry_size, size_t key_size);
+extern size_t mos_hm_get_fn(void *hm, void *key, size_t entry_size, size_t key_size);
+extern void *mos_hm_get_e_fn(void *hm, void *key, size_t entry_size, size_t key_size);
+extern void *mos_hm_first_fn(void *hm, size_t entry_size);
+extern void *mos_hm_next_fn(void *hm, void *curr, size_t entry_size);
 
 #endif // MOSLIB_DS_HASHMAP_H
diff --git a/src/ds/array.c b/src/ds/array.c
index 61978bf..3d0baa3 100644
--- a/src/ds/array.c
+++ b/src/ds/array.c
@@ -12,21 +12,21 @@ typedef struct {
     size_t cap;
 } Header;
 
-Header *arr2hdr(const void *arr) {
+static Header *arr2hdr(const void *arr) {
     return (Header *)arr - 1;
 }
 
-void *hdr2arr(Header *hdr) {
+static void *hdr2arr(Header *hdr) {
     return hdr + 1;
 }
 
-void *init(size_t cap, size_t el_size) {
+static void *init(size_t cap, size_t el_size) {
     Header *hdr = mos_safe_malloc(sizeof(Header) + cap * el_size);
     *hdr = (Header){.len = 0, .cap = cap};
     return hdr2arr(hdr);
 }
 
-void *expand(void *arr, size_t min_cap, size_t el_size) {
+static void *expand(void *arr, size_t min_cap, size_t el_size) {
     Header *hdr = arr2hdr(arr);
     if (hdr->cap >= min_cap)
         return arr;
diff --git a/src/ds/hashmap.c b/src/ds/hashmap.c
index 8a3608a..ca9ce62 100644
--- a/src/ds/hashmap.c
+++ b/src/ds/hashmap.c
@@ -1,52 +1,98 @@
+#include <stddef.h>
 #define MOS_FORCE_PREFIXES
 #include "moslib/ds/hashmap.h"
 
+#include <stdlib.h>
 #include <string.h>
 
 #include "moslib/safe.h"
 #include "moslib/string.h"
 
+#define INIT_CAP 16
+
 typedef struct {
+    uint8_t *filled;
     size_t size;
     size_t cap;
     uint32_t (*hash)(const void *key);
     int (*eq)(const void *key1, const void *key2);
 } Header;
 
-Header *hm2hdr(const void *hm) {
+static Header *hm2hdr(const void *hm) {
     return (Header *)hm - 1;
 }
 
-void *hdr2hm(Header *hdr) {
+static void *hdr2hm(Header *hdr) {
     return hdr + 1;
 }
 
-uint32_t default_hash(const void *key, size_t key_size) {
-    return 0;
+static int filled(void *hm, size_t index) {
+    return hm2hdr(hm)->filled[index / 8] & (1 << index % 8);
+}
+
+static void fill(void *hm, size_t index) {
+    hm2hdr(hm)->filled[index / 8] |= (1 << index % 8);
 }
 
-int default_eq(const void *key1, const void *key2, size_t key_size) {
+// FNV-1a
+static uint32_t default_hash(const void *key, size_t key_size) {
+    const uint8_t *p = key;
+    uint32_t h = 2166136261;
+    for (size_t i = 0; i < key_size; i++) {
+        h ^= p[i];
+        h *= 16777619;
+    }
+    return h;
+}
+
+static int default_eq(const void *key1, const void *key2, size_t key_size) {
     return memcmp(key1, key2, key_size) == 0;
 }
 
-uint32_t string_hash(const void *key) {
-    return 0;
+static uint32_t string_hash(const void *key) {
+    const char *str = *(char **)key;
+    return default_hash(str, strlen(str));
 }
 
-int string_eq(const void *key1, const void *key2) {
-    return strcmp(key1, key2) == 0;
+static int string_eq(const void *key1, const void *key2) {
+    return strcmp(*(char **)key1, *(char **)key2) == 0;
 }
 
-uint32_t slice_hash(const void *key) {
-    return 0;
+static uint32_t slice_hash(const void *key) {
+    const MosStringSlice *slice = key;
+    return default_hash(slice->data, slice->len);
 }
 
-int slice_eq(const void *key1, const void *key2) {
+static int slice_eq(const void *key1, const void *key2) {
     return mos_ss_eq(*(MosStringSlice *)key1, *(MosStringSlice *)key2);
 }
 
+void mos_hm_init(void *p_hm, size_t entry_size) {
+    if (!*(void **)p_hm) {
+        Header *hdr = mos_safe_malloc(sizeof(Header) + (INIT_CAP + 1) * entry_size);
+        *hdr = (Header){
+            .filled = mos_safe_calloc((INIT_CAP - 1) / 8 + 1, 1),
+            .size = 0,
+            .cap = INIT_CAP,
+            .hash = NULL,
+            .eq = NULL,
+        };
+        *(void **)p_hm = hdr2hm(hdr);
+        return;
+    }
+
+    Header *hdr = hm2hdr(*(void **)p_hm);
+    if (hdr->cap == 0) {
+        hdr = mos_safe_realloc(hdr, sizeof(Header) + (INIT_CAP + 1) * entry_size);
+        hdr->filled = mos_safe_calloc((INIT_CAP - 1) / 8 + 1, 1);
+        hdr->cap = INIT_CAP;
+        *(void **)p_hm = hdr2hm(hdr);
+    }
+}
+
 void *mos_hm_new_fn(MosHmInitArgs args) {
     Header *hdr = mos_safe_malloc(sizeof(Header));
+    hdr->filled = NULL;
     hdr->cap = 0;
     hdr->size = 0;
 
@@ -70,16 +116,138 @@ void *mos_hm_new_fn(MosHmInitArgs args) {
     if (args.hash != NULL)
         hdr->hash = args.hash;
 
-    return hdr;
+    return hdr2hm(hdr);
+}
+
+static size_t probe(void *hm, void *key, size_t entry_size, size_t key_size, size_t key_off) {
+    Header *hdr = hm2hdr(hm);
+    uint32_t hash = hdr->hash ? hdr->hash(key) : default_hash(key, key_size);
+    size_t i = hash % hdr->cap;
+
+    for (size_t it = 0; it < hdr->cap; it++) {
+        void *key2 = (char *)hm + (i + 1) * entry_size + key_off;
+        if (!filled(hm, i) || (hdr->eq ? hdr->eq(key, key2) : default_eq(key, key2, key_size))) {
+            return i;
+        }
+        i = (i + 1) % hdr->cap;
+    }
+    return 0;
+}
+
+static void expand(void *p_hm, size_t entry_size, size_t key_size, size_t key_off) {
+    void *hm = *(void **)p_hm;
+    Header *hdr = hm2hdr(hm);
+
+    Header *new_hdr = mos_safe_malloc(sizeof(Header) + (2 * hdr->cap + 1) * entry_size);
+    *new_hdr = (Header){
+        .filled = mos_safe_calloc((2 * hdr->cap - 1) / 8 + 1, 1),
+        .size = hdr->size,
+        .cap = 2 * hdr->cap,
+        .hash = hdr->hash,
+        .eq = hdr->eq,
+    };
+    void *new_hm = hdr2hm(new_hdr);
+
+    for (size_t i = 0; i < hdr->cap; i++) {
+        if (!filled(hm, i))
+            continue;
+
+        void *entry = (char *)hm + (i + 1) * entry_size;
+        void *key = (char *)entry + key_off;
+
+        uint32_t hash = new_hdr->hash ? new_hdr->hash(key) : default_hash(key, key_size);
+        size_t j = hash % new_hdr->cap;
+        for (size_t it = 0; it < new_hdr->cap; it++) {
+            if (!filled(new_hm, j)) {
+                memcpy((char *)new_hm + (j + 1) * entry_size, entry, entry_size);
+                fill(new_hm, j);
+                break;
+            }
+            j = (j + 1) % new_hdr->cap;
+        }
+    }
+
+    free(hdr->filled);
+    free(hdr);
+    *(void **)p_hm = new_hm;
 }
 
-#define mos_hm_put(hm, key, ...)
-#define mos_hm_put_e(hm, ...)
-#define mos_hm_get(hm, key) 0
-#define mos_hm_get_e(hm, key) NULL
-#define mos_hm_first(hm) NULL
-#define mos_hm_next(hm, curr) NULL
+void mos_hm_put_fn(void *p_hm, void *key, size_t entry_size, size_t key_size) {
+    size_t key_off = (char *)key - *(char **)p_hm;
+    Header *hdr = hm2hdr(*(void **)p_hm);
+
+    void *hm = *(void **)p_hm;
+    size_t i = probe(hm, key, entry_size, key_size, key_off);
+    memcpy((char *)hm + (i + 1) * entry_size, hm, entry_size);
+    if (!filled(hm, i)) {
+        hdr->size++;
+        fill(hm, i);
+    }
+
+    if (hdr->size * 100 > hdr->cap * MOS_HM_LOAD_FACTOR)
+        expand(p_hm, entry_size, key_size, key_off);
+}
+
+size_t mos_hm_get_fn(void *hm, void *key, size_t entry_size, size_t key_size) {
+    size_t key_off = (char *)key - (char *)hm;
+    size_t i = probe(hm, key, entry_size, key_size, key_off);
+    if (!filled(hm, i)) {
+        memset(hm, 0, entry_size);
+        return 0;
+    }
+    return i + 1;
+}
+
+void *mos_hm_get_e_fn(void *hm, void *key, size_t entry_size, size_t key_size) {
+    size_t key_off = (char *)key - (char *)hm;
+    size_t i = probe(hm, key, entry_size, key_size, key_off);
+    if (!filled(hm, i))
+        return NULL;
+    return (char *)hm + (i + 1) * entry_size;
+}
+
+void *mos_hm_first_fn(void *hm, size_t entry_size) {
+    if (!hm)
+        return NULL;
+
+    Header *hdr = hm2hdr(hm);
+    if (hdr->size == 0)
+        return NULL;
+
+    for (size_t i = 0; i < hdr->cap; i++) {
+        if (filled(hm, i))
+            return (char *)hm + (i + 1) * entry_size;
+    }
+    return NULL;
+}
+
+void *mos_hm_next_fn(void *hm, void *curr, size_t entry_size) {
+    if (!hm)
+        return NULL;
+
+    Header *hdr = hm2hdr(hm);
+    if (hdr->size == 0)
+        return NULL;
+
+    if (!curr)
+        return mos_hm_first_fn(hm, entry_size);
+
+    size_t index = ((char *)curr - (char *)hm) / entry_size;
+    if (index >= hdr->cap)
+        return NULL;
+
+    for (size_t i = index; i < hdr->cap; i++) {
+        if (filled(hm, i))
+            return (char *)hm + (i + 1) * entry_size;
+    }
+    return NULL;
+}
 
 void mos_hm_free(void *hm) {
-    (void)hm;
+    if (!hm)
+        return;
+
+    Header *hdr = hm2hdr(hm);
+    free(hdr->filled);
+    free(hdr);
 }
diff --git a/src/safe.c b/src/safe.c
index 6e22d0a..1b75bf2 100644
--- a/src/safe.c
+++ b/src/safe.c
@@ -8,7 +8,7 @@
 
 #define ERR_MESS(...) err_mess(info, __VA_ARGS__)
 
-void err_mess(MosSafeErrInfo info, const char *msg, ...) {
+static void err_mess(MosSafeErrInfo info, const char *msg, ...) {
     va_list args;
     va_start(args, msg);
     fprintf(stderr, "%s:%d - fatal error in function %s:\n", info.file, info.line, info.func);
diff --git a/src/tester.c b/src/tester.c
index 4ac7987..b36a4d2 100644
--- a/src/tester.c
+++ b/src/tester.c
@@ -20,8 +20,8 @@
 
 #define RENDER_WIDTH 80
 
-int failed = 0;
-FILE *dev_null = NULL;
+static int failed = 0;
+static FILE *dev_null = NULL;
 
 typedef struct {
     int *outs;
@@ -30,7 +30,7 @@ typedef struct {
     size_t out_cap;
 } Outputs;
 
-Outputs suppressed = {
+static Outputs suppressed = {
     .outs = NULL,
     .ogs = NULL,
     .n_outs = 0,
@@ -40,7 +40,7 @@ Outputs suppressed = {
 #define print_color(template, ...) printf("\033[%dm" template "\033[0m", __VA_ARGS__)
 #define nl printf("\n")
 
-void print_center(const char *text, int color, char padding_char) {
+static void print_center(const char *text, int color, char padding_char) {
     size_t post_char_count = (RENDER_WIDTH - strlen(text)) / 2;
     size_t pre_char_count = RENDER_WIDTH - post_char_count - strlen(text);
 
@@ -107,9 +107,9 @@ void mos_test_assert(int expression, const char *fail_message) {
     }
 }
 
-jmp_buf jump_env;
-int expected_code;
-const char *fn_name;
+static jmp_buf jump_env;
+static int expected_code;
+static const char *fn_name;
 void exit(int code) {
     if (code != expected_code) {
         failed = 1;
diff --git a/tests/ds/hashmap_tests.c b/tests/ds/hashmap_tests.c
index 49e4261..749564a 100644
--- a/tests/ds/hashmap_tests.c
+++ b/tests/ds/hashmap_tests.c
@@ -1,3 +1,4 @@
+#define _GNU_SOURCE
 #include "hashmap_tests.h"
 #include "moslib/ds/hashmap.h"
 
@@ -101,7 +102,7 @@ Test looping() {
     E items[] = {{1, 10}, {2, 20}, {3, 30}};
     arr_append_n(allowed, items, 3);
 
-    test_assert(memcmp(hm_first(hm), hm_next(hm, NULL), sizeof(E)), "hm_next(hm, NULL) != hm_first(hm)");
+    test_assert(memcmp(hm_first(hm), hm_next(hm, NULL), sizeof(E)) == 0, "hm_next(hm, NULL) != hm_first(hm)");
     E *e = NULL;
     while ((e = hm_next(hm, e))) {
         int flag = 0;