diff options
| author | Jake Koroman <jake@jakekoroman.com> | 2026-04-10 15:52:32 -0400 |
|---|---|---|
| committer | Jake Koroman <jake@jakekoroman.com> | 2026-04-10 15:52:32 -0400 |
| commit | 93a9ca1896754af7400c6534adc3cc9c1ea727d0 (patch) | |
| tree | 2c4aa36faa8b5b50e2844f1056f617b24fbe6344 /jrk.h | |
| parent | eaeca17334fe3b8c944af2ef51be35debf6ced96 (diff) | |
brand new and better hash map.
Diffstat (limited to 'jrk.h')
| -rw-r--r-- | jrk.h | 266 |
1 files changed, 172 insertions, 94 deletions
@@ -301,100 +301,178 @@ bool jrk_sb_read_entire_file(jrk_String_Builder*, const char*); #define JRK_FNV1A_64_PRIME 0x100000001B3 u64 jrk_fnv1a_64(const u8*, u64); -#define jrk_hm_prototype(type, max_key_size) \ - typedef struct { \ - char key[(max_key_size)]; \ - type val; \ - } jrk_Hash_Map_Item_##type; \ - \ - typedef struct { \ - jrk_Hash_Map_Item_##type *items; \ - u64 capacity; \ - } jrk_Hash_Map_##type; \ - \ - bool jrk_hm_##type##_init(jrk_Hash_Map_##type *map, jrk_Hash_Map_Item_##type *items, u64 items_cap); \ - bool jrk_hm_##type##_push(jrk_Hash_Map_##type *map, char *key, type val); \ - bool jrk_hm_##type##_get(jrk_Hash_Map_##type *map, char *key, type *outval); - -#define jrk_hm_impl(type) \ - bool \ - jrk_hm_##type##_init(jrk_Hash_Map_##type *map, jrk_Hash_Map_Item_##type *items, u64 items_cap) \ - { \ - if (!map) { \ - fprintf(stderr, "error: failed to init hashmap: map pointer is NULL\n"); \ - return false; \ - } \ - if (!items) { \ - fprintf(stderr, "error: failed to init hashmap: buf pointer is NULL\n"); \ - return false; \ - } \ - map->items = items; \ - map->capacity = items_cap; \ - return true; \ - } \ - \ - bool \ - jrk_hm_##type##_push(jrk_Hash_Map_##type *map, char *key, type val) \ - { \ - if (!key) { \ - fprintf(stderr, "error: failed to push key into hashmap: key pointer is NULL\n"); \ - return false; \ - } \ - if (!map) { \ - fprintf(stderr, "error: failed to push key '%s' into hashmap: map pointer is NULL\n", key); \ - return false; \ - } \ - u64 keylen = sizeof(map->items->key); \ - u64 idx = jrk_fnv1a_64((u8 *) key, strnlen(key, keylen)) % map->capacity; \ - jrk_Hash_Map_Item_##type *item = &map->items[idx]; \ - if (item->key[0] != 0 && 0 != strncmp(item->key, key, sizeof(map->items->key))) \ - printf("%s collision with %s\n", key, item->key); \ - for (; item < &map->items[map->capacity] && item->key[0] != 0 && 0 != strncmp(item->key, key, keylen); ++item); \ - if (item == &map->items[map->capacity]) { \ - for (item = &map->items[0]; item < &map->items[idx] && item->key[0] != 0; ++item); \ - if (item == &map->items[idx]) { \ - fprintf(stderr, "error: no space found for key '%s': hashmap is full\n", key); \ - return false; \ - } \ - } \ - memcpy(item->key, key, strnlen(key, _JRK_MAX_STRNLEN)); \ - item->val = val; \ - return true; \ - } \ - \ - bool \ - jrk_hm_##type##_get(jrk_Hash_Map_##type *map, char *key, type *outval) \ - { \ - if (!key) { \ - fprintf(stderr, "error: failed to get key from hashmap: key pointer is NULL\n"); \ - return false; \ - } \ - if (!map) { \ - fprintf(stderr, "error: failed to get key '%s' from hashmap: map pointer is NULL\n", key); \ - return false; \ - } \ - if (!outval) { \ - fprintf(stderr, "error: failed to get key '%s' from hashmap: outval pointer is NULL\n", key); \ - return false; \ - } \ - u64 keylen = sizeof(map->items->key); \ - u64 idx = jrk_fnv1a_64((u8 *) key, strnlen(key, keylen)) % map->capacity; \ - jrk_Hash_Map_Item_##type *item = &map->items[idx]; \ - if (0 == strncmp(item->key, key, keylen)) { \ - *outval = item->val; \ - return true; \ - } \ - for (; item < &map->items[map->capacity] && 0 != strncmp(item->key, key, keylen); ++item) \ - if (item->key[0] == 0) \ - return false; \ - if (item == &map->items[map->capacity]) { \ - for (item = &map->items[0]; item < &map->items[idx] && 0 != strncmp(item->key, key, keylen); ++item); \ - if (item == &map->items[idx]) \ - return false; \ - } \ - *outval = item->val; \ - return true; \ - } +#ifndef JRK_HM_DEFAULT_ALLOC_FN + #define JRK_HM_DEFAULT_ALLOC_FN jrk_ecalloc +#endif + +#ifndef JRK_HM_DEFAULT_FREE_FN + #define JRK_HM_DEFAULT_FREE_FN free +#endif + +typedef jrk_array_alloc_function_t jrk_hm_alloc_function_t; +typedef jrk_array_realloc_function_t jrk_hm_realloc_function_t; + +#define __jrk_hm_alloc(hm, count, len) (hm)->allocfn ? (hm)->allocfn((count), (len), (hm)->allocfn_user) : JRK_HM_DEFAULT_ALLOC_FN((count), (len)) + +#define jrk_hm_prototype(type, fnname, typename) \ + typedef struct { \ + jrk_String key; \ + type val; \ + } jrk_Hash_Map_Item_##typename; \ + \ + typedef struct { \ + jrk_Hash_Map_Item_##typename *items; \ + u64 len; \ + u64 capacity; \ + jrk_hm_alloc_function_t allocfn; \ + void *allocfn_user; \ + } jrk_Hash_Map_##typename; \ + \ + bool jrk_hm_##fnname##_grow(jrk_Hash_Map_##typename*); \ + jrk_Hash_Map_Item_##typename *jrk_hm_##fnname##_get_spot(jrk_Hash_Map_##typename*,jrk_String); \ + bool jrk_hm_##fnname##_push(jrk_Hash_Map_##typename*,jrk_String,type); \ + bool jrk_hm_##fnname##_push_no_alloc(jrk_Hash_Map_##typename*,jrk_String,type); \ + bool jrk_hm_##fnname##_get(const jrk_Hash_Map_##typename*,jrk_String,type*); \ + bool jrk_hm_##fnname##_init(jrk_Hash_Map_##typename*,u64); \ + bool jrk_hm_##fnname##_init_ex(jrk_Hash_Map_##typename*,u64,jrk_hm_alloc_function_t,void*); + +#define jrk_hm_impl(type, fnname, typename) \ + jrk_Hash_Map_Item_##fnname * \ + jrk_hm_##fnname##_get_spot(jrk_Hash_Map_##typename *hm, jrk_String key) \ + { \ + jrk_Hash_Map_Item_##typename *result = NULL; \ + u64 idx = jrk_fnv1a_64((u8 *)key.data, key.len) % hm->capacity; \ + result = &hm->items[idx]; \ + for (; result < &hm->items[hm->capacity] && result->key.len > 0 && !jrk_string_equals_exact(key, result->key); ++result); \ + if (result == &hm->items[hm->capacity]) { \ + for (result = &hm->items[0]; result < &hm->items[idx] && result->key.len > 0; ++result); \ + } \ + return result; \ + } \ + \ + bool \ + jrk_hm_##fnname##_push_no_alloc(jrk_Hash_Map_##typename *hm, jrk_String key, type val) \ + { \ + if (hm->len + 1 > hm->capacity) { \ + if (!jrk_hm_##fnname##_grow(hm)) return false; \ + } \ + jrk_Hash_Map_Item_##typename *item = jrk_hm_##fnname##_get_spot(hm, key); \ + jrk_Hash_Map_Item_##typename new_item = (jrk_Hash_Map_Item_##typename) { \ + .key = key, \ + .val = val \ + }; \ + *item = new_item; \ + hm->len++; \ + return true; \ + } \ + \ + bool \ + jrk_hm_##fnname##_push(jrk_Hash_Map_##typename *hm, jrk_String key, type val) \ + { \ + if (hm->len + 1 > hm->capacity) { \ + if (!jrk_hm_##fnname##_grow(hm)) return false; \ + } \ + jrk_Hash_Map_Item_##typename *item = jrk_hm_##fnname##_get_spot(hm, key); \ + if (jrk_string_equals_exact(key, item->key)) { \ + item->val = val; \ + return true; \ + } \ + char *allocd_key = __jrk_hm_alloc(hm, key.len, 1); \ + if (!allocd_key) return false; \ + memcpy(allocd_key, key.data, key.len); \ + jrk_String new_key = (jrk_String) { \ + .data = allocd_key, \ + .len = key.len, \ + }; \ + jrk_Hash_Map_Item_##typename new_item = (jrk_Hash_Map_Item_##typename) { \ + .key = new_key, \ + .val = val \ + }; \ + *item = new_item; \ + hm->len++; \ + return true; \ + } \ + \ + bool \ + jrk_hm_##fnname##_get(const jrk_Hash_Map_##typename *hm, jrk_String key, type *outval) \ + { \ + u64 idx = jrk_fnv1a_64((u8 *)key.data, key.len) % hm->capacity; \ + jrk_Hash_Map_Item_##typename *item = &hm->items[idx]; \ + if (jrk_string_equals_exact(key, item->key)) { \ + *outval = item->val; \ + return true; \ + } \ + for (; item < &hm->items[hm->capacity] && !jrk_string_equals_exact(key, item->key); ++item) { \ + if (item->key.len == 0) \ + return false; \ + } \ + if (item == &hm->items[hm->capacity]) { \ + for (item = &hm->items[0]; item < &hm->items[idx] && !jrk_string_equals_exact(key, item->key); ++item); \ + if (item == &hm->items[idx]) \ + return false; \ + } \ + *outval = item->val; \ + return true; \ + } \ + \ + bool \ + jrk_hm_##fnname##_init_ex(jrk_Hash_Map_##typename *hm, u64 capacity, jrk_hm_alloc_function_t allocfn, void *allocfn_user) \ + { \ + hm->allocfn = allocfn ? allocfn : NULL; \ + hm->allocfn_user = allocfn_user ? allocfn_user : NULL; \ + hm->len = 0; \ + hm->capacity = capacity; \ + hm->items = __jrk_hm_alloc(hm, hm->capacity, sizeof(jrk_Hash_Map_Item_##typename)); \ + \ + return true; \ + } \ + \ + bool \ + jrk_hm_##fnname##_init(jrk_Hash_Map_##typename *hm, u64 capacity) \ + { \ + return jrk_hm_##fnname##_init_ex(hm, capacity, NULL, NULL); \ + } \ + \ + void \ + jrk_hm_##fnname##_destroy(jrk_Hash_Map_##typename *hm) \ + { \ + if (hm->items && !hm->allocfn) { \ + for (u64 i = 0; i < hm->capacity; ++i) { \ + if (hm->items[i].key.data) \ + JRK_HM_DEFAULT_FREE_FN((void *)hm->items[i].key.data); \ + } \ + JRK_HM_DEFAULT_FREE_FN(hm->items); \ + } \ + } \ + \ + bool \ + jrk_hm_##fnname##_grow(jrk_Hash_Map_##typename *hm) \ + { \ + jrk_Hash_Map_##typename tmp_map = {0}; \ + tmp_map.capacity = hm->capacity * 2; \ + tmp_map.items = __jrk_hm_alloc(hm, tmp_map.capacity, sizeof(jrk_Hash_Map_Item_##typename)); \ + if (!tmp_map.items) return false; \ + tmp_map.len = hm->len; \ + for (u64 i = 0; i < hm->capacity; ++i) { \ + jrk_Hash_Map_Item_##typename *item = &hm->items[i]; \ + if (item->key.len > 0) { \ + if (!jrk_hm_##fnname##_push_no_alloc(&tmp_map, item->key, item->val)) { \ + free(tmp_map.items); \ + return false; \ + } \ + } \ + } \ + if (hm->items && !hm->allocfn) \ + JRK_HM_DEFAULT_FREE_FN(hm->items); \ + hm->items = tmp_map.items; \ + hm->capacity *= 2; \ + hm->len = tmp_map.len; \ + return true; \ + } + +#define jrk_hm_prototype_and_impl(type, fnname, typename) \ + jrk_hm_prototype(type, fnname, typename); \ + jrk_hm_impl(type, fnname, typename) #ifdef JRK_IMPLEMENTATION #include <ctype.h> |