diff options
| -rw-r--r-- | include/moslib/ds/hashmap.h | 16 | ||||
| -rw-r--r-- | src/ds/hashmap.c | 29 |
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); } |