| Line | Branch | Exec | Source |
|---|---|---|---|
| 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 "collection.h" | ||
| 42 | |||
| 43 | /** | ||
| 44 | * An element in a visitor queue. | ||
| 45 | */ | ||
| 46 | struct cx_tree_visitor_queue_s { | ||
| 47 | /** | ||
| 48 | * The tree node to visit. | ||
| 49 | */ | ||
| 50 | void *node; | ||
| 51 | /** | ||
| 52 | * The depth of the node. | ||
| 53 | * The first visited node has depth 1. | ||
| 54 | */ | ||
| 55 | size_t depth; | ||
| 56 | /** | ||
| 57 | * The next element in the queue or @c NULL. | ||
| 58 | */ | ||
| 59 | struct cx_tree_visitor_queue_s *next; | ||
| 60 | }; | ||
| 61 | |||
| 62 | /** | ||
| 63 | * An iterator (DFS) or visitor (BFS) for a tree. | ||
| 64 | */ | ||
| 65 | typedef struct cx_tree_combined_iterator_s { | ||
| 66 | /** | ||
| 67 | * Base members. | ||
| 68 | */ | ||
| 69 | CX_ITERATOR_BASE; | ||
| 70 | /** | ||
| 71 | * Offset in the node struct for the children linked list. | ||
| 72 | */ | ||
| 73 | ptrdiff_t loc_children; | ||
| 74 | /** | ||
| 75 | * Offset in the node struct for the next pointer. | ||
| 76 | */ | ||
| 77 | ptrdiff_t loc_next; | ||
| 78 | /** | ||
| 79 | * The total number of distinct nodes that have been passed so far. | ||
| 80 | * This includes the currently visited node. | ||
| 81 | */ | ||
| 82 | size_t counter; | ||
| 83 | /** | ||
| 84 | * The current depth in the tree. | ||
| 85 | */ | ||
| 86 | size_t depth; | ||
| 87 | /** | ||
| 88 | * The currently observed node. | ||
| 89 | * | ||
| 90 | * This is the same what cxIteratorCurrent() would return. | ||
| 91 | */ | ||
| 92 | void *node; | ||
| 93 | /** | ||
| 94 | * Memory for BFS or DFS-specific data. | ||
| 95 | */ | ||
| 96 | union { | ||
| 97 | struct { | ||
| 98 | /** | ||
| 99 | * Stores a copy of the pointer to the successor of the visited node. | ||
| 100 | * Allows freeing a node on exit without corrupting the iteration. | ||
| 101 | */ | ||
| 102 | void *node_next; | ||
| 103 | /** | ||
| 104 | * Internal stack. | ||
| 105 | * Will be automatically freed once the iterator becomes invalid. | ||
| 106 | * | ||
| 107 | * If you want to discard the iterator before, you need to manually | ||
| 108 | * call cxTreeIteratorDispose(). | ||
| 109 | */ | ||
| 110 | void **stack; | ||
| 111 | /** | ||
| 112 | * Internal capacity of the stack. | ||
| 113 | */ | ||
| 114 | size_t stack_capacity; | ||
| 115 | }; | ||
| 116 | struct { | ||
| 117 | /** | ||
| 118 | * The next element in the visitor queue. | ||
| 119 | */ | ||
| 120 | struct cx_tree_visitor_queue_s *queue_next; | ||
| 121 | /** | ||
| 122 | * The last element in the visitor queue. | ||
| 123 | */ | ||
| 124 | struct cx_tree_visitor_queue_s *queue_last; | ||
| 125 | }; | ||
| 126 | }; | ||
| 127 | /** | ||
| 128 | * Indicates whether the subtree below the current node shall be skipped. | ||
| 129 | */ | ||
| 130 | bool skip; | ||
| 131 | /** | ||
| 132 | * Set to true, when the iterator shall visit a node again | ||
| 133 | * when all its children have been processed. | ||
| 134 | */ | ||
| 135 | bool visit_on_exit; | ||
| 136 | /** | ||
| 137 | * True, if this iterator is currently leaving the node. | ||
| 138 | */ | ||
| 139 | bool exiting; | ||
| 140 | /** | ||
| 141 | * Indicates whether the @c iterator (true) or the @c visitor (false) aspect is active. | ||
| 142 | */ | ||
| 143 | bool use_dfs; | ||
| 144 | } CxTreeIterator; | ||
| 145 | |||
| 146 | /** | ||
| 147 | * Releases internal memory of the given tree iterator. | ||
| 148 | * @param iter the iterator | ||
| 149 | */ | ||
| 150 | CX_EXTERN CX_NONNULL | ||
| 151 | void cxTreeIteratorDispose(CxTreeIterator *iter); | ||
| 152 | |||
| 153 | /** | ||
| 154 | * Advises the iterator to skip the subtree below the current node and | ||
| 155 | * also continues the current loop. | ||
| 156 | * | ||
| 157 | * @param iterator (@c CxTreeIterator) the iterator | ||
| 158 | */ | ||
| 159 | #define cxTreeIteratorContinue(iterator) (iterator).skip = true; continue | ||
| 160 | |||
| 161 | /** | ||
| 162 | * Links a node to a (new) parent. | ||
| 163 | * | ||
| 164 | * If the node already has a parent, it is unlinked, first. | ||
| 165 | * If the parent has children already, the node is @em appended to the list | ||
| 166 | * of all currently existing children. | ||
| 167 | * | ||
| 168 | * @param parent the parent node | ||
| 169 | * @param node the node that shall be linked | ||
| 170 | * @param loc_parent offset in the node struct for the parent pointer | ||
| 171 | * @param loc_children offset in the node struct for the children linked list | ||
| 172 | * @param loc_last_child optional offset in the node struct for the pointer to | ||
| 173 | * the last child in the linked list (negative if there is no such pointer) | ||
| 174 | * @param loc_prev optional offset in the node struct for the prev pointer | ||
| 175 | * @param loc_next offset in the node struct for the next pointer | ||
| 176 | * @see cx_tree_remove() | ||
| 177 | */ | ||
| 178 | CX_EXTERN CX_NONNULL | ||
| 179 | void cx_tree_add(void *parent, void *node, | ||
| 180 | ptrdiff_t loc_parent, ptrdiff_t loc_children, ptrdiff_t loc_last_child, | ||
| 181 | ptrdiff_t loc_prev, ptrdiff_t loc_next); | ||
| 182 | |||
| 183 | /** | ||
| 184 | * Unlinks a node from its parent. | ||
| 185 | * | ||
| 186 | * If the node has no parent, this function does nothing. | ||
| 187 | * | ||
| 188 | * @param node the node that shall be unlinked from its parent | ||
| 189 | * @param loc_parent offset in the node struct for the parent pointer | ||
| 190 | * @param loc_children offset in the node struct for the children linked list | ||
| 191 | * @param loc_last_child optional offset in the node struct for the pointer to | ||
| 192 | * the last child in the linked list (negative if there is no such pointer) | ||
| 193 | * @param loc_prev optional offset in the node struct for the prev pointer | ||
| 194 | * @param loc_next offset in the node struct for the next pointer | ||
| 195 | * @see cx_tree_add() | ||
| 196 | */ | ||
| 197 | CX_EXTERN CX_NONNULL | ||
| 198 | void cx_tree_remove(void *node, | ||
| 199 | ptrdiff_t loc_parent, ptrdiff_t loc_children, ptrdiff_t loc_last_child, | ||
| 200 | ptrdiff_t loc_prev, ptrdiff_t loc_next); | ||
| 201 | |||
| 202 | /** | ||
| 203 | * Macro that can be used instead of the magic value for infinite search depth. | ||
| 204 | */ | ||
| 205 | #define CX_TREE_SEARCH_INFINITE_DEPTH 0 | ||
| 206 | |||
| 207 | /** | ||
| 208 | * Function pointer for a search function. | ||
| 209 | * | ||
| 210 | * A function of this kind shall check if the specified @p node | ||
| 211 | * contains the given @p data or if one of the children might contain | ||
| 212 | * the data. | ||
| 213 | * | ||
| 214 | * The function should use the returned integer to indicate how close the | ||
| 215 | * match is, where a negative number means that it does not match at all. | ||
| 216 | * Zero means exact match and a positive number is an implementation defined | ||
| 217 | * measure for the distance to an exact match. | ||
| 218 | * | ||
| 219 | * For example, consider a tree that stores file path information. | ||
| 220 | * A node which is describing a parent directory of a searched file shall | ||
| 221 | * return a positive number to indicate that a child node might contain the | ||
| 222 | * searched item. On the other hand, if the node denotes a path that is not a | ||
| 223 | * prefix of the searched filename, the function would return -1 to indicate | ||
| 224 | * that the search does not need to be continued in that branch. | ||
| 225 | * | ||
| 226 | * @param node the node that is currently investigated | ||
| 227 | * @param data the data that is searched for | ||
| 228 | * | ||
| 229 | * @return 0 if the node contains the data, | ||
| 230 | * positive if one of the children might contain the data, | ||
| 231 | * negative if neither the node nor the children contains the data | ||
| 232 | */ | ||
| 233 | typedef int (*cx_tree_search_func)(const void *node, const void *data); | ||
| 234 | |||
| 235 | /** | ||
| 236 | * Searches for data in a tree. | ||
| 237 | * | ||
| 238 | * When the data cannot be found exactly, the search function might return the | ||
| 239 | * closest result, which might be a good starting point for adding a new node | ||
| 240 | * to the tree. | ||
| 241 | * | ||
| 242 | * Depending on the tree structure, it is not necessarily guaranteed that the | ||
| 243 | * "closest" match is uniquely defined. This function will search for a node | ||
| 244 | * with the best match according to the @p sfunc (meaning: the return value of | ||
| 245 | * @p sfunc which is closest to zero). If that is also ambiguous, an arbitrary | ||
| 246 | * node matching the criteria is returned. | ||
| 247 | * | ||
| 248 | * @param root the root node | ||
| 249 | * @param max_depth the maximum depth (zero=indefinite, one=just root) | ||
| 250 | * @param data the data to search for | ||
| 251 | * @param sfunc the search function | ||
| 252 | * @param result where the result shall be stored | ||
| 253 | * @param loc_children offset in the node struct for the children linked list | ||
| 254 | * @param loc_next offset in the node struct for the next pointer | ||
| 255 | * @return zero if the node was found exactly, positive if a node was found that | ||
| 256 | * could contain the node (but doesn't right now), negative if the tree does not | ||
| 257 | * contain any node that might be related to the searched data | ||
| 258 | */ | ||
| 259 | CX_EXTERN CX_NONNULL_ARG(4, 5) CX_ACCESS_W(5) | ||
| 260 | int cx_tree_search(const void *root, size_t max_depth, | ||
| 261 | const void *data, cx_tree_search_func sfunc, void **result, | ||
| 262 | ptrdiff_t loc_children, ptrdiff_t loc_next); | ||
| 263 | |||
| 264 | /** | ||
| 265 | * Creates a depth-first iterator for a tree with the specified root node. | ||
| 266 | * | ||
| 267 | * @note A tree iterator needs to maintain a stack of visited nodes, which is | ||
| 268 | * allocated using the cxDefaultAllocator. | ||
| 269 | * When the iterator becomes invalid, this memory is automatically released. | ||
| 270 | * However, if you wish to cancel the iteration before the iterator becomes | ||
| 271 | * invalid by itself, you MUST call cxTreeIteratorDispose() manually to release | ||
| 272 | * the memory. | ||
| 273 | * | ||
| 274 | * @remark The returned iterator does not support cxIteratorFlagRemoval(). | ||
| 275 | * | ||
| 276 | * @param root the root node | ||
| 277 | * @param visit_on_exit set to true, when the iterator shall visit a node again | ||
| 278 | * after processing all children | ||
| 279 | * @param loc_children offset in the node struct for the children linked list | ||
| 280 | * @param loc_next offset in the node struct for the next pointer | ||
| 281 | * @return the new tree iterator | ||
| 282 | * @see cxTreeIteratorDispose() | ||
| 283 | */ | ||
| 284 | CX_EXTERN CX_NODISCARD | ||
| 285 | CxTreeIterator cx_tree_iterator(void *root, bool visit_on_exit, | ||
| 286 | ptrdiff_t loc_children, ptrdiff_t loc_next); | ||
| 287 | |||
| 288 | /** | ||
| 289 | * Creates a breadth-first iterator for a tree with the specified root node. | ||
| 290 | * | ||
| 291 | * @note A tree visitor needs to maintain a queue of to-be visited nodes, which | ||
| 292 | * is allocated using the cxDefaultAllocator. | ||
| 293 | * When the visitor becomes invalid, this memory is automatically released. | ||
| 294 | * However, if you wish to cancel the iteration before the visitor becomes | ||
| 295 | * invalid by itself, you MUST call cxTreeIteratorDispose() manually to release | ||
| 296 | * the memory. | ||
| 297 | * | ||
| 298 | * @remark The returned iterator does not support cxIteratorFlagRemoval(). | ||
| 299 | * | ||
| 300 | * @param root the root node | ||
| 301 | * @param loc_children offset in the node struct for the children linked list | ||
| 302 | * @param loc_next offset in the node struct for the next pointer | ||
| 303 | * @return the new tree visitor | ||
| 304 | * @see cxTreeIteratorDispose() | ||
| 305 | */ | ||
| 306 | CX_EXTERN CX_NODISCARD | ||
| 307 | CxTreeIterator cx_tree_visitor(void *root, | ||
| 308 | ptrdiff_t loc_children, ptrdiff_t loc_next); | ||
| 309 | |||
| 310 | /** | ||
| 311 | * Base structure that can be used for tree nodes in a #CxTree. | ||
| 312 | */ | ||
| 313 | struct cx_tree_node_base_s { | ||
| 314 | /** | ||
| 315 | * Pointer to the parent. | ||
| 316 | */ | ||
| 317 | struct cx_tree_node_base_s *parent; | ||
| 318 | /** | ||
| 319 | * Pointer to the first child. | ||
| 320 | */ | ||
| 321 | struct cx_tree_node_base_s *children; | ||
| 322 | /** | ||
| 323 | * Pointer to the last child. | ||
| 324 | */ | ||
| 325 | struct cx_tree_node_base_s *last_child; | ||
| 326 | /** | ||
| 327 | * Pointer to the previous sibling. | ||
| 328 | */ | ||
| 329 | struct cx_tree_node_base_s *prev; | ||
| 330 | /** | ||
| 331 | * Pointer to the next sibling. | ||
| 332 | */ | ||
| 333 | struct cx_tree_node_base_s *next; | ||
| 334 | }; | ||
| 335 | |||
| 336 | /** | ||
| 337 | * Structure for holding the base data of a tree. | ||
| 338 | */ | ||
| 339 | typedef struct cx_tree_s { | ||
| 340 | /** Base attributes. */ | ||
| 341 | CX_COLLECTION_BASE; | ||
| 342 | /** | ||
| 343 | * A pointer to the root node. | ||
| 344 | * | ||
| 345 | * Will be @c NULL when @c size is 0. | ||
| 346 | */ | ||
| 347 | void *root; | ||
| 348 | |||
| 349 | /** | ||
| 350 | * The size of the node structure. | ||
| 351 | */ | ||
| 352 | size_t node_size; | ||
| 353 | |||
| 354 | /** | ||
| 355 | * Offset in the node struct for the parent pointer. | ||
| 356 | */ | ||
| 357 | ptrdiff_t loc_parent; | ||
| 358 | |||
| 359 | /** | ||
| 360 | * Offset in the node struct for the children linked list. | ||
| 361 | */ | ||
| 362 | ptrdiff_t loc_children; | ||
| 363 | |||
| 364 | /** | ||
| 365 | * Optional offset in the node struct for the pointer to the last child | ||
| 366 | * in the linked list (negative if there is no such pointer). | ||
| 367 | */ | ||
| 368 | ptrdiff_t loc_last_child; | ||
| 369 | |||
| 370 | /** | ||
| 371 | * Offset in the node struct for the previous sibling pointer. | ||
| 372 | */ | ||
| 373 | ptrdiff_t loc_prev; | ||
| 374 | |||
| 375 | /** | ||
| 376 | * Offset in the node struct for the next sibling pointer. | ||
| 377 | */ | ||
| 378 | ptrdiff_t loc_next; | ||
| 379 | |||
| 380 | /** | ||
| 381 | * Offset in the node struct where the payload is located. | ||
| 382 | */ | ||
| 383 | ptrdiff_t loc_data; | ||
| 384 | } CxTree; | ||
| 385 | |||
| 386 | /** | ||
| 387 | * Macro to roll out the #cx_tree_node_base_s structure with a custom | ||
| 388 | * node type. | ||
| 389 | * | ||
| 390 | * Must be used as the first member in your custom tree struct. | ||
| 391 | * | ||
| 392 | * @param type the data type for the nodes | ||
| 393 | */ | ||
| 394 | #define CX_TREE_NODE(type) \ | ||
| 395 | type *parent; \ | ||
| 396 | type *children;\ | ||
| 397 | type *last_child;\ | ||
| 398 | type *prev;\ | ||
| 399 | type *next | ||
| 400 | |||
| 401 | /** | ||
| 402 | * Macro for specifying the layout of a tree node. | ||
| 403 | * | ||
| 404 | * When your tree uses #CX_TREE_NODE, you can use this | ||
| 405 | * macro in all tree functions that expect the layout parameters | ||
| 406 | * @c loc_parent, @c loc_children, @c loc_last_child, @c loc_prev, | ||
| 407 | * and @c loc_next. | ||
| 408 | * @param struct_name the name of the node structure | ||
| 409 | */ | ||
| 410 | #define cx_tree_node_layout(struct_name) \ | ||
| 411 | offsetof(struct_name, parent),\ | ||
| 412 | offsetof(struct_name, children),\ | ||
| 413 | offsetof(struct_name, last_child),\ | ||
| 414 | offsetof(struct_name, prev), \ | ||
| 415 | offsetof(struct_name, next) | ||
| 416 | |||
| 417 | /** | ||
| 418 | * Destroys a node and its subtree. | ||
| 419 | * | ||
| 420 | * It is guaranteed that the simple destructor is invoked before | ||
| 421 | * the advanced destructor, starting with the leaf nodes of the subtree. | ||
| 422 | * | ||
| 423 | * When this function is invoked on the root node of the tree, it destroys the | ||
| 424 | * tree contents, but - in contrast to #cxTreeFree() - not the tree | ||
| 425 | * structure, leaving an empty tree behind. | ||
| 426 | * | ||
| 427 | * @note The destructor function, if any, will @em not be invoked. That means | ||
| 428 | * you will need to free the removed subtree by yourself, eventually. | ||
| 429 | * | ||
| 430 | * @attention This function will not free the memory of the nodes with the | ||
| 431 | * tree's allocator, because that is usually done by the advanced destructor | ||
| 432 | * and would therefore result in a double-free. | ||
| 433 | * | ||
| 434 | * @param tree the tree | ||
| 435 | * @param node the node being the root of the subtree to remove | ||
| 436 | * @see cxTreeFree() | ||
| 437 | */ | ||
| 438 | CX_EXTERN CX_NONNULL | ||
| 439 | void cxTreeDestroySubtree(CxTree *tree, void *node); | ||
| 440 | |||
| 441 | |||
| 442 | /** | ||
| 443 | * Destroys the tree contents. | ||
| 444 | * | ||
| 445 | * It is guaranteed that the simple destructor is invoked before | ||
| 446 | * the advanced destructor, starting with the leaf nodes of the subtree. | ||
| 447 | * | ||
| 448 | * This is a convenience macro for invoking #cxTreeDestroySubtree() on the | ||
| 449 | * root node of the tree. | ||
| 450 | * | ||
| 451 | * @attention Be careful when calling this function when no destructor function | ||
| 452 | * is registered that actually frees the memory of nodes. In that case you will | ||
| 453 | * need a reference to the (former) root node of the tree somewhere, or | ||
| 454 | * otherwise you will be leaking memory. | ||
| 455 | * | ||
| 456 | * @param tree the tree | ||
| 457 | * @see cxTreeDestroySubtree() | ||
| 458 | */ | ||
| 459 | CX_INLINE | ||
| 460 | void cxTreeClear(CxTree *tree) { | ||
| 461 |
1/2✓ Branch 0 (5→6) taken 17 times.
✗ Branch 1 (5→7) not taken.
|
17 | if (tree->root != NULL) { |
| 462 | 17 | cxTreeDestroySubtree(tree, tree->root); | |
| 463 | } | ||
| 464 | 17 | } | |
| 465 | |||
| 466 | /** | ||
| 467 | * Deallocates the tree structure. | ||
| 468 | * | ||
| 469 | * The destructor functions are invoked for each node, starting with the leaf | ||
| 470 | * nodes. | ||
| 471 | * It is guaranteed that for each node the simple destructor is invoked before | ||
| 472 | * the advanced destructor. | ||
| 473 | * | ||
| 474 | * @attention This function will only invoke the destructor functions | ||
| 475 | * on the nodes. | ||
| 476 | * It will NOT additionally free the nodes with the tree's allocator, because | ||
| 477 | * that would cause a double-free in most scenarios where the advanced | ||
| 478 | * destructor is already freeing the memory. | ||
| 479 | * | ||
| 480 | * @param tree the tree to free | ||
| 481 | */ | ||
| 482 | CX_EXTERN | ||
| 483 | void cxTreeFree(CxTree *tree); | ||
| 484 | |||
| 485 | /** | ||
| 486 | * Creates a new tree. | ||
| 487 | * | ||
| 488 | * The specified @p allocator will be used for creating the tree struct | ||
| 489 | * @em and the nodes. | ||
| 490 | * | ||
| 491 | * When you do not specify an existing @p root, the tree will be created | ||
| 492 | * empty. Additionally, cxFree() is registered as the advanced destructor for | ||
| 493 | * the tree so that all nodes that you will add to the tree are automatically | ||
| 494 | * freed together with the tree. | ||
| 495 | * When @p root is not @c NULL, no destructors are registered automatically. | ||
| 496 | * | ||
| 497 | * @param allocator the allocator to use | ||
| 498 | * (if @c NULL, the cxDefaultAllocator is assumed) | ||
| 499 | * @param node_size the complete size of one node | ||
| 500 | * @param elem_size the size of the payload stored in the node | ||
| 501 | * (@c CX_STORE_POINTERS is also supported) | ||
| 502 | * @param root an optional already existing root node | ||
| 503 | * @param loc_data optional offset in the node struct for the payload | ||
| 504 | * (when negative, cxTreeAddData() is not supported) | ||
| 505 | * @param loc_parent offset in the node struct for the parent pointer | ||
| 506 | * @param loc_children offset in the node struct for the children linked list | ||
| 507 | * @param loc_last_child optional offset in the node struct for the pointer to | ||
| 508 | * the last child in the linked list (negative if there is no such pointer) | ||
| 509 | * @param loc_prev optional offset in the node struct for the prev pointer | ||
| 510 | * @param loc_next offset in the node struct for the next pointer | ||
| 511 | * @return the new tree | ||
| 512 | * @see cxTreeCreate() | ||
| 513 | */ | ||
| 514 | CX_EXTERN CX_NODISCARD CX_MALLOC CX_DEALLOC(cxTreeFree, 1) | ||
| 515 | CxTree *cxTreeCreate(const CxAllocator *allocator, | ||
| 516 | size_t node_size, size_t elem_size, void *root, ptrdiff_t loc_data, | ||
| 517 | ptrdiff_t loc_parent, ptrdiff_t loc_children, ptrdiff_t loc_last_child, | ||
| 518 | ptrdiff_t loc_prev, ptrdiff_t loc_next); | ||
| 519 | |||
| 520 | /** | ||
| 521 | * Searches the data in the specified subtree. | ||
| 522 | * | ||
| 523 | * When @p max_depth is zero, the depth is not limited. | ||
| 524 | * The @p subtree_root itself is on depth 1 and its children have depth 2. | ||
| 525 | * | ||
| 526 | * @note When @p subtree_root is not @c NULL and not part of the @p tree, | ||
| 527 | * the behavior is undefined. | ||
| 528 | * | ||
| 529 | * @attention When @p loc_data is not available, this function immediately returns | ||
| 530 | * @c NULL. | ||
| 531 | * | ||
| 532 | * @param tree the tree | ||
| 533 | * @param data the data to search for | ||
| 534 | * @param subtree_root the node where to start (@c NULL to start from root) | ||
| 535 | * @param max_depth the maximum search depth | ||
| 536 | * @param use_dfs @c true when depth-first search should be used; | ||
| 537 | * @c false when breadth-first search should be used | ||
| 538 | * @return the first matching node, or @c NULL when the data cannot be found | ||
| 539 | * @see cxTreeFind() | ||
| 540 | */ | ||
| 541 | CX_EXTERN CX_NONNULL_ARG(1, 2) CX_NODISCARD | ||
| 542 | void *cxTreeFindInSubtree(CxTree *tree, const void *data, void *subtree_root, | ||
| 543 | size_t max_depth, bool use_dfs); | ||
| 544 | |||
| 545 | /** | ||
| 546 | * Searches the data in the specified tree. | ||
| 547 | * | ||
| 548 | * @attention When @p loc_data is not available, this function immediately returns | ||
| 549 | * @c NULL. | ||
| 550 | * | ||
| 551 | * @param tree the tree | ||
| 552 | * @param data the data to search for | ||
| 553 | * @param use_dfs @c true when depth-first search should be used; | ||
| 554 | * @c false when breadth-first search should be used | ||
| 555 | * @return the first matching node, or @c NULL when the data cannot be found | ||
| 556 | * @see cxTreeFindInSubtree() | ||
| 557 | * @see cxTreeFindFast() | ||
| 558 | */ | ||
| 559 | CX_INLINE CX_NONNULL CX_NODISCARD | ||
| 560 | void *cxTreeFind(CxTree *tree, const void *data, bool use_dfs) { | ||
| 561 | if (tree->root == NULL) return NULL; | ||
| 562 | return cxTreeFindInSubtree(tree, data, tree->root, 0, use_dfs); | ||
| 563 | } | ||
| 564 | |||
| 565 | /** | ||
| 566 | * Performs an efficient depth-first search in a branch of the specified tree. | ||
| 567 | * | ||
| 568 | * When @p max_depth is zero, the depth is not limited. | ||
| 569 | * The @p subtree_root itself is on depth 1 and its children have depth 2. | ||
| 570 | * | ||
| 571 | * @note When @p subtree_root is not @c NULL and not part of the @p tree, | ||
| 572 | * the behavior is undefined. | ||
| 573 | * | ||
| 574 | * @param tree the tree | ||
| 575 | * @param data the data to search for | ||
| 576 | * @param sfunc the search function | ||
| 577 | * @param subtree_root the node where to start (@c NULL to start from root) | ||
| 578 | * @param max_depth the maximum search depth | ||
| 579 | * @return the first matching node, or @c NULL when the data cannot be found | ||
| 580 | * @see cxTreeFindInSubtree() | ||
| 581 | */ | ||
| 582 | CX_EXTERN CX_NONNULL CX_NODISCARD | ||
| 583 | void *cxTreeFindFastInSubtree(CxTree *tree, const void *data, | ||
| 584 | cx_tree_search_func sfunc, void *subtree_root, size_t max_depth); | ||
| 585 | |||
| 586 | /** | ||
| 587 | * Performs an efficient depth-first search in the tree. | ||
| 588 | * | ||
| 589 | * @param tree the tree | ||
| 590 | * @param data the data to search for | ||
| 591 | * @param sfunc the search function | ||
| 592 | * @return the first matching node, or @c NULL when the data cannot be found | ||
| 593 | * @see cxTreeFind() | ||
| 594 | */ | ||
| 595 | CX_INLINE CX_NONNULL CX_NODISCARD | ||
| 596 | void *cxTreeFindFast(CxTree *tree, const void *data, cx_tree_search_func sfunc) { | ||
| 597 | return cxTreeFindFastInSubtree(tree, data, sfunc, tree->root, 0); | ||
| 598 | } | ||
| 599 | |||
| 600 | /** | ||
| 601 | * Determines the size of the specified subtree. | ||
| 602 | * | ||
| 603 | * @param tree the tree | ||
| 604 | * @param subtree_root the root node of the subtree | ||
| 605 | * @return the number of nodes in the specified subtree | ||
| 606 | */ | ||
| 607 | CX_EXTERN CX_NONNULL CX_NODISCARD | ||
| 608 | size_t cxTreeSubtreeSize(CxTree *tree, void *subtree_root); | ||
| 609 | |||
| 610 | /** | ||
| 611 | * Determines the depth of the specified subtree. | ||
| 612 | * | ||
| 613 | * @param tree the tree | ||
| 614 | * @param subtree_root the root node of the subtree | ||
| 615 | * @return the tree depth including the @p subtree_root | ||
| 616 | */ | ||
| 617 | CX_EXTERN CX_NONNULL CX_NODISCARD | ||
| 618 | size_t cxTreeSubtreeDepth(CxTree *tree, void *subtree_root); | ||
| 619 | |||
| 620 | /** | ||
| 621 | * Determines the size of the entire tree. | ||
| 622 | * | ||
| 623 | * @param tree the tree | ||
| 624 | * @return the tree size, counting the root as one | ||
| 625 | */ | ||
| 626 | CX_EXTERN CX_NONNULL CX_NODISCARD | ||
| 627 | size_t cxTreeSize(CxTree *tree); | ||
| 628 | |||
| 629 | /** | ||
| 630 | * Determines the depth of the entire tree. | ||
| 631 | * | ||
| 632 | * @param tree the tree | ||
| 633 | * @return the tree depth, counting the root as one | ||
| 634 | */ | ||
| 635 | CX_EXTERN CX_NONNULL CX_NODISCARD | ||
| 636 | size_t cxTreeDepth(CxTree *tree); | ||
| 637 | |||
| 638 | /** | ||
| 639 | * Creates a depth-first iterator for the specified tree starting in @p node. | ||
| 640 | * | ||
| 641 | * If the node is not part of the tree, the behavior is undefined. | ||
| 642 | * | ||
| 643 | * @param tree the tree to iterate | ||
| 644 | * @param node the node where to start | ||
| 645 | * @param visit_on_exit true, if the iterator shall visit a node again when | ||
| 646 | * leaving the subtree | ||
| 647 | * @return a tree iterator (depth-first) | ||
| 648 | * @see cxTreeVisit() | ||
| 649 | */ | ||
| 650 | CX_EXTERN CX_NONNULL CX_NODISCARD | ||
| 651 | CxTreeIterator cxTreeIterateSubtree(CxTree *tree, void *node, bool visit_on_exit); | ||
| 652 | |||
| 653 | /** | ||
| 654 | * Creates a breadth-first iterator for the specified tree starting in @p node. | ||
| 655 | * | ||
| 656 | * If the node is not part of the tree, the behavior is undefined. | ||
| 657 | * | ||
| 658 | * @param tree the tree to iterate | ||
| 659 | * @param node the node where to start | ||
| 660 | * @return a tree visitor (a.k.a. breadth-first iterator) | ||
| 661 | * @see cxTreeIterate() | ||
| 662 | */ | ||
| 663 | CX_EXTERN CX_NONNULL CX_NODISCARD | ||
| 664 | CxTreeIterator cxTreeVisitSubtree(CxTree *tree, void *node); | ||
| 665 | |||
| 666 | /** | ||
| 667 | * Creates a depth-first iterator for the specified tree. | ||
| 668 | * | ||
| 669 | * @param tree the tree to iterate | ||
| 670 | * @param visit_on_exit true, if the iterator shall visit a node again when | ||
| 671 | * leaving the subtree | ||
| 672 | * @return a tree iterator (depth-first) | ||
| 673 | * @see cxTreeVisit() | ||
| 674 | */ | ||
| 675 | CX_EXTERN CX_NONNULL CX_NODISCARD | ||
| 676 | CxTreeIterator cxTreeIterate(CxTree *tree, bool visit_on_exit); | ||
| 677 | |||
| 678 | /** | ||
| 679 | * Creates a breadth-first iterator for the specified tree. | ||
| 680 | * | ||
| 681 | * @param tree the tree to iterate | ||
| 682 | * @return a tree visitor (a.k.a. breadth-first iterator) | ||
| 683 | * @see cxTreeIterate() | ||
| 684 | */ | ||
| 685 | CX_EXTERN CX_NONNULL CX_NODISCARD | ||
| 686 | CxTreeIterator cxTreeVisit(CxTree *tree); | ||
| 687 | |||
| 688 | /** | ||
| 689 | * Sets the (new) parent of the specified child. | ||
| 690 | * | ||
| 691 | * If the @p child is not already a member of the tree, this function behaves | ||
| 692 | * as #cxTreeAddNode(). | ||
| 693 | * | ||
| 694 | * @param tree the tree | ||
| 695 | * @param parent the (new) parent of the child | ||
| 696 | * @param child the node to add | ||
| 697 | * @see cxTreeAddNode() | ||
| 698 | */ | ||
| 699 | CX_EXTERN CX_NONNULL | ||
| 700 | void cxTreeSetParent(CxTree *tree, void *parent, void *child); | ||
| 701 | |||
| 702 | /** | ||
| 703 | * Adds a new node to the tree. | ||
| 704 | * | ||
| 705 | * If the @p child is already a member of the tree, the behavior is undefined. | ||
| 706 | * Use #cxTreeSetParent() if you want to move a subtree to another location. | ||
| 707 | * | ||
| 708 | * @attention The node may be externally created, but MUST obey the same rules | ||
| 709 | * as if it was created by the tree itself with #cxTreeAddData() (e.g., use | ||
| 710 | * the tree's allocator). | ||
| 711 | * | ||
| 712 | * @param tree the tree | ||
| 713 | * @param parent the parent of the node to add | ||
| 714 | * @param child the node to add | ||
| 715 | * @see cxTreeSetParent() | ||
| 716 | * @see cxTreeAddData() | ||
| 717 | */ | ||
| 718 | CX_EXTERN CX_NONNULL | ||
| 719 | void cxTreeAddNode(CxTree *tree, void *parent, void *child); | ||
| 720 | |||
| 721 | /** | ||
| 722 | * Creates a new node and adds it to the tree. | ||
| 723 | * | ||
| 724 | * @param tree the tree | ||
| 725 | * @param parent the parent node of the new node | ||
| 726 | * @param data the data that will be submitted to the create function | ||
| 727 | * @return the added node or @c NULL when the allocation failed | ||
| 728 | * @see cxTreeAdd() | ||
| 729 | */ | ||
| 730 | CX_EXTERN CX_NONNULL | ||
| 731 | void *cxTreeAddData(CxTree *tree, void *parent, const void *data); | ||
| 732 | |||
| 733 | /** | ||
| 734 | * Creates a new node and adds it to the tree. | ||
| 735 | * | ||
| 736 | * @param tree the tree | ||
| 737 | * @param parent the parent node of the new node | ||
| 738 | * @return the added node or @c NULL when the allocation failed | ||
| 739 | */ | ||
| 740 | CX_EXTERN CX_NODISCARD CX_NONNULL | ||
| 741 | void *cxTreeCreateNode(CxTree *tree, void *parent); | ||
| 742 | |||
| 743 | /** | ||
| 744 | * Creates a new root node or returns the existing root node. | ||
| 745 | * | ||
| 746 | * @param tree the tree | ||
| 747 | * @return the new root node, the existing root node, or @c NULL when the allocation failed | ||
| 748 | * @see cxTreeCreateRootData() | ||
| 749 | */ | ||
| 750 | CX_EXTERN CX_NODISCARD CX_NONNULL | ||
| 751 | void *cxTreeCreateRoot(CxTree *tree); | ||
| 752 | |||
| 753 | /** | ||
| 754 | * Creates a new root node or uses the existing root node and writes the specified data to that node. | ||
| 755 | * | ||
| 756 | * @note This function immediately returns @c NULL when @c loc_data was not initialized with a positive value. | ||
| 757 | * | ||
| 758 | * @param tree the tree | ||
| 759 | * @param data the data for the root node | ||
| 760 | * @return the new root node, the existing root node, | ||
| 761 | * or @c NULL when the allocation failed or the data location is not known | ||
| 762 | * @see cxTreeCreateRoot() | ||
| 763 | */ | ||
| 764 | CX_EXTERN CX_NODISCARD CX_NONNULL | ||
| 765 | void *cxTreeCreateRootData(CxTree *tree, const void *data); | ||
| 766 | |||
| 767 | /** | ||
| 768 | * Exchanges the root of the tree. | ||
| 769 | * | ||
| 770 | * @attention The old tree nodes might need to be deallocated by the caller. | ||
| 771 | * On the other hand, when the tree has destructors registered, keep in mind | ||
| 772 | * that they will be applied to the new tree. | ||
| 773 | * In particular, using cxTreeCreate() with a @c NULL root and setting the | ||
| 774 | * root with this function is @em not equivalent to creating the tree with | ||
| 775 | * a reference to an existing root because trees created without a root will | ||
| 776 | * have destructors registered. | ||
| 777 | * | ||
| 778 | * @param tree the tree | ||
| 779 | * @param new_root the new root node | ||
| 780 | * @return the old root node (or @c NULL when the tree was empty) | ||
| 781 | */ | ||
| 782 | CX_EXTERN CX_NONNULL_ARG(1) CX_NODISCARD | ||
| 783 | void *cxTreeSetRoot(CxTree *tree, void *new_root); | ||
| 784 | |||
| 785 | /** | ||
| 786 | * A function that is invoked when a node needs to be re-linked to a new parent. | ||
| 787 | * | ||
| 788 | * When a node is re-linked, sometimes the contents need to be updated. | ||
| 789 | * This callback is invoked by #cxTreeRemoveNode() and #cxTreeDestroyNode() | ||
| 790 | * so that those updates can be applied when re-linking the children of the | ||
| 791 | * removed node. | ||
| 792 | * | ||
| 793 | * @param node the affected node | ||
| 794 | * @param old_parent the old parent of the node | ||
| 795 | * @param new_parent the new parent of the node | ||
| 796 | */ | ||
| 797 | typedef void (*cx_tree_relink_func)( | ||
| 798 | void *node, | ||
| 799 | const void *old_parent, | ||
| 800 | const void *new_parent | ||
| 801 | ); | ||
| 802 | |||
| 803 | /** | ||
| 804 | * Removes a node and re-links its children to its former parent. | ||
| 805 | * | ||
| 806 | * If the node is not part of the tree, the behavior is undefined. | ||
| 807 | * | ||
| 808 | * @note The destructor function, if any, will @em not be invoked. That means | ||
| 809 | * you will need to free the removed node by yourself, eventually. | ||
| 810 | * | ||
| 811 | * @param tree the tree | ||
| 812 | * @param node the node to remove (must not be the root node) | ||
| 813 | * @param relink_func optional callback to update the content of each re-linked | ||
| 814 | * node | ||
| 815 | * @return zero on success, non-zero if @p node is the root node of the tree | ||
| 816 | */ | ||
| 817 | CX_EXTERN CX_NONNULL_ARG(1, 2) | ||
| 818 | int cxTreeRemoveNode(CxTree *tree, void *node, cx_tree_relink_func relink_func); | ||
| 819 | |||
| 820 | /** | ||
| 821 | * Removes a node and its subtree from the tree. | ||
| 822 | * | ||
| 823 | * If the node is not part of the tree, the behavior is undefined. | ||
| 824 | * | ||
| 825 | * @note The destructor function, if any, will @em not be invoked. That means | ||
| 826 | * you will need to free the removed subtree by yourself, eventually. | ||
| 827 | * | ||
| 828 | * @param tree the tree | ||
| 829 | * @param node the node to remove | ||
| 830 | */ | ||
| 831 | CX_EXTERN CX_NONNULL | ||
| 832 | void cxTreeRemoveSubtree(CxTree *tree, void *node); | ||
| 833 | |||
| 834 | /** | ||
| 835 | * Destroys a node and re-links its children to its former parent. | ||
| 836 | * | ||
| 837 | * If the node is not part of the tree, the behavior is undefined. | ||
| 838 | * | ||
| 839 | * It is guaranteed that the simple destructor is invoked before | ||
| 840 | * the advanced destructor. | ||
| 841 | * | ||
| 842 | * @attention This function will not free the memory of the node with the | ||
| 843 | * tree's allocator, because that is usually done by the advanced destructor | ||
| 844 | * and would therefore result in a double-free. | ||
| 845 | * | ||
| 846 | * @param tree the tree | ||
| 847 | * @param node the node to destroy (must not be the root node) | ||
| 848 | * @param relink_func optional callback to update the content of each re-linked | ||
| 849 | * node | ||
| 850 | * @return zero on success, non-zero if @p node is the root node of the tree | ||
| 851 | */ | ||
| 852 | CX_EXTERN CX_NONNULL_ARG(1, 2) | ||
| 853 | int cxTreeDestroyNode(CxTree *tree, void *node, cx_tree_relink_func relink_func); | ||
| 854 | |||
| 855 | #endif //UCX_TREE_H | ||
| 856 |