Sat, 17 Aug 2024 11:14:39 +0200
merge changes from default branch
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 | * \file tree.h |
425234b05dff
add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
30 | * \brief Interface for tree implementations. |
425234b05dff
add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
31 | * \author Mike Becker |
425234b05dff
add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
32 | * \author Olaf Wintermann |
425234b05dff
add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
33 | * \copyright 2-Clause BSD License |
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 | |
425234b05dff
add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
36 | #ifndef UCX_TREE_H |
425234b05dff
add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
37 | #define UCX_TREE_H |
425234b05dff
add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
38 | |
425234b05dff
add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
39 | #include "common.h" |
425234b05dff
add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
40 | |
827
13b40a598d16
first draft of a tree iterator
Mike Becker <universe@uap-core.de>
parents:
826
diff
changeset
|
41 | #include "iterator.h" |
13b40a598d16
first draft of a tree iterator
Mike Becker <universe@uap-core.de>
parents:
826
diff
changeset
|
42 | |
816
425234b05dff
add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
43 | #ifdef __cplusplus |
425234b05dff
add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
44 | extern "C" { |
425234b05dff
add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
45 | #endif |
425234b05dff
add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
46 | |
827
13b40a598d16
first draft of a tree iterator
Mike Becker <universe@uap-core.de>
parents:
826
diff
changeset
|
47 | /** |
845 | 48 | * A depth-first tree iterator. |
827
13b40a598d16
first draft of a tree iterator
Mike Becker <universe@uap-core.de>
parents:
826
diff
changeset
|
49 | * |
859 | 50 | * This iterator is not position-aware in a strict sense, as it does not assume |
51 | * a particular order of elements in the tree. However, the iterator keeps track | |
52 | * of the number of nodes it has passed in a counter variable. | |
827
13b40a598d16
first draft of a tree iterator
Mike Becker <universe@uap-core.de>
parents:
826
diff
changeset
|
53 | * Each node, regardless of the number of passes, is counted only once. |
13b40a598d16
first draft of a tree iterator
Mike Becker <universe@uap-core.de>
parents:
826
diff
changeset
|
54 | * |
859 | 55 | * @note Objects that are pointed to by an iterator are mutable through that |
56 | * iterator. However, if the | |
57 | * underlying data structure is mutated by other means than this iterator (e.g. | |
58 | * elements added or removed), the iterator becomes invalid (regardless of what | |
59 | * cxIteratorValid() returns). | |
827
13b40a598d16
first draft of a tree iterator
Mike Becker <universe@uap-core.de>
parents:
826
diff
changeset
|
60 | * |
13b40a598d16
first draft of a tree iterator
Mike Becker <universe@uap-core.de>
parents:
826
diff
changeset
|
61 | * @see CxIterator |
13b40a598d16
first draft of a tree iterator
Mike Becker <universe@uap-core.de>
parents:
826
diff
changeset
|
62 | */ |
13b40a598d16
first draft of a tree iterator
Mike Becker <universe@uap-core.de>
parents:
826
diff
changeset
|
63 | typedef struct cx_tree_iterator_s { |
854
fe0d69d72bcd
fix members inherited by macro or include are not documented
Mike Becker <universe@uap-core.de>
parents:
853
diff
changeset
|
64 | /** |
fe0d69d72bcd
fix members inherited by macro or include are not documented
Mike Becker <universe@uap-core.de>
parents:
853
diff
changeset
|
65 | * Base members. |
fe0d69d72bcd
fix members inherited by macro or include are not documented
Mike Becker <universe@uap-core.de>
parents:
853
diff
changeset
|
66 | */ |
fe0d69d72bcd
fix members inherited by macro or include are not documented
Mike Becker <universe@uap-core.de>
parents:
853
diff
changeset
|
67 | CX_ITERATOR_BASE; |
827
13b40a598d16
first draft of a tree iterator
Mike Becker <universe@uap-core.de>
parents:
826
diff
changeset
|
68 | /** |
848
6456036bbb37
implement tree continue - fixes #376
Mike Becker <universe@uap-core.de>
parents:
845
diff
changeset
|
69 | * Indicates whether the subtree below the current node shall be skipped. |
6456036bbb37
implement tree continue - fixes #376
Mike Becker <universe@uap-core.de>
parents:
845
diff
changeset
|
70 | */ |
6456036bbb37
implement tree continue - fixes #376
Mike Becker <universe@uap-core.de>
parents:
845
diff
changeset
|
71 | bool skip; |
6456036bbb37
implement tree continue - fixes #376
Mike Becker <universe@uap-core.de>
parents:
845
diff
changeset
|
72 | /** |
833
5c926801f052
vastly simplify tree iterators and add test for creating them
Mike Becker <universe@uap-core.de>
parents:
830
diff
changeset
|
73 | * Set to true, when the iterator shall visit a node again |
5c926801f052
vastly simplify tree iterators and add test for creating them
Mike Becker <universe@uap-core.de>
parents:
830
diff
changeset
|
74 | * when all it's children have been processed. |
827
13b40a598d16
first draft of a tree iterator
Mike Becker <universe@uap-core.de>
parents:
826
diff
changeset
|
75 | */ |
833
5c926801f052
vastly simplify tree iterators and add test for creating them
Mike Becker <universe@uap-core.de>
parents:
830
diff
changeset
|
76 | bool visit_on_exit; |
827
13b40a598d16
first draft of a tree iterator
Mike Becker <universe@uap-core.de>
parents:
826
diff
changeset
|
77 | /** |
833
5c926801f052
vastly simplify tree iterators and add test for creating them
Mike Becker <universe@uap-core.de>
parents:
830
diff
changeset
|
78 | * True, if this iterator is currently leaving the node. |
827
13b40a598d16
first draft of a tree iterator
Mike Becker <universe@uap-core.de>
parents:
826
diff
changeset
|
79 | */ |
833
5c926801f052
vastly simplify tree iterators and add test for creating them
Mike Becker <universe@uap-core.de>
parents:
830
diff
changeset
|
80 | bool exiting; |
827
13b40a598d16
first draft of a tree iterator
Mike Becker <universe@uap-core.de>
parents:
826
diff
changeset
|
81 | /** |
13b40a598d16
first draft of a tree iterator
Mike Becker <universe@uap-core.de>
parents:
826
diff
changeset
|
82 | * Offset in the node struct for the children linked list. |
13b40a598d16
first draft of a tree iterator
Mike Becker <universe@uap-core.de>
parents:
826
diff
changeset
|
83 | */ |
845 | 84 | ptrdiff_t loc_children; |
827
13b40a598d16
first draft of a tree iterator
Mike Becker <universe@uap-core.de>
parents:
826
diff
changeset
|
85 | /** |
13b40a598d16
first draft of a tree iterator
Mike Becker <universe@uap-core.de>
parents:
826
diff
changeset
|
86 | * Offset in the node struct for the next pointer. |
13b40a598d16
first draft of a tree iterator
Mike Becker <universe@uap-core.de>
parents:
826
diff
changeset
|
87 | */ |
845 | 88 | ptrdiff_t loc_next; |
827
13b40a598d16
first draft of a tree iterator
Mike Becker <universe@uap-core.de>
parents:
826
diff
changeset
|
89 | /** |
13b40a598d16
first draft of a tree iterator
Mike Becker <universe@uap-core.de>
parents:
826
diff
changeset
|
90 | * The total number of distinct nodes that have been passed so far. |
13b40a598d16
first draft of a tree iterator
Mike Becker <universe@uap-core.de>
parents:
826
diff
changeset
|
91 | */ |
13b40a598d16
first draft of a tree iterator
Mike Becker <universe@uap-core.de>
parents:
826
diff
changeset
|
92 | size_t counter; |
13b40a598d16
first draft of a tree iterator
Mike Becker <universe@uap-core.de>
parents:
826
diff
changeset
|
93 | /** |
13b40a598d16
first draft of a tree iterator
Mike Becker <universe@uap-core.de>
parents:
826
diff
changeset
|
94 | * The currently observed node. |
13b40a598d16
first draft of a tree iterator
Mike Becker <universe@uap-core.de>
parents:
826
diff
changeset
|
95 | * |
13b40a598d16
first draft of a tree iterator
Mike Becker <universe@uap-core.de>
parents:
826
diff
changeset
|
96 | * This is the same what cxIteratorCurrent() would return. |
13b40a598d16
first draft of a tree iterator
Mike Becker <universe@uap-core.de>
parents:
826
diff
changeset
|
97 | */ |
13b40a598d16
first draft of a tree iterator
Mike Becker <universe@uap-core.de>
parents:
826
diff
changeset
|
98 | void *node; |
13b40a598d16
first draft of a tree iterator
Mike Becker <universe@uap-core.de>
parents:
826
diff
changeset
|
99 | /** |
840
4f02995ce44e
allow freeing tree nodes on exit - fixes #377
Mike Becker <universe@uap-core.de>
parents:
835
diff
changeset
|
100 | * Stores a copy of the next pointer of the visited node. |
4f02995ce44e
allow freeing tree nodes on exit - fixes #377
Mike Becker <universe@uap-core.de>
parents:
835
diff
changeset
|
101 | * Allows freeing a node on exit without corrupting the iteration. |
4f02995ce44e
allow freeing tree nodes on exit - fixes #377
Mike Becker <universe@uap-core.de>
parents:
835
diff
changeset
|
102 | */ |
853
d4baf4dd55c3
simplify iterator structures
Mike Becker <universe@uap-core.de>
parents:
848
diff
changeset
|
103 | void *node_next; |
840
4f02995ce44e
allow freeing tree nodes on exit - fixes #377
Mike Becker <universe@uap-core.de>
parents:
835
diff
changeset
|
104 | /** |
827
13b40a598d16
first draft of a tree iterator
Mike Becker <universe@uap-core.de>
parents:
826
diff
changeset
|
105 | * Internal stack. |
13b40a598d16
first draft of a tree iterator
Mike Becker <universe@uap-core.de>
parents:
826
diff
changeset
|
106 | * Will be automatically freed once the iterator becomes invalid. |
13b40a598d16
first draft of a tree iterator
Mike Becker <universe@uap-core.de>
parents:
826
diff
changeset
|
107 | * |
13b40a598d16
first draft of a tree iterator
Mike Becker <universe@uap-core.de>
parents:
826
diff
changeset
|
108 | * If you want to discard the iterator before, you need to manually |
13b40a598d16
first draft of a tree iterator
Mike Becker <universe@uap-core.de>
parents:
826
diff
changeset
|
109 | * call cxTreeIteratorDispose(). |
13b40a598d16
first draft of a tree iterator
Mike Becker <universe@uap-core.de>
parents:
826
diff
changeset
|
110 | */ |
13b40a598d16
first draft of a tree iterator
Mike Becker <universe@uap-core.de>
parents:
826
diff
changeset
|
111 | void **stack; |
828
88fa3381206d
improve tree iterator struct and add signature for a function that can create an iterator
Mike Becker <universe@uap-core.de>
parents:
827
diff
changeset
|
112 | /** |
88fa3381206d
improve tree iterator struct and add signature for a function that can create an iterator
Mike Becker <universe@uap-core.de>
parents:
827
diff
changeset
|
113 | * Internal capacity of the stack. |
88fa3381206d
improve tree iterator struct and add signature for a function that can create an iterator
Mike Becker <universe@uap-core.de>
parents:
827
diff
changeset
|
114 | */ |
88fa3381206d
improve tree iterator struct and add signature for a function that can create an iterator
Mike Becker <universe@uap-core.de>
parents:
827
diff
changeset
|
115 | size_t stack_capacity; |
833
5c926801f052
vastly simplify tree iterators and add test for creating them
Mike Becker <universe@uap-core.de>
parents:
830
diff
changeset
|
116 | union { |
5c926801f052
vastly simplify tree iterators and add test for creating them
Mike Becker <universe@uap-core.de>
parents:
830
diff
changeset
|
117 | /** |
5c926801f052
vastly simplify tree iterators and add test for creating them
Mike Becker <universe@uap-core.de>
parents:
830
diff
changeset
|
118 | * Internal stack size. |
5c926801f052
vastly simplify tree iterators and add test for creating them
Mike Becker <universe@uap-core.de>
parents:
830
diff
changeset
|
119 | */ |
5c926801f052
vastly simplify tree iterators and add test for creating them
Mike Becker <universe@uap-core.de>
parents:
830
diff
changeset
|
120 | size_t stack_size; |
5c926801f052
vastly simplify tree iterators and add test for creating them
Mike Becker <universe@uap-core.de>
parents:
830
diff
changeset
|
121 | /** |
5c926801f052
vastly simplify tree iterators and add test for creating them
Mike Becker <universe@uap-core.de>
parents:
830
diff
changeset
|
122 | * The current depth in the tree. |
5c926801f052
vastly simplify tree iterators and add test for creating them
Mike Becker <universe@uap-core.de>
parents:
830
diff
changeset
|
123 | */ |
5c926801f052
vastly simplify tree iterators and add test for creating them
Mike Becker <universe@uap-core.de>
parents:
830
diff
changeset
|
124 | size_t depth; |
5c926801f052
vastly simplify tree iterators and add test for creating them
Mike Becker <universe@uap-core.de>
parents:
830
diff
changeset
|
125 | }; |
827
13b40a598d16
first draft of a tree iterator
Mike Becker <universe@uap-core.de>
parents:
826
diff
changeset
|
126 | } CxTreeIterator; |
13b40a598d16
first draft of a tree iterator
Mike Becker <universe@uap-core.de>
parents:
826
diff
changeset
|
127 | |
13b40a598d16
first draft of a tree iterator
Mike Becker <universe@uap-core.de>
parents:
826
diff
changeset
|
128 | /** |
845 | 129 | * An element in a visitor queue. |
130 | */ | |
131 | struct cx_tree_visitor_queue_s { | |
132 | /** | |
133 | * The tree node to visit. | |
134 | */ | |
135 | void *node; | |
136 | /** | |
137 | * The depth of the node. | |
138 | */ | |
139 | size_t depth; | |
140 | /** | |
141 | * The next element in the queue or \c NULL. | |
142 | */ | |
143 | struct cx_tree_visitor_queue_s *next; | |
144 | }; | |
145 | ||
146 | /** | |
147 | * A breadth-first tree iterator. | |
148 | * | |
859 | 149 | * This iterator needs to maintain a visitor queue that will be automatically |
150 | * freed once the iterator becomes invalid. | |
151 | * If you want to discard the iterator before, you MUST manually call | |
152 | * cxTreeVisitorDispose(). | |
845 | 153 | * |
859 | 154 | * This iterator is not position-aware in a strict sense, as it does not assume |
155 | * a particular order of elements in the tree. However, the iterator keeps track | |
156 | * of the number of nodes it has passed in a counter variable. | |
845 | 157 | * Each node, regardless of the number of passes, is counted only once. |
158 | * | |
859 | 159 | * @note Objects that are pointed to by an iterator are mutable through that |
160 | * iterator. However, if the | |
161 | * underlying data structure is mutated by other means than this iterator (e.g. | |
162 | * elements added or removed), the iterator becomes invalid (regardless of what | |
163 | * cxIteratorValid() returns). | |
845 | 164 | * |
165 | * @see CxIterator | |
166 | */ | |
167 | typedef struct cx_tree_visitor_s { | |
854
fe0d69d72bcd
fix members inherited by macro or include are not documented
Mike Becker <universe@uap-core.de>
parents:
853
diff
changeset
|
168 | /** |
fe0d69d72bcd
fix members inherited by macro or include are not documented
Mike Becker <universe@uap-core.de>
parents:
853
diff
changeset
|
169 | * Base members. |
fe0d69d72bcd
fix members inherited by macro or include are not documented
Mike Becker <universe@uap-core.de>
parents:
853
diff
changeset
|
170 | */ |
fe0d69d72bcd
fix members inherited by macro or include are not documented
Mike Becker <universe@uap-core.de>
parents:
853
diff
changeset
|
171 | CX_ITERATOR_BASE; |
845 | 172 | /** |
848
6456036bbb37
implement tree continue - fixes #376
Mike Becker <universe@uap-core.de>
parents:
845
diff
changeset
|
173 | * Indicates whether the subtree below the current node shall be skipped. |
6456036bbb37
implement tree continue - fixes #376
Mike Becker <universe@uap-core.de>
parents:
845
diff
changeset
|
174 | */ |
6456036bbb37
implement tree continue - fixes #376
Mike Becker <universe@uap-core.de>
parents:
845
diff
changeset
|
175 | bool skip; |
6456036bbb37
implement tree continue - fixes #376
Mike Becker <universe@uap-core.de>
parents:
845
diff
changeset
|
176 | /** |
845 | 177 | * Offset in the node struct for the children linked list. |
178 | */ | |
179 | ptrdiff_t loc_children; | |
180 | /** | |
181 | * Offset in the node struct for the next pointer. | |
182 | */ | |
183 | ptrdiff_t loc_next; | |
184 | /** | |
185 | * The total number of distinct nodes that have been passed so far. | |
186 | */ | |
187 | size_t counter; | |
188 | /** | |
189 | * The currently observed node. | |
190 | * | |
191 | * This is the same what cxIteratorCurrent() would return. | |
192 | */ | |
193 | void *node; | |
194 | /** | |
195 | * The current depth in the tree. | |
196 | */ | |
197 | size_t depth; | |
198 | /** | |
199 | * The next element in the visitor queue. | |
200 | */ | |
201 | struct cx_tree_visitor_queue_s *queue_next; | |
202 | /** | |
203 | * The last element in the visitor queue. | |
204 | */ | |
205 | struct cx_tree_visitor_queue_s *queue_last; | |
206 | } CxTreeVisitor; | |
207 | ||
208 | /** | |
827
13b40a598d16
first draft of a tree iterator
Mike Becker <universe@uap-core.de>
parents:
826
diff
changeset
|
209 | * Releases internal memory of the given tree iterator. |
13b40a598d16
first draft of a tree iterator
Mike Becker <universe@uap-core.de>
parents:
826
diff
changeset
|
210 | * @param iter the iterator |
13b40a598d16
first draft of a tree iterator
Mike Becker <universe@uap-core.de>
parents:
826
diff
changeset
|
211 | */ |
845 | 212 | __attribute__((__nonnull__)) |
827
13b40a598d16
first draft of a tree iterator
Mike Becker <universe@uap-core.de>
parents:
826
diff
changeset
|
213 | static inline void cxTreeIteratorDispose(CxTreeIterator *iter) { |
13b40a598d16
first draft of a tree iterator
Mike Becker <universe@uap-core.de>
parents:
826
diff
changeset
|
214 | free(iter->stack); |
835
13068743197f
set tree iterator stack pointer to NULL on dispose to avoid accidental double-frees
Mike Becker <universe@uap-core.de>
parents:
833
diff
changeset
|
215 | iter->stack = NULL; |
827
13b40a598d16
first draft of a tree iterator
Mike Becker <universe@uap-core.de>
parents:
826
diff
changeset
|
216 | } |
816
425234b05dff
add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
217 | |
822
e2243453127f
add code documentation for tree functions
Mike Becker <universe@uap-core.de>
parents:
816
diff
changeset
|
218 | /** |
845 | 219 | * Releases internal memory of the given tree visitor. |
220 | * @param visitor the visitor | |
221 | */ | |
222 | __attribute__((__nonnull__)) | |
223 | static inline void cxTreeVisitorDispose(CxTreeVisitor *visitor) { | |
224 | struct cx_tree_visitor_queue_s *q = visitor->queue_next; | |
225 | while (q != NULL) { | |
226 | struct cx_tree_visitor_queue_s *next = q->next; | |
227 | free(q); | |
228 | q = next; | |
229 | } | |
230 | } | |
231 | ||
232 | /** | |
848
6456036bbb37
implement tree continue - fixes #376
Mike Becker <universe@uap-core.de>
parents:
845
diff
changeset
|
233 | * Advises the iterator to skip the subtree below the current node and |
6456036bbb37
implement tree continue - fixes #376
Mike Becker <universe@uap-core.de>
parents:
845
diff
changeset
|
234 | * also continues the current loop. |
6456036bbb37
implement tree continue - fixes #376
Mike Becker <universe@uap-core.de>
parents:
845
diff
changeset
|
235 | * |
6456036bbb37
implement tree continue - fixes #376
Mike Becker <universe@uap-core.de>
parents:
845
diff
changeset
|
236 | * @param iterator the iterator |
6456036bbb37
implement tree continue - fixes #376
Mike Becker <universe@uap-core.de>
parents:
845
diff
changeset
|
237 | */ |
6456036bbb37
implement tree continue - fixes #376
Mike Becker <universe@uap-core.de>
parents:
845
diff
changeset
|
238 | #define cxTreeIteratorContinue(iterator) (iterator).skip = true; continue |
6456036bbb37
implement tree continue - fixes #376
Mike Becker <universe@uap-core.de>
parents:
845
diff
changeset
|
239 | |
6456036bbb37
implement tree continue - fixes #376
Mike Becker <universe@uap-core.de>
parents:
845
diff
changeset
|
240 | /** |
6456036bbb37
implement tree continue - fixes #376
Mike Becker <universe@uap-core.de>
parents:
845
diff
changeset
|
241 | * Advises the visitor to skip the subtree below the current node and |
6456036bbb37
implement tree continue - fixes #376
Mike Becker <universe@uap-core.de>
parents:
845
diff
changeset
|
242 | * also continues the current loop. |
6456036bbb37
implement tree continue - fixes #376
Mike Becker <universe@uap-core.de>
parents:
845
diff
changeset
|
243 | * |
6456036bbb37
implement tree continue - fixes #376
Mike Becker <universe@uap-core.de>
parents:
845
diff
changeset
|
244 | * @param visitor the visitor |
6456036bbb37
implement tree continue - fixes #376
Mike Becker <universe@uap-core.de>
parents:
845
diff
changeset
|
245 | */ |
6456036bbb37
implement tree continue - fixes #376
Mike Becker <universe@uap-core.de>
parents:
845
diff
changeset
|
246 | #define cxTreeVisitorContinue(visitor) cxTreeIteratorContinue(visitor) |
6456036bbb37
implement tree continue - fixes #376
Mike Becker <universe@uap-core.de>
parents:
845
diff
changeset
|
247 | |
6456036bbb37
implement tree continue - fixes #376
Mike Becker <universe@uap-core.de>
parents:
845
diff
changeset
|
248 | /** |
822
e2243453127f
add code documentation for tree functions
Mike Becker <universe@uap-core.de>
parents:
816
diff
changeset
|
249 | * Links a node to a (new) parent. |
e2243453127f
add code documentation for tree functions
Mike Becker <universe@uap-core.de>
parents:
816
diff
changeset
|
250 | * |
e2243453127f
add code documentation for tree functions
Mike Becker <universe@uap-core.de>
parents:
816
diff
changeset
|
251 | * If the node has already a parent, it is unlinked, first. |
862
387414a7afd8
change cx_tree_link() from prepending to appending children - fixes #391
Mike Becker <universe@uap-core.de>
parents:
859
diff
changeset
|
252 | * If the parent has children already, the node is \em appended to the list |
826
21840975d541
add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents:
824
diff
changeset
|
253 | * of all currently existing children. |
822
e2243453127f
add code documentation for tree functions
Mike Becker <universe@uap-core.de>
parents:
816
diff
changeset
|
254 | * |
e2243453127f
add code documentation for tree functions
Mike Becker <universe@uap-core.de>
parents:
816
diff
changeset
|
255 | * @param parent the parent node |
e2243453127f
add code documentation for tree functions
Mike Becker <universe@uap-core.de>
parents:
816
diff
changeset
|
256 | * @param node the node that shall be linked |
e2243453127f
add code documentation for tree functions
Mike Becker <universe@uap-core.de>
parents:
816
diff
changeset
|
257 | * @param loc_parent offset in the node struct for the parent pointer |
e2243453127f
add code documentation for tree functions
Mike Becker <universe@uap-core.de>
parents:
816
diff
changeset
|
258 | * @param loc_children offset in the node struct for the children linked list |
862
387414a7afd8
change cx_tree_link() from prepending to appending children - fixes #391
Mike Becker <universe@uap-core.de>
parents:
859
diff
changeset
|
259 | * @param loc_last_child optional offset in the node struct for the pointer to |
387414a7afd8
change cx_tree_link() from prepending to appending children - fixes #391
Mike Becker <universe@uap-core.de>
parents:
859
diff
changeset
|
260 | * the last child in the linked list (negative if there is no such pointer) |
822
e2243453127f
add code documentation for tree functions
Mike Becker <universe@uap-core.de>
parents:
816
diff
changeset
|
261 | * @param loc_prev offset in the node struct for the prev pointer |
e2243453127f
add code documentation for tree functions
Mike Becker <universe@uap-core.de>
parents:
816
diff
changeset
|
262 | * @param loc_next offset in the node struct for the next pointer |
e2243453127f
add code documentation for tree functions
Mike Becker <universe@uap-core.de>
parents:
816
diff
changeset
|
263 | * @see cx_tree_unlink() |
e2243453127f
add code documentation for tree functions
Mike Becker <universe@uap-core.de>
parents:
816
diff
changeset
|
264 | */ |
816
425234b05dff
add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
265 | __attribute__((__nonnull__)) |
425234b05dff
add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
266 | void cx_tree_link( |
862
387414a7afd8
change cx_tree_link() from prepending to appending children - fixes #391
Mike Becker <universe@uap-core.de>
parents:
859
diff
changeset
|
267 | void *restrict parent, |
387414a7afd8
change cx_tree_link() from prepending to appending children - fixes #391
Mike Becker <universe@uap-core.de>
parents:
859
diff
changeset
|
268 | void *restrict node, |
816
425234b05dff
add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
269 | ptrdiff_t loc_parent, |
425234b05dff
add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
270 | ptrdiff_t loc_children, |
862
387414a7afd8
change cx_tree_link() from prepending to appending children - fixes #391
Mike Becker <universe@uap-core.de>
parents:
859
diff
changeset
|
271 | ptrdiff_t loc_last_child, |
816
425234b05dff
add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
272 | ptrdiff_t loc_prev, |
425234b05dff
add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
273 | ptrdiff_t loc_next |
425234b05dff
add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
274 | ); |
425234b05dff
add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
275 | |
822
e2243453127f
add code documentation for tree functions
Mike Becker <universe@uap-core.de>
parents:
816
diff
changeset
|
276 | /** |
e2243453127f
add code documentation for tree functions
Mike Becker <universe@uap-core.de>
parents:
816
diff
changeset
|
277 | * Unlinks a node from its parent. |
e2243453127f
add code documentation for tree functions
Mike Becker <universe@uap-core.de>
parents:
816
diff
changeset
|
278 | * |
e2243453127f
add code documentation for tree functions
Mike Becker <universe@uap-core.de>
parents:
816
diff
changeset
|
279 | * If the node has no parent, this function does nothing. |
e2243453127f
add code documentation for tree functions
Mike Becker <universe@uap-core.de>
parents:
816
diff
changeset
|
280 | * |
e2243453127f
add code documentation for tree functions
Mike Becker <universe@uap-core.de>
parents:
816
diff
changeset
|
281 | * @param node the node that shall be unlinked from its parent |
e2243453127f
add code documentation for tree functions
Mike Becker <universe@uap-core.de>
parents:
816
diff
changeset
|
282 | * @param loc_parent offset in the node struct for the parent pointer |
e2243453127f
add code documentation for tree functions
Mike Becker <universe@uap-core.de>
parents:
816
diff
changeset
|
283 | * @param loc_children offset in the node struct for the children linked list |
862
387414a7afd8
change cx_tree_link() from prepending to appending children - fixes #391
Mike Becker <universe@uap-core.de>
parents:
859
diff
changeset
|
284 | * @param loc_last_child optional offset in the node struct for the pointer to |
387414a7afd8
change cx_tree_link() from prepending to appending children - fixes #391
Mike Becker <universe@uap-core.de>
parents:
859
diff
changeset
|
285 | * the last child in the linked list (negative if there is no such pointer) |
822
e2243453127f
add code documentation for tree functions
Mike Becker <universe@uap-core.de>
parents:
816
diff
changeset
|
286 | * @param loc_prev offset in the node struct for the prev pointer |
e2243453127f
add code documentation for tree functions
Mike Becker <universe@uap-core.de>
parents:
816
diff
changeset
|
287 | * @param loc_next offset in the node struct for the next pointer |
e2243453127f
add code documentation for tree functions
Mike Becker <universe@uap-core.de>
parents:
816
diff
changeset
|
288 | * @see cx_tree_link() |
e2243453127f
add code documentation for tree functions
Mike Becker <universe@uap-core.de>
parents:
816
diff
changeset
|
289 | */ |
816
425234b05dff
add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
290 | __attribute__((__nonnull__)) |
425234b05dff
add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
291 | void cx_tree_unlink( |
425234b05dff
add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
292 | void *node, |
425234b05dff
add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
293 | ptrdiff_t loc_parent, |
425234b05dff
add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
294 | ptrdiff_t loc_children, |
862
387414a7afd8
change cx_tree_link() from prepending to appending children - fixes #391
Mike Becker <universe@uap-core.de>
parents:
859
diff
changeset
|
295 | ptrdiff_t loc_last_child, |
816
425234b05dff
add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
296 | ptrdiff_t loc_prev, |
425234b05dff
add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
297 | ptrdiff_t loc_next |
425234b05dff
add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
298 | ); |
425234b05dff
add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
299 | |
823
f4faa7f73cb8
declare cx_tree_search_func function pointer
Mike Becker <universe@uap-core.de>
parents:
822
diff
changeset
|
300 | /** |
f4faa7f73cb8
declare cx_tree_search_func function pointer
Mike Becker <universe@uap-core.de>
parents:
822
diff
changeset
|
301 | * Function pointer for a search function. |
f4faa7f73cb8
declare cx_tree_search_func function pointer
Mike Becker <universe@uap-core.de>
parents:
822
diff
changeset
|
302 | * |
f4faa7f73cb8
declare cx_tree_search_func function pointer
Mike Becker <universe@uap-core.de>
parents:
822
diff
changeset
|
303 | * A function of this kind shall check if the specified \p node |
f4faa7f73cb8
declare cx_tree_search_func function pointer
Mike Becker <universe@uap-core.de>
parents:
822
diff
changeset
|
304 | * contains the given \p data or if one of the children might contain |
f4faa7f73cb8
declare cx_tree_search_func function pointer
Mike Becker <universe@uap-core.de>
parents:
822
diff
changeset
|
305 | * the data. |
f4faa7f73cb8
declare cx_tree_search_func function pointer
Mike Becker <universe@uap-core.de>
parents:
822
diff
changeset
|
306 | * |
826
21840975d541
add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents:
824
diff
changeset
|
307 | * The function should use the returned integer to indicate how close the |
21840975d541
add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents:
824
diff
changeset
|
308 | * match is, where a negative number means that it does not match at all. |
21840975d541
add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents:
824
diff
changeset
|
309 | * |
823
f4faa7f73cb8
declare cx_tree_search_func function pointer
Mike Becker <universe@uap-core.de>
parents:
822
diff
changeset
|
310 | * For example if a tree stores file path information, a node that is |
f4faa7f73cb8
declare cx_tree_search_func function pointer
Mike Becker <universe@uap-core.de>
parents:
822
diff
changeset
|
311 | * describing a parent directory of a filename that is searched, shall |
826
21840975d541
add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents:
824
diff
changeset
|
312 | * return a positive number to indicate that a child node might contain the |
21840975d541
add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents:
824
diff
changeset
|
313 | * searched item. On the other hand, if the node denotes a path that is not a |
21840975d541
add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents:
824
diff
changeset
|
314 | * prefix of the searched filename, the function would return -1 to indicate |
859 | 315 | * that the search does not need to be continued in that branch. |
823
f4faa7f73cb8
declare cx_tree_search_func function pointer
Mike Becker <universe@uap-core.de>
parents:
822
diff
changeset
|
316 | * |
f4faa7f73cb8
declare cx_tree_search_func function pointer
Mike Becker <universe@uap-core.de>
parents:
822
diff
changeset
|
317 | * @param node the node that is currently investigated |
f4faa7f73cb8
declare cx_tree_search_func function pointer
Mike Becker <universe@uap-core.de>
parents:
822
diff
changeset
|
318 | * @param data the data that is searched for |
f4faa7f73cb8
declare cx_tree_search_func function pointer
Mike Becker <universe@uap-core.de>
parents:
822
diff
changeset
|
319 | * |
f4faa7f73cb8
declare cx_tree_search_func function pointer
Mike Becker <universe@uap-core.de>
parents:
822
diff
changeset
|
320 | * @return 0 if the node contains the data, |
826
21840975d541
add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents:
824
diff
changeset
|
321 | * positive if one of the children might contain the data, |
21840975d541
add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents:
824
diff
changeset
|
322 | * negative if neither the node, nor the children contains the data |
823
f4faa7f73cb8
declare cx_tree_search_func function pointer
Mike Becker <universe@uap-core.de>
parents:
822
diff
changeset
|
323 | */ |
859 | 324 | typedef int (*cx_tree_search_func)(void const *node, void const *data); |
823
f4faa7f73cb8
declare cx_tree_search_func function pointer
Mike Becker <universe@uap-core.de>
parents:
822
diff
changeset
|
325 | |
826
21840975d541
add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents:
824
diff
changeset
|
326 | |
21840975d541
add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents:
824
diff
changeset
|
327 | /** |
21840975d541
add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents:
824
diff
changeset
|
328 | * Searches for data in a tree. |
21840975d541
add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents:
824
diff
changeset
|
329 | * |
21840975d541
add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents:
824
diff
changeset
|
330 | * When the data cannot be found exactly, the search function might return a |
21840975d541
add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents:
824
diff
changeset
|
331 | * closest result which might be a good starting point for adding a new node |
21840975d541
add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents:
824
diff
changeset
|
332 | * to the tree. |
21840975d541
add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents:
824
diff
changeset
|
333 | * |
21840975d541
add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents:
824
diff
changeset
|
334 | * Depending on the tree structure it is not necessarily guaranteed that the |
21840975d541
add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents:
824
diff
changeset
|
335 | * "closest" match is uniquely defined. This function will search for a node |
21840975d541
add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents:
824
diff
changeset
|
336 | * with the best match according to the \p sfunc (meaning: the return value of |
21840975d541
add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents:
824
diff
changeset
|
337 | * \p sfunc which is closest to zero). If that is also ambiguous, an arbitrary |
21840975d541
add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents:
824
diff
changeset
|
338 | * node matching the criteria is returned. |
21840975d541
add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents:
824
diff
changeset
|
339 | * |
21840975d541
add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents:
824
diff
changeset
|
340 | * @param root the root node |
21840975d541
add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents:
824
diff
changeset
|
341 | * @param data the data to search for |
21840975d541
add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents:
824
diff
changeset
|
342 | * @param sfunc the search function |
21840975d541
add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents:
824
diff
changeset
|
343 | * @param result where the result shall be stored |
21840975d541
add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents:
824
diff
changeset
|
344 | * @param loc_children offset in the node struct for the children linked list |
21840975d541
add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents:
824
diff
changeset
|
345 | * @param loc_next offset in the node struct for the next pointer |
21840975d541
add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents:
824
diff
changeset
|
346 | * @return zero if the node was found exactly, positive if a node was found that |
21840975d541
add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents:
824
diff
changeset
|
347 | * could contain the node (but doesn't right now), negative if the tree does not |
21840975d541
add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents:
824
diff
changeset
|
348 | * contain any node that might be related to the searched data |
21840975d541
add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents:
824
diff
changeset
|
349 | */ |
21840975d541
add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents:
824
diff
changeset
|
350 | __attribute__((__nonnull__)) |
21840975d541
add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents:
824
diff
changeset
|
351 | int cx_tree_search( |
21840975d541
add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents:
824
diff
changeset
|
352 | void const *root, |
21840975d541
add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents:
824
diff
changeset
|
353 | void const *data, |
21840975d541
add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents:
824
diff
changeset
|
354 | cx_tree_search_func sfunc, |
21840975d541
add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents:
824
diff
changeset
|
355 | void **result, |
21840975d541
add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents:
824
diff
changeset
|
356 | ptrdiff_t loc_children, |
21840975d541
add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents:
824
diff
changeset
|
357 | ptrdiff_t loc_next |
21840975d541
add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents:
824
diff
changeset
|
358 | ); |
21840975d541
add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents:
824
diff
changeset
|
359 | |
828
88fa3381206d
improve tree iterator struct and add signature for a function that can create an iterator
Mike Becker <universe@uap-core.de>
parents:
827
diff
changeset
|
360 | /** |
845 | 361 | * Creates a depth-first iterator for a tree with the specified root node. |
828
88fa3381206d
improve tree iterator struct and add signature for a function that can create an iterator
Mike Becker <universe@uap-core.de>
parents:
827
diff
changeset
|
362 | * |
859 | 363 | * @note A tree iterator needs to maintain a stack of visited nodes, which is |
364 | * allocated using stdlib malloc(). | |
365 | * When the iterator becomes invalid, this memory is automatically released. | |
366 | * However, if you wish to cancel the iteration before the iterator becomes | |
367 | * invalid by itself, you MUST call cxTreeIteratorDispose() manually to release | |
828
88fa3381206d
improve tree iterator struct and add signature for a function that can create an iterator
Mike Becker <universe@uap-core.de>
parents:
827
diff
changeset
|
368 | * the memory. |
88fa3381206d
improve tree iterator struct and add signature for a function that can create an iterator
Mike Becker <universe@uap-core.de>
parents:
827
diff
changeset
|
369 | * |
845 | 370 | * @remark The returned iterator does not support cxIteratorFlagRemoval(). |
828
88fa3381206d
improve tree iterator struct and add signature for a function that can create an iterator
Mike Becker <universe@uap-core.de>
parents:
827
diff
changeset
|
371 | * |
88fa3381206d
improve tree iterator struct and add signature for a function that can create an iterator
Mike Becker <universe@uap-core.de>
parents:
827
diff
changeset
|
372 | * @param root the root node |
859 | 373 | * @param visit_on_exit set to true, when the iterator shall visit a node again |
374 | * after processing all children | |
828
88fa3381206d
improve tree iterator struct and add signature for a function that can create an iterator
Mike Becker <universe@uap-core.de>
parents:
827
diff
changeset
|
375 | * @param loc_children offset in the node struct for the children linked list |
88fa3381206d
improve tree iterator struct and add signature for a function that can create an iterator
Mike Becker <universe@uap-core.de>
parents:
827
diff
changeset
|
376 | * @param loc_next offset in the node struct for the next pointer |
88fa3381206d
improve tree iterator struct and add signature for a function that can create an iterator
Mike Becker <universe@uap-core.de>
parents:
827
diff
changeset
|
377 | * @return the new tree iterator |
88fa3381206d
improve tree iterator struct and add signature for a function that can create an iterator
Mike Becker <universe@uap-core.de>
parents:
827
diff
changeset
|
378 | * @see cxTreeIteratorDispose() |
88fa3381206d
improve tree iterator struct and add signature for a function that can create an iterator
Mike Becker <universe@uap-core.de>
parents:
827
diff
changeset
|
379 | */ |
88fa3381206d
improve tree iterator struct and add signature for a function that can create an iterator
Mike Becker <universe@uap-core.de>
parents:
827
diff
changeset
|
380 | __attribute__((__nonnull__)) |
830
c4dae6fe6d5b
commit complicated stuff before simplifying it
Mike Becker <universe@uap-core.de>
parents:
828
diff
changeset
|
381 | CxTreeIterator cx_tree_iterator( |
c4dae6fe6d5b
commit complicated stuff before simplifying it
Mike Becker <universe@uap-core.de>
parents:
828
diff
changeset
|
382 | void *root, |
833
5c926801f052
vastly simplify tree iterators and add test for creating them
Mike Becker <universe@uap-core.de>
parents:
830
diff
changeset
|
383 | bool visit_on_exit, |
828
88fa3381206d
improve tree iterator struct and add signature for a function that can create an iterator
Mike Becker <universe@uap-core.de>
parents:
827
diff
changeset
|
384 | ptrdiff_t loc_children, |
88fa3381206d
improve tree iterator struct and add signature for a function that can create an iterator
Mike Becker <universe@uap-core.de>
parents:
827
diff
changeset
|
385 | ptrdiff_t loc_next |
88fa3381206d
improve tree iterator struct and add signature for a function that can create an iterator
Mike Becker <universe@uap-core.de>
parents:
827
diff
changeset
|
386 | ); |
88fa3381206d
improve tree iterator struct and add signature for a function that can create an iterator
Mike Becker <universe@uap-core.de>
parents:
827
diff
changeset
|
387 | |
845 | 388 | /** |
389 | * Creates a breadth-first iterator for a tree with the specified root node. | |
390 | * | |
859 | 391 | * @note A tree visitor needs to maintain a queue of to be visited nodes, which |
392 | * is allocated using stdlib malloc(). | |
393 | * When the visitor becomes invalid, this memory is automatically released. | |
394 | * However, if you wish to cancel the iteration before the visitor becomes | |
395 | * invalid by itself, you MUST call cxTreeVisitorDispose() manually to release | |
845 | 396 | * the memory. |
397 | * | |
398 | * @remark The returned iterator does not support cxIteratorFlagRemoval(). | |
399 | * | |
400 | * @param root the root node | |
401 | * @param loc_children offset in the node struct for the children linked list | |
402 | * @param loc_next offset in the node struct for the next pointer | |
403 | * @return the new tree visitor | |
404 | * @see cxTreeVisitorDispose() | |
405 | */ | |
406 | __attribute__((__nonnull__)) | |
407 | CxTreeVisitor cx_tree_visitor( | |
408 | void *root, | |
409 | ptrdiff_t loc_children, | |
410 | ptrdiff_t loc_next | |
411 | ); | |
412 | ||
860
558ed4c6abd0
add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents:
859
diff
changeset
|
413 | /** |
558ed4c6abd0
add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents:
859
diff
changeset
|
414 | * Describes a function that creates a tree node from the specified data. |
558ed4c6abd0
add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents:
859
diff
changeset
|
415 | */ |
558ed4c6abd0
add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents:
859
diff
changeset
|
416 | typedef void (*cx_tree_node_create_fun)(void const*); |
558ed4c6abd0
add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents:
859
diff
changeset
|
417 | |
558ed4c6abd0
add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents:
859
diff
changeset
|
418 | __attribute__((__nonnull__)) |
558ed4c6abd0
add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents:
859
diff
changeset
|
419 | size_t cx_tree_add_iter( |
558ed4c6abd0
add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents:
859
diff
changeset
|
420 | struct cx_iterator_base_s *iter, |
558ed4c6abd0
add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents:
859
diff
changeset
|
421 | cx_tree_search_func sfunc, |
558ed4c6abd0
add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents:
859
diff
changeset
|
422 | cx_tree_node_create_fun cfunc, |
558ed4c6abd0
add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents:
859
diff
changeset
|
423 | void **root, |
558ed4c6abd0
add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents:
859
diff
changeset
|
424 | ptrdiff_t loc_parent, |
558ed4c6abd0
add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents:
859
diff
changeset
|
425 | ptrdiff_t loc_children, |
558ed4c6abd0
add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents:
859
diff
changeset
|
426 | ptrdiff_t loc_prev, |
558ed4c6abd0
add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents:
859
diff
changeset
|
427 | ptrdiff_t loc_next |
558ed4c6abd0
add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents:
859
diff
changeset
|
428 | ); |
558ed4c6abd0
add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents:
859
diff
changeset
|
429 | |
558ed4c6abd0
add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents:
859
diff
changeset
|
430 | __attribute__((__nonnull__)) |
558ed4c6abd0
add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents:
859
diff
changeset
|
431 | size_t cx_tree_add_array( |
558ed4c6abd0
add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents:
859
diff
changeset
|
432 | void const *src, |
558ed4c6abd0
add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents:
859
diff
changeset
|
433 | size_t num, |
558ed4c6abd0
add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents:
859
diff
changeset
|
434 | size_t elem_size, |
558ed4c6abd0
add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents:
859
diff
changeset
|
435 | cx_tree_search_func sfunc, |
558ed4c6abd0
add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents:
859
diff
changeset
|
436 | cx_tree_node_create_fun cfunc, |
558ed4c6abd0
add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents:
859
diff
changeset
|
437 | void **root, |
558ed4c6abd0
add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents:
859
diff
changeset
|
438 | ptrdiff_t loc_parent, |
558ed4c6abd0
add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents:
859
diff
changeset
|
439 | ptrdiff_t loc_children, |
558ed4c6abd0
add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents:
859
diff
changeset
|
440 | ptrdiff_t loc_prev, |
558ed4c6abd0
add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents:
859
diff
changeset
|
441 | ptrdiff_t loc_next |
558ed4c6abd0
add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents:
859
diff
changeset
|
442 | ); |
558ed4c6abd0
add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents:
859
diff
changeset
|
443 | |
558ed4c6abd0
add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents:
859
diff
changeset
|
444 | __attribute__((__nonnull__)) |
558ed4c6abd0
add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents:
859
diff
changeset
|
445 | void *cx_tree_add( |
558ed4c6abd0
add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents:
859
diff
changeset
|
446 | void const *src, |
558ed4c6abd0
add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents:
859
diff
changeset
|
447 | cx_tree_search_func sfunc, |
558ed4c6abd0
add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents:
859
diff
changeset
|
448 | cx_tree_node_create_fun cfunc, |
558ed4c6abd0
add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents:
859
diff
changeset
|
449 | void **root, |
558ed4c6abd0
add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents:
859
diff
changeset
|
450 | ptrdiff_t loc_parent, |
558ed4c6abd0
add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents:
859
diff
changeset
|
451 | ptrdiff_t loc_children, |
558ed4c6abd0
add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents:
859
diff
changeset
|
452 | ptrdiff_t loc_prev, |
558ed4c6abd0
add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents:
859
diff
changeset
|
453 | ptrdiff_t loc_next |
558ed4c6abd0
add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents:
859
diff
changeset
|
454 | ); |
558ed4c6abd0
add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents:
859
diff
changeset
|
455 | |
816
425234b05dff
add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
456 | #ifdef __cplusplus |
425234b05dff
add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
457 | } // extern "C" |
425234b05dff
add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
458 | #endif |
425234b05dff
add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
459 | |
425234b05dff
add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
460 | #endif //UCX_TREE_H |