GCC Code Coverage Report

Directory: ./
File: tree.c
Date: 2025-12-31 16:19:05
Exec Total Coverage
Lines: 399 399 100.0%
Functions: 39 39 100.0%
Branches: 171 186 91.9%
Line Branch Exec Source
1 /*
2 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER.
3 *
4 * Copyright 2024 Mike Becker, Olaf Wintermann 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
10 * notice, this list of conditions and the following disclaimer.
11 *
12 * 2. Redistributions in binary form must reproduce the above copyright
13 * notice, this list of conditions and the following disclaimer in the
14 * documentation and/or other materials provided with the distribution.
15 *
16 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
17 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
18 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
19 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
20 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
21 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
22 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
23 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
24 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
25 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
26 * POSSIBILITY OF SUCH DAMAGE.
27 */
28
29 #include "cx/tree.h"
30
31 #include <assert.h>
32 #include <string.h>
33
34 #define CX_TREE_PTR(cur, off) (*(void**)(((char*)(cur))+(off)))
35 #define tree_parent(node) CX_TREE_PTR(node, loc_parent)
36 #define tree_children(node) CX_TREE_PTR(node, loc_children)
37 #define tree_last_child(node) CX_TREE_PTR(node, loc_last_child)
38 #define tree_prev(node) CX_TREE_PTR(node, loc_prev)
39 #define tree_next(node) CX_TREE_PTR(node, loc_next)
40
41 #define tree_layout(tree) \
42 (tree)->loc_parent,\
43 (tree)->loc_children,\
44 (tree)->loc_last_child,\
45 (tree)->loc_prev, \
46 (tree)->loc_next
47
48 338 void cx_tree_add(
49 void *parent,
50 void *node,
51 ptrdiff_t loc_parent,
52 ptrdiff_t loc_children,
53 ptrdiff_t loc_last_child,
54 ptrdiff_t loc_prev,
55 ptrdiff_t loc_next
56 ) {
57 assert(loc_parent >= 0);
58 assert(loc_children >= 0);
59 assert(loc_next >= 0);
60
61 338 void *current_parent = tree_parent(node);
62
1/2
✗ Branch 0 (2→3) not taken.
✓ Branch 1 (2→4) taken 338 times.
 338 if (current_parent == parent) return;
63
2/2
✓ Branch 0 (4→5) taken 3 times.
✓ Branch 1 (4→6) taken 335 times.
 338 if (current_parent != NULL) {
64 3 cx_tree_remove(node, loc_parent, loc_children,
65 loc_last_child, loc_prev, loc_next);
66 }
67
68
2/2
✓ Branch 0 (6→7) taken 226 times.
✓ Branch 1 (6→9) taken 112 times.
 338 if (tree_children(parent) == NULL) {
69 226 tree_children(parent) = node;
70
2/2
✓ Branch 0 (7→8) taken 51 times.
✓ Branch 1 (7→17) taken 175 times.
 226 if (loc_last_child >= 0) {
71 51 tree_last_child(parent) = node;
72 }
73 } else {
74 void *child;
75
2/2
✓ Branch 0 (9→10) taken 38 times.
✓ Branch 1 (9→11) taken 74 times.
 112 if (loc_last_child >= 0) {
76 38 child = tree_last_child(parent);
77 38 tree_last_child(parent) = node;
78 } else {
79 74 child = tree_children(parent);
80 void *next;
81
2/2
✓ Branch 0 (13→12) taken 29 times.
✓ Branch 1 (13→14) taken 74 times.
 103 while ((next = tree_next(child)) != NULL) {
82 29 child = next;
83 }
84 }
85
2/2
✓ Branch 0 (14→15) taken 110 times.
✓ Branch 1 (14→16) taken 2 times.
 112 if (loc_prev >= 0) {
86 110 tree_prev(node) = child;
87 }
88 112 tree_next(child) = node;
89 }
90 338 tree_parent(node) = parent;
91 }
92
93 2 static void *cx_tree_node_prev(
94 ptrdiff_t loc_parent,
95 ptrdiff_t loc_children,
96 ptrdiff_t loc_next,
97 const void *node
98 ) {
99 2 void *parent = tree_parent(node);
100 2 void *begin = tree_children(parent);
101
2/2
✓ Branch 0 (2→3) taken 1 times.
✓ Branch 1 (2→4) taken 1 times.
 2 if (begin == node) return NULL;
102 1 const void *cur = begin;
103 const void *next;
104 while (1) {
105 2 next = tree_next(cur);
106
2/2
✓ Branch 0 (5→6) taken 1 times.
✓ Branch 1 (5→7) taken 1 times.
 2 if (next == node) return (void *) cur;
107 1 cur = next;
108 }
109 }
110
111 37 void cx_tree_remove(
112 void *node,
113 ptrdiff_t loc_parent,
114 ptrdiff_t loc_children,
115 ptrdiff_t loc_last_child,
116 ptrdiff_t loc_prev,
117 ptrdiff_t loc_next
118 ) {
119
2/2
✓ Branch 0 (2→3) taken 19 times.
✓ Branch 1 (2→4) taken 18 times.
 37 if (tree_parent(node) == NULL) return;
120
121 assert(loc_children >= 0);
122 assert(loc_next >= 0);
123 assert(loc_parent >= 0);
124 void *left;
125
2/2
✓ Branch 0 (4→5) taken 16 times.
✓ Branch 1 (4→6) taken 2 times.
 18 if (loc_prev >= 0) {
126 16 left = tree_prev(node);
127 } else {
128 2 left = cx_tree_node_prev(loc_parent, loc_children, loc_next, node);
129 }
130 18 void *right = tree_next(node);
131 18 void *parent = tree_parent(node);
132 assert(left == NULL || tree_children(parent) != node);
133 assert(right == NULL || loc_last_child < 0 ||
134 tree_last_child(parent) != node);
135
136
2/2
✓ Branch 0 (7→8) taken 9 times.
✓ Branch 1 (7→9) taken 9 times.
 18 if (left == NULL) {
137 9 tree_children(parent) = right;
138 } else {
139 9 tree_next(left) = right;
140 }
141
2/2
✓ Branch 0 (10→11) taken 8 times.
✓ Branch 1 (10→13) taken 10 times.
 18 if (right == NULL) {
142
2/2
✓ Branch 0 (11→12) taken 6 times.
✓ Branch 1 (11→15) taken 2 times.
 8 if (loc_last_child >= 0) {
143 6 tree_last_child(parent) = left;
144 }
145 } else {
146
2/2
✓ Branch 0 (13→14) taken 9 times.
✓ Branch 1 (13→15) taken 1 times.
 10 if (loc_prev >= 0) {
147 9 tree_prev(right) = left;
148 }
149 }
150
151 18 tree_parent(node) = NULL;
152 18 tree_next(node) = NULL;
153
2/2
✓ Branch 0 (15→16) taken 16 times.
✓ Branch 1 (15→17) taken 2 times.
 18 if (loc_prev >= 0) {
154 16 tree_prev(node) = NULL;
155 }
156 }
157
158 45 int cx_tree_search(const void *root, size_t max_depth,
159 const void *data, cx_tree_search_func sfunc, void **result,
160 ptrdiff_t loc_children, ptrdiff_t loc_next) {
161 // help avoiding bugs due to uninitialized memory
162 assert(result != NULL);
163 45 *result = NULL;
164
165 // NULL root? exit!
166
2/2
✓ Branch 0 (2→3) taken 1 times.
✓ Branch 1 (2→4) taken 44 times.
 45 if (root == NULL) {
167 1 return -1;
168 }
169
170 // remember return value for best match
171 44 int ret = sfunc(root, data);
172
2/2
✓ Branch 0 (5→6) taken 4 times.
✓ Branch 1 (5→7) taken 40 times.
 44 if (ret < 0) {
173 // not contained, exit
174 4 return -1;
175 }
176 40 *result = (void*) root;
177 // if root is already exact match, exit
178
2/2
✓ Branch 0 (7→8) taken 3 times.
✓ Branch 1 (7→9) taken 37 times.
 40 if (ret == 0) {
179 3 return 0;
180 }
181
182 // when depth is one, we are already done
183
2/2
✓ Branch 0 (9→10) taken 2 times.
✓ Branch 1 (9→11) taken 35 times.
 37 if (max_depth == 1) {
184 2 return ret;
185 }
186
187 // special case: indefinite depth
188
2/2
✓ Branch 0 (11→12) taken 22 times.
✓ Branch 1 (11→13) taken 13 times.
 35 if (max_depth == 0) {
189 22 max_depth = SIZE_MAX;
190 }
191
192 // create an iterator
193 35 CxTreeIterator iter = cx_tree_iterator(
194 (void*) root, false, loc_children, loc_next
195 );
196
197 // skip root, we already handled it
198 35 cxIteratorNext(iter);
199
200 // loop through the remaining tree
201
3/4
✓ Branch 0 (29→30) taken 137 times.
✓ Branch 1 (29→32) taken 9 times.
✓ Branch 2 (31→16) taken 137 times.
✗ Branch 3 (31→32) not taken.
 146 cx_foreach(void *, elem, iter) {
202 // investigate the current node
203 137 int ret_elem = sfunc(elem, data);
204
2/2
✓ Branch 0 (17→18) taken 26 times.
✓ Branch 1 (17→19) taken 111 times.
 137 if (ret_elem == 0) {
205 // if found, exit the search
206 26 *result = elem;
207 26 ret = 0;
208 26 break;
209
3/4
✓ Branch 0 (19→20) taken 97 times.
✓ Branch 1 (19→22) taken 14 times.
✓ Branch 2 (20→21) taken 97 times.
✗ Branch 3 (20→22) not taken.
 111 } else if (ret_elem > 0 && ret_elem < ret) {
210 // new distance is better
211 97 *result = elem;
212 97 ret = ret_elem;
213
1/4
✗ Branch 0 (22→23) not taken.
✓ Branch 1 (22→24) taken 14 times.
✗ Branch 2 (23→24) not taken.
✗ Branch 3 (23→25) not taken.
 14 } else if (ret_elem < 0 || ret_elem > ret) {
214 // not contained or distance is worse, skip entire subtree
215 14 cxTreeIteratorContinue(iter);
216 }
217
218 // when we reached the max depth, skip the subtree
219
2/2
✓ Branch 0 (25→26) taken 5 times.
✓ Branch 1 (25→27) taken 92 times.
 97 if (iter.depth == max_depth) {
220 5 cxTreeIteratorContinue(iter);
221 }
222 }
223
224 // dispose of the iterator as we might have exited the loop early
225 35 cxTreeIteratorDispose(&iter);
226
227 assert(ret < 0 || *result != NULL);
228 35 return ret;
229 }
230
231 2217 static bool cx_tree_iter_valid(const void *it) {
232 2217 const CxTreeIterator *iter = it;
233 2217 return iter->node != NULL;
234 }
235
236 908 static void *cx_tree_iter_current(const void *it) {
237 908 const CxTreeIterator *iter = it;
238 908 return iter->node;
239 }
240
241 1061 static void cx_tree_iter_next(void *it) {
242 1061 CxTreeIterator *iter = it;
243 1061 ptrdiff_t const loc_next = iter->loc_next;
244 1061 ptrdiff_t const loc_children = iter->loc_children;
245 // protect us from misuse
246
1/2
✗ Branch 0 (3→4) not taken.
✓ Branch 1 (3→5) taken 1061 times.
 1061 if (!iter->base.valid(iter)) return;
247
248 void *children;
249
250 // check if we are currently exiting or entering nodes
251
2/2
✓ Branch 0 (5→6) taken 244 times.
✓ Branch 1 (5→7) taken 817 times.
 1061 if (iter->exiting) {
252 244 children = NULL;
253 // skipping on exit is pointless, just clear the flag
254 244 iter->skip = false;
255 } else {
256
2/2
✓ Branch 0 (7→8) taken 24 times.
✓ Branch 1 (7→9) taken 793 times.
 817 if (iter->skip) {
257 // skip flag is set, pretend that there are no children
258 24 iter->skip = false;
259 24 children = NULL;
260 } else {
261 // try to enter the children (if any)
262 793 children = tree_children(iter->node);
263 }
264 }
265
266
2/2
✓ Branch 0 (10→11) taken 492 times.
✓ Branch 1 (10→30) taken 569 times.
 1061 if (children == NULL) {
267 // search for the next node
268 492 void *next = NULL;
269 985 cx_tree_iter_search_next:
270 // check if there is a sibling, but only if we are not a (subtree-)root
271
2/2
✓ Branch 0 (12→13) taken 244 times.
✓ Branch 1 (12→14) taken 741 times.
 985 if (iter->exiting) {
272 244 next = iter->node_next;
273
2/2
✓ Branch 0 (14→15) taken 660 times.
✓ Branch 1 (14→16) taken 81 times.
 741 } else if (iter->depth > 1) {
274 660 next = tree_next(iter->node);
275 660 iter->node_next = next;
276 }
277
2/2
✓ Branch 0 (16→17) taken 768 times.
✓ Branch 1 (16→25) taken 217 times.
 985 if (next == NULL) {
278 // no sibling, we are done with this node and exit
279
4/4
✓ Branch 0 (17→18) taken 388 times.
✓ Branch 1 (17→20) taken 380 times.
✓ Branch 2 (18→19) taken 194 times.
✓ Branch 3 (18→20) taken 194 times.
 768 if (iter->visit_on_exit && !iter->exiting) {
280 // iter is supposed to visit the node again
281 194 iter->exiting = true;
282 } else {
283 574 iter->exiting = false;
284
2/2
✓ Branch 0 (20→21) taken 81 times.
✓ Branch 1 (20→23) taken 493 times.
 574 if (iter->depth == 1) {
285 // there is no parent - we have iterated the entire tree
286 // invalidate the iterator and free the node stack
287 81 iter->node = iter->node_next = NULL;
288 81 iter->stack_capacity = iter->depth = 0;
289 81 cxFreeDefault(iter->stack);
290 81 iter->stack = NULL;
291 } else {
292 // the parent node can be obtained from the top of stack
293 // this way we can avoid the loc_parent in the iterator
294 493 iter->depth--;
295 493 iter->node = iter->stack[iter->depth - 1];
296 // retry with the parent node to find a sibling
297 493 goto cx_tree_iter_search_next;
298 }
299 }
300 } else {
301
4/4
✓ Branch 0 (25→26) taken 100 times.
✓ Branch 1 (25→28) taken 117 times.
✓ Branch 2 (26→27) taken 50 times.
✓ Branch 3 (26→28) taken 50 times.
 217 if (iter->visit_on_exit && !iter->exiting) {
302 // iter is supposed to visit the node again
303 50 iter->exiting = true;
304 } else {
305 167 iter->exiting = false;
306 // move to the sibling
307 167 iter->counter++;
308 167 iter->node = next;
309 // new top of stack is the sibling
310 167 iter->stack[iter->depth - 1] = next;
311 }
312 }
313 } else {
314 // node has children, push the first child onto the stack and enter it
315
2/2
✓ Branch 0 (30→31) taken 9 times.
✓ Branch 1 (30→35) taken 560 times.
 569 if (iter->depth >= iter->stack_capacity) {
316 9 const size_t newcap = iter->stack_capacity + 8;
317
1/2
✗ Branch 0 (32→33) not taken.
✓ Branch 1 (32→34) taken 9 times.
 9 if (cxReallocateArrayDefault(&iter->stack, newcap, sizeof(void*))) {
318 // we cannot return an error in this function
319 − abort(); // LCOV_EXCL_LINE
320 }
321 9 iter->stack_capacity = newcap;
322 }
323 569 iter->stack[iter->depth] = children;
324 569 iter->depth++;
325 569 iter->node = children;
326 569 iter->counter++;
327 }
328 }
329
330 131 CxTreeIterator cx_tree_iterator(
331 void *root,
332 bool visit_on_exit,
333 ptrdiff_t loc_children,
334 ptrdiff_t loc_next
335 ) {
336 CxTreeIterator ret;
337 131 ret.use_dfs = true;
338 131 ret.loc_children = loc_children;
339 131 ret.loc_next = loc_next;
340 131 ret.visit_on_exit = visit_on_exit;
341
342 // initialize members
343 131 ret.node_next = NULL;
344 131 ret.exiting = false;
345 131 ret.skip = false;
346
347 // assign base iterator functions
348 131 ret.base.allow_remove = false;
349 131 ret.base.remove = false;
350 131 ret.base.current_impl = NULL;
351 131 ret.base.valid = cx_tree_iter_valid;
352 131 ret.base.next = cx_tree_iter_next;
353 131 ret.base.current = cx_tree_iter_current;
354
355 // visit the root node
356 131 ret.node = root;
357
2/2
✓ Branch 0 (2→3) taken 127 times.
✓ Branch 1 (2→5) taken 4 times.
 131 if (root != NULL) {
358 127 ret.stack_capacity = 16;
359 127 ret.stack = cxMallocDefault(sizeof(void *) * 16);
360 127 ret.stack[0] = root;
361 127 ret.counter = 1;
362 127 ret.depth = 1;
363 } else {
364 4 ret.stack_capacity = 0;
365 4 ret.stack = NULL;
366 4 ret.counter = 0;
367 4 ret.depth = 0;
368 }
369
370 131 return ret;
371 }
372
373 328 static bool cx_tree_visitor_valid(const void *it) {
374 328 const CxTreeIterator *iter = it;
375 328 return iter->node != NULL;
376 }
377
378 161 static void *cx_tree_visitor_current(const void *it) {
379 161 const CxTreeIterator *iter = it;
380 161 return iter->node;
381 }
382
383 CX_NONNULL
384 85 static void cx_tree_visitor_enqueue_siblings(
385 CxTreeIterator *iter, void *node, ptrdiff_t loc_next) {
386 85 node = tree_next(node);
387
2/2
✓ Branch 0 (5→3) taken 64 times.
✓ Branch 1 (5→6) taken 85 times.
 149 while (node != NULL) {
388 struct cx_tree_visitor_queue_s *q;
389 64 q = cxMallocDefault(sizeof(struct cx_tree_visitor_queue_s));
390 64 q->depth = iter->queue_last->depth;
391 64 q->node = node;
392 64 iter->queue_last->next = q;
393 64 iter->queue_last = q;
394 64 node = tree_next(node);
395 }
396 85 iter->queue_last->next = NULL;
397 85 }
398
399 146 static void cx_tree_visitor_next(void *it) {
400 146 CxTreeIterator *iter = it;
401 // protect us from misuse
402
1/2
✗ Branch 0 (3→4) not taken.
✓ Branch 1 (3→5) taken 146 times.
 146 if (!iter->base.valid(iter)) return;
403
404 146 ptrdiff_t const loc_next = iter->loc_next;
405 146 ptrdiff_t const loc_children = iter->loc_children;
406
407 // add the children of the current node to the queue
408 // unless the skip flag is set
409 void *children;
410
2/2
✓ Branch 0 (5→6) taken 1 times.
✓ Branch 1 (5→7) taken 145 times.
 146 if (iter->skip) {
411 1 iter->skip = false;
412 1 children = NULL;
413 } else {
414 145 children = tree_children(iter->node);
415 }
416
2/2
✓ Branch 0 (8→9) taken 85 times.
✓ Branch 1 (8→14) taken 61 times.
 146 if (children != NULL) {
417 struct cx_tree_visitor_queue_s *q;
418 85 q = cxMallocDefault(sizeof(struct cx_tree_visitor_queue_s));
419 85 q->depth = iter->depth + 1;
420 85 q->node = children;
421
2/2
✓ Branch 0 (10→11) taken 38 times.
✓ Branch 1 (10→12) taken 47 times.
 85 if (iter->queue_last == NULL) {
422 assert(iter->queue_next == NULL);
423 38 iter->queue_next = q;
424 } else {
425 47 iter->queue_last->next = q;
426 }
427 85 iter->queue_last = q;
428 85 cx_tree_visitor_enqueue_siblings(iter, children, loc_next);
429 }
430
431 // check if there is a next node
432
2/2
✓ Branch 0 (14→15) taken 20 times.
✓ Branch 1 (14→16) taken 126 times.
 146 if (iter->queue_next == NULL) {
433 20 iter->node = NULL;
434 20 return;
435 }
436
437 // dequeue the next node
438 126 iter->node = iter->queue_next->node;
439 126 iter->depth = iter->queue_next->depth;
440 {
441 126 struct cx_tree_visitor_queue_s *q = iter->queue_next;
442 126 iter->queue_next = q->next;
443
2/2
✓ Branch 0 (16→17) taken 23 times.
✓ Branch 1 (16→18) taken 103 times.
 126 if (iter->queue_next == NULL) {
444 assert(iter->queue_last == q);
445 23 iter->queue_last = NULL;
446 }
447 126 cxFreeDefault(q);
448 }
449
450 // increment the node counter
451 126 iter->counter++;
452 }
453
454 38 CxTreeIterator cx_tree_visitor(
455 void *root,
456 ptrdiff_t loc_children,
457 ptrdiff_t loc_next
458 ) {
459 CxTreeIterator ret;
460 38 ret.visit_on_exit = false;
461 38 ret.exiting = false;
462 38 ret.use_dfs = false;
463 38 ret.loc_children = loc_children;
464 38 ret.loc_next = loc_next;
465
466 // initialize members
467 38 ret.skip = false;
468 38 ret.queue_next = NULL;
469 38 ret.queue_last = NULL;
470
471 // assign base iterator functions
472 38 ret.base.allow_remove = false;
473 38 ret.base.remove = false;
474 38 ret.base.current_impl = NULL;
475 38 ret.base.valid = cx_tree_visitor_valid;
476 38 ret.base.next = cx_tree_visitor_next;
477 38 ret.base.current = cx_tree_visitor_current;
478
479 // visit the root node
480 38 ret.node = root;
481
2/2
✓ Branch 0 (2→3) taken 37 times.
✓ Branch 1 (2→4) taken 1 times.
 38 if (root != NULL) {
482 37 ret.counter = 1;
483 37 ret.depth = 1;
484 } else {
485 1 ret.counter = 0;
486 1 ret.depth = 0;
487 }
488
489 38 return ret;
490 }
491
492 11 size_t cx_tree_size(void *root, ptrdiff_t loc_children, ptrdiff_t loc_next) {
493 11 CxTreeIterator iter = cx_tree_iterator(root, false, loc_children, loc_next);
494
2/2
✓ Branch 0 (6→4) taken 131 times.
✓ Branch 1 (6→7) taken 11 times.
 142 while (cxIteratorValid(iter)) {
495 131 cxIteratorNext(iter);
496 }
497 11 return iter.counter;
498 }
499
500 17 size_t cx_tree_depth(void *root, ptrdiff_t loc_children, ptrdiff_t loc_next) {
501 17 CxTreeIterator iter = cx_tree_iterator(root, false, loc_children, loc_next);
502 17 size_t depth = 0;
503
2/2
✓ Branch 0 (8→4) taken 32 times.
✓ Branch 1 (8→9) taken 17 times.
 49 while (cxIteratorValid(iter)) {
504
2/2
✓ Branch 0 (4→5) taken 27 times.
✓ Branch 1 (4→6) taken 5 times.
 32 if (iter.depth > depth) {
505 27 depth = iter.depth;
506 }
507 32 cxIteratorNext(iter);
508 }
509 17 return depth;
510 }
511
512 22 CxTree *cxTreeCreate(const CxAllocator *allocator,
513 size_t node_size, size_t elem_size, void *root, ptrdiff_t loc_data,
514 ptrdiff_t loc_parent, ptrdiff_t loc_children, ptrdiff_t loc_last_child,
515 ptrdiff_t loc_prev, ptrdiff_t loc_next) {
516
517
2/2
✓ Branch 0 (2→3) taken 5 times.
✓ Branch 1 (2→4) taken 17 times.
 22 if (allocator == NULL) {
518 5 allocator = cxDefaultAllocator;
519 }
520
521 22 CxTree *tree = cxZalloc(allocator, sizeof(CxTree));
522 − if (tree == NULL) return NULL; // LCOV_EXCL_LINE
523 22 tree->collection.allocator = allocator;
524
525
2/2
✓ Branch 0 (7→8) taken 16 times.
✓ Branch 1 (7→9) taken 6 times.
 22 if (elem_size == CX_STORE_POINTERS) {
526 16 tree->collection.store_pointer = true;
527 16 tree->collection.elem_size = sizeof(void*);
528 } else {
529 6 tree->collection.elem_size = elem_size;
530 }
531
532 22 tree->root = root;
533 22 tree->node_size = node_size;
534 22 tree->loc_parent = loc_parent;
535 22 tree->loc_children = loc_children;
536 22 tree->loc_last_child = loc_last_child;
537 22 tree->loc_prev = loc_prev;
538 22 tree->loc_next = loc_next;
539 22 tree->loc_data = loc_data;
540
541
2/2
✓ Branch 0 (10→11) taken 16 times.
✓ Branch 1 (10→12) taken 6 times.
 22 if (root == NULL) {
542 16 cxSetAdvancedDestructor(tree, cxFree, (void*)allocator);
543 } else {
544 6 tree->collection.size = cx_tree_size(root, loc_children, loc_next);
545 }
546
547 22 return tree;
548 }
549
550 22 void cxTreeFree(CxTree *tree) {
551
1/2
✗ Branch 0 (2→3) not taken.
✓ Branch 1 (2→4) taken 22 times.
 22 if (tree == NULL) return;
552
2/2
✓ Branch 0 (4→5) taken 17 times.
✓ Branch 1 (4→9) taken 5 times.
 22 if (tree->root != NULL) {
553 cxTreeClear(tree);
554 }
555 22 cxFree(tree->collection.allocator, tree);
556 }
557
558 4 void cxTreeSetParent(CxTree *tree, void *parent, void *child) {
559 4 size_t loc_parent = tree->loc_parent;
560
2/2
✓ Branch 0 (2→3) taken 3 times.
✓ Branch 1 (2→4) taken 1 times.
 4 if (tree_parent(child) == NULL) {
561 3 tree->collection.size++;
562 }
563 4 cx_tree_add(parent, child, tree_layout(tree));
564 4 }
565
566 4 void cxTreeAddNode(CxTree *tree, void *parent, void *child) {
567 4 cx_tree_add(parent, child, tree_layout(tree));
568 4 tree->collection.size++;
569 4 }
570
571 169 void *cxTreeCreateNode(CxTree *tree, void *parent) {
572 169 void *node = cxZalloc(tree->collection.allocator, tree->node_size);
573 − if (node == NULL) return NULL; // LCOV_EXCL_LINE
574 169 cx_tree_add(parent, node, tree_layout(tree));
575 169 tree->collection.size++;
576 169 return node;
577 }
578
579 170 void *cxTreeAddData(CxTree *tree, void *parent, const void *data) {
580
2/2
✓ Branch 0 (2→3) taken 1 times.
✓ Branch 1 (2→4) taken 169 times.
 170 if (tree->loc_data < 0) return NULL;
581
582 169 void *node = cxTreeCreateNode(tree, parent);
583 − if (node == NULL) return NULL; // LCOV_EXCL_LINE
584
585 169 char *dst = node;
586 169 dst += tree->loc_data;
587
2/2
✓ Branch 0 (7→8) taken 61 times.
✓ Branch 1 (7→9) taken 108 times.
 169 const void *src = cxCollectionStoresPointers(tree) ? (const void*)&data : data;
588 169 memcpy(dst, src, tree->collection.elem_size);
589
590 169 return node;
591 }
592
593 15 void *cxTreeCreateRoot(CxTree *tree) {
594
2/2
✓ Branch 0 (2→3) taken 1 times.
✓ Branch 1 (2→4) taken 14 times.
 15 if (tree->root != NULL) {
595 1 return tree->root;
596 }
597
598 14 void *node = cxZalloc(tree->collection.allocator, tree->node_size);
599 − if (node == NULL) return NULL; // LCOV_EXCL_LINE
600 14 tree->root = node;
601 14 tree->collection.size = 1;
602 14 return node;
603 }
604
605 13 void *cxTreeCreateRootData(CxTree *tree, const void *data) {
606
2/2
✓ Branch 0 (2→3) taken 1 times.
✓ Branch 1 (2→4) taken 12 times.
 13 if (tree->loc_data < 0) return NULL;
607
608 12 void *node = cxTreeCreateRoot(tree);
609 − if (node == NULL) return NULL; // LCOV_EXCL_LINE
610
611 12 char *dst = node;
612 12 dst += tree->loc_data;
613
2/2
✓ Branch 0 (7→8) taken 11 times.
✓ Branch 1 (7→9) taken 1 times.
 12 const void *src = cxCollectionStoresPointers(tree) ? (const void*)&data : data;
614 12 memcpy(dst, src, tree->collection.elem_size);
615
616 12 return node;
617 }
618
619 1 void *cxTreeSetRoot(CxTree *tree, void *new_root) {
620 1 void *old_root = tree->root;
621 1 tree->root = new_root;
622 1 return old_root;
623 }
624
625 66 void *cxTreeFindInSubtree(CxTree *tree, const void *data,
626 void *subtree_root, size_t max_depth, bool use_dfs) {
627
3/4
✓ Branch 0 (2→3) taken 65 times.
✓ Branch 1 (2→4) taken 1 times.
✗ Branch 2 (3→4) not taken.
✓ Branch 3 (3→5) taken 65 times.
 66 if (tree->loc_data < 0 || subtree_root == NULL) {
628 1 return NULL;
629 }
630
631 CxTreeIterator iter = use_dfs
632 35 ? cx_tree_iterator(subtree_root, false, tree->loc_children, tree->loc_next)
633
2/2
✓ Branch 0 (5→6) taken 35 times.
✓ Branch 1 (5→7) taken 30 times.
 65 : cx_tree_visitor(subtree_root, tree->loc_children, tree->loc_next);
634
635
3/4
✓ Branch 0 (23→24) taken 271 times.
✓ Branch 1 (23→26) taken 30 times.
✓ Branch 2 (25→9) taken 271 times.
✗ Branch 3 (25→26) not taken.
 301 cx_foreach(char*, node, iter) {
636 271 char *node_data = node + tree->loc_data;
637
1/2
✓ Branch 0 (9→10) taken 271 times.
✗ Branch 1 (9→11) not taken.
 271 if (cxCollectionStoresPointers(tree)) {
638 271 node_data = *(void**)node_data;
639 }
640
3/4
✗ Branch 0 (11→12) not taken.
✓ Branch 1 (11→14) taken 271 times.
✓ Branch 2 (16→17) taken 35 times.
✓ Branch 3 (16→19) taken 236 times.
 271 if (cx_invoke_compare_func(tree, node_data, data) == 0) {
641 35 cxTreeIteratorDispose(&iter);
642 35 return node;
643 }
644
2/2
✓ Branch 0 (19→20) taken 3 times.
✓ Branch 1 (19→21) taken 233 times.
 236 if (iter.depth == max_depth) {
645 3 cxTreeIteratorContinue(iter);
646 }
647 }
648 30 return NULL;
649 }
650
651 16 void *cxTreeFindFastInSubtree(CxTree *tree, const void *data,
652 cx_tree_search_func sfunc, void *root, size_t max_depth) {
653 void *result;
654 16 int ret = cx_tree_search(root, max_depth, data, sfunc, &result,
655 16 tree->loc_children, tree->loc_next);
656
2/2
✓ Branch 0 (3→4) taken 11 times.
✓ Branch 1 (3→5) taken 5 times.
 16 if (ret == 0) {
657 11 return result;
658 } else {
659 5 return NULL;
660 }
661 }
662
663 6 size_t cxTreeSubtreeSize(CxTree *tree, void *subtree_root) {
664
2/2
✓ Branch 0 (2→3) taken 1 times.
✓ Branch 1 (2→4) taken 5 times.
 6 if (subtree_root == tree->root) {
665 1 return tree->collection.size;
666 }
667 5 return cx_tree_size(subtree_root, tree->loc_children, tree->loc_next);
668 }
669
670 12 size_t cxTreeSubtreeDepth(CxTree *tree, void *subtree_root) {
671 12 return cx_tree_depth(subtree_root, tree->loc_children, tree->loc_next);
672 }
673
674 24 size_t cxTreeSize(CxTree *tree) {
675 24 return tree->collection.size;
676 }
677
678 5 size_t cxTreeDepth(CxTree *tree) {
679 5 return cx_tree_depth(tree->root, tree->loc_children, tree->loc_next);
680 }
681
682 7 int cxTreeRemoveNode(
683 CxTree *tree,
684 void *node,
685 cx_tree_relink_func relink_func
686 ) {
687
2/2
✓ Branch 0 (2→3) taken 2 times.
✓ Branch 1 (2→4) taken 5 times.
 7 if (node == tree->root) return 1;
688
689 // determine the new parent
690 5 ptrdiff_t loc_parent = tree->loc_parent;
691 5 void *new_parent = tree_parent(node);
692
693 // first, unlink from the parent
694 5 cx_tree_remove(node, tree_layout(tree));
695
696 // then relink each child
697 5 ptrdiff_t loc_children = tree->loc_children;
698 5 ptrdiff_t loc_next = tree->loc_next;
699 5 void *child = tree_children(node);
700
2/2
✓ Branch 0 (10→6) taken 9 times.
✓ Branch 1 (10→11) taken 5 times.
 14 while (child != NULL) {
701 // forcibly set the parent to NULL - we do not use the unlink function
702 // because that would unnecessarily modify the children linked list
703 9 tree_parent(child) = NULL;
704
705 // update contents, if required
706
2/2
✓ Branch 0 (6→7) taken 8 times.
✓ Branch 1 (6→8) taken 1 times.
 9 if (relink_func != NULL) {
707 8 relink_func(child, node, new_parent);
708 }
709
710 // link to new parent
711 9 cx_tree_add(new_parent, child, tree_layout(tree));
712
713 // proceed to next child
714 9 child = tree_next(child);
715 }
716
717 // clear the linked list of the removed node
718 5 tree_children(node) = NULL;
719 5 ptrdiff_t loc_last_child = tree->loc_last_child;
720
2/2
✓ Branch 0 (11→12) taken 4 times.
✓ Branch 1 (11→13) taken 1 times.
 5 if (loc_last_child >= 0) tree_last_child(node) = NULL;
721
722 // the tree now has one member less
723 5 tree->collection.size--;
724
725 5 return 0;
726 }
727
728 3 void cxTreeRemoveSubtree(CxTree *tree, void *node) {
729
2/2
✓ Branch 0 (2→3) taken 1 times.
✓ Branch 1 (2→4) taken 2 times.
 3 if (node == tree->root) {
730 1 tree->root = NULL;
731 1 tree->collection.size = 0;
732 1 return;
733 }
734 2 size_t subtree_size = cxTreeSubtreeSize(tree, node);
735 2 cx_tree_remove(node, tree_layout(tree));
736 2 tree->collection.size -= subtree_size;
737 }
738
739 4 int cxTreeDestroyNode(
740 CxTree *tree,
741 void *node,
742 cx_tree_relink_func relink_func
743 ) {
744 4 int result = cxTreeRemoveNode(tree, node, relink_func);
745
2/2
✓ Branch 0 (3→4) taken 3 times.
✓ Branch 1 (3→9) taken 1 times.
 4 if (result == 0) {
746
4/4
✓ Branch 0 (4→5) taken 1 times.
✓ Branch 1 (4→6) taken 2 times.
✓ Branch 2 (6→7) taken 2 times.
✓ Branch 3 (6→8) taken 1 times.
 3 cx_invoke_destructor_raw(tree, node);
747 3 return 0;
748 } else {
749 1 return result;
750 }
751 }
752
753 21 void cxTreeDestroySubtree(CxTree *tree, void *node) {
754 21 cx_tree_remove(node, tree_layout(tree));
755 21 CxTreeIterator iter = cx_tree_iterator(
756 node, true,
757 21 tree->loc_children, tree->loc_next
758 );
759
3/4
✓ Branch 0 (12→13) taken 388 times.
✓ Branch 1 (12→15) taken 21 times.
✓ Branch 2 (14→5) taken 388 times.
✗ Branch 3 (14→15) not taken.
 409 cx_foreach(void *, child, iter) {
760
2/2
✓ Branch 0 (5→6) taken 194 times.
✓ Branch 1 (5→10) taken 194 times.
 388 if (iter.exiting) {
761 // always call the destructors with the node!
762
4/4
✓ Branch 0 (6→7) taken 3 times.
✓ Branch 1 (6→8) taken 191 times.
✓ Branch 2 (8→9) taken 183 times.
✓ Branch 3 (8→10) taken 11 times.
 194 cx_invoke_destructor_raw(tree, child);
763 }
764 }
765 21 tree->collection.size -= iter.counter;
766
2/2
✓ Branch 0 (15→16) taken 19 times.
✓ Branch 1 (15→17) taken 2 times.
 21 if (node == tree->root) {
767 19 tree->root = NULL;
768 }
769 21 }
770
771 74 void cxTreeIteratorDispose(CxTreeIterator *iter) {
772
2/2
✓ Branch 0 (2→3) taken 56 times.
✓ Branch 1 (2→5) taken 18 times.
 74 if (iter->use_dfs) {
773 56 cxFreeDefault(iter->stack);
774 56 iter->stack = NULL;
775 } else {
776 18 struct cx_tree_visitor_queue_s *q = iter->queue_next;
777
2/2
✓ Branch 0 (8→6) taken 23 times.
✓ Branch 1 (8→9) taken 18 times.
 41 while (q != NULL) {
778 23 struct cx_tree_visitor_queue_s *next = q->next;
779 23 cxFreeDefault(q);
780 23 q = next;
781 }
782 18 iter->queue_next = iter->queue_last = NULL;
783 }
784 74 }
785
786 2 CxTreeIterator cxTreeIterateSubtree(CxTree *tree, void *node, bool visit_on_exit) {
787 4 return cx_tree_iterator(
788 node, visit_on_exit,
789 2 tree->loc_children, tree->loc_next
790 );
791 }
792
793 1 CxTreeIterator cxTreeVisitSubtree(CxTree *tree, void *node) {
794 2 return cx_tree_visitor(
795 1 node, tree->loc_children, tree->loc_next
796 );
797 }
798
799 2 CxTreeIterator cxTreeIterate(CxTree *tree, bool visit_on_exit) {
800 2 return cxTreeIterateSubtree(tree, tree->root, visit_on_exit);
801 }
802
803 1 CxTreeIterator cxTreeVisit(CxTree *tree) {
804 1 return cxTreeVisitSubtree(tree, tree->root);
805 }
806