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
|
#include "map.h"
#include "common.h"
#include "smrt_arena.h"
#include <stdint.h>
#include <stdio.h>
#include <string.h>
#define ENTRY_TOMBSTONE 0b0000000000000000000000000000000000000000000000000000000000000001
#define ENTRY_MASK 0b1111111111111111111111111111111111111111111111111111111111111110
typedef struct {
void const *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 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->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 const map, u8 const *key, u64 keylen, void *value) {
u64 h = hash(key, keylen) & 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) {
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;
}
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;
}
}
return -1;
}
i32 map_delete(map_t const map, u8 const *key, u64 keylen) {
u64 h = hash(key, keylen) & 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;
}
}
return -1;
}
void *map_lookup(map_t const map, u8 const *key, u64 keylen) {
u64 h = hash(key, keylen) & 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;
}
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;
}
|
