Mercurial > hg > dav / file comparison

comparison: ucx/cx/tree.h

ucx/cx/tree.h

changeset 818
bc782cca0759
parent 816
839fefbdedc7
equal deleted inserted replaced
817:22257f6d06a3 818:bc782cca0759
1 /* 1 /*
2 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER. 2 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER.
3 * 3 *
4 * Copyright 2021 Mike Becker, Olaf Wintermann All rights reserved. 4 * Copyright 2024 Mike Becker, Olaf Wintermann All rights reserved.
5 * 5 *
6 * Redistribution and use in source and binary forms, with or without 6 * Redistribution and use in source and binary forms, with or without
7 * modification, are permitted provided that the following conditions are met: 7 * modification, are permitted provided that the following conditions are met:
8 * 8 *
9 * 1. Redistributions of source code must retain the above copyright 9 * 1. Redistributions of source code must retain the above copyright
26 * POSSIBILITY OF SUCH DAMAGE. 26 * POSSIBILITY OF SUCH DAMAGE.
27 */ 27 */
28 /** 28 /**
29 * \file tree.h 29 * \file tree.h
30 * \brief Interface for tree implementations. 30 * \brief Interface for tree implementations.
31 * \author Mike Becker
31 * \author Olaf Wintermann 32 * \author Olaf Wintermann
32 * \author Mike Becker
33 * \version 3.0
34 * \copyright 2-Clause BSD License 33 * \copyright 2-Clause BSD License
35 */ 34 */
36 35
37 #ifndef UCX_TREE_H 36 #ifndef UCX_TREE_H
38 #define UCX_TREE_H 37 #define UCX_TREE_H
39 38
40 #include "common.h" 39 #include "common.h"
41 #include "allocator.h" 40
41 #include "iterator.h"
42 42
43 #ifdef __cplusplus 43 #ifdef __cplusplus
44 extern "C" { 44 extern "C" {
45 #endif 45 #endif
46 46
47 /** 47 /**
48 * Adds a sibling to the current tree node. 48 * A depth-first tree iterator.
49 * 49 *
50 * In case your struct does not have a \p prev or a \p parent pointer, 50 * This iterator is not position-aware in a strict sense, as it does not assume a particular order of elements in the
51 * specify a negative location. The location of the \p next pointer is 51 * tree. However, the iterator keeps track of the number of nodes it has passed in a counter variable.
52 * mandatory. 52 * Each node, regardless of the number of passes, is counted only once.
53 * 53 *
54 * \attention Do not use this function to add siblings in a tree where the 54 * @note Objects that are pointed to by an iterator are mutable through that iterator. However, if the
55 * nodes store a pointer to the last sibling because that would not be modified by this function. 55 * underlying data structure is mutated by other means than this iterator (e.g. elements added or removed),
56 * 56 * the iterator becomes invalid (regardless of what cxIteratorValid() returns).
57 * \remark If yo do not provide a location to the parent pointer, a call to this function is 57 *
58 * effectively the same as a call to cx_linked_list_add(). 58 * @see CxIterator
59 * 59 */
60 * @param node a pointer to the node 60 typedef struct cx_tree_iterator_s {
61 * @param loc_prev the location of a \c prev pointer within your node struct 61 /**
62 * @param loc_next the location of a \c next pointer within your node struct 62 * Base members.
63 * @param loc_parent the location of a \c parent pointer within your node struct 63 */
64 * @param new_node the new node that shall be added as a sibling 64 CX_ITERATOR_BASE;
65 */ 65 /**
66 void cx_tree_add_sibling(void *node, 66 * Indicates whether the subtree below the current node shall be skipped.
67 ptrdiff_t loc_prev, ptrdiff_t loc_next, 67 */
68 ptrdiff_t loc_parent, 68 bool skip;
69 void *new_node) 69 /**
70 __attribute__((__nonnull__)); 70 * Set to true, when the iterator shall visit a node again
71 71 * when all it's children have been processed.
72 /** 72 */
73 * Adds a node to the list of children. 73 bool visit_on_exit;
74 * 74 /**
75 * \par Example with a full structure 75 * True, if this iterator is currently leaving the node.
76 * A full tree node structure may look like this: 76 */
77 * \code 77 bool exiting;
78 * typedef struct MyTreeNode MyTreeNode; 78 /**
79 * struct MyTreeNode { 79 * Offset in the node struct for the children linked list.
80 * MyTreeNode* parent; 80 */
81 * MyTreeNode* first_child; 81 ptrdiff_t loc_children;
82 * MyTreeNode* last_child; 82 /**
83 * MyTreeNode* prev_sibling; 83 * Offset in the node struct for the next pointer.
84 * MyTreeNode* next_sibling; 84 */
85 * // ...contents... 85 ptrdiff_t loc_next;
86 * } 86 /**
87 * \endcode 87 * The total number of distinct nodes that have been passed so far.
88 * Adding a new child to a node with the above structure can be performed with the following call: 88 */
89 * \code 89 size_t counter;
90 * MyTreeNode *node, *child; // given 90 /**
91 * cx_tree_add_child(&node->first_child, &node->last_child, 91 * The currently observed node.
92 * offsetof(MyTreeNode, prev_sibling), offsetof(MyTreeNode, next_sibling), 92 *
93 * child, offsetof(MyTreeNode, parent), node); 93 * This is the same what cxIteratorCurrent() would return.
94 * \endcode 94 */
95 * 95 void *node;
96 * \par Example with a reduced structure 96 /**
97 * The minimal reasonable structure with parent pointer looks like this: 97 * Stores a copy of the next pointer of the visited node.
98 * \code 98 * Allows freeing a node on exit without corrupting the iteration.
99 * typedef struct MyTreeNode MyTreeNode; 99 */
100 * struct MyTreeNode { 100 void *node_next;
101 * MyTreeNode* parent; 101 /**
102 * MyTreeNode* children; 102 * Internal stack.
103 * MyTreeNode* next_sibling; 103 * Will be automatically freed once the iterator becomes invalid.
104 * // ...contents... 104 *
105 * } 105 * If you want to discard the iterator before, you need to manually
106 * \endcode 106 * call cxTreeIteratorDispose().
107 * This simplifies the function call to: 107 */
108 * \code 108 void **stack;
109 * MyTreeNode *node, *child; // given 109 /**
110 * cx_tree_add_child(&node->children, NULL, -1, offsetof(MyTreeNode, next_sibling), 110 * Internal capacity of the stack.
111 * child, offsetof(MyTreeNode, parent), node); 111 */
112 * \endcode 112 size_t stack_capacity;
113 * 113 union {
114 * \remark If your tree structure does not possess a parent pointer, a call to this function is 114 /**
115 * effectively the same as a call to cx_linked_list_add(). 115 * Internal stack size.
116 * 116 */
117 * @param children_begin a pointer to the begin node pointer (if your list has one) 117 size_t stack_size;
118 * @param children_end a pointer to the end node pointer (if your list has one) 118 /**
119 * @param loc_prev the location of a \c prev pointer within your node struct 119 * The current depth in the tree.
120 * @param loc_next the location of a \c next pointer within your node struct 120 */
121 * @param new_node a pointer to the node that shall be appended 121 size_t depth;
122 * @param loc_parent the location of a \c parent pointer within your node struct 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 *
123 * @param parent the parent node 247 * @param parent the parent node
124 */ 248 * @param node the node that shall be linked
125 void cx_tree_add_child(void **children_begin, void **children_end, 249 * @param loc_parent offset in the node struct for the parent pointer
126 ptrdiff_t loc_prev, ptrdiff_t loc_next, void *new_node, 250 * @param loc_children offset in the node struct for the children linked list
127 ptrdiff_t loc_parent, void *parent) 251 * @param loc_prev offset in the node struct for the prev pointer
128 __attribute__((__nonnull__ (5))); 252 * @param loc_next offset in the node struct for the next pointer
129 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 );
130 393
131 #ifdef __cplusplus 394 #ifdef __cplusplus
132 } // extern "C" 395 } // extern "C"
133 #endif 396 #endif
134 397
135 #endif // UCX_TREE_H 398 #endif //UCX_TREE_H
136

Mercurial Repository: dav

mercurial