From b844718a1687424b2748608cbb52fb4012417fe5 Mon Sep 17 00:00:00 2001 From: steven-na Date: Fri, 21 Aug 2026 16:01:34 -0700 Subject: Hashmap usable i think, now with proper 3rd party algorithm --- src/map.c | 118 +++++++++++++++++++++++++++----------------------------------- src/map.h | 4 ++- 2 files changed, 54 insertions(+), 68 deletions(-) (limited to 'src') diff --git a/src/map.c b/src/map.c index 00b56b8..788095f 100644 --- a/src/map.c +++ b/src/map.c @@ -2,12 +2,15 @@ #include "common.h" #include "smrt_arena.h" +#include "../include/a5hash.h" + +#include #include -#include #include -#define ENTRY_TOMBSTONE 0b0000000000000000000000000000000000000000000000000000000000000001 -#define ENTRY_MASK 0b1111111111111111111111111111111111111111111111111111111111111110 +#define ENTRY_TOMBSTONE 0b00000001 +#define ENTRY_EMPTY 0b00000000 +#define ENTRY_MASK 0b11111110 typedef struct { void const *key; @@ -16,24 +19,17 @@ typedef struct { typedef struct _map_t { u64 table_size; + u8 *hashlookup; u64 *hashes; map_key_entry_t *keys; void **values; } _map_t; -u32 hash(u8 const *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->hashlookup = SMRTA_ALLOC_ARRAY(arena, u8, capacity); map->keys = SMRTA_ALLOC_ARRAY(arena, map_key_entry_t, capacity); map->values = SMRTA_ALLOC_ARRAY(arena, void*, capacity); map->table_size = capacity; @@ -42,96 +38,84 @@ map_t map_create(smrt_arena_t *arena, u64 capacity) { } i32 map_insert(map_t const map, u8 const *key, u64 keylen, void *value) { - u64 h = hash(key, keylen) & ENTRY_MASK; + u64 h = a5hash128(key, keylen, 0, NULL); + u8 h_lookup = h >> (64-8) & ENTRY_MASK; u64 start = h % map->table_size; i64 first_tombstone = -1; u64 tsize = map->table_size; - for (u64 i = start; i != start - 1; i = (i+1)%tsize) { - // If didnt find match, insert at first tombstone or current i - if (map->keys[i].key == NULL) { + for (u64 i = start; i != start - 1; i=(i+1)%tsize) { + u8 h_lookupcmp = map->hashlookup[i]; + if (h_lookupcmp == ENTRY_EMPTY) { if (first_tombstone != -1) i = first_tombstone; + map->hashes[i] = h; - map->keys[i] = (map_key_entry_t){.key=key, .keylen=keylen, }; + map->hashlookup[i] = h_lookup; + 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) { + if (first_tombstone == -1 && + h_lookupcmp == ENTRY_TOMBSTONE) { first_tombstone = i; continue; } - 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 0; + if ( + h_lookupcmp == h_lookup && + keylen == map->keys[i].keylen && + h == map->hashes[i] && + (memcmp(key, map->keys[i].key, keylen) == 0) + ) { + map->keys[i].key=key; + map->values[i]=value; } - } + } return -1; } i32 map_delete(map_t const map, u8 const *key, u64 keylen) { - u64 h = hash(key, keylen) & ENTRY_MASK; + u64 h = a5hash128(key, keylen, 0, NULL); + u8 h_lookup = h >> (64-8) & ENTRY_MASK; u64 start = h % map->table_size; u64 tsize = map->table_size; - for (u64 i = start; i != start - 1; i = (i+1)%tsize) { - if (map->keys[i].key == NULL) { - return -1; - } - - u64 h_cmp = map->hashes[i]; - - if ((h_cmp & ENTRY_TOMBSTONE) == ENTRY_TOMBSTONE) { - continue; - } - - 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[i] = ENTRY_TOMBSTONE; - return 0; - } + for (u64 i = start; i != start - 1; i=(i+1)%tsize) { + u8 h_lookupcmp = map->hashlookup[i]; + if (h_lookupcmp == ENTRY_EMPTY) return -1; + if (h_lookupcmp == ENTRY_TOMBSTONE) continue; + + if (h_lookupcmp == h_lookup && + h == map->hashes[i] && + keylen == map->keys[i].keylen && + (memcmp(key, map->keys[i].key, keylen) == 0)) + { map->keys[i].keylen=0; + map->hashlookup[i]=ENTRY_TOMBSTONE; + return 0; } } return -1; } void *map_lookup(map_t const map, u8 const *key, u64 keylen) { - u64 h = hash(key, keylen) & ENTRY_MASK; + u64 h = a5hash128(key, keylen, 0, NULL); + u8 h_lookup = h >> (64-8) & ENTRY_MASK; u64 start = h % map->table_size; u64 tsize = map->table_size; for (u64 i = start; i != start - 1; i = (i+1)%tsize) { - if (map->keys[i].key == NULL) { - return NULL; - } - - u64 h_cmp = map->hashes[i]; - - if ((h_cmp & ENTRY_TOMBSTONE) == ENTRY_TOMBSTONE) { - continue; - } + u8 h_lookupcmp = map->hashlookup[i]; + if (h_lookupcmp == ENTRY_EMPTY) return NULL; + if (h_lookupcmp == ENTRY_TOMBSTONE) continue; 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]; - } + if (h_lookupcmp == h_lookup && + h == map->hashes[i] && + k.keylen == keylen && + (memcmp(key, k.key, keylen) == 0)) + { return map->values[i]; } } return NULL; diff --git a/src/map.h b/src/map.h index b99a306..6678ddd 100644 --- a/src/map.h +++ b/src/map.h @@ -4,7 +4,9 @@ #include "smrt_arena.h" // Hashmap structure that stores u8* keys and void* values. -// API: map_create, map_insert, map_delete, map_lookoop +// API: map_create, map_insert, map_delete, map_lookup +// There is no map_destroy. It is allocated on the arena +// Uses a5hash to hash keys. typedef struct _map_t* map_t; map_t map_create(smrt_arena_t *arena, u64 table_size); -- cgit v1.2.3