GCC Code Coverage Report

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