commit 65df062e8ad1eacf7ebb1b957aa533eee335c59e
parent 38eadc144b00bec2bbcc4b94af9f8871db3e1ff3
Author: Jake Koroman <jake@jakekoroman.com>
Date: Fri, 2 Jan 2026 18:17:48 -0500
add basic hashmap implementation.
Diffstat:
| M | jrk.h | | | 117 | ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++- |
1 file changed, 116 insertions(+), 1 deletion(-)
diff --git a/jrk.h b/jrk.h
@@ -4,9 +4,13 @@
* that i like.
*
* TODO:
+ * - add jrk_StringView compare function.
+ *
+ * - remove strnlen/strncmp from hm impl. should probably be using
+ * jrk_StringView's
+ *
* - look at at the jrk_sv_chop_delim_loop stuff. there must
* must be a better way of handling things.
- *
*/
#include <stdbool.h>
@@ -275,6 +279,107 @@ bool jrk_sb_write_entire_file(jrk_StringBuilder *, char *);
bool jrk_sb_fd_read_all(jrk_StringBuilder*, i32);
bool jrk_sb_read_entire_file(jrk_StringBuilder*, char*);
+
+// http://www.isthe.com/chongo/tech/comp/fnv/index.html#FNV-param
+// for 64 bit hash
+#define FNV1A_64_OFFSET_BASIS 0xCBF29CE484222325
+#define FNV1A_64_PRIME 0x100000001B3
+uint64_t jrk_fnv1a_64(uint8_t *data, uint64_t size);
+
+#define JRK_HM_MAX_KEY_SIZE 16
+#define jrk_hm_prototype(type) \
+ typedef struct { \
+ char key[JRK_HM_MAX_KEY_SIZE]; \
+ type val; \
+ } jrk_HashMapItem_##type; \
+ \
+ typedef struct { \
+ jrk_HashMapItem_##type *items; \
+ uint64_t capacity; \
+ } jrk_HashMap_##type; \
+ \
+ bool jrk_hm_##type##_init(jrk_HashMap_##type *map, jrk_HashMapItem_##type *items, uint64_t items_sz); \
+ bool jrk_hm_##type##_push(jrk_HashMap_##type *map, char *key, type val); \
+ bool jrk_hm_##type##_get(jrk_HashMap_##type *map, char *key, type *outval);
+
+#define jrk_hm_impl(type) \
+ bool \
+ jrk_hm_##type##_init(jrk_HashMap_##type *map, jrk_HashMapItem_##type *items, uint64_t 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_HashMap_##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; \
+ } \
+ uint64_t idx = jrk_fnv1a_64((uint8_t *) key, strnlen(key, JRK_HM_MAX_KEY_SIZE)) % map->capacity; \
+ jrk_HashMapItem_##type *item = &map->items[idx]; \
+ if (item->key[0] != 0 && 0 != strncmp(item->key, key, JRK_HM_MAX_KEY_SIZE)) \
+ printf("%s collision with %s\n", key, item->key); \
+ for (; item < &map->items[map->capacity] && item->key[0] != 0 && 0 != strncmp(item->key, key, JRK_HM_MAX_KEY_SIZE); ++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, strlen(key)); \
+ item->val = val; \
+ return true; \
+ } \
+ \
+ bool \
+ jrk_hm_##type##_get(jrk_HashMap_##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; \
+ } \
+ uint64_t idx = jrk_fnv1a_64((uint8_t *) key, strnlen(key, JRK_HM_MAX_KEY_SIZE)) % map->capacity; \
+ jrk_HashMapItem_##type *item = &map->items[idx]; \
+ if (0 == strncmp(item->key, key, JRK_HM_MAX_KEY_SIZE)) { \
+ *outval = item->val; \
+ return true; \
+ } \
+ for (; item < &map->items[map->capacity] && 0 != strncmp(item->key, key, JRK_HM_MAX_KEY_SIZE); ++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, JRK_HM_MAX_KEY_SIZE); ++item); \
+ if (item == &map->items[idx]) \
+ return false; \
+ } \
+ *outval = item->val; \
+ return true; \
+ }
+
#ifdef JRK_IMPLEMENTATION
#include <ctype.h>
#include <errno.h>
@@ -689,6 +794,16 @@ jrk_sv_chop_delim(jrk_StringView *sv, char delim)
return result;
}
+uint64_t jrk_fnv1a_64(uint8_t *data, uint64_t size)
+{
+ uint64_t result = FNV1A_64_OFFSET_BASIS;
+ for (uint64_t i = 0; i < size; ++i) {
+ result ^= data[i];
+ result *= FNV1A_64_PRIME;
+ }
+ return result;
+}
+
i32
jrk_rand_num(i32 upbound)
{
