Wed, 30 Oct 2024 12:23:52 +0100
add textarea (WINUI)
253
087cc9216f28
initial newapi GTK port
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
1 | /* |
087cc9216f28
initial newapi GTK port
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
2 | * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER. |
087cc9216f28
initial newapi GTK port
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
3 | * |
087cc9216f28
initial newapi GTK port
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
4 | * Copyright 2024 Mike Becker, Olaf Wintermann All rights reserved. |
087cc9216f28
initial newapi GTK port
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
5 | * |
087cc9216f28
initial newapi GTK port
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
6 | * Redistribution and use in source and binary forms, with or without |
087cc9216f28
initial newapi GTK port
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
7 | * modification, are permitted provided that the following conditions are met: |
087cc9216f28
initial newapi GTK port
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
8 | * |
087cc9216f28
initial newapi GTK port
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
9 | * 1. Redistributions of source code must retain the above copyright |
087cc9216f28
initial newapi GTK port
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
10 | * notice, this list of conditions and the following disclaimer. |
087cc9216f28
initial newapi GTK port
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
11 | * |
087cc9216f28
initial newapi GTK port
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
12 | * 2. Redistributions in binary form must reproduce the above copyright |
087cc9216f28
initial newapi GTK port
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
13 | * notice, this list of conditions and the following disclaimer in the |
087cc9216f28
initial newapi GTK port
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
14 | * documentation and/or other materials provided with the distribution. |
087cc9216f28
initial newapi GTK port
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
15 | * |
087cc9216f28
initial newapi GTK port
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
16 | * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" |
087cc9216f28
initial newapi GTK port
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
17 | * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE |
087cc9216f28
initial newapi GTK port
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
18 | * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE |
087cc9216f28
initial newapi GTK port
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
19 | * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE |
087cc9216f28
initial newapi GTK port
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
20 | * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR |
087cc9216f28
initial newapi GTK port
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
21 | * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF |
087cc9216f28
initial newapi GTK port
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
22 | * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS |
087cc9216f28
initial newapi GTK port
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
23 | * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN |
087cc9216f28
initial newapi GTK port
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
24 | * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) |
087cc9216f28
initial newapi GTK port
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
25 | * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE |
087cc9216f28
initial newapi GTK port
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
26 | * POSSIBILITY OF SUCH DAMAGE. |
087cc9216f28
initial newapi GTK port
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
27 | */ |
087cc9216f28
initial newapi GTK port
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
28 | /** |
087cc9216f28
initial newapi GTK port
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
29 | * \file tree.h |
087cc9216f28
initial newapi GTK port
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
30 | * \brief Interface for tree implementations. |
087cc9216f28
initial newapi GTK port
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
31 | * \author Mike Becker |
087cc9216f28
initial newapi GTK port
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
32 | * \author Olaf Wintermann |
087cc9216f28
initial newapi GTK port
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
33 | * \copyright 2-Clause BSD License |
087cc9216f28
initial newapi GTK port
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
34 | */ |
087cc9216f28
initial newapi GTK port
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
35 | |
087cc9216f28
initial newapi GTK port
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
36 | #ifndef UCX_TREE_H |
087cc9216f28
initial newapi GTK port
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
37 | #define UCX_TREE_H |
087cc9216f28
initial newapi GTK port
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
38 | |
087cc9216f28
initial newapi GTK port
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
39 | #include "common.h" |
087cc9216f28
initial newapi GTK port
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
40 | |
324 | 41 | #include "collection.h" |
42 | ||
253
087cc9216f28
initial newapi GTK port
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
43 | #ifdef __cplusplus |
087cc9216f28
initial newapi GTK port
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
44 | extern "C" { |
087cc9216f28
initial newapi GTK port
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
45 | #endif |
087cc9216f28
initial newapi GTK port
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
46 | |
324 | 47 | /** |
48 | * A depth-first tree iterator. | |
49 | * | |
50 | * This iterator is not position-aware in a strict sense, as it does not assume | |
51 | * a particular order of elements in the tree. However, the iterator keeps track | |
52 | * of the number of nodes it has passed in a counter variable. | |
53 | * Each node, regardless of the number of passes, is counted only once. | |
54 | * | |
55 | * @note Objects that are pointed to by an iterator are mutable through that | |
56 | * iterator. However, if the | |
57 | * underlying data structure is mutated by other means than this iterator (e.g. | |
58 | * elements added or removed), the iterator becomes invalid (regardless of what | |
59 | * cxIteratorValid() returns). | |
60 | * | |
61 | * @see CxIterator | |
62 | */ | |
63 | typedef struct cx_tree_iterator_s { | |
64 | /** | |
65 | * Base members. | |
66 | */ | |
67 | CX_ITERATOR_BASE; | |
68 | /** | |
69 | * Indicates whether the subtree below the current node shall be skipped. | |
70 | */ | |
71 | bool skip; | |
72 | /** | |
73 | * Set to true, when the iterator shall visit a node again | |
74 | * when all it's children have been processed. | |
75 | */ | |
76 | bool visit_on_exit; | |
77 | /** | |
78 | * True, if this iterator is currently leaving the node. | |
79 | */ | |
80 | bool exiting; | |
81 | /** | |
82 | * Offset in the node struct for the children linked list. | |
83 | */ | |
84 | ptrdiff_t loc_children; | |
85 | /** | |
86 | * Offset in the node struct for the next pointer. | |
87 | */ | |
88 | ptrdiff_t loc_next; | |
89 | /** | |
90 | * The total number of distinct nodes that have been passed so far. | |
91 | */ | |
92 | size_t counter; | |
93 | /** | |
94 | * The currently observed node. | |
95 | * | |
96 | * This is the same what cxIteratorCurrent() would return. | |
97 | */ | |
98 | void *node; | |
99 | /** | |
100 | * Stores a copy of the next pointer of the visited node. | |
101 | * Allows freeing a node on exit without corrupting the iteration. | |
102 | */ | |
103 | void *node_next; | |
104 | /** | |
105 | * Internal stack. | |
106 | * Will be automatically freed once the iterator becomes invalid. | |
107 | * | |
108 | * If you want to discard the iterator before, you need to manually | |
109 | * call cxTreeIteratorDispose(). | |
110 | */ | |
111 | void **stack; | |
112 | /** | |
113 | * Internal capacity of the stack. | |
114 | */ | |
115 | size_t stack_capacity; | |
116 | union { | |
117 | /** | |
118 | * Internal stack size. | |
119 | */ | |
120 | size_t stack_size; | |
121 | /** | |
122 | * The current depth in the tree. | |
123 | */ | |
124 | size_t depth; | |
125 | }; | |
126 | } CxTreeIterator; | |
253
087cc9216f28
initial newapi GTK port
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
127 | |
324 | 128 | /** |
129 | * An element in a visitor queue. | |
130 | */ | |
131 | struct cx_tree_visitor_queue_s { | |
132 | /** | |
133 | * The tree node to visit. | |
134 | */ | |
135 | void *node; | |
136 | /** | |
137 | * The depth of the node. | |
138 | */ | |
139 | size_t depth; | |
140 | /** | |
141 | * The next element in the queue or \c NULL. | |
142 | */ | |
143 | struct cx_tree_visitor_queue_s *next; | |
144 | }; | |
145 | ||
146 | /** | |
147 | * A breadth-first tree iterator. | |
148 | * | |
149 | * This iterator needs to maintain a visitor queue that will be automatically | |
150 | * freed once the iterator becomes invalid. | |
151 | * If you want to discard the iterator before, you MUST manually call | |
152 | * cxTreeVisitorDispose(). | |
153 | * | |
154 | * This iterator is not position-aware in a strict sense, as it does not assume | |
155 | * a particular order of elements in the tree. However, the iterator keeps track | |
156 | * of the number of nodes it has passed in a counter variable. | |
157 | * Each node, regardless of the number of passes, is counted only once. | |
158 | * | |
159 | * @note Objects that are pointed to by an iterator are mutable through that | |
160 | * iterator. However, if the | |
161 | * underlying data structure is mutated by other means than this iterator (e.g. | |
162 | * elements added or removed), the iterator becomes invalid (regardless of what | |
163 | * cxIteratorValid() returns). | |
164 | * | |
165 | * @see CxIterator | |
166 | */ | |
167 | typedef struct cx_tree_visitor_s { | |
168 | /** | |
169 | * Base members. | |
170 | */ | |
171 | CX_ITERATOR_BASE; | |
172 | /** | |
173 | * Indicates whether the subtree below the current node shall be skipped. | |
174 | */ | |
175 | bool skip; | |
176 | /** | |
177 | * Offset in the node struct for the children linked list. | |
178 | */ | |
179 | ptrdiff_t loc_children; | |
180 | /** | |
181 | * Offset in the node struct for the next pointer. | |
182 | */ | |
183 | ptrdiff_t loc_next; | |
184 | /** | |
185 | * The total number of distinct nodes that have been passed so far. | |
186 | */ | |
187 | size_t counter; | |
188 | /** | |
189 | * The currently observed node. | |
190 | * | |
191 | * This is the same what cxIteratorCurrent() would return. | |
192 | */ | |
193 | void *node; | |
194 | /** | |
195 | * The current depth in the tree. | |
196 | */ | |
197 | size_t depth; | |
198 | /** | |
199 | * The next element in the visitor queue. | |
200 | */ | |
201 | struct cx_tree_visitor_queue_s *queue_next; | |
202 | /** | |
203 | * The last element in the visitor queue. | |
204 | */ | |
205 | struct cx_tree_visitor_queue_s *queue_last; | |
206 | } CxTreeVisitor; | |
207 | ||
208 | /** | |
209 | * Releases internal memory of the given tree iterator. | |
210 | * @param iter the iterator | |
211 | */ | |
212 | __attribute__((__nonnull__)) | |
213 | static inline void cxTreeIteratorDispose(CxTreeIterator *iter) { | |
214 | free(iter->stack); | |
215 | iter->stack = NULL; | |
216 | } | |
217 | ||
218 | /** | |
219 | * Releases internal memory of the given tree visitor. | |
220 | * @param visitor the visitor | |
221 | */ | |
222 | __attribute__((__nonnull__)) | |
223 | static inline void cxTreeVisitorDispose(CxTreeVisitor *visitor) { | |
224 | struct cx_tree_visitor_queue_s *q = visitor->queue_next; | |
225 | while (q != NULL) { | |
226 | struct cx_tree_visitor_queue_s *next = q->next; | |
227 | free(q); | |
228 | q = next; | |
229 | } | |
230 | } | |
231 | ||
232 | /** | |
233 | * Advises the iterator to skip the subtree below the current node and | |
234 | * also continues the current loop. | |
235 | * | |
236 | * @param iterator the iterator | |
237 | */ | |
238 | #define cxTreeIteratorContinue(iterator) (iterator).skip = true; continue | |
239 | ||
240 | /** | |
241 | * Advises the visitor to skip the subtree below the current node and | |
242 | * also continues the current loop. | |
243 | * | |
244 | * @param visitor the visitor | |
245 | */ | |
246 | #define cxTreeVisitorContinue(visitor) cxTreeIteratorContinue(visitor) | |
247 | ||
248 | /** | |
249 | * Links a node to a (new) parent. | |
250 | * | |
251 | * If the node has already a parent, it is unlinked, first. | |
252 | * If the parent has children already, the node is \em appended to the list | |
253 | * of all currently existing children. | |
254 | * | |
255 | * @param parent the parent node | |
256 | * @param node the node that shall be linked | |
257 | * @param loc_parent offset in the node struct for the parent pointer | |
258 | * @param loc_children offset in the node struct for the children linked list | |
259 | * @param loc_last_child optional offset in the node struct for the pointer to | |
260 | * the last child in the linked list (negative if there is no such pointer) | |
261 | * @param loc_prev offset in the node struct for the prev pointer | |
262 | * @param loc_next offset in the node struct for the next pointer | |
263 | * @see cx_tree_unlink() | |
264 | */ | |
253
087cc9216f28
initial newapi GTK port
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
265 | __attribute__((__nonnull__)) |
087cc9216f28
initial newapi GTK port
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
266 | void cx_tree_link( |
324 | 267 | void *restrict parent, |
268 | void *restrict node, | |
253
087cc9216f28
initial newapi GTK port
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
269 | ptrdiff_t loc_parent, |
087cc9216f28
initial newapi GTK port
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
270 | ptrdiff_t loc_children, |
324 | 271 | ptrdiff_t loc_last_child, |
253
087cc9216f28
initial newapi GTK port
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
272 | ptrdiff_t loc_prev, |
087cc9216f28
initial newapi GTK port
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
273 | ptrdiff_t loc_next |
087cc9216f28
initial newapi GTK port
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
274 | ); |
087cc9216f28
initial newapi GTK port
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
275 | |
324 | 276 | /** |
277 | * Unlinks a node from its parent. | |
278 | * | |
279 | * If the node has no parent, this function does nothing. | |
280 | * | |
281 | * @param node the node that shall be unlinked from its parent | |
282 | * @param loc_parent offset in the node struct for the parent pointer | |
283 | * @param loc_children offset in the node struct for the children linked list | |
284 | * @param loc_last_child optional offset in the node struct for the pointer to | |
285 | * the last child in the linked list (negative if there is no such pointer) | |
286 | * @param loc_prev offset in the node struct for the prev pointer | |
287 | * @param loc_next offset in the node struct for the next pointer | |
288 | * @see cx_tree_link() | |
289 | */ | |
253
087cc9216f28
initial newapi GTK port
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
290 | __attribute__((__nonnull__)) |
087cc9216f28
initial newapi GTK port
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
291 | void cx_tree_unlink( |
087cc9216f28
initial newapi GTK port
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
292 | void *node, |
087cc9216f28
initial newapi GTK port
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
293 | ptrdiff_t loc_parent, |
087cc9216f28
initial newapi GTK port
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
294 | ptrdiff_t loc_children, |
324 | 295 | ptrdiff_t loc_last_child, |
296 | ptrdiff_t loc_prev, | |
297 | ptrdiff_t loc_next | |
298 | ); | |
299 | ||
300 | /** | |
301 | * Function pointer for a search function. | |
302 | * | |
303 | * A function of this kind shall check if the specified \p node | |
304 | * contains the given \p data or if one of the children might contain | |
305 | * the data. | |
306 | * | |
307 | * The function should use the returned integer to indicate how close the | |
308 | * match is, where a negative number means that it does not match at all. | |
309 | * | |
310 | * For example if a tree stores file path information, a node that is | |
311 | * describing a parent directory of a filename that is searched, shall | |
312 | * return a positive number to indicate that a child node might contain the | |
313 | * searched item. On the other hand, if the node denotes a path that is not a | |
314 | * prefix of the searched filename, the function would return -1 to indicate | |
315 | * that the search does not need to be continued in that branch. | |
316 | * | |
317 | * @param node the node that is currently investigated | |
318 | * @param data the data that is searched for | |
319 | * | |
320 | * @return 0 if the node contains the data, | |
321 | * positive if one of the children might contain the data, | |
322 | * negative if neither the node, nor the children contains the data | |
323 | */ | |
324 | typedef int (*cx_tree_search_data_func)(const void *node, const void *data); | |
325 | ||
326 | ||
327 | /** | |
328 | * Function pointer for a search function. | |
329 | * | |
330 | * A function of this kind shall check if the specified \p node | |
331 | * contains the same \p data as \p new_node or if one of the children might | |
332 | * contain the data. | |
333 | * | |
334 | * The function should use the returned integer to indicate how close the | |
335 | * match is, where a negative number means that it does not match at all. | |
336 | * | |
337 | * For example if a tree stores file path information, a node that is | |
338 | * describing a parent directory of a filename that is searched, shall | |
339 | * return a positive number to indicate that a child node might contain the | |
340 | * searched item. On the other hand, if the node denotes a path that is not a | |
341 | * prefix of the searched filename, the function would return -1 to indicate | |
342 | * that the search does not need to be continued in that branch. | |
343 | * | |
344 | * @param node the node that is currently investigated | |
345 | * @param new_node a new node with the information which is searched | |
346 | * | |
347 | * @return 0 if \p node contains the same data as \p new_node, | |
348 | * positive if one of the children might contain the data, | |
349 | * negative if neither the node, nor the children contains the data | |
350 | */ | |
351 | typedef int (*cx_tree_search_func)(const void *node, const void *new_node); | |
352 | ||
353 | /** | |
354 | * Searches for data in a tree. | |
355 | * | |
356 | * When the data cannot be found exactly, the search function might return a | |
357 | * closest result which might be a good starting point for adding a new node | |
358 | * to the tree (see also #cx_tree_add()). | |
359 | * | |
360 | * Depending on the tree structure it is not necessarily guaranteed that the | |
361 | * "closest" match is uniquely defined. This function will search for a node | |
362 | * with the best match according to the \p sfunc (meaning: the return value of | |
363 | * \p sfunc which is closest to zero). If that is also ambiguous, an arbitrary | |
364 | * node matching the criteria is returned. | |
365 | * | |
366 | * @param root the root node | |
367 | * @param data the data to search for | |
368 | * @param sfunc the search function | |
369 | * @param result where the result shall be stored | |
370 | * @param loc_children offset in the node struct for the children linked list | |
371 | * @param loc_next offset in the node struct for the next pointer | |
372 | * @return zero if the node was found exactly, positive if a node was found that | |
373 | * could contain the node (but doesn't right now), negative if the tree does not | |
374 | * contain any node that might be related to the searched data | |
375 | */ | |
376 | __attribute__((__nonnull__)) | |
377 | int cx_tree_search_data( | |
378 | const void *root, | |
379 | const void *data, | |
380 | cx_tree_search_data_func sfunc, | |
381 | void **result, | |
382 | ptrdiff_t loc_children, | |
383 | ptrdiff_t loc_next | |
384 | ); | |
385 | ||
386 | /** | |
387 | * Searches for a node in a tree. | |
388 | * | |
389 | * When no node with the same data can be found, the search function might | |
390 | * return a closest result which might be a good starting point for adding the | |
391 | * new node to the tree (see also #cx_tree_add()). | |
392 | * | |
393 | * Depending on the tree structure it is not necessarily guaranteed that the | |
394 | * "closest" match is uniquely defined. This function will search for a node | |
395 | * with the best match according to the \p sfunc (meaning: the return value of | |
396 | * \p sfunc which is closest to zero). If that is also ambiguous, an arbitrary | |
397 | * node matching the criteria is returned. | |
398 | * | |
399 | * @param root the root node | |
400 | * @param node the node to search for | |
401 | * @param sfunc the search function | |
402 | * @param result where the result shall be stored | |
403 | * @param loc_children offset in the node struct for the children linked list | |
404 | * @param loc_next offset in the node struct for the next pointer | |
405 | * @return zero if the node was found exactly, positive if a node was found that | |
406 | * could contain the node (but doesn't right now), negative if the tree does not | |
407 | * contain any node that might be related to the searched data | |
408 | */ | |
409 | __attribute__((__nonnull__)) | |
410 | int cx_tree_search( | |
411 | const void *root, | |
412 | const void *node, | |
413 | cx_tree_search_func sfunc, | |
414 | void **result, | |
415 | ptrdiff_t loc_children, | |
416 | ptrdiff_t loc_next | |
417 | ); | |
418 | ||
419 | /** | |
420 | * Creates a depth-first iterator for a tree with the specified root node. | |
421 | * | |
422 | * @note A tree iterator needs to maintain a stack of visited nodes, which is | |
423 | * allocated using stdlib malloc(). | |
424 | * When the iterator becomes invalid, this memory is automatically released. | |
425 | * However, if you wish to cancel the iteration before the iterator becomes | |
426 | * invalid by itself, you MUST call cxTreeIteratorDispose() manually to release | |
427 | * the memory. | |
428 | * | |
429 | * @remark The returned iterator does not support cxIteratorFlagRemoval(). | |
430 | * | |
431 | * @param root the root node | |
432 | * @param visit_on_exit set to true, when the iterator shall visit a node again | |
433 | * after processing all children | |
434 | * @param loc_children offset in the node struct for the children linked list | |
435 | * @param loc_next offset in the node struct for the next pointer | |
436 | * @return the new tree iterator | |
437 | * @see cxTreeIteratorDispose() | |
438 | */ | |
439 | CxTreeIterator cx_tree_iterator( | |
440 | void *root, | |
441 | bool visit_on_exit, | |
442 | ptrdiff_t loc_children, | |
443 | ptrdiff_t loc_next | |
444 | ); | |
445 | ||
446 | /** | |
447 | * Creates a breadth-first iterator for a tree with the specified root node. | |
448 | * | |
449 | * @note A tree visitor needs to maintain a queue of to be visited nodes, which | |
450 | * is allocated using stdlib malloc(). | |
451 | * When the visitor becomes invalid, this memory is automatically released. | |
452 | * However, if you wish to cancel the iteration before the visitor becomes | |
453 | * invalid by itself, you MUST call cxTreeVisitorDispose() manually to release | |
454 | * the memory. | |
455 | * | |
456 | * @remark The returned iterator does not support cxIteratorFlagRemoval(). | |
457 | * | |
458 | * @param root the root node | |
459 | * @param loc_children offset in the node struct for the children linked list | |
460 | * @param loc_next offset in the node struct for the next pointer | |
461 | * @return the new tree visitor | |
462 | * @see cxTreeVisitorDispose() | |
463 | */ | |
464 | CxTreeVisitor cx_tree_visitor( | |
465 | void *root, | |
466 | ptrdiff_t loc_children, | |
467 | ptrdiff_t loc_next | |
468 | ); | |
469 | ||
470 | /** | |
471 | * Describes a function that creates a tree node from the specified data. | |
472 | * The first argument points to the data the node shall contain and | |
473 | * the second argument may be used for additional data (e.g. an allocator). | |
474 | * Functions of this type shall either return a new pointer to a newly | |
475 | * created node or \c NULL when allocation fails. | |
476 | * | |
477 | * \note the function may leave the node pointers in the struct uninitialized. | |
478 | * The caller is responsible to set them according to the intended use case. | |
479 | */ | |
480 | typedef void *(*cx_tree_node_create_func)(const void *, void *); | |
481 | ||
482 | /** | |
483 | * The local search depth for a new subtree when adding multiple elements. | |
484 | * The default value is 3. | |
485 | * This variable is used by #cx_tree_add_array() and #cx_tree_add_iter() to | |
486 | * implement optimized insertion of multiple elements into a tree. | |
487 | */ | |
488 | extern unsigned int cx_tree_add_look_around_depth; | |
489 | ||
490 | /** | |
491 | * Adds multiple elements efficiently to a tree. | |
492 | * | |
493 | * Once an element cannot be added to the tree, this function returns, leaving | |
494 | * the iterator in a valid state pointing to the element that could not be | |
495 | * added. | |
496 | * Also, the pointer of the created node will be stored to \p failed. | |
497 | * The integer returned by this function denotes the number of elements obtained | |
498 | * from the \p iter that have been successfully processed. | |
499 | * When all elements could be processed, a \c NULL pointer will be written to | |
500 | * \p failed. | |
501 | * | |
502 | * The advantage of this function compared to multiple invocations of | |
503 | * #cx_tree_add() is that the search for the insert locations is not always | |
504 | * started from the root node. | |
505 | * Instead, the function checks #cx_tree_add_look_around_depth many parent nodes | |
506 | * of the current insert location before starting from the root node again. | |
507 | * When the variable is set to zero, only the last found location is checked | |
508 | * again. | |
509 | * | |
510 | * Refer to the documentation of #cx_tree_add() for more details. | |
511 | * | |
512 | * @param iter a pointer to an arbitrary iterator | |
513 | * @param num the maximum number of elements to obtain from the iterator | |
514 | * @param sfunc a search function | |
515 | * @param cfunc a node creation function | |
516 | * @param cdata optional additional data | |
517 | * @param root the root node of the tree | |
518 | * @param failed location where the pointer to a failed node shall be stored | |
519 | * @param loc_parent offset in the node struct for the parent pointer | |
520 | * @param loc_children offset in the node struct for the children linked list | |
521 | * @param loc_last_child optional offset in the node struct for the pointer to | |
522 | * the last child in the linked list (negative if there is no such pointer) | |
523 | * @param loc_prev offset in the node struct for the prev pointer | |
524 | * @param loc_next offset in the node struct for the next pointer | |
525 | * @return the number of nodes created and added | |
526 | * @see cx_tree_add() | |
527 | */ | |
528 | __attribute__((__nonnull__(1, 3, 4, 6, 7))) | |
529 | size_t cx_tree_add_iter( | |
530 | struct cx_iterator_base_s *iter, | |
531 | size_t num, | |
532 | cx_tree_search_func sfunc, | |
533 | cx_tree_node_create_func cfunc, | |
534 | void *cdata, | |
535 | void **failed, | |
536 | void *root, | |
537 | ptrdiff_t loc_parent, | |
538 | ptrdiff_t loc_children, | |
539 | ptrdiff_t loc_last_child, | |
540 | ptrdiff_t loc_prev, | |
541 | ptrdiff_t loc_next | |
542 | ); | |
543 | ||
544 | /** | |
545 | * Adds multiple elements efficiently to a tree. | |
546 | * | |
547 | * Once an element cannot be added to the tree, this function returns, storing | |
548 | * the pointer of the created node to \p failed. | |
549 | * The integer returned by this function denotes the number of elements from | |
550 | * the \p src array that have been successfully processed. | |
551 | * When all elements could be processed, a \c NULL pointer will be written to | |
552 | * \p failed. | |
553 | * | |
554 | * The advantage of this function compared to multiple invocations of | |
555 | * #cx_tree_add() is that the search for the insert locations is not always | |
556 | * started from the root node. | |
557 | * Instead, the function checks #cx_tree_add_look_around_depth many parent nodes | |
558 | * of the current insert location before starting from the root node again. | |
559 | * When the variable is set to zero, only the last found location is checked | |
560 | * again. | |
561 | * | |
562 | * Refer to the documentation of #cx_tree_add() for more details. | |
563 | * | |
564 | * @param src a pointer to the source data array | |
565 | * @param num the number of elements in the \p src array | |
566 | * @param elem_size the size of each element in the \p src array | |
567 | * @param sfunc a search function | |
568 | * @param cfunc a node creation function | |
569 | * @param cdata optional additional data | |
570 | * @param failed location where the pointer to a failed node shall be stored | |
571 | * @param root the root node of the tree | |
572 | * @param loc_parent offset in the node struct for the parent pointer | |
573 | * @param loc_children offset in the node struct for the children linked list | |
574 | * @param loc_last_child optional offset in the node struct for the pointer to | |
575 | * the last child in the linked list (negative if there is no such pointer) | |
576 | * @param loc_prev offset in the node struct for the prev pointer | |
577 | * @param loc_next offset in the node struct for the next pointer | |
578 | * @return the number of array elements successfully processed | |
579 | * @see cx_tree_add() | |
580 | */ | |
581 | __attribute__((__nonnull__(1, 4, 5, 7, 8))) | |
582 | size_t cx_tree_add_array( | |
583 | const void *src, | |
584 | size_t num, | |
585 | size_t elem_size, | |
586 | cx_tree_search_func sfunc, | |
587 | cx_tree_node_create_func cfunc, | |
588 | void *cdata, | |
589 | void **failed, | |
590 | void *root, | |
591 | ptrdiff_t loc_parent, | |
592 | ptrdiff_t loc_children, | |
593 | ptrdiff_t loc_last_child, | |
594 | ptrdiff_t loc_prev, | |
595 | ptrdiff_t loc_next | |
596 | ); | |
597 | ||
598 | /** | |
599 | * Adds data to a tree. | |
600 | * | |
601 | * An adequate location where to add the new tree node is searched with the | |
602 | * specified \p sfunc. | |
603 | * | |
604 | * When a location is found, the \p cfunc will be invoked with \p cdata. | |
605 | * | |
606 | * The node returned by \p cfunc will be linked into the tree. | |
607 | * When \p sfunc returned a positive integer, the new node will be linked as a | |
608 | * child. The other children (now siblings of the new node) are then checked | |
609 | * with \p sfunc, whether they could be children of the new node and re-linked | |
610 | * accordingly. | |
611 | * | |
612 | * When \p sfunc returned zero and the found node has a parent, the new | |
613 | * node will be added as sibling - otherwise, the new node will be added | |
614 | * as a child. | |
615 | * | |
616 | * When \p sfunc returned a negative value, the new node will not be added to | |
617 | * the tree and this function returns a non-zero value. | |
618 | * The caller should check if \p cnode contains a node pointer and deal with the | |
619 | * node that could not be added. | |
620 | * | |
621 | * This function also returns a non-zero value when \p cfunc tries to allocate | |
622 | * a new node but fails to do so. In that case, the pointer stored to \p cnode | |
623 | * will be \c NULL. | |
624 | * | |
625 | * Multiple elements can be added more efficiently with | |
626 | * #cx_tree_add_array() or #cx_tree_add_iter(). | |
627 | * | |
628 | * @param src a pointer to the data | |
629 | * @param sfunc a search function | |
630 | * @param cfunc a node creation function | |
631 | * @param cdata optional additional data | |
632 | * @param cnode the location where a pointer to the new node is stored | |
633 | * @param root the root node of the tree | |
634 | * @param loc_parent offset in the node struct for the parent pointer | |
635 | * @param loc_children offset in the node struct for the children linked list | |
636 | * @param loc_last_child optional offset in the node struct for the pointer to | |
637 | * the last child in the linked list (negative if there is no such pointer) | |
638 | * @param loc_prev offset in the node struct for the prev pointer | |
639 | * @param loc_next offset in the node struct for the next pointer | |
640 | * @return zero when a new node was created and added to the tree, | |
641 | * non-zero otherwise | |
642 | */ | |
643 | __attribute__((__nonnull__(1, 2, 3, 5, 6))) | |
644 | int cx_tree_add( | |
645 | const void *src, | |
646 | cx_tree_search_func sfunc, | |
647 | cx_tree_node_create_func cfunc, | |
648 | void *cdata, | |
649 | void **cnode, | |
650 | void *root, | |
651 | ptrdiff_t loc_parent, | |
652 | ptrdiff_t loc_children, | |
653 | ptrdiff_t loc_last_child, | |
253
087cc9216f28
initial newapi GTK port
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
654 | ptrdiff_t loc_prev, |
087cc9216f28
initial newapi GTK port
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
655 | ptrdiff_t loc_next |
087cc9216f28
initial newapi GTK port
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
656 | ); |
087cc9216f28
initial newapi GTK port
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
657 | |
324 | 658 | |
659 | /** | |
660 | * Tree class type. | |
661 | */ | |
662 | typedef struct cx_tree_class_s cx_tree_class; | |
663 | ||
664 | /** | |
665 | * Base structure that can be used for tree nodes in a #CxTree. | |
666 | */ | |
667 | struct cx_tree_node_base_s { | |
668 | /** | |
669 | * Pointer to the parent. | |
670 | */ | |
671 | struct cx_tree_node_base_s *parent; | |
672 | /** | |
673 | * Pointer to the first child. | |
674 | */ | |
675 | struct cx_tree_node_base_s *children; | |
676 | /** | |
677 | * Pointer to the last child. | |
678 | */ | |
679 | struct cx_tree_node_base_s *last_child; | |
680 | /** | |
681 | * Pointer to the previous sibling. | |
682 | */ | |
683 | struct cx_tree_node_base_s *prev; | |
684 | /** | |
685 | * Pointer to the next sibling. | |
686 | */ | |
687 | struct cx_tree_node_base_s *next; | |
688 | }; | |
689 | ||
690 | /** | |
691 | * Structure for holding the base data of a tree. | |
692 | */ | |
693 | struct cx_tree_s { | |
694 | /** | |
695 | * The tree class definition. | |
696 | */ | |
697 | const cx_tree_class *cl; | |
698 | ||
699 | /** | |
700 | * Allocator to allocate new nodes. | |
701 | */ | |
702 | const CxAllocator *allocator; | |
703 | ||
704 | /** | |
705 | * A pointer to the root node. | |
706 | * | |
707 | * Will be \c NULL when \c size is 0. | |
708 | */ | |
709 | void *root; | |
710 | ||
711 | /** | |
712 | * A function to create new nodes. | |
713 | * | |
714 | * Invocations to this function will receive a pointer to this tree | |
715 | * structure as second argument. | |
716 | * | |
717 | * Nodes MAY use #cx_tree_node_base_s as base layout, but do not need to. | |
718 | */ | |
719 | cx_tree_node_create_func node_create; | |
720 | ||
721 | /** | |
722 | * An optional simple destructor for the tree nodes. | |
723 | */ | |
724 | cx_destructor_func simple_destructor; | |
725 | ||
726 | /** | |
727 | * An optional advanced destructor for the tree nodes. | |
728 | */ | |
729 | cx_destructor_func2 advanced_destructor; | |
730 | ||
731 | /** | |
732 | * The pointer to additional data that is passed to the advanced destructor. | |
733 | */ | |
734 | void *destructor_data; | |
735 | ||
736 | /** | |
737 | * A function to compare two nodes. | |
738 | */ | |
739 | cx_tree_search_func search; | |
740 | ||
741 | /** | |
742 | * A function to compare a node with data. | |
743 | */ | |
744 | cx_tree_search_data_func search_data; | |
745 | ||
746 | /** | |
747 | * The number of currently stored elements. | |
748 | */ | |
749 | size_t size; | |
750 | ||
751 | /** | |
752 | * Offset in the node struct for the parent pointer. | |
753 | */ | |
754 | ptrdiff_t loc_parent; | |
755 | ||
756 | /** | |
757 | * Offset in the node struct for the children linked list. | |
758 | */ | |
759 | ptrdiff_t loc_children; | |
760 | ||
761 | /** | |
762 | * Optional offset in the node struct for the pointer to the last child | |
763 | * in the linked list (negative if there is no such pointer). | |
764 | */ | |
765 | ptrdiff_t loc_last_child; | |
766 | ||
767 | /** | |
768 | * Offset in the node struct for the previous sibling pointer. | |
769 | */ | |
770 | ptrdiff_t loc_prev; | |
771 | ||
772 | /** | |
773 | * Offset in the node struct for the next sibling pointer. | |
774 | */ | |
775 | ptrdiff_t loc_next; | |
776 | }; | |
777 | ||
778 | /** | |
779 | * Macro to roll out the #cx_tree_node_base_s structure with a custom | |
780 | * node type. | |
781 | */ | |
782 | #define CX_TREE_NODE_BASE(type) \ | |
783 | type *parent; \ | |
784 | type *children;\ | |
785 | type *last_child;\ | |
786 | type *prev;\ | |
787 | type *next | |
788 | ||
789 | /** | |
790 | * Macro for specifying the layout of a base node tree. | |
791 | */ | |
792 | #define cx_tree_node_base_layout \ | |
793 | offsetof(struct cx_tree_node_base_s, parent),\ | |
794 | offsetof(struct cx_tree_node_base_s, children),\ | |
795 | offsetof(struct cx_tree_node_base_s, last_child),\ | |
796 | offsetof(struct cx_tree_node_base_s, prev), \ | |
797 | offsetof(struct cx_tree_node_base_s, next) | |
798 | ||
799 | /** | |
800 | * Macro for obtaining the node pointer layout for a specific tree. | |
801 | */ | |
802 | #define cx_tree_node_layout(tree) \ | |
803 | (tree)->loc_parent,\ | |
804 | (tree)->loc_children,\ | |
805 | (tree)->loc_last_child,\ | |
806 | (tree)->loc_prev, \ | |
807 | (tree)->loc_next | |
808 | ||
809 | /** | |
810 | * The class definition for arbitrary trees. | |
811 | */ | |
812 | struct cx_tree_class_s { | |
813 | /** | |
814 | * Destructor function. | |
815 | * | |
816 | * Implementations SHALL invoke the node destructor functions if provided | |
817 | * and SHALL deallocate the tree memory. | |
818 | */ | |
819 | void (*destructor)(struct cx_tree_s *); | |
820 | ||
821 | /** | |
822 | * Member function for inserting a single element. | |
823 | * | |
824 | * Implementations SHALL NOT simply invoke \p insert_many as this comes | |
825 | * with too much overhead. | |
826 | */ | |
827 | int (*insert_element)( | |
828 | struct cx_tree_s *tree, | |
829 | const void *data | |
830 | ); | |
831 | ||
832 | /** | |
833 | * Member function for inserting multiple elements. | |
834 | * | |
835 | * Implementations SHALL avoid to perform a full search in the tree for | |
836 | * every element even though the source data MAY be unsorted. | |
837 | */ | |
838 | size_t (*insert_many)( | |
839 | struct cx_tree_s *tree, | |
840 | struct cx_iterator_base_s *iter, | |
841 | size_t n | |
842 | ); | |
843 | ||
844 | /** | |
845 | * Member function for finding a node. | |
846 | */ | |
847 | void *(*find)( | |
848 | struct cx_tree_s *tree, | |
849 | const void *subtree, | |
850 | const void *data | |
851 | ); | |
852 | ||
853 | /** | |
854 | * Member function for creating an iterator for the tree. | |
855 | */ | |
856 | CxTreeIterator (*iterator)( | |
857 | struct cx_tree_s *tree, | |
858 | bool visit_on_exit | |
859 | ); | |
860 | ||
861 | /** | |
862 | * Member function for creating a visitor for the tree. | |
863 | */ | |
864 | CxTreeVisitor (*visitor)(struct cx_tree_s *tree); | |
865 | }; | |
866 | ||
867 | /** | |
868 | * Common type for all tree implementations. | |
869 | */ | |
870 | typedef struct cx_tree_s CxTree; | |
871 | ||
872 | /** | |
873 | * Creates a new tree structure based on the specified layout. | |
874 | * | |
875 | * The specified \p allocator will be used for creating the tree struct | |
876 | * and SHALL be used by \p create_func to allocate memory for the nodes. | |
877 | * | |
878 | * \note This function will also register an advanced destructor which | |
879 | * will free the nodes with the allocator's free() method. | |
880 | * | |
881 | * @param allocator the allocator that shall be used | |
882 | * @param create_func a function that creates new nodes | |
883 | * @param search_func a function that compares two nodes | |
884 | * @param search_data_func a function that compares a node with data | |
885 | * @param loc_parent offset in the node struct for the parent pointer | |
886 | * @param loc_children offset in the node struct for the children linked list | |
887 | * @param loc_last_child optional offset in the node struct for the pointer to | |
888 | * the last child in the linked list (negative if there is no such pointer) | |
889 | * @param loc_prev offset in the node struct for the prev pointer | |
890 | * @param loc_next offset in the node struct for the next pointer | |
891 | * @return the new tree | |
892 | * @see cxTreeCreateSimple() | |
893 | * @see cxTreeCreateWrapped() | |
894 | */ | |
895 | __attribute__((__nonnull__, __warn_unused_result__)) | |
896 | CxTree *cxTreeCreate( | |
897 | const CxAllocator *allocator, | |
898 | cx_tree_node_create_func create_func, | |
899 | cx_tree_search_func search_func, | |
900 | cx_tree_search_data_func search_data_func, | |
901 | ptrdiff_t loc_parent, | |
902 | ptrdiff_t loc_children, | |
903 | ptrdiff_t loc_last_child, | |
904 | ptrdiff_t loc_prev, | |
905 | ptrdiff_t loc_next | |
906 | ); | |
907 | ||
908 | /** | |
909 | * Creates a new tree structure based on a default layout. | |
910 | * | |
911 | * Nodes created by \p create_func MUST contain #cx_tree_node_base_s as first | |
912 | * member (or at least respect the default offsets specified in the tree | |
913 | * struct) and they MUST be allocated with the specified allocator. | |
914 | * | |
915 | * \note This function will also register an advanced destructor which | |
916 | * will free the nodes with the allocator's free() method. | |
917 | * | |
918 | * @param allocator the allocator that shall be used | |
919 | * @param create_func a function that creates new nodes | |
920 | * @param search_func a function that compares two nodes | |
921 | * @param search_data_func a function that compares a node with data | |
922 | * @return the new tree | |
923 | * @see cxTreeCreate() | |
924 | */ | |
925 | __attribute__((__nonnull__, __warn_unused_result__)) | |
926 | static inline CxTree *cxTreeCreateSimple( | |
927 | const CxAllocator *allocator, | |
928 | cx_tree_node_create_func create_func, | |
929 | cx_tree_search_func search_func, | |
930 | cx_tree_search_data_func search_data_func | |
931 | ) { | |
932 | return cxTreeCreate( | |
933 | allocator, | |
934 | create_func, | |
935 | search_func, | |
936 | search_data_func, | |
937 | cx_tree_node_base_layout | |
938 | ); | |
939 | } | |
940 | ||
941 | /** | |
942 | * Creates a new tree structure based on an existing tree. | |
943 | * | |
944 | * The specified \p allocator will be used for creating the tree struct. | |
945 | * | |
946 | * \attention This function will create an incompletely defined tree structure | |
947 | * where neither the create function, the search function, nor a destructor | |
948 | * will be set. If you wish to use any of this functionality for the wrapped | |
949 | * tree, you need to specify those functions afterwards. | |
950 | * | |
951 | * @param root the root node of the tree that shall be wrapped | |
952 | * @param loc_parent offset in the node struct for the parent pointer | |
953 | * @param loc_children offset in the node struct for the children linked list | |
954 | * @param loc_last_child optional offset in the node struct for the pointer to | |
955 | * the last child in the linked list (negative if there is no such pointer) | |
956 | * @param loc_prev offset in the node struct for the prev pointer | |
957 | * @param loc_next offset in the node struct for the next pointer | |
958 | * @return the new tree | |
959 | * @see cxTreeCreate() | |
960 | */ | |
961 | __attribute__((__nonnull__, __warn_unused_result__)) | |
962 | CxTree *cxTreeCreateWrapped( | |
963 | const CxAllocator *allocator, | |
964 | void *root, | |
965 | ptrdiff_t loc_parent, | |
966 | ptrdiff_t loc_children, | |
967 | ptrdiff_t loc_last_child, | |
968 | ptrdiff_t loc_prev, | |
969 | ptrdiff_t loc_next | |
970 | ); | |
971 | ||
972 | /** | |
973 | * Destroys the tree structure. | |
974 | * | |
975 | * \attention This function will only invoke the destructor functions | |
976 | * on the nodes, if specified. | |
977 | * It will NOT additionally free the nodes with the tree's allocator, because | |
978 | * that would cause a double-free in most scenarios. | |
979 | * | |
980 | * @param tree the tree to destroy | |
981 | */ | |
982 | __attribute__((__nonnull__)) | |
983 | static inline void cxTreeDestroy(CxTree *tree) { | |
984 | tree->cl->destructor(tree); | |
985 | } | |
986 | ||
987 | /** | |
988 | * Inserts data into the tree. | |
989 | * | |
990 | * \remark For this function to work, the tree needs specified search and | |
991 | * create functions, which might not be available for wrapped trees | |
992 | * (see #cxTreeCreateWrapped()). | |
993 | * | |
994 | * @param tree the tree | |
995 | * @param data the data to insert | |
996 | * @return zero on success, non-zero on failure | |
997 | */ | |
998 | __attribute__((__nonnull__)) | |
999 | static inline int cxTreeInsert( | |
1000 | CxTree *tree, | |
1001 | const void *data | |
1002 | ) { | |
1003 | return tree->cl->insert_element(tree, data); | |
1004 | } | |
1005 | ||
1006 | /** | |
1007 | * Inserts elements provided by an iterator efficiently into the tree. | |
1008 | * | |
1009 | * \remark For this function to work, the tree needs specified search and | |
1010 | * create functions, which might not be available for wrapped trees | |
1011 | * (see #cxTreeCreateWrapped()). | |
1012 | * | |
1013 | * @param tree the tree | |
1014 | * @param iter the iterator providing the elements | |
1015 | * @param n the maximum number of elements to insert | |
1016 | * @return the number of elements that could be successfully inserted | |
1017 | */ | |
1018 | __attribute__((__nonnull__)) | |
1019 | static inline size_t cxTreeInsertIter( | |
1020 | CxTree *tree, | |
1021 | struct cx_iterator_base_s *iter, | |
1022 | size_t n | |
1023 | ) { | |
1024 | return tree->cl->insert_many(tree, iter, n); | |
1025 | } | |
1026 | ||
1027 | /** | |
1028 | * Inserts an array of data efficiently into the tree. | |
1029 | * | |
1030 | * \remark For this function to work, the tree needs specified search and | |
1031 | * create functions, which might not be available for wrapped trees | |
1032 | * (see #cxTreeCreateWrapped()). | |
1033 | * | |
1034 | * @param tree the tree | |
1035 | * @param data the array of data to insert | |
1036 | * @param elem_size the size of each element in the array | |
1037 | * @param n the number of elements in the array | |
1038 | * @return the number of elements that could be successfully inserted | |
1039 | */ | |
1040 | __attribute__((__nonnull__)) | |
1041 | static inline size_t cxTreeInsertArray( | |
1042 | CxTree *tree, | |
1043 | const void *data, | |
1044 | size_t elem_size, | |
1045 | size_t n | |
1046 | ) { | |
1047 | if (n == 0) return 0; | |
1048 | if (n == 1) return 0 == cxTreeInsert(tree, data) ? 1 : 0; | |
1049 | CxIterator iter = cxIterator(data, elem_size, n); | |
1050 | return cxTreeInsertIter(tree, cxIteratorRef(iter), n); | |
1051 | } | |
1052 | ||
1053 | /** | |
1054 | * Searches the data in the specified tree. | |
1055 | * | |
1056 | * \remark For this function to work, the tree needs a specified \c search_data | |
1057 | * function, which might not be available wrapped trees | |
1058 | * (see #cxTreeCreateWrapped()). | |
1059 | * | |
1060 | * @param tree the tree | |
1061 | * @param data the data to search for | |
1062 | * @return the first matching node, or \c NULL when the data cannot be found | |
1063 | */ | |
1064 | __attribute__((__nonnull__)) | |
1065 | static inline void *cxTreeFind( | |
1066 | CxTree *tree, | |
1067 | const void *data | |
1068 | ) { | |
1069 | return tree->cl->find(tree, tree->root, data); | |
1070 | } | |
1071 | ||
1072 | /** | |
1073 | * Searches the data in the specified subtree. | |
1074 | * | |
1075 | * \note When \p subtree_root is not part of the \p tree, the behavior is | |
1076 | * undefined. | |
1077 | * | |
1078 | * \remark For this function to work, the tree needs a specified \c search_data | |
1079 | * function, which might not be the case for wrapped trees | |
1080 | * (see #cxTreeCreateWrapped()). | |
1081 | * | |
1082 | * @param tree the tree | |
1083 | * @param data the data to search for | |
1084 | * @param subtree_root the node where to start | |
1085 | * @return the first matching node, or \c NULL when the data cannot be found | |
1086 | */ | |
1087 | __attribute__((__nonnull__)) | |
1088 | static inline void *cxTreeFindInSubtree( | |
1089 | CxTree *tree, | |
1090 | const void *data, | |
1091 | void *subtree_root | |
1092 | ) { | |
1093 | return tree->cl->find(tree, subtree_root, data); | |
1094 | } | |
1095 | ||
1096 | /** | |
1097 | * Determines the size of the specified subtree. | |
1098 | * | |
1099 | * @param tree the tree | |
1100 | * @param subtree_root the root node of the subtree | |
1101 | * @return the number of nodes in the specified subtree | |
1102 | */ | |
1103 | __attribute__((__nonnull__)) | |
1104 | size_t cxTreeSubtreeSize(CxTree *tree, void *subtree_root); | |
1105 | ||
1106 | /** | |
1107 | * Determines the depth of the specified subtree. | |
1108 | * | |
1109 | * @param tree the tree | |
1110 | * @param subtree_root the root node of the subtree | |
1111 | * @return the tree depth including the \p subtree_root | |
1112 | */ | |
1113 | __attribute__((__nonnull__)) | |
1114 | size_t cxTreeSubtreeDepth(CxTree *tree, void *subtree_root); | |
1115 | ||
1116 | /** | |
1117 | * Determines the depth of the entire tree. | |
1118 | * | |
1119 | * @param tree the tree | |
1120 | * @return the tree depth, counting the root as one | |
1121 | */ | |
1122 | __attribute__((__nonnull__)) | |
1123 | size_t cxTreeDepth(CxTree *tree); | |
1124 | ||
1125 | /** | |
1126 | * Creates a depth-first iterator for the specified tree. | |
1127 | * | |
1128 | * @param tree the tree to iterate | |
1129 | * @param visit_on_exit true, if the iterator shall visit a node again when | |
1130 | * leaving the sub-tree | |
1131 | * @return a tree iterator (depth-first) | |
1132 | * @see cxTreeVisitor() | |
1133 | */ | |
1134 | __attribute__((__nonnull__, __warn_unused_result__)) | |
1135 | static inline CxTreeIterator cxTreeIterator( | |
1136 | CxTree *tree, | |
1137 | bool visit_on_exit | |
1138 | ) { | |
1139 | return tree->cl->iterator(tree, visit_on_exit); | |
1140 | } | |
1141 | ||
1142 | /** | |
1143 | * Creates a breadth-first iterator for the specified tree. | |
1144 | * | |
1145 | * @param tree the tree to iterate | |
1146 | * @return a tree visitor (a.k.a. breadth-first iterator) | |
1147 | * @see cxTreeIterator() | |
1148 | */ | |
1149 | __attribute__((__nonnull__, __warn_unused_result__)) | |
1150 | static inline CxTreeVisitor cxTreeVisitor(CxTree *tree) { | |
1151 | return tree->cl->visitor(tree); | |
1152 | } | |
1153 | ||
1154 | /** | |
1155 | * Adds a new node to the tree. | |
1156 | * | |
1157 | * \attention The node may be externally created, but MUST obey the same rules | |
1158 | * as if it was created by the tree itself with #cxTreeAddChild() (e.g. use | |
1159 | * the same allocator). | |
1160 | * | |
1161 | * @param tree the tree | |
1162 | * @param parent the parent of the node to add | |
1163 | * @param child the node to add | |
1164 | */ | |
1165 | __attribute__((__nonnull__)) | |
1166 | static inline void cxTreeAddChildNode( | |
1167 | CxTree *tree, | |
1168 | void *parent, | |
1169 | void *child) { | |
1170 | cx_tree_link(parent, child, cx_tree_node_layout(tree)); | |
1171 | tree->size++; | |
1172 | } | |
1173 | ||
1174 | /** | |
1175 | * Creates a new node and adds it to the tree. | |
1176 | * | |
1177 | * With this function you can decide where exactly the new node shall be added. | |
1178 | * If you specified an appropriate search function, you may want to consider | |
1179 | * leaving this task to the tree by using #cxTreeInsert(). | |
1180 | * | |
1181 | * Be aware that adding nodes at arbitrary locations in the tree might cause | |
1182 | * wrong or undesired results when subsequently invoking #cxTreeInsert() and | |
1183 | * the invariant imposed by the search function does not hold any longer. | |
1184 | * | |
1185 | * @param tree the tree | |
1186 | * @param parent the parent node of the new node | |
1187 | * @param data the data that will be submitted to the create function | |
1188 | * @return zero when the new node was created, non-zero on allocation failure | |
1189 | * @see cxTreeInsert() | |
1190 | */ | |
1191 | __attribute__((__nonnull__)) | |
1192 | int cxTreeAddChild( | |
1193 | CxTree *tree, | |
1194 | void *parent, | |
1195 | const void *data | |
1196 | ); | |
1197 | ||
1198 | /** | |
1199 | * A function that is invoked when a node needs to be re-linked to a new parent. | |
1200 | * | |
1201 | * When a node is re-linked, sometimes the contents need to be updated. | |
1202 | * This callback is invoked by #cxTreeRemove() so that those updates can be | |
1203 | * applied when re-linking the children of the removed node. | |
1204 | * | |
1205 | * @param node the affected node | |
1206 | * @param old_parent the old parent of the node | |
1207 | * @param new_parent the new parent of the node | |
1208 | */ | |
1209 | typedef void (*cx_tree_relink_func)( | |
1210 | void *node, | |
1211 | const void *old_parent, | |
1212 | const void *new_parent | |
1213 | ); | |
1214 | ||
1215 | /** | |
1216 | * Removes a node and re-links its children to its former parent. | |
1217 | * | |
1218 | * If the node is not part of the tree, the behavior is undefined. | |
1219 | * | |
1220 | * \note The destructor function, if any, will \em not be invoked. That means | |
1221 | * you will need to free the removed node by yourself, eventually. | |
1222 | * | |
1223 | * @param tree the tree | |
1224 | * @param node the node to remove (must not be the root node) | |
1225 | * @param relink_func optional callback to update the content of each re-linked | |
1226 | * node | |
1227 | * @return zero on success, non-zero if \p node is the root node of the tree | |
1228 | */ | |
1229 | __attribute__((__nonnull__(1,2))) | |
1230 | int cxTreeRemove( | |
1231 | CxTree *tree, | |
1232 | void *node, | |
1233 | cx_tree_relink_func relink_func | |
1234 | ); | |
1235 | ||
1236 | /** | |
1237 | * Removes a node and it's subtree from the tree. | |
1238 | * | |
1239 | * If the node is not part of the tree, the behavior is undefined. | |
1240 | * | |
1241 | * \note The destructor function, if any, will \em not be invoked. That means | |
1242 | * you will need to free the removed subtree by yourself, eventually. | |
1243 | * | |
1244 | * @param tree the tree | |
1245 | * @param node the node to remove | |
1246 | */ | |
1247 | __attribute__((__nonnull__)) | |
1248 | void cxTreeRemoveSubtree(CxTree *tree, void *node); | |
1249 | ||
253
087cc9216f28
initial newapi GTK port
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
1250 | #ifdef __cplusplus |
087cc9216f28
initial newapi GTK port
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
1251 | } // extern "C" |
087cc9216f28
initial newapi GTK port
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
1252 | #endif |
087cc9216f28
initial newapi GTK port
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
1253 | |
087cc9216f28
initial newapi GTK port
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
1254 | #endif //UCX_TREE_H |