Sun, 07 Jul 2024 12:21:58 +0200
add prototypes for cx_tree_add() family of functions
relates to #390
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. |
845 | 252 | * If the parent has children already, the node is \em prepended 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 |
e2243453127f
add code documentation for tree functions
Mike Becker <universe@uap-core.de>
parents:
816
diff
changeset
|
259 | * @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
|
260 | * @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
|
261 | * @see cx_tree_unlink() |
e2243453127f
add code documentation for tree functions
Mike Becker <universe@uap-core.de>
parents:
816
diff
changeset
|
262 | */ |
816
425234b05dff
add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
263 | __attribute__((__nonnull__)) |
425234b05dff
add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
264 | void cx_tree_link( |
425234b05dff
add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
265 | void * restrict parent, |
425234b05dff
add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
266 | void * restrict node, |
425234b05dff
add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
267 | ptrdiff_t loc_parent, |
425234b05dff
add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
268 | ptrdiff_t loc_children, |
425234b05dff
add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
269 | ptrdiff_t loc_prev, |
425234b05dff
add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
270 | ptrdiff_t loc_next |
425234b05dff
add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
271 | ); |
425234b05dff
add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
272 | |
822
e2243453127f
add code documentation for tree functions
Mike Becker <universe@uap-core.de>
parents:
816
diff
changeset
|
273 | /** |
e2243453127f
add code documentation for tree functions
Mike Becker <universe@uap-core.de>
parents:
816
diff
changeset
|
274 | * Unlinks a node from its parent. |
e2243453127f
add code documentation for tree functions
Mike Becker <universe@uap-core.de>
parents:
816
diff
changeset
|
275 | * |
e2243453127f
add code documentation for tree functions
Mike Becker <universe@uap-core.de>
parents:
816
diff
changeset
|
276 | * 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
|
277 | * |
e2243453127f
add code documentation for tree functions
Mike Becker <universe@uap-core.de>
parents:
816
diff
changeset
|
278 | * @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
|
279 | * @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
|
280 | * @param loc_children offset in the node struct for the children linked list |
e2243453127f
add code documentation for tree functions
Mike Becker <universe@uap-core.de>
parents:
816
diff
changeset
|
281 | * @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
|
282 | * @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
|
283 | * @see cx_tree_link() |
e2243453127f
add code documentation for tree functions
Mike Becker <universe@uap-core.de>
parents:
816
diff
changeset
|
284 | */ |
816
425234b05dff
add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
285 | __attribute__((__nonnull__)) |
425234b05dff
add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
286 | void cx_tree_unlink( |
425234b05dff
add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
287 | void *node, |
425234b05dff
add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
288 | ptrdiff_t loc_parent, |
425234b05dff
add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
289 | ptrdiff_t loc_children, |
425234b05dff
add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
290 | ptrdiff_t loc_prev, |
425234b05dff
add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
291 | ptrdiff_t loc_next |
425234b05dff
add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
292 | ); |
425234b05dff
add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
293 | |
823
f4faa7f73cb8
declare cx_tree_search_func function pointer
Mike Becker <universe@uap-core.de>
parents:
822
diff
changeset
|
294 | /** |
f4faa7f73cb8
declare cx_tree_search_func function pointer
Mike Becker <universe@uap-core.de>
parents:
822
diff
changeset
|
295 | * Function pointer for a search function. |
f4faa7f73cb8
declare cx_tree_search_func function pointer
Mike Becker <universe@uap-core.de>
parents:
822
diff
changeset
|
296 | * |
f4faa7f73cb8
declare cx_tree_search_func function pointer
Mike Becker <universe@uap-core.de>
parents:
822
diff
changeset
|
297 | * 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
|
298 | * 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
|
299 | * the data. |
f4faa7f73cb8
declare cx_tree_search_func function pointer
Mike Becker <universe@uap-core.de>
parents:
822
diff
changeset
|
300 | * |
826
21840975d541
add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents:
824
diff
changeset
|
301 | * 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
|
302 | * 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
|
303 | * |
823
f4faa7f73cb8
declare cx_tree_search_func function pointer
Mike Becker <universe@uap-core.de>
parents:
822
diff
changeset
|
304 | * 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
|
305 | * 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
|
306 | * 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
|
307 | * 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
|
308 | * prefix of the searched filename, the function would return -1 to indicate |
859 | 309 | * 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
|
310 | * |
f4faa7f73cb8
declare cx_tree_search_func function pointer
Mike Becker <universe@uap-core.de>
parents:
822
diff
changeset
|
311 | * @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
|
312 | * @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
|
313 | * |
f4faa7f73cb8
declare cx_tree_search_func function pointer
Mike Becker <universe@uap-core.de>
parents:
822
diff
changeset
|
314 | * @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
|
315 | * 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
|
316 | * 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
|
317 | */ |
859 | 318 | 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
|
319 | |
826
21840975d541
add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents:
824
diff
changeset
|
320 | |
21840975d541
add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents:
824
diff
changeset
|
321 | /** |
21840975d541
add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents:
824
diff
changeset
|
322 | * Searches for data in a tree. |
21840975d541
add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents:
824
diff
changeset
|
323 | * |
21840975d541
add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents:
824
diff
changeset
|
324 | * 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
|
325 | * 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
|
326 | * to the tree. |
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 | * 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
|
329 | * "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
|
330 | * 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
|
331 | * \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
|
332 | * node matching the criteria is returned. |
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 | * @param root the root node |
21840975d541
add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents:
824
diff
changeset
|
335 | * @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
|
336 | * @param sfunc the search function |
21840975d541
add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents:
824
diff
changeset
|
337 | * @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
|
338 | * @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
|
339 | * @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
|
340 | * @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
|
341 | * 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
|
342 | * 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
|
343 | */ |
21840975d541
add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents:
824
diff
changeset
|
344 | __attribute__((__nonnull__)) |
21840975d541
add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents:
824
diff
changeset
|
345 | int cx_tree_search( |
21840975d541
add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents:
824
diff
changeset
|
346 | void const *root, |
21840975d541
add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents:
824
diff
changeset
|
347 | void const *data, |
21840975d541
add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents:
824
diff
changeset
|
348 | cx_tree_search_func sfunc, |
21840975d541
add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents:
824
diff
changeset
|
349 | void **result, |
21840975d541
add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents:
824
diff
changeset
|
350 | ptrdiff_t loc_children, |
21840975d541
add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents:
824
diff
changeset
|
351 | ptrdiff_t loc_next |
21840975d541
add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents:
824
diff
changeset
|
352 | ); |
21840975d541
add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents:
824
diff
changeset
|
353 | |
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
|
354 | /** |
845 | 355 | * 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
|
356 | * |
859 | 357 | * @note A tree iterator needs to maintain a stack of visited nodes, which is |
358 | * allocated using stdlib malloc(). | |
359 | * When the iterator becomes invalid, this memory is automatically released. | |
360 | * However, if you wish to cancel the iteration before the iterator becomes | |
361 | * 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
|
362 | * 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
|
363 | * |
845 | 364 | * @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
|
365 | * |
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
|
366 | * @param root the root node |
859 | 367 | * @param visit_on_exit set to true, when the iterator shall visit a node again |
368 | * 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
|
369 | * @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
|
370 | * @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
|
371 | * @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
|
372 | * @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
|
373 | */ |
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
|
374 | __attribute__((__nonnull__)) |
830
c4dae6fe6d5b
commit complicated stuff before simplifying it
Mike Becker <universe@uap-core.de>
parents:
828
diff
changeset
|
375 | CxTreeIterator cx_tree_iterator( |
c4dae6fe6d5b
commit complicated stuff before simplifying it
Mike Becker <universe@uap-core.de>
parents:
828
diff
changeset
|
376 | void *root, |
833
5c926801f052
vastly simplify tree iterators and add test for creating them
Mike Becker <universe@uap-core.de>
parents:
830
diff
changeset
|
377 | 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
|
378 | 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
|
379 | 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
|
380 | ); |
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
|
381 | |
845 | 382 | /** |
383 | * Creates a breadth-first iterator for a tree with the specified root node. | |
384 | * | |
859 | 385 | * @note A tree visitor needs to maintain a queue of to be visited nodes, which |
386 | * is allocated using stdlib malloc(). | |
387 | * When the visitor becomes invalid, this memory is automatically released. | |
388 | * However, if you wish to cancel the iteration before the visitor becomes | |
389 | * invalid by itself, you MUST call cxTreeVisitorDispose() manually to release | |
845 | 390 | * the memory. |
391 | * | |
392 | * @remark The returned iterator does not support cxIteratorFlagRemoval(). | |
393 | * | |
394 | * @param root the root node | |
395 | * @param loc_children offset in the node struct for the children linked list | |
396 | * @param loc_next offset in the node struct for the next pointer | |
397 | * @return the new tree visitor | |
398 | * @see cxTreeVisitorDispose() | |
399 | */ | |
400 | __attribute__((__nonnull__)) | |
401 | CxTreeVisitor cx_tree_visitor( | |
402 | void *root, | |
403 | ptrdiff_t loc_children, | |
404 | ptrdiff_t loc_next | |
405 | ); | |
406 | ||
860
558ed4c6abd0
add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents:
859
diff
changeset
|
407 | /** |
558ed4c6abd0
add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents:
859
diff
changeset
|
408 | * 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
|
409 | */ |
558ed4c6abd0
add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents:
859
diff
changeset
|
410 | 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
|
411 | |
558ed4c6abd0
add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents:
859
diff
changeset
|
412 | __attribute__((__nonnull__)) |
558ed4c6abd0
add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents:
859
diff
changeset
|
413 | 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
|
414 | 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
|
415 | 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
|
416 | 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
|
417 | void **root, |
558ed4c6abd0
add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents:
859
diff
changeset
|
418 | ptrdiff_t loc_parent, |
558ed4c6abd0
add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents:
859
diff
changeset
|
419 | ptrdiff_t loc_children, |
558ed4c6abd0
add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents:
859
diff
changeset
|
420 | ptrdiff_t loc_prev, |
558ed4c6abd0
add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents:
859
diff
changeset
|
421 | ptrdiff_t loc_next |
558ed4c6abd0
add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents:
859
diff
changeset
|
422 | ); |
558ed4c6abd0
add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents:
859
diff
changeset
|
423 | |
558ed4c6abd0
add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents:
859
diff
changeset
|
424 | __attribute__((__nonnull__)) |
558ed4c6abd0
add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents:
859
diff
changeset
|
425 | 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
|
426 | void const *src, |
558ed4c6abd0
add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents:
859
diff
changeset
|
427 | size_t num, |
558ed4c6abd0
add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents:
859
diff
changeset
|
428 | size_t elem_size, |
558ed4c6abd0
add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents:
859
diff
changeset
|
429 | 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
|
430 | 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
|
431 | void **root, |
558ed4c6abd0
add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents:
859
diff
changeset
|
432 | ptrdiff_t loc_parent, |
558ed4c6abd0
add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents:
859
diff
changeset
|
433 | ptrdiff_t loc_children, |
558ed4c6abd0
add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents:
859
diff
changeset
|
434 | ptrdiff_t loc_prev, |
558ed4c6abd0
add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents:
859
diff
changeset
|
435 | ptrdiff_t loc_next |
558ed4c6abd0
add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents:
859
diff
changeset
|
436 | ); |
558ed4c6abd0
add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents:
859
diff
changeset
|
437 | |
558ed4c6abd0
add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents:
859
diff
changeset
|
438 | __attribute__((__nonnull__)) |
558ed4c6abd0
add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents:
859
diff
changeset
|
439 | void *cx_tree_add( |
558ed4c6abd0
add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents:
859
diff
changeset
|
440 | void const *src, |
558ed4c6abd0
add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents:
859
diff
changeset
|
441 | 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
|
442 | 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
|
443 | void **root, |
558ed4c6abd0
add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents:
859
diff
changeset
|
444 | ptrdiff_t loc_parent, |
558ed4c6abd0
add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents:
859
diff
changeset
|
445 | ptrdiff_t loc_children, |
558ed4c6abd0
add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents:
859
diff
changeset
|
446 | ptrdiff_t loc_prev, |
558ed4c6abd0
add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents:
859
diff
changeset
|
447 | ptrdiff_t loc_next |
558ed4c6abd0
add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents:
859
diff
changeset
|
448 | ); |
558ed4c6abd0
add prototypes for cx_tree_add() family of functions
Mike Becker <universe@uap-core.de>
parents:
859
diff
changeset
|
449 | |
816
425234b05dff
add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
450 | #ifdef __cplusplus |
425234b05dff
add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
451 | } // extern "C" |
425234b05dff
add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
452 | #endif |
425234b05dff
add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
453 | |
425234b05dff
add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
454 | #endif //UCX_TREE_H |