GCC Code Coverage Report

Directory: ./
File: tree.c
Date: 2025-04-06 13:22:55
Exec Total Coverage
Lines: 450 452 99.6%
Functions: 36 36 100.0%
Branches: 178 200 89.0%
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 "cx/array_list.h"
32
33 #include <assert.h>
34
35 #define CX_TREE_PTR(cur, off) (*(void**)(((char*)(cur))+(off)))
36 #define tree_parent(node) CX_TREE_PTR(node, loc_parent)
37 #define tree_children(node) CX_TREE_PTR(node, loc_children)
38 #define tree_last_child(node) CX_TREE_PTR(node, loc_last_child)
39 #define tree_prev(node) CX_TREE_PTR(node, loc_prev)
40 #define tree_next(node) CX_TREE_PTR(node, loc_next)
41
42 #define cx_tree_ptr_locations \
43 loc_parent, loc_children, loc_last_child, loc_prev, loc_next
44
45 #define cx_tree_node_layout(tree) \
46 (tree)->loc_parent,\
47 (tree)->loc_children,\
48 (tree)->loc_last_child,\
49 (tree)->loc_prev, \
50 (tree)->loc_next
51
52 72 static void cx_tree_zero_pointers(
53 void *node,
54 ptrdiff_t loc_parent,
55 ptrdiff_t loc_children,
56 ptrdiff_t loc_last_child,
57 ptrdiff_t loc_prev,
58 ptrdiff_t loc_next
59 ) {
60 72 tree_parent(node) = NULL;
61
1/2
✓ Branch 0 taken 72 times.
✗ Branch 1 not taken.
 72 if (loc_prev >= 0) {
62 72 tree_prev(node) = NULL;
63 }
64 72 tree_next(node) = NULL;
65 72 tree_children(node) = NULL;
66
1/2
✓ Branch 0 taken 72 times.
✗ Branch 1 not taken.
 72 if (loc_last_child >= 0) {
67 72 tree_last_child(node) = NULL;
68 }
69 72 }
70
71 224 void cx_tree_link(
72 void *parent,
73 void *node,
74 ptrdiff_t loc_parent,
75 ptrdiff_t loc_children,
76 ptrdiff_t loc_last_child,
77 ptrdiff_t loc_prev,
78 ptrdiff_t loc_next
79 ) {
80 assert(loc_parent >= 0);
81 assert(loc_children >= 0);
82 assert(loc_next >= 0);
83
84 224 void *current_parent = tree_parent(node);
85
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 224 times.
 224 if (current_parent == parent) return;
86
2/2
✓ Branch 0 taken 6 times.
✓ Branch 1 taken 218 times.
 224 if (current_parent != NULL) {
87 6 cx_tree_unlink(node, cx_tree_ptr_locations);
88 }
89
90
2/2
✓ Branch 0 taken 131 times.
✓ Branch 1 taken 93 times.
 224 if (tree_children(parent) == NULL) {
91 131 tree_children(parent) = node;
92
2/2
✓ Branch 0 taken 65 times.
✓ Branch 1 taken 66 times.
 131 if (loc_last_child >= 0) {
93 65 tree_last_child(parent) = node;
94 }
95 } else {
96 void *child;
97
2/2
✓ Branch 0 taken 33 times.
✓ Branch 1 taken 60 times.
 93 if (loc_last_child >= 0) {
98 33 child = tree_last_child(parent);
99 33 tree_last_child(parent) = node;
100 } else {
101 60 child = tree_children(parent);
102 void *next;
103
2/2
✓ Branch 0 taken 24 times.
✓ Branch 1 taken 60 times.
 84 while ((next = tree_next(child)) != NULL) {
104 24 child = next;
105 }
106 }
107
2/2
✓ Branch 0 taken 91 times.
✓ Branch 1 taken 2 times.
 93 if (loc_prev >= 0) {
108 91 tree_prev(node) = child;
109 }
110 93 tree_next(child) = node;
111 }
112 224 tree_parent(node) = parent;
113 }
114
115 2 static void *cx_tree_node_prev(
116 ptrdiff_t loc_parent,
117 ptrdiff_t loc_children,
118 ptrdiff_t loc_next,
119 const void *node
120 ) {
121 2 void *parent = tree_parent(node);
122 2 void *begin = tree_children(parent);
123
2/2
✓ Branch 0 taken 1 times.
✓ Branch 1 taken 1 times.
 2 if (begin == node) return NULL;
124 1 const void *cur = begin;
125 const void *next;
126 while (1) {
127 2 next = tree_next(cur);
128
2/2
✓ Branch 0 taken 1 times.
✓ Branch 1 taken 1 times.
 2 if (next == node) return (void *) cur;
129 1 cur = next;
130 }
131 }
132
133 27 void cx_tree_unlink(
134 void *node,
135 ptrdiff_t loc_parent,
136 ptrdiff_t loc_children,
137 ptrdiff_t loc_last_child,
138 ptrdiff_t loc_prev,
139 ptrdiff_t loc_next
140 ) {
141
2/2
✓ Branch 0 taken 10 times.
✓ Branch 1 taken 17 times.
 27 if (tree_parent(node) == NULL) return;
142
143 assert(loc_children >= 0);
144 assert(loc_next >= 0);
145 assert(loc_parent >= 0);
146 void *left;
147
2/2
✓ Branch 0 taken 15 times.
✓ Branch 1 taken 2 times.
 17 if (loc_prev >= 0) {
148 15 left = tree_prev(node);
149 } else {
150 2 left = cx_tree_node_prev(loc_parent, loc_children, loc_next, node);
151 }
152 17 void *right = tree_next(node);
153 17 void *parent = tree_parent(node);
154 assert(left == NULL || tree_children(parent) != node);
155 assert(right == NULL || loc_last_child < 0 ||
156 tree_last_child(parent) != node);
157
158
2/2
✓ Branch 0 taken 11 times.
✓ Branch 1 taken 6 times.
 17 if (left == NULL) {
159 11 tree_children(parent) = right;
160 } else {
161 6 tree_next(left) = right;
162 }
163
2/2
✓ Branch 0 taken 7 times.
✓ Branch 1 taken 10 times.
 17 if (right == NULL) {
164
2/2
✓ Branch 0 taken 5 times.
✓ Branch 1 taken 2 times.
 7 if (loc_last_child >= 0) {
165 5 tree_last_child(parent) = left;
166 }
167 } else {
168
2/2
✓ Branch 0 taken 9 times.
✓ Branch 1 taken 1 times.
 10 if (loc_prev >= 0) {
169 9 tree_prev(right) = left;
170 }
171 }
172
173 17 tree_parent(node) = NULL;
174 17 tree_next(node) = NULL;
175
2/2
✓ Branch 0 taken 15 times.
✓ Branch 1 taken 2 times.
 17 if (loc_prev >= 0) {
176 15 tree_prev(node) = NULL;
177 }
178 }
179
180 148 int cx_tree_search(
181 const void *root,
182 size_t depth,
183 const void *node,
184 cx_tree_search_func sfunc,
185 void **result,
186 ptrdiff_t loc_children,
187 ptrdiff_t loc_next
188 ) {
189 // help avoiding bugs due to uninitialized memory
190 assert(result != NULL);
191 148 *result = NULL;
192
193 // remember return value for best match
194 148 int ret = sfunc(root, node);
195
2/2
✓ Branch 0 taken 34 times.
✓ Branch 1 taken 114 times.
 148 if (ret < 0) {
196 // not contained, exit
197 34 return -1;
198 }
199 114 *result = (void*) root;
200 // if root is already exact match, exit
201
2/2
✓ Branch 0 taken 3 times.
✓ Branch 1 taken 111 times.
 114 if (ret == 0) {
202 3 return 0;
203 }
204
205 // when depth is one, we are already done
206
2/2
✓ Branch 0 taken 2 times.
✓ Branch 1 taken 109 times.
 111 if (depth == 1) {
207 2 return ret;
208 }
209
210 // special case: indefinite depth
211
2/2
✓ Branch 0 taken 100 times.
✓ Branch 1 taken 9 times.
 109 if (depth == 0) {
212 100 depth = SIZE_MAX;
213 }
214
215 // create an iterator
216 109 CxTreeIterator iter = cx_tree_iterator(
217 (void*) root, false, loc_children, loc_next
218 );
219
220 // skip root, we already handled it
221 109 cxIteratorNext(iter);
222
223 // loop through the remaining tree
224
3/4
✓ Branch 2 taken 282 times.
✓ Branch 3 taken 75 times.
✓ Branch 5 taken 282 times.
✗ Branch 6 not taken.
 357 cx_foreach(void *, elem, iter) {
225 // investigate the current node
226 282 int ret_elem = sfunc(elem, node);
227
2/2
✓ Branch 0 taken 34 times.
✓ Branch 1 taken 248 times.
 282 if (ret_elem == 0) {
228 // if found, exit the search
229 34 *result = (void *) elem;
230 34 ret = 0;
231 34 break;
232
3/4
✓ Branch 0 taken 141 times.
✓ Branch 1 taken 107 times.
✓ Branch 2 taken 141 times.
✗ Branch 3 not taken.
 248 } else if (ret_elem > 0 && ret_elem < ret) {
233 // new distance is better
234 141 *result = elem;
235 141 ret = ret_elem;
236 } else {
237 // not contained or distance is worse, skip entire subtree
238 107 cxTreeIteratorContinue(iter);
239 }
240
241 // when we reached the max depth, skip the subtree
242
2/2
✓ Branch 0 taken 3 times.
✓ Branch 1 taken 138 times.
 141 if (iter.depth == depth) {
243 3 cxTreeIteratorContinue(iter);
244 }
245 }
246
247 // dispose the iterator as we might have exited the loop early
248 109 cxTreeIteratorDispose(&iter);
249
250 assert(ret < 0 || *result != NULL);
251 109 return ret;
252 }
253
254 58 int cx_tree_search_data(
255 const void *root,
256 size_t depth,
257 const void *data,
258 cx_tree_search_data_func sfunc,
259 void **result,
260 ptrdiff_t loc_children,
261 ptrdiff_t loc_next
262 ) {
263 // it is basically the same implementation
264 58 return cx_tree_search(
265 root, depth, data,
266 (cx_tree_search_func) sfunc,
267 result,
268 loc_children, loc_next);
269 }
270
271 1235 static bool cx_tree_iter_valid(const void *it) {
272 1235 const struct cx_tree_iterator_s *iter = it;
273 1235 return iter->node != NULL;
274 }
275
276 532 static void *cx_tree_iter_current(const void *it) {
277 532 const struct cx_tree_iterator_s *iter = it;
278 532 return iter->node;
279 }
280
281 607 static void cx_tree_iter_next(void *it) {
282 607 struct cx_tree_iterator_s *iter = it;
283 607 ptrdiff_t const loc_next = iter->loc_next;
284 607 ptrdiff_t const loc_children = iter->loc_children;
285 // protect us from misuse
286
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 607 times.
 607 if (!iter->base.valid(iter)) return;
287
288 void *children;
289
290 // check if we are currently exiting or entering nodes
291
2/2
✓ Branch 0 taken 116 times.
✓ Branch 1 taken 491 times.
 607 if (iter->exiting) {
292 116 children = NULL;
293 // skipping on exit is pointless, just clear the flag
294 116 iter->skip = false;
295 } else {
296
2/2
✓ Branch 0 taken 112 times.
✓ Branch 1 taken 379 times.
 491 if (iter->skip) {
297 // skip flag is set, pretend that there are no children
298 112 iter->skip = false;
299 112 children = NULL;
300 } else {
301 // try to enter the children (if any)
302 379 children = tree_children(iter->node);
303 }
304 }
305
306
2/2
✓ Branch 0 taken 374 times.
✓ Branch 1 taken 233 times.
 607 if (children == NULL) {
307 // search for the next node
308 void *next;
309 374 cx_tree_iter_search_next:
310 // check if there is a sibling
311
2/2
✓ Branch 0 taken 116 times.
✓ Branch 1 taken 437 times.
 553 if (iter->exiting) {
312 116 next = iter->node_next;
313 } else {
314 437 next = tree_next(iter->node);
315 437 iter->node_next = next;
316 }
317
2/2
✓ Branch 0 taken 353 times.
✓ Branch 1 taken 200 times.
 553 if (next == NULL) {
318 // no sibling, we are done with this node and exit
319
4/4
✓ Branch 0 taken 158 times.
✓ Branch 1 taken 195 times.
✓ Branch 2 taken 79 times.
✓ Branch 3 taken 79 times.
 353 if (iter->visit_on_exit && !iter->exiting) {
320 // iter is supposed to visit the node again
321 79 iter->exiting = true;
322 } else {
323 274 iter->exiting = false;
324
2/2
✓ Branch 0 taken 95 times.
✓ Branch 1 taken 179 times.
 274 if (iter->depth == 1) {
325 // there is no parent - we have iterated the entire tree
326 // invalidate the iterator and free the node stack
327 95 iter->node = iter->node_next = NULL;
328 95 iter->stack_capacity = iter->depth = 0;
329 95 free(iter->stack);
330 95 iter->stack = NULL;
331 } else {
332 // the parent node can be obtained from the top of stack
333 // this way we can avoid the loc_parent in the iterator
334 179 iter->depth--;
335 179 iter->node = iter->stack[iter->depth - 1];
336 // retry with the parent node to find a sibling
337 179 goto cx_tree_iter_search_next;
338 }
339 }
340 } else {
341
4/4
✓ Branch 0 taken 74 times.
✓ Branch 1 taken 126 times.
✓ Branch 2 taken 37 times.
✓ Branch 3 taken 37 times.
 200 if (iter->visit_on_exit && !iter->exiting) {
342 // iter is supposed to visit the node again
343 37 iter->exiting = true;
344 } else {
345 163 iter->exiting = false;
346 // move to the sibling
347 163 iter->counter++;
348 163 iter->node = next;
349 // new top of stack is the sibling
350 163 iter->stack[iter->depth - 1] = next;
351 }
352 }
353 } else {
354 // node has children, push the first child onto the stack and enter it
355 233 cx_array_simple_add(iter->stack, children);
356 233 iter->node = children;
357 233 iter->counter++;
358 }
359 }
360
361 131 CxTreeIterator cx_tree_iterator(
362 void *root,
363 bool visit_on_exit,
364 ptrdiff_t loc_children,
365 ptrdiff_t loc_next
366 ) {
367 CxTreeIterator iter;
368 131 iter.loc_children = loc_children;
369 131 iter.loc_next = loc_next;
370 131 iter.visit_on_exit = visit_on_exit;
371
372 // initialize members
373 131 iter.node_next = NULL;
374 131 iter.exiting = false;
375 131 iter.skip = false;
376
377 // assign base iterator functions
378 131 iter.base.mutating = false;
379 131 iter.base.remove = false;
380 131 iter.base.current_impl = NULL;
381 131 iter.base.valid = cx_tree_iter_valid;
382 131 iter.base.next = cx_tree_iter_next;
383 131 iter.base.current = cx_tree_iter_current;
384
385 // visit the root node
386 131 iter.node = root;
387
2/2
✓ Branch 0 taken 130 times.
✓ Branch 1 taken 1 times.
 131 if (root != NULL) {
388 130 iter.stack_capacity = 16;
389 130 iter.stack = malloc(sizeof(void *) * 16);
390 130 iter.stack[0] = root;
391 130 iter.counter = 1;
392 130 iter.depth = 1;
393 } else {
394 1 iter.stack_capacity = 0;
395 1 iter.stack = NULL;
396 1 iter.counter = 0;
397 1 iter.depth = 0;
398 }
399
400 131 return iter;
401 }
402
403 184 static bool cx_tree_visitor_valid(const void *it) {
404 184 const struct cx_tree_visitor_s *iter = it;
405 184 return iter->node != NULL;
406 }
407
408 23 static void *cx_tree_visitor_current(const void *it) {
409 23 const struct cx_tree_visitor_s *iter = it;
410 23 return iter->node;
411 }
412
413 cx_attr_nonnull
414 36 static void cx_tree_visitor_enqueue_siblings(
415 struct cx_tree_visitor_s *iter, void *node, ptrdiff_t loc_next) {
416 36 node = tree_next(node);
417
2/2
✓ Branch 0 taken 17 times.
✓ Branch 1 taken 36 times.
 53 while (node != NULL) {
418 struct cx_tree_visitor_queue_s *q;
419 17 q = malloc(sizeof(struct cx_tree_visitor_queue_s));
420 17 q->depth = iter->queue_last->depth;
421 17 q->node = node;
422 17 iter->queue_last->next = q;
423 17 iter->queue_last = q;
424 17 node = tree_next(node);
425 }
426 36 iter->queue_last->next = NULL;
427 36 }
428
429 78 static void cx_tree_visitor_next(void *it) {
430 78 struct cx_tree_visitor_s *iter = it;
431 // protect us from misuse
432
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 78 times.
 78 if (!iter->base.valid(iter)) return;
433
434 78 ptrdiff_t const loc_next = iter->loc_next;
435 78 ptrdiff_t const loc_children = iter->loc_children;
436
437 // add the children of the current node to the queue
438 // unless the skip flag is set
439 void *children;
440
2/2
✓ Branch 0 taken 1 times.
✓ Branch 1 taken 77 times.
 78 if (iter->skip) {
441 1 iter->skip = false;
442 1 children = NULL;
443 } else {
444 77 children = tree_children(iter->node);
445 }
446
2/2
✓ Branch 0 taken 36 times.
✓ Branch 1 taken 42 times.
 78 if (children != NULL) {
447 struct cx_tree_visitor_queue_s *q;
448 36 q = malloc(sizeof(struct cx_tree_visitor_queue_s));
449 36 q->depth = iter->depth + 1;
450 36 q->node = children;
451
2/2
✓ Branch 0 taken 21 times.
✓ Branch 1 taken 15 times.
 36 if (iter->queue_last == NULL) {
452 assert(iter->queue_next == NULL);
453 21 iter->queue_next = q;
454 } else {
455 15 iter->queue_last->next = q;
456 }
457 36 iter->queue_last = q;
458 36 cx_tree_visitor_enqueue_siblings(iter, children, loc_next);
459 }
460
461 // check if there is a next node
462
2/2
✓ Branch 0 taken 25 times.
✓ Branch 1 taken 53 times.
 78 if (iter->queue_next == NULL) {
463 25 iter->node = NULL;
464 25 return;
465 }
466
467 // dequeue the next node
468 53 iter->node = iter->queue_next->node;
469 53 iter->depth = iter->queue_next->depth;
470 {
471 53 struct cx_tree_visitor_queue_s *q = iter->queue_next;
472 53 iter->queue_next = q->next;
473
2/2
✓ Branch 0 taken 21 times.
✓ Branch 1 taken 32 times.
 53 if (iter->queue_next == NULL) {
474 assert(iter->queue_last == q);
475 21 iter->queue_last = NULL;
476 }
477 53 free(q);
478 }
479
480 // increment the node counter
481 53 iter->counter++;
482 }
483
484 28 CxTreeVisitor cx_tree_visitor(
485 void *root,
486 ptrdiff_t loc_children,
487 ptrdiff_t loc_next
488 ) {
489 CxTreeVisitor iter;
490 28 iter.loc_children = loc_children;
491 28 iter.loc_next = loc_next;
492
493 // initialize members
494 28 iter.skip = false;
495 28 iter.queue_next = NULL;
496 28 iter.queue_last = NULL;
497
498 // assign base iterator functions
499 28 iter.base.mutating = false;
500 28 iter.base.remove = false;
501 28 iter.base.current_impl = NULL;
502 28 iter.base.valid = cx_tree_visitor_valid;
503 28 iter.base.next = cx_tree_visitor_next;
504 28 iter.base.current = cx_tree_visitor_current;
505
506 // visit the root node
507 28 iter.node = root;
508
2/2
✓ Branch 0 taken 25 times.
✓ Branch 1 taken 3 times.
 28 if (root != NULL) {
509 25 iter.counter = 1;
510 25 iter.depth = 1;
511 } else {
512 3 iter.counter = 0;
513 3 iter.depth = 0;
514 }
515
516 28 return iter;
517 }
518
519 3 static void cx_tree_add_link_duplicate(
520 void *original, void *duplicate,
521 ptrdiff_t loc_parent, ptrdiff_t loc_children, ptrdiff_t loc_last_child,
522 ptrdiff_t loc_prev, ptrdiff_t loc_next
523 ) {
524 3 void *shared_parent = tree_parent(original);
525
2/2
✓ Branch 0 taken 1 times.
✓ Branch 1 taken 2 times.
 3 if (shared_parent == NULL) {
526 1 cx_tree_link(original, duplicate, cx_tree_ptr_locations);
527 } else {
528 2 cx_tree_link(shared_parent, duplicate, cx_tree_ptr_locations);
529 }
530 3 }
531
532 56 static void cx_tree_add_link_new(
533 void *parent, void *node, cx_tree_search_func sfunc,
534 ptrdiff_t loc_parent, ptrdiff_t loc_children, ptrdiff_t loc_last_child,
535 ptrdiff_t loc_prev, ptrdiff_t loc_next
536 ) {
537 // check the current children one by one,
538 // if they could be children of the new node
539 56 void *child = tree_children(parent);
540
2/2
✓ Branch 0 taken 19 times.
✓ Branch 1 taken 56 times.
 75 while (child != NULL) {
541 19 void *next = tree_next(child);
542
543
2/2
✓ Branch 1 taken 3 times.
✓ Branch 2 taken 16 times.
 19 if (sfunc(node, child) > 0) {
544 // the sibling could be a child -> re-link
545 3 cx_tree_link(node, child, cx_tree_ptr_locations);
546 }
547
548 19 child = next;
549 }
550
551 // add new node as new child
552 56 cx_tree_link(parent, node, cx_tree_ptr_locations);
553 56 }
554
555 13 int cx_tree_add(
556 const void *src,
557 cx_tree_search_func sfunc,
558 cx_tree_node_create_func cfunc,
559 void *cdata,
560 void **cnode,
561 void *root,
562 ptrdiff_t loc_parent,
563 ptrdiff_t loc_children,
564 ptrdiff_t loc_last_child,
565 ptrdiff_t loc_prev,
566 ptrdiff_t loc_next
567 ) {
568 13 *cnode = cfunc(src, cdata);
569
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 13 times.
 13 if (*cnode == NULL) return 1;
570 13 cx_tree_zero_pointers(*cnode, cx_tree_ptr_locations);
571
572 13 void *match = NULL;
573 13 int result = cx_tree_search(
574 root,
575 0,
576 *cnode,
577 sfunc,
578 &match,
579 loc_children,
580 loc_next
581 );
582
583
2/2
✓ Branch 0 taken 4 times.
✓ Branch 1 taken 9 times.
 13 if (result < 0) {
584 // node does not fit into the tree - return non-zero value
585 4 return 1;
586
2/2
✓ Branch 0 taken 2 times.
✓ Branch 1 taken 7 times.
 9 } else if (result == 0) {
587 // data already found in the tree, link duplicate
588 2 cx_tree_add_link_duplicate(match, *cnode, cx_tree_ptr_locations);
589 } else {
590 // closest match found, add new node
591 7 cx_tree_add_link_new(match, *cnode, sfunc, cx_tree_ptr_locations);
592 }
593
594 9 return 0;
595 }
596
597 unsigned int cx_tree_add_look_around_depth = 3;
598
599 10 size_t cx_tree_add_iter(
600 struct cx_iterator_base_s *iter,
601 size_t num,
602 cx_tree_search_func sfunc,
603 cx_tree_node_create_func cfunc,
604 void *cdata,
605 void **failed,
606 void *root,
607 ptrdiff_t loc_parent,
608 ptrdiff_t loc_children,
609 ptrdiff_t loc_last_child,
610 ptrdiff_t loc_prev,
611 ptrdiff_t loc_next
612 ) {
613 // erase the failed pointer
614 10 *failed = NULL;
615
616 // iter not valid? cancel...
617
2/2
✓ Branch 1 taken 1 times.
✓ Branch 2 taken 9 times.
 10 if (!iter->valid(iter)) return 0;
618
619 9 size_t processed = 0;
620 9 void *current_node = root;
621 const void *elem;
622
623
2/2
✓ Branch 0 taken 52 times.
✓ Branch 1 taken 3 times.
 64 for (void **eptr; processed < num &&
624
3/4
✓ Branch 0 taken 55 times.
✓ Branch 1 taken 4 times.
✓ Branch 4 taken 52 times.
✗ Branch 5 not taken.
 111 iter->valid(iter) && (eptr = iter->current(iter)) != NULL;
625 50 iter->next(iter)) {
626 52 elem = *eptr;
627
628 // create the new node
629 52 void *new_node = cfunc(elem, cdata);
630
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 52 times.
 54 if (new_node == NULL) return processed;
631 52 cx_tree_zero_pointers(new_node, cx_tree_ptr_locations);
632
633 // start searching from current node
634 void *match;
635 int result;
636 52 unsigned int look_around_retries = cx_tree_add_look_around_depth;
637 77 cx_tree_add_look_around_retry:
638 77 result = cx_tree_search(
639 current_node,
640 0,
641 new_node,
642 sfunc,
643 &match,
644 loc_children,
645 loc_next
646 );
647
648
2/2
✓ Branch 0 taken 27 times.
✓ Branch 1 taken 50 times.
 77 if (result < 0) {
649 // traverse upwards and try to find better parents
650 27 void *parent = tree_parent(current_node);
651
2/2
✓ Branch 0 taken 25 times.
✓ Branch 1 taken 2 times.
 27 if (parent != NULL) {
652
2/2
✓ Branch 0 taken 23 times.
✓ Branch 1 taken 2 times.
 25 if (look_around_retries > 0) {
653 23 look_around_retries--;
654 23 current_node = parent;
655 } else {
656 // look around retries exhausted, start from the root
657 2 current_node = root;
658 }
659 25 goto cx_tree_add_look_around_retry;
660 } else {
661 // no parents. so we failed
662 2 *failed = new_node;
663 2 return processed;
664 }
665
2/2
✓ Branch 0 taken 1 times.
✓ Branch 1 taken 49 times.
 50 } else if (result == 0) {
666 // data already found in the tree, link duplicate
667 1 cx_tree_add_link_duplicate(match, new_node, cx_tree_ptr_locations);
668 // but stick with the original match, in case we needed a new root
669 1 current_node = match;
670 } else {
671 // closest match found, add new node as child
672 49 cx_tree_add_link_new(match, new_node, sfunc,
673 cx_tree_ptr_locations);
674 49 current_node = match;
675 }
676
677 50 processed++;
678 }
679 7 return processed;
680 }
681
682 7 size_t cx_tree_add_array(
683 const void *src,
684 size_t num,
685 size_t elem_size,
686 cx_tree_search_func sfunc,
687 cx_tree_node_create_func cfunc,
688 void *cdata,
689 void **failed,
690 void *root,
691 ptrdiff_t loc_parent,
692 ptrdiff_t loc_children,
693 ptrdiff_t loc_last_child,
694 ptrdiff_t loc_prev,
695 ptrdiff_t loc_next
696 ) {
697 // erase failed pointer
698 7 *failed = NULL;
699
700 // super special case: zero elements
701
2/2
✓ Branch 0 taken 1 times.
✓ Branch 1 taken 6 times.
 7 if (num == 0) {
702 1 return 0;
703 }
704
705 // special case: one element does not need an iterator
706
2/2
✓ Branch 0 taken 2 times.
✓ Branch 1 taken 4 times.
 6 if (num == 1) {
707 void *node;
708
2/2
✓ Branch 1 taken 1 times.
✓ Branch 2 taken 1 times.
 2 if (0 == cx_tree_add(
709 src, sfunc, cfunc, cdata, &node, root,
710 loc_parent, loc_children, loc_last_child,
711 loc_prev, loc_next)) {
712 1 return 1;
713 } else {
714 1 *failed = node;
715 1 return 0;
716 }
717 }
718
719 // otherwise, create iterator and hand over to other function
720 4 CxIterator iter = cxIterator(src, elem_size, num);
721 4 return cx_tree_add_iter(cxIteratorRef(iter), num, sfunc,
722 cfunc, cdata, failed, root,
723 loc_parent, loc_children, loc_last_child,
724 loc_prev, loc_next);
725 }
726
727 7 static int cx_tree_default_insert_element(
728 CxTree *tree,
729 const void *data
730 ) {
731 void *node;
732
2/2
✓ Branch 0 taken 1 times.
✓ Branch 1 taken 6 times.
 7 if (tree->root == NULL) {
733 1 node = tree->node_create(data, tree);
734
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 1 times.
 1 if (node == NULL) return 1;
735 1 cx_tree_zero_pointers(node, cx_tree_node_layout(tree));
736 1 tree->root = node;
737 1 tree->size = 1;
738 1 return 0;
739 }
740 6 int result = cx_tree_add(data, tree->search, tree->node_create,
741 tree, &node, tree->root, cx_tree_node_layout(tree));
742
2/2
✓ Branch 0 taken 5 times.
✓ Branch 1 taken 1 times.
 6 if (0 == result) {
743 5 tree->size++;
744 } else {
745 1 cxFree(tree->allocator, node);
746 }
747 6 return result;
748 }
749
750 4 static size_t cx_tree_default_insert_many(
751 CxTree *tree,
752 CxIteratorBase *iter,
753 size_t n
754 ) {
755 4 size_t ins = 0;
756
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 4 times.
 4 if (!iter->valid(iter)) return 0;
757
1/2
✓ Branch 0 taken 4 times.
✗ Branch 1 not taken.
 4 if (tree->root == NULL) {
758 // use the first element from the iter to create the root node
759 4 void **eptr = iter->current(iter);
760 4 void *node = tree->node_create(*eptr, tree);
761
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 4 times.
 4 if (node == NULL) return 0;
762 4 cx_tree_zero_pointers(node, cx_tree_node_layout(tree));
763 4 tree->root = node;
764 4 ins = 1;
765 4 iter->next(iter);
766 }
767 void *failed;
768 4 ins += cx_tree_add_iter(iter, n, tree->search, tree->node_create,
769 tree, &failed, tree->root, cx_tree_node_layout(tree));
770 4 tree->size += ins;
771
2/2
✓ Branch 0 taken 1 times.
✓ Branch 1 taken 3 times.
 4 if (ins < n) {
772 1 cxFree(tree->allocator, failed);
773 }
774 4 return ins;
775 }
776
777 30 static void *cx_tree_default_find(
778 CxTree *tree,
779 const void *subtree,
780 const void *data,
781 size_t depth
782 ) {
783
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 30 times.
 30 if (tree->root == NULL) return NULL;
784
785 void *found;
786
2/2
✓ Branch 1 taken 16 times.
✓ Branch 2 taken 14 times.
 30 if (0 == cx_tree_search_data(
787 subtree,
788 depth,
789 data,
790 tree->search_data,
791 &found,
792 tree->loc_children,
793 tree->loc_next
794 )) {
795 16 return found;
796 } else {
797 14 return NULL;
798 }
799 }
800
801 static cx_tree_class cx_tree_default_class = {
802 cx_tree_default_insert_element,
803 cx_tree_default_insert_many,
804 cx_tree_default_find
805 };
806
807 9 CxTree *cxTreeCreate(
808 const CxAllocator *allocator,
809 cx_tree_node_create_func create_func,
810 cx_tree_search_func search_func,
811 cx_tree_search_data_func search_data_func,
812 ptrdiff_t loc_parent,
813 ptrdiff_t loc_children,
814 ptrdiff_t loc_last_child,
815 ptrdiff_t loc_prev,
816 ptrdiff_t loc_next
817 ) {
818
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 9 times.
 9 if (allocator == NULL) {
819 ✗ allocator = cxDefaultAllocator;
820 }
821 assert(create_func != NULL);
822 assert(search_func != NULL);
823 assert(search_data_func != NULL);
824
825 9 CxTree *tree = cxMalloc(allocator, sizeof(CxTree));
826
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 9 times.
 9 if (tree == NULL) return NULL;
827
828 9 tree->cl = &cx_tree_default_class;
829 9 tree->allocator = allocator;
830 9 tree->node_create = create_func;
831 9 tree->search = search_func;
832 9 tree->search_data = search_data_func;
833 9 tree->simple_destructor = NULL;
834 9 tree->advanced_destructor = (cx_destructor_func2) cxFree;
835 9 tree->destructor_data = (void *) allocator;
836 9 tree->loc_parent = loc_parent;
837 9 tree->loc_children = loc_children;
838 9 tree->loc_last_child = loc_last_child;
839 9 tree->loc_prev = loc_prev;
840 9 tree->loc_next = loc_next;
841 9 tree->root = NULL;
842 9 tree->size = 0;
843
844 9 return tree;
845 }
846
847 15 void cxTreeFree(CxTree *tree) {
848
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 15 times.
 15 if (tree == NULL) return;
849
2/2
✓ Branch 0 taken 9 times.
✓ Branch 1 taken 6 times.
 15 if (tree->root != NULL) {
850 9 cxTreeClear(tree);
851 }
852 15 cxFree(tree->allocator, tree);
853 }
854
855 6 CxTree *cxTreeCreateWrapped(
856 const CxAllocator *allocator,
857 void *root,
858 ptrdiff_t loc_parent,
859 ptrdiff_t loc_children,
860 ptrdiff_t loc_last_child,
861 ptrdiff_t loc_prev,
862 ptrdiff_t loc_next
863 ) {
864
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 6 times.
 6 if (allocator == NULL) {
865 ✗ allocator = cxDefaultAllocator;
866 }
867 assert(root != NULL);
868
869 6 CxTree *tree = cxMalloc(allocator, sizeof(CxTree));
870
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 6 times.
 6 if (tree == NULL) return NULL;
871
872 6 tree->cl = &cx_tree_default_class;
873 // set the allocator anyway, just in case...
874 6 tree->allocator = allocator;
875 6 tree->node_create = NULL;
876 6 tree->search = NULL;
877 6 tree->search_data = NULL;
878 6 tree->simple_destructor = NULL;
879 6 tree->advanced_destructor = NULL;
880 6 tree->destructor_data = NULL;
881 6 tree->loc_parent = loc_parent;
882 6 tree->loc_children = loc_children;
883 6 tree->loc_last_child = loc_last_child;
884 6 tree->loc_prev = loc_prev;
885 6 tree->loc_next = loc_next;
886 6 tree->root = root;
887 6 tree->size = cxTreeSubtreeSize(tree, root);
888 6 return tree;
889 }
890
891 4 void cxTreeSetParent(
892 CxTree *tree,
893 void *parent,
894 void *child
895 ) {
896 4 size_t loc_parent = tree->loc_parent;
897
2/2
✓ Branch 0 taken 3 times.
✓ Branch 1 taken 1 times.
 4 if (tree_parent(child) == NULL) {
898 3 tree->size++;
899 }
900 4 cx_tree_link(parent, child, cx_tree_node_layout(tree));
901 4 }
902
903 2 void cxTreeAddChildNode(
904 CxTree *tree,
905 void *parent,
906 void *child
907 ) {
908 2 cx_tree_link(parent, child, cx_tree_node_layout(tree));
909 2 tree->size++;
910 2 }
911
912 2 int cxTreeAddChild(
913 CxTree *tree,
914 void *parent,
915 const void *data) {
916 2 void *node = tree->node_create(data, tree);
917
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 2 times.
 2 if (node == NULL) return 1;
918 2 cx_tree_zero_pointers(node, cx_tree_node_layout(tree));
919 2 cx_tree_link(parent, node, cx_tree_node_layout(tree));
920 2 tree->size++;
921 2 return 0;
922 }
923
924 7 size_t cxTreeSubtreeSize(CxTree *tree, void *subtree_root) {
925 7 CxTreeVisitor visitor = cx_tree_visitor(
926 subtree_root,
927 tree->loc_children,
928 tree->loc_next
929 );
930
2/2
✓ Branch 1 taken 23 times.
✓ Branch 2 taken 7 times.
 30 while (cxIteratorValid(visitor)) {
931 23 cxIteratorNext(visitor);
932 }
933 7 return visitor.counter;
934 }
935
936 12 size_t cxTreeSubtreeDepth(CxTree *tree, void *subtree_root) {
937 12 CxTreeVisitor visitor = cx_tree_visitor(
938 subtree_root,
939 tree->loc_children,
940 tree->loc_next
941 );
942
2/2
✓ Branch 1 taken 24 times.
✓ Branch 2 taken 12 times.
 36 while (cxIteratorValid(visitor)) {
943 24 cxIteratorNext(visitor);
944 }
945 12 return visitor.depth;
946 }
947
948 5 size_t cxTreeDepth(CxTree *tree) {
949 5 CxTreeVisitor visitor = cx_tree_visitor(
950 tree->root, tree->loc_children, tree->loc_next
951 );
952
2/2
✓ Branch 1 taken 8 times.
✓ Branch 2 taken 5 times.
 13 while (cxIteratorValid(visitor)) {
953 8 cxIteratorNext(visitor);
954 }
955 5 return visitor.depth;
956 }
957
958 5 int cxTreeRemoveNode(
959 CxTree *tree,
960 void *node,
961 cx_tree_relink_func relink_func
962 ) {
963
2/2
✓ Branch 0 taken 2 times.
✓ Branch 1 taken 3 times.
 5 if (node == tree->root) return 1;
964
965 // determine the new parent
966 3 ptrdiff_t loc_parent = tree->loc_parent;
967 3 void *new_parent = tree_parent(node);
968
969 // first, unlink from the parent
970 3 cx_tree_unlink(node, cx_tree_node_layout(tree));
971
972 // then relink each child
973 3 ptrdiff_t loc_children = tree->loc_children;
974 3 ptrdiff_t loc_next = tree->loc_next;
975 3 void *child = tree_children(node);
976
2/2
✓ Branch 0 taken 5 times.
✓ Branch 1 taken 3 times.
 8 while (child != NULL) {
977 // forcibly set the parent to NULL - we do not use the unlink function
978 // because that would unnecessarily modify the children linked list
979 5 tree_parent(child) = NULL;
980
981 // update contents, if required
982
2/2
✓ Branch 0 taken 4 times.
✓ Branch 1 taken 1 times.
 5 if (relink_func != NULL) {
983 4 relink_func(child, node, new_parent);
984 }
985
986 // link to new parent
987 5 cx_tree_link(new_parent, child, cx_tree_node_layout(tree));
988
989 // proceed to next child
990 5 child = tree_next(child);
991 }
992
993 // clear the linked list of the removed node
994 3 tree_children(node) = NULL;
995 3 ptrdiff_t loc_last_child = tree->loc_last_child;
996
2/2
✓ Branch 0 taken 2 times.
✓ Branch 1 taken 1 times.
 3 if (loc_last_child >= 0) tree_last_child(node) = NULL;
997
998 // the tree now has one member less
999 3 tree->size--;
1000
1001 3 return 0;
1002 }
1003
1004 2 void cxTreeRemoveSubtree(CxTree *tree, void *node) {
1005
2/2
✓ Branch 0 taken 1 times.
✓ Branch 1 taken 1 times.
 2 if (node == tree->root) {
1006 1 tree->root = NULL;
1007 1 tree->size = 0;
1008 1 return;
1009 }
1010 1 size_t subtree_size = cxTreeSubtreeSize(tree, node);
1011 1 cx_tree_unlink(node, cx_tree_node_layout(tree));
1012 1 tree->size -= subtree_size;
1013 }
1014
1015 3 int cxTreeDestroyNode(
1016 CxTree *tree,
1017 void *node,
1018 cx_tree_relink_func relink_func
1019 ) {
1020 3 int result = cxTreeRemoveNode(tree, node, relink_func);
1021
2/2
✓ Branch 0 taken 2 times.
✓ Branch 1 taken 1 times.
 3 if (result == 0) {
1022
2/2
✓ Branch 0 taken 1 times.
✓ Branch 1 taken 1 times.
 2 if (tree->simple_destructor) {
1023 1 tree->simple_destructor(node);
1024 }
1025
2/2
✓ Branch 0 taken 1 times.
✓ Branch 1 taken 1 times.
 2 if (tree->advanced_destructor) {
1026 1 tree->advanced_destructor(tree->destructor_data, node);
1027 }
1028 2 return 0;
1029 } else {
1030 1 return result;
1031 }
1032 }
1033
1034 11 void cxTreeDestroySubtree(CxTree *tree, void *node) {
1035 11 cx_tree_unlink(node, cx_tree_node_layout(tree));
1036 11 CxTreeIterator iter = cx_tree_iterator(
1037 node, true,
1038 tree->loc_children, tree->loc_next
1039 );
1040
3/4
✓ Branch 2 taken 94 times.
✓ Branch 3 taken 11 times.
✓ Branch 5 taken 94 times.
✗ Branch 6 not taken.
 105 cx_foreach(void *, child, iter) {
1041
2/2
✓ Branch 0 taken 47 times.
✓ Branch 1 taken 47 times.
 94 if (iter.exiting) {
1042
2/2
✓ Branch 0 taken 3 times.
✓ Branch 1 taken 44 times.
 47 if (tree->simple_destructor) {
1043 3 tree->simple_destructor(child);
1044 }
1045
2/2
✓ Branch 0 taken 32 times.
✓ Branch 1 taken 15 times.
 47 if (tree->advanced_destructor) {
1046 32 tree->advanced_destructor(tree->destructor_data, child);
1047 }
1048 }
1049 }
1050 11 tree->size -= iter.counter;
1051
2/2
✓ Branch 0 taken 10 times.
✓ Branch 1 taken 1 times.
 11 if (node == tree->root) {
1052 10 tree->root = NULL;
1053 }
1054 11 }
1055