From 0ef02ddf28c626916da9d5c7081a01ab707be8ce Mon Sep 17 00:00:00 2001 From: Mosder Date: Sat, 12 Sep 2026 15:53:50 +0200 Subject: feat: implemented hashmap --- README.md | 4 +- include/moslib/ds/hashmap.h | 37 ++++++-- src/ds/array.c | 8 +- src/ds/hashmap.c | 208 +++++++++++++++++++++++++++++++++++++++----- src/safe.c | 2 +- src/tester.c | 14 +-- tests/ds/hashmap_tests.c | 3 +- 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 +// +// ---------------------------------------------------------------------------------------------------- +// // 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 #define MOS_FORCE_PREFIXES #include "moslib/ds/hashmap.h" +#include #include #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; -- cgit v1.2.3