src/tree.c

Sat, 05 Oct 2024 14:16:01 +0200

author
Mike Becker <universe@uap-core.de>
date
Sat, 05 Oct 2024 14:16:01 +0200
changeset 906
b51e5268bd9b
parent 905
39aa4f106a71
child 907
1f72fb9af87e
permissions
-rw-r--r--

add test for simple destructor in trees - fixes #436

816
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
1 /*
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
2 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER.
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
3 *
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
4 * Copyright 2024 Mike Becker, Olaf Wintermann All rights reserved.
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
5 *
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
6 * Redistribution and use in source and binary forms, with or without
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
7 * modification, are permitted provided that the following conditions are met:
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
8 *
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
9 * 1. Redistributions of source code must retain the above copyright
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
10 * notice, this list of conditions and the following disclaimer.
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
11 *
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
12 * 2. Redistributions in binary form must reproduce the above copyright
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
13 * notice, this list of conditions and the following disclaimer in the
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
14 * documentation and/or other materials provided with the distribution.
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
15 *
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
16 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
17 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
18 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
19 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
20 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
21 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
22 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
23 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
24 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
25 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
26 * POSSIBILITY OF SUCH DAMAGE.
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
27 */
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
28
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
29 #include "cx/tree.h"
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
30
826
21840975d541 add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents: 816
diff changeset
31 #include "cx/array_list.h"
21840975d541 add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents: 816
diff changeset
32
816
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
33 #include <assert.h>
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
34
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
35 #define CX_TREE_PTR(cur, off) (*(void**)(((char*)(cur))+(off)))
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
36 #define tree_parent(node) CX_TREE_PTR(node, loc_parent)
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
37 #define tree_children(node) CX_TREE_PTR(node, loc_children)
862
387414a7afd8 change cx_tree_link() from prepending to appending children - fixes #391
Mike Becker <universe@uap-core.de>
parents: 854
diff changeset
38 #define tree_last_child(node) CX_TREE_PTR(node, loc_last_child)
816
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
39 #define tree_prev(node) CX_TREE_PTR(node, loc_prev)
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
40 #define tree_next(node) CX_TREE_PTR(node, loc_next)
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
41
866
1f636de4a63f complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents: 864
diff changeset
42 #define cx_tree_ptr_locations \
1f636de4a63f complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents: 864
diff changeset
43 loc_parent, loc_children, loc_last_child, loc_prev, loc_next
1f636de4a63f complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents: 864
diff changeset
44
1f636de4a63f complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents: 864
diff changeset
45 static void cx_tree_zero_pointers(
1f636de4a63f complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents: 864
diff changeset
46 void *node,
1f636de4a63f complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents: 864
diff changeset
47 ptrdiff_t loc_parent,
1f636de4a63f complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents: 864
diff changeset
48 ptrdiff_t loc_children,
1f636de4a63f complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents: 864
diff changeset
49 ptrdiff_t loc_last_child,
1f636de4a63f complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents: 864
diff changeset
50 ptrdiff_t loc_prev,
1f636de4a63f complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents: 864
diff changeset
51 ptrdiff_t loc_next
1f636de4a63f complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents: 864
diff changeset
52 ) {
1f636de4a63f complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents: 864
diff changeset
53 tree_parent(node) = NULL;
1f636de4a63f complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents: 864
diff changeset
54 tree_prev(node) = NULL;
1f636de4a63f complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents: 864
diff changeset
55 tree_next(node) = NULL;
1f636de4a63f complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents: 864
diff changeset
56 tree_children(node) = NULL;
1f636de4a63f complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents: 864
diff changeset
57 if (loc_last_child >= 0) {
1f636de4a63f complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents: 864
diff changeset
58 tree_last_child(node) = NULL;
1f636de4a63f complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents: 864
diff changeset
59 }
1f636de4a63f complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents: 864
diff changeset
60 }
1f636de4a63f complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents: 864
diff changeset
61
816
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
62 void cx_tree_link(
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
63 void *restrict parent,
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
64 void *restrict node,
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
65 ptrdiff_t loc_parent,
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
66 ptrdiff_t loc_children,
862
387414a7afd8 change cx_tree_link() from prepending to appending children - fixes #391
Mike Becker <universe@uap-core.de>
parents: 854
diff changeset
67 ptrdiff_t loc_last_child,
816
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
68 ptrdiff_t loc_prev,
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
69 ptrdiff_t loc_next
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
70 ) {
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
71 void *current_parent = tree_parent(node);
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
72 if (current_parent == parent) return;
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
73 if (current_parent != NULL) {
866
1f636de4a63f complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents: 864
diff changeset
74 cx_tree_unlink(node, cx_tree_ptr_locations);
816
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
75 }
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
76
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
77 if (tree_children(parent) == NULL) {
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
78 tree_children(parent) = node;
862
387414a7afd8 change cx_tree_link() from prepending to appending children - fixes #391
Mike Becker <universe@uap-core.de>
parents: 854
diff changeset
79 if (loc_last_child >= 0) {
387414a7afd8 change cx_tree_link() from prepending to appending children - fixes #391
Mike Becker <universe@uap-core.de>
parents: 854
diff changeset
80 tree_last_child(parent) = node;
387414a7afd8 change cx_tree_link() from prepending to appending children - fixes #391
Mike Becker <universe@uap-core.de>
parents: 854
diff changeset
81 }
816
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
82 } else {
862
387414a7afd8 change cx_tree_link() from prepending to appending children - fixes #391
Mike Becker <universe@uap-core.de>
parents: 854
diff changeset
83 if (loc_last_child >= 0) {
387414a7afd8 change cx_tree_link() from prepending to appending children - fixes #391
Mike Becker <universe@uap-core.de>
parents: 854
diff changeset
84 void *child = tree_last_child(parent);
387414a7afd8 change cx_tree_link() from prepending to appending children - fixes #391
Mike Becker <universe@uap-core.de>
parents: 854
diff changeset
85 tree_prev(node) = child;
387414a7afd8 change cx_tree_link() from prepending to appending children - fixes #391
Mike Becker <universe@uap-core.de>
parents: 854
diff changeset
86 tree_next(child) = node;
387414a7afd8 change cx_tree_link() from prepending to appending children - fixes #391
Mike Becker <universe@uap-core.de>
parents: 854
diff changeset
87 tree_last_child(parent) = node;
387414a7afd8 change cx_tree_link() from prepending to appending children - fixes #391
Mike Becker <universe@uap-core.de>
parents: 854
diff changeset
88 } else {
387414a7afd8 change cx_tree_link() from prepending to appending children - fixes #391
Mike Becker <universe@uap-core.de>
parents: 854
diff changeset
89 void *child = tree_children(parent);
387414a7afd8 change cx_tree_link() from prepending to appending children - fixes #391
Mike Becker <universe@uap-core.de>
parents: 854
diff changeset
90 void *next;
387414a7afd8 change cx_tree_link() from prepending to appending children - fixes #391
Mike Becker <universe@uap-core.de>
parents: 854
diff changeset
91 while ((next = tree_next(child)) != NULL) {
387414a7afd8 change cx_tree_link() from prepending to appending children - fixes #391
Mike Becker <universe@uap-core.de>
parents: 854
diff changeset
92 child = next;
387414a7afd8 change cx_tree_link() from prepending to appending children - fixes #391
Mike Becker <universe@uap-core.de>
parents: 854
diff changeset
93 }
387414a7afd8 change cx_tree_link() from prepending to appending children - fixes #391
Mike Becker <universe@uap-core.de>
parents: 854
diff changeset
94 tree_prev(node) = child;
387414a7afd8 change cx_tree_link() from prepending to appending children - fixes #391
Mike Becker <universe@uap-core.de>
parents: 854
diff changeset
95 tree_next(child) = node;
387414a7afd8 change cx_tree_link() from prepending to appending children - fixes #391
Mike Becker <universe@uap-core.de>
parents: 854
diff changeset
96 }
816
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
97 }
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
98 tree_parent(node) = parent;
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
99 }
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
100
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
101 void cx_tree_unlink(
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
102 void *node,
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
103 ptrdiff_t loc_parent,
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
104 ptrdiff_t loc_children,
862
387414a7afd8 change cx_tree_link() from prepending to appending children - fixes #391
Mike Becker <universe@uap-core.de>
parents: 854
diff changeset
105 ptrdiff_t loc_last_child,
816
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
106 ptrdiff_t loc_prev,
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
107 ptrdiff_t loc_next
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
108 ) {
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
109 if (tree_parent(node) == NULL) return;
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
110
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
111 void *left = tree_prev(node);
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
112 void *right = tree_next(node);
862
387414a7afd8 change cx_tree_link() from prepending to appending children - fixes #391
Mike Becker <universe@uap-core.de>
parents: 854
diff changeset
113 void *parent = tree_parent(node);
387414a7afd8 change cx_tree_link() from prepending to appending children - fixes #391
Mike Becker <universe@uap-core.de>
parents: 854
diff changeset
114 assert(left == NULL || tree_children(parent) != node);
387414a7afd8 change cx_tree_link() from prepending to appending children - fixes #391
Mike Becker <universe@uap-core.de>
parents: 854
diff changeset
115 assert(right == NULL || loc_last_child < 0 ||
387414a7afd8 change cx_tree_link() from prepending to appending children - fixes #391
Mike Becker <universe@uap-core.de>
parents: 854
diff changeset
116 tree_last_child(parent) != node);
387414a7afd8 change cx_tree_link() from prepending to appending children - fixes #391
Mike Becker <universe@uap-core.de>
parents: 854
diff changeset
117
816
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
118 if (left == NULL) {
862
387414a7afd8 change cx_tree_link() from prepending to appending children - fixes #391
Mike Becker <universe@uap-core.de>
parents: 854
diff changeset
119 tree_children(parent) = right;
816
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
120 } else {
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
121 tree_next(left) = right;
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
122 }
862
387414a7afd8 change cx_tree_link() from prepending to appending children - fixes #391
Mike Becker <universe@uap-core.de>
parents: 854
diff changeset
123 if (right == NULL) {
387414a7afd8 change cx_tree_link() from prepending to appending children - fixes #391
Mike Becker <universe@uap-core.de>
parents: 854
diff changeset
124 if (loc_last_child >= 0) {
387414a7afd8 change cx_tree_link() from prepending to appending children - fixes #391
Mike Becker <universe@uap-core.de>
parents: 854
diff changeset
125 tree_last_child(parent) = left;
387414a7afd8 change cx_tree_link() from prepending to appending children - fixes #391
Mike Becker <universe@uap-core.de>
parents: 854
diff changeset
126 }
387414a7afd8 change cx_tree_link() from prepending to appending children - fixes #391
Mike Becker <universe@uap-core.de>
parents: 854
diff changeset
127 } else {
387414a7afd8 change cx_tree_link() from prepending to appending children - fixes #391
Mike Becker <universe@uap-core.de>
parents: 854
diff changeset
128 tree_prev(right) = left;
387414a7afd8 change cx_tree_link() from prepending to appending children - fixes #391
Mike Becker <universe@uap-core.de>
parents: 854
diff changeset
129 }
387414a7afd8 change cx_tree_link() from prepending to appending children - fixes #391
Mike Becker <universe@uap-core.de>
parents: 854
diff changeset
130
816
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
131 tree_parent(node) = NULL;
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
132 tree_prev(node) = NULL;
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
133 tree_next(node) = NULL;
425234b05dff add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
134 }
826
21840975d541 add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents: 816
diff changeset
135
21840975d541 add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents: 816
diff changeset
136 int cx_tree_search(
890
54565fd74e74 move all const keywords to the west - fixes #426
Mike Becker <universe@uap-core.de>
parents: 871
diff changeset
137 const void *root,
54565fd74e74 move all const keywords to the west - fixes #426
Mike Becker <universe@uap-core.de>
parents: 871
diff changeset
138 const void *node,
826
21840975d541 add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents: 816
diff changeset
139 cx_tree_search_func sfunc,
21840975d541 add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents: 816
diff changeset
140 void **result,
21840975d541 add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents: 816
diff changeset
141 ptrdiff_t loc_children,
21840975d541 add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents: 816
diff changeset
142 ptrdiff_t loc_next
21840975d541 add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents: 816
diff changeset
143 ) {
21840975d541 add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents: 816
diff changeset
144 int ret;
21840975d541 add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents: 816
diff changeset
145 *result = NULL;
21840975d541 add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents: 816
diff changeset
146
21840975d541 add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents: 816
diff changeset
147 // shortcut: compare root before doing anything else
871
e29c1f96646d rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents: 870
diff changeset
148 ret = sfunc(root, node);
826
21840975d541 add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents: 816
diff changeset
149 if (ret < 0) {
21840975d541 add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents: 816
diff changeset
150 return ret;
21840975d541 add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents: 816
diff changeset
151 } else if (ret == 0 || tree_children(root) == NULL) {
21840975d541 add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents: 816
diff changeset
152 *result = (void*)root;
21840975d541 add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents: 816
diff changeset
153 return ret;
21840975d541 add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents: 816
diff changeset
154 }
21840975d541 add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents: 816
diff changeset
155
21840975d541 add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents: 816
diff changeset
156 // create a working stack
890
54565fd74e74 move all const keywords to the west - fixes #426
Mike Becker <universe@uap-core.de>
parents: 871
diff changeset
157 CX_ARRAY_DECLARE(const void *, work);
833
5c926801f052 vastly simplify tree iterators and add test for creating them
Mike Becker <universe@uap-core.de>
parents: 830
diff changeset
158 cx_array_initialize(work, 32);
826
21840975d541 add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents: 816
diff changeset
159
21840975d541 add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents: 816
diff changeset
160 // add the children of root to the working stack
21840975d541 add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents: 816
diff changeset
161 {
21840975d541 add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents: 816
diff changeset
162 void *c = tree_children(root);
21840975d541 add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents: 816
diff changeset
163 while (c != NULL) {
833
5c926801f052 vastly simplify tree iterators and add test for creating them
Mike Becker <universe@uap-core.de>
parents: 830
diff changeset
164 cx_array_simple_add(work, c);
826
21840975d541 add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents: 816
diff changeset
165 c = tree_next(c);
21840975d541 add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents: 816
diff changeset
166 }
21840975d541 add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents: 816
diff changeset
167 }
21840975d541 add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents: 816
diff changeset
168
21840975d541 add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents: 816
diff changeset
169 // remember a candidate for adding the data
21840975d541 add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents: 816
diff changeset
170 // also remember the exact return code from sfunc
869
9e7f0db6a725 fix cx_tree_search() not remembering root as a valid candidate
Mike Becker <universe@uap-core.de>
parents: 868
diff changeset
171 void *candidate = (void *) root;
9e7f0db6a725 fix cx_tree_search() not remembering root as a valid candidate
Mike Becker <universe@uap-core.de>
parents: 868
diff changeset
172 int ret_candidate = ret;
826
21840975d541 add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents: 816
diff changeset
173
21840975d541 add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents: 816
diff changeset
174 // process the working stack
21840975d541 add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents: 816
diff changeset
175 while (work_size > 0) {
21840975d541 add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents: 816
diff changeset
176 // pop element
890
54565fd74e74 move all const keywords to the west - fixes #426
Mike Becker <universe@uap-core.de>
parents: 871
diff changeset
177 const void *elem = work[--work_size];
826
21840975d541 add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents: 816
diff changeset
178
21840975d541 add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents: 816
diff changeset
179 // apply the search function
871
e29c1f96646d rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents: 870
diff changeset
180 ret = sfunc(elem, node);
826
21840975d541 add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents: 816
diff changeset
181
21840975d541 add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents: 816
diff changeset
182 if (ret == 0) {
21840975d541 add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents: 816
diff changeset
183 // if found, exit the search
871
e29c1f96646d rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents: 870
diff changeset
184 *result = (void *) elem;
826
21840975d541 add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents: 816
diff changeset
185 work_size = 0;
21840975d541 add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents: 816
diff changeset
186 break;
21840975d541 add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents: 816
diff changeset
187 } else if (ret > 0) {
21840975d541 add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents: 816
diff changeset
188 // if children might contain the data, add them to the stack
871
e29c1f96646d rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents: 870
diff changeset
189 void *c = tree_children(elem);
826
21840975d541 add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents: 816
diff changeset
190 while (c != NULL) {
833
5c926801f052 vastly simplify tree iterators and add test for creating them
Mike Becker <universe@uap-core.de>
parents: 830
diff changeset
191 cx_array_simple_add(work, c);
826
21840975d541 add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents: 816
diff changeset
192 c = tree_next(c);
21840975d541 add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents: 816
diff changeset
193 }
21840975d541 add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents: 816
diff changeset
194
21840975d541 add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents: 816
diff changeset
195 // remember this node in case no child is suitable
870
af0092d8789a remove condition that is always false after recent fix
Mike Becker <universe@uap-core.de>
parents: 869
diff changeset
196 if (ret < ret_candidate) {
871
e29c1f96646d rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents: 870
diff changeset
197 candidate = (void *) elem;
826
21840975d541 add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents: 816
diff changeset
198 ret_candidate = ret;
21840975d541 add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents: 816
diff changeset
199 }
21840975d541 add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents: 816
diff changeset
200 }
21840975d541 add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents: 816
diff changeset
201 }
21840975d541 add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents: 816
diff changeset
202
21840975d541 add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents: 816
diff changeset
203 // not found, but was there a candidate?
21840975d541 add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents: 816
diff changeset
204 if (ret != 0 && candidate != NULL) {
21840975d541 add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents: 816
diff changeset
205 ret = ret_candidate;
21840975d541 add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents: 816
diff changeset
206 *result = candidate;
21840975d541 add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents: 816
diff changeset
207 }
21840975d541 add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents: 816
diff changeset
208
21840975d541 add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents: 816
diff changeset
209 // free the working queue and return
21840975d541 add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents: 816
diff changeset
210 free(work);
21840975d541 add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents: 816
diff changeset
211 return ret;
21840975d541 add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents: 816
diff changeset
212 }
830
c4dae6fe6d5b commit complicated stuff before simplifying it
Mike Becker <universe@uap-core.de>
parents: 826
diff changeset
213
871
e29c1f96646d rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents: 870
diff changeset
214 int cx_tree_search_data(
890
54565fd74e74 move all const keywords to the west - fixes #426
Mike Becker <universe@uap-core.de>
parents: 871
diff changeset
215 const void *root,
54565fd74e74 move all const keywords to the west - fixes #426
Mike Becker <universe@uap-core.de>
parents: 871
diff changeset
216 const void *data,
871
e29c1f96646d rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents: 870
diff changeset
217 cx_tree_search_data_func sfunc,
e29c1f96646d rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents: 870
diff changeset
218 void **result,
e29c1f96646d rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents: 870
diff changeset
219 ptrdiff_t loc_children,
e29c1f96646d rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents: 870
diff changeset
220 ptrdiff_t loc_next
e29c1f96646d rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents: 870
diff changeset
221 ) {
e29c1f96646d rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents: 870
diff changeset
222 // it is basically the same implementation
e29c1f96646d rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents: 870
diff changeset
223 return cx_tree_search(
e29c1f96646d rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents: 870
diff changeset
224 root, data,
e29c1f96646d rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents: 870
diff changeset
225 (cx_tree_search_func) sfunc,
e29c1f96646d rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents: 870
diff changeset
226 result,
e29c1f96646d rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents: 870
diff changeset
227 loc_children, loc_next);
e29c1f96646d rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents: 870
diff changeset
228 }
e29c1f96646d rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents: 870
diff changeset
229
890
54565fd74e74 move all const keywords to the west - fixes #426
Mike Becker <universe@uap-core.de>
parents: 871
diff changeset
230 static bool cx_tree_iter_valid(const void *it) {
54565fd74e74 move all const keywords to the west - fixes #426
Mike Becker <universe@uap-core.de>
parents: 871
diff changeset
231 const struct cx_tree_iterator_s *iter = it;
830
c4dae6fe6d5b commit complicated stuff before simplifying it
Mike Becker <universe@uap-core.de>
parents: 826
diff changeset
232 return iter->node != NULL;
c4dae6fe6d5b commit complicated stuff before simplifying it
Mike Becker <universe@uap-core.de>
parents: 826
diff changeset
233 }
c4dae6fe6d5b commit complicated stuff before simplifying it
Mike Becker <universe@uap-core.de>
parents: 826
diff changeset
234
890
54565fd74e74 move all const keywords to the west - fixes #426
Mike Becker <universe@uap-core.de>
parents: 871
diff changeset
235 static void *cx_tree_iter_current(const void *it) {
54565fd74e74 move all const keywords to the west - fixes #426
Mike Becker <universe@uap-core.de>
parents: 871
diff changeset
236 const struct cx_tree_iterator_s *iter = it;
830
c4dae6fe6d5b commit complicated stuff before simplifying it
Mike Becker <universe@uap-core.de>
parents: 826
diff changeset
237 return iter->node;
c4dae6fe6d5b commit complicated stuff before simplifying it
Mike Becker <universe@uap-core.de>
parents: 826
diff changeset
238 }
c4dae6fe6d5b commit complicated stuff before simplifying it
Mike Becker <universe@uap-core.de>
parents: 826
diff changeset
239
c4dae6fe6d5b commit complicated stuff before simplifying it
Mike Becker <universe@uap-core.de>
parents: 826
diff changeset
240 static void cx_tree_iter_next(void *it) {
c4dae6fe6d5b commit complicated stuff before simplifying it
Mike Becker <universe@uap-core.de>
parents: 826
diff changeset
241 struct cx_tree_iterator_s *iter = it;
845
2615317311b7 add cx_tree_visitor()
Mike Becker <universe@uap-core.de>
parents: 840
diff changeset
242 ptrdiff_t const loc_next = iter->loc_next;
2615317311b7 add cx_tree_visitor()
Mike Becker <universe@uap-core.de>
parents: 840
diff changeset
243 ptrdiff_t const loc_children = iter->loc_children;
905
39aa4f106a71 complete implementation of remaining high level tree functions
Mike Becker <universe@uap-core.de>
parents: 904
diff changeset
244 // protect us from misuse
39aa4f106a71 complete implementation of remaining high level tree functions
Mike Becker <universe@uap-core.de>
parents: 904
diff changeset
245 if (!iter->base.valid(iter)) return;
838
1ce90ab4fab9 add visit_on_exit to iterator implementation
Mike Becker <universe@uap-core.de>
parents: 836
diff changeset
246
1ce90ab4fab9 add visit_on_exit to iterator implementation
Mike Becker <universe@uap-core.de>
parents: 836
diff changeset
247 void *children;
830
c4dae6fe6d5b commit complicated stuff before simplifying it
Mike Becker <universe@uap-core.de>
parents: 826
diff changeset
248
838
1ce90ab4fab9 add visit_on_exit to iterator implementation
Mike Becker <universe@uap-core.de>
parents: 836
diff changeset
249 // check if we are currently exiting or entering nodes
1ce90ab4fab9 add visit_on_exit to iterator implementation
Mike Becker <universe@uap-core.de>
parents: 836
diff changeset
250 if (iter->exiting) {
1ce90ab4fab9 add visit_on_exit to iterator implementation
Mike Becker <universe@uap-core.de>
parents: 836
diff changeset
251 children = NULL;
848
6456036bbb37 implement tree continue - fixes #376
Mike Becker <universe@uap-core.de>
parents: 845
diff changeset
252 // skipping on exit is pointless, just clear the flag
6456036bbb37 implement tree continue - fixes #376
Mike Becker <universe@uap-core.de>
parents: 845
diff changeset
253 iter->skip = false;
838
1ce90ab4fab9 add visit_on_exit to iterator implementation
Mike Becker <universe@uap-core.de>
parents: 836
diff changeset
254 } else {
848
6456036bbb37 implement tree continue - fixes #376
Mike Becker <universe@uap-core.de>
parents: 845
diff changeset
255 if (iter->skip) {
6456036bbb37 implement tree continue - fixes #376
Mike Becker <universe@uap-core.de>
parents: 845
diff changeset
256 // skip flag is set, pretend that there are no children
6456036bbb37 implement tree continue - fixes #376
Mike Becker <universe@uap-core.de>
parents: 845
diff changeset
257 iter->skip = false;
6456036bbb37 implement tree continue - fixes #376
Mike Becker <universe@uap-core.de>
parents: 845
diff changeset
258 children = NULL;
6456036bbb37 implement tree continue - fixes #376
Mike Becker <universe@uap-core.de>
parents: 845
diff changeset
259 } else {
6456036bbb37 implement tree continue - fixes #376
Mike Becker <universe@uap-core.de>
parents: 845
diff changeset
260 // try to enter the children (if any)
6456036bbb37 implement tree continue - fixes #376
Mike Becker <universe@uap-core.de>
parents: 845
diff changeset
261 children = tree_children(iter->node);
6456036bbb37 implement tree continue - fixes #376
Mike Becker <universe@uap-core.de>
parents: 845
diff changeset
262 }
838
1ce90ab4fab9 add visit_on_exit to iterator implementation
Mike Becker <universe@uap-core.de>
parents: 836
diff changeset
263 }
1ce90ab4fab9 add visit_on_exit to iterator implementation
Mike Becker <universe@uap-core.de>
parents: 836
diff changeset
264
836
2672a2f79484 implement basic (enter only) tree iterator
Mike Becker <universe@uap-core.de>
parents: 834
diff changeset
265 if (children == NULL) {
2672a2f79484 implement basic (enter only) tree iterator
Mike Becker <universe@uap-core.de>
parents: 834
diff changeset
266 // search for the next node
838
1ce90ab4fab9 add visit_on_exit to iterator implementation
Mike Becker <universe@uap-core.de>
parents: 836
diff changeset
267 void *next;
1ce90ab4fab9 add visit_on_exit to iterator implementation
Mike Becker <universe@uap-core.de>
parents: 836
diff changeset
268 cx_tree_iter_search_next:
1ce90ab4fab9 add visit_on_exit to iterator implementation
Mike Becker <universe@uap-core.de>
parents: 836
diff changeset
269 // check if there is a sibling
840
4f02995ce44e allow freeing tree nodes on exit - fixes #377
Mike Becker <universe@uap-core.de>
parents: 838
diff changeset
270 if (iter->exiting) {
853
d4baf4dd55c3 simplify iterator structures
Mike Becker <universe@uap-core.de>
parents: 848
diff changeset
271 next = iter->node_next;
840
4f02995ce44e allow freeing tree nodes on exit - fixes #377
Mike Becker <universe@uap-core.de>
parents: 838
diff changeset
272 } else {
4f02995ce44e allow freeing tree nodes on exit - fixes #377
Mike Becker <universe@uap-core.de>
parents: 838
diff changeset
273 next = tree_next(iter->node);
853
d4baf4dd55c3 simplify iterator structures
Mike Becker <universe@uap-core.de>
parents: 848
diff changeset
274 iter->node_next = next;
840
4f02995ce44e allow freeing tree nodes on exit - fixes #377
Mike Becker <universe@uap-core.de>
parents: 838
diff changeset
275 }
838
1ce90ab4fab9 add visit_on_exit to iterator implementation
Mike Becker <universe@uap-core.de>
parents: 836
diff changeset
276 if (next == NULL) {
1ce90ab4fab9 add visit_on_exit to iterator implementation
Mike Becker <universe@uap-core.de>
parents: 836
diff changeset
277 // no sibling, we are done with this node and exit
1ce90ab4fab9 add visit_on_exit to iterator implementation
Mike Becker <universe@uap-core.de>
parents: 836
diff changeset
278 if (iter->visit_on_exit && !iter->exiting) {
1ce90ab4fab9 add visit_on_exit to iterator implementation
Mike Becker <universe@uap-core.de>
parents: 836
diff changeset
279 // iter is supposed to visit the node again
1ce90ab4fab9 add visit_on_exit to iterator implementation
Mike Becker <universe@uap-core.de>
parents: 836
diff changeset
280 iter->exiting = true;
1ce90ab4fab9 add visit_on_exit to iterator implementation
Mike Becker <universe@uap-core.de>
parents: 836
diff changeset
281 } else {
1ce90ab4fab9 add visit_on_exit to iterator implementation
Mike Becker <universe@uap-core.de>
parents: 836
diff changeset
282 iter->exiting = false;
1ce90ab4fab9 add visit_on_exit to iterator implementation
Mike Becker <universe@uap-core.de>
parents: 836
diff changeset
283 if (iter->depth == 1) {
836
2672a2f79484 implement basic (enter only) tree iterator
Mike Becker <universe@uap-core.de>
parents: 834
diff changeset
284 // there is no parent - we have iterated the entire tree
2672a2f79484 implement basic (enter only) tree iterator
Mike Becker <universe@uap-core.de>
parents: 834
diff changeset
285 // invalidate the iterator and free the node stack
853
d4baf4dd55c3 simplify iterator structures
Mike Becker <universe@uap-core.de>
parents: 848
diff changeset
286 iter->node = iter->node_next = NULL;
838
1ce90ab4fab9 add visit_on_exit to iterator implementation
Mike Becker <universe@uap-core.de>
parents: 836
diff changeset
287 iter->stack_capacity = iter->depth = 0;
836
2672a2f79484 implement basic (enter only) tree iterator
Mike Becker <universe@uap-core.de>
parents: 834
diff changeset
288 free(iter->stack);
2672a2f79484 implement basic (enter only) tree iterator
Mike Becker <universe@uap-core.de>
parents: 834
diff changeset
289 iter->stack = NULL;
2672a2f79484 implement basic (enter only) tree iterator
Mike Becker <universe@uap-core.de>
parents: 834
diff changeset
290 } else {
2672a2f79484 implement basic (enter only) tree iterator
Mike Becker <universe@uap-core.de>
parents: 834
diff changeset
291 // the parent node can be obtained from the top of stack
2672a2f79484 implement basic (enter only) tree iterator
Mike Becker <universe@uap-core.de>
parents: 834
diff changeset
292 // this way we can avoid the loc_parent in the iterator
838
1ce90ab4fab9 add visit_on_exit to iterator implementation
Mike Becker <universe@uap-core.de>
parents: 836
diff changeset
293 iter->depth--;
1ce90ab4fab9 add visit_on_exit to iterator implementation
Mike Becker <universe@uap-core.de>
parents: 836
diff changeset
294 iter->node = iter->stack[iter->depth - 1];
1ce90ab4fab9 add visit_on_exit to iterator implementation
Mike Becker <universe@uap-core.de>
parents: 836
diff changeset
295 // retry with the parent node to find a sibling
1ce90ab4fab9 add visit_on_exit to iterator implementation
Mike Becker <universe@uap-core.de>
parents: 836
diff changeset
296 goto cx_tree_iter_search_next;
836
2672a2f79484 implement basic (enter only) tree iterator
Mike Becker <universe@uap-core.de>
parents: 834
diff changeset
297 }
838
1ce90ab4fab9 add visit_on_exit to iterator implementation
Mike Becker <universe@uap-core.de>
parents: 836
diff changeset
298 }
1ce90ab4fab9 add visit_on_exit to iterator implementation
Mike Becker <universe@uap-core.de>
parents: 836
diff changeset
299 } else {
1ce90ab4fab9 add visit_on_exit to iterator implementation
Mike Becker <universe@uap-core.de>
parents: 836
diff changeset
300 if (iter->visit_on_exit && !iter->exiting) {
1ce90ab4fab9 add visit_on_exit to iterator implementation
Mike Becker <universe@uap-core.de>
parents: 836
diff changeset
301 // iter is supposed to visit the node again
1ce90ab4fab9 add visit_on_exit to iterator implementation
Mike Becker <universe@uap-core.de>
parents: 836
diff changeset
302 iter->exiting = true;
836
2672a2f79484 implement basic (enter only) tree iterator
Mike Becker <universe@uap-core.de>
parents: 834
diff changeset
303 } else {
838
1ce90ab4fab9 add visit_on_exit to iterator implementation
Mike Becker <universe@uap-core.de>
parents: 836
diff changeset
304 iter->exiting = false;
1ce90ab4fab9 add visit_on_exit to iterator implementation
Mike Becker <universe@uap-core.de>
parents: 836
diff changeset
305 // move to the sibling
836
2672a2f79484 implement basic (enter only) tree iterator
Mike Becker <universe@uap-core.de>
parents: 834
diff changeset
306 iter->counter++;
2672a2f79484 implement basic (enter only) tree iterator
Mike Becker <universe@uap-core.de>
parents: 834
diff changeset
307 iter->node = next;
2672a2f79484 implement basic (enter only) tree iterator
Mike Becker <universe@uap-core.de>
parents: 834
diff changeset
308 // new top of stack is the sibling
2672a2f79484 implement basic (enter only) tree iterator
Mike Becker <universe@uap-core.de>
parents: 834
diff changeset
309 iter->stack[iter->depth - 1] = next;
2672a2f79484 implement basic (enter only) tree iterator
Mike Becker <universe@uap-core.de>
parents: 834
diff changeset
310 }
838
1ce90ab4fab9 add visit_on_exit to iterator implementation
Mike Becker <universe@uap-core.de>
parents: 836
diff changeset
311 }
836
2672a2f79484 implement basic (enter only) tree iterator
Mike Becker <universe@uap-core.de>
parents: 834
diff changeset
312 } else {
2672a2f79484 implement basic (enter only) tree iterator
Mike Becker <universe@uap-core.de>
parents: 834
diff changeset
313 // node has children, push the first child onto the stack and enter it
2672a2f79484 implement basic (enter only) tree iterator
Mike Becker <universe@uap-core.de>
parents: 834
diff changeset
314 cx_array_simple_add(iter->stack, children);
2672a2f79484 implement basic (enter only) tree iterator
Mike Becker <universe@uap-core.de>
parents: 834
diff changeset
315 iter->node = children;
2672a2f79484 implement basic (enter only) tree iterator
Mike Becker <universe@uap-core.de>
parents: 834
diff changeset
316 iter->counter++;
2672a2f79484 implement basic (enter only) tree iterator
Mike Becker <universe@uap-core.de>
parents: 834
diff changeset
317 }
830
c4dae6fe6d5b commit complicated stuff before simplifying it
Mike Becker <universe@uap-core.de>
parents: 826
diff changeset
318 }
c4dae6fe6d5b commit complicated stuff before simplifying it
Mike Becker <universe@uap-core.de>
parents: 826
diff changeset
319
c4dae6fe6d5b commit complicated stuff before simplifying it
Mike Becker <universe@uap-core.de>
parents: 826
diff changeset
320 CxTreeIterator cx_tree_iterator(
c4dae6fe6d5b commit complicated stuff before simplifying it
Mike Becker <universe@uap-core.de>
parents: 826
diff changeset
321 void *root,
833
5c926801f052 vastly simplify tree iterators and add test for creating them
Mike Becker <universe@uap-core.de>
parents: 830
diff changeset
322 bool visit_on_exit,
830
c4dae6fe6d5b commit complicated stuff before simplifying it
Mike Becker <universe@uap-core.de>
parents: 826
diff changeset
323 ptrdiff_t loc_children,
c4dae6fe6d5b commit complicated stuff before simplifying it
Mike Becker <universe@uap-core.de>
parents: 826
diff changeset
324 ptrdiff_t loc_next
c4dae6fe6d5b commit complicated stuff before simplifying it
Mike Becker <universe@uap-core.de>
parents: 826
diff changeset
325 ) {
c4dae6fe6d5b commit complicated stuff before simplifying it
Mike Becker <universe@uap-core.de>
parents: 826
diff changeset
326 CxTreeIterator iter;
c4dae6fe6d5b commit complicated stuff before simplifying it
Mike Becker <universe@uap-core.de>
parents: 826
diff changeset
327 iter.loc_children = loc_children;
c4dae6fe6d5b commit complicated stuff before simplifying it
Mike Becker <universe@uap-core.de>
parents: 826
diff changeset
328 iter.loc_next = loc_next;
833
5c926801f052 vastly simplify tree iterators and add test for creating them
Mike Becker <universe@uap-core.de>
parents: 830
diff changeset
329 iter.visit_on_exit = visit_on_exit;
830
c4dae6fe6d5b commit complicated stuff before simplifying it
Mike Becker <universe@uap-core.de>
parents: 826
diff changeset
330
905
39aa4f106a71 complete implementation of remaining high level tree functions
Mike Becker <universe@uap-core.de>
parents: 904
diff changeset
331 // initialize members
853
d4baf4dd55c3 simplify iterator structures
Mike Becker <universe@uap-core.de>
parents: 848
diff changeset
332 iter.node_next = NULL;
833
5c926801f052 vastly simplify tree iterators and add test for creating them
Mike Becker <universe@uap-core.de>
parents: 830
diff changeset
333 iter.exiting = false;
848
6456036bbb37 implement tree continue - fixes #376
Mike Becker <universe@uap-core.de>
parents: 845
diff changeset
334 iter.skip = false;
830
c4dae6fe6d5b commit complicated stuff before simplifying it
Mike Becker <universe@uap-core.de>
parents: 826
diff changeset
335
c4dae6fe6d5b commit complicated stuff before simplifying it
Mike Becker <universe@uap-core.de>
parents: 826
diff changeset
336 // assign base iterator functions
854
fe0d69d72bcd fix members inherited by macro or include are not documented
Mike Becker <universe@uap-core.de>
parents: 853
diff changeset
337 iter.base.mutating = false;
fe0d69d72bcd fix members inherited by macro or include are not documented
Mike Becker <universe@uap-core.de>
parents: 853
diff changeset
338 iter.base.remove = false;
fe0d69d72bcd fix members inherited by macro or include are not documented
Mike Becker <universe@uap-core.de>
parents: 853
diff changeset
339 iter.base.current_impl = NULL;
fe0d69d72bcd fix members inherited by macro or include are not documented
Mike Becker <universe@uap-core.de>
parents: 853
diff changeset
340 iter.base.valid = cx_tree_iter_valid;
fe0d69d72bcd fix members inherited by macro or include are not documented
Mike Becker <universe@uap-core.de>
parents: 853
diff changeset
341 iter.base.next = cx_tree_iter_next;
fe0d69d72bcd fix members inherited by macro or include are not documented
Mike Becker <universe@uap-core.de>
parents: 853
diff changeset
342 iter.base.current = cx_tree_iter_current;
830
c4dae6fe6d5b commit complicated stuff before simplifying it
Mike Becker <universe@uap-core.de>
parents: 826
diff changeset
343
905
39aa4f106a71 complete implementation of remaining high level tree functions
Mike Becker <universe@uap-core.de>
parents: 904
diff changeset
344 // visit the root node
39aa4f106a71 complete implementation of remaining high level tree functions
Mike Becker <universe@uap-core.de>
parents: 904
diff changeset
345 iter.node = root;
39aa4f106a71 complete implementation of remaining high level tree functions
Mike Becker <universe@uap-core.de>
parents: 904
diff changeset
346 if (root != NULL) {
39aa4f106a71 complete implementation of remaining high level tree functions
Mike Becker <universe@uap-core.de>
parents: 904
diff changeset
347 iter.stack_capacity = 16;
39aa4f106a71 complete implementation of remaining high level tree functions
Mike Becker <universe@uap-core.de>
parents: 904
diff changeset
348 iter.stack = malloc(sizeof(void *) * 16);
39aa4f106a71 complete implementation of remaining high level tree functions
Mike Becker <universe@uap-core.de>
parents: 904
diff changeset
349 iter.stack[0] = root;
39aa4f106a71 complete implementation of remaining high level tree functions
Mike Becker <universe@uap-core.de>
parents: 904
diff changeset
350 iter.counter = 1;
39aa4f106a71 complete implementation of remaining high level tree functions
Mike Becker <universe@uap-core.de>
parents: 904
diff changeset
351 iter.depth = 1;
39aa4f106a71 complete implementation of remaining high level tree functions
Mike Becker <universe@uap-core.de>
parents: 904
diff changeset
352 } else {
39aa4f106a71 complete implementation of remaining high level tree functions
Mike Becker <universe@uap-core.de>
parents: 904
diff changeset
353 iter.stack_capacity = 0;
39aa4f106a71 complete implementation of remaining high level tree functions
Mike Becker <universe@uap-core.de>
parents: 904
diff changeset
354 iter.stack = NULL;
39aa4f106a71 complete implementation of remaining high level tree functions
Mike Becker <universe@uap-core.de>
parents: 904
diff changeset
355 iter.counter = 0;
39aa4f106a71 complete implementation of remaining high level tree functions
Mike Becker <universe@uap-core.de>
parents: 904
diff changeset
356 iter.depth = 0;
39aa4f106a71 complete implementation of remaining high level tree functions
Mike Becker <universe@uap-core.de>
parents: 904
diff changeset
357 }
39aa4f106a71 complete implementation of remaining high level tree functions
Mike Becker <universe@uap-core.de>
parents: 904
diff changeset
358
830
c4dae6fe6d5b commit complicated stuff before simplifying it
Mike Becker <universe@uap-core.de>
parents: 826
diff changeset
359 return iter;
c4dae6fe6d5b commit complicated stuff before simplifying it
Mike Becker <universe@uap-core.de>
parents: 826
diff changeset
360 }
845
2615317311b7 add cx_tree_visitor()
Mike Becker <universe@uap-core.de>
parents: 840
diff changeset
361
890
54565fd74e74 move all const keywords to the west - fixes #426
Mike Becker <universe@uap-core.de>
parents: 871
diff changeset
362 static bool cx_tree_visitor_valid(const void *it) {
54565fd74e74 move all const keywords to the west - fixes #426
Mike Becker <universe@uap-core.de>
parents: 871
diff changeset
363 const struct cx_tree_visitor_s *iter = it;
845
2615317311b7 add cx_tree_visitor()
Mike Becker <universe@uap-core.de>
parents: 840
diff changeset
364 return iter->node != NULL;
2615317311b7 add cx_tree_visitor()
Mike Becker <universe@uap-core.de>
parents: 840
diff changeset
365 }
2615317311b7 add cx_tree_visitor()
Mike Becker <universe@uap-core.de>
parents: 840
diff changeset
366
890
54565fd74e74 move all const keywords to the west - fixes #426
Mike Becker <universe@uap-core.de>
parents: 871
diff changeset
367 static void *cx_tree_visitor_current(const void *it) {
54565fd74e74 move all const keywords to the west - fixes #426
Mike Becker <universe@uap-core.de>
parents: 871
diff changeset
368 const struct cx_tree_visitor_s *iter = it;
845
2615317311b7 add cx_tree_visitor()
Mike Becker <universe@uap-core.de>
parents: 840
diff changeset
369 return iter->node;
2615317311b7 add cx_tree_visitor()
Mike Becker <universe@uap-core.de>
parents: 840
diff changeset
370 }
2615317311b7 add cx_tree_visitor()
Mike Becker <universe@uap-core.de>
parents: 840
diff changeset
371
2615317311b7 add cx_tree_visitor()
Mike Becker <universe@uap-core.de>
parents: 840
diff changeset
372 __attribute__((__nonnull__))
2615317311b7 add cx_tree_visitor()
Mike Becker <universe@uap-core.de>
parents: 840
diff changeset
373 static void cx_tree_visitor_enqueue_siblings(
2615317311b7 add cx_tree_visitor()
Mike Becker <universe@uap-core.de>
parents: 840
diff changeset
374 struct cx_tree_visitor_s *iter, void *node, ptrdiff_t loc_next) {
2615317311b7 add cx_tree_visitor()
Mike Becker <universe@uap-core.de>
parents: 840
diff changeset
375 node = tree_next(node);
2615317311b7 add cx_tree_visitor()
Mike Becker <universe@uap-core.de>
parents: 840
diff changeset
376 while (node != NULL) {
2615317311b7 add cx_tree_visitor()
Mike Becker <universe@uap-core.de>
parents: 840
diff changeset
377 struct cx_tree_visitor_queue_s *q;
2615317311b7 add cx_tree_visitor()
Mike Becker <universe@uap-core.de>
parents: 840
diff changeset
378 q = malloc(sizeof(struct cx_tree_visitor_queue_s));
2615317311b7 add cx_tree_visitor()
Mike Becker <universe@uap-core.de>
parents: 840
diff changeset
379 q->depth = iter->queue_last->depth;
2615317311b7 add cx_tree_visitor()
Mike Becker <universe@uap-core.de>
parents: 840
diff changeset
380 q->node = node;
2615317311b7 add cx_tree_visitor()
Mike Becker <universe@uap-core.de>
parents: 840
diff changeset
381 iter->queue_last->next = q;
2615317311b7 add cx_tree_visitor()
Mike Becker <universe@uap-core.de>
parents: 840
diff changeset
382 iter->queue_last = q;
2615317311b7 add cx_tree_visitor()
Mike Becker <universe@uap-core.de>
parents: 840
diff changeset
383 node = tree_next(node);
2615317311b7 add cx_tree_visitor()
Mike Becker <universe@uap-core.de>
parents: 840
diff changeset
384 }
2615317311b7 add cx_tree_visitor()
Mike Becker <universe@uap-core.de>
parents: 840
diff changeset
385 iter->queue_last->next = NULL;
2615317311b7 add cx_tree_visitor()
Mike Becker <universe@uap-core.de>
parents: 840
diff changeset
386 }
2615317311b7 add cx_tree_visitor()
Mike Becker <universe@uap-core.de>
parents: 840
diff changeset
387
2615317311b7 add cx_tree_visitor()
Mike Becker <universe@uap-core.de>
parents: 840
diff changeset
388 static void cx_tree_visitor_next(void *it) {
2615317311b7 add cx_tree_visitor()
Mike Becker <universe@uap-core.de>
parents: 840
diff changeset
389 struct cx_tree_visitor_s *iter = it;
905
39aa4f106a71 complete implementation of remaining high level tree functions
Mike Becker <universe@uap-core.de>
parents: 904
diff changeset
390 // protect us from misuse
39aa4f106a71 complete implementation of remaining high level tree functions
Mike Becker <universe@uap-core.de>
parents: 904
diff changeset
391 if (!iter->base.valid(iter)) return;
39aa4f106a71 complete implementation of remaining high level tree functions
Mike Becker <universe@uap-core.de>
parents: 904
diff changeset
392
845
2615317311b7 add cx_tree_visitor()
Mike Becker <universe@uap-core.de>
parents: 840
diff changeset
393 ptrdiff_t const loc_next = iter->loc_next;
2615317311b7 add cx_tree_visitor()
Mike Becker <universe@uap-core.de>
parents: 840
diff changeset
394 ptrdiff_t const loc_children = iter->loc_children;
2615317311b7 add cx_tree_visitor()
Mike Becker <universe@uap-core.de>
parents: 840
diff changeset
395
848
6456036bbb37 implement tree continue - fixes #376
Mike Becker <universe@uap-core.de>
parents: 845
diff changeset
396 // add the children of the current node to the queue
6456036bbb37 implement tree continue - fixes #376
Mike Becker <universe@uap-core.de>
parents: 845
diff changeset
397 // unless the skip flag is set
6456036bbb37 implement tree continue - fixes #376
Mike Becker <universe@uap-core.de>
parents: 845
diff changeset
398 void *children;
6456036bbb37 implement tree continue - fixes #376
Mike Becker <universe@uap-core.de>
parents: 845
diff changeset
399 if (iter->skip) {
6456036bbb37 implement tree continue - fixes #376
Mike Becker <universe@uap-core.de>
parents: 845
diff changeset
400 iter->skip = false;
6456036bbb37 implement tree continue - fixes #376
Mike Becker <universe@uap-core.de>
parents: 845
diff changeset
401 children = NULL;
6456036bbb37 implement tree continue - fixes #376
Mike Becker <universe@uap-core.de>
parents: 845
diff changeset
402 } else {
6456036bbb37 implement tree continue - fixes #376
Mike Becker <universe@uap-core.de>
parents: 845
diff changeset
403 children = tree_children(iter->node);
6456036bbb37 implement tree continue - fixes #376
Mike Becker <universe@uap-core.de>
parents: 845
diff changeset
404 }
6456036bbb37 implement tree continue - fixes #376
Mike Becker <universe@uap-core.de>
parents: 845
diff changeset
405 if (children != NULL) {
6456036bbb37 implement tree continue - fixes #376
Mike Becker <universe@uap-core.de>
parents: 845
diff changeset
406 struct cx_tree_visitor_queue_s *q;
6456036bbb37 implement tree continue - fixes #376
Mike Becker <universe@uap-core.de>
parents: 845
diff changeset
407 q = malloc(sizeof(struct cx_tree_visitor_queue_s));
6456036bbb37 implement tree continue - fixes #376
Mike Becker <universe@uap-core.de>
parents: 845
diff changeset
408 q->depth = iter->depth + 1;
6456036bbb37 implement tree continue - fixes #376
Mike Becker <universe@uap-core.de>
parents: 845
diff changeset
409 q->node = children;
6456036bbb37 implement tree continue - fixes #376
Mike Becker <universe@uap-core.de>
parents: 845
diff changeset
410 if (iter->queue_last == NULL) {
6456036bbb37 implement tree continue - fixes #376
Mike Becker <universe@uap-core.de>
parents: 845
diff changeset
411 assert(iter->queue_next == NULL);
6456036bbb37 implement tree continue - fixes #376
Mike Becker <universe@uap-core.de>
parents: 845
diff changeset
412 iter->queue_next = q;
6456036bbb37 implement tree continue - fixes #376
Mike Becker <universe@uap-core.de>
parents: 845
diff changeset
413 } else {
6456036bbb37 implement tree continue - fixes #376
Mike Becker <universe@uap-core.de>
parents: 845
diff changeset
414 iter->queue_last->next = q;
6456036bbb37 implement tree continue - fixes #376
Mike Becker <universe@uap-core.de>
parents: 845
diff changeset
415 }
6456036bbb37 implement tree continue - fixes #376
Mike Becker <universe@uap-core.de>
parents: 845
diff changeset
416 iter->queue_last = q;
6456036bbb37 implement tree continue - fixes #376
Mike Becker <universe@uap-core.de>
parents: 845
diff changeset
417 cx_tree_visitor_enqueue_siblings(iter, children, loc_next);
6456036bbb37 implement tree continue - fixes #376
Mike Becker <universe@uap-core.de>
parents: 845
diff changeset
418 }
6456036bbb37 implement tree continue - fixes #376
Mike Becker <universe@uap-core.de>
parents: 845
diff changeset
419
845
2615317311b7 add cx_tree_visitor()
Mike Becker <universe@uap-core.de>
parents: 840
diff changeset
420 // check if there is a next node
2615317311b7 add cx_tree_visitor()
Mike Becker <universe@uap-core.de>
parents: 840
diff changeset
421 if (iter->queue_next == NULL) {
2615317311b7 add cx_tree_visitor()
Mike Becker <universe@uap-core.de>
parents: 840
diff changeset
422 iter->node = NULL;
2615317311b7 add cx_tree_visitor()
Mike Becker <universe@uap-core.de>
parents: 840
diff changeset
423 return;
2615317311b7 add cx_tree_visitor()
Mike Becker <universe@uap-core.de>
parents: 840
diff changeset
424 }
2615317311b7 add cx_tree_visitor()
Mike Becker <universe@uap-core.de>
parents: 840
diff changeset
425
2615317311b7 add cx_tree_visitor()
Mike Becker <universe@uap-core.de>
parents: 840
diff changeset
426 // dequeue the next node
2615317311b7 add cx_tree_visitor()
Mike Becker <universe@uap-core.de>
parents: 840
diff changeset
427 iter->node = iter->queue_next->node;
2615317311b7 add cx_tree_visitor()
Mike Becker <universe@uap-core.de>
parents: 840
diff changeset
428 iter->depth = iter->queue_next->depth;
2615317311b7 add cx_tree_visitor()
Mike Becker <universe@uap-core.de>
parents: 840
diff changeset
429 {
2615317311b7 add cx_tree_visitor()
Mike Becker <universe@uap-core.de>
parents: 840
diff changeset
430 struct cx_tree_visitor_queue_s *q = iter->queue_next;
2615317311b7 add cx_tree_visitor()
Mike Becker <universe@uap-core.de>
parents: 840
diff changeset
431 iter->queue_next = q->next;
2615317311b7 add cx_tree_visitor()
Mike Becker <universe@uap-core.de>
parents: 840
diff changeset
432 if (iter->queue_next == NULL) {
2615317311b7 add cx_tree_visitor()
Mike Becker <universe@uap-core.de>
parents: 840
diff changeset
433 assert(iter->queue_last == q);
2615317311b7 add cx_tree_visitor()
Mike Becker <universe@uap-core.de>
parents: 840
diff changeset
434 iter->queue_last = NULL;
2615317311b7 add cx_tree_visitor()
Mike Becker <universe@uap-core.de>
parents: 840
diff changeset
435 }
2615317311b7 add cx_tree_visitor()
Mike Becker <universe@uap-core.de>
parents: 840
diff changeset
436 free(q);
2615317311b7 add cx_tree_visitor()
Mike Becker <universe@uap-core.de>
parents: 840
diff changeset
437 }
2615317311b7 add cx_tree_visitor()
Mike Becker <universe@uap-core.de>
parents: 840
diff changeset
438
2615317311b7 add cx_tree_visitor()
Mike Becker <universe@uap-core.de>
parents: 840
diff changeset
439 // increment the node counter
2615317311b7 add cx_tree_visitor()
Mike Becker <universe@uap-core.de>
parents: 840
diff changeset
440 iter->counter++;
2615317311b7 add cx_tree_visitor()
Mike Becker <universe@uap-core.de>
parents: 840
diff changeset
441 }
2615317311b7 add cx_tree_visitor()
Mike Becker <universe@uap-core.de>
parents: 840
diff changeset
442
2615317311b7 add cx_tree_visitor()
Mike Becker <universe@uap-core.de>
parents: 840
diff changeset
443 CxTreeVisitor cx_tree_visitor(
2615317311b7 add cx_tree_visitor()
Mike Becker <universe@uap-core.de>
parents: 840
diff changeset
444 void *root,
2615317311b7 add cx_tree_visitor()
Mike Becker <universe@uap-core.de>
parents: 840
diff changeset
445 ptrdiff_t loc_children,
2615317311b7 add cx_tree_visitor()
Mike Becker <universe@uap-core.de>
parents: 840
diff changeset
446 ptrdiff_t loc_next
2615317311b7 add cx_tree_visitor()
Mike Becker <universe@uap-core.de>
parents: 840
diff changeset
447 ) {
2615317311b7 add cx_tree_visitor()
Mike Becker <universe@uap-core.de>
parents: 840
diff changeset
448 CxTreeVisitor iter;
2615317311b7 add cx_tree_visitor()
Mike Becker <universe@uap-core.de>
parents: 840
diff changeset
449 iter.loc_children = loc_children;
2615317311b7 add cx_tree_visitor()
Mike Becker <universe@uap-core.de>
parents: 840
diff changeset
450 iter.loc_next = loc_next;
2615317311b7 add cx_tree_visitor()
Mike Becker <universe@uap-core.de>
parents: 840
diff changeset
451
905
39aa4f106a71 complete implementation of remaining high level tree functions
Mike Becker <universe@uap-core.de>
parents: 904
diff changeset
452 // initialize members
848
6456036bbb37 implement tree continue - fixes #376
Mike Becker <universe@uap-core.de>
parents: 845
diff changeset
453 iter.skip = false;
6456036bbb37 implement tree continue - fixes #376
Mike Becker <universe@uap-core.de>
parents: 845
diff changeset
454 iter.queue_next = NULL;
6456036bbb37 implement tree continue - fixes #376
Mike Becker <universe@uap-core.de>
parents: 845
diff changeset
455 iter.queue_last = NULL;
845
2615317311b7 add cx_tree_visitor()
Mike Becker <universe@uap-core.de>
parents: 840
diff changeset
456
2615317311b7 add cx_tree_visitor()
Mike Becker <universe@uap-core.de>
parents: 840
diff changeset
457 // assign base iterator functions
854
fe0d69d72bcd fix members inherited by macro or include are not documented
Mike Becker <universe@uap-core.de>
parents: 853
diff changeset
458 iter.base.mutating = false;
fe0d69d72bcd fix members inherited by macro or include are not documented
Mike Becker <universe@uap-core.de>
parents: 853
diff changeset
459 iter.base.remove = false;
fe0d69d72bcd fix members inherited by macro or include are not documented
Mike Becker <universe@uap-core.de>
parents: 853
diff changeset
460 iter.base.current_impl = NULL;
fe0d69d72bcd fix members inherited by macro or include are not documented
Mike Becker <universe@uap-core.de>
parents: 853
diff changeset
461 iter.base.valid = cx_tree_visitor_valid;
fe0d69d72bcd fix members inherited by macro or include are not documented
Mike Becker <universe@uap-core.de>
parents: 853
diff changeset
462 iter.base.next = cx_tree_visitor_next;
fe0d69d72bcd fix members inherited by macro or include are not documented
Mike Becker <universe@uap-core.de>
parents: 853
diff changeset
463 iter.base.current = cx_tree_visitor_current;
845
2615317311b7 add cx_tree_visitor()
Mike Becker <universe@uap-core.de>
parents: 840
diff changeset
464
905
39aa4f106a71 complete implementation of remaining high level tree functions
Mike Becker <universe@uap-core.de>
parents: 904
diff changeset
465 // visit the root node
39aa4f106a71 complete implementation of remaining high level tree functions
Mike Becker <universe@uap-core.de>
parents: 904
diff changeset
466 iter.node = root;
39aa4f106a71 complete implementation of remaining high level tree functions
Mike Becker <universe@uap-core.de>
parents: 904
diff changeset
467 if (root != NULL) {
39aa4f106a71 complete implementation of remaining high level tree functions
Mike Becker <universe@uap-core.de>
parents: 904
diff changeset
468 iter.counter = 1;
39aa4f106a71 complete implementation of remaining high level tree functions
Mike Becker <universe@uap-core.de>
parents: 904
diff changeset
469 iter.depth = 1;
39aa4f106a71 complete implementation of remaining high level tree functions
Mike Becker <universe@uap-core.de>
parents: 904
diff changeset
470 } else {
39aa4f106a71 complete implementation of remaining high level tree functions
Mike Becker <universe@uap-core.de>
parents: 904
diff changeset
471 iter.counter = 0;
39aa4f106a71 complete implementation of remaining high level tree functions
Mike Becker <universe@uap-core.de>
parents: 904
diff changeset
472 iter.depth = 0;
39aa4f106a71 complete implementation of remaining high level tree functions
Mike Becker <universe@uap-core.de>
parents: 904
diff changeset
473 }
39aa4f106a71 complete implementation of remaining high level tree functions
Mike Becker <universe@uap-core.de>
parents: 904
diff changeset
474
845
2615317311b7 add cx_tree_visitor()
Mike Becker <universe@uap-core.de>
parents: 840
diff changeset
475 return iter;
2615317311b7 add cx_tree_visitor()
Mike Becker <universe@uap-core.de>
parents: 840
diff changeset
476 }
2615317311b7 add cx_tree_visitor()
Mike Becker <universe@uap-core.de>
parents: 840
diff changeset
477
867
471c714d5b6f cx_tree_add() fix missing spec for adding duplicates
Mike Becker <universe@uap-core.de>
parents: 866
diff changeset
478 static void cx_tree_add_link_duplicate(
871
e29c1f96646d rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents: 870
diff changeset
479 void *original, void *duplicate,
867
471c714d5b6f cx_tree_add() fix missing spec for adding duplicates
Mike Becker <universe@uap-core.de>
parents: 866
diff changeset
480 ptrdiff_t loc_parent, ptrdiff_t loc_children, ptrdiff_t loc_last_child,
471c714d5b6f cx_tree_add() fix missing spec for adding duplicates
Mike Becker <universe@uap-core.de>
parents: 866
diff changeset
481 ptrdiff_t loc_prev, ptrdiff_t loc_next
471c714d5b6f cx_tree_add() fix missing spec for adding duplicates
Mike Becker <universe@uap-core.de>
parents: 866
diff changeset
482 ) {
471c714d5b6f cx_tree_add() fix missing spec for adding duplicates
Mike Becker <universe@uap-core.de>
parents: 866
diff changeset
483 void *shared_parent = tree_parent(original);
471c714d5b6f cx_tree_add() fix missing spec for adding duplicates
Mike Becker <universe@uap-core.de>
parents: 866
diff changeset
484 if (shared_parent == NULL) {
871
e29c1f96646d rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents: 870
diff changeset
485 cx_tree_link(original, duplicate, cx_tree_ptr_locations);
867
471c714d5b6f cx_tree_add() fix missing spec for adding duplicates
Mike Becker <universe@uap-core.de>
parents: 866
diff changeset
486 } else {
471c714d5b6f cx_tree_add() fix missing spec for adding duplicates
Mike Becker <universe@uap-core.de>
parents: 866
diff changeset
487 cx_tree_link(shared_parent, duplicate, cx_tree_ptr_locations);
471c714d5b6f cx_tree_add() fix missing spec for adding duplicates
Mike Becker <universe@uap-core.de>
parents: 866
diff changeset
488 }
471c714d5b6f cx_tree_add() fix missing spec for adding duplicates
Mike Becker <universe@uap-core.de>
parents: 866
diff changeset
489 }
471c714d5b6f cx_tree_add() fix missing spec for adding duplicates
Mike Becker <universe@uap-core.de>
parents: 866
diff changeset
490
871
e29c1f96646d rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents: 870
diff changeset
491 static void cx_tree_add_link_new(
e29c1f96646d rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents: 870
diff changeset
492 void *parent, void *node, cx_tree_search_func sfunc,
e29c1f96646d rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents: 870
diff changeset
493 ptrdiff_t loc_parent, ptrdiff_t loc_children, ptrdiff_t loc_last_child,
e29c1f96646d rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents: 870
diff changeset
494 ptrdiff_t loc_prev, ptrdiff_t loc_next
e29c1f96646d rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents: 870
diff changeset
495 ) {
e29c1f96646d rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents: 870
diff changeset
496 // check the current children one by one,
e29c1f96646d rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents: 870
diff changeset
497 // if they could be children of the new node
e29c1f96646d rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents: 870
diff changeset
498 void *child = tree_children(parent);
e29c1f96646d rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents: 870
diff changeset
499 while (child != NULL) {
e29c1f96646d rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents: 870
diff changeset
500 void *next = tree_next(child);
e29c1f96646d rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents: 870
diff changeset
501
e29c1f96646d rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents: 870
diff changeset
502 if (sfunc(node, child) > 0) {
e29c1f96646d rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents: 870
diff changeset
503 // the sibling could be a child -> re-link
e29c1f96646d rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents: 870
diff changeset
504 cx_tree_link(node, child, cx_tree_ptr_locations);
e29c1f96646d rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents: 870
diff changeset
505 }
e29c1f96646d rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents: 870
diff changeset
506
e29c1f96646d rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents: 870
diff changeset
507 child = next;
e29c1f96646d rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents: 870
diff changeset
508 }
e29c1f96646d rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents: 870
diff changeset
509
e29c1f96646d rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents: 870
diff changeset
510 // add new node as new child
e29c1f96646d rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents: 870
diff changeset
511 cx_tree_link(parent, node, cx_tree_ptr_locations);
e29c1f96646d rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents: 870
diff changeset
512 }
e29c1f96646d rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents: 870
diff changeset
513
e29c1f96646d rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents: 870
diff changeset
514 int cx_tree_add(
890
54565fd74e74 move all const keywords to the west - fixes #426
Mike Becker <universe@uap-core.de>
parents: 871
diff changeset
515 const void *src,
860
558ed4c6abd0 add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents: 854
diff changeset
516 cx_tree_search_func sfunc,
864
7d3061f212cb complete specification for tree_add functions
Mike Becker <universe@uap-core.de>
parents: 863
diff changeset
517 cx_tree_node_create_func cfunc,
7d3061f212cb complete specification for tree_add functions
Mike Becker <universe@uap-core.de>
parents: 863
diff changeset
518 void *cdata,
871
e29c1f96646d rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents: 870
diff changeset
519 void **cnode,
e29c1f96646d rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents: 870
diff changeset
520 void *root,
860
558ed4c6abd0 add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents: 854
diff changeset
521 ptrdiff_t loc_parent,
558ed4c6abd0 add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents: 854
diff changeset
522 ptrdiff_t loc_children,
864
7d3061f212cb complete specification for tree_add functions
Mike Becker <universe@uap-core.de>
parents: 863
diff changeset
523 ptrdiff_t loc_last_child,
860
558ed4c6abd0 add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents: 854
diff changeset
524 ptrdiff_t loc_prev,
558ed4c6abd0 add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents: 854
diff changeset
525 ptrdiff_t loc_next
558ed4c6abd0 add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents: 854
diff changeset
526 ) {
871
e29c1f96646d rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents: 870
diff changeset
527 *cnode = cfunc(src, cdata);
e29c1f96646d rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents: 870
diff changeset
528 if (*cnode == NULL) return 1;
e29c1f96646d rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents: 870
diff changeset
529 cx_tree_zero_pointers(*cnode, cx_tree_ptr_locations);
866
1f636de4a63f complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents: 864
diff changeset
530
1f636de4a63f complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents: 864
diff changeset
531 void *match = NULL;
1f636de4a63f complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents: 864
diff changeset
532 int result = cx_tree_search(
871
e29c1f96646d rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents: 870
diff changeset
533 root,
e29c1f96646d rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents: 870
diff changeset
534 *cnode,
866
1f636de4a63f complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents: 864
diff changeset
535 sfunc,
1f636de4a63f complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents: 864
diff changeset
536 &match,
1f636de4a63f complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents: 864
diff changeset
537 loc_children,
1f636de4a63f complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents: 864
diff changeset
538 loc_next
1f636de4a63f complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents: 864
diff changeset
539 );
1f636de4a63f complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents: 864
diff changeset
540
1f636de4a63f complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents: 864
diff changeset
541 if (result < 0) {
871
e29c1f96646d rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents: 870
diff changeset
542 // node does not fit into the tree - return non-zero value
e29c1f96646d rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents: 870
diff changeset
543 return 1;
866
1f636de4a63f complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents: 864
diff changeset
544 } else if (result == 0) {
871
e29c1f96646d rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents: 870
diff changeset
545 // data already found in the tree, link duplicate
e29c1f96646d rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents: 870
diff changeset
546 cx_tree_add_link_duplicate(match, *cnode, cx_tree_ptr_locations);
866
1f636de4a63f complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents: 864
diff changeset
547 } else {
871
e29c1f96646d rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents: 870
diff changeset
548 // closest match found, add new node
e29c1f96646d rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents: 870
diff changeset
549 cx_tree_add_link_new(match, *cnode, sfunc, cx_tree_ptr_locations);
866
1f636de4a63f complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents: 864
diff changeset
550 }
1f636de4a63f complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents: 864
diff changeset
551
871
e29c1f96646d rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents: 870
diff changeset
552 return 0;
860
558ed4c6abd0 add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents: 854
diff changeset
553 }
558ed4c6abd0 add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents: 854
diff changeset
554
864
7d3061f212cb complete specification for tree_add functions
Mike Becker <universe@uap-core.de>
parents: 863
diff changeset
555 unsigned int cx_tree_add_look_around_depth = 3;
7d3061f212cb complete specification for tree_add functions
Mike Becker <universe@uap-core.de>
parents: 863
diff changeset
556
860
558ed4c6abd0 add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents: 854
diff changeset
557 size_t cx_tree_add_iter(
558ed4c6abd0 add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents: 854
diff changeset
558 struct cx_iterator_base_s *iter,
893
0a2b328f5b91 add bounding parameter to cx_tree_add_iter()
Mike Becker <universe@uap-core.de>
parents: 890
diff changeset
559 size_t num,
860
558ed4c6abd0 add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents: 854
diff changeset
560 cx_tree_search_func sfunc,
864
7d3061f212cb complete specification for tree_add functions
Mike Becker <universe@uap-core.de>
parents: 863
diff changeset
561 cx_tree_node_create_func cfunc,
7d3061f212cb complete specification for tree_add functions
Mike Becker <universe@uap-core.de>
parents: 863
diff changeset
562 void *cdata,
871
e29c1f96646d rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents: 870
diff changeset
563 void **failed,
e29c1f96646d rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents: 870
diff changeset
564 void *root,
860
558ed4c6abd0 add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents: 854
diff changeset
565 ptrdiff_t loc_parent,
558ed4c6abd0 add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents: 854
diff changeset
566 ptrdiff_t loc_children,
864
7d3061f212cb complete specification for tree_add functions
Mike Becker <universe@uap-core.de>
parents: 863
diff changeset
567 ptrdiff_t loc_last_child,
860
558ed4c6abd0 add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents: 854
diff changeset
568 ptrdiff_t loc_prev,
558ed4c6abd0 add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents: 854
diff changeset
569 ptrdiff_t loc_next
558ed4c6abd0 add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents: 854
diff changeset
570 ) {
871
e29c1f96646d rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents: 870
diff changeset
571 // erase the failed pointer
e29c1f96646d rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents: 870
diff changeset
572 *failed = NULL;
e29c1f96646d rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents: 870
diff changeset
573
868
56a908924510 cx_tree_add_iter() - optimize check for empty trees
Mike Becker <universe@uap-core.de>
parents: 867
diff changeset
574 // iter not valid? cancel...
56a908924510 cx_tree_add_iter() - optimize check for empty trees
Mike Becker <universe@uap-core.de>
parents: 867
diff changeset
575 if (!iter->valid(iter)) return 0;
56a908924510 cx_tree_add_iter() - optimize check for empty trees
Mike Becker <universe@uap-core.de>
parents: 867
diff changeset
576
866
1f636de4a63f complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents: 864
diff changeset
577 size_t processed = 0;
871
e29c1f96646d rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents: 870
diff changeset
578 void *current_node = root;
890
54565fd74e74 move all const keywords to the west - fixes #426
Mike Becker <universe@uap-core.de>
parents: 871
diff changeset
579 const void *elem;
868
56a908924510 cx_tree_add_iter() - optimize check for empty trees
Mike Becker <universe@uap-core.de>
parents: 867
diff changeset
580
893
0a2b328f5b91 add bounding parameter to cx_tree_add_iter()
Mike Becker <universe@uap-core.de>
parents: 890
diff changeset
581 for (void **eptr; processed < num &&
866
1f636de4a63f complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents: 864
diff changeset
582 iter->valid(iter) && (eptr = iter->current(iter)) != NULL;
1f636de4a63f complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents: 864
diff changeset
583 iter->next(iter)) {
868
56a908924510 cx_tree_add_iter() - optimize check for empty trees
Mike Becker <universe@uap-core.de>
parents: 867
diff changeset
584 elem = *eptr;
866
1f636de4a63f complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents: 864
diff changeset
585
871
e29c1f96646d rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents: 870
diff changeset
586 // create the new node
e29c1f96646d rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents: 870
diff changeset
587 void *new_node = cfunc(elem, cdata);
e29c1f96646d rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents: 870
diff changeset
588 if (new_node == NULL) return processed;
e29c1f96646d rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents: 870
diff changeset
589 cx_tree_zero_pointers(new_node, cx_tree_ptr_locations);
e29c1f96646d rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents: 870
diff changeset
590
866
1f636de4a63f complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents: 864
diff changeset
591 // start searching from current node
1f636de4a63f complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents: 864
diff changeset
592 void *match;
1f636de4a63f complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents: 864
diff changeset
593 int result;
1f636de4a63f complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents: 864
diff changeset
594 unsigned int look_around_retries = cx_tree_add_look_around_depth;
1f636de4a63f complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents: 864
diff changeset
595 cx_tree_add_look_around_retry:
1f636de4a63f complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents: 864
diff changeset
596 result = cx_tree_search(
1f636de4a63f complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents: 864
diff changeset
597 current_node,
871
e29c1f96646d rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents: 870
diff changeset
598 new_node,
866
1f636de4a63f complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents: 864
diff changeset
599 sfunc,
1f636de4a63f complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents: 864
diff changeset
600 &match,
1f636de4a63f complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents: 864
diff changeset
601 loc_children,
1f636de4a63f complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents: 864
diff changeset
602 loc_next
1f636de4a63f complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents: 864
diff changeset
603 );
1f636de4a63f complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents: 864
diff changeset
604
1f636de4a63f complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents: 864
diff changeset
605 if (result < 0) {
1f636de4a63f complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents: 864
diff changeset
606 // traverse upwards and try to find better parents
1f636de4a63f complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents: 864
diff changeset
607 void *parent = tree_parent(current_node);
1f636de4a63f complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents: 864
diff changeset
608 if (parent != NULL) {
1f636de4a63f complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents: 864
diff changeset
609 if (look_around_retries > 0) {
1f636de4a63f complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents: 864
diff changeset
610 look_around_retries--;
1f636de4a63f complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents: 864
diff changeset
611 current_node = parent;
1f636de4a63f complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents: 864
diff changeset
612 } else {
1f636de4a63f complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents: 864
diff changeset
613 // look around retries exhausted, start from the root
871
e29c1f96646d rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents: 870
diff changeset
614 current_node = root;
866
1f636de4a63f complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents: 864
diff changeset
615 }
1f636de4a63f complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents: 864
diff changeset
616 goto cx_tree_add_look_around_retry;
1f636de4a63f complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents: 864
diff changeset
617 } else {
871
e29c1f96646d rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents: 870
diff changeset
618 // no parents. so we failed
e29c1f96646d rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents: 870
diff changeset
619 *failed = new_node;
e29c1f96646d rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents: 870
diff changeset
620 return processed;
866
1f636de4a63f complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents: 864
diff changeset
621 }
1f636de4a63f complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents: 864
diff changeset
622 } else if (result == 0) {
871
e29c1f96646d rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents: 870
diff changeset
623 // data already found in the tree, link duplicate
e29c1f96646d rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents: 870
diff changeset
624 cx_tree_add_link_duplicate(match, new_node, cx_tree_ptr_locations);
e29c1f96646d rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents: 870
diff changeset
625 // but stick with the original match, in case we needed a new root
e29c1f96646d rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents: 870
diff changeset
626 current_node = match;
866
1f636de4a63f complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents: 864
diff changeset
627 } else {
1f636de4a63f complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents: 864
diff changeset
628 // closest match found, add new node as child
871
e29c1f96646d rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents: 870
diff changeset
629 cx_tree_add_link_new(match, new_node, sfunc,
e29c1f96646d rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents: 870
diff changeset
630 cx_tree_ptr_locations);
866
1f636de4a63f complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents: 864
diff changeset
631 current_node = match;
1f636de4a63f complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents: 864
diff changeset
632 }
1f636de4a63f complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents: 864
diff changeset
633
1f636de4a63f complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents: 864
diff changeset
634 processed++;
1f636de4a63f complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents: 864
diff changeset
635 }
1f636de4a63f complete cx_tree_add() implementations
Mike Becker <universe@uap-core.de>
parents: 864
diff changeset
636 return processed;
860
558ed4c6abd0 add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents: 854
diff changeset
637 }
558ed4c6abd0 add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents: 854
diff changeset
638
558ed4c6abd0 add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents: 854
diff changeset
639 size_t cx_tree_add_array(
890
54565fd74e74 move all const keywords to the west - fixes #426
Mike Becker <universe@uap-core.de>
parents: 871
diff changeset
640 const void *src,
860
558ed4c6abd0 add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents: 854
diff changeset
641 size_t num,
558ed4c6abd0 add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents: 854
diff changeset
642 size_t elem_size,
558ed4c6abd0 add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents: 854
diff changeset
643 cx_tree_search_func sfunc,
864
7d3061f212cb complete specification for tree_add functions
Mike Becker <universe@uap-core.de>
parents: 863
diff changeset
644 cx_tree_node_create_func cfunc,
7d3061f212cb complete specification for tree_add functions
Mike Becker <universe@uap-core.de>
parents: 863
diff changeset
645 void *cdata,
871
e29c1f96646d rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents: 870
diff changeset
646 void **failed,
e29c1f96646d rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents: 870
diff changeset
647 void *root,
860
558ed4c6abd0 add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents: 854
diff changeset
648 ptrdiff_t loc_parent,
558ed4c6abd0 add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents: 854
diff changeset
649 ptrdiff_t loc_children,
864
7d3061f212cb complete specification for tree_add functions
Mike Becker <universe@uap-core.de>
parents: 863
diff changeset
650 ptrdiff_t loc_last_child,
860
558ed4c6abd0 add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents: 854
diff changeset
651 ptrdiff_t loc_prev,
558ed4c6abd0 add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents: 854
diff changeset
652 ptrdiff_t loc_next
558ed4c6abd0 add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents: 854
diff changeset
653 ) {
871
e29c1f96646d rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents: 870
diff changeset
654 // erase failed pointer
e29c1f96646d rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents: 870
diff changeset
655 *failed = NULL;
e29c1f96646d rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents: 870
diff changeset
656
860
558ed4c6abd0 add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents: 854
diff changeset
657 // super special case: zero elements
558ed4c6abd0 add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents: 854
diff changeset
658 if (num == 0) {
558ed4c6abd0 add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents: 854
diff changeset
659 return 0;
558ed4c6abd0 add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents: 854
diff changeset
660 }
558ed4c6abd0 add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents: 854
diff changeset
661
558ed4c6abd0 add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents: 854
diff changeset
662 // special case: one element does not need an iterator
558ed4c6abd0 add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents: 854
diff changeset
663 if (num == 1) {
871
e29c1f96646d rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents: 870
diff changeset
664 void *node;
e29c1f96646d rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents: 870
diff changeset
665 if (0 == cx_tree_add(
e29c1f96646d rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents: 870
diff changeset
666 src, sfunc, cfunc, cdata, &node, root,
864
7d3061f212cb complete specification for tree_add functions
Mike Becker <universe@uap-core.de>
parents: 863
diff changeset
667 loc_parent, loc_children, loc_last_child,
7d3061f212cb complete specification for tree_add functions
Mike Becker <universe@uap-core.de>
parents: 863
diff changeset
668 loc_prev, loc_next)) {
860
558ed4c6abd0 add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents: 854
diff changeset
669 return 1;
558ed4c6abd0 add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents: 854
diff changeset
670 } else {
871
e29c1f96646d rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents: 870
diff changeset
671 *failed = node;
860
558ed4c6abd0 add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents: 854
diff changeset
672 return 0;
558ed4c6abd0 add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents: 854
diff changeset
673 }
558ed4c6abd0 add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents: 854
diff changeset
674 }
558ed4c6abd0 add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents: 854
diff changeset
675
558ed4c6abd0 add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents: 854
diff changeset
676 // otherwise, create iterator and hand over to other function
558ed4c6abd0 add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents: 854
diff changeset
677 CxIterator iter = cxIterator(src, elem_size, num);
893
0a2b328f5b91 add bounding parameter to cx_tree_add_iter()
Mike Becker <universe@uap-core.de>
parents: 890
diff changeset
678 return cx_tree_add_iter(cxIteratorRef(iter), num, sfunc,
871
e29c1f96646d rework cx_tree_add() API to allow insertion of edge nodes
Mike Becker <universe@uap-core.de>
parents: 870
diff changeset
679 cfunc, cdata, failed, root,
864
7d3061f212cb complete specification for tree_add functions
Mike Becker <universe@uap-core.de>
parents: 863
diff changeset
680 loc_parent, loc_children, loc_last_child,
7d3061f212cb complete specification for tree_add functions
Mike Becker <universe@uap-core.de>
parents: 863
diff changeset
681 loc_prev, loc_next);
860
558ed4c6abd0 add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents: 854
diff changeset
682 }
558ed4c6abd0 add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents: 854
diff changeset
683
902
5ed7f634f046 implement cxTreeCreate family of functions
Mike Becker <universe@uap-core.de>
parents: 901
diff changeset
684 static void cx_tree_default_destructor(CxTree *tree) {
904
cdc49211d87f implement cxTreeInsert family of functions
Mike Becker <universe@uap-core.de>
parents: 903
diff changeset
685 if (tree->simple_destructor != NULL || tree->advanced_destructor != NULL) {
cdc49211d87f implement cxTreeInsert family of functions
Mike Becker <universe@uap-core.de>
parents: 903
diff changeset
686 CxTreeIterator iter = tree->cl->iterator(tree, true);
cdc49211d87f implement cxTreeInsert family of functions
Mike Becker <universe@uap-core.de>
parents: 903
diff changeset
687 cx_foreach(void *, node, iter) {
cdc49211d87f implement cxTreeInsert family of functions
Mike Becker <universe@uap-core.de>
parents: 903
diff changeset
688 if (iter.exiting) {
cdc49211d87f implement cxTreeInsert family of functions
Mike Becker <universe@uap-core.de>
parents: 903
diff changeset
689 if (tree->simple_destructor) {
cdc49211d87f implement cxTreeInsert family of functions
Mike Becker <universe@uap-core.de>
parents: 903
diff changeset
690 tree->simple_destructor(node);
cdc49211d87f implement cxTreeInsert family of functions
Mike Becker <universe@uap-core.de>
parents: 903
diff changeset
691 }
cdc49211d87f implement cxTreeInsert family of functions
Mike Becker <universe@uap-core.de>
parents: 903
diff changeset
692 if (tree->advanced_destructor) {
cdc49211d87f implement cxTreeInsert family of functions
Mike Becker <universe@uap-core.de>
parents: 903
diff changeset
693 tree->advanced_destructor(tree->destructor_data, node);
cdc49211d87f implement cxTreeInsert family of functions
Mike Becker <universe@uap-core.de>
parents: 903
diff changeset
694 }
cdc49211d87f implement cxTreeInsert family of functions
Mike Becker <universe@uap-core.de>
parents: 903
diff changeset
695 }
cdc49211d87f implement cxTreeInsert family of functions
Mike Becker <universe@uap-core.de>
parents: 903
diff changeset
696 }
cdc49211d87f implement cxTreeInsert family of functions
Mike Becker <universe@uap-core.de>
parents: 903
diff changeset
697 }
902
5ed7f634f046 implement cxTreeCreate family of functions
Mike Becker <universe@uap-core.de>
parents: 901
diff changeset
698 cxFree(tree->allocator, tree);
5ed7f634f046 implement cxTreeCreate family of functions
Mike Becker <universe@uap-core.de>
parents: 901
diff changeset
699 }
5ed7f634f046 implement cxTreeCreate family of functions
Mike Becker <universe@uap-core.de>
parents: 901
diff changeset
700
5ed7f634f046 implement cxTreeCreate family of functions
Mike Becker <universe@uap-core.de>
parents: 901
diff changeset
701 static CxTreeIterator cx_tree_default_iterator(
5ed7f634f046 implement cxTreeCreate family of functions
Mike Becker <universe@uap-core.de>
parents: 901
diff changeset
702 CxTree *tree,
5ed7f634f046 implement cxTreeCreate family of functions
Mike Becker <universe@uap-core.de>
parents: 901
diff changeset
703 bool visit_on_exit
5ed7f634f046 implement cxTreeCreate family of functions
Mike Becker <universe@uap-core.de>
parents: 901
diff changeset
704 ) {
5ed7f634f046 implement cxTreeCreate family of functions
Mike Becker <universe@uap-core.de>
parents: 901
diff changeset
705 return cx_tree_iterator(
5ed7f634f046 implement cxTreeCreate family of functions
Mike Becker <universe@uap-core.de>
parents: 901
diff changeset
706 tree->root, visit_on_exit,
5ed7f634f046 implement cxTreeCreate family of functions
Mike Becker <universe@uap-core.de>
parents: 901
diff changeset
707 tree->loc_children, tree->loc_next
5ed7f634f046 implement cxTreeCreate family of functions
Mike Becker <universe@uap-core.de>
parents: 901
diff changeset
708 );
5ed7f634f046 implement cxTreeCreate family of functions
Mike Becker <universe@uap-core.de>
parents: 901
diff changeset
709 }
5ed7f634f046 implement cxTreeCreate family of functions
Mike Becker <universe@uap-core.de>
parents: 901
diff changeset
710
5ed7f634f046 implement cxTreeCreate family of functions
Mike Becker <universe@uap-core.de>
parents: 901
diff changeset
711 static CxTreeVisitor cx_tree_default_visitor(CxTree *tree) {
5ed7f634f046 implement cxTreeCreate family of functions
Mike Becker <universe@uap-core.de>
parents: 901
diff changeset
712 return cx_tree_visitor(tree->root, tree->loc_children, tree->loc_next);
5ed7f634f046 implement cxTreeCreate family of functions
Mike Becker <universe@uap-core.de>
parents: 901
diff changeset
713 }
5ed7f634f046 implement cxTreeCreate family of functions
Mike Becker <universe@uap-core.de>
parents: 901
diff changeset
714
904
cdc49211d87f implement cxTreeInsert family of functions
Mike Becker <universe@uap-core.de>
parents: 903
diff changeset
715 static int cx_tree_default_insert_element(
cdc49211d87f implement cxTreeInsert family of functions
Mike Becker <universe@uap-core.de>
parents: 903
diff changeset
716 CxTree *tree,
cdc49211d87f implement cxTreeInsert family of functions
Mike Becker <universe@uap-core.de>
parents: 903
diff changeset
717 const void *data
cdc49211d87f implement cxTreeInsert family of functions
Mike Becker <universe@uap-core.de>
parents: 903
diff changeset
718 ) {
cdc49211d87f implement cxTreeInsert family of functions
Mike Becker <universe@uap-core.de>
parents: 903
diff changeset
719 void *node;
cdc49211d87f implement cxTreeInsert family of functions
Mike Becker <universe@uap-core.de>
parents: 903
diff changeset
720 if (tree->root == NULL) {
cdc49211d87f implement cxTreeInsert family of functions
Mike Becker <universe@uap-core.de>
parents: 903
diff changeset
721 node = tree->node_create(data, tree);
cdc49211d87f implement cxTreeInsert family of functions
Mike Becker <universe@uap-core.de>
parents: 903
diff changeset
722 if (node == NULL) return 1;
cdc49211d87f implement cxTreeInsert family of functions
Mike Becker <universe@uap-core.de>
parents: 903
diff changeset
723 cx_tree_zero_pointers(node, cx_tree_node_layout(tree));
cdc49211d87f implement cxTreeInsert family of functions
Mike Becker <universe@uap-core.de>
parents: 903
diff changeset
724 tree->root = node;
cdc49211d87f implement cxTreeInsert family of functions
Mike Becker <universe@uap-core.de>
parents: 903
diff changeset
725 tree->size = 1;
cdc49211d87f implement cxTreeInsert family of functions
Mike Becker <universe@uap-core.de>
parents: 903
diff changeset
726 return 0;
cdc49211d87f implement cxTreeInsert family of functions
Mike Becker <universe@uap-core.de>
parents: 903
diff changeset
727 }
cdc49211d87f implement cxTreeInsert family of functions
Mike Becker <universe@uap-core.de>
parents: 903
diff changeset
728 int result = cx_tree_add(data, tree->search, tree->node_create,
cdc49211d87f implement cxTreeInsert family of functions
Mike Becker <universe@uap-core.de>
parents: 903
diff changeset
729 tree, &node, tree->root, cx_tree_node_layout(tree));
cdc49211d87f implement cxTreeInsert family of functions
Mike Becker <universe@uap-core.de>
parents: 903
diff changeset
730 if (0 == result) {
cdc49211d87f implement cxTreeInsert family of functions
Mike Becker <universe@uap-core.de>
parents: 903
diff changeset
731 tree->size++;
cdc49211d87f implement cxTreeInsert family of functions
Mike Becker <universe@uap-core.de>
parents: 903
diff changeset
732 } else {
cdc49211d87f implement cxTreeInsert family of functions
Mike Becker <universe@uap-core.de>
parents: 903
diff changeset
733 cxFree(tree->allocator, node);
cdc49211d87f implement cxTreeInsert family of functions
Mike Becker <universe@uap-core.de>
parents: 903
diff changeset
734 }
cdc49211d87f implement cxTreeInsert family of functions
Mike Becker <universe@uap-core.de>
parents: 903
diff changeset
735 return result;
cdc49211d87f implement cxTreeInsert family of functions
Mike Becker <universe@uap-core.de>
parents: 903
diff changeset
736 }
cdc49211d87f implement cxTreeInsert family of functions
Mike Becker <universe@uap-core.de>
parents: 903
diff changeset
737
cdc49211d87f implement cxTreeInsert family of functions
Mike Becker <universe@uap-core.de>
parents: 903
diff changeset
738 static size_t cx_tree_default_insert_many(
cdc49211d87f implement cxTreeInsert family of functions
Mike Becker <universe@uap-core.de>
parents: 903
diff changeset
739 CxTree *tree,
cdc49211d87f implement cxTreeInsert family of functions
Mike Becker <universe@uap-core.de>
parents: 903
diff changeset
740 struct cx_iterator_base_s *iter,
cdc49211d87f implement cxTreeInsert family of functions
Mike Becker <universe@uap-core.de>
parents: 903
diff changeset
741 size_t n
cdc49211d87f implement cxTreeInsert family of functions
Mike Becker <universe@uap-core.de>
parents: 903
diff changeset
742 ) {
cdc49211d87f implement cxTreeInsert family of functions
Mike Becker <universe@uap-core.de>
parents: 903
diff changeset
743 size_t ins = 0;
cdc49211d87f implement cxTreeInsert family of functions
Mike Becker <universe@uap-core.de>
parents: 903
diff changeset
744 if (!iter->valid(iter)) return 0;
cdc49211d87f implement cxTreeInsert family of functions
Mike Becker <universe@uap-core.de>
parents: 903
diff changeset
745 if (tree->root == NULL) {
cdc49211d87f implement cxTreeInsert family of functions
Mike Becker <universe@uap-core.de>
parents: 903
diff changeset
746 // use the first element from the iter to create the root node
cdc49211d87f implement cxTreeInsert family of functions
Mike Becker <universe@uap-core.de>
parents: 903
diff changeset
747 void **eptr = iter->current(iter);
cdc49211d87f implement cxTreeInsert family of functions
Mike Becker <universe@uap-core.de>
parents: 903
diff changeset
748 void *node = tree->node_create(*eptr, tree);
cdc49211d87f implement cxTreeInsert family of functions
Mike Becker <universe@uap-core.de>
parents: 903
diff changeset
749 if (node == NULL) return 0;
cdc49211d87f implement cxTreeInsert family of functions
Mike Becker <universe@uap-core.de>
parents: 903
diff changeset
750 cx_tree_zero_pointers(node, cx_tree_node_layout(tree));
cdc49211d87f implement cxTreeInsert family of functions
Mike Becker <universe@uap-core.de>
parents: 903
diff changeset
751 tree->root = node;
cdc49211d87f implement cxTreeInsert family of functions
Mike Becker <universe@uap-core.de>
parents: 903
diff changeset
752 ins = 1;
cdc49211d87f implement cxTreeInsert family of functions
Mike Becker <universe@uap-core.de>
parents: 903
diff changeset
753 iter->next(iter);
cdc49211d87f implement cxTreeInsert family of functions
Mike Becker <universe@uap-core.de>
parents: 903
diff changeset
754 }
cdc49211d87f implement cxTreeInsert family of functions
Mike Becker <universe@uap-core.de>
parents: 903
diff changeset
755 void *failed;
cdc49211d87f implement cxTreeInsert family of functions
Mike Becker <universe@uap-core.de>
parents: 903
diff changeset
756 ins += cx_tree_add_iter(iter, n, tree->search, tree->node_create,
cdc49211d87f implement cxTreeInsert family of functions
Mike Becker <universe@uap-core.de>
parents: 903
diff changeset
757 tree, &failed, tree->root, cx_tree_node_layout(tree));
cdc49211d87f implement cxTreeInsert family of functions
Mike Becker <universe@uap-core.de>
parents: 903
diff changeset
758 tree->size += ins;
cdc49211d87f implement cxTreeInsert family of functions
Mike Becker <universe@uap-core.de>
parents: 903
diff changeset
759 if (ins < n) {
cdc49211d87f implement cxTreeInsert family of functions
Mike Becker <universe@uap-core.de>
parents: 903
diff changeset
760 cxFree(tree->allocator, failed);
cdc49211d87f implement cxTreeInsert family of functions
Mike Becker <universe@uap-core.de>
parents: 903
diff changeset
761 }
cdc49211d87f implement cxTreeInsert family of functions
Mike Becker <universe@uap-core.de>
parents: 903
diff changeset
762 return ins;
cdc49211d87f implement cxTreeInsert family of functions
Mike Becker <universe@uap-core.de>
parents: 903
diff changeset
763 }
cdc49211d87f implement cxTreeInsert family of functions
Mike Becker <universe@uap-core.de>
parents: 903
diff changeset
764
905
39aa4f106a71 complete implementation of remaining high level tree functions
Mike Becker <universe@uap-core.de>
parents: 904
diff changeset
765 static void *cx_tree_default_find(
39aa4f106a71 complete implementation of remaining high level tree functions
Mike Becker <universe@uap-core.de>
parents: 904
diff changeset
766 CxTree *tree,
39aa4f106a71 complete implementation of remaining high level tree functions
Mike Becker <universe@uap-core.de>
parents: 904
diff changeset
767 const void *subtree,
39aa4f106a71 complete implementation of remaining high level tree functions
Mike Becker <universe@uap-core.de>
parents: 904
diff changeset
768 const void *data
39aa4f106a71 complete implementation of remaining high level tree functions
Mike Becker <universe@uap-core.de>
parents: 904
diff changeset
769 ) {
39aa4f106a71 complete implementation of remaining high level tree functions
Mike Becker <universe@uap-core.de>
parents: 904
diff changeset
770 if (tree->root == NULL) return NULL;
39aa4f106a71 complete implementation of remaining high level tree functions
Mike Becker <universe@uap-core.de>
parents: 904
diff changeset
771
39aa4f106a71 complete implementation of remaining high level tree functions
Mike Becker <universe@uap-core.de>
parents: 904
diff changeset
772 void *found;
39aa4f106a71 complete implementation of remaining high level tree functions
Mike Becker <universe@uap-core.de>
parents: 904
diff changeset
773 if (0 == cx_tree_search_data(
39aa4f106a71 complete implementation of remaining high level tree functions
Mike Becker <universe@uap-core.de>
parents: 904
diff changeset
774 subtree,
39aa4f106a71 complete implementation of remaining high level tree functions
Mike Becker <universe@uap-core.de>
parents: 904
diff changeset
775 data,
39aa4f106a71 complete implementation of remaining high level tree functions
Mike Becker <universe@uap-core.de>
parents: 904
diff changeset
776 tree->search_data,
39aa4f106a71 complete implementation of remaining high level tree functions
Mike Becker <universe@uap-core.de>
parents: 904
diff changeset
777 &found,
39aa4f106a71 complete implementation of remaining high level tree functions
Mike Becker <universe@uap-core.de>
parents: 904
diff changeset
778 tree->loc_children,
39aa4f106a71 complete implementation of remaining high level tree functions
Mike Becker <universe@uap-core.de>
parents: 904
diff changeset
779 tree->loc_next
39aa4f106a71 complete implementation of remaining high level tree functions
Mike Becker <universe@uap-core.de>
parents: 904
diff changeset
780 )) {
39aa4f106a71 complete implementation of remaining high level tree functions
Mike Becker <universe@uap-core.de>
parents: 904
diff changeset
781 return found;
39aa4f106a71 complete implementation of remaining high level tree functions
Mike Becker <universe@uap-core.de>
parents: 904
diff changeset
782 } else {
39aa4f106a71 complete implementation of remaining high level tree functions
Mike Becker <universe@uap-core.de>
parents: 904
diff changeset
783 return NULL;
39aa4f106a71 complete implementation of remaining high level tree functions
Mike Becker <universe@uap-core.de>
parents: 904
diff changeset
784 }
39aa4f106a71 complete implementation of remaining high level tree functions
Mike Becker <universe@uap-core.de>
parents: 904
diff changeset
785 }
39aa4f106a71 complete implementation of remaining high level tree functions
Mike Becker <universe@uap-core.de>
parents: 904
diff changeset
786
902
5ed7f634f046 implement cxTreeCreate family of functions
Mike Becker <universe@uap-core.de>
parents: 901
diff changeset
787 static cx_tree_class cx_tree_default_class = {
5ed7f634f046 implement cxTreeCreate family of functions
Mike Becker <universe@uap-core.de>
parents: 901
diff changeset
788 cx_tree_default_destructor,
904
cdc49211d87f implement cxTreeInsert family of functions
Mike Becker <universe@uap-core.de>
parents: 903
diff changeset
789 cx_tree_default_insert_element,
cdc49211d87f implement cxTreeInsert family of functions
Mike Becker <universe@uap-core.de>
parents: 903
diff changeset
790 cx_tree_default_insert_many,
905
39aa4f106a71 complete implementation of remaining high level tree functions
Mike Becker <universe@uap-core.de>
parents: 904
diff changeset
791 cx_tree_default_find,
902
5ed7f634f046 implement cxTreeCreate family of functions
Mike Becker <universe@uap-core.de>
parents: 901
diff changeset
792 cx_tree_default_iterator,
5ed7f634f046 implement cxTreeCreate family of functions
Mike Becker <universe@uap-core.de>
parents: 901
diff changeset
793 cx_tree_default_visitor
5ed7f634f046 implement cxTreeCreate family of functions
Mike Becker <universe@uap-core.de>
parents: 901
diff changeset
794 };
5ed7f634f046 implement cxTreeCreate family of functions
Mike Becker <universe@uap-core.de>
parents: 901
diff changeset
795
5ed7f634f046 implement cxTreeCreate family of functions
Mike Becker <universe@uap-core.de>
parents: 901
diff changeset
796 CxTree *cxTreeCreate(
5ed7f634f046 implement cxTreeCreate family of functions
Mike Becker <universe@uap-core.de>
parents: 901
diff changeset
797 const CxAllocator *allocator,
5ed7f634f046 implement cxTreeCreate family of functions
Mike Becker <universe@uap-core.de>
parents: 901
diff changeset
798 cx_tree_node_create_func create_func,
5ed7f634f046 implement cxTreeCreate family of functions
Mike Becker <universe@uap-core.de>
parents: 901
diff changeset
799 cx_tree_search_func search_func,
905
39aa4f106a71 complete implementation of remaining high level tree functions
Mike Becker <universe@uap-core.de>
parents: 904
diff changeset
800 cx_tree_search_data_func search_data_func,
902
5ed7f634f046 implement cxTreeCreate family of functions
Mike Becker <universe@uap-core.de>
parents: 901
diff changeset
801 ptrdiff_t loc_parent,
5ed7f634f046 implement cxTreeCreate family of functions
Mike Becker <universe@uap-core.de>
parents: 901
diff changeset
802 ptrdiff_t loc_children,
5ed7f634f046 implement cxTreeCreate family of functions
Mike Becker <universe@uap-core.de>
parents: 901
diff changeset
803 ptrdiff_t loc_last_child,
5ed7f634f046 implement cxTreeCreate family of functions
Mike Becker <universe@uap-core.de>
parents: 901
diff changeset
804 ptrdiff_t loc_prev,
5ed7f634f046 implement cxTreeCreate family of functions
Mike Becker <universe@uap-core.de>
parents: 901
diff changeset
805 ptrdiff_t loc_next
5ed7f634f046 implement cxTreeCreate family of functions
Mike Becker <universe@uap-core.de>
parents: 901
diff changeset
806 ) {
5ed7f634f046 implement cxTreeCreate family of functions
Mike Becker <universe@uap-core.de>
parents: 901
diff changeset
807 CxTree *tree = cxMalloc(allocator, sizeof(CxTree));
5ed7f634f046 implement cxTreeCreate family of functions
Mike Becker <universe@uap-core.de>
parents: 901
diff changeset
808 if (tree == NULL) return NULL;
5ed7f634f046 implement cxTreeCreate family of functions
Mike Becker <universe@uap-core.de>
parents: 901
diff changeset
809
5ed7f634f046 implement cxTreeCreate family of functions
Mike Becker <universe@uap-core.de>
parents: 901
diff changeset
810 tree->cl = &cx_tree_default_class;
5ed7f634f046 implement cxTreeCreate family of functions
Mike Becker <universe@uap-core.de>
parents: 901
diff changeset
811 tree->allocator = allocator;
5ed7f634f046 implement cxTreeCreate family of functions
Mike Becker <universe@uap-core.de>
parents: 901
diff changeset
812 tree->node_create = create_func;
5ed7f634f046 implement cxTreeCreate family of functions
Mike Becker <universe@uap-core.de>
parents: 901
diff changeset
813 tree->search = search_func;
905
39aa4f106a71 complete implementation of remaining high level tree functions
Mike Becker <universe@uap-core.de>
parents: 904
diff changeset
814 tree->search_data = search_data_func;
902
5ed7f634f046 implement cxTreeCreate family of functions
Mike Becker <universe@uap-core.de>
parents: 901
diff changeset
815 tree->advanced_destructor = (cx_destructor_func2) cxFree;
5ed7f634f046 implement cxTreeCreate family of functions
Mike Becker <universe@uap-core.de>
parents: 901
diff changeset
816 tree->destructor_data = (void *) allocator;
5ed7f634f046 implement cxTreeCreate family of functions
Mike Becker <universe@uap-core.de>
parents: 901
diff changeset
817 tree->loc_parent = loc_parent;
5ed7f634f046 implement cxTreeCreate family of functions
Mike Becker <universe@uap-core.de>
parents: 901
diff changeset
818 tree->loc_children = loc_children;
5ed7f634f046 implement cxTreeCreate family of functions
Mike Becker <universe@uap-core.de>
parents: 901
diff changeset
819 tree->loc_last_child = loc_last_child;
5ed7f634f046 implement cxTreeCreate family of functions
Mike Becker <universe@uap-core.de>
parents: 901
diff changeset
820 tree->loc_prev = loc_prev;
5ed7f634f046 implement cxTreeCreate family of functions
Mike Becker <universe@uap-core.de>
parents: 901
diff changeset
821 tree->loc_next = loc_next;
5ed7f634f046 implement cxTreeCreate family of functions
Mike Becker <universe@uap-core.de>
parents: 901
diff changeset
822 tree->root = NULL;
5ed7f634f046 implement cxTreeCreate family of functions
Mike Becker <universe@uap-core.de>
parents: 901
diff changeset
823 tree->size = 0;
5ed7f634f046 implement cxTreeCreate family of functions
Mike Becker <universe@uap-core.de>
parents: 901
diff changeset
824
5ed7f634f046 implement cxTreeCreate family of functions
Mike Becker <universe@uap-core.de>
parents: 901
diff changeset
825 return tree;
5ed7f634f046 implement cxTreeCreate family of functions
Mike Becker <universe@uap-core.de>
parents: 901
diff changeset
826 }
5ed7f634f046 implement cxTreeCreate family of functions
Mike Becker <universe@uap-core.de>
parents: 901
diff changeset
827
5ed7f634f046 implement cxTreeCreate family of functions
Mike Becker <universe@uap-core.de>
parents: 901
diff changeset
828 CxTree *cxTreeCreateWrapped(
905
39aa4f106a71 complete implementation of remaining high level tree functions
Mike Becker <universe@uap-core.de>
parents: 904
diff changeset
829 const CxAllocator *allocator,
902
5ed7f634f046 implement cxTreeCreate family of functions
Mike Becker <universe@uap-core.de>
parents: 901
diff changeset
830 void *root,
5ed7f634f046 implement cxTreeCreate family of functions
Mike Becker <universe@uap-core.de>
parents: 901
diff changeset
831 ptrdiff_t loc_parent,
5ed7f634f046 implement cxTreeCreate family of functions
Mike Becker <universe@uap-core.de>
parents: 901
diff changeset
832 ptrdiff_t loc_children,
5ed7f634f046 implement cxTreeCreate family of functions
Mike Becker <universe@uap-core.de>
parents: 901
diff changeset
833 ptrdiff_t loc_last_child,
5ed7f634f046 implement cxTreeCreate family of functions
Mike Becker <universe@uap-core.de>
parents: 901
diff changeset
834 ptrdiff_t loc_prev,
5ed7f634f046 implement cxTreeCreate family of functions
Mike Becker <universe@uap-core.de>
parents: 901
diff changeset
835 ptrdiff_t loc_next
5ed7f634f046 implement cxTreeCreate family of functions
Mike Becker <universe@uap-core.de>
parents: 901
diff changeset
836 ) {
905
39aa4f106a71 complete implementation of remaining high level tree functions
Mike Becker <universe@uap-core.de>
parents: 904
diff changeset
837 CxTree *tree = cxMalloc(allocator, sizeof(CxTree));
902
5ed7f634f046 implement cxTreeCreate family of functions
Mike Becker <universe@uap-core.de>
parents: 901
diff changeset
838 if (tree == NULL) return NULL;
5ed7f634f046 implement cxTreeCreate family of functions
Mike Becker <universe@uap-core.de>
parents: 901
diff changeset
839
5ed7f634f046 implement cxTreeCreate family of functions
Mike Becker <universe@uap-core.de>
parents: 901
diff changeset
840 tree->cl = &cx_tree_default_class;
5ed7f634f046 implement cxTreeCreate family of functions
Mike Becker <universe@uap-core.de>
parents: 901
diff changeset
841 // set the allocator anyway, just in case...
905
39aa4f106a71 complete implementation of remaining high level tree functions
Mike Becker <universe@uap-core.de>
parents: 904
diff changeset
842 tree->allocator = allocator;
902
5ed7f634f046 implement cxTreeCreate family of functions
Mike Becker <universe@uap-core.de>
parents: 901
diff changeset
843 tree->node_create = NULL;
5ed7f634f046 implement cxTreeCreate family of functions
Mike Becker <universe@uap-core.de>
parents: 901
diff changeset
844 tree->search = NULL;
905
39aa4f106a71 complete implementation of remaining high level tree functions
Mike Becker <universe@uap-core.de>
parents: 904
diff changeset
845 tree->search_data = NULL;
39aa4f106a71 complete implementation of remaining high level tree functions
Mike Becker <universe@uap-core.de>
parents: 904
diff changeset
846 tree->simple_destructor = NULL;
902
5ed7f634f046 implement cxTreeCreate family of functions
Mike Becker <universe@uap-core.de>
parents: 901
diff changeset
847 tree->advanced_destructor = NULL;
5ed7f634f046 implement cxTreeCreate family of functions
Mike Becker <universe@uap-core.de>
parents: 901
diff changeset
848 tree->destructor_data = NULL;
5ed7f634f046 implement cxTreeCreate family of functions
Mike Becker <universe@uap-core.de>
parents: 901
diff changeset
849 tree->loc_parent = loc_parent;
5ed7f634f046 implement cxTreeCreate family of functions
Mike Becker <universe@uap-core.de>
parents: 901
diff changeset
850 tree->loc_children = loc_children;
5ed7f634f046 implement cxTreeCreate family of functions
Mike Becker <universe@uap-core.de>
parents: 901
diff changeset
851 tree->loc_last_child = loc_last_child;
5ed7f634f046 implement cxTreeCreate family of functions
Mike Becker <universe@uap-core.de>
parents: 901
diff changeset
852 tree->loc_prev = loc_prev;
5ed7f634f046 implement cxTreeCreate family of functions
Mike Becker <universe@uap-core.de>
parents: 901
diff changeset
853 tree->loc_next = loc_next;
5ed7f634f046 implement cxTreeCreate family of functions
Mike Becker <universe@uap-core.de>
parents: 901
diff changeset
854 tree->root = root;
5ed7f634f046 implement cxTreeCreate family of functions
Mike Becker <universe@uap-core.de>
parents: 901
diff changeset
855 tree->size = cxTreeSubtreeSize(tree, root);
5ed7f634f046 implement cxTreeCreate family of functions
Mike Becker <universe@uap-core.de>
parents: 901
diff changeset
856 return tree;
5ed7f634f046 implement cxTreeCreate family of functions
Mike Becker <universe@uap-core.de>
parents: 901
diff changeset
857 }
901
109567325fe7 add functions to link/unlink nodes manually
Mike Becker <universe@uap-core.de>
parents: 893
diff changeset
858
109567325fe7 add functions to link/unlink nodes manually
Mike Becker <universe@uap-core.de>
parents: 893
diff changeset
859 int cxTreeAddChild(
109567325fe7 add functions to link/unlink nodes manually
Mike Becker <universe@uap-core.de>
parents: 893
diff changeset
860 CxTree *tree,
109567325fe7 add functions to link/unlink nodes manually
Mike Becker <universe@uap-core.de>
parents: 893
diff changeset
861 void *parent,
109567325fe7 add functions to link/unlink nodes manually
Mike Becker <universe@uap-core.de>
parents: 893
diff changeset
862 const void *data) {
109567325fe7 add functions to link/unlink nodes manually
Mike Becker <universe@uap-core.de>
parents: 893
diff changeset
863 void *node = tree->node_create(data, tree);
109567325fe7 add functions to link/unlink nodes manually
Mike Becker <universe@uap-core.de>
parents: 893
diff changeset
864 if (node == NULL) return 1;
109567325fe7 add functions to link/unlink nodes manually
Mike Becker <universe@uap-core.de>
parents: 893
diff changeset
865 cx_tree_zero_pointers(node, cx_tree_node_layout(tree));
109567325fe7 add functions to link/unlink nodes manually
Mike Becker <universe@uap-core.de>
parents: 893
diff changeset
866 cx_tree_link(parent, node, cx_tree_node_layout(tree));
109567325fe7 add functions to link/unlink nodes manually
Mike Becker <universe@uap-core.de>
parents: 893
diff changeset
867 tree->size++;
109567325fe7 add functions to link/unlink nodes manually
Mike Becker <universe@uap-core.de>
parents: 893
diff changeset
868 return 0;
109567325fe7 add functions to link/unlink nodes manually
Mike Becker <universe@uap-core.de>
parents: 893
diff changeset
869 }
902
5ed7f634f046 implement cxTreeCreate family of functions
Mike Becker <universe@uap-core.de>
parents: 901
diff changeset
870
5ed7f634f046 implement cxTreeCreate family of functions
Mike Becker <universe@uap-core.de>
parents: 901
diff changeset
871 size_t cxTreeSubtreeSize(CxTree *tree, void *subtree_root) {
5ed7f634f046 implement cxTreeCreate family of functions
Mike Becker <universe@uap-core.de>
parents: 901
diff changeset
872 CxTreeVisitor visitor = cx_tree_visitor(
5ed7f634f046 implement cxTreeCreate family of functions
Mike Becker <universe@uap-core.de>
parents: 901
diff changeset
873 subtree_root,
5ed7f634f046 implement cxTreeCreate family of functions
Mike Becker <universe@uap-core.de>
parents: 901
diff changeset
874 tree->loc_children,
5ed7f634f046 implement cxTreeCreate family of functions
Mike Becker <universe@uap-core.de>
parents: 901
diff changeset
875 tree->loc_next
5ed7f634f046 implement cxTreeCreate family of functions
Mike Becker <universe@uap-core.de>
parents: 901
diff changeset
876 );
5ed7f634f046 implement cxTreeCreate family of functions
Mike Becker <universe@uap-core.de>
parents: 901
diff changeset
877 while (cxIteratorValid(visitor)) {
5ed7f634f046 implement cxTreeCreate family of functions
Mike Becker <universe@uap-core.de>
parents: 901
diff changeset
878 cxIteratorNext(visitor);
5ed7f634f046 implement cxTreeCreate family of functions
Mike Becker <universe@uap-core.de>
parents: 901
diff changeset
879 }
5ed7f634f046 implement cxTreeCreate family of functions
Mike Becker <universe@uap-core.de>
parents: 901
diff changeset
880 return visitor.counter;
5ed7f634f046 implement cxTreeCreate family of functions
Mike Becker <universe@uap-core.de>
parents: 901
diff changeset
881 }
903
a018f5916d3b add cxTreeSubtreeDepth()
Mike Becker <universe@uap-core.de>
parents: 902
diff changeset
882
a018f5916d3b add cxTreeSubtreeDepth()
Mike Becker <universe@uap-core.de>
parents: 902
diff changeset
883 size_t cxTreeSubtreeDepth(CxTree *tree, void *subtree_root) {
a018f5916d3b add cxTreeSubtreeDepth()
Mike Becker <universe@uap-core.de>
parents: 902
diff changeset
884 CxTreeVisitor visitor = cx_tree_visitor(
a018f5916d3b add cxTreeSubtreeDepth()
Mike Becker <universe@uap-core.de>
parents: 902
diff changeset
885 subtree_root,
a018f5916d3b add cxTreeSubtreeDepth()
Mike Becker <universe@uap-core.de>
parents: 902
diff changeset
886 tree->loc_children,
a018f5916d3b add cxTreeSubtreeDepth()
Mike Becker <universe@uap-core.de>
parents: 902
diff changeset
887 tree->loc_next
a018f5916d3b add cxTreeSubtreeDepth()
Mike Becker <universe@uap-core.de>
parents: 902
diff changeset
888 );
a018f5916d3b add cxTreeSubtreeDepth()
Mike Becker <universe@uap-core.de>
parents: 902
diff changeset
889 while (cxIteratorValid(visitor)) {
a018f5916d3b add cxTreeSubtreeDepth()
Mike Becker <universe@uap-core.de>
parents: 902
diff changeset
890 cxIteratorNext(visitor);
a018f5916d3b add cxTreeSubtreeDepth()
Mike Becker <universe@uap-core.de>
parents: 902
diff changeset
891 }
a018f5916d3b add cxTreeSubtreeDepth()
Mike Becker <universe@uap-core.de>
parents: 902
diff changeset
892 return visitor.depth;
a018f5916d3b add cxTreeSubtreeDepth()
Mike Becker <universe@uap-core.de>
parents: 902
diff changeset
893 }
905
39aa4f106a71 complete implementation of remaining high level tree functions
Mike Becker <universe@uap-core.de>
parents: 904
diff changeset
894
39aa4f106a71 complete implementation of remaining high level tree functions
Mike Becker <universe@uap-core.de>
parents: 904
diff changeset
895 size_t cxTreeDepth(CxTree *tree) {
39aa4f106a71 complete implementation of remaining high level tree functions
Mike Becker <universe@uap-core.de>
parents: 904
diff changeset
896 CxTreeVisitor visitor = tree->cl->visitor(tree);
39aa4f106a71 complete implementation of remaining high level tree functions
Mike Becker <universe@uap-core.de>
parents: 904
diff changeset
897 while (cxIteratorValid(visitor)) {
39aa4f106a71 complete implementation of remaining high level tree functions
Mike Becker <universe@uap-core.de>
parents: 904
diff changeset
898 cxIteratorNext(visitor);
39aa4f106a71 complete implementation of remaining high level tree functions
Mike Becker <universe@uap-core.de>
parents: 904
diff changeset
899 }
39aa4f106a71 complete implementation of remaining high level tree functions
Mike Becker <universe@uap-core.de>
parents: 904
diff changeset
900 return visitor.depth;
39aa4f106a71 complete implementation of remaining high level tree functions
Mike Becker <universe@uap-core.de>
parents: 904
diff changeset
901 }
39aa4f106a71 complete implementation of remaining high level tree functions
Mike Becker <universe@uap-core.de>
parents: 904
diff changeset
902
39aa4f106a71 complete implementation of remaining high level tree functions
Mike Becker <universe@uap-core.de>
parents: 904
diff changeset
903 void cxTreeRemove(CxTree *tree, void *node) {
39aa4f106a71 complete implementation of remaining high level tree functions
Mike Becker <universe@uap-core.de>
parents: 904
diff changeset
904 size_t subtree_size = cxTreeSubtreeSize(tree, node);
39aa4f106a71 complete implementation of remaining high level tree functions
Mike Becker <universe@uap-core.de>
parents: 904
diff changeset
905 cx_tree_unlink(node, cx_tree_node_layout(tree));
39aa4f106a71 complete implementation of remaining high level tree functions
Mike Becker <universe@uap-core.de>
parents: 904
diff changeset
906 tree->size -= subtree_size;
39aa4f106a71 complete implementation of remaining high level tree functions
Mike Becker <universe@uap-core.de>
parents: 904
diff changeset
907 }

mercurial