src/oa_hash.c

filter: Statementstmt 46.5% 101 / 217 Branchbran 24.2% 17 / 70 Conditioncond n/a MC/DCmcdc n/a Subroutinesub n/a Podpod n/a totaltotal 41.1% 118 / 287 CC 0 SCAR 0
CC
0
Cov
0%
CRAP 0
« src/shared.c ↑ Summary Simple.xs »
1 #include "oa_hash.h"
2 #include "log.h"
3  
4 #include <stdlib.h>
5 #include <string.h>
6 #include <stdatomic.h>
7 #include <stdio.h>
8 #include <unistd.h>
9 #define NOTHING_IS_UPDATED UINT64_MAX
10  
11 3 static SLOT_TYPE next4(size_t x)
12 {
13 3 size_t n = (x + 3u) & ~(size_t)3u;
14 3 return n / SLOT_SIZE;
15 }
16  
17 // A simple hash function for strings
18 7 static uint32_t hash(const char *key) {
19 7 size_t hash_val = 0;
20 49 ▶ while (*key)
Branch: 1 branch
BranchTrueFalseTotal
while (*key) 42 7 49
21 42 hash_val = (hash_val << 5) + (uint8_t)*key++;
22 7 return hash_val;
23 }
24  
25 7 static HashIndexEntry* get_index(const HashTable *ht, uint32_t index) {
26 7 return ht->index_entries + index;
27 }
28  
29 8 static char* get_key(const HashTable* ht, HashIndexEntry* entry) {
30 8 Key key = { .storable = entry->key };
31 8 return (char *) ((uint32_t*) ht->data_entries + key.key_start);
32 }
33  
34 5 static const char* get_value(const HashTable* ht, HashIndexEntry* entry) {
35 5 Key key = { .storable = entry->key };
36 5 return (const char*)(ht->data_entries + key.key_start + key.key_size);
37 }
38  
39 1 static void set_value(const HashTable* ht, HashIndexEntry* entry, const char value[VALUE_SIZE]) {
40 1 Key key = { .storable = entry->key };
41 1 char* stored = (char*)(ht->data_entries + key.key_start + key.key_size);
42 1 memcpy(stored, value, VALUE_SIZE);
43 1 }
44  
45 3 static void commit_new_entry(HashTable *ht, HashIndexEntry* ht_index, const char *key, uint32_t key_size, const char value[VALUE_SIZE]) {
46 3 SLOT_TYPE data_size = key_size + VALUE_SLOTS;
47  
48 Sizes sizes;
49 3 sizes.storable = atomic_load_explicit(&ht->sizes->sizes, memory_order_acquire);
50 3 Key key_id = {0};
51 3 key_id.key_start = sizes.data;
52 3 key_id.key_size = key_size;
53 3 key_id.status = INDEX_SET;
54 3 atomic_store_explicit(&ht_index->key, key_id.storable, memory_order_release);
55  
56 3 strcpy((char *) (ht->data_entries + sizes.data), key);
57 3 memcpy(ht->data_entries + sizes.data + key_size, value, VALUE_SIZE);
58 3 key_id.status = DATA_SET;
59 3 atomic_store_explicit(&ht_index->key, key_id.storable, memory_order_release);
60  
61 3 sizes.data += data_size;
62 3 sizes.index += 1;
63 3 key_id.status = COMMITED;
64 3 atomic_store_explicit(&ht->sizes->sizes, sizes.storable, memory_order_release);
65 3 atomic_store_explicit(&ht_index->key, key_id.storable, memory_order_release);
66 3 }
67  
68 0 void fix_entry(HashTable* ht, uint32_t entry_slot) {
69 0 HashIndexEntry* ht_index = get_index(ht, entry_slot);
70 _Static_assert(STATUS_LAST == 4, "Update case statement below if you add new status");
71 0 int done = 0;
72 0 ▶ while (!done) {
Branch: 1 branch
BranchTrueFalseTotal
while (!done) { 0 0 0
73 0 Key key_id = { .storable = atomic_load_explicit(&ht_index->key, memory_order_acquire) };
74 0 switch (key_id.status) {
75 0 case UNSET:
76 // if status unset then process died on index update
77 // index update is atomic, so we can safely set it
78 0 done = 1;
79 0 break;
80 0 case INDEX_SET: {
81 // if index committed then process died on data update, cleanup it
82 0 Key key = { .storable = ht_index->key };
83 0 uint32_t slot_size = key.key_size + VALUE_SLOTS;
84 0 uint32_t* slot = (uint32_t*) ht->data_entries + key.key_start;
85 0 memset(slot, 0, slot_size);
86 0 key.status = UNSET;
87 0 key.key_start = 0;
88 0 key.key_size = 0;
89 0 atomic_store_explicit(&ht_index->key, key.storable, memory_order_release);
90 0 break;
91 }
92 0 case DATA_SET: {
93 // index and data was commit, need ot check if sizes were updated
94 0 uint32_t index_size_exp = 0;
95 0 Sizes sizes = { .storable = ht->sizes->sizes };
96 0 Sizes capacities = { .storable = ht->sizes->capacities};
97 0 ▶ for (uint32_t i = 0; i < capacities.index; i++) {
Branch: 1 branch
BranchTrueFalseTotal
for (uint32_t i = 0; i < capacities.index; i++) { 0 0 0
98 0 HashIndexEntry* index_entry = get_index(ht, i);
99 0 Key index_key = { .storable = index_entry->key };
100 0 ▶ if (index_key.status) {
Branch: 1 branch
BranchTrueFalseTotal
if (index_key.status) { 0 0 0
101 0 index_size_exp++;
102 }
103 }
104 0 Key key = { .storable = ht_index->key };
105 0 uint32_t data_size_exp = key.key_start + key.key_size + 1;
106 0 sizes.index = index_size_exp;
107 0 sizes.data = data_size_exp;
108 0 key.status = COMMITED;
109 0 atomic_store_explicit(&ht->sizes->sizes, sizes.storable, memory_order_release);
110 0 atomic_store_explicit(&ht_index->key, key.storable, memory_order_release);
111 0 break;
112 }
113 0 case COMMITED:
114 // Fixed
115 0 done = 1;
116 0 break;
117 }
118 }
119 0 atomic_store_explicit(&ht->sizes->current_update, NOTHING_IS_UPDATED, memory_order_release);
120 0 }
121  
122 7 static int find_index(HashTable *ht, const char *key, HashIndexEntry** res, Stats *stats) {
123 7 Sizes capacites = { .storable = ht->sizes->capacities };
124 7 uint32_t capacity = capacites.index;
125 7 uint32_t key_hash = hash(key);
126 7 uint32_t index = key_hash % capacity;
127 7 uint32_t start_index = index;
128  
129 0 for (;;) {
130 7 ▶ if (stats) stats->probes++;
Branch: 1 branch
BranchTrueFalseTotal
if (stats) stats->probes++; 4 3 7
131 7 HashIndexEntry* ht_index = get_index(ht, index);
132 7 Key ht_index_as_key = (Key)ht_index->key;
133 7 ▶ if (!ht_index_as_key.status) {
Branch: 1 branch
BranchTrueFalseTotal
if (!ht_index_as_key.status) { 4 3 7
134 4 *res = ht_index;
135 7 return index;
136 }
137 3 char *key_in_slot = get_key(ht, ht_index);
138 3 ▶ if (strcmp(key_in_slot, key) == 0) {
Branch: 1 branch
BranchTrueFalseTotal
if (strcmp(key_in_slot, key) == 0) { 3 0 3
139 3 *res = ht_index;
140 3 return index;
141 }
142 0 index = (index + 1) % capacity; // Linear probing
143 0 ▶ if (index == start_index) {
Branch: 1 branch
BranchTrueFalseTotal
if (index == start_index) { 0 0 0
144 0 ▶ LOG("find_index: full circle, key='%s' capacity=%u\n", key, capacity);
Branch: 1 branch
BranchTrueFalseTotal
LOG("find_index: full circle, key='%s' capacity=%u\n", key, capacity); 0 0 0
145 0 *res = 0; // Came full circle, not found
146 0 return -1;
147 }
148 }
149 }
150  
151 // PUBLIC API
152 2 OA_HASH_ERR ht_init_table(HashTable* ht, Sizes capacities, void* mem) {
153 2 ▶ if (!mem) {
Branch: 1 branch
BranchTrueFalseTotal
if (!mem) { 0 2 2
154 0 return OA_HASH_ERR_INVALID_ARGUMENT;
155 }
156  
157 2 ht->sizes = (HashDataSizes*) mem;
158 2 ht->index_entries = OFFSET(ht->sizes, ht->index_entries);
159 2 ht->data_entries = OFFSETA(ht->index_entries, capacities.index, ht->data_entries);
160 2 atomic_store_explicit(&ht->sizes->current_update, NOTHING_IS_UPDATED, memory_order_release);
161 2 atomic_store_explicit(&ht->sizes->capacities, capacities.storable, memory_order_release);
162 2 return OA_HASH_OK;
163 }
164  
165 0 Sizes ht_resize_table(const HashTable* ht, uint32_t ratio) {
166 0 Sizes old_capacities = { .storable = atomic_load_explicit(&ht->sizes->capacities, memory_order_acquire) };
167 0 Sizes new_capacities = old_capacities;
168 0 new_capacities.index *= ratio;
169 0 ▶ if (new_capacities.data < ((Sizes) ht->sizes->sizes).data * ratio) {
Branch: 1 branch
BranchTrueFalseTotal
if (new_capacities.data < ((Sizes) ht->sizes->sizes).data * ratio) { 0 0 0
170 0 new_capacities.data = ((Sizes) ht->sizes->capacities).data * ratio;
171 }
172 0 return new_capacities;
173 }
174  
175 0 void ht_table_fix(HashTable* ht) {
176 0 ▶ if (ht->sizes->current_update != NOTHING_IS_UPDATED) {
Branch: 1 branch
BranchTrueFalseTotal
if (ht->sizes->current_update != NOTHING_IS_UPDATED) { 0 0 0
177 0 fix_entry(ht, (uint32_t)ht->sizes->current_update);
178 }
179 0 }
180  
181 0 OA_HASH_ERR ht_copy_to_local_memory(HashTable* src, HashTable* dst) {
182 0 Sizes capacities = { .storable = src->sizes->capacities };
183 0 Sizes sizes = { .storable = src->sizes->sizes };
184 0 size_t size = ht_table_size(capacities.index, capacities.data);
185 0 void* mem = calloc(size, 1);
186 0 ▶ if (!mem) {
Branch: 1 branch
BranchTrueFalseTotal
if (!mem) { 0 0 0
187 0 return OA_HASH_ERR_FAILED;
188 }
189 0 OA_HASH_ERR error = ht_init_table(dst, capacities, mem);
190 0 ▶ if (error != OA_HASH_OK) return error;
Branch: 1 branch
BranchTrueFalseTotal
if (error != OA_HASH_OK) return error; 0 0 0
191 0 memcpy(dst->index_entries, src->index_entries, capacities.index * sizeof(HashIndexEntry));
192 0 memcpy(dst->data_entries, src->data_entries, sizes.data * sizeof(HashDataEntry));
193 0 atomic_store_explicit(&dst->sizes->sizes, sizes.storable, memory_order_release);
194 0 return OA_HASH_OK;
195 }
196  
197 2 size_t ht_table_size(uint32_t index_len, uint32_t data_len) {
198 2 size_t sizes_size = ALIGN_UP(sizeof(HashDataSizes), alignof(HashIndexEntry));
199 2 size_t index_size = ALIGN_UP(sizeof(HashIndexEntry) * index_len, alignof(HashDataEntry));
200 2 size_t data_size = sizeof(HashDataEntry) * data_len;
201 2 size_t bytes = sizes_size + index_size + data_size;
202 2 return bytes;
203 }
204  
205 4 OA_HASH_ERR ht_insert(HashTable *ht, const char *key, const char value[VALUE_SIZE], Stats *stats) {
206 4 uint64_t cur = atomic_load_explicit(&ht->sizes->current_update, memory_order_acquire);
207 4 ▶ if (cur != NOTHING_IS_UPDATED) {
Branch: 1 branch
BranchTrueFalseTotal
if (cur != NOTHING_IS_UPDATED) { 0 4 4
208 0 ▶ LOG("ht_insert: invalid state, current_update=%" PRIu64 " key='%s'\n", cur, key);
Branch: 1 branch
BranchTrueFalseTotal
LOG("ht_insert: invalid state, current_update=%" PRIu64 " key='%s'\n", cur, key); 0 0 0
209 0 return OA_HASH_INVALD_STATE;
210 }
211 4 HashIndexEntry *ht_index = 0;
212 4 int index = find_index(ht, key, &ht_index, stats);
213 4 ▶ if (!ht_index) {
Branch: 1 branch
BranchTrueFalseTotal
if (!ht_index) { 0 4 4
214 0 ▶ LOG("ht_insert: index full, key='%s'\n", key);
Branch: 1 branch
BranchTrueFalseTotal
LOG("ht_insert: index full, key='%s'\n", key); 0 0 0
215 0 ▶ if (stats) stats->reallocates++;
Branch: 1 branch
BranchTrueFalseTotal
if (stats) stats->reallocates++; 0 0 0
216 0 return OA_HASH_ERR_INDEX_FULL;
217 }
218  
219 4 Key ht_index_as_key = (Key)ht_index->key;
220 4 ▶ if (ht_index_as_key.status) {
Branch: 1 branch
BranchTrueFalseTotal
if (ht_index_as_key.status) { 1 3 4
221 1 set_value(ht, ht_index, value);
222 } else {
223 3 uint32_t key_size = next4(strlen(key) + 1);
224 3 uint32_t data_size = key_size + VALUE_SLOTS;
225 3 Sizes capacities = { .storable = atomic_load_explicit(&ht->sizes->capacities, memory_order_acquire) };
226 3 Sizes sizes = { .storable = atomic_load_explicit(&ht->sizes->sizes, memory_order_acquire) };
227 3 ▶ if (capacities.data <= sizes.data + data_size) {
Branch: 1 branch
BranchTrueFalseTotal
if (capacities.data <= sizes.data + data_size) { 0 3 3
228 0 ▶ LOG("ht_insert: data full, key='%s' used=%u cap=%u need=%u\n",
Branch: 1 branch
BranchTrueFalseTotal
LOG("ht_insert: data full, key='%s' used=%u cap=%u need=%u\n", 0 0 0
229 key, sizes.data, capacities.data, sizes.data + data_size);
230 0 ▶ if (stats) stats->reallocates++;
Branch: 1 branch
BranchTrueFalseTotal
if (stats) stats->reallocates++; 0 0 0
231 0 return OA_HASH_ERR_DATA_FULL;
232 }
233  
234 3 atomic_store_explicit(&ht->sizes->current_update, (uint64_t)index, memory_order_release);
235 3 commit_new_entry(ht, ht_index, key, key_size, value);
236 3 atomic_store_explicit(&ht->sizes->current_update, NOTHING_IS_UPDATED, memory_order_release);
237 }
238 4 return OA_HASH_OK;
239 }
240  
241 3 OA_HASH_ERR ht_lookup(HashTable *ht, const char *key, HashEntry *entry) {
242 3 uint64_t cur = atomic_load_explicit(&ht->sizes->current_update, memory_order_acquire);
243 3 ▶ if (cur != NOTHING_IS_UPDATED) {
Branch: 1 branch
BranchTrueFalseTotal
if (cur != NOTHING_IS_UPDATED) { 0 3 3
244 0 ▶ LOG("ht_lookup: invalid state, current_update=%" PRIu64 " key='%s'\n", cur, key);
Branch: 1 branch
BranchTrueFalseTotal
LOG("ht_lookup: invalid state, current_update=%" PRIu64 " key='%s'\n", cur, key); 0 0 0
245 0 return OA_HASH_INVALD_STATE;
246 }
247 3 HashIndexEntry *ht_index = 0;
248 3 find_index(ht, key, &ht_index, 0);
249 3 ▶ if (!ht_index || !((Key)ht_index->key).status) {
Branch: 2 branches
BranchTrueFalseTotal
if (!ht_index || !((Key)ht_index->key).status) { 3 0 3
if (!ht_index || !((Key)ht_index->key).status) { 1 2 3
250 1 return OA_HASH_ERR_NOT_FOUND;
251 }
252  
253 2 memcpy(entry->value, get_value(ht, ht_index), VALUE_SIZE);
254 2 entry->key = get_key(ht, ht_index);
255 2 return OA_HASH_OK;
256 }
257  
258 3 void ht_get_entry(HashTable* ht, HashIndexEntry * ht_index, HashEntry *entry) {
259 3 memcpy(entry->value, get_value(ht, ht_index), VALUE_SIZE);
260 3 entry->key = get_key(ht, ht_index);
261 3 }
262  
263 0 OA_HASH_ERR ht_copy(HashTable *dst, HashTable *src) {
264 0 ▶ if (dst->sizes->current_update != NOTHING_IS_UPDATED) {
Branch: 1 branch
BranchTrueFalseTotal
if (dst->sizes->current_update != NOTHING_IS_UPDATED) { 0 0 0
265 0 return OA_HASH_INVALD_STATE;
266 }
267 0 Sizes src_sizes = { .storable = src->sizes->sizes };
268 0 Sizes dst_sizes = { .storable = dst->sizes->sizes };
269 0 Sizes src_capacities = { .storable = src->sizes->capacities };
270 0 Sizes dst_capacities = { .storable = dst->sizes->capacities };
271 0 ▶ if (src_sizes.index + dst_sizes.index > dst_capacities.index) {
Branch: 1 branch
BranchTrueFalseTotal
if (src_sizes.index + dst_sizes.index > dst_capacities.index) { 0 0 0
272 0 return OA_HASH_ERR_INDEX_FULL;
273 }
274 0 ▶ if (src_sizes.data + dst_sizes.data > dst_capacities.data) {
Branch: 1 branch
BranchTrueFalseTotal
if (src_sizes.data + dst_sizes.data > dst_capacities.data) { 0 0 0
275 0 return OA_HASH_ERR_DATA_FULL;
276 }
277 0 ▶ for (size_t i = 0; i < src_capacities.index; i++) {
Branch: 1 branch
BranchTrueFalseTotal
for (size_t i = 0; i < src_capacities.index; i++) { 0 0 0
278 0 HashIndexEntry* ht_index = get_index(src, i);
279 0 ▶ if (!((Key)ht_index->key).status){
Branch: 1 branch
BranchTrueFalseTotal
if (!((Key)ht_index->key).status){ 0 0 0
280 0 continue;
281 }
282 0 char *key = get_key(src, ht_index);
283 0 HashIndexEntry* ht_new_index = 0;
284 0 find_index(dst, key, &ht_new_index,0);
285 0 ▶ if (!ht_new_index || ((Key)ht_new_index->key).status) {
Branch: 2 branches
BranchTrueFalseTotal
if (!ht_new_index || ((Key)ht_new_index->key).status) { 0 0 0
if (!ht_new_index || ((Key)ht_new_index->key).status) { 0 0 0
286 0 return OA_HASH_ERR_INVALID_ARGUMENT;
287 }
288 0 *ht_new_index = *ht_index;
289 0 dst_sizes.index += 1;
290 }
291 0 memcpy(dst->data_entries, src->data_entries, src_sizes.data * sizeof(HashDataEntry));
292 0 dst_sizes.data += src_sizes.data;
293 0 atomic_store_explicit(&dst->sizes->sizes, dst_sizes.storable, memory_order_release);
294 0 return OA_HASH_OK;
295 }
296  
297 0 void ht_clear_table(HashTable *ht) {
298 0 ▶ if (!ht) {
Branch: 1 branch
BranchTrueFalseTotal
if (!ht) { 0 0 0
299 0 return;
300 }
301 0 Sizes capacities = { .storable = atomic_load_explicit(&ht->sizes->capacities, memory_order_acquire) };
302 0 memset(ht->index_entries, 0, capacities.index * sizeof(HashIndexEntry));
303 0 memset(ht->data_entries, 0, capacities.data * sizeof(HashDataEntry));
304 0 atomic_store_explicit(&ht->sizes->current_update, NOTHING_IS_UPDATED, memory_order_release);
305 0 atomic_store_explicit(&ht->sizes->sizes, 0, memory_order_release);
306 }
307  
« src/shared.c ↑ Summary Simple.xs »