fix: fixed naming, and some edge cases for hashmap

2 files changed, 24 insertions, 21 deletions

diff --git a/include/moslib/ds/hashmap.h b/include/moslib/ds/hashmap.h
index 4136ac2..ee5de6f 100644
--- a/include/moslib/ds/hashmap.h
+++ b/include/moslib/ds/hashmap.h
@@ -190,7 +190,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, k, ...) (mos_hm_ini, (hm)->key = k, (hm)->val = __VA_ARGS__, mos_hm_put_fn(&(hm), mos_hm_fn_args, MOS_HM_LOAD_FACTOR))
+#define mos_hm_put(hm, k, ...) (mos_hm_ini(hm), (hm)->key = k, (hm)->val = __VA_ARGS__, mos_hm_put_fn(&(hm), mos_hm_fn_args(hm), MOS_HM_LOAD_FACTOR))
 
 // Put a given entry in the hashmap
 // If entry of the same key exists - overwrites it
@@ -202,7 +202,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, ...) (mos_hm_ini, (hm)[0] = __VA_ARGS__, mos_hm_put_fn(&(hm), mos_hm_fn_args, MOS_HM_LOAD_FACTOR))
+#define mos_hm_put_e(hm, ...) (mos_hm_ini(hm), (hm)[0] = __VA_ARGS__, mos_hm_put_fn(&(hm), mos_hm_fn_args(hm), MOS_HM_LOAD_FACTOR))
 
 // Get the value of entry with specific key
 //
@@ -215,7 +215,7 @@ typedef struct {
 //
 // Returns:
 //   value of the entry with given key or 0 if no such entry exist
-#define mos_hm_get(hm, k) (mos_hm_ini, (hm)->key = k, (hm)[mos_hm_get_fn(hm, mos_hm_fn_args)].val)
+#define mos_hm_get(hm, k) (mos_hm_ini(hm), (hm)->key = k, (hm)[mos_hm_get_fn(hm, mos_hm_fn_args(hm))].val)
 
 // Get a pointer to an entry with specific key in hashmap
 //
@@ -228,7 +228,7 @@ typedef struct {
 //
 // Returns:
 //   pointer to the entry or NULL if no entry with such key exists
-#define mos_hm_get_e(hm, k) (mos_hm_ini, (hm)->key = k, mos_hm_get_e_fn(hm, mos_hm_fn_args))
+#define mos_hm_get_e(hm, k) (mos_hm_ini(hm), (hm)->key = k, mos_hm_get_e_fn(hm, mos_hm_fn_args(hm)))
 
 // Delete an entry with specific key from the hashmap
 //
@@ -241,7 +241,7 @@ typedef struct {
 //
 // Returns:
 //   1 if an entry of given key was deleted, 0 otherwise
-#define mos_hm_del(hm, k) (mos_hm_ini, (hm)->key = k, mos_hm_del_fn(hm, mos_hm_fn_args))
+#define mos_hm_del(hm, k) (mos_hm_ini(hm), (hm)->key = k, mos_hm_del_fn(hm, mos_hm_fn_args(hm)))
 
 // Get a pointer to the first entry in the hashmap
 //
@@ -281,17 +281,17 @@ extern size_t mos_hm_size(const void *hm);
 //     hashmap to free
 extern void mos_hm_free(void *hm);
 
-#define mos_hm_ini mos_hm_init(&(hm), sizeof(*(hm)))
+#define mos_hm_ini(hm) 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)
+#define mos_hm_fn_args(hm) &(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, uint8_t load_factor);
 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(const void *hm, const void *key, size_t entry_size, size_t key_size);
-extern int mos_hm_del_fn(const void *hm, const void *key, size_t entry_size, size_t key_size);
+extern int mos_hm_del_fn(void *hm, void *key, size_t entry_size, size_t key_size);
 extern void *mos_hm_first_fn(const void *hm, size_t entry_size);
 extern void *mos_hm_next_fn(const void *hm, const void *curr, size_t entry_size);
 
diff --git a/src/ds/hashmap.c b/src/ds/hashmap.c
index 60c85af..9cdc663 100644
--- a/src/ds/hashmap.c
+++ b/src/ds/hashmap.c
@@ -139,28 +139,29 @@ static size_t probe(const void *hm, const void *key, size_t entry_size, size_t k
     uint32_t hash = hdr->hash ? hdr->hash(key) : default_hash(key, key_size);
     size_t i = hash % hdr->cap;
 
-    size_t tomb = 0;
+    size_t tomb = -1;
     for (size_t it = 0; it < hdr->cap; it++) {
         void *key2 = (char *)hm + (i + 1) * entry_size + key_off;
         if (!filled(hm, i))
-            return tomb ? tomb : i;
+            return tomb != (size_t)-1 ? tomb : i;
         if (hdr->eq ? hdr->eq(key, key2) : default_eq(key, key2, key_size))
             return i;
-        if (put && tomb == 0 && dead(hm, i))
+        if (put && tomb == (size_t)-1 && dead(hm, i))
             tomb = i;
         i = (i + 1) % hdr->cap;
     }
-    return 0;
+    return -1;
 }
 
-static void expand(void *p_hm, size_t entry_size, size_t key_size, size_t key_off) {
+static void rehash(void *p_hm, size_t entry_size, size_t key_size, size_t key_off, uint8_t load_factor) {
     void *hm = *(void **)p_hm;
     Header *hdr = hm2hdr(hm);
+    size_t new_cap = (mos_hm_size(hm) * 400 >= hdr->cap * 3 * load_factor) ? 2 * hdr->cap : hdr->cap;
 
-    Header *new_hdr = mos_safe_malloc(sizeof(Header) + (2 * hdr->cap + 1) * entry_size);
+    Header *new_hdr = mos_safe_malloc(sizeof(Header) + (new_cap + 1) * entry_size);
     *new_hdr = (Header){
-        .filled = mos_safe_calloc((2 * hdr->cap - 1) / 8 + 1, 1),
-        .dead = mos_safe_calloc((2 * hdr->cap - 1) / 8 + 1, 1),
+        .filled = mos_safe_calloc((new_cap - 1) / 8 + 1, 1),
+        .dead = mos_safe_calloc((new_cap - 1) / 8 + 1, 1),
         .size = mos_hm_size(hm),
         .cap = 2 * hdr->cap,
         .hash = hdr->hash,
@@ -207,13 +208,13 @@ void mos_hm_put_fn(void *p_hm, void *key, size_t entry_size, size_t key_size, ui
     unkill(hm, i);
 
     if (hdr->size * 100 >= hdr->cap * load_factor)
-        expand(p_hm, entry_size, key_size, key_off);
+        rehash(p_hm, entry_size, key_size, key_off, load_factor);
 }
 
 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, 0);
-    if (!filled(hm, i) || dead(hm, i)) {
+    if (i == (size_t)-1 || !filled(hm, i) || dead(hm, i)) {
         memset(hm, 0, entry_size);
         return 0;
     }
@@ -223,15 +224,15 @@ size_t mos_hm_get_fn(void *hm, void *key, size_t entry_size, size_t key_size) {
 void *mos_hm_get_e_fn(const void *hm, const 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, 0);
-    if (!filled(hm, i) || dead(hm, i))
+    if (i == (size_t)-1 || !filled(hm, i) || dead(hm, i))
         return NULL;
     return (char *)hm + (i + 1) * entry_size;
 }
 
-int mos_hm_del_fn(const void *hm, const void *key, size_t entry_size, size_t key_size) {
+int mos_hm_del_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, 0);
-    if (!filled(hm, i) || dead(hm, i))
+    if (i == (size_t)-1 || !filled(hm, i) || dead(hm, i))
         return 0;
     kill(hm, i);
     return 1;
@@ -288,6 +289,8 @@ size_t mos_hm_size(const void *hm) {
     if (!hm)
         return 0;
     Header *hdr = hm2hdr(hm);
+    if (hdr->cap == 0)
+        return 0;
     return hdr->size - bit_count(hdr->dead, (hdr->cap - 1) / 8 + 1);
 }