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 */
35
36 #ifndef UCX_TREE_H
37 #define UCX_TREE_H
38
39 #include "common.h"
40
41 #include "iterator.h"
42
43 #ifdef __cplusplus
44 extern "C" {
45 #endif
46
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 * Base members.
63 */
64 CX_ITERATOR_BASE;
65 /**
66 * Indicates whether the subtree below the current node shall be skipped.
67 */
68 bool skip;
69 /**
70 * Set to true, when the iterator shall visit a node again
71 * when all it's children have been processed.
72 */
73 bool visit_on_exit;
74 /**
75 * True, if this iterator is currently leaving the node.
76 */
77 bool exiting;
78 /**
79 * Offset in the node struct for the children linked list.
80 */
81 ptrdiff_t loc_children;
82 /**
83 * Offset in the node struct for the next pointer.
84 */
85 ptrdiff_t loc_next;
86 /**
87 * The total number of distinct nodes that have been passed so far.
88 */
89 size_t counter;
90 /**
91 * The currently observed node.
92 *
93 * This is the same what cxIteratorCurrent() would return.
94 */
95 void *node;
96 /**
97 * Stores a copy of the next pointer of the visited node.
98 * Allows freeing a node on exit without corrupting the iteration.
99 */
100 void *node_next;
101 /**
102 * Internal stack.
103 * Will be automatically freed once the iterator becomes invalid.
104 *
105 * If you want to discard the iterator before, you need to manually
106 * call cxTreeIteratorDispose().
107 */
108 void **stack;
109 /**
110 * Internal capacity of the stack.
111 */
112 size_t stack_capacity;
113 union {
114 /**
115 * Internal stack size.
116 */
117 size_t stack_size;
118 /**
119 * The current depth in the tree.
120 */
121 size_t depth;
122 };
123 } CxTreeIterator;
124
125 /**
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 * Base members.
162 */
163 CX_ITERATOR_BASE;
164 /**
165 * Indicates whether the subtree below the current node shall be skipped.
166 */
167 bool skip;
168 /**
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 /**
201 * Releases internal memory of the given tree iterator.
202 * @param iter the iterator
203 */
204 __attribute__((__nonnull__))
205 static inline void cxTreeIteratorDispose(CxTreeIterator *iter) {
206 free(iter->stack);
207 iter->stack = NULL;
208 }
209
210 /**
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 /**
225 * Advises the iterator to skip the subtree below the current node and
226 * also continues the current loop.
227 *
228 * @param iterator the iterator
229 */
230 #define cxTreeIteratorContinue(iterator) (iterator).skip = true; continue
231
232 /**
233 * Advises the visitor to skip the subtree below the current node and
234 * also continues the current loop.
235 *
236 * @param visitor the visitor
237 */
238 #define cxTreeVisitorContinue(visitor) cxTreeIteratorContinue(visitor)
239
240 /**
241 * Links a node to a (new) parent.
242 *
243 * If the node has already a parent, it is unlinked, first.
244 * If the parent has children already, the node is \em prepended to the list
245 * of all currently existing children.
246 *
247 * @param parent the parent node
248 * @param node the node that shall be linked
249 * @param loc_parent offset in the node struct for the parent pointer
250 * @param loc_children offset in the node struct for the children linked list
251 * @param loc_prev offset in the node struct for the prev pointer
252 * @param loc_next offset in the node struct for the next pointer
253 * @see cx_tree_unlink()
254 */
255 __attribute__((__nonnull__))
256 void cx_tree_link(
257 void * restrict parent,
258 void * restrict node,
259 ptrdiff_t loc_parent,
260 ptrdiff_t loc_children,
261 ptrdiff_t loc_prev,
262 ptrdiff_t loc_next
263 );
264
265 /**
266 * Unlinks a node from its parent.
267 *
268 * If the node has no parent, this function does nothing.
269 *
270 * @param node the node that shall be unlinked from its parent
271 * @param loc_parent offset in the node struct for the parent pointer
272 * @param loc_children offset in the node struct for the children linked list
273 * @param loc_prev offset in the node struct for the prev pointer
274 * @param loc_next offset in the node struct for the next pointer
275 * @see cx_tree_link()
276 */
277 __attribute__((__nonnull__))
278 void cx_tree_unlink(
279 void *node,
280 ptrdiff_t loc_parent,
281 ptrdiff_t loc_children,
282 ptrdiff_t loc_prev,
283 ptrdiff_t loc_next
284 );
285
286 /**
287 * Function pointer for a search function.
288 *
289 * A function of this kind shall check if the specified \p node
290 * contains the given \p data or if one of the children might contain
291 * the data.
292 *
293 * The function should use the returned integer to indicate how close the
294 * match is, where a negative number means that it does not match at all.
295 *
296 * For example if a tree stores file path information, a node that is
297 * describing a parent directory of a filename that is searched, shall
298 * return a positive number to indicate that a child node might contain the
299 * searched item. On the other hand, if the node denotes a path that is not a
300 * prefix of the searched filename, the function would return -1 to indicate
301 * that * the search does not need to be continued in that branch.
302 *
303 * @param node the node that is currently investigated
304 * @param data the data that is searched for
305 *
306 * @return 0 if the node contains the data,
307 * positive if one of the children might contain the data,
308 * negative if neither the node, nor the children contains the data
309 */
310 typedef int (*cx_tree_search_func)(void const *node, void const* data);
311
312
313 /**
314 * Searches for data in a tree.
315 *
316 * When the data cannot be found exactly, the search function might return a
317 * closest result which might be a good starting point for adding a new node
318 * to the tree.
319 *
320 * Depending on the tree structure it is not necessarily guaranteed that the
321 * "closest" match is uniquely defined. This function will search for a node
322 * with the best match according to the \p sfunc (meaning: the return value of
323 * \p sfunc which is closest to zero). If that is also ambiguous, an arbitrary
324 * node matching the criteria is returned.
325 *
326 * @param root the root node
327 * @param data the data to search for
328 * @param sfunc the search function
329 * @param result where the result shall be stored
330 * @param loc_children offset in the node struct for the children linked list
331 * @param loc_next offset in the node struct for the next pointer
332 * @return zero if the node was found exactly, positive if a node was found that
333 * could contain the node (but doesn't right now), negative if the tree does not
334 * contain any node that might be related to the searched data
335 */
336 __attribute__((__nonnull__))
337 int cx_tree_search(
338 void const *root,
339 void const *data,
340 cx_tree_search_func sfunc,
341 void **result,
342 ptrdiff_t loc_children,
343 ptrdiff_t loc_next
344 );
345
346 /**
347 * Creates a depth-first iterator for a tree with the specified root node.
348 *
349 * @note A tree iterator needs to maintain a stack of visited nodes, which is allocated using stdlib malloc().
350 * When the iterator becomes invalid, this memory is automatically released. However, if you wish to cancel the
351 * iteration before the iterator becomes invalid by itself, you MUST call cxTreeIteratorDispose() manually to release
352 * the memory.
353 *
354 * @remark The returned iterator does not support cxIteratorFlagRemoval().
355 *
356 * @param root the root node
357 * @param visit_on_exit set to true, when the iterator shall visit a node again after processing all children
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 iterator
361 * @see cxTreeIteratorDispose()
362 */
363 __attribute__((__nonnull__))
364 CxTreeIterator cx_tree_iterator(
365 void *root,
366 bool visit_on_exit,
367 ptrdiff_t loc_children,
368 ptrdiff_t loc_next
369 );
370
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
394 #ifdef __cplusplus
395 } // extern "C"
396 #endif
397
398 #endif //UCX_TREE_H
399