1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
|
#include "map.h"
#include "common.h"
#include "smrt_arena.h"
#include "log.h"
#include "../include/a5hash.h"
#include <stdint.h>
#include <string.h>
#define ENTRY_TOMBSTONE 0b00000001
#define ENTRY_EMPTY 0b00000000
#define ENTRY_MASK 0b11111110
typedef struct {
u8 const *key;
u64 keylen;
} map_key_entry_t;
typedef struct _map_t {
u64 table_size;
u8 *hashlookup;
u64 *hashes;
map_key_entry_t *keys;
void **values;
} _map_t;
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;
#ifndef NLOG_TRACE
log_trace("Created hashmap; Total capacity %lu",
capacity);
#endif /* ifndef NLOG_TRACE */
return map;
}
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 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 MapInsertResultSuccessNew;
}
if (first_tombstone == -1 &&
h_lookupcmp == ENTRY_TOMBSTONE)
{
first_tombstone = i;
continue;
}
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 MapInsertResultSuccessPreexisted;
}
}
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;
}
log_warn("Attempted to insert value with key \"%.*s...\" into hashmap that is full",
(i32)MIN(5, keylen), key);
return MapInsertResultFailedFull;
}
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 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;
map_key_entry_t k = map->keys[i];
if (h_lookupcmp == h_lookup &&
h == map->hashes[i] &&
k.keylen == keylen &&
(memcmp(key, k.key, keylen) == 0))
{ 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 MapChangeKeyPtrResultKeyNotPresent;
}
|
