From 80223cd4a18b95f05addce9d6eab29348583becb Mon Sep 17 00:00:00 2001 From: steven-na Date: Wed, 19 Aug 2026 12:59:37 -0700 Subject: Started working on hashmap --- src/map.c | 150 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ src/map.h | 13 ++++++ src/string.c | 4 +- src/string.h | 8 ++-- src/unity.c | 1 + 5 files changed, 170 insertions(+), 6 deletions(-) create mode 100644 src/map.c create mode 100644 src/map.h (limited to 'src') diff --git a/src/map.c b/src/map.c new file mode 100644 index 0000000..5e77995 --- /dev/null +++ b/src/map.c @@ -0,0 +1,150 @@ +#include "map.h" +#include "common.h" +#include "log.h" +#include "smrt_arena.h" + +#include +#include +#include + +#define ENTRY_TOMBSTONE 0b0000000000000000000000000000000000000000000000000000000000000001 +#define ENTRY_MASK 0b1111111111111111111111111111111111111111111111111111111111111110 + +typedef struct { + void *key; + u64 keylen; +} map_key_entry_t; + +typedef struct _map_t { + u64 table_size; + u64 *hashes; + map_key_entry_t *keys; + void **values; +} _map_t; + +u32 hash(u8 *input, u64 inputlen) { + // Make this batched + SIMD eventually + u32 sum = UINT32_MAX / 2; + for (u64 i = 0; i < inputlen; i++) { + sum += input[i]; + } + return sum; +} + +map_t map_create(smrt_arena_t *arena, u64 capacity) { + map_t map = smrt_arena_push(arena, sizeof(_map_t), true); + map->hashes = SMRTA_ALLOC_ARRAY(arena, u64, capacity); + map->keys = SMRTA_ALLOC_ARRAY(arena, map_key_entry_t, capacity); + map->values = SMRTA_ALLOC_ARRAY(arena, void*, capacity); + map->table_size=capacity; + + return map; +} + +i32 map_insert(map_t map, u8 *key, u64 keylen, void *value) { + u64 h = hash(key, keylen) & ENTRY_MASK; + + u64 start = h % map->table_size; + i64 first_tombstone = -1; + for (u64 i = start; i != start - 1; i = (i+1)%map->table_size) { + // If didnt find match, insert at first tombstone or current i + if (map->keys[i].key == NULL) { + if (first_tombstone != -1) i = first_tombstone; + map->hashes[i] = h; + map->keys[i] = (map_key_entry_t){.key=key, .keylen=keylen, }; + map->values[i] = value; + return 0; + } + + u64 h_cmp = map->hashes[i]; + + // if tombstone, update first tombstone + if (first_tombstone != -1 && (h_cmp & ENTRY_TOMBSTONE) == ENTRY_TOMBSTONE) { + first_tombstone = i; + continue; + } + + h_cmp &= ENTRY_MASK; + map_key_entry_t k = map->keys[i]; + if (k.keylen == keylen && + h == h_cmp && + memcmp(key, k.key, keylen) != 0) + { + map->keys[i].key = key; + map->values[i] = value; + } + } + + return -1; +} + +i32 map_delete(map_t map, u8 *key, u64 keylen) { + u64 h = hash(key, keylen) & ENTRY_MASK; + + u64 start = h % map->table_size; + for (u64 i = start; i != start - 1; i = (i+1)%map->table_size) { + if (map->keys[i].key == NULL) { + return -1; + } + + u64 h_cmp = map->hashes[i]; + + // if tombstone, skip + if ((h_cmp & ENTRY_TOMBSTONE) == ENTRY_TOMBSTONE) { + continue; + } + + h_cmp &= ENTRY_MASK; + map_key_entry_t k = map->keys[i]; + if (k.keylen == keylen && + h == h_cmp && + memcmp(key, k.key, keylen) == 0) + { + map->keys[i].keylen = 0; + *map->hashes &= ENTRY_TOMBSTONE; + } + } + + return -1; +} + +void *map_lookup(map_t map, u8 *key, u64 keylen) { + u64 h = hash(key, keylen) & ENTRY_MASK; + + u64 start = h % map->table_size; + for (u64 i = start; i != start - 1; i = (i+1)%map->table_size) { + if (map->keys[i].key == NULL) { + return NULL; + } + + u64 h_cmp = map->hashes[i]; + + // if tombstone, skip + if ((h_cmp & ENTRY_TOMBSTONE) == ENTRY_TOMBSTONE) { + continue; + } + + h_cmp &= ENTRY_MASK; + map_key_entry_t k = map->keys[i]; + if (k.keylen == keylen && + h == h_cmp && + memcmp(key, k.key, keylen) == 0) + { + return map->values[i]; + } + } + + return NULL; +} + +void map_print(map_t map) { + printf("=== MAP ===\n"); + for (u64 i = 0; i < map->table_size; i++) { + if (map->values[i] || (map->hashes[i] & ENTRY_TOMBSTONE) == 1) { + printf("%lu %s %lu\n", i, (char*)map->keys[i].key, *(u64*)map->values[i]); + } else { + printf("%lu\n", i); + } + } + printf("=== END ===\n"); +} diff --git a/src/map.h b/src/map.h new file mode 100644 index 0000000..e8183d2 --- /dev/null +++ b/src/map.h @@ -0,0 +1,13 @@ +#pragma once + +#include "common.h" +#include "smrt_arena.h" + +typedef struct _map_t* map_t; + +map_t map_create(smrt_arena_t *arena, u64 table_size); + i32 map_insert(map_t map, u8 *key, u64 keylen, void *value); + i32 map_delete(map_t map, u8 *key, u64 keylen); + void *map_lookup(map_t map, u8 *key, u64 keylen); + +void map_print(map_t map); diff --git a/src/string.c b/src/string.c index 413ad5e..795eb95 100644 --- a/src/string.c +++ b/src/string.c @@ -106,12 +106,12 @@ i32 strng_app_c(strng_t *dest, char const *source) { } i32 strng_app_v(strng_t *dest, strng_view_t const *source) { - u64 slen = source->end - source->start; + u64 slen = sv_len(source); u64 nlen = dest->len + slen; if (nlen > dest->alloc_size) return -1; char *dst = STRNG_TO(dest)+dest->len; - char const *src = source->string+source->start; + char const *src = SV_TO(*source); memcpy(dst, src, slen); dest->len = nlen; diff --git a/src/string.h b/src/string.h index e3f74cf..9ff4978 100644 --- a/src/string.h +++ b/src/string.h @@ -121,10 +121,10 @@ i32 sv_find_char(strng_view_t const *sv, char n); b32 sv_starts_with(strng_view_t const *sv, char const *prefix); b32 sv_ends_with(strng_view_t const *sv, char const *suffix); -static inline b32 sv_starts_with_c(strng_view_t sv, char c) { return - (sv_len(&sv) > 0) && (*SV_TO(sv) == c); } -static inline b32 sv_ends_with_c(strng_view_t sv, char c) { return - (sv_len(&sv) > 0) && (*(sv.string + sv.end) == c); } +static inline b32 sv_starts_with_c(strng_view_t const *sv, char c) { return + (sv_len(sv) > 0) && (*SV_TO(*sv) == c); } +static inline b32 sv_ends_with_c(strng_view_t const *sv, char c) { return + (sv_len(sv) > 0) && (*(sv->string + sv->end) == c); } b32 sv_eq_case_insensitive(strng_view_t const *sv1, strng_view_t const *sv2); diff --git a/src/unity.c b/src/unity.c index 6fe4973..a694f13 100644 --- a/src/unity.c +++ b/src/unity.c @@ -21,6 +21,7 @@ #include "slidingwindow.c" #include "vec2sw.c" #include "deque.c" +#include "map.c" // DSP/Audio #include "wav.c" -- cgit v1.2.3