Mercurial > hg > ucx / file comparison

comparison: src/cx/tree.h

src/cx/tree.h

changeset 1675
36c0fb2b60b2
parent 1549
72ad8a78378a
equal deleted inserted replaced
1674:8b0f162ac88e 1675:36c0fb2b60b2
37 #define UCX_TREE_H 37 #define UCX_TREE_H
38 38
39 #include "common.h" 39 #include "common.h"
40 40
41 #include "collection.h" 41 #include "collection.h"
42
43 #ifdef __cplusplus
44 extern "C" {
45 #endif
46 42
47 /** 43 /**
48 * A depth-first tree iterator. 44 * A depth-first tree iterator.
49 * 45 *
50 * This iterator is not position-aware in a strict sense, as it does not assume 46 * This iterator is not position-aware in a strict sense, as it does not assume
211 207
212 /** 208 /**
213 * Releases internal memory of the given tree iterator. 209 * Releases internal memory of the given tree iterator.
214 * @param iter the iterator 210 * @param iter the iterator
215 */ 211 */
216 cx_attr_nonnull 212 CX_EXTERN CX_NONNULL
217 CX_EXPORT void cxTreeIteratorDispose(CxTreeIterator *iter); 213 void cxTreeIteratorDispose(CxTreeIterator *iter);
218 214
219 /** 215 /**
220 * Releases internal memory of the given tree visitor. 216 * Releases internal memory of the given tree visitor.
221 * @param visitor the visitor 217 * @param visitor the visitor
222 */ 218 */
223 cx_attr_nonnull 219 CX_EXTERN CX_NONNULL
224 CX_EXPORT void cxTreeVisitorDispose(CxTreeVisitor *visitor); 220 void cxTreeVisitorDispose(CxTreeVisitor *visitor);
225 221
226 /** 222 /**
227 * Advises the iterator to skip the subtree below the current node and 223 * Advises the iterator to skip the subtree below the current node and
228 * also continues the current loop. 224 * also continues the current loop.
229 * 225 *
254 * the last child in the linked list (negative if there is no such pointer) 250 * the last child in the linked list (negative if there is no such pointer)
255 * @param loc_prev optional offset in the node struct for the prev pointer 251 * @param loc_prev optional offset in the node struct for the prev pointer
256 * @param loc_next offset in the node struct for the next pointer 252 * @param loc_next offset in the node struct for the next pointer
257 * @see cx_tree_unlink() 253 * @see cx_tree_unlink()
258 */ 254 */
259 cx_attr_nonnull 255 CX_EXTERN CX_NONNULL
260 CX_EXPORT void cx_tree_link(void *parent, void *node, 256 void cx_tree_link(void *parent, void *node,
261 ptrdiff_t loc_parent, ptrdiff_t loc_children, ptrdiff_t loc_last_child, 257 ptrdiff_t loc_parent, ptrdiff_t loc_children, ptrdiff_t loc_last_child,
262 ptrdiff_t loc_prev, ptrdiff_t loc_next); 258 ptrdiff_t loc_prev, ptrdiff_t loc_next);
263 259
264 /** 260 /**
265 * Unlinks a node from its parent. 261 * Unlinks a node from its parent.
273 * the last child in the linked list (negative if there is no such pointer) 269 * the last child in the linked list (negative if there is no such pointer)
274 * @param loc_prev optional offset in the node struct for the prev pointer 270 * @param loc_prev optional offset in the node struct for the prev pointer
275 * @param loc_next offset in the node struct for the next pointer 271 * @param loc_next offset in the node struct for the next pointer
276 * @see cx_tree_link() 272 * @see cx_tree_link()
277 */ 273 */
278 cx_attr_nonnull 274 CX_EXTERN CX_NONNULL
279 CX_EXPORT void cx_tree_unlink(void *node, 275 void cx_tree_unlink(void *node,
280 ptrdiff_t loc_parent, ptrdiff_t loc_children, ptrdiff_t loc_last_child, 276 ptrdiff_t loc_parent, ptrdiff_t loc_children, ptrdiff_t loc_last_child,
281 ptrdiff_t loc_prev, ptrdiff_t loc_next); 277 ptrdiff_t loc_prev, ptrdiff_t loc_next);
282 278
283 /** 279 /**
284 * Macro that can be used instead of the magic value for infinite search depth. 280 * Macro that can be used instead of the magic value for infinite search depth.
364 * @param loc_next offset in the node struct for the next pointer 360 * @param loc_next offset in the node struct for the next pointer
365 * @return zero if the node was found exactly, positive if a node was found that 361 * @return zero if the node was found exactly, positive if a node was found that
366 * could contain the node (but doesn't right now), negative if the tree does not 362 * could contain the node (but doesn't right now), negative if the tree does not
367 * contain any node that might be related to the searched data 363 * contain any node that might be related to the searched data
368 */ 364 */
369 cx_attr_nonnull cx_attr_access_w(5) 365 CX_EXTERN CX_NONNULL CX_ACCESS_W(5)
370 CX_EXPORT int cx_tree_search_data(const void *root, size_t depth, 366 int cx_tree_search_data(const void *root, size_t depth,
371 const void *data, cx_tree_search_data_func sfunc, 367 const void *data, cx_tree_search_data_func sfunc,
372 void **result, ptrdiff_t loc_children, ptrdiff_t loc_next); 368 void **result, ptrdiff_t loc_children, ptrdiff_t loc_next);
373 369
374 /** 370 /**
375 * Searches for a node in a tree. 371 * Searches for a node in a tree.
383 * with the best match according to the @p sfunc (meaning: the return value of 379 * with the best match according to the @p sfunc (meaning: the return value of
384 * @p sfunc which is closest to zero). If that is also ambiguous, an arbitrary 380 * @p sfunc which is closest to zero). If that is also ambiguous, an arbitrary
385 * node matching the criteria is returned. 381 * node matching the criteria is returned.
386 * 382 *
387 * @param root the root node 383 * @param root the root node
388 * @param depth the maximum depth (zero=indefinite, one=just root) 384 * @param depth the maximum depth (zero=indefinite, one=just root)
389 * @param node the node to search for 385 * @param node the node to search for
390 * @param sfunc the search function 386 * @param sfunc the search function
391 * @param result where the result shall be stored 387 * @param result where the result shall be stored
392 * @param loc_children offset in the node struct for the children linked list 388 * @param loc_children offset in the node struct for the children linked list
393 * @param loc_next offset in the node struct for the next pointer 389 * @param loc_next offset in the node struct for the next pointer
394 * @return zero if the node was found exactly, positive if a node was found that 390 * @return zero if the node was found exactly, positive if a node was found that
395 * could contain the node (but doesn't right now), negative if the tree does not 391 * could contain the node (but doesn't right now), negative if the tree does not
396 * contain any node that might be related to the searched data 392 * contain any node that might be related to the searched data
397 */ 393 */
398 cx_attr_nonnull cx_attr_access_w(5) 394 CX_EXTERN CX_NONNULL CX_ACCESS_W(5)
399 CX_EXPORT int cx_tree_search(const void *root, size_t depth, 395 int cx_tree_search(const void *root, size_t depth,
400 const void *node, cx_tree_search_func sfunc, 396 const void *node, cx_tree_search_func sfunc,
401 void **result, ptrdiff_t loc_children, ptrdiff_t loc_next); 397 void **result, ptrdiff_t loc_children, ptrdiff_t loc_next);
402 398
403 /** 399 /**
404 * Creates a depth-first iterator for a tree with the specified root node. 400 * Creates a depth-first iterator for a tree with the specified root node.
418 * @param loc_children offset in the node struct for the children linked list 414 * @param loc_children offset in the node struct for the children linked list
419 * @param loc_next offset in the node struct for the next pointer 415 * @param loc_next offset in the node struct for the next pointer
420 * @return the new tree iterator 416 * @return the new tree iterator
421 * @see cxTreeIteratorDispose() 417 * @see cxTreeIteratorDispose()
422 */ 418 */
423 cx_attr_nodiscard 419 CX_EXTERN CX_NODISCARD
424 CX_EXPORT CxTreeIterator cx_tree_iterator(void *root, bool visit_on_exit, 420 CxTreeIterator cx_tree_iterator(void *root, bool visit_on_exit,
425 ptrdiff_t loc_children, ptrdiff_t loc_next); 421 ptrdiff_t loc_children, ptrdiff_t loc_next);
426 422
427 /** 423 /**
428 * Creates a breadth-first iterator for a tree with the specified root node. 424 * Creates a breadth-first iterator for a tree with the specified root node.
429 * 425 *
440 * @param loc_children offset in the node struct for the children linked list 436 * @param loc_children offset in the node struct for the children linked list
441 * @param loc_next offset in the node struct for the next pointer 437 * @param loc_next offset in the node struct for the next pointer
442 * @return the new tree visitor 438 * @return the new tree visitor
443 * @see cxTreeVisitorDispose() 439 * @see cxTreeVisitorDispose()
444 */ 440 */
445 cx_attr_nodiscard 441 CX_EXTERN CX_NODISCARD
446 CX_EXPORT CxTreeVisitor cx_tree_visitor(void *root, 442 CxTreeVisitor cx_tree_visitor(void *root,
447 ptrdiff_t loc_children, ptrdiff_t loc_next); 443 ptrdiff_t loc_children, ptrdiff_t loc_next);
448 444
449 /** 445 /**
450 * Describes a function that creates a tree node from the specified data. 446 * Describes a function that creates a tree node from the specified data.
451 * The first argument points to the data the node shall contain, and 447 * The first argument points to the data the node shall contain, and
502 * @param loc_prev optional offset in the node struct for the prev pointer 498 * @param loc_prev optional offset in the node struct for the prev pointer
503 * @param loc_next offset in the node struct for the next pointer 499 * @param loc_next offset in the node struct for the next pointer
504 * @return the number of nodes created and added 500 * @return the number of nodes created and added
505 * @see cx_tree_add() 501 * @see cx_tree_add()
506 */ 502 */
507 cx_attr_nonnull_arg(1, 3, 4, 6, 7) cx_attr_access_w(6) 503 CX_EXTERN CX_NONNULL_ARG(1, 3, 4, 6, 7) CX_ACCESS_W(6)
508 CX_EXPORT size_t cx_tree_add_iter(struct cx_iterator_base_s *iter, size_t num, 504 size_t cx_tree_add_iter(struct cx_iterator_base_s *iter, size_t num,
509 cx_tree_search_func sfunc, cx_tree_node_create_func cfunc, 505 cx_tree_search_func sfunc, cx_tree_node_create_func cfunc,
510 void *cdata, void **failed, void *root, 506 void *cdata, void **failed, void *root,
511 ptrdiff_t loc_parent, ptrdiff_t loc_children, ptrdiff_t loc_last_child, 507 ptrdiff_t loc_parent, ptrdiff_t loc_children, ptrdiff_t loc_last_child,
512 ptrdiff_t loc_prev, ptrdiff_t loc_next); 508 ptrdiff_t loc_prev, ptrdiff_t loc_next);
513 509
546 * @param loc_prev optional offset in the node struct for the prev pointer 542 * @param loc_prev optional offset in the node struct for the prev pointer
547 * @param loc_next offset in the node struct for the next pointer 543 * @param loc_next offset in the node struct for the next pointer
548 * @return the number of array elements successfully processed 544 * @return the number of array elements successfully processed
549 * @see cx_tree_add() 545 * @see cx_tree_add()
550 */ 546 */
551 cx_attr_nonnull_arg(1, 4, 5, 7, 8) cx_attr_access_w(7) 547 CX_EXTERN CX_NONNULL_ARG(1, 4, 5, 7, 8) CX_ACCESS_W(7)
552 CX_EXPORT size_t cx_tree_add_array(const void *src, size_t num, size_t elem_size, 548 size_t cx_tree_add_array(const void *src, size_t num, size_t elem_size,
553 cx_tree_search_func sfunc, cx_tree_node_create_func cfunc, 549 cx_tree_search_func sfunc, cx_tree_node_create_func cfunc,
554 void *cdata, void **failed, void *root, 550 void *cdata, void **failed, void *root,
555 ptrdiff_t loc_parent, ptrdiff_t loc_children, ptrdiff_t loc_last_child, 551 ptrdiff_t loc_parent, ptrdiff_t loc_children, ptrdiff_t loc_last_child,
556 ptrdiff_t loc_prev, ptrdiff_t loc_next); 552 ptrdiff_t loc_prev, ptrdiff_t loc_next);
557 553
598 * @param loc_prev optional offset in the node struct for the prev pointer 594 * @param loc_prev optional offset in the node struct for the prev pointer
599 * @param loc_next offset in the node struct for the next pointer 595 * @param loc_next offset in the node struct for the next pointer
600 * @return zero when a new node was created and added to the tree, 596 * @return zero when a new node was created and added to the tree,
601 * non-zero otherwise 597 * non-zero otherwise
602 */ 598 */
603 cx_attr_nonnull_arg(1, 2, 3, 5, 6) cx_attr_access_w(5) 599 CX_EXTERN CX_NONNULL_ARG(1, 2, 3, 5, 6) CX_ACCESS_W(5)
604 CX_EXPORT int cx_tree_add(const void *src, 600 int cx_tree_add(const void *src,
605 cx_tree_search_func sfunc, cx_tree_node_create_func cfunc, 601 cx_tree_search_func sfunc, cx_tree_node_create_func cfunc,
606 void *cdata, void **cnode, void *root, 602 void *cdata, void **cnode, void *root,
607 ptrdiff_t loc_parent, ptrdiff_t loc_children, ptrdiff_t loc_last_child, 603 ptrdiff_t loc_parent, ptrdiff_t loc_children, ptrdiff_t loc_last_child,
608 ptrdiff_t loc_prev, ptrdiff_t loc_next); 604 ptrdiff_t loc_prev, ptrdiff_t loc_next);
609 605
784 * 780 *
785 * @param tree the tree 781 * @param tree the tree
786 * @param node the node to remove 782 * @param node the node to remove
787 * @see cxTreeFree() 783 * @see cxTreeFree()
788 */ 784 */
789 cx_attr_nonnull 785 CX_EXTERN CX_NONNULL
790 CX_EXPORT void cxTreeDestroySubtree(CxTree *tree, void *node); 786 void cxTreeDestroySubtree(CxTree *tree, void *node);
791 787
792 788
793 /** 789 /**
794 * Destroys the tree contents. 790 * Destroys the tree contents.
795 * 791 *
823 * that would cause a double-free in most scenarios where the advanced 819 * that would cause a double-free in most scenarios where the advanced
824 * destructor is already freeing the memory. 820 * destructor is already freeing the memory.
825 * 821 *
826 * @param tree the tree to free 822 * @param tree the tree to free
827 */ 823 */
828 CX_EXPORT void cxTreeFree(CxTree *tree); 824 CX_EXTERN
825 void cxTreeFree(CxTree *tree);
829 826
830 /** 827 /**
831 * Creates a new tree structure based on the specified layout. 828 * Creates a new tree structure based on the specified layout.
832 * 829 *
833 * The specified @p allocator will be used for creating the tree struct 830 * The specified @p allocator will be used for creating the tree struct
849 * @param loc_next offset in the node struct for the next pointer 846 * @param loc_next offset in the node struct for the next pointer
850 * @return the new tree 847 * @return the new tree
851 * @see cxTreeCreateSimple() 848 * @see cxTreeCreateSimple()
852 * @see cxTreeCreateWrapped() 849 * @see cxTreeCreateWrapped()
853 */ 850 */
854 cx_attr_nonnull_arg(2, 3, 4) cx_attr_nodiscard cx_attr_malloc cx_attr_dealloc(cxTreeFree, 1) 851 CX_EXTERN CX_NONNULL_ARG(2, 3, 4) CX_NODISCARD CX_MALLOC CX_DEALLOC(cxTreeFree, 1)
855 CX_EXPORT CxTree *cxTreeCreate(const CxAllocator *allocator, cx_tree_node_create_func create_func, 852 CxTree *cxTreeCreate(const CxAllocator *allocator, cx_tree_node_create_func create_func,
856 cx_tree_search_func search_func, cx_tree_search_data_func search_data_func, 853 cx_tree_search_func search_func, cx_tree_search_data_func search_data_func,
857 ptrdiff_t loc_parent, ptrdiff_t loc_children, ptrdiff_t loc_last_child, 854 ptrdiff_t loc_parent, ptrdiff_t loc_children, ptrdiff_t loc_last_child,
858 ptrdiff_t loc_prev, ptrdiff_t loc_next); 855 ptrdiff_t loc_prev, ptrdiff_t loc_next);
859 856
860 /** 857 /**
897 * @param loc_prev optional offset in the node struct for the prev pointer 894 * @param loc_prev optional offset in the node struct for the prev pointer
898 * @param loc_next offset in the node struct for the next pointer 895 * @param loc_next offset in the node struct for the next pointer
899 * @return the new tree 896 * @return the new tree
900 * @see cxTreeCreate() 897 * @see cxTreeCreate()
901 */ 898 */
902 cx_attr_nonnull_arg(2) cx_attr_nodiscard cx_attr_malloc cx_attr_dealloc(cxTreeFree, 1) 899 CX_EXTERN CX_NONNULL_ARG(2) CX_NODISCARD CX_MALLOC CX_DEALLOC(cxTreeFree, 1)
903 CX_EXPORT CxTree *cxTreeCreateWrapped(const CxAllocator *allocator, void *root, 900 CxTree *cxTreeCreateWrapped(const CxAllocator *allocator, void *root,
904 ptrdiff_t loc_parent, ptrdiff_t loc_children, ptrdiff_t loc_last_child, 901 ptrdiff_t loc_parent, ptrdiff_t loc_children, ptrdiff_t loc_last_child,
905 ptrdiff_t loc_prev, ptrdiff_t loc_next); 902 ptrdiff_t loc_prev, ptrdiff_t loc_next);
906 903
907 /** 904 /**
908 * Inserts data into the tree. 905 * Inserts data into the tree.
914 * @param tree the tree 911 * @param tree the tree
915 * @param data the data to insert 912 * @param data the data to insert
916 * @retval zero success 913 * @retval zero success
917 * @retval non-zero failure 914 * @retval non-zero failure
918 */ 915 */
919 cx_attr_nonnull 916 CX_EXTERN CX_NONNULL
920 CX_EXPORT int cxTreeInsert(CxTree *tree, const void *data); 917 int cxTreeInsert(CxTree *tree, const void *data);
921 918
922 /** 919 /**
923 * Inserts elements provided by an iterator efficiently into the tree. 920 * Inserts elements provided by an iterator efficiently into the tree.
924 * 921 *
925 * @remark For this function to work, the tree needs specified search and 922 * @remark For this function to work, the tree needs specified search and
929 * @param tree the tree 926 * @param tree the tree
930 * @param iter the iterator providing the elements 927 * @param iter the iterator providing the elements
931 * @param n the maximum number of elements to insert 928 * @param n the maximum number of elements to insert
932 * @return the number of elements that could be successfully inserted 929 * @return the number of elements that could be successfully inserted
933 */ 930 */
934 cx_attr_nonnull 931 CX_EXTERN CX_NONNULL
935 CX_EXPORT size_t cxTreeInsertIter(CxTree *tree, CxIteratorBase *iter, size_t n); 932 size_t cxTreeInsertIter(CxTree *tree, CxIteratorBase *iter, size_t n);
936 933
937 /** 934 /**
938 * Inserts an array of data efficiently into the tree. 935 * Inserts an array of data efficiently into the tree.
939 * 936 *
940 * @remark For this function to work, the tree needs specified search and 937 * @remark For this function to work, the tree needs specified search and
945 * @param data the array of data to insert 942 * @param data the array of data to insert
946 * @param elem_size the size of each element in the array 943 * @param elem_size the size of each element in the array
947 * @param n the number of elements in the array 944 * @param n the number of elements in the array
948 * @return the number of elements that could be successfully inserted 945 * @return the number of elements that could be successfully inserted
949 */ 946 */
950 cx_attr_nonnull 947 CX_EXTERN CX_NONNULL
951 CX_EXPORT size_t cxTreeInsertArray(CxTree *tree, const void *data, size_t elem_size, size_t n); 948 size_t cxTreeInsertArray(CxTree *tree, const void *data, size_t elem_size, size_t n);
952 949
953 /** 950 /**
954 * Searches the data in the specified tree. 951 * Searches the data in the specified tree.
955 * 952 *
956 * @remark For this function to work, the tree needs a specified @c search_data 953 * @remark For this function to work, the tree needs a specified @c search_data
959 * 956 *
960 * @param tree the tree 957 * @param tree the tree
961 * @param data the data to search for 958 * @param data the data to search for
962 * @return the first matching node, or @c NULL when the data cannot be found 959 * @return the first matching node, or @c NULL when the data cannot be found
963 */ 960 */
964 cx_attr_nonnull cx_attr_nodiscard 961 CX_EXTERN CX_NONNULL CX_NODISCARD
965 CX_EXPORT void *cxTreeFind(CxTree *tree, const void *data); 962 void *cxTreeFind(CxTree *tree, const void *data);
966 963
967 /** 964 /**
968 * Searches the data in the specified subtree. 965 * Searches the data in the specified subtree.
969 * 966 *
970 * When @p max_depth is zero, the depth is not limited. 967 * When @p max_depth is zero, the depth is not limited.
981 * @param data the data to search for 978 * @param data the data to search for
982 * @param subtree_root the node where to start 979 * @param subtree_root the node where to start
983 * @param max_depth the maximum search depth 980 * @param max_depth the maximum search depth
984 * @return the first matching node, or @c NULL when the data cannot be found 981 * @return the first matching node, or @c NULL when the data cannot be found
985 */ 982 */
986 cx_attr_nonnull cx_attr_nodiscard 983 CX_EXTERN CX_NONNULL CX_NODISCARD
987 CX_EXPORT void *cxTreeFindInSubtree(CxTree *tree, const void *data, void *subtree_root, size_t max_depth); 984 void *cxTreeFindInSubtree(CxTree *tree, const void *data, void *subtree_root, size_t max_depth);
988 985
989 /** 986 /**
990 * Determines the size of the specified subtree. 987 * Determines the size of the specified subtree.
991 * 988 *
992 * @param tree the tree 989 * @param tree the tree
993 * @param subtree_root the root node of the subtree 990 * @param subtree_root the root node of the subtree
994 * @return the number of nodes in the specified subtree 991 * @return the number of nodes in the specified subtree
995 */ 992 */
996 cx_attr_nonnull cx_attr_nodiscard 993 CX_EXTERN CX_NONNULL CX_NODISCARD
997 CX_EXPORT size_t cxTreeSubtreeSize(CxTree *tree, void *subtree_root); 994 size_t cxTreeSubtreeSize(CxTree *tree, void *subtree_root);
998 995
999 /** 996 /**
1000 * Determines the depth of the specified subtree. 997 * Determines the depth of the specified subtree.
1001 * 998 *
1002 * @param tree the tree 999 * @param tree the tree
1003 * @param subtree_root the root node of the subtree 1000 * @param subtree_root the root node of the subtree
1004 * @return the tree depth including the @p subtree_root 1001 * @return the tree depth including the @p subtree_root
1005 */ 1002 */
1006 cx_attr_nonnull cx_attr_nodiscard 1003 CX_EXTERN CX_NONNULL CX_NODISCARD
1007 CX_EXPORT size_t cxTreeSubtreeDepth(CxTree *tree, void *subtree_root); 1004 size_t cxTreeSubtreeDepth(CxTree *tree, void *subtree_root);
1008 1005
1009 /** 1006 /**
1010 * Determines the size of the entire tree. 1007 * Determines the size of the entire tree.
1011 * 1008 *
1012 * @param tree the tree 1009 * @param tree the tree
1013 * @return the tree size, counting the root as one 1010 * @return the tree size, counting the root as one
1014 */ 1011 */
1015 cx_attr_nonnull cx_attr_nodiscard 1012 CX_EXTERN CX_NONNULL CX_NODISCARD
1016 CX_EXPORT size_t cxTreeSize(CxTree *tree); 1013 size_t cxTreeSize(CxTree *tree);
1017 1014
1018 /** 1015 /**
1019 * Determines the depth of the entire tree. 1016 * Determines the depth of the entire tree.
1020 * 1017 *
1021 * @param tree the tree 1018 * @param tree the tree
1022 * @return the tree depth, counting the root as one 1019 * @return the tree depth, counting the root as one
1023 */ 1020 */
1024 cx_attr_nonnull cx_attr_nodiscard 1021 CX_EXTERN CX_NONNULL CX_NODISCARD
1025 CX_EXPORT size_t cxTreeDepth(CxTree *tree); 1022 size_t cxTreeDepth(CxTree *tree);
1026 1023
1027 /** 1024 /**
1028 * Creates a depth-first iterator for the specified tree starting in @p node. 1025 * Creates a depth-first iterator for the specified tree starting in @p node.
1029 * 1026 *
1030 * If the node is not part of the tree, the behavior is undefined. 1027 * If the node is not part of the tree, the behavior is undefined.
1034 * @param visit_on_exit true, if the iterator shall visit a node again when 1031 * @param visit_on_exit true, if the iterator shall visit a node again when
1035 * leaving the subtree 1032 * leaving the subtree
1036 * @return a tree iterator (depth-first) 1033 * @return a tree iterator (depth-first)
1037 * @see cxTreeVisit() 1034 * @see cxTreeVisit()
1038 */ 1035 */
1039 cx_attr_nonnull cx_attr_nodiscard 1036 CX_EXTERN CX_NONNULL CX_NODISCARD
1040 CX_EXPORT CxTreeIterator cxTreeIterateSubtree(CxTree *tree, void *node, bool visit_on_exit); 1037 CxTreeIterator cxTreeIterateSubtree(CxTree *tree, void *node, bool visit_on_exit);
1041 1038
1042 /** 1039 /**
1043 * Creates a breadth-first iterator for the specified tree starting in @p node. 1040 * Creates a breadth-first iterator for the specified tree starting in @p node.
1044 * 1041 *
1045 * If the node is not part of the tree, the behavior is undefined. 1042 * If the node is not part of the tree, the behavior is undefined.
1047 * @param tree the tree to iterate 1044 * @param tree the tree to iterate
1048 * @param node the node where to start 1045 * @param node the node where to start
1049 * @return a tree visitor (a.k.a. breadth-first iterator) 1046 * @return a tree visitor (a.k.a. breadth-first iterator)
1050 * @see cxTreeIterate() 1047 * @see cxTreeIterate()
1051 */ 1048 */
1052 cx_attr_nonnull cx_attr_nodiscard 1049 CX_EXTERN CX_NONNULL CX_NODISCARD
1053 CX_EXPORT CxTreeVisitor cxTreeVisitSubtree(CxTree *tree, void *node); 1050 CxTreeVisitor cxTreeVisitSubtree(CxTree *tree, void *node);
1054 1051
1055 /** 1052 /**
1056 * Creates a depth-first iterator for the specified tree. 1053 * Creates a depth-first iterator for the specified tree.
1057 * 1054 *
1058 * @param tree the tree to iterate 1055 * @param tree the tree to iterate
1059 * @param visit_on_exit true, if the iterator shall visit a node again when 1056 * @param visit_on_exit true, if the iterator shall visit a node again when
1060 * leaving the subtree 1057 * leaving the subtree
1061 * @return a tree iterator (depth-first) 1058 * @return a tree iterator (depth-first)
1062 * @see cxTreeVisit() 1059 * @see cxTreeVisit()
1063 */ 1060 */
1064 cx_attr_nonnull cx_attr_nodiscard 1061 CX_EXTERN CX_NONNULL CX_NODISCARD
1065 CX_EXPORT CxTreeIterator cxTreeIterate(CxTree *tree, bool visit_on_exit); 1062 CxTreeIterator cxTreeIterate(CxTree *tree, bool visit_on_exit);
1066 1063
1067 /** 1064 /**
1068 * Creates a breadth-first iterator for the specified tree. 1065 * Creates a breadth-first iterator for the specified tree.
1069 * 1066 *
1070 * @param tree the tree to iterate 1067 * @param tree the tree to iterate
1071 * @return a tree visitor (a.k.a. breadth-first iterator) 1068 * @return a tree visitor (a.k.a. breadth-first iterator)
1072 * @see cxTreeIterate() 1069 * @see cxTreeIterate()
1073 */ 1070 */
1074 cx_attr_nonnull cx_attr_nodiscard 1071 CX_EXTERN CX_NONNULL CX_NODISCARD
1075 CX_EXPORT CxTreeVisitor cxTreeVisit(CxTree *tree); 1072 CxTreeVisitor cxTreeVisit(CxTree *tree);
1076 1073
1077 /** 1074 /**
1078 * Sets the (new) parent of the specified child. 1075 * Sets the (new) parent of the specified child.
1079 * 1076 *
1080 * If the @p child is not already a member of the tree, this function behaves 1077 * If the @p child is not already a member of the tree, this function behaves
1083 * @param tree the tree 1080 * @param tree the tree
1084 * @param parent the (new) parent of the child 1081 * @param parent the (new) parent of the child
1085 * @param child the node to add 1082 * @param child the node to add
1086 * @see cxTreeAddChildNode() 1083 * @see cxTreeAddChildNode()
1087 */ 1084 */
1088 cx_attr_nonnull 1085 CX_EXTERN CX_NONNULL
1089 CX_EXPORT void cxTreeSetParent(CxTree *tree, void *parent, void *child); 1086 void cxTreeSetParent(CxTree *tree, void *parent, void *child);
1090 1087
1091 /** 1088 /**
1092 * Adds a new node to the tree. 1089 * Adds a new node to the tree.
1093 * 1090 *
1094 * If the @p child is already a member of the tree, the behavior is undefined. 1091 * If the @p child is already a member of the tree, the behavior is undefined.
1101 * @param tree the tree 1098 * @param tree the tree
1102 * @param parent the parent of the node to add 1099 * @param parent the parent of the node to add
1103 * @param child the node to add 1100 * @param child the node to add
1104 * @see cxTreeSetParent() 1101 * @see cxTreeSetParent()
1105 */ 1102 */
1106 cx_attr_nonnull 1103 CX_EXTERN CX_NONNULL
1107 CX_EXPORT void cxTreeAddChildNode(CxTree *tree, void *parent, void *child); 1104 void cxTreeAddChildNode(CxTree *tree, void *parent, void *child);
1108 1105
1109 /** 1106 /**
1110 * Creates a new node and adds it to the tree. 1107 * Creates a new node and adds it to the tree.
1111 * 1108 *
1112 * With this function you can decide where exactly the new node shall be added. 1109 * With this function you can decide where exactly the new node shall be added.
1121 * @param parent the parent node of the new node 1118 * @param parent the parent node of the new node
1122 * @param data the data that will be submitted to the create function 1119 * @param data the data that will be submitted to the create function
1123 * @return zero when the new node was created, non-zero on allocation failure 1120 * @return zero when the new node was created, non-zero on allocation failure
1124 * @see cxTreeInsert() 1121 * @see cxTreeInsert()
1125 */ 1122 */
1126 cx_attr_nonnull 1123 CX_EXTERN CX_NONNULL
1127 CX_EXPORT int cxTreeAddChild(CxTree *tree, void *parent, const void *data); 1124 int cxTreeAddChild(CxTree *tree, void *parent, const void *data);
1128 1125
1129 /** 1126 /**
1130 * A function that is invoked when a node needs to be re-linked to a new parent. 1127 * A function that is invoked when a node needs to be re-linked to a new parent.
1131 * 1128 *
1132 * When a node is re-linked, sometimes the contents need to be updated. 1129 * When a node is re-linked, sometimes the contents need to be updated.
1156 * @param node the node to remove (must not be the root node) 1153 * @param node the node to remove (must not be the root node)
1157 * @param relink_func optional callback to update the content of each re-linked 1154 * @param relink_func optional callback to update the content of each re-linked
1158 * node 1155 * node
1159 * @return zero on success, non-zero if @p node is the root node of the tree 1156 * @return zero on success, non-zero if @p node is the root node of the tree
1160 */ 1157 */
1161 cx_attr_nonnull_arg(1, 2) 1158 CX_EXTERN CX_NONNULL_ARG(1, 2)
1162 CX_EXPORT int cxTreeRemoveNode(CxTree *tree, void *node, cx_tree_relink_func relink_func); 1159 int cxTreeRemoveNode(CxTree *tree, void *node, cx_tree_relink_func relink_func);
1163 1160
1164 /** 1161 /**
1165 * Removes a node and its subtree from the tree. 1162 * Removes a node and its subtree from the tree.
1166 * 1163 *
1167 * If the node is not part of the tree, the behavior is undefined. 1164 * If the node is not part of the tree, the behavior is undefined.
1170 * you will need to free the removed subtree by yourself, eventually. 1167 * you will need to free the removed subtree by yourself, eventually.
1171 * 1168 *
1172 * @param tree the tree 1169 * @param tree the tree
1173 * @param node the node to remove 1170 * @param node the node to remove
1174 */ 1171 */
1175 cx_attr_nonnull 1172 CX_EXTERN CX_NONNULL
1176 CX_EXPORT void cxTreeRemoveSubtree(CxTree *tree, void *node); 1173 void cxTreeRemoveSubtree(CxTree *tree, void *node);
1177 1174
1178 /** 1175 /**
1179 * Destroys a node and re-links its children to its former parent. 1176 * Destroys a node and re-links its children to its former parent.
1180 * 1177 *
1181 * If the node is not part of the tree, the behavior is undefined. 1178 * If the node is not part of the tree, the behavior is undefined.
1191 * @param node the node to destroy (must not be the root node) 1188 * @param node the node to destroy (must not be the root node)
1192 * @param relink_func optional callback to update the content of each re-linked 1189 * @param relink_func optional callback to update the content of each re-linked
1193 * node 1190 * node
1194 * @return zero on success, non-zero if @p node is the root node of the tree 1191 * @return zero on success, non-zero if @p node is the root node of the tree
1195 */ 1192 */
1196 cx_attr_nonnull_arg(1, 2) 1193 CX_EXTERN CX_NONNULL_ARG(1, 2)
1197 CX_EXPORT int cxTreeDestroyNode(CxTree *tree, void *node, cx_tree_relink_func relink_func); 1194 int cxTreeDestroyNode(CxTree *tree, void *node, cx_tree_relink_func relink_func);
1198
1199 #ifdef __cplusplus
1200 } // extern "C"
1201 #endif
1202 1195
1203 #endif //UCX_TREE_H 1196 #endif //UCX_TREE_H

Mercurial Repository: ucx

mercurial