GCC Code Coverage Report

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