GCC Code Coverage Report

Directory: src/gate/
File: src/gate/maps.c
Date: 2026-09-21 06:26:40
Exec Total Coverage
Lines: 799 1033 77.3%
Functions: 94 113 83.2%
Branches: 318 506 62.8%
Line Branch Exec Source
1 /* GATE PROJECT LICENSE:
2 +----------------------------------------------------------------------------+
3 | Copyright (c) 2018-2026, Stefan Meislinger <sm@opengate.at> |
4 | All rights reserved. |
5 | |
6 | Redistribution and use in source and binary forms, with or without |
7 | modification, are permitted provided that the following conditions are met:|
8 | |
9 | 1. Redistributions of source code must retain the above copyright notice, |
10 | this list of conditions and the following disclaimer. |
11 | 2. Redistributions in binary form must reproduce the above copyright |
12 | notice, this list of conditions and the following disclaimer in the |
13 | documentation and/or other materials provided with the distribution. |
14 | |
15 | THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"|
16 | AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE |
17 | IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE |
18 | ARE DISCLAIMED.IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE |
19 | LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR |
20 | CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF |
21 | SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS |
22 | INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN |
23 | CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) |
24 | ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF |
25 | THE POSSIBILITY OF SUCH DAMAGE. |
26 +----------------------------------------------------------------------------+
27 */
28
29 #include "gate/maps.h"
30 #include "gate/debugging.h"
31 #include "gate/memalloc.h"
32 #include "gate/arrays.h"
33
34 /* based on https://en.wikipedia.org/wiki/Red%E2%80%93black_tree */
35
36 305223 static gate_treenode_t* gate_treenode_parent(gate_treenode_t* node)
37 {
38 305223 return node->parent;
39 }
40
41 103545 static gate_treenode_t* gate_treenode_sibling(gate_treenode_t* node)
42 {
43 103545 gate_treenode_t* parent = gate_treenode_parent(node);
44
2/2
✓ Branch 0 taken 4 times.
✓ Branch 1 taken 103541 times.
 103545 if (parent == NULL)
45 {
46 4 return NULL;
47 }
48
2/2
✓ Branch 0 taken 48200 times.
✓ Branch 1 taken 55341 times.
 103541 else if (node == parent->left)
49 {
50 48200 return parent->right;
51 }
52
1/2
✓ Branch 0 taken 55341 times.
✗ Branch 1 not taken.
 55341 else if (node == parent->right)
53 {
54 55341 return parent->left;
55 }
56 else
57 {
58 ✗ GATE_DEBUG_BREAKPOINT;
59 ✗ return NULL;
60 }
61 }
62
63 42953 static gate_treenode_t* gate_treenode_uncle(gate_treenode_t* node)
64 {
65 42953 gate_treenode_t* parent = gate_treenode_parent(node);
66
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 42953 times.
 42953 if (parent == NULL)
67 {
68 ✗ return NULL;
69 }
70 42953 return gate_treenode_sibling(parent);
71 }
72
73 23074 static void gate_treenode_rotate_left(gate_treenode_t** root, gate_treenode_t* node)
74 {
75 23074 gate_treenode_t* nnew = node->right;
76 23074 gate_treenode_t* parent = gate_treenode_parent(node);
77
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 23074 times.
 23074 GATE_DEBUG_ASSERT(nnew != NULL);
78 23074 node->right = nnew->left;
79 23074 nnew->left = node;
80 23074 node->parent = nnew;
81
82
2/2
✓ Branch 0 taken 5010 times.
✓ Branch 1 taken 18064 times.
 23074 if (node->right != NULL)
83 {
84 5010 node->right->parent = node;
85 }
86
2/2
✓ Branch 0 taken 22872 times.
✓ Branch 1 taken 202 times.
 23074 if (parent != NULL)
87 {
88
2/2
✓ Branch 0 taken 13859 times.
✓ Branch 1 taken 9013 times.
 22872 if (node == parent->left)
89 {
90 13859 parent->left = nnew;
91 }
92
1/2
✓ Branch 0 taken 9013 times.
✗ Branch 1 not taken.
 9013 else if (node == parent->right)
93 {
94 9013 parent->right = nnew;
95 }
96 }
97 else
98 {
99 202 *root = nnew;
100 }
101 23074 nnew->parent = parent;
102 23074 }
103
104 28536 static void gate_treenode_rotate_right(gate_treenode_t** root, gate_treenode_t* node)
105 {
106 28536 gate_treenode_t* nnew = node->left;
107 28536 gate_treenode_t* parent = gate_treenode_parent(node);
108
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 28536 times.
 28536 GATE_DEBUG_ASSERT(nnew != NULL);
109 28536 node->left = nnew->right;
110 28536 nnew->right = node;
111 28536 node->parent = nnew;
112
2/2
✓ Branch 0 taken 5813 times.
✓ Branch 1 taken 22723 times.
 28536 if (node->left != NULL)
113 {
114 5813 node->left->parent = node;
115 }
116
2/2
✓ Branch 0 taken 28384 times.
✓ Branch 1 taken 152 times.
 28536 if (parent != NULL)
117 {
118
2/2
✓ Branch 0 taken 8518 times.
✓ Branch 1 taken 19866 times.
 28384 if (node == parent->left)
119 {
120 8518 parent->left = nnew;
121 }
122
1/2
✓ Branch 0 taken 19866 times.
✗ Branch 1 not taken.
 19866 else if (node == parent->right)
123 {
124 19866 parent->right = nnew;
125 }
126 }
127 else
128 {
129 152 *root = nnew;
130 }
131 28536 nnew->parent = parent;
132 28536 }
133
134 155188 static gate_bool_t is_black(gate_treenode_t* node)
135 {
136
4/4
✓ Branch 0 taken 142223 times.
✓ Branch 1 taken 12965 times.
✓ Branch 2 taken 77021 times.
✓ Branch 3 taken 65202 times.
 155188 return (node == NULL) || (node->red == false);
137 }
138 77203 static gate_bool_t is_red(gate_treenode_t* node)
139 {
140
4/4
✓ Branch 0 taken 69966 times.
✓ Branch 1 taken 7237 times.
✓ Branch 2 taken 45060 times.
✓ Branch 3 taken 24906 times.
 77203 return (node == NULL) ? false : node->red;
141 }
142
143 83518 void gate_treenode_insert_repair_tree(gate_treenode_t** root, gate_treenode_t* node)
144 {
145 83518 gate_treenode_t* parent = gate_treenode_parent(node);
146
2/2
✓ Branch 0 taken 220 times.
✓ Branch 1 taken 83298 times.
 83518 if (parent == NULL)
147 {
148 /* case 1: element is root */
149 220 node->red = false;
150 }
151
2/2
✓ Branch 1 taken 42953 times.
✓ Branch 2 taken 40345 times.
 83298 else if (is_black(parent))
152 {
153 /* case 2: parent is BLACK -> nothing to do */
154 }
155 else
156 {
157 /* case 3: parent is RED */
158 42953 gate_treenode_t* uncle = gate_treenode_uncle(node);
159
4/4
✓ Branch 0 taken 27522 times.
✓ Branch 1 taken 15431 times.
✓ Branch 3 taken 19352 times.
✓ Branch 4 taken 8170 times.
 42953 if ((uncle != NULL) && is_red(uncle))
160 {
161 /*uncle is RED */
162 19352 parent->red = false;
163 19352 uncle->red = false;
164 19352 parent->parent->red = true;
165
166 19352 gate_treenode_insert_repair_tree(root, parent->parent);
167 }
168 else
169 {
170 /* case 4: uncle is BLACK */
171 23601 gate_treenode_t* grandparent = parent->parent;
172
2/2
✓ Branch 0 taken 23597 times.
✓ Branch 1 taken 4 times.
 23601 if (grandparent != NULL)
173 {
174
4/4
✓ Branch 0 taken 15654 times.
✓ Branch 1 taken 7943 times.
✓ Branch 2 taken 5347 times.
✓ Branch 3 taken 10307 times.
 23597 if ((grandparent->left != NULL) && (node == grandparent->left->right))
175 {
176 5347 gate_treenode_rotate_left(root, parent);
177 5347 node = node->left;
178 }
179
4/4
✓ Branch 0 taken 13896 times.
✓ Branch 1 taken 4354 times.
✓ Branch 2 taken 6142 times.
✓ Branch 3 taken 7754 times.
 18250 else if ((grandparent->right != NULL) && (node == grandparent->right->left))
180 {
181 6142 gate_treenode_rotate_right(root, parent);
182 6142 node = node->right;
183 }
184
185 /* case 4, part 2 */
186 23597 parent = gate_treenode_parent(node);
187 23597 grandparent = parent->parent;
188
189
2/2
✓ Branch 0 taken 12954 times.
✓ Branch 1 taken 10643 times.
 23597 if (node == parent->left)
190 {
191 12954 gate_treenode_rotate_right(root, grandparent);
192 }
193 else
194 {
195 10643 gate_treenode_rotate_left(root, grandparent);
196
197 }
198 23597 parent->red = false;
199 23597 grandparent->red = true;
200 }
201 }
202 }
203 83518 }
204
205 323099 gate_treenode_t* gate_treenode_find(gate_treenode_t* root, gate_comparer_t comparer, void const* key, gate_treenode_t** ptr_last_parent)
206 {
207 323099 gate_treenode_t* current = root;
208 323099 root = NULL;
209
210
2/2
✓ Branch 0 taken 6668448 times.
✓ Branch 1 taken 127239 times.
 6795687 while (current != NULL)
211 {
212 6668448 gate_intptr_t diff = comparer(key, current->mapping.key);
213
214
2/2
✓ Branch 0 taken 1105633 times.
✓ Branch 1 taken 5562815 times.
 6668448 if (diff < 0)
215 {
216 1105633 root = current;
217 1105633 current = current->left;
218 }
219
2/2
✓ Branch 0 taken 5366955 times.
✓ Branch 1 taken 195860 times.
 5562815 else if (diff > 0)
220 {
221 5366955 root = current;
222 5366955 current = current->right;
223 }
224 else /* if(diff == 0) */
225 {
226 195860 break;
227 }
228 }
229
1/2
✓ Branch 0 taken 323099 times.
✗ Branch 1 not taken.
 323099 if (ptr_last_parent != NULL)
230 {
231 323099 *ptr_last_parent = root;
232 }
233 323099 return current;
234 }
235
236 26586 static void gate_treenode_delete_repair_tree(gate_treenode_t** root, gate_treenode_t* node)
237 {
238 gate_treenode_t* sibling;
239
240 /* case 1 */
241
2/2
✓ Branch 0 taken 233 times.
✓ Branch 1 taken 26353 times.
 26586 if (node->parent == NULL)
242 {
243 /* node is root -> nothing to do */
244 233 return;
245 }
246
247 /* case 2 */
248 26353 sibling = gate_treenode_sibling(node);
249
250
2/2
✓ Branch 1 taken 5863 times.
✓ Branch 2 taken 20490 times.
 26353 if (is_red(sibling))
251 {
252 5863 node->parent->red = true;
253 5863 sibling->red = false;
254
2/2
✓ Branch 0 taken 2092 times.
✓ Branch 1 taken 3771 times.
 5863 if (node == node->parent->left)
255 {
256 2092 gate_treenode_rotate_left(root, node->parent);
257 }
258 else
259 {
260 3771 gate_treenode_rotate_right(root, node->parent);
261 }
262 }
263
264 /* update sibling for case 3 */
265 26353 sibling = gate_treenode_sibling(node);
266
2/2
✓ Branch 0 taken 11024 times.
✓ Branch 1 taken 15329 times.
 26353 if (sibling == NULL)
267 {
268 11024 return;
269 }
270
271 /* case 3 */
272
5/6
✓ Branch 1 taken 6145 times.
✓ Branch 2 taken 9184 times.
✓ Branch 4 taken 6145 times.
✗ Branch 5 not taken.
✓ Branch 6 taken 3831 times.
✓ Branch 7 taken 2314 times.
 21474 if (is_black(node->parent) && is_black(sibling) &&
273
2/2
✓ Branch 2 taken 2696 times.
✓ Branch 3 taken 1135 times.
 9976 is_black(sibling->left) && is_black(sibling->right))
274 {
275 2696 sibling->red = true;
276 2696 gate_treenode_delete_repair_tree(root, node->parent);
277 2696 return;
278 }
279
280 /* case 4 */
281
6/6
✓ Branch 1 taken 9184 times.
✓ Branch 2 taken 3449 times.
✓ Branch 4 taken 9150 times.
✓ Branch 5 taken 34 times.
✓ Branch 6 taken 6300 times.
✓ Branch 7 taken 2850 times.
 21783 if (is_red(node->parent) && is_black(sibling) &&
282
2/2
✓ Branch 2 taken 4713 times.
✓ Branch 3 taken 1587 times.
 15450 is_black(sibling->left) && is_black(sibling->right)
283 )
284 {
285 4713 sibling->red = true;
286 4713 node->parent->red = false;
287 4713 return;
288 }
289
290 /* case 5*/
291
2/2
✓ Branch 1 taken 7886 times.
✓ Branch 2 taken 34 times.
 7920 if (is_black(sibling))
292 {
293
5/6
✓ Branch 0 taken 3529 times.
✓ Branch 1 taken 4357 times.
✓ Branch 3 taken 1312 times.
✓ Branch 4 taken 2217 times.
✓ Branch 6 taken 1312 times.
✗ Branch 7 not taken.
 7886 if ((node == node->parent->left) && is_black(sibling->right) && is_red(sibling->left))
294 {
295 1312 sibling->red = true;
296 1312 sibling->left->red = false;
297 1312 gate_treenode_rotate_right(root, sibling);
298 }
299
5/6
✓ Branch 0 taken 4357 times.
✓ Branch 1 taken 2217 times.
✓ Branch 3 taken 1463 times.
✓ Branch 4 taken 2894 times.
✓ Branch 6 taken 1463 times.
✗ Branch 7 not taken.
 6574 else if ((node == node->parent->right) && is_black(sibling->left) && is_red(sibling->right))
300 {
301 1463 sibling->red = true;
302 1463 sibling->right->red = false;
303 1463 gate_treenode_rotate_left(root, sibling);
304 }
305
306 /* update sibling for case 6 */
307 7886 sibling = gate_treenode_sibling(node);
308 }
309
310 /* case 6 */
311
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 7920 times.
 7920 if (sibling == NULL)
312 {
313 ✗ return;
314 }
315
316 7920 sibling->red = node->parent->red;
317 7920 node->parent->red = false;
318
2/2
✓ Branch 0 taken 3533 times.
✓ Branch 1 taken 4387 times.
 7920 if (node == node->parent->left)
319 {
320
2/2
✓ Branch 1 taken 3529 times.
✓ Branch 2 taken 4 times.
 3533 if (is_red(sibling->right))
321 {
322 3529 sibling->right->red = false;
323 3529 gate_treenode_rotate_left(root, node->parent);
324 }
325 }
326
1/2
✓ Branch 0 taken 4387 times.
✗ Branch 1 not taken.
 4387 else if (node == node->parent->right)
327 {
328
2/2
✓ Branch 1 taken 4357 times.
✓ Branch 2 taken 30 times.
 4387 if (is_red(sibling->left))
329 {
330 4357 sibling->left->red = false;
331 4357 gate_treenode_rotate_right(root, node->parent);
332 }
333 }
334 else
335 {
336 ✗ GATE_DEBUG_BREAKPOINT;
337 }
338 }
339
340 288773 gate_treenode_t* gate_treenode_minimum(gate_treenode_t* node)
341 {
342 288773 gate_treenode_t* ret = node;
343
2/2
✓ Branch 0 taken 272508 times.
✓ Branch 1 taken 288773 times.
 561281 while (ret->left != NULL)
344 {
345 272508 ret = ret->left;
346 }
347 288773 return ret;
348 }
349 21827 gate_treenode_t* gate_treenode_maximum(gate_treenode_t* node)
350 {
351 21827 gate_treenode_t* ret = node;
352
2/2
✓ Branch 0 taken 19112 times.
✓ Branch 1 taken 21827 times.
 40939 while (ret->right != NULL)
353 {
354 19112 ret = ret->right;
355 }
356 21827 return ret;
357 }
358
359 62952 void gate_treenode_remove_repair_tree(gate_treenode_t** root, gate_treenode_t* node)
360 {
361 125904 gate_treenode_t** ptr_parent = (node->parent == NULL)
362 ? root
363
4/4
✓ Branch 0 taken 62670 times.
✓ Branch 1 taken 282 times.
✓ Branch 2 taken 28821 times.
✓ Branch 3 taken 33849 times.
 62952 : ((node == node->parent->left) ? &node->parent->left : &node->parent->right);
364
365
366
367
4/4
✓ Branch 0 taken 34462 times.
✓ Branch 1 taken 28490 times.
✓ Branch 2 taken 22226 times.
✓ Branch 3 taken 12236 times.
 62952 if ((node->left == NULL) && (node->right == NULL))
368 {
369 /* no children */
370 22226 *ptr_parent = NULL;
371 }
372
4/4
✓ Branch 0 taken 28490 times.
✓ Branch 1 taken 12236 times.
✓ Branch 2 taken 21821 times.
✓ Branch 3 taken 6669 times.
 40726 else if ((node->left != NULL) && (node->right != NULL))
373 21821 {
374 /* two children */
375 21821 gate_treenode_t* replacement = gate_treenode_maximum(node->left);
376
377 21821 replacement->right = node->right;
378 21821 replacement->parent->right = replacement->left;
379
2/2
✓ Branch 0 taken 5462 times.
✓ Branch 1 taken 16359 times.
 21821 if (replacement->left != NULL)
380 {
381 5462 replacement->left->parent = replacement->parent;
382 }
383
2/2
✓ Branch 0 taken 8783 times.
✓ Branch 1 taken 13038 times.
 21821 if (replacement != node->left)
384 {
385 8783 replacement->left = node->left;
386 }
387
388 21821 replacement->parent = node->parent;
389 21821 *ptr_parent = replacement;
390
391
2/2
✓ Branch 0 taken 12639 times.
✓ Branch 1 taken 9182 times.
 21821 if (replacement->left != NULL)
392 {
393 12639 replacement->left->parent = replacement;
394 }
395
1/2
✓ Branch 0 taken 21821 times.
✗ Branch 1 not taken.
 21821 if (replacement->right != NULL)
396 {
397 21821 replacement->right->parent = replacement;
398 }
399
400
2/2
✓ Branch 0 taken 15829 times.
✓ Branch 1 taken 5992 times.
 21821 if (node->red == false)
401 {
402
2/2
✓ Branch 0 taken 10844 times.
✓ Branch 1 taken 4985 times.
 15829 if (replacement->red == true)
403 {
404 10844 replacement->red = false;
405 }
406 else
407 {
408 4985 gate_treenode_delete_repair_tree(root, replacement);
409 }
410 }
411 }
412
2/2
✓ Branch 0 taken 6669 times.
✓ Branch 1 taken 12236 times.
 18905 else if ((node->left != NULL))
413 {
414 /* one child on left side */
415 6669 *ptr_parent = node->left;
416 6669 node->left->parent = node->parent;
417 6669 gate_treenode_delete_repair_tree(root, node->left);
418 }
419 else
420 {
421 /* one child on right side */
422 12236 *ptr_parent = node->right;
423 12236 node->right->parent = node->parent;
424 12236 gate_treenode_delete_repair_tree(root, node->right);
425 }
426 62952 }
427
428 ✗ gate_treenode_t* gate_treenode_next(gate_treenode_t* node)
429 {
430 for (;;)
431 {
432 ✗ if (node->right != NULL)
433 {
434 ✗ return gate_treenode_minimum(node->right);
435 }
436 else
437 {
438 ✗ if (node->parent == NULL)
439 {
440 ✗ return NULL;
441 }
442 ✗ if (node == node->parent->left)
443 {
444 ✗ return node->parent;
445 }
446 ✗ node = node->parent;
447 }
448 }
449 }
450 ✗ gate_treenode_t* gate_treenode_prev(gate_treenode_t* node)
451 {
452 for (;;)
453 {
454 ✗ if (node->left != NULL)
455 {
456 ✗ return gate_treenode_maximum(node->left);
457 }
458 else
459 {
460 ✗ if (node->parent == NULL)
461 {
462 ✗ return NULL;
463 }
464 ✗ if (node == node->parent->right)
465 {
466 ✗ return node->parent;
467 }
468 ✗ node = node->parent;
469 }
470 }
471 }
472
473
474
475
476 /************************
477 * MAP implementation *
478 ************************/
479
480 ✗ gate_result_t gate_map_copy_constructor(void* dest, void const* src)
481 {
482 ✗ if (NULL == gate_map_copy((gate_map_t*)dest, (gate_map_t const*)src))
483 {
484 ✗ return GATE_RESULT_OUTOFMEMORY;
485 }
486 else
487 {
488 ✗ return GATE_RESULT_OK;
489 }
490 }
491
492 ✗ void gate_map_destructor(void* dest)
493 {
494 ✗ gate_map_destroy((gate_map_t*)dest);
495 ✗ }
496
497
498 194 gate_map_t* gate_map_create(gate_map_t* m, gate_comparer_t key_comparer,
499 gate_size_t key_size, gate_mem_copyctor_t key_ctor, gate_mem_dtor_t key_dtor,
500 gate_size_t value_size, gate_mem_copyctor_t value_ctor, gate_mem_dtor_t value_dtor
501 )
502 {
503 194 m->item_count = 0;
504 194 m->key_comparer = key_comparer;
505
506 194 m->key_size = key_size;
507 194 m->key_constructor = key_ctor;
508 194 m->key_destructor = key_dtor;
509
510 194 m->value_size = value_size;
511 194 m->value_constructor = value_ctor;
512 194 m->value_destructor = value_dtor;
513
514 194 m->root = NULL;
515
516 194 return m;
517 }
518
519 64202 static gate_treenode_t* gate_map_create_node(gate_map_t* m, void const* key, void const* value)
520 {
521 64202 gate_size_t const keysize = gate_mem_align_size(m->key_size);
522 64202 gate_size_t const valuesize = gate_mem_align_size(m->value_size);
523 64202 gate_treenode_t* ret = (gate_treenode_t*)gate_mem_alloc(sizeof(gate_treenode_t) + keysize + valuesize);
524
525
1/2
✓ Branch 0 taken 64202 times.
✗ Branch 1 not taken.
 64202 if (ret != NULL)
526 {
527 64202 char* ptr = NULL;
528 do
529 {
530 gate_result_t result;
531 char* keyptr;
532 64202 ptr = (char*)ret;
533 64202 ret->red = true;
534 64202 ret->parent = NULL;
535 64202 ret->left = NULL;
536 64202 ret->right = NULL;
537 64202 keyptr = ptr + sizeof(gate_treenode_t);
538 64202 ret->mapping.key = keyptr;
539 64202 ret->mapping.value = ptr + (sizeof(gate_treenode_t) + keysize);
540 64202 result = gate_mem_copy_construct(keyptr, key, m->key_size, m->key_constructor);
541
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 64202 times.
 64202 if (GATE_FAILED(result))
542 {
543 /* key construction failed */
544 ✗ ret = NULL;
545 ✗ break;
546 }
547
548 64202 result = gate_mem_copy_construct(ret->mapping.value, value, m->value_size, m->value_constructor);
549
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 64202 times.
 64202 if (GATE_FAILED(result))
550 {
551 ✗ ret = NULL;
552 ✗ break;
553 }
554
555 /* all succeeded, no cleanup required */
556 64202 ptr = NULL;
557 } while (0);
558
559
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 64202 times.
 64202 if (ptr != NULL)
560 {
561 ✗ gate_mem_dealloc(ptr);
562 }
563 }
564 64202 return ret;
565 }
566 64202 static void gate_map_delete_node(gate_map_t* m, gate_treenode_t* node)
567 {
568
2/2
✓ Branch 0 taken 1014 times.
✓ Branch 1 taken 63188 times.
 64202 if (m->value_destructor != NULL)
569 {
570 1014 m->value_destructor(node->mapping.value);
571 }
572
2/2
✓ Branch 0 taken 1239 times.
✓ Branch 1 taken 62963 times.
 64202 if (m->key_destructor != NULL)
573 {
574 1239 m->key_destructor((void*)node->mapping.key);
575 }
576 64202 gate_mem_dealloc(node);
577 64202 }
578
579 2717 static void gate_map_delete_nodes(gate_map_t* m, gate_treenode_t* node)
580 {
581
2/2
✓ Branch 0 taken 1250 times.
✓ Branch 1 taken 1467 times.
 2717 if (node != NULL)
582 {
583 1250 gate_map_delete_nodes(m, node->left);
584 1250 gate_map_delete_nodes(m, node->right);
585 1250 gate_map_delete_node(m, node);
586 }
587 2717 }
588
589 217 void gate_map_clear(gate_map_t* m)
590 {
591 217 gate_treenode_t* node = m->root;
592 217 m->root = NULL;
593 217 m->item_count = 0;
594 217 gate_map_delete_nodes(m, node);
595 217 }
596
597 194 void gate_map_destroy(gate_map_t* m)
598 {
599 194 gate_map_clear(m);
600 194 gate_mem_clear(m, sizeof(gate_map_t));
601 194 }
602
603 2021 gate_size_t gate_map_count(gate_map_t const* m)
604 {
605 2021 return m->item_count;
606 }
607
608 ✗ gate_size_t gate_map_merge(gate_map_t* m, gate_map_t const* with)
609 {
610 ✗ gate_size_t count = 0;
611 ✗ gate_map_iterator_t iter = gate_map_first(with);
612 ✗ while (gate_map_iterator_valid(iter))
613 {
614 ✗ if (gate_map_iterator_valid(gate_map_add(m, iter->mapping.key, iter->mapping.value)))
615 {
616 ✗ ++count;
617 }
618 ✗ iter = gate_map_iterator_next(iter);
619 }
620 ✗ return count;
621 }
622 ✗ gate_size_t gate_map_remove_keys(gate_map_t* m, gate_map_t const* keys)
623 {
624 ✗ gate_size_t count = 0;
625 ✗ gate_map_iterator_t iter = gate_map_first(keys);
626 ✗ while (gate_map_iterator_valid(iter))
627 {
628 ✗ if (gate_map_remove(m, iter->mapping.key))
629 {
630 ✗ ++count;
631 }
632 ✗ iter = gate_map_iterator_next(iter);
633 }
634 ✗ return count;
635 }
636
637
638 36 static gate_bool_t gate_map_clone_node(gate_map_t* m, gate_treenode_t const* src, gate_treenode_t** dst)
639 {
640 36 gate_treenode_t* newnode = gate_map_create_node(m, src->mapping.key, src->mapping.value);
641
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 36 times.
 36 if (newnode == NULL)
642 {
643 ✗ return false;
644 }
645 36 newnode->red = src->red;
646 36 *dst = newnode;
647
648
2/2
✓ Branch 0 taken 11 times.
✓ Branch 1 taken 25 times.
 36 if (src->left != NULL)
649 {
650
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 11 times.
 11 if (!gate_map_clone_node(m, src->left, &newnode->left))
651 {
652 ✗ return false;
653 }
654 11 newnode->left->parent = newnode;
655 }
656
2/2
✓ Branch 0 taken 11 times.
✓ Branch 1 taken 25 times.
 36 if (src->right != NULL)
657 {
658
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 11 times.
 11 if (!gate_map_clone_node(m, src->right, &newnode->right))
659 {
660 ✗ return false;
661 }
662 11 newnode->right->parent = newnode;
663 }
664 36 return true;
665 }
666
667 23 gate_map_t* gate_map_copy(gate_map_t* dst, gate_map_t const* src)
668 {
669 23 dst->item_count = src->item_count;
670 23 dst->key_comparer = src->key_comparer;
671
672 23 dst->key_size = src->key_size;
673 23 dst->key_constructor = src->key_constructor;
674 23 dst->key_destructor = src->key_destructor;
675
676 23 dst->value_size = src->value_size;
677 23 dst->value_constructor = src->value_constructor;
678 23 dst->value_destructor = src->value_destructor;
679
680 23 dst->root = NULL;
681
2/2
✓ Branch 0 taken 14 times.
✓ Branch 1 taken 9 times.
 23 if (src->root != NULL)
682 {
683
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 14 times.
 14 if (!gate_map_clone_node(dst, src->root, &dst->root))
684 {
685 /* cloning failed */
686 ✗ gate_map_destroy(dst);
687 ✗ return NULL;
688 }
689 }
690 23 return dst;
691 }
692
693
694 126767 gate_map_iterator_t gate_map_add(gate_map_t* m, void const* key, void const* value)
695 {
696 126767 gate_treenode_t* node = NULL;
697
698
2/2
✓ Branch 0 taken 97 times.
✓ Branch 1 taken 126670 times.
 126767 if (m->root == NULL)
699 {
700 97 node = gate_map_create_node(m, key, value);
701 97 m->root = node;
702 97 gate_treenode_insert_repair_tree(&m->root, node);
703 97 ++m->item_count;
704 }
705 else
706 {
707 gate_result_t result;
708 126670 gate_treenode_t* parentnode = NULL;
709 126670 node = gate_treenode_find(m->root, m->key_comparer, key, &parentnode);
710
2/2
✓ Branch 0 taken 62601 times.
✓ Branch 1 taken 64069 times.
 126670 if (node != NULL)
711 {
712 /* item found -> overwrite value */
713 62601 gate_mem_destruct(node->mapping.value, m->value_destructor);
714 62601 result = gate_mem_copy_construct(node->mapping.value, value, m->value_size, m->value_constructor);
715
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 62601 times.
 62601 if (GATE_FAILED(result))
716 {
717 /* construction failed -> we cannot recover from this error */
718 ✗ gate_mem_clear(node->mapping.value, m->value_size);
719 ✗ gate_map_remove(m, key);
720 ✗ node = NULL;
721 }
722 }
723 else
724 {
725 gate_intptr_t cmp;
726 64069 node = gate_map_create_node(m, key, value);
727 64069 cmp = m->key_comparer(key, parentnode->mapping.key);
728
2/2
✓ Branch 0 taken 39497 times.
✓ Branch 1 taken 24572 times.
 64069 if (cmp < 0)
729 {
730 39497 parentnode->left = node;
731 }
732 else
733 {
734
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 24572 times.
 24572 GATE_DEBUG_ASSERT(cmp > 0);
735 24572 parentnode->right = node;
736 }
737 64069 node->parent = parentnode;
738 64069 gate_treenode_insert_repair_tree(&m->root, node);
739 64069 ++m->item_count;
740 }
741 }
742 126767 return node;
743 }
744 126036 gate_bool_t gate_map_remove(gate_map_t* m, void const* key)
745 {
746 126036 gate_treenode_t* parentnode = NULL;
747 126036 gate_treenode_t* node = gate_treenode_find(m->root, m->key_comparer, key, &parentnode);
748
2/2
✓ Branch 0 taken 63084 times.
✓ Branch 1 taken 62952 times.
 126036 if (node == NULL)
749 {
750 63084 return false;
751 }
752 else
753 {
754 62952 gate_treenode_remove_repair_tree(&m->root, node);
755
756 62952 gate_map_delete_node(m, node);
757 62952 --m->item_count;
758 62952 return true;
759 }
760 }
761
762 3 gate_bool_t gate_map_is_empty(gate_map_t const* m)
763 {
764
3/4
✓ Branch 0 taken 3 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 2 times.
✓ Branch 3 taken 1 times.
 3 return (m == NULL) ? true : (m->item_count == 0);
765 }
766
767 34973 gate_map_iterator_t gate_map_get(gate_map_t const* m, void const* key)
768 {
769 34973 gate_treenode_t* parentnode = NULL;
770 34973 gate_treenode_t* node = gate_treenode_find(m->root, m->key_comparer, key, &parentnode);
771 34973 return node;
772 }
773
774
775 2099 gate_map_iterator_t gate_map_first(gate_map_t const* m)
776 {
777
2/2
✓ Branch 0 taken 2062 times.
✓ Branch 1 taken 37 times.
 2099 return (m->root == NULL) ? NULL : gate_treenode_minimum(m->root);
778 }
779 ✗ gate_map_iterator_t gate_map_last(gate_map_t const* m)
780 {
781 ✗ return (m->root == NULL) ? NULL : gate_treenode_maximum(m->root);
782 }
783 561274 gate_map_iterator_t gate_map_iterator_next(gate_map_iterator_t iterator)
784 {
785
1/2
✓ Branch 0 taken 561274 times.
✗ Branch 1 not taken.
 561274 if (iterator != NULL)
786 {
787
2/2
✓ Branch 0 taken 286711 times.
✓ Branch 1 taken 274563 times.
 561274 if (iterator->right != NULL)
788 {
789 286711 iterator = gate_treenode_minimum(iterator->right);
790 }
791 else
792 {
793 for (;;)
794 {
795
2/2
✓ Branch 0 taken 2052 times.
✓ Branch 1 taken 559221 times.
 561273 if (iterator->parent == NULL)
796 {
797 2052 iterator = NULL;
798 2052 break;
799 }
800
2/2
✓ Branch 0 taken 272511 times.
✓ Branch 1 taken 286710 times.
 559221 if (iterator == iterator->parent->left)
801 {
802 272511 iterator = iterator->parent;
803 272511 break;
804 }
805 286710 iterator = iterator->parent;
806 }
807 }
808 }
809 561274 return iterator;
810 }
811 6 gate_map_iterator_t gate_map_iterator_prev(gate_map_iterator_t iterator)
812 {
813
1/2
✓ Branch 0 taken 6 times.
✗ Branch 1 not taken.
 6 if (iterator != NULL)
814 {
815
1/2
✓ Branch 0 taken 6 times.
✗ Branch 1 not taken.
 6 if (iterator->left != NULL)
816 {
817 6 iterator = gate_treenode_maximum(iterator->left);
818 }
819 else
820 {
821 for (;;)
822 {
823 ✗ if (iterator->parent == NULL)
824 {
825 ✗ iterator = NULL;
826 ✗ break;
827 }
828 ✗ if (iterator == iterator->parent->right)
829 {
830 ✗ iterator = iterator->parent;
831 ✗ break;
832 }
833 ✗ iterator = iterator->parent;
834 }
835 }
836 }
837 6 return iterator;
838 }
839
840 501043 gate_bool_t gate_map_iterator_equals(gate_map_iterator_t iter1, gate_map_iterator_t iter2)
841 {
842 501043 return iter1 == iter2;
843 }
844 4 gate_map_iterator_t gate_map_end(gate_map_t const* m)
845 {
846 (void)m;
847 4 return NULL;
848 }
849 1065708 gate_bool_t gate_map_iterator_valid(gate_map_iterator_t iterator)
850 {
851 1065708 return iterator != NULL;
852 }
853
854
855 35420 void* gate_map_get_value(gate_map_t const* m, void const* key)
856 {
857 35420 gate_treenode_t* parentnode = NULL;
858 35420 gate_treenode_t* node = gate_treenode_find(m->root, m->key_comparer, key, &parentnode);
859
2/2
✓ Branch 0 taken 35400 times.
✓ Branch 1 taken 20 times.
 35420 if (node != NULL)
860 {
861 35400 return node->mapping.value;
862 }
863 20 return NULL;
864 }
865
866 311158 void const* gate_map_iterator_key(gate_map_iterator_t iterator)
867 {
868
1/2
✓ Branch 0 taken 311158 times.
✗ Branch 1 not taken.
 311158 if (iterator != NULL)
869 {
870 311158 return (void const*)iterator->mapping.key;
871 }
872 else
873 {
874 ✗ return NULL;
875 }
876 }
877 74 void* gate_map_iterator_value(gate_map_iterator_t iterator)
878 {
879
1/2
✓ Branch 0 taken 74 times.
✗ Branch 1 not taken.
 74 if (iterator != NULL)
880 {
881 74 return (void*)iterator->mapping.value;
882 }
883 else
884 {
885 ✗ return NULL;
886 }
887 }
888
889
890 ✗ static gate_bool_t gate_map_enumerate_is_valid(gate_enumerator_t const* enumerator)
891 {
892 ✗ return gate_map_iterator_valid((gate_map_iterator_t)enumerator->current_position);
893 }
894 ✗ static gate_bool_t gate_map_enumerate_next(gate_enumerator_t* enumerator)
895 {
896 ✗ if (enumerator->current_position)
897 {
898 ✗ enumerator->current_position = (void*)gate_map_iterator_next((gate_map_iterator_t)enumerator->current_position);
899 ✗ return gate_map_iterator_valid((gate_map_iterator_t)enumerator->current_position);
900 }
901 else
902 {
903 ✗ return false;
904 }
905 }
906 ✗ static void const* gate_map_enumerate_get(gate_enumerator_t const* enumerator)
907 {
908 ✗ gate_map_iterator_t iter = (gate_map_iterator_t)enumerator->current_position;
909 ✗ return &iter->mapping;
910 }
911
912 ✗ gate_enumerator_t* gate_map_enumerate(gate_map_t const* m, gate_enumerator_t* enumerator)
913 {
914 ✗ enumerator->is_valid = &gate_map_enumerate_is_valid;
915 ✗ enumerator->next = &gate_map_enumerate_next;
916 ✗ enumerator->get = &gate_map_enumerate_get;
917
918 ✗ enumerator->ptr_origin = (void*)m;
919 ✗ enumerator->current_position = (void*)gate_map_first(m);
920 ✗ enumerator->end_position = (void*)gate_map_end(m);
921 ✗ return enumerator;
922 }
923
924
925
926
927
928 /*********************************
929 * Sequence map implementation *
930 *********************************/
931
932 44 gate_result_t gate_flatmap_copy_constructor(void* dest, void const* src)
933 {
934
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 44 times.
 44 if (NULL == gate_flatmap_copy(dest, src))
935 {
936 ✗ return GATE_RESULT_OUTOFMEMORY;
937 }
938 else
939 {
940 44 return GATE_RESULT_OK;
941 }
942 }
943 44 void gate_flatmap_destructor(void* dest)
944 {
945 44 gate_flatmap_destroy(dest);
946 44 }
947
948
949 4523 static gate_mapping_t* gate_flatmap_entry_create(gate_flatmap_t* m, void const* key, void const* value)
950 {
951 4523 gate_mapping_t* ret = NULL;
952 4523 gate_mapping_t* entry_block = NULL;
953
954 do
955 {
956 4523 char* key_block = NULL;
957 4523 char* value_block = NULL;
958 gate_result_t result;
959
960 4523 entry_block = (gate_mapping_t*)gate_mem_alloc(m->item_size);
961
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 4523 times.
 4523 if (entry_block == NULL)
962 {
963 ✗ break;
964 }
965 4523 gate_mem_clear(entry_block, m->item_size);
966
967 4523 key_block = ((char*)entry_block) + m->item_key_offset;
968 4523 value_block = ((char*)entry_block) + m->item_value_offset;
969
970 4523 result = gate_mem_copy_construct(key_block, key, m->key_size, m->key_constructor);
971
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 4523 times.
 4523 if (GATE_FAILED(result))
972 {
973 /* failed to allocate key */
974 ✗ break;
975 }
976
977 4523 result = gate_mem_copy_construct(value_block, value, m->value_size, m->value_constructor);
978
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 4523 times.
 4523 if (GATE_FAILED(result))
979 {
980 /* failed to allocate value */
981 ✗ gate_mem_destruct(key_block, m->key_destructor);
982 ✗ break;
983 }
984 4523 entry_block->key = key_block;
985 4523 entry_block->value = value_block;
986
987 4523 ret = entry_block;
988 4523 entry_block = NULL;
989
990 } while (0);
991
992
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 4523 times.
 4523 if (entry_block != NULL)
993 {
994 ✗ gate_mem_dealloc(entry_block);
995 }
996
997 4523 return ret;
998 }
999
1000 4523 static void gate_flatmap_entry_destroy(gate_flatmap_t* m, gate_mapping_t* entry)
1001 {
1002 4523 void* key_block = (void*)entry->key;
1003 4523 void* value_block = entry->value;
1004
1005 4523 gate_mem_destruct(key_block, m->key_destructor);
1006 4523 gate_mem_destruct(value_block, m->value_destructor);
1007 4523 gate_mem_dealloc(entry);
1008 4523 }
1009
1010
1011 2027 gate_flatmap_t* gate_flatmap_create(gate_flatmap_t* m,
1012 gate_comparer_t key_comparer, gate_size_t key_size, gate_mem_copyctor_t key_ctor, gate_mem_dtor_t key_dtor,
1013 gate_size_t value_size, gate_mem_copyctor_t value_ctor, gate_mem_dtor_t value_dtor)
1014 {
1015 2027 gate_flatmap_t* ret = NULL;
1016 do
1017 {
1018 2027 gate_mem_clear(m, sizeof(gate_flatmap_t));
1019
1020 2027 m->key_comparer = key_comparer;
1021 2027 m->key_size = key_size;
1022 2027 m->key_constructor = key_ctor;
1023 2027 m->key_destructor = key_dtor;
1024
1025 2027 m->value_size = value_size;
1026 2027 m->value_constructor = value_ctor;
1027 2027 m->value_destructor = value_dtor;
1028
1029 2027 m->item_key_offset = gate_mem_align_size(sizeof(gate_mapping_t));
1030 2027 m->item_value_offset = m->item_key_offset + gate_mem_align_size(key_size);
1031 2027 m->item_size = m->item_value_offset + gate_mem_align_size(value_size);
1032
1033 2027 m->item_capacity = 0;
1034 2027 m->item_count = 0;
1035 2027 m->items = NULL;
1036
1037 2027 ret = m;
1038 } while (0);
1039 2027 return ret;
1040 }
1041
1042 1940 static gate_mapping_t** gate_flatmap_reserve(gate_flatmap_t* m, gate_size_t new_capacity)
1043 {
1044
1/2
✓ Branch 0 taken 1940 times.
✗ Branch 1 not taken.
 1940 if (new_capacity > m->item_capacity)
1045 {
1046 1940 gate_size_t new_size = sizeof(gate_mapping_t*) * new_capacity;
1047 1940 gate_mapping_t** new_contents = (gate_mapping_t**)gate_mem_alloc(new_size);
1048
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 1940 times.
 1940 if (new_contents == NULL)
1049 {
1050 ✗ return NULL;
1051 }
1052 1940 gate_mem_clear(new_contents, new_size);
1053
2/2
✓ Branch 0 taken 52 times.
✓ Branch 1 taken 1888 times.
 1940 if (m->items)
1054 {
1055
1/2
✓ Branch 0 taken 52 times.
✗ Branch 1 not taken.
 52 if (m->item_count > 0)
1056 {
1057 52 gate_mem_copy(new_contents, m->items, sizeof(gate_mapping_t*) * m->item_count);
1058 }
1059 52 gate_mem_dealloc(m->items);
1060 }
1061 1940 m->items = new_contents;
1062 1940 m->item_capacity = new_capacity;
1063 }
1064 1940 return m->items;
1065 }
1066
1067 4517 static gate_mapping_t** gate_flatmap_new_entry_slot(gate_flatmap_t* m)
1068 {
1069
2/2
✓ Branch 0 taken 410 times.
✓ Branch 1 taken 4107 times.
 4517 if (m->item_count >= m->item_capacity)
1070 {
1071 410 gate_size_t new_capacity = m->item_count + 4 + m->item_count / 2;
1072
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 410 times.
 410 if (NULL == gate_flatmap_reserve(m, new_capacity))
1073 {
1074 ✗ return NULL;
1075 }
1076 }
1077 4517 return &m->items[m->item_count];
1078 }
1079
1080 1607 gate_flatmap_t* gate_flatmap_copy(gate_flatmap_t* dst, gate_flatmap_t const* src)
1081 {
1082 1607 gate_flatmap_t* ret = NULL;
1083
1084 do
1085 {
1086 1607 int failed = 0;
1087
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 1607 times.
 1607 if (NULL == gate_flatmap_create(dst, src->key_comparer,
1088 src->key_size, src->key_constructor, src->key_destructor,
1089 src->value_size, src->value_constructor, src->value_destructor))
1090 {
1091 ✗ dst = NULL;
1092 ✗ break;
1093 }
1094
1095
2/2
✓ Branch 0 taken 1530 times.
✓ Branch 1 taken 77 times.
 1607 if (src->item_count > 0)
1096 {
1097 gate_flatmap_iterator_t iter;
1098
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 1530 times.
 1530 if (NULL == gate_flatmap_reserve(dst, src->item_count))
1099 {
1100 ✗ break;
1101 }
1102 1530 iter = gate_flatmap_first(src);
1103
2/2
✓ Branch 1 taken 3565 times.
✓ Branch 2 taken 1530 times.
 5095 while (gate_flatmap_iterator_valid(src, iter))
1104 {
1105 3565 void const* ptr_key = gate_flatmap_iterator_key(iter);
1106 3565 void const* ptr_value = gate_flatmap_iterator_value(iter);
1107
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 3565 times.
 3565 if (NULL == gate_flatmap_add(dst, ptr_key, ptr_value))
1108 {
1109 ✗ ++failed;
1110 ✗ break;
1111 }
1112 3565 iter = gate_flatmap_iterator_next(iter);
1113 }
1114 }
1115
1116
1/2
✓ Branch 0 taken 1607 times.
✗ Branch 1 not taken.
 1607 if (!failed)
1117 {
1118 1607 ret = dst;
1119 1607 dst = NULL;
1120 }
1121 } while (0);
1122
1123
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 1607 times.
 1607 if (dst != NULL)
1124 {
1125 ✗ gate_flatmap_destroy(dst);
1126 }
1127
1128 1607 return ret;
1129 }
1130
1131 1981 void gate_flatmap_destroy(gate_flatmap_t* m)
1132 {
1133 1981 gate_flatmap_clear(m);
1134
2/2
✓ Branch 0 taken 1888 times.
✓ Branch 1 taken 93 times.
 1981 if (m->items)
1135 {
1136 1888 gate_mem_dealloc(m->items);
1137 }
1138 1981 m->items = NULL;
1139 1981 m->item_capacity = 0;
1140 /*gate_mem_clear(m, sizeof(gate_flatmap_t));*/
1141 1981 }
1142
1143 57 gate_size_t gate_flatmap_count(gate_flatmap_t const* m)
1144 {
1145 57 return m->item_count;
1146 }
1147
1148
1149 4523 gate_flatmap_iterator_t gate_flatmap_add(gate_flatmap_t* m, void const* key, void const* value)
1150 {
1151 4523 gate_flatmap_iterator_t ret = NULL;
1152 gate_mapping_t* new_entry;
1153 do
1154 {
1155 gate_flatmap_iterator_t iter;
1156 gate_mapping_t** slot;
1157 4523 new_entry = gate_flatmap_entry_create(m, key, value);
1158
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 4523 times.
 4523 if (new_entry == NULL)
1159 {
1160 ✗ break;
1161 }
1162
1163 4523 iter = gate_flatmap_get(m, key);
1164
2/2
✓ Branch 1 taken 4517 times.
✓ Branch 2 taken 6 times.
 4523 if (!gate_flatmap_iterator_valid(m, iter))
1165 {
1166 4517 slot = gate_flatmap_new_entry_slot(m);
1167
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 4517 times.
 4517 if (slot == NULL)
1168 {
1169 ✗ break;
1170 }
1171 4517 ++m->item_count;
1172 }
1173 else
1174 {
1175 /* iterator points to existing slot-mapping-entry */
1176 6 slot = (gate_mapping_t**)iter;
1177 6 gate_flatmap_entry_destroy(m, *slot);
1178 }
1179 4523 *slot = new_entry; /* overwrite slot-mapping-entry */
1180
1181 4523 new_entry = NULL;
1182 4523 ret = (gate_flatmap_iterator_t)slot;
1183 } while (0);
1184
1185
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 4523 times.
 4523 if (new_entry != NULL)
1186 {
1187 ✗ gate_flatmap_entry_destroy(m, new_entry);
1188 }
1189 4523 return ret;
1190 }
1191
1192
1193 14 gate_bool_t gate_flatmap_remove(gate_flatmap_t* m, void const* key)
1194 {
1195 14 gate_bool_t ret = false;
1196 14 gate_flatmap_iterator_t entry = gate_flatmap_get(m, key);
1197
1198
2/2
✓ Branch 1 taken 12 times.
✓ Branch 2 taken 2 times.
 14 if (entry != gate_flatmap_end(m))
1199 {
1200 12 gate_flatmap_iterator_t first_entry = gate_flatmap_first(m);
1201 12 gate_size_t index = entry - first_entry;
1202 12 gate_flatmap_entry_destroy(m, *(void**)entry);
1203
2/2
✓ Branch 0 taken 2 times.
✓ Branch 1 taken 10 times.
 12 if (index + 1 < m->item_count)
1204 {
1205 2 gate_mem_move((void*)entry, entry + 1, (m->item_count - index - 1) * sizeof(gate_mapping_t*));
1206 }
1207 12 --m->item_count;
1208 12 m->items[m->item_count] = NULL;
1209 12 ret = true;
1210 }
1211 14 return ret;
1212 }
1213
1214 ✗ gate_bool_t gate_flatmap_is_empty(gate_flatmap_t const* m)
1215 {
1216 ✗ return m->item_count == 0;
1217 }
1218
1219 1982 void gate_flatmap_clear(gate_flatmap_t* m)
1220 {
1221
2/2
✓ Branch 0 taken 1889 times.
✓ Branch 1 taken 93 times.
 1982 if (m->item_capacity != 0)
1222 {
1223 1889 gate_mapping_t** ptr = m->items;
1224 1889 gate_size_t count = m->item_count;
1225
2/2
✓ Branch 0 taken 4505 times.
✓ Branch 1 taken 1889 times.
 6394 while (count-- != 0)
1226 {
1227 4505 gate_flatmap_entry_destroy(m, *ptr);
1228 4505 ++ptr;
1229 }
1230 1889 gate_mem_clear(m->items, m->item_capacity * sizeof(gate_mapping_t*));
1231 1889 m->item_count = 0;
1232 }
1233 1982 }
1234
1235 ✗ gate_size_t gate_flatmap_merge(gate_flatmap_t* m, gate_flatmap_t const* with)
1236 {
1237 ✗ gate_size_t merged_items = 0;
1238
1239 ✗ if ((with->key_size == m->key_size) && (with->value_size == m->value_size))
1240 {
1241 ✗ gate_size_t count = with->item_count;
1242 ✗ gate_flatmap_iterator_t ptr = (gate_flatmap_iterator_t)with->items;
1243 ✗ while (count-- != 0)
1244 {
1245 ✗ void const* current_key = gate_flatmap_iterator_key(ptr);
1246 ✗ void const* current_value = gate_flatmap_iterator_value(ptr);
1247 ✗ if (NULL != gate_flatmap_add(m, current_key, current_value))
1248 {
1249 ✗ ++merged_items;
1250 }
1251 ✗ ++ptr;
1252 }
1253 }
1254 ✗ return merged_items;
1255 }
1256
1257 ✗ gate_size_t gate_flatmap_remove_keys(gate_flatmap_t* m, gate_flatmap_t const* keys)
1258 {
1259 ✗ gate_size_t removed_items = 0;
1260
1261 ✗ if (keys->key_size == m->key_size)
1262 {
1263 ✗ gate_flatmap_iterator_t ptr = (gate_flatmap_iterator_t)keys->items;
1264 ✗ gate_size_t count = keys->item_count;
1265
1266 ✗ while (count-- != 0)
1267 {
1268 ✗ void const* current_key = gate_flatmap_iterator_key(ptr);
1269 ✗ if (gate_flatmap_remove(m, current_key))
1270 {
1271 ✗ ++removed_items;
1272 }
1273 ✗ ++ptr;
1274 }
1275 }
1276 ✗ return removed_items;
1277
1278 }
1279
1280 6174 gate_flatmap_iterator_t gate_flatmap_get(gate_flatmap_t const* m, void const* key)
1281 {
1282 6174 gate_flatmap_iterator_t iter = (gate_flatmap_iterator_t)m->items;
1283 6174 gate_size_t count = m->item_count;
1284
1285
2/2
✓ Branch 0 taken 7908 times.
✓ Branch 1 taken 4565 times.
 12473 while (count-- != 0)
1286 {
1287 7908 void const* ptr_key = gate_flatmap_iterator_key(iter);
1288
1/2
✓ Branch 0 taken 7908 times.
✗ Branch 1 not taken.
 7908 if (ptr_key)
1289 {
1290
2/2
✓ Branch 1 taken 1609 times.
✓ Branch 2 taken 6299 times.
 7908 if (0 == gate_compare_types(ptr_key, key, m->key_size, m->key_comparer))
1291 {
1292 /* current iterator matches given key */
1293 1609 return iter;
1294 }
1295 }
1296 6299 ++iter;
1297 }
1298 4565 return gate_flatmap_end(m);
1299 }
1300
1301 12056 gate_flatmap_iterator_t gate_flatmap_first(gate_flatmap_t const* m)
1302 {
1303
2/2
✓ Branch 0 taken 12051 times.
✓ Branch 1 taken 5 times.
 12056 if (m->item_count != 0)
1304 {
1305 12051 return (gate_flatmap_iterator_t)m->items;
1306 }
1307 5 return gate_flatmap_end(m);
1308 }
1309
1310 10418 gate_flatmap_iterator_t gate_flatmap_last(gate_flatmap_t const* m)
1311 {
1312
1/2
✓ Branch 0 taken 10418 times.
✗ Branch 1 not taken.
 10418 if (m->item_count != 0)
1313 {
1314 10418 return (gate_flatmap_iterator_t)&m->items[m->item_count - 1];
1315 }
1316 ✗ return gate_flatmap_end(m);
1317 }
1318
1319 4612 gate_flatmap_iterator_t gate_flatmap_end(gate_flatmap_t const* m)
1320 {
1321
2/2
✓ Branch 0 taken 2698 times.
✓ Branch 1 taken 1914 times.
 4612 if (m->item_count != 0)
1322 {
1323 2698 return (gate_flatmap_iterator_t)&m->items[m->item_count];
1324 }
1325 1914 return NULL;
1326 }
1327
1328 3760 gate_flatmap_iterator_t gate_flatmap_iterator_next(gate_flatmap_iterator_t iterator)
1329 {
1330
1/2
✓ Branch 0 taken 3760 times.
✗ Branch 1 not taken.
 3760 if (iterator)
1331 {
1332 3760 ++iterator;
1333 }
1334 3760 return iterator;
1335 }
1336
1337 4 gate_flatmap_iterator_t gate_flatmap_iterator_prev(gate_flatmap_iterator_t iterator)
1338 {
1339
1/2
✓ Branch 0 taken 4 times.
✗ Branch 1 not taken.
 4 if (iterator)
1340 {
1341 4 --iterator;
1342 }
1343 4 return iterator;
1344 }
1345
1346 27 gate_bool_t gate_flatmap_iterator_equals(gate_flatmap_iterator_t iter1, gate_flatmap_iterator_t iter2)
1347 {
1348 27 return iter1 == iter2;
1349 }
1350
1351 12331 gate_bool_t gate_flatmap_iterator_valid(gate_flatmap_t const* m, gate_flatmap_iterator_t iterator)
1352 {
1353
2/2
✓ Branch 0 taken 10418 times.
✓ Branch 1 taken 1913 times.
 12331 if (iterator != NULL)
1354 {
1355
3/4
✓ Branch 1 taken 10418 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 6152 times.
✓ Branch 5 taken 4266 times.
 10418 return ((iterator >= gate_flatmap_first(m)) && (iterator <= gate_flatmap_last(m)));
1356 }
1357 1913 return false;
1358 }
1359
1360
1361 3 static gate_bool_t gate_flatmap_enumerate_is_valid(gate_enumerator_t const* enumerator)
1362 {
1363 6 return gate_flatmap_iterator_valid((gate_flatmap_t*)enumerator->ptr_origin,
1364 3 (gate_flatmap_iterator_t)enumerator->current_position);
1365 }
1366 2 static gate_bool_t gate_flatmap_enumerate_next(gate_enumerator_t* enumerator)
1367 {
1368
1/2
✓ Branch 0 taken 2 times.
✗ Branch 1 not taken.
 2 if (enumerator->current_position != NULL)
1369 {
1370 2 enumerator->current_position =
1371 2 (void*)gate_flatmap_iterator_next((gate_flatmap_iterator_t)enumerator->current_position);
1372 2 return gate_flatmap_iterator_valid((gate_flatmap_t*)enumerator->ptr_origin,
1373 2 (gate_flatmap_iterator_t)enumerator->current_position);
1374 }
1375 else
1376 {
1377 ✗ return false;
1378 }
1379 }
1380 2 static void const* gate_flatmap_enumerate_get(gate_enumerator_t const* enumerator)
1381 {
1382 2 return (void const*)(*(void**)enumerator->current_position);
1383 }
1384
1385 4 gate_enumerator_t* gate_flatmap_enumerate(gate_flatmap_t const* m, gate_enumerator_t* enumerator)
1386 {
1387 4 enumerator->is_valid = &gate_flatmap_enumerate_is_valid;
1388 4 enumerator->next = &gate_flatmap_enumerate_next;
1389 4 enumerator->get = &gate_flatmap_enumerate_get;
1390
1391 4 enumerator->ptr_origin = (void*)m;
1392 4 enumerator->current_position = (void*)gate_flatmap_first(m);
1393 4 enumerator->end_position = (void*)gate_flatmap_end(m);
1394 4 return enumerator;
1395 }
1396
1397 5 void* gate_flatmap_get_value(gate_flatmap_t const* m, void const* key)
1398 {
1399 5 void* ret = NULL;
1400 5 gate_flatmap_iterator_t iter = gate_flatmap_get(m, key);
1401
1/2
✓ Branch 1 taken 5 times.
✗ Branch 2 not taken.
 5 if (iter != gate_flatmap_end(m))
1402 {
1403 5 return gate_flatmap_iterator_value(iter);
1404 }
1405 ✗ return ret;
1406 }
1407
1408 11676 void const* gate_flatmap_iterator_key(gate_flatmap_iterator_t iterator)
1409 {
1410
2/4
✓ Branch 0 taken 11676 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 11676 times.
✗ Branch 3 not taken.
 11676 if (iterator && *iterator)
1411 {
1412 11676 return (*iterator)->key;
1413 }
1414 ✗ return NULL;
1415 }
1416 6057 void* gate_flatmap_iterator_value(gate_flatmap_iterator_t iterator)
1417 {
1418
2/4
✓ Branch 0 taken 6057 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 6057 times.
✗ Branch 3 not taken.
 6057 if (iterator && *iterator)
1419 {
1420 6057 return (*iterator)->value;
1421 }
1422 ✗ return NULL;
1423 }
1424
1425
1426
1427
1428
1429 /***************************************
1430 * Unordered hash map implementation *
1431 ***************************************/
1432
1433 29 static gate_size_t gate_hashmap_get_bucket_index(gate_hashmap_t const* m, void const* key)
1434 {
1435 29 gate_hash_code_t hash = m->hash_generator(key);
1436 29 gate_size_t bucket_index = (gate_size_t)hash % (gate_size_t)m->bucket_count;
1437 29 return bucket_index;
1438 }
1439
1440 30 static gate_size_t gate_hashmap_get_aligned_sized(gate_size_t sz)
1441 {
1442 30 gate_size_t diff = sz % sizeof(gate_c_maxalign_t);
1443
1/2
✓ Branch 0 taken 30 times.
✗ Branch 1 not taken.
 30 if (diff != 0)
1444 {
1445 30 sz += (sizeof(gate_c_maxalign_t) - diff);
1446 }
1447 30 return sz;
1448 }
1449
1450 typedef struct gate_hashmap_entry_impl_class
1451 {
1452 gate_mapping_t base;
1453 gate_c_maxalign_t data_area;
1454 } gate_hashmap_entry_impl_t;
1455
1456 15 static gate_mapping_t* gate_hashmap_create_entry(gate_hashmap_t const* m, void const* key, void const* value)
1457 {
1458 gate_result_t result;
1459 15 gate_size_t key_size = gate_hashmap_get_aligned_sized(m->key_size);
1460 15 gate_size_t value_size = gate_hashmap_get_aligned_sized(m->value_size);
1461 15 gate_size_t entry_size = sizeof(gate_hashmap_entry_impl_t) - sizeof(gate_c_maxalign_t) + key_size + value_size;
1462 15 gate_hashmap_entry_impl_t* ptr_entry = (gate_hashmap_entry_impl_t*)gate_mem_alloc(entry_size);
1463 char* ptr;
1464
1465
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 15 times.
 15 if (NULL == ptr_entry)
1466 {
1467 ✗ return NULL;
1468 }
1469 15 ptr = (char*)&ptr_entry->data_area;
1470 15 ptr_entry->base.key = ptr;
1471 15 ptr_entry->base.value = (ptr + value_size);
1472
1473 15 result = gate_mem_copy_construct(ptr, key, m->key_size, m->key_constructor);
1474
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 15 times.
 15 if (GATE_FAILED(result))
1475 {
1476 ✗ gate_mem_dealloc(ptr_entry);
1477 ✗ return NULL;
1478 }
1479 15 result = gate_mem_copy_construct(ptr_entry->base.value, value, m->value_size, m->value_constructor);
1480
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 15 times.
 15 if (GATE_FAILED(result))
1481 {
1482 ✗ gate_mem_destruct(ptr, m->key_destructor);
1483 ✗ gate_mem_dealloc(ptr_entry);
1484 ✗ return NULL;
1485 }
1486 15 return &ptr_entry->base;
1487 }
1488 15 static void gate_hashmap_destroy_entry(gate_hashmap_t const* m, gate_mapping_t* entry)
1489 {
1490
1/2
✓ Branch 0 taken 15 times.
✗ Branch 1 not taken.
 15 if (entry->key)
1491 {
1492 15 gate_mem_destruct((char*)entry->key, m->key_destructor);
1493 }
1494
1/2
✓ Branch 0 taken 15 times.
✗ Branch 1 not taken.
 15 if (entry->value)
1495 {
1496 15 gate_mem_destruct((char*)entry->value, m->value_destructor);
1497 }
1498 15 gate_mem_dealloc(entry);
1499 15 }
1500
1501 14 static gate_bool_t gate_hashmap_resolve_key(gate_hashmap_t const* m, void const* key, gate_size_t* bucket_index, gate_size_t* entry_index)
1502 {
1503 14 gate_size_t index = gate_hashmap_get_bucket_index(m, key);
1504 14 gate_hashmap_bucket_t const* bucket = m->buckets[index];
1505
1506 14 *bucket_index = index;
1507
2/2
✓ Branch 0 taken 13 times.
✓ Branch 1 taken 1 times.
 14 if (bucket != NULL)
1508 {
1509 13 gate_size_t count = bucket->size;
1510
1/2
✓ Branch 0 taken 13 times.
✗ Branch 1 not taken.
 13 for (index = 0; index != count; ++index)
1511 {
1512 13 gate_mapping_t const* ptr_entry = bucket->entries[index];
1513 13 gate_intptr_t comp = gate_compare_types(ptr_entry->key, key, m->key_size, m->key_comparer);
1514
1/2
✓ Branch 0 taken 13 times.
✗ Branch 1 not taken.
 13 if (0 == comp)
1515 {
1516 13 *entry_index = index;
1517 13 return true;
1518 }
1519 }
1520 }
1521 1 return false;
1522 }
1523
1524 15 static gate_hashmap_bucket_t* gate_hashmap_create_bucket(gate_hashmap_t* m, gate_size_t entry_count)
1525 {
1526 15 gate_size_t bucket_size = sizeof(gate_hashmap_bucket_t) + sizeof(gate_mapping_t*) * (entry_count - 1);
1527 15 gate_hashmap_bucket_t* bucket = gate_mem_alloc(bucket_size);
1528 (void)m;
1529
1/2
✓ Branch 0 taken 15 times.
✗ Branch 1 not taken.
 15 if (NULL != bucket)
1530 {
1531 15 gate_mem_clear(bucket, bucket_size);
1532 15 bucket->capacity = entry_count;
1533 15 bucket->size = 0;
1534 }
1535 15 return bucket;
1536 }
1537
1538 15 static gate_result_t gate_hashmap_insert_entry(gate_hashmap_t* m, gate_mapping_t* insert_entry)
1539 {
1540 15 gate_hashmap_bucket_t* bucket = NULL;
1541 gate_size_t index;
1542 gate_size_t count;
1543
1544
1/2
✓ Branch 0 taken 15 times.
✗ Branch 1 not taken.
 15 if (m->bucket_count != 0)
1545 {
1546 15 index = gate_hashmap_get_bucket_index(m, insert_entry->key);
1547 15 bucket = m->buckets[index];
1548 }
1549
1550
1/2
✓ Branch 0 taken 15 times.
✗ Branch 1 not taken.
 15 if (bucket == NULL)
1551 {
1552 15 bucket = gate_hashmap_create_bucket(m, 8);
1553
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 15 times.
 15 if (bucket == NULL)
1554 {
1555 ✗ return GATE_RESULT_OUTOFMEMORY;
1556 }
1557 else
1558 {
1559 15 m->buckets[index] = bucket;
1560 }
1561 }
1562
1563 15 count = bucket->size;
1564
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 15 times.
 15 for (index = 0; index != count; ++index)
1565 {
1566 ✗ gate_mapping_t* ptr_entry = bucket->entries[index];
1567 ✗ gate_intptr_t comp = gate_compare_types(ptr_entry->key, insert_entry->key, m->key_size, m->key_comparer);
1568 ✗ if (0 == comp)
1569 {
1570 /* replace existing entry */
1571 ✗ gate_hashmap_destroy_entry(m, ptr_entry);
1572 ✗ bucket->entries[index] = insert_entry;
1573 ✗ return GATE_RESULT_OK;
1574 }
1575 }
1576
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 15 times.
 15 if (bucket->size >= bucket->capacity)
1577 {
1578 /* create new bucket with greater array size */
1579 ✗ gate_size_t new_capacity = bucket->size + 4 + bucket->size / 2;
1580 ✗ gate_hashmap_bucket_t* new_bucket = gate_hashmap_create_bucket(m, new_capacity);
1581 ✗ if (new_bucket == NULL)
1582 {
1583 ✗ return GATE_RESULT_OUTOFMEMORY;
1584 }
1585 ✗ gate_mem_copy(&new_bucket->entries[0], &bucket->entries[0], sizeof(gate_mapping_t*) * bucket->size);
1586 ✗ new_bucket->size = bucket->size;
1587 ✗ m->buckets[index] = new_bucket;
1588 ✗ gate_mem_dealloc(bucket);
1589 ✗ bucket = new_bucket;
1590 }
1591
1592 /* add new entry to bucket */
1593 15 bucket->entries[bucket->size] = insert_entry;
1594 15 ++bucket->size;
1595 15 ++m->entry_count;
1596 15 return GATE_RESULT_OK;
1597
1598 }
1599
1600 15 static gate_result_t gate_hashmap_insert(gate_hashmap_t* m, void const* key, void const* value)
1601 {
1602 15 gate_result_t ret = GATE_RESULT_FAILED;
1603 15 gate_mapping_t* new_entry = gate_hashmap_create_entry(m, key, value);
1604
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 15 times.
 15 if (NULL == new_entry)
1605 {
1606 ✗ ret = GATE_RESULT_OUTOFMEMORY;
1607 }
1608 else
1609 {
1610 15 ret = gate_hashmap_insert_entry(m, new_entry);
1611
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 15 times.
 15 if (GATE_FAILED(ret))
1612 {
1613 ✗ gate_hashmap_destroy_entry(m, new_entry);
1614 }
1615 }
1616 15 return ret;
1617 }
1618
1619
1620 //static gate_hashmap_bucket_t* gate_hashmap_access
1621
1622 6 gate_hashmap_t* gate_hashmap_create(gate_hashmap_t* m, gate_comparer_t key_comparer, gate_type_hash_generator_t hash_function,
1623 gate_size_t key_size, gate_mem_copyctor_t key_ctor, gate_mem_dtor_t key_dtor,
1624 gate_size_t value_size, gate_mem_copyctor_t value_ctor, gate_mem_dtor_t value_dtor)
1625 {
1626 6 gate_mem_clear(m, sizeof(gate_hashmap_t));
1627 6 m->key_comparer = key_comparer;
1628 6 m->hash_generator = hash_function;
1629
1630 6 m->key_size = key_size;
1631 6 m->key_constructor = key_ctor;
1632 6 m->key_destructor = key_dtor;
1633
1634 6 m->value_size = value_size;
1635 6 m->value_constructor = value_ctor;
1636 6 m->value_destructor = value_dtor;
1637
1638 6 m->entry_count = 0;
1639 6 m->bucket_count = 0;
1640 6 m->buckets = NULL;
1641 6 return m;
1642 }
1643
1644 #if defined(GATE_SYS_DOS) || defined(GATE_SYS_WIN16)
1645
1646 static gate_size_t const bucket_thresholds[] = {
1647 16384,
1648 4096,
1649 1024,
1650 256,
1651 32
1652 };
1653
1654 #else
1655
1656 static gate_size_t const bucket_thresholds[] = {
1657 16777216UL,
1658 1048576UL,
1659 65536UL,
1660 4096UL,
1661 64UL
1662 };
1663
1664 #endif
1665
1666 static gate_size_t const bucket_thresholds_count = (sizeof(bucket_thresholds) / sizeof(bucket_thresholds[0]));
1667
1668 5 static void gate_hashmap_detach_all_entries(gate_hashmap_t* m)
1669 {
1670 gate_size_t buck_index, entry_index;
1671
1672
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 5 times.
 5 for (buck_index = 0; buck_index < m->bucket_count; ++buck_index)
1673 {
1674 ✗ gate_hashmap_bucket_t* ptr_bucket = m->buckets[buck_index];
1675 ✗ if (ptr_bucket)
1676 {
1677 ✗ for (entry_index = 0; entry_index < ptr_bucket->size; ++entry_index)
1678 {
1679 ✗ ptr_bucket->entries[entry_index] = NULL;
1680 }
1681 ✗ ptr_bucket->size = 0;
1682 }
1683 }
1684 5 m->entry_count = 0;
1685 5 }
1686
1687 5 static gate_result_t gate_hashmap_update_bucket_count(gate_hashmap_t* m)
1688 {
1689 gate_size_t index;
1690 5 gate_size_t new_bucket_count = 0;
1691 gate_hashmap_t new_hashmap;
1692
1693
2/2
✓ Branch 0 taken 25 times.
✓ Branch 1 taken 5 times.
 30 for (index = 0; index != bucket_thresholds_count; ++index)
1694 {
1695
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 25 times.
 25 if (m->entry_count >= bucket_thresholds[index])
1696 {
1697 ✗ new_bucket_count = bucket_thresholds[index];
1698 ✗ break;
1699 }
1700 }
1701
1/2
✓ Branch 0 taken 5 times.
✗ Branch 1 not taken.
 5 if (new_bucket_count == 0)
1702 {
1703 5 new_bucket_count = bucket_thresholds[bucket_thresholds_count - 1];
1704 }
1705
1/2
✓ Branch 0 taken 5 times.
✗ Branch 1 not taken.
 5 if (m->bucket_count < new_bucket_count)
1706 {
1707 gate_size_t sz;
1708 gate_size_t buck_index;
1709 5 gate_mem_copy(&new_hashmap, m, sizeof(gate_hashmap_t));
1710
1711 5 new_hashmap.bucket_count = new_bucket_count;
1712 5 new_hashmap.entry_count = 0;
1713 5 sz = sizeof(gate_hashmap_bucket_t*) * new_bucket_count;
1714 5 new_hashmap.buckets = (gate_hashmap_bucket_t**)gate_mem_alloc(sz);
1715
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 5 times.
 5 if (NULL == new_hashmap.buckets)
1716 {
1717 ✗ return GATE_RESULT_OUTOFMEMORY;
1718 }
1719 5 gate_mem_clear(new_hashmap.buckets, sz);
1720
1721
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 5 times.
 5 for (buck_index = 0; buck_index < m->bucket_count; ++buck_index)
1722 {
1723 ✗ gate_hashmap_bucket_t* ptr_bucket = m->buckets[buck_index];
1724 ✗ if (ptr_bucket)
1725 {
1726 gate_size_t entry_index;
1727 ✗ for (entry_index = 0; entry_index < ptr_bucket->size; ++entry_index)
1728 {
1729 ✗ gate_mapping_t* ptr_entry = ptr_bucket->entries[entry_index];
1730 /* attach existing entries to new hashmap */
1731 ✗ gate_result_t result = gate_hashmap_insert_entry(&new_hashmap, ptr_entry);
1732 ✗ if (GATE_FAILED(result))
1733 {
1734 /* remove attached entries from new hashmap */
1735 ✗ gate_hashmap_detach_all_entries(&new_hashmap);
1736 ✗ gate_hashmap_destroy(&new_hashmap);
1737 ✗ return result;
1738 }
1739 }
1740 }
1741 }
1742 /* all entries were transfered to new_hashmap */
1743
1744 5 gate_hashmap_detach_all_entries(m); /* remove old hashmap's entry references */
1745 5 gate_mem_copy(m, &new_hashmap, sizeof(gate_hashmap_t));
1746 5 gate_mem_clear(&new_hashmap, sizeof(gate_hashmap_t));
1747 }
1748 5 return GATE_RESULT_OK;
1749 }
1750
1751 15 static gate_result_t gate_hashmap_check_bucket_count(gate_hashmap_t* m)
1752 {
1753
2/2
✓ Branch 0 taken 5 times.
✓ Branch 1 taken 10 times.
 15 if (m->entry_count >= m->bucket_count)
1754 {
1755 5 return gate_hashmap_update_bucket_count(m);
1756 }
1757 else
1758 {
1759 10 return GATE_RESULT_OK;
1760 }
1761 }
1762
1763 2 gate_hashmap_t* gate_hashmap_copy(gate_hashmap_t* dst, gate_hashmap_t const* src)
1764 {
1765 gate_hashmap_iterator_t iter;
1766
1767
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 2 times.
 2 if (NULL == gate_hashmap_create(dst, src->key_comparer, src->hash_generator,
1768 src->key_size, src->key_constructor, src->key_destructor,
1769 src->value_size, src->value_constructor, src->value_destructor))
1770 {
1771 ✗ return NULL;
1772 }
1773
1774
2/2
✓ Branch 3 taken 6 times.
✓ Branch 4 taken 2 times.
 8 for (iter = gate_hashmap_first(src); gate_hashmap_iterator_valid(iter); iter = gate_hashmap_iterator_next(iter))
1775 {
1776 6 void const* ptr_key = gate_hashmap_iterator_key(iter);
1777 6 void const* ptr_value = gate_hashmap_iterator_value(iter);
1778
1779 6 gate_result_t result = gate_hashmap_check_bucket_count(dst);
1780
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 6 times.
 6 if (GATE_FAILED(result))
1781 {
1782 ✗ gate_hashmap_destroy(dst);
1783 ✗ return NULL;
1784 }
1785 6 result = gate_hashmap_insert(dst, ptr_key, ptr_value);
1786
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 6 times.
 6 if (GATE_FAILED(result))
1787 {
1788 ✗ gate_hashmap_destroy(dst);
1789 ✗ return NULL;
1790 }
1791 }
1792 2 return dst;
1793 }
1794 6 void gate_hashmap_destroy(gate_hashmap_t* m)
1795 {
1796 6 gate_hashmap_clear(m);
1797
3/4
✓ Branch 0 taken 5 times.
✓ Branch 1 taken 1 times.
✓ Branch 2 taken 5 times.
✗ Branch 3 not taken.
 6 if (m->buckets != NULL && m->bucket_count != 0)
1798 {
1799 5 gate_mem_dealloc(m->buckets);
1800 }
1801 6 m->buckets = NULL;
1802 6 m->bucket_count = 0;
1803 6 }
1804 8 gate_size_t gate_hashmap_count(gate_hashmap_t const* m)
1805 {
1806 8 return m->entry_count;
1807 }
1808
1809 9 gate_hashmap_iterator_t gate_hashmap_add(gate_hashmap_t* m, void const* key, void const* value)
1810 {
1811 gate_hashmap_iterator_t ret;
1812
1813 do
1814 {
1815 9 gate_hashmap_iterator_t end = gate_hashmap_end(m);
1816 gate_bool_t found;
1817 gate_result_t result;
1818
1819 9 result = gate_hashmap_check_bucket_count(m);
1820
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 9 times.
 9 if (GATE_FAILED(result))
1821 {
1822 ✗ ret = end;
1823 ✗ break;
1824 }
1825
1826 9 result = gate_hashmap_insert(m, key, value);
1827
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 9 times.
 9 if (GATE_FAILED(result))
1828 {
1829 ✗ ret = end;
1830 ✗ break;
1831 }
1832
1833 9 ret.hashmap = m;
1834 9 found = gate_hashmap_resolve_key(m, key, &ret.bucket_index, &ret.entry_index);
1835
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 9 times.
 9 if (!found)
1836 {
1837 ✗ ret = end;
1838 }
1839
1840 } while (0);
1841
1842 9 return ret;
1843 }
1844 1 gate_bool_t gate_hashmap_remove(gate_hashmap_t* m, void const* key)
1845 {
1846 1 gate_bool_t removed = false;
1847 gate_size_t bucket;
1848 gate_size_t entry;
1849 1 gate_bool_t resolved = gate_hashmap_resolve_key(m, key, &bucket, &entry);
1850
1/2
✓ Branch 0 taken 1 times.
✗ Branch 1 not taken.
 1 if (resolved)
1851 {
1852 1 gate_hashmap_bucket_t* ptr_bucket = m->buckets[bucket];
1853 1 gate_hashmap_destroy_entry(m, ptr_bucket->entries[entry]);
1854 1 --ptr_bucket->size;
1855
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 1 times.
 1 if (entry < ptr_bucket->size)
1856 {
1857 ✗ ptr_bucket->entries[entry] = ptr_bucket->entries[ptr_bucket->size];
1858 ✗ ptr_bucket->entries[ptr_bucket->size] = NULL;
1859 }
1860 else
1861 {
1862 1 ptr_bucket->entries[entry] = NULL;
1863 }
1864 1 --m->entry_count;
1865 1 removed = true;
1866 }
1867 1 return removed;
1868 }
1869 ✗ gate_bool_t gate_hashmap_is_empty(gate_hashmap_t const* m)
1870 {
1871 ✗ return m->entry_count == 0;
1872 }
1873 7 void gate_hashmap_clear(gate_hashmap_t* m)
1874 {
1875 gate_size_t bucket;
1876
1877
2/2
✓ Branch 0 taken 384 times.
✓ Branch 1 taken 7 times.
 391 for (bucket = 0; bucket < m->bucket_count; ++bucket)
1878 {
1879 384 gate_hashmap_bucket_t* ptr_bucket = m->buckets[bucket];
1880
2/2
✓ Branch 0 taken 15 times.
✓ Branch 1 taken 369 times.
 384 if (ptr_bucket)
1881 {
1882 gate_size_t entry;
1883
2/2
✓ Branch 0 taken 14 times.
✓ Branch 1 taken 15 times.
 29 for (entry = 0; entry != ptr_bucket->size; ++entry)
1884 {
1885 14 gate_mapping_t* ptr_entry = ptr_bucket->entries[entry];
1886
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 14 times.
 14 GATE_DEBUG_ASSERT(ptr_entry != NULL);
1887 14 gate_hashmap_destroy_entry(m, ptr_entry);
1888 }
1889 15 gate_mem_dealloc(ptr_bucket);
1890 15 m->buckets[bucket] = NULL;
1891 }
1892 }
1893 7 m->entry_count = 0;
1894 7 }
1895 ✗ gate_size_t gate_hashmap_merge(gate_hashmap_t* m, gate_hashmap_t const* with)
1896 {
1897 ✗ gate_hashmap_iterator_t iter = gate_hashmap_first(with);
1898 ✗ gate_size_t ret = 0;
1899
1900 ✗ while (gate_hashmap_iterator_valid(iter))
1901 {
1902 ✗ void const* ptr_key = gate_hashmap_iterator_key(iter);
1903 ✗ void const* ptr_value = gate_hashmap_iterator_value(iter);
1904 ✗ if (gate_hashmap_iterator_valid(gate_hashmap_add(m, ptr_key, ptr_value)))
1905 {
1906 ✗ ++ret;
1907 }
1908 }
1909 ✗ return ret;
1910 }
1911 ✗ gate_size_t gate_hashmap_remove_keys(gate_hashmap_t* m, gate_hashmap_t const* keys)
1912 {
1913 ✗ gate_hashmap_iterator_t iter = gate_hashmap_first(keys);
1914 ✗ gate_size_t ret = 0;
1915
1916 ✗ while (gate_hashmap_iterator_valid(iter))
1917 {
1918 ✗ void const* ptr_key = gate_hashmap_iterator_key(iter);
1919 ✗ if (gate_hashmap_remove(m, ptr_key))
1920 {
1921 ✗ ++ret;
1922 }
1923 }
1924 ✗ return ret;
1925 }
1926
1927 4 gate_hashmap_iterator_t gate_hashmap_get(gate_hashmap_t const* m, void const* key)
1928 {
1929 gate_hashmap_iterator_t iter;
1930 4 gate_bool_t found = gate_hashmap_resolve_key(m, key, &iter.bucket_index, &iter.entry_index);
1931
2/2
✓ Branch 0 taken 3 times.
✓ Branch 1 taken 1 times.
 4 if (found)
1932 {
1933 3 iter.hashmap = m;
1934 }
1935 else
1936 {
1937 1 iter = gate_hashmap_end(m);
1938 }
1939 4 return iter;
1940 }
1941 5 gate_hashmap_iterator_t gate_hashmap_first(gate_hashmap_t const* m)
1942 {
1943 gate_size_t bucket;
1944
1945
1/2
✓ Branch 0 taken 5 times.
✗ Branch 1 not taken.
 5 for (bucket = 0; bucket < m->bucket_count; ++bucket)
1946 {
1947
1/2
✓ Branch 0 taken 5 times.
✗ Branch 1 not taken.
 5 if (m->buckets[bucket])
1948 {
1949
1/2
✓ Branch 0 taken 5 times.
✗ Branch 1 not taken.
 5 if (m->buckets[bucket]->size > 0)
1950 {
1951 gate_hashmap_iterator_t new_iter;
1952 5 new_iter.hashmap = m;
1953 5 new_iter.bucket_index = bucket;
1954 5 new_iter.entry_index = 0;
1955
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 5 times.
 5 GATE_DEBUG_ASSERT(m->buckets[new_iter.bucket_index]->entries[new_iter.entry_index] != NULL);
1956 5 return new_iter;
1957 }
1958 }
1959 }
1960 ✗ return gate_hashmap_end(m);
1961 }
1962 ✗ gate_hashmap_iterator_t gate_hashmap_last(gate_hashmap_t const* m)
1963 {
1964 gate_size_t bucket;
1965
1966 ✗ for (bucket = m->bucket_count; bucket > 0; )
1967 {
1968 ✗ --bucket;
1969 ✗ if (m->buckets[bucket])
1970 {
1971 ✗ if (m->buckets[bucket]->size > 0)
1972 {
1973 gate_hashmap_iterator_t new_iter;
1974 ✗ new_iter.hashmap = m;
1975 ✗ new_iter.bucket_index = bucket;
1976 ✗ new_iter.entry_index = m->buckets[bucket]->size - 1;
1977 ✗ GATE_DEBUG_ASSERT(m->buckets[new_iter.bucket_index]->entries[new_iter.entry_index] != NULL);
1978 ✗ return new_iter;
1979 }
1980 }
1981 }
1982 ✗ return gate_hashmap_end(m);
1983 }
1984 17 gate_hashmap_iterator_t gate_hashmap_end(gate_hashmap_t const* m)
1985 {
1986 gate_hashmap_iterator_t iter;
1987 17 iter.hashmap = m;
1988 17 iter.bucket_index = (gate_size_t)(-1);
1989 17 iter.entry_index = (gate_size_t)(-1);
1990 17 return iter;
1991 }
1992 13 gate_hashmap_iterator_t gate_hashmap_iterator_next(gate_hashmap_iterator_t iterator)
1993 {
1994 13 gate_hashmap_t const* m = iterator.hashmap;
1995
1996
1/2
✓ Branch 1 taken 13 times.
✗ Branch 2 not taken.
 13 if (gate_hashmap_iterator_valid(iterator))
1997 {
1998 gate_hashmap_iterator_t new_iter;
1999 13 gate_size_t bucket = iterator.bucket_index;
2000
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 13 times.
 13 if (iterator.entry_index + 1 < m->buckets[bucket]->size)
2001 {
2002 ✗ new_iter.hashmap = m;
2003 ✗ new_iter.bucket_index = bucket;
2004 ✗ new_iter.entry_index = iterator.entry_index + 1;
2005 ✗ GATE_DEBUG_ASSERT(m->buckets[new_iter.bucket_index]->entries[new_iter.entry_index] != NULL);
2006 10 return new_iter;
2007 }
2008
2/2
✓ Branch 0 taken 305 times.
✓ Branch 1 taken 3 times.
 308 for (bucket = iterator.bucket_index + 1; bucket < m->bucket_count; ++bucket)
2009 {
2010
2/2
✓ Branch 0 taken 295 times.
✓ Branch 1 taken 10 times.
 305 if (m->buckets[bucket] == NULL)
2011 {
2012 295 continue;
2013 }
2014
1/2
✓ Branch 0 taken 10 times.
✗ Branch 1 not taken.
 10 if (m->buckets[bucket]->size != 0)
2015 {
2016 10 new_iter.hashmap = m;
2017 10 new_iter.bucket_index = bucket;
2018 10 new_iter.entry_index = 0;
2019
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 10 times.
 10 GATE_DEBUG_ASSERT(m->buckets[new_iter.bucket_index]->entries[new_iter.entry_index] != NULL);
2020 10 return new_iter;
2021 }
2022 }
2023 }
2024 3 return gate_hashmap_end(m);
2025 }
2026 4 gate_hashmap_iterator_t gate_hashmap_iterator_prev(gate_hashmap_iterator_t iterator)
2027 {
2028 4 gate_hashmap_t const* m = iterator.hashmap;
2029
2030
1/2
✓ Branch 1 taken 4 times.
✗ Branch 2 not taken.
 4 if (gate_hashmap_iterator_valid(iterator))
2031 {
2032 gate_size_t bucket;
2033 gate_hashmap_iterator_t new_iter;
2034
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 4 times.
 4 if (iterator.entry_index > 0)
2035 {
2036 ✗ new_iter.hashmap = m;
2037 ✗ new_iter.bucket_index = iterator.bucket_index;
2038 ✗ new_iter.entry_index = iterator.entry_index - 1;
2039 ✗ GATE_DEBUG_ASSERT(m->buckets[new_iter.bucket_index]->entries[new_iter.entry_index] != NULL);
2040 4 return new_iter;
2041 }
2042
2043 4 bucket = iterator.bucket_index;
2044
1/2
✓ Branch 0 taken 116 times.
✗ Branch 1 not taken.
 116 while (bucket > 0)
2045 {
2046 116 --bucket;
2047
2/2
✓ Branch 0 taken 112 times.
✓ Branch 1 taken 4 times.
 116 if (m->buckets[bucket] == NULL)
2048 {
2049 112 continue;
2050 }
2051
1/2
✓ Branch 0 taken 4 times.
✗ Branch 1 not taken.
 4 if (m->buckets[bucket]->size != 0)
2052 {
2053 4 new_iter.hashmap = m;
2054 4 new_iter.bucket_index = bucket;
2055 4 new_iter.entry_index = m->buckets[bucket]->size - 1;
2056
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 4 times.
 4 GATE_DEBUG_ASSERT(m->buckets[new_iter.bucket_index]->entries[new_iter.entry_index] != NULL);
2057 4 return new_iter;
2058 }
2059 }
2060 }
2061 ✗ return gate_hashmap_end(m);
2062 }
2063 4 gate_bool_t gate_hashmap_iterator_equals(gate_hashmap_iterator_t iter1, gate_hashmap_iterator_t iter2)
2064 {
2065 4 return (iter1.hashmap == iter2.hashmap)
2066
2/2
✓ Branch 0 taken 1 times.
✓ Branch 1 taken 3 times.
 4 && (iter1.bucket_index == iter2.bucket_index)
2067
2/4
✓ Branch 0 taken 4 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 1 times.
✗ Branch 3 not taken.
 8 && (iter1.entry_index == iter2.entry_index)
2068 ;
2069 }
2070 67 gate_bool_t gate_hashmap_iterator_valid(gate_hashmap_iterator_t iterator)
2071 {
2072
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 67 times.
 67 if (!iterator.hashmap)
2073 {
2074 ✗ return false;
2075 }
2076
2/2
✓ Branch 0 taken 9 times.
✓ Branch 1 taken 58 times.
 67 if (iterator.bucket_index >= iterator.hashmap->bucket_count)
2077 {
2078 9 return false;
2079 }
2080
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 58 times.
 58 if (iterator.entry_index >= iterator.hashmap->buckets[iterator.bucket_index]->size)
2081 {
2082 ✗ return false;
2083 }
2084 58 return NULL != iterator.hashmap->buckets[iterator.bucket_index]->entries[iterator.entry_index];
2085 }
2086
2087
2088 4 static gate_bool_t gate_hashmap_enum_is_valid(gate_enumerator_t const* enumerator)
2089 {
2090 4 gate_hashmap_iterator_t* ptr_iter = (gate_hashmap_iterator_t*)&enumerator->handles[0];
2091 4 return gate_hashmap_iterator_valid(*ptr_iter);
2092 }
2093 3 static gate_bool_t gate_hashmap_enum_next(gate_enumerator_t* enumerator)
2094 {
2095 3 gate_hashmap_iterator_t* ptr_iter = (gate_hashmap_iterator_t*)&enumerator->handles[0];
2096
1/2
✓ Branch 1 taken 3 times.
✗ Branch 2 not taken.
 3 if (gate_hashmap_iterator_valid(*ptr_iter))
2097 {
2098 3 gate_hashmap_iterator_t next_iter = gate_hashmap_iterator_next(*ptr_iter);
2099 3 gate_mem_copy(&enumerator->handles[0], &next_iter, sizeof(gate_hashmap_iterator_t));
2100
2/2
✓ Branch 1 taken 2 times.
✓ Branch 2 taken 1 times.
 3 if (gate_hashmap_iterator_valid(next_iter))
2101 {
2102 2 enumerator->current_position = next_iter.hashmap->buckets[next_iter.bucket_index]->entries[next_iter.entry_index];
2103 2 return true;
2104 }
2105 else
2106 {
2107 1 enumerator->current_position = NULL;
2108 1 return false;
2109 }
2110 }
2111 else
2112 {
2113 ✗ return false;
2114 }
2115 }
2116 6 static void const* gate_hashmap_enum_get(gate_enumerator_t const* enumerator)
2117 {
2118 6 gate_mapping_t const* ptr_iter = (gate_mapping_t const*)enumerator->current_position;
2119 6 return ptr_iter;
2120 }
2121
2122 1 gate_enumerator_t* gate_hashmap_enumerate(gate_hashmap_t const* m, gate_enumerator_t* enumerator)
2123 {
2124 1 gate_enumerator_t* ret = NULL;
2125 1 gate_hashmap_iterator_t iter = gate_hashmap_first(m);
2126 1 gate_mem_clear(enumerator, sizeof(gate_enumerator_t));
2127 1 enumerator->ptr_origin = m;
2128 1 enumerator->is_valid = &gate_hashmap_enum_is_valid;
2129 1 enumerator->next = &gate_hashmap_enum_next;
2130 1 enumerator->get = &gate_hashmap_enum_get;
2131 GATE_DEBUG_ASSERT(sizeof(enumerator->handles) >= sizeof(iter));
2132 1 gate_mem_copy(&enumerator->handles[0], &iter, sizeof(gate_hashmap_iterator_t));
2133
1/2
✓ Branch 1 taken 1 times.
✗ Branch 2 not taken.
 1 if (gate_hashmap_iterator_valid(iter))
2134 {
2135 1 enumerator->current_position = m->buckets[iter.bucket_index]->entries[iter.entry_index];
2136 }
2137 1 ret = enumerator;
2138 1 return ret;
2139 }
2140 ✗ void* gate_hashmap_get_value(gate_hashmap_t const* m, void const* key)
2141 {
2142 gate_size_t bucket_index;
2143 gate_size_t entry_index;
2144 ✗ gate_bool_t found = gate_hashmap_resolve_key(m, key, &bucket_index, &entry_index);
2145 ✗ if (found)
2146 {
2147 ✗ return m->buckets[bucket_index]->entries[entry_index]->value;
2148 }
2149 else
2150 {
2151 ✗ return NULL;
2152 }
2153 }
2154 6 void const* gate_hashmap_iterator_key(gate_hashmap_iterator_t iterator)
2155 {
2156 6 return iterator.hashmap->buckets[iterator.bucket_index]->entries[iterator.entry_index]->key;
2157 }
2158 6 void* gate_hashmap_iterator_value(gate_hashmap_iterator_t iterator)
2159 {
2160 6 return iterator.hashmap->buckets[iterator.bucket_index]->entries[iterator.entry_index]->value;
2161 }
2162