diff options
| -rw-r--r-- | src/map.c | 86 | ||||
| -rw-r--r-- | src/map.h | 36 |
2 files changed, 84 insertions, 38 deletions
@@ -13,13 +13,13 @@ #define ENTRY_MASK 0b11111110 typedef struct { - void const *key; + u8 const *key; u64 keylen; } map_key_entry_t; typedef struct _map_t { u64 table_size; - u8 *hashlookup; + u8 *hashlookup; u64 *hashes; map_key_entry_t *keys; void **values; @@ -42,27 +42,27 @@ map_t map_create(smrt_arena_t *arena, u64 capacity) { return map; } -i32 map_insert(map_t const map, u8 const *key, u64 keylen, void *value) { +MapInsertResultK map_insert(map_t map, u8 const *key, u64 keylen, void *value) { 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) { + for (u64 count = 0, i = start; count < tsize; count++, 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->hashlookup[i] = h_lookup; map->keys[i] = (map_key_entry_t){ .key=key, .keylen=keylen }; map->values[i] = value; - return 0; + return MapInsertResultSuccessNew; } if (first_tombstone == -1 && - h_lookupcmp == ENTRY_TOMBSTONE) { + h_lookupcmp == ENTRY_TOMBSTONE) + { first_tombstone = i; continue; } @@ -75,44 +75,31 @@ i32 map_insert(map_t const map, u8 const *key, u64 keylen, void *value) { ) { map->keys[i].key=key; map->values[i]=value; + return MapInsertResultSuccessPreexisted; } } - log_warn("Attempted to insert value with key \"%.*s...\" into hashmap that is full", - (i32)MIN(5, keylen), key); - return -1; -} -i32 map_delete(map_t const map, u8 const *key, u64 keylen) { - 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) { - 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; } + if (first_tombstone >= 0) { + map->hashes[first_tombstone] = h; + map->hashlookup[first_tombstone] = h_lookup; + map->keys[first_tombstone] = (map_key_entry_t){ .key=key, .keylen=keylen }; + map->values[first_tombstone] = value; + return MapInsertResultSuccessNew; } - return -1; + log_warn("Attempted to insert value with key \"%.*s...\" into hashmap that is full", + (i32)MIN(5, keylen), key); + return MapInsertResultFailedFull; } -void *map_lookup(map_t const map, u8 const *key, u64 keylen) { +static inline i64 map_find_slot(map_t const map, u8 const *key, u64 keylen) { 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) { + for (u64 count = 0, i = start; count < tsize; count++, i = (i + 1) % tsize) { u8 h_lookupcmp = map->hashlookup[i]; if (h_lookupcmp == ENTRY_EMPTY) break; if (h_lookupcmp == ENTRY_TOMBSTONE) continue; @@ -122,8 +109,39 @@ void *map_lookup(map_t const map, u8 const *key, u64 keylen) { h == map->hashes[i] && k.keylen == keylen && (memcmp(key, k.key, keylen) == 0)) - { return map->values[i]; } + { return (i64)i; } + } + + return -1; +} + +MapDeleteResultK map_delete(map_t map, u8 const *key, u64 keylen) { + i64 slot = map_find_slot(map, key, keylen); + if (slot >= 0) { + map->keys[slot].keylen=0; + map->hashlookup[slot]=ENTRY_TOMBSTONE; + return MapDeleteResultSuccess; + } + return MapDeleteResultNotFound; +} + +void map_clear(map_t map) { + for (u64 i = 0; i < map->table_size; i++) { + map->hashlookup[i] = ENTRY_EMPTY; + } +} + +void *map_lookup(map_t const map, u8 const *key, u64 keylen) { + i64 slot = map_find_slot(map, key, keylen); + return slot >= 0 ? map->values[slot] : NULL; +} + +MapChangeKeyPtrResultK map_change_key_ptr(map_t map, u8 const *new_but_identical_key, u64 keylen) { + i64 slot = map_find_slot(map, new_but_identical_key, keylen); + if (slot >= 0) { + map->keys[slot].key = new_but_identical_key; + return MapChangeKeyPtrResultSuccess; } - return NULL; + return MapChangeKeyPtrResultKeyNotPresent; } @@ -9,7 +9,35 @@ // Uses a5hash to hash keys. typedef struct _map_t* map_t; -map_t map_create(smrt_arena_t *arena, u64 table_size); - i32 map_insert(map_t const map, u8 const *key, u64 keylen, void *value); - i32 map_delete(map_t const map, u8 const *key, u64 keylen); - void *map_lookup(map_t const map, u8 const *key, u64 keylen); +typedef enum { + MapInsertResultSuccessNew = 0, + MapInsertResultSuccessPreexisted = 1, + MapInsertResultFailedFull = -1, +} MapInsertResultK; + +typedef enum { + MapDeleteResultSuccess = 0, + MapDeleteResultNotFound = -1, +} MapDeleteResultK; + +typedef enum { + MapChangeKeyPtrResultSuccess = 0, + MapChangeKeyPtrResultKeyNotPresent = -1, +} MapChangeKeyPtrResultK; + +map_t map_create(smrt_arena_t *arena, u64 table_size); + +MapInsertResultK map_insert(map_t map, u8 const *key, u64 keylen, void *value); + +MapDeleteResultK map_delete(map_t map, u8 const *key, u64 keylen); +void map_clear(map_t map); + +void *map_lookup(map_t const map, u8 const *key, u64 keylen); + +#define map_lookup_or(map, key, keylen, default_val) \ + ({ \ + void *val = map_lookup((map), (key), (keylen); \ + (val != NULL) ? val : (default_val); \ + }) + +MapChangeKeyPtrResultK map_change_key_ptr(map_t map, u8 const *new_but_identical_key, u64 keylen); |