Thu, 23 May 2024 15:05:24 +0200
add iterator over raw C arrays - closes #389
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 | * |
13b40a598d16
first draft of a tree iterator
Mike Becker <universe@uap-core.de>
parents:
826
diff
changeset
|
50 | * This iterator is not position-aware in a strict sense, as it does not assume a particular order of elements in the |
13b40a598d16
first draft of a tree iterator
Mike Becker <universe@uap-core.de>
parents:
826
diff
changeset
|
51 | * tree. However, the iterator keeps track of the number of nodes it has passed in a counter variable. |
13b40a598d16
first draft of a tree iterator
Mike Becker <universe@uap-core.de>
parents:
826
diff
changeset
|
52 | * 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
|
53 | * |
13b40a598d16
first draft of a tree iterator
Mike Becker <universe@uap-core.de>
parents:
826
diff
changeset
|
54 | * @note Objects that are pointed to by an iterator are mutable through that iterator. However, if the |
833
5c926801f052
vastly simplify tree iterators and add test for creating them
Mike Becker <universe@uap-core.de>
parents:
830
diff
changeset
|
55 | * underlying data structure is mutated by other means than this iterator (e.g. elements added or removed), |
5c926801f052
vastly simplify tree iterators and add test for creating them
Mike Becker <universe@uap-core.de>
parents:
830
diff
changeset
|
56 | * the iterator becomes invalid (regardless of what cxIteratorValid() returns). |
827
13b40a598d16
first draft of a tree iterator
Mike Becker <universe@uap-core.de>
parents:
826
diff
changeset
|
57 | * |
13b40a598d16
first draft of a tree iterator
Mike Becker <universe@uap-core.de>
parents:
826
diff
changeset
|
58 | * @see CxIterator |
13b40a598d16
first draft of a tree iterator
Mike Becker <universe@uap-core.de>
parents:
826
diff
changeset
|
59 | */ |
13b40a598d16
first draft of a tree iterator
Mike Becker <universe@uap-core.de>
parents:
826
diff
changeset
|
60 | typedef struct cx_tree_iterator_s { |
13b40a598d16
first draft of a tree iterator
Mike Becker <universe@uap-core.de>
parents:
826
diff
changeset
|
61 | /** |
13b40a598d16
first draft of a tree iterator
Mike Becker <universe@uap-core.de>
parents:
826
diff
changeset
|
62 | * The base properties of this iterator. |
13b40a598d16
first draft of a tree iterator
Mike Becker <universe@uap-core.de>
parents:
826
diff
changeset
|
63 | */ |
13b40a598d16
first draft of a tree iterator
Mike Becker <universe@uap-core.de>
parents:
826
diff
changeset
|
64 | struct cx_iterator_base_s base; |
13b40a598d16
first draft of a tree iterator
Mike Becker <universe@uap-core.de>
parents:
826
diff
changeset
|
65 | /** |
848
6456036bbb37
implement tree continue - fixes #376
Mike Becker <universe@uap-core.de>
parents:
845
diff
changeset
|
66 | * 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
|
67 | */ |
6456036bbb37
implement tree continue - fixes #376
Mike Becker <universe@uap-core.de>
parents:
845
diff
changeset
|
68 | bool skip; |
6456036bbb37
implement tree continue - fixes #376
Mike Becker <universe@uap-core.de>
parents:
845
diff
changeset
|
69 | /** |
833
5c926801f052
vastly simplify tree iterators and add test for creating them
Mike Becker <universe@uap-core.de>
parents:
830
diff
changeset
|
70 | * 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
|
71 | * 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
|
72 | */ |
833
5c926801f052
vastly simplify tree iterators and add test for creating them
Mike Becker <universe@uap-core.de>
parents:
830
diff
changeset
|
73 | bool visit_on_exit; |
827
13b40a598d16
first draft of a tree iterator
Mike Becker <universe@uap-core.de>
parents:
826
diff
changeset
|
74 | /** |
833
5c926801f052
vastly simplify tree iterators and add test for creating them
Mike Becker <universe@uap-core.de>
parents:
830
diff
changeset
|
75 | * 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
|
76 | */ |
833
5c926801f052
vastly simplify tree iterators and add test for creating them
Mike Becker <universe@uap-core.de>
parents:
830
diff
changeset
|
77 | bool exiting; |
827
13b40a598d16
first draft of a tree iterator
Mike Becker <universe@uap-core.de>
parents:
826
diff
changeset
|
78 | /** |
13b40a598d16
first draft of a tree iterator
Mike Becker <universe@uap-core.de>
parents:
826
diff
changeset
|
79 | * 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
|
80 | */ |
845 | 81 | ptrdiff_t loc_children; |
827
13b40a598d16
first draft of a tree iterator
Mike Becker <universe@uap-core.de>
parents:
826
diff
changeset
|
82 | /** |
13b40a598d16
first draft of a tree iterator
Mike Becker <universe@uap-core.de>
parents:
826
diff
changeset
|
83 | * 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
|
84 | */ |
845 | 85 | ptrdiff_t loc_next; |
827
13b40a598d16
first draft of a tree iterator
Mike Becker <universe@uap-core.de>
parents:
826
diff
changeset
|
86 | /** |
13b40a598d16
first draft of a tree iterator
Mike Becker <universe@uap-core.de>
parents:
826
diff
changeset
|
87 | * 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
|
88 | */ |
13b40a598d16
first draft of a tree iterator
Mike Becker <universe@uap-core.de>
parents:
826
diff
changeset
|
89 | size_t counter; |
13b40a598d16
first draft of a tree iterator
Mike Becker <universe@uap-core.de>
parents:
826
diff
changeset
|
90 | /** |
13b40a598d16
first draft of a tree iterator
Mike Becker <universe@uap-core.de>
parents:
826
diff
changeset
|
91 | * The currently observed node. |
13b40a598d16
first draft of a tree iterator
Mike Becker <universe@uap-core.de>
parents:
826
diff
changeset
|
92 | * |
13b40a598d16
first draft of a tree iterator
Mike Becker <universe@uap-core.de>
parents:
826
diff
changeset
|
93 | * 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
|
94 | */ |
13b40a598d16
first draft of a tree iterator
Mike Becker <universe@uap-core.de>
parents:
826
diff
changeset
|
95 | void *node; |
13b40a598d16
first draft of a tree iterator
Mike Becker <universe@uap-core.de>
parents:
826
diff
changeset
|
96 | /** |
840
4f02995ce44e
allow freeing tree nodes on exit - fixes #377
Mike Becker <universe@uap-core.de>
parents:
835
diff
changeset
|
97 | * 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
|
98 | * 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
|
99 | */ |
4f02995ce44e
allow freeing tree nodes on exit - fixes #377
Mike Becker <universe@uap-core.de>
parents:
835
diff
changeset
|
100 | void *next; |
4f02995ce44e
allow freeing tree nodes on exit - fixes #377
Mike Becker <universe@uap-core.de>
parents:
835
diff
changeset
|
101 | /** |
827
13b40a598d16
first draft of a tree iterator
Mike Becker <universe@uap-core.de>
parents:
826
diff
changeset
|
102 | * Internal stack. |
13b40a598d16
first draft of a tree iterator
Mike Becker <universe@uap-core.de>
parents:
826
diff
changeset
|
103 | * 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
|
104 | * |
13b40a598d16
first draft of a tree iterator
Mike Becker <universe@uap-core.de>
parents:
826
diff
changeset
|
105 | * 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
|
106 | * call cxTreeIteratorDispose(). |
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 | 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
|
109 | /** |
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
|
110 | * 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
|
111 | */ |
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 | 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
|
113 | union { |
5c926801f052
vastly simplify tree iterators and add test for creating them
Mike Becker <universe@uap-core.de>
parents:
830
diff
changeset
|
114 | /** |
5c926801f052
vastly simplify tree iterators and add test for creating them
Mike Becker <universe@uap-core.de>
parents:
830
diff
changeset
|
115 | * Internal stack size. |
5c926801f052
vastly simplify tree iterators and add test for creating them
Mike Becker <universe@uap-core.de>
parents:
830
diff
changeset
|
116 | */ |
5c926801f052
vastly simplify tree iterators and add test for creating them
Mike Becker <universe@uap-core.de>
parents:
830
diff
changeset
|
117 | 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
|
118 | /** |
5c926801f052
vastly simplify tree iterators and add test for creating them
Mike Becker <universe@uap-core.de>
parents:
830
diff
changeset
|
119 | * 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
|
120 | */ |
5c926801f052
vastly simplify tree iterators and add test for creating them
Mike Becker <universe@uap-core.de>
parents:
830
diff
changeset
|
121 | size_t depth; |
5c926801f052
vastly simplify tree iterators and add test for creating them
Mike Becker <universe@uap-core.de>
parents:
830
diff
changeset
|
122 | }; |
827
13b40a598d16
first draft of a tree iterator
Mike Becker <universe@uap-core.de>
parents:
826
diff
changeset
|
123 | } CxTreeIterator; |
13b40a598d16
first draft of a tree iterator
Mike Becker <universe@uap-core.de>
parents:
826
diff
changeset
|
124 | |
13b40a598d16
first draft of a tree iterator
Mike Becker <universe@uap-core.de>
parents:
826
diff
changeset
|
125 | /** |
845 | 126 | * An element in a visitor queue. |
127 | */ | |
128 | struct cx_tree_visitor_queue_s { | |
129 | /** | |
130 | * The tree node to visit. | |
131 | */ | |
132 | void *node; | |
133 | /** | |
134 | * The depth of the node. | |
135 | */ | |
136 | size_t depth; | |
137 | /** | |
138 | * The next element in the queue or \c NULL. | |
139 | */ | |
140 | struct cx_tree_visitor_queue_s *next; | |
141 | }; | |
142 | ||
143 | /** | |
144 | * A breadth-first tree iterator. | |
145 | * | |
146 | * This iterator needs to maintain a visitor queue that will be automatically freed once the iterator becomes invalid. | |
147 | * If you want to discard the iterator before, you MUST manually call cxTreeVisitorDispose(). | |
148 | * | |
149 | * This iterator is not position-aware in a strict sense, as it does not assume a particular order of elements in the | |
150 | * tree. However, the iterator keeps track of the number of nodes it has passed in a counter variable. | |
151 | * Each node, regardless of the number of passes, is counted only once. | |
152 | * | |
153 | * @note Objects that are pointed to by an iterator are mutable through that iterator. However, if the | |
154 | * underlying data structure is mutated by other means than this iterator (e.g. elements added or removed), | |
155 | * the iterator becomes invalid (regardless of what cxIteratorValid() returns). | |
156 | * | |
157 | * @see CxIterator | |
158 | */ | |
159 | typedef struct cx_tree_visitor_s { | |
160 | /** | |
161 | * The base properties of this iterator. | |
162 | */ | |
163 | struct cx_iterator_base_s base; | |
164 | /** | |
848
6456036bbb37
implement tree continue - fixes #376
Mike Becker <universe@uap-core.de>
parents:
845
diff
changeset
|
165 | * 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
|
166 | */ |
6456036bbb37
implement tree continue - fixes #376
Mike Becker <universe@uap-core.de>
parents:
845
diff
changeset
|
167 | bool skip; |
6456036bbb37
implement tree continue - fixes #376
Mike Becker <universe@uap-core.de>
parents:
845
diff
changeset
|
168 | /** |
845 | 169 | * Offset in the node struct for the children linked list. |
170 | */ | |
171 | ptrdiff_t loc_children; | |
172 | /** | |
173 | * Offset in the node struct for the next pointer. | |
174 | */ | |
175 | ptrdiff_t loc_next; | |
176 | /** | |
177 | * The total number of distinct nodes that have been passed so far. | |
178 | */ | |
179 | size_t counter; | |
180 | /** | |
181 | * The currently observed node. | |
182 | * | |
183 | * This is the same what cxIteratorCurrent() would return. | |
184 | */ | |
185 | void *node; | |
186 | /** | |
187 | * The current depth in the tree. | |
188 | */ | |
189 | size_t depth; | |
190 | /** | |
191 | * The next element in the visitor queue. | |
192 | */ | |
193 | struct cx_tree_visitor_queue_s *queue_next; | |
194 | /** | |
195 | * The last element in the visitor queue. | |
196 | */ | |
197 | struct cx_tree_visitor_queue_s *queue_last; | |
198 | } CxTreeVisitor; | |
199 | ||
200 | /** | |
827
13b40a598d16
first draft of a tree iterator
Mike Becker <universe@uap-core.de>
parents:
826
diff
changeset
|
201 | * 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
|
202 | * @param iter the iterator |
13b40a598d16
first draft of a tree iterator
Mike Becker <universe@uap-core.de>
parents:
826
diff
changeset
|
203 | */ |
845 | 204 | __attribute__((__nonnull__)) |
827
13b40a598d16
first draft of a tree iterator
Mike Becker <universe@uap-core.de>
parents:
826
diff
changeset
|
205 | static inline void cxTreeIteratorDispose(CxTreeIterator *iter) { |
13b40a598d16
first draft of a tree iterator
Mike Becker <universe@uap-core.de>
parents:
826
diff
changeset
|
206 | 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
|
207 | iter->stack = NULL; |
827
13b40a598d16
first draft of a tree iterator
Mike Becker <universe@uap-core.de>
parents:
826
diff
changeset
|
208 | } |
816
425234b05dff
add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
209 | |
822
e2243453127f
add code documentation for tree functions
Mike Becker <universe@uap-core.de>
parents:
816
diff
changeset
|
210 | /** |
845 | 211 | * Releases internal memory of the given tree visitor. |
212 | * @param visitor the visitor | |
213 | */ | |
214 | __attribute__((__nonnull__)) | |
215 | static inline void cxTreeVisitorDispose(CxTreeVisitor *visitor) { | |
216 | struct cx_tree_visitor_queue_s *q = visitor->queue_next; | |
217 | while (q != NULL) { | |
218 | struct cx_tree_visitor_queue_s *next = q->next; | |
219 | free(q); | |
220 | q = next; | |
221 | } | |
222 | } | |
223 | ||
224 | /** | |
848
6456036bbb37
implement tree continue - fixes #376
Mike Becker <universe@uap-core.de>
parents:
845
diff
changeset
|
225 | * 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
|
226 | * also continues the current loop. |
6456036bbb37
implement tree continue - fixes #376
Mike Becker <universe@uap-core.de>
parents:
845
diff
changeset
|
227 | * |
6456036bbb37
implement tree continue - fixes #376
Mike Becker <universe@uap-core.de>
parents:
845
diff
changeset
|
228 | * @param iterator the iterator |
6456036bbb37
implement tree continue - fixes #376
Mike Becker <universe@uap-core.de>
parents:
845
diff
changeset
|
229 | */ |
6456036bbb37
implement tree continue - fixes #376
Mike Becker <universe@uap-core.de>
parents:
845
diff
changeset
|
230 | #define cxTreeIteratorContinue(iterator) (iterator).skip = true; continue |
6456036bbb37
implement tree continue - fixes #376
Mike Becker <universe@uap-core.de>
parents:
845
diff
changeset
|
231 | |
6456036bbb37
implement tree continue - fixes #376
Mike Becker <universe@uap-core.de>
parents:
845
diff
changeset
|
232 | /** |
6456036bbb37
implement tree continue - fixes #376
Mike Becker <universe@uap-core.de>
parents:
845
diff
changeset
|
233 | * 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
|
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 visitor the visitor |
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 cxTreeVisitorContinue(visitor) cxTreeIteratorContinue(visitor) |
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 | /** |
822
e2243453127f
add code documentation for tree functions
Mike Becker <universe@uap-core.de>
parents:
816
diff
changeset
|
241 | * Links a node to a (new) parent. |
e2243453127f
add code documentation for tree functions
Mike Becker <universe@uap-core.de>
parents:
816
diff
changeset
|
242 | * |
e2243453127f
add code documentation for tree functions
Mike Becker <universe@uap-core.de>
parents:
816
diff
changeset
|
243 | * If the node has already a parent, it is unlinked, first. |
845 | 244 | * 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
|
245 | * of all currently existing children. |
822
e2243453127f
add code documentation for tree functions
Mike Becker <universe@uap-core.de>
parents:
816
diff
changeset
|
246 | * |
e2243453127f
add code documentation for tree functions
Mike Becker <universe@uap-core.de>
parents:
816
diff
changeset
|
247 | * @param parent the parent node |
e2243453127f
add code documentation for tree functions
Mike Becker <universe@uap-core.de>
parents:
816
diff
changeset
|
248 | * @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
|
249 | * @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
|
250 | * @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
|
251 | * @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
|
252 | * @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
|
253 | * @see cx_tree_unlink() |
e2243453127f
add code documentation for tree functions
Mike Becker <universe@uap-core.de>
parents:
816
diff
changeset
|
254 | */ |
816
425234b05dff
add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
255 | __attribute__((__nonnull__)) |
425234b05dff
add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
256 | void cx_tree_link( |
425234b05dff
add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
257 | void * restrict parent, |
425234b05dff
add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
258 | void * restrict node, |
425234b05dff
add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
259 | ptrdiff_t loc_parent, |
425234b05dff
add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
260 | ptrdiff_t loc_children, |
425234b05dff
add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
261 | ptrdiff_t loc_prev, |
425234b05dff
add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
262 | ptrdiff_t loc_next |
425234b05dff
add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
263 | ); |
425234b05dff
add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
264 | |
822
e2243453127f
add code documentation for tree functions
Mike Becker <universe@uap-core.de>
parents:
816
diff
changeset
|
265 | /** |
e2243453127f
add code documentation for tree functions
Mike Becker <universe@uap-core.de>
parents:
816
diff
changeset
|
266 | * Unlinks a node from its parent. |
e2243453127f
add code documentation for tree functions
Mike Becker <universe@uap-core.de>
parents:
816
diff
changeset
|
267 | * |
e2243453127f
add code documentation for tree functions
Mike Becker <universe@uap-core.de>
parents:
816
diff
changeset
|
268 | * 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
|
269 | * |
e2243453127f
add code documentation for tree functions
Mike Becker <universe@uap-core.de>
parents:
816
diff
changeset
|
270 | * @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
|
271 | * @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
|
272 | * @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
|
273 | * @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
|
274 | * @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
|
275 | * @see cx_tree_link() |
e2243453127f
add code documentation for tree functions
Mike Becker <universe@uap-core.de>
parents:
816
diff
changeset
|
276 | */ |
816
425234b05dff
add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
277 | __attribute__((__nonnull__)) |
425234b05dff
add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
278 | void cx_tree_unlink( |
425234b05dff
add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
279 | void *node, |
425234b05dff
add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
280 | ptrdiff_t loc_parent, |
425234b05dff
add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
281 | ptrdiff_t loc_children, |
425234b05dff
add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
282 | ptrdiff_t loc_prev, |
425234b05dff
add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
283 | ptrdiff_t loc_next |
425234b05dff
add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
284 | ); |
425234b05dff
add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
285 | |
823
f4faa7f73cb8
declare cx_tree_search_func function pointer
Mike Becker <universe@uap-core.de>
parents:
822
diff
changeset
|
286 | /** |
f4faa7f73cb8
declare cx_tree_search_func function pointer
Mike Becker <universe@uap-core.de>
parents:
822
diff
changeset
|
287 | * Function pointer for a search function. |
f4faa7f73cb8
declare cx_tree_search_func function pointer
Mike Becker <universe@uap-core.de>
parents:
822
diff
changeset
|
288 | * |
f4faa7f73cb8
declare cx_tree_search_func function pointer
Mike Becker <universe@uap-core.de>
parents:
822
diff
changeset
|
289 | * 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
|
290 | * 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
|
291 | * the data. |
f4faa7f73cb8
declare cx_tree_search_func function pointer
Mike Becker <universe@uap-core.de>
parents:
822
diff
changeset
|
292 | * |
826
21840975d541
add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents:
824
diff
changeset
|
293 | * 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
|
294 | * 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
|
295 | * |
823
f4faa7f73cb8
declare cx_tree_search_func function pointer
Mike Becker <universe@uap-core.de>
parents:
822
diff
changeset
|
296 | * 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
|
297 | * 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
|
298 | * 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
|
299 | * 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
|
300 | * prefix of the searched filename, the function would return -1 to indicate |
21840975d541
add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents:
824
diff
changeset
|
301 | * 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
|
302 | * |
f4faa7f73cb8
declare cx_tree_search_func function pointer
Mike Becker <universe@uap-core.de>
parents:
822
diff
changeset
|
303 | * @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
|
304 | * @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
|
305 | * |
f4faa7f73cb8
declare cx_tree_search_func function pointer
Mike Becker <universe@uap-core.de>
parents:
822
diff
changeset
|
306 | * @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
|
307 | * 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
|
308 | * 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
|
309 | */ |
824 | 310 | 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
|
311 | |
826
21840975d541
add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents:
824
diff
changeset
|
312 | |
21840975d541
add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents:
824
diff
changeset
|
313 | /** |
21840975d541
add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents:
824
diff
changeset
|
314 | * Searches for data in a tree. |
21840975d541
add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents:
824
diff
changeset
|
315 | * |
21840975d541
add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents:
824
diff
changeset
|
316 | * 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
|
317 | * 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
|
318 | * to the tree. |
21840975d541
add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents:
824
diff
changeset
|
319 | * |
21840975d541
add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents:
824
diff
changeset
|
320 | * 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
|
321 | * "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
|
322 | * 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
|
323 | * \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
|
324 | * node matching the criteria is returned. |
21840975d541
add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents:
824
diff
changeset
|
325 | * |
21840975d541
add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents:
824
diff
changeset
|
326 | * @param root the root node |
21840975d541
add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents:
824
diff
changeset
|
327 | * @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
|
328 | * @param sfunc the search function |
21840975d541
add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents:
824
diff
changeset
|
329 | * @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
|
330 | * @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
|
331 | * @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
|
332 | * @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
|
333 | * 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
|
334 | * 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
|
335 | */ |
21840975d541
add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents:
824
diff
changeset
|
336 | __attribute__((__nonnull__)) |
21840975d541
add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents:
824
diff
changeset
|
337 | int cx_tree_search( |
21840975d541
add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents:
824
diff
changeset
|
338 | void const *root, |
21840975d541
add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents:
824
diff
changeset
|
339 | void const *data, |
21840975d541
add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents:
824
diff
changeset
|
340 | cx_tree_search_func sfunc, |
21840975d541
add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents:
824
diff
changeset
|
341 | void **result, |
21840975d541
add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents:
824
diff
changeset
|
342 | ptrdiff_t loc_children, |
21840975d541
add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents:
824
diff
changeset
|
343 | ptrdiff_t loc_next |
21840975d541
add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents:
824
diff
changeset
|
344 | ); |
21840975d541
add cx_tree_search() - relates to #165
Mike Becker <universe@uap-core.de>
parents:
824
diff
changeset
|
345 | |
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
|
346 | /** |
845 | 347 | * 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
|
348 | * |
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
|
349 | * @note A tree iterator needs to maintain a stack of visited nodes, which is allocated using stdlib malloc(). |
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
|
350 | * When the iterator becomes invalid, this memory is automatically released. However, if you wish to cancel the |
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
|
351 | * iteration before the iterator becomes invalid by itself, you MUST call cxTreeIteratorDispose() manually to release |
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
|
352 | * 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
|
353 | * |
845 | 354 | * @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
|
355 | * |
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 | * @param root the root node |
833
5c926801f052
vastly simplify tree iterators and add test for creating them
Mike Becker <universe@uap-core.de>
parents:
830
diff
changeset
|
357 | * @param visit_on_exit set to true, when the iterator shall visit a node again 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
|
358 | * @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
|
359 | * @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
|
360 | * @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
|
361 | * @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
|
362 | */ |
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 | __attribute__((__nonnull__)) |
830
c4dae6fe6d5b
commit complicated stuff before simplifying it
Mike Becker <universe@uap-core.de>
parents:
828
diff
changeset
|
364 | CxTreeIterator cx_tree_iterator( |
c4dae6fe6d5b
commit complicated stuff before simplifying it
Mike Becker <universe@uap-core.de>
parents:
828
diff
changeset
|
365 | void *root, |
833
5c926801f052
vastly simplify tree iterators and add test for creating them
Mike Becker <universe@uap-core.de>
parents:
830
diff
changeset
|
366 | 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
|
367 | 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
|
368 | 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
|
369 | ); |
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 | |
845 | 371 | /** |
372 | * Creates a breadth-first iterator for a tree with the specified root node. | |
373 | * | |
374 | * @note A tree visitor needs to maintain a queue of to be visited nodes, which is allocated using stdlib malloc(). | |
375 | * When the visitor becomes invalid, this memory is automatically released. However, if you wish to cancel the | |
376 | * iteration before the visitor becomes invalid by itself, you MUST call cxTreeVisitorDispose() manually to release | |
377 | * the memory. | |
378 | * | |
379 | * @remark The returned iterator does not support cxIteratorFlagRemoval(). | |
380 | * | |
381 | * @param root the root node | |
382 | * @param loc_children offset in the node struct for the children linked list | |
383 | * @param loc_next offset in the node struct for the next pointer | |
384 | * @return the new tree visitor | |
385 | * @see cxTreeVisitorDispose() | |
386 | */ | |
387 | __attribute__((__nonnull__)) | |
388 | CxTreeVisitor cx_tree_visitor( | |
389 | void *root, | |
390 | ptrdiff_t loc_children, | |
391 | ptrdiff_t loc_next | |
392 | ); | |
393 | ||
816
425234b05dff
add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
394 | #ifdef __cplusplus |
425234b05dff
add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
395 | } // extern "C" |
425234b05dff
add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
396 | #endif |
425234b05dff
add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
397 | |
425234b05dff
add first basic low level tree functions
Mike Becker <universe@uap-core.de>
parents:
diff
changeset
|
398 | #endif //UCX_TREE_H |