Wed, 20 Mar 2024 23:31:41 +0100
add cx_tree_visitor()
1 /*
2 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER.
3 *
4 * Copyright 2024 Mike Becker, Olaf Wintermann All rights reserved.
5 *
6 * Redistribution and use in source and binary forms, with or without
7 * modification, are permitted provided that the following conditions are met:
8 *
9 * 1. Redistributions of source code must retain the above copyright
10 * notice, this list of conditions and the following disclaimer.
11 *
12 * 2. Redistributions in binary form must reproduce the above copyright
13 * notice, this list of conditions and the following disclaimer in the
14 * documentation and/or other materials provided with the distribution.
15 *
16 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
17 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
18 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
19 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
20 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
21 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
22 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
23 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
24 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
25 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
26 * POSSIBILITY OF SUCH DAMAGE.
27 */
28 /**
29 * \file tree.h
30 * \brief Interface for tree implementations.
31 * \author Mike Becker
32 * \author Olaf Wintermann
33 * \copyright 2-Clause BSD License
34 */
36 #ifndef UCX_TREE_H
37 #define UCX_TREE_H
39 #include "common.h"
41 #include "iterator.h"
43 #ifdef __cplusplus
44 extern "C" {
45 #endif
47 /**
48 * A depth-first tree iterator.
49 *
50 * This iterator is not position-aware in a strict sense, as it does not assume a particular order of elements in the
51 * tree. However, the iterator keeps track of the number of nodes it has passed in a counter variable.
52 * Each node, regardless of the number of passes, is counted only once.
53 *
54 * @note Objects that are pointed to by an iterator are mutable through that iterator. However, if the
55 * underlying data structure is mutated by other means than this iterator (e.g. elements added or removed),
56 * the iterator becomes invalid (regardless of what cxIteratorValid() returns).
57 *
58 * @see CxIterator
59 */
60 typedef struct cx_tree_iterator_s {
61 /**
62 * The base properties of this iterator.
63 */
64 struct cx_iterator_base_s base;
65 /**
66 * Set to true, when the iterator shall visit a node again
67 * when all it's children have been processed.
68 */
69 bool visit_on_exit;
70 /**
71 * True, if this iterator is currently leaving the node.
72 */
73 bool exiting;
74 /**
75 * Offset in the node struct for the children linked list.
76 */
77 ptrdiff_t loc_children;
78 /**
79 * Offset in the node struct for the next pointer.
80 */
81 ptrdiff_t loc_next;
82 /**
83 * The total number of distinct nodes that have been passed so far.
84 */
85 size_t counter;
86 /**
87 * The currently observed node.
88 *
89 * This is the same what cxIteratorCurrent() would return.
90 */
91 void *node;
92 /**
93 * Stores a copy of the next pointer of the visited node.
94 * Allows freeing a node on exit without corrupting the iteration.
95 */
96 void *next;
97 /**
98 * Internal stack.
99 * Will be automatically freed once the iterator becomes invalid.
100 *
101 * If you want to discard the iterator before, you need to manually
102 * call cxTreeIteratorDispose().
103 */
104 void **stack;
105 /**
106 * Internal capacity of the stack.
107 */
108 size_t stack_capacity;
109 union {
110 /**
111 * Internal stack size.
112 */
113 size_t stack_size;
114 /**
115 * The current depth in the tree.
116 */
117 size_t depth;
118 };
119 } CxTreeIterator;
121 /**
122 * An element in a visitor queue.
123 */
124 struct cx_tree_visitor_queue_s {
125 /**
126 * The tree node to visit.
127 */
128 void *node;
129 /**
130 * The depth of the node.
131 */
132 size_t depth;
133 /**
134 * The next element in the queue or \c NULL.
135 */
136 struct cx_tree_visitor_queue_s *next;
137 };
139 /**
140 * A breadth-first tree iterator.
141 *
142 * This iterator needs to maintain a visitor queue that will be automatically freed once the iterator becomes invalid.
143 * If you want to discard the iterator before, you MUST manually call cxTreeVisitorDispose().
144 *
145 * This iterator is not position-aware in a strict sense, as it does not assume a particular order of elements in the
146 * tree. However, the iterator keeps track of the number of nodes it has passed in a counter variable.
147 * Each node, regardless of the number of passes, is counted only once.
148 *
149 * @note Objects that are pointed to by an iterator are mutable through that iterator. However, if the
150 * underlying data structure is mutated by other means than this iterator (e.g. elements added or removed),
151 * the iterator becomes invalid (regardless of what cxIteratorValid() returns).
152 *
153 * @see CxIterator
154 */
155 typedef struct cx_tree_visitor_s {
156 /**
157 * The base properties of this iterator.
158 */
159 struct cx_iterator_base_s base;
160 /**
161 * Offset in the node struct for the children linked list.
162 */
163 ptrdiff_t loc_children;
164 /**
165 * Offset in the node struct for the next pointer.
166 */
167 ptrdiff_t loc_next;
168 /**
169 * The total number of distinct nodes that have been passed so far.
170 */
171 size_t counter;
172 /**
173 * The currently observed node.
174 *
175 * This is the same what cxIteratorCurrent() would return.
176 */
177 void *node;
178 /**
179 * The current depth in the tree.
180 */
181 size_t depth;
182 /**
183 * The next element in the visitor queue.
184 */
185 struct cx_tree_visitor_queue_s *queue_next;
186 /**
187 * The last element in the visitor queue.
188 */
189 struct cx_tree_visitor_queue_s *queue_last;
190 } CxTreeVisitor;
192 /**
193 * Releases internal memory of the given tree iterator.
194 * @param iter the iterator
195 */
196 __attribute__((__nonnull__))
197 static inline void cxTreeIteratorDispose(CxTreeIterator *iter) {
198 free(iter->stack);
199 iter->stack = NULL;
200 }
202 /**
203 * Releases internal memory of the given tree visitor.
204 * @param visitor the visitor
205 */
206 __attribute__((__nonnull__))
207 static inline void cxTreeVisitorDispose(CxTreeVisitor *visitor) {
208 struct cx_tree_visitor_queue_s *q = visitor->queue_next;
209 while (q != NULL) {
210 struct cx_tree_visitor_queue_s *next = q->next;
211 free(q);
212 q = next;
213 }
214 }
216 /**
217 * Links a node to a (new) parent.
218 *
219 * If the node has already a parent, it is unlinked, first.
220 * If the parent has children already, the node is \em prepended to the list
221 * of all currently existing children.
222 *
223 * @param parent the parent node
224 * @param node the node that shall be linked
225 * @param loc_parent offset in the node struct for the parent pointer
226 * @param loc_children offset in the node struct for the children linked list
227 * @param loc_prev offset in the node struct for the prev pointer
228 * @param loc_next offset in the node struct for the next pointer
229 * @see cx_tree_unlink()
230 */
231 __attribute__((__nonnull__))
232 void cx_tree_link(
233 void * restrict parent,
234 void * restrict node,
235 ptrdiff_t loc_parent,
236 ptrdiff_t loc_children,
237 ptrdiff_t loc_prev,
238 ptrdiff_t loc_next
239 );
241 /**
242 * Unlinks a node from its parent.
243 *
244 * If the node has no parent, this function does nothing.
245 *
246 * @param node the node that shall be unlinked from its parent
247 * @param loc_parent offset in the node struct for the parent pointer
248 * @param loc_children offset in the node struct for the children linked list
249 * @param loc_prev offset in the node struct for the prev pointer
250 * @param loc_next offset in the node struct for the next pointer
251 * @see cx_tree_link()
252 */
253 __attribute__((__nonnull__))
254 void cx_tree_unlink(
255 void *node,
256 ptrdiff_t loc_parent,
257 ptrdiff_t loc_children,
258 ptrdiff_t loc_prev,
259 ptrdiff_t loc_next
260 );
262 /**
263 * Function pointer for a search function.
264 *
265 * A function of this kind shall check if the specified \p node
266 * contains the given \p data or if one of the children might contain
267 * the data.
268 *
269 * The function should use the returned integer to indicate how close the
270 * match is, where a negative number means that it does not match at all.
271 *
272 * For example if a tree stores file path information, a node that is
273 * describing a parent directory of a filename that is searched, shall
274 * return a positive number to indicate that a child node might contain the
275 * searched item. On the other hand, if the node denotes a path that is not a
276 * prefix of the searched filename, the function would return -1 to indicate
277 * that * the search does not need to be continued in that branch.
278 *
279 * @param node the node that is currently investigated
280 * @param data the data that is searched for
281 *
282 * @return 0 if the node contains the data,
283 * positive if one of the children might contain the data,
284 * negative if neither the node, nor the children contains the data
285 */
286 typedef int (*cx_tree_search_func)(void const *node, void const* data);
289 /**
290 * Searches for data in a tree.
291 *
292 * When the data cannot be found exactly, the search function might return a
293 * closest result which might be a good starting point for adding a new node
294 * to the tree.
295 *
296 * Depending on the tree structure it is not necessarily guaranteed that the
297 * "closest" match is uniquely defined. This function will search for a node
298 * with the best match according to the \p sfunc (meaning: the return value of
299 * \p sfunc which is closest to zero). If that is also ambiguous, an arbitrary
300 * node matching the criteria is returned.
301 *
302 * @param root the root node
303 * @param data the data to search for
304 * @param sfunc the search function
305 * @param result where the result shall be stored
306 * @param loc_children offset in the node struct for the children linked list
307 * @param loc_next offset in the node struct for the next pointer
308 * @return zero if the node was found exactly, positive if a node was found that
309 * could contain the node (but doesn't right now), negative if the tree does not
310 * contain any node that might be related to the searched data
311 */
312 __attribute__((__nonnull__))
313 int cx_tree_search(
314 void const *root,
315 void const *data,
316 cx_tree_search_func sfunc,
317 void **result,
318 ptrdiff_t loc_children,
319 ptrdiff_t loc_next
320 );
322 /**
323 * Creates a depth-first iterator for a tree with the specified root node.
324 *
325 * @note A tree iterator needs to maintain a stack of visited nodes, which is allocated using stdlib malloc().
326 * When the iterator becomes invalid, this memory is automatically released. However, if you wish to cancel the
327 * iteration before the iterator becomes invalid by itself, you MUST call cxTreeIteratorDispose() manually to release
328 * the memory.
329 *
330 * @remark The returned iterator does not support cxIteratorFlagRemoval().
331 *
332 * @param root the root node
333 * @param visit_on_exit set to true, when the iterator shall visit a node again after processing all children
334 * @param loc_children offset in the node struct for the children linked list
335 * @param loc_next offset in the node struct for the next pointer
336 * @return the new tree iterator
337 * @see cxTreeIteratorDispose()
338 */
339 __attribute__((__nonnull__))
340 CxTreeIterator cx_tree_iterator(
341 void *root,
342 bool visit_on_exit,
343 ptrdiff_t loc_children,
344 ptrdiff_t loc_next
345 );
347 /**
348 * Creates a breadth-first iterator for a tree with the specified root node.
349 *
350 * @note A tree visitor needs to maintain a queue of to be visited nodes, which is allocated using stdlib malloc().
351 * When the visitor becomes invalid, this memory is automatically released. However, if you wish to cancel the
352 * iteration before the visitor becomes invalid by itself, you MUST call cxTreeVisitorDispose() manually to release
353 * the memory.
354 *
355 * @remark The returned iterator does not support cxIteratorFlagRemoval().
356 *
357 * @param root the root node
358 * @param loc_children offset in the node struct for the children linked list
359 * @param loc_next offset in the node struct for the next pointer
360 * @return the new tree visitor
361 * @see cxTreeVisitorDispose()
362 */
363 __attribute__((__nonnull__))
364 CxTreeVisitor cx_tree_visitor(
365 void *root,
366 ptrdiff_t loc_children,
367 ptrdiff_t loc_next
368 );
370 #ifdef __cplusplus
371 } // extern "C"
372 #endif
374 #endif //UCX_TREE_H