src/cx/tree.h

changeset 1426
3a89b31f0724
parent 1424
563033aa998c
equal deleted inserted replaced
1425:83284b289430 1426:3a89b31f0724
210 /** 210 /**
211 * Releases internal memory of the given tree iterator. 211 * Releases internal memory of the given tree iterator.
212 * @param iter the iterator 212 * @param iter the iterator
213 */ 213 */
214 cx_attr_nonnull 214 cx_attr_nonnull
215 static inline void cxTreeIteratorDispose(CxTreeIterator *iter) { 215 CX_EXPORT void cxTreeIteratorDispose(CxTreeIterator *iter);
216 cxFreeDefault(iter->stack);
217 iter->stack = NULL;
218 }
219 216
220 /** 217 /**
221 * Releases internal memory of the given tree visitor. 218 * Releases internal memory of the given tree visitor.
222 * @param visitor the visitor 219 * @param visitor the visitor
223 */ 220 */
224 cx_attr_nonnull 221 cx_attr_nonnull
225 static inline void cxTreeVisitorDispose(CxTreeVisitor *visitor) { 222 CX_EXPORT void cxTreeVisitorDispose(CxTreeVisitor *visitor);
226 struct cx_tree_visitor_queue_s *q = visitor->queue_next;
227 while (q != NULL) {
228 struct cx_tree_visitor_queue_s *next = q->next;
229 cxFreeDefault(q);
230 q = next;
231 }
232 }
233 223
234 /** 224 /**
235 * Advises the iterator to skip the subtree below the current node and 225 * Advises the iterator to skip the subtree below the current node and
236 * also continues the current loop. 226 * also continues the current loop.
237 * 227 *
263 * @param loc_prev optional offset in the node struct for the prev pointer 253 * @param loc_prev optional offset in the node struct for the prev pointer
264 * @param loc_next offset in the node struct for the next pointer 254 * @param loc_next offset in the node struct for the next pointer
265 * @see cx_tree_unlink() 255 * @see cx_tree_unlink()
266 */ 256 */
267 cx_attr_nonnull 257 cx_attr_nonnull
268 cx_attr_export 258 CX_EXPORT void cx_tree_link(void *parent, void *node,
269 void cx_tree_link( 259 ptrdiff_t loc_parent, ptrdiff_t loc_children, ptrdiff_t loc_last_child,
270 void *parent, 260 ptrdiff_t loc_prev, ptrdiff_t loc_next);
271 void *node,
272 ptrdiff_t loc_parent,
273 ptrdiff_t loc_children,
274 ptrdiff_t loc_last_child,
275 ptrdiff_t loc_prev,
276 ptrdiff_t loc_next
277 );
278 261
279 /** 262 /**
280 * Unlinks a node from its parent. 263 * Unlinks a node from its parent.
281 * 264 *
282 * If the node has no parent, this function does nothing. 265 * If the node has no parent, this function does nothing.
289 * @param loc_prev optional offset in the node struct for the prev pointer 272 * @param loc_prev optional offset in the node struct for the prev pointer
290 * @param loc_next offset in the node struct for the next pointer 273 * @param loc_next offset in the node struct for the next pointer
291 * @see cx_tree_link() 274 * @see cx_tree_link()
292 */ 275 */
293 cx_attr_nonnull 276 cx_attr_nonnull
294 cx_attr_export 277 CX_EXPORT void cx_tree_unlink(void *node,
295 void cx_tree_unlink( 278 ptrdiff_t loc_parent, ptrdiff_t loc_children, ptrdiff_t loc_last_child,
296 void *node, 279 ptrdiff_t loc_prev, ptrdiff_t loc_next);
297 ptrdiff_t loc_parent,
298 ptrdiff_t loc_children,
299 ptrdiff_t loc_last_child,
300 ptrdiff_t loc_prev,
301 ptrdiff_t loc_next
302 );
303 280
304 /** 281 /**
305 * Macro that can be used instead of the magic value for infinite search depth. 282 * Macro that can be used instead of the magic value for infinite search depth.
306 */ 283 */
307 #define CX_TREE_SEARCH_INFINITE_DEPTH 0 284 #define CX_TREE_SEARCH_INFINITE_DEPTH 0
330 * 307 *
331 * @return 0 if the node contains the data, 308 * @return 0 if the node contains the data,
332 * positive if one of the children might contain the data, 309 * positive if one of the children might contain the data,
333 * negative if neither the node nor the children contains the data 310 * negative if neither the node nor the children contains the data
334 */ 311 */
335 cx_attr_nonnull
336 typedef int (*cx_tree_search_data_func)(const void *node, const void *data); 312 typedef int (*cx_tree_search_data_func)(const void *node, const void *data);
337 313
338 314
339 /** 315 /**
340 * Function pointer for a search function. 316 * Function pointer for a search function.
360 * 336 *
361 * @return 0 if @p node contains the same data as @p new_node, 337 * @return 0 if @p node contains the same data as @p new_node,
362 * positive if one of the children might contain the data, 338 * positive if one of the children might contain the data,
363 * negative if neither the node nor the children contains the data 339 * negative if neither the node nor the children contains the data
364 */ 340 */
365 cx_attr_nonnull
366 typedef int (*cx_tree_search_func)(const void *node, const void *new_node); 341 typedef int (*cx_tree_search_func)(const void *node, const void *new_node);
367 342
368 /** 343 /**
369 * Searches for data in a tree. 344 * Searches for data in a tree.
370 * 345 *
387 * @param loc_next offset in the node struct for the next pointer 362 * @param loc_next offset in the node struct for the next pointer
388 * @return zero if the node was found exactly, positive if a node was found that 363 * @return zero if the node was found exactly, positive if a node was found that
389 * could contain the node (but doesn't right now), negative if the tree does not 364 * could contain the node (but doesn't right now), negative if the tree does not
390 * contain any node that might be related to the searched data 365 * contain any node that might be related to the searched data
391 */ 366 */
392 cx_attr_nonnull 367 cx_attr_nonnull cx_attr_access_w(5)
393 cx_attr_access_w(5) 368 CX_EXPORT int cx_tree_search_data(const void *root, size_t depth,
394 cx_attr_export 369 const void *data, cx_tree_search_data_func sfunc,
395 int cx_tree_search_data( 370 void **result, ptrdiff_t loc_children, ptrdiff_t loc_next);
396 const void *root,
397 size_t depth,
398 const void *data,
399 cx_tree_search_data_func sfunc,
400 void **result,
401 ptrdiff_t loc_children,
402 ptrdiff_t loc_next
403 );
404 371
405 /** 372 /**
406 * Searches for a node in a tree. 373 * Searches for a node in a tree.
407 * 374 *
408 * When no node with the same data can be found, the search function might 375 * When no node with the same data can be found, the search function might
424 * @param loc_next offset in the node struct for the next pointer 391 * @param loc_next offset in the node struct for the next pointer
425 * @return zero if the node was found exactly, positive if a node was found that 392 * @return zero if the node was found exactly, positive if a node was found that
426 * could contain the node (but doesn't right now), negative if the tree does not 393 * could contain the node (but doesn't right now), negative if the tree does not
427 * contain any node that might be related to the searched data 394 * contain any node that might be related to the searched data
428 */ 395 */
429 cx_attr_nonnull 396 cx_attr_nonnull cx_attr_access_w(5)
430 cx_attr_access_w(5) 397 CX_EXPORT int cx_tree_search(const void *root, size_t depth,
431 cx_attr_export 398 const void *node, cx_tree_search_func sfunc,
432 int cx_tree_search( 399 void **result, ptrdiff_t loc_children, ptrdiff_t loc_next);
433 const void *root,
434 size_t depth,
435 const void *node,
436 cx_tree_search_func sfunc,
437 void **result,
438 ptrdiff_t loc_children,
439 ptrdiff_t loc_next
440 );
441 400
442 /** 401 /**
443 * Creates a depth-first iterator for a tree with the specified root node. 402 * Creates a depth-first iterator for a tree with the specified root node.
444 * 403 *
445 * @note A tree iterator needs to maintain a stack of visited nodes, which is 404 * @note A tree iterator needs to maintain a stack of visited nodes, which is
458 * @param loc_next offset in the node struct for the next pointer 417 * @param loc_next offset in the node struct for the next pointer
459 * @return the new tree iterator 418 * @return the new tree iterator
460 * @see cxTreeIteratorDispose() 419 * @see cxTreeIteratorDispose()
461 */ 420 */
462 cx_attr_nodiscard 421 cx_attr_nodiscard
463 cx_attr_export 422 CX_EXPORT CxTreeIterator cx_tree_iterator(void *root, bool visit_on_exit,
464 CxTreeIterator cx_tree_iterator( 423 ptrdiff_t loc_children, ptrdiff_t loc_next);
465 void *root,
466 bool visit_on_exit,
467 ptrdiff_t loc_children,
468 ptrdiff_t loc_next
469 );
470 424
471 /** 425 /**
472 * Creates a breadth-first iterator for a tree with the specified root node. 426 * Creates a breadth-first iterator for a tree with the specified root node.
473 * 427 *
474 * @note A tree visitor needs to maintain a queue of to-be visited nodes, which 428 * @note A tree visitor needs to maintain a queue of to-be visited nodes, which
485 * @param loc_next offset in the node struct for the next pointer 439 * @param loc_next offset in the node struct for the next pointer
486 * @return the new tree visitor 440 * @return the new tree visitor
487 * @see cxTreeVisitorDispose() 441 * @see cxTreeVisitorDispose()
488 */ 442 */
489 cx_attr_nodiscard 443 cx_attr_nodiscard
490 cx_attr_export 444 CX_EXPORT CxTreeVisitor cx_tree_visitor(void *root,
491 CxTreeVisitor cx_tree_visitor( 445 ptrdiff_t loc_children, ptrdiff_t loc_next);
492 void *root,
493 ptrdiff_t loc_children,
494 ptrdiff_t loc_next
495 );
496 446
497 /** 447 /**
498 * Describes a function that creates a tree node from the specified data. 448 * Describes a function that creates a tree node from the specified data.
499 * The first argument points to the data the node shall contain, and 449 * The first argument points to the data the node shall contain, and
500 * the second argument may be used for additional data (e.g., an allocator). 450 * the second argument may be used for additional data (e.g., an allocator).
502 * created node or @c NULL when allocation fails. 452 * created node or @c NULL when allocation fails.
503 * 453 *
504 * @note the function may leave the node pointers in the struct uninitialized. 454 * @note the function may leave the node pointers in the struct uninitialized.
505 * The caller is responsible to set them according to the intended use case. 455 * The caller is responsible to set them according to the intended use case.
506 */ 456 */
507 cx_attr_nonnull_arg(1)
508 typedef void *(*cx_tree_node_create_func)(const void *, void *); 457 typedef void *(*cx_tree_node_create_func)(const void *, void *);
509 458
510 /** 459 /**
511 * The local search depth for a new subtree when adding multiple elements. 460 * The local search depth for a new subtree when adding multiple elements.
512 * The default value is 3. 461 * The default value is 3.
513 * This variable is used by #cx_tree_add_array() and #cx_tree_add_iter() to 462 * This variable is used by #cx_tree_add_array() and #cx_tree_add_iter() to
514 * implement optimized insertion of multiple elements into a tree. 463 * implement optimized insertion of multiple elements into a tree.
515 */ 464 */
516 cx_attr_export 465 CX_EXPORT extern unsigned int cx_tree_add_look_around_depth;
517 extern unsigned int cx_tree_add_look_around_depth;
518 466
519 /** 467 /**
520 * Adds multiple elements efficiently to a tree. 468 * Adds multiple elements efficiently to a tree.
521 * 469 *
522 * Once an element cannot be added to the tree, this function returns, leaving 470 * Once an element cannot be added to the tree, this function returns, leaving
552 * @param loc_prev optional offset in the node struct for the prev pointer 500 * @param loc_prev optional offset in the node struct for the prev pointer
553 * @param loc_next offset in the node struct for the next pointer 501 * @param loc_next offset in the node struct for the next pointer
554 * @return the number of nodes created and added 502 * @return the number of nodes created and added
555 * @see cx_tree_add() 503 * @see cx_tree_add()
556 */ 504 */
557 cx_attr_nonnull_arg(1, 3, 4, 6, 7) 505 cx_attr_nonnull_arg(1, 3, 4, 6, 7) cx_attr_access_w(6)
558 cx_attr_access_w(6) 506 CX_EXPORT size_t cx_tree_add_iter(struct cx_iterator_base_s *iter, size_t num,
559 cx_attr_export 507 cx_tree_search_func sfunc, cx_tree_node_create_func cfunc,
560 size_t cx_tree_add_iter( 508 void *cdata, void **failed, void *root,
561 struct cx_iterator_base_s *iter, 509 ptrdiff_t loc_parent, ptrdiff_t loc_children, ptrdiff_t loc_last_child,
562 size_t num, 510 ptrdiff_t loc_prev, ptrdiff_t loc_next);
563 cx_tree_search_func sfunc,
564 cx_tree_node_create_func cfunc,
565 void *cdata,
566 void **failed,
567 void *root,
568 ptrdiff_t loc_parent,
569 ptrdiff_t loc_children,
570 ptrdiff_t loc_last_child,
571 ptrdiff_t loc_prev,
572 ptrdiff_t loc_next
573 );
574 511
575 /** 512 /**
576 * Adds multiple elements efficiently to a tree. 513 * Adds multiple elements efficiently to a tree.
577 * 514 *
578 * Once an element cannot be added to the tree, this function returns, storing 515 * Once an element cannot be added to the tree, this function returns, storing
607 * @param loc_prev optional offset in the node struct for the prev pointer 544 * @param loc_prev optional offset in the node struct for the prev pointer
608 * @param loc_next offset in the node struct for the next pointer 545 * @param loc_next offset in the node struct for the next pointer
609 * @return the number of array elements successfully processed 546 * @return the number of array elements successfully processed
610 * @see cx_tree_add() 547 * @see cx_tree_add()
611 */ 548 */
612 cx_attr_nonnull_arg(1, 4, 5, 7, 8) 549 cx_attr_nonnull_arg(1, 4, 5, 7, 8) cx_attr_access_w(7)
613 cx_attr_access_w(7) 550 CX_EXPORT size_t cx_tree_add_array(const void *src, size_t num, size_t elem_size,
614 cx_attr_export 551 cx_tree_search_func sfunc, cx_tree_node_create_func cfunc,
615 size_t cx_tree_add_array( 552 void *cdata, void **failed, void *root,
616 const void *src, 553 ptrdiff_t loc_parent, ptrdiff_t loc_children, ptrdiff_t loc_last_child,
617 size_t num, 554 ptrdiff_t loc_prev, ptrdiff_t loc_next);
618 size_t elem_size,
619 cx_tree_search_func sfunc,
620 cx_tree_node_create_func cfunc,
621 void *cdata,
622 void **failed,
623 void *root,
624 ptrdiff_t loc_parent,
625 ptrdiff_t loc_children,
626 ptrdiff_t loc_last_child,
627 ptrdiff_t loc_prev,
628 ptrdiff_t loc_next
629 );
630 555
631 /** 556 /**
632 * Adds data to a tree. 557 * Adds data to a tree.
633 * 558 *
634 * An adequate location where to add the new tree node is searched with the 559 * An adequate location where to add the new tree node is searched with the
671 * @param loc_prev optional offset in the node struct for the prev pointer 596 * @param loc_prev optional offset in the node struct for the prev pointer
672 * @param loc_next offset in the node struct for the next pointer 597 * @param loc_next offset in the node struct for the next pointer
673 * @return zero when a new node was created and added to the tree, 598 * @return zero when a new node was created and added to the tree,
674 * non-zero otherwise 599 * non-zero otherwise
675 */ 600 */
676 cx_attr_nonnull_arg(1, 2, 3, 5, 6) 601 cx_attr_nonnull_arg(1, 2, 3, 5, 6) cx_attr_access_w(5)
677 cx_attr_access_w(5) 602 CX_EXPORT int cx_tree_add(const void *src,
678 cx_attr_export 603 cx_tree_search_func sfunc, cx_tree_node_create_func cfunc,
679 int cx_tree_add( 604 void *cdata, void **cnode, void *root,
680 const void *src, 605 ptrdiff_t loc_parent, ptrdiff_t loc_children, ptrdiff_t loc_last_child,
681 cx_tree_search_func sfunc, 606 ptrdiff_t loc_prev, ptrdiff_t loc_next);
682 cx_tree_node_create_func cfunc,
683 void *cdata,
684 void **cnode,
685 void *root,
686 ptrdiff_t loc_parent,
687 ptrdiff_t loc_children,
688 ptrdiff_t loc_last_child,
689 ptrdiff_t loc_prev,
690 ptrdiff_t loc_next
691 );
692 607
693 608
694 /** 609 /**
695 * Tree class type. 610 * Tree class type.
696 */ 611 */
848 * Member function for inserting a single element. 763 * Member function for inserting a single element.
849 * 764 *
850 * Implementations SHALL NOT simply invoke @p insert_many as this comes 765 * Implementations SHALL NOT simply invoke @p insert_many as this comes
851 * with too much overhead. 766 * with too much overhead.
852 */ 767 */
853 int (*insert_element)( 768 int (*insert_element)(struct cx_tree_s *tree, const void *data);
854 struct cx_tree_s *tree,
855 const void *data
856 );
857 769
858 /** 770 /**
859 * Member function for inserting multiple elements. 771 * Member function for inserting multiple elements.
860 * 772 *
861 * Implementations SHALL avoid performing a full search in the tree for 773 * Implementations SHALL avoid performing a full search in the tree for
862 * every element even though the source data MAY be unsorted. 774 * every element even though the source data MAY be unsorted.
863 */ 775 */
864 size_t (*insert_many)( 776 size_t (*insert_many)(struct cx_tree_s *tree, struct cx_iterator_base_s *iter, size_t n);
865 struct cx_tree_s *tree,
866 struct cx_iterator_base_s *iter,
867 size_t n
868 );
869 777
870 /** 778 /**
871 * Member function for finding a node. 779 * Member function for finding a node.
872 */ 780 */
873 void *(*find)( 781 void *(*find)(struct cx_tree_s *tree, const void *subtree, const void *data, size_t depth);
874 struct cx_tree_s *tree,
875 const void *subtree,
876 const void *data,
877 size_t depth
878 );
879 }; 782 };
880 783
881 /** 784 /**
882 * Common type for all tree implementations. 785 * Common type for all tree implementations.
883 */ 786 */
904 * @param tree the tree 807 * @param tree the tree
905 * @param node the node to remove 808 * @param node the node to remove
906 * @see cxTreeFree() 809 * @see cxTreeFree()
907 */ 810 */
908 cx_attr_nonnull 811 cx_attr_nonnull
909 cx_attr_export 812 CX_EXPORT void cxTreeDestroySubtree(CxTree *tree, void *node);
910 void cxTreeDestroySubtree(CxTree *tree, void *node);
911 813
912 814
913 /** 815 /**
914 * Destroys the tree contents. 816 * Destroys the tree contents.
915 * 817 *
943 * that would cause a double-free in most scenarios where the advanced 845 * that would cause a double-free in most scenarios where the advanced
944 * destructor is already freeing the memory. 846 * destructor is already freeing the memory.
945 * 847 *
946 * @param tree the tree to free 848 * @param tree the tree to free
947 */ 849 */
948 cx_attr_export 850 CX_EXPORT void cxTreeFree(CxTree *tree);
949 void cxTreeFree(CxTree *tree);
950 851
951 /** 852 /**
952 * Creates a new tree structure based on the specified layout. 853 * Creates a new tree structure based on the specified layout.
953 * 854 *
954 * The specified @p allocator will be used for creating the tree struct 855 * The specified @p allocator will be used for creating the tree struct
970 * @param loc_next offset in the node struct for the next pointer 871 * @param loc_next offset in the node struct for the next pointer
971 * @return the new tree 872 * @return the new tree
972 * @see cxTreeCreateSimple() 873 * @see cxTreeCreateSimple()
973 * @see cxTreeCreateWrapped() 874 * @see cxTreeCreateWrapped()
974 */ 875 */
975 cx_attr_nonnull_arg(2, 3, 4) 876 cx_attr_nonnull_arg(2, 3, 4) cx_attr_nodiscard cx_attr_malloc cx_attr_dealloc(cxTreeFree, 1)
976 cx_attr_nodiscard 877 CX_EXPORT CxTree *cxTreeCreate(const CxAllocator *allocator, cx_tree_node_create_func create_func,
977 cx_attr_malloc 878 cx_tree_search_func search_func, cx_tree_search_data_func search_data_func,
978 cx_attr_dealloc(cxTreeFree, 1) 879 ptrdiff_t loc_parent, ptrdiff_t loc_children, ptrdiff_t loc_last_child,
979 cx_attr_export 880 ptrdiff_t loc_prev, ptrdiff_t loc_next);
980 CxTree *cxTreeCreate(
981 const CxAllocator *allocator,
982 cx_tree_node_create_func create_func,
983 cx_tree_search_func search_func,
984 cx_tree_search_data_func search_data_func,
985 ptrdiff_t loc_parent,
986 ptrdiff_t loc_children,
987 ptrdiff_t loc_last_child,
988 ptrdiff_t loc_prev,
989 ptrdiff_t loc_next
990 );
991 881
992 /** 882 /**
993 * Creates a new tree structure based on a default layout. 883 * Creates a new tree structure based on a default layout.
994 * 884 *
995 * Nodes created by @p create_func MUST contain #cx_tree_node_base_s as the first 885 * Nodes created by @p create_func MUST contain #cx_tree_node_base_s as the first
1004 * @param search_func (@c cx_tree_search_func) a function that compares two nodes 894 * @param search_func (@c cx_tree_search_func) a function that compares two nodes
1005 * @param search_data_func (@c cx_tree_search_data_func) a function that compares a node with data 895 * @param search_data_func (@c cx_tree_search_data_func) a function that compares a node with data
1006 * @return (@c CxTree*) the new tree 896 * @return (@c CxTree*) the new tree
1007 * @see cxTreeCreate() 897 * @see cxTreeCreate()
1008 */ 898 */
1009 #define cxTreeCreateSimple(\ 899 #define cxTreeCreateSimple(allocator, create_func, search_func, search_data_func) \
1010 allocator, create_func, search_func, search_data_func \ 900 cxTreeCreate(allocator, create_func, search_func, search_data_func, cx_tree_node_base_layout)
1011 ) cxTreeCreate(allocator, create_func, search_func, search_data_func, \
1012 cx_tree_node_base_layout)
1013 901
1014 /** 902 /**
1015 * Creates a new tree structure based on an existing tree. 903 * Creates a new tree structure based on an existing tree.
1016 * 904 *
1017 * The specified @p allocator will be used for creating the tree struct. 905 * The specified @p allocator will be used for creating the tree struct.
1031 * @param loc_prev optional offset in the node struct for the prev pointer 919 * @param loc_prev optional offset in the node struct for the prev pointer
1032 * @param loc_next offset in the node struct for the next pointer 920 * @param loc_next offset in the node struct for the next pointer
1033 * @return the new tree 921 * @return the new tree
1034 * @see cxTreeCreate() 922 * @see cxTreeCreate()
1035 */ 923 */
1036 cx_attr_nonnull_arg(2) 924 cx_attr_nonnull_arg(2) cx_attr_nodiscard cx_attr_malloc cx_attr_dealloc(cxTreeFree, 1)
1037 cx_attr_nodiscard 925 CX_EXPORT CxTree *cxTreeCreateWrapped(const CxAllocator *allocator, void *root,
1038 cx_attr_malloc 926 ptrdiff_t loc_parent, ptrdiff_t loc_children, ptrdiff_t loc_last_child,
1039 cx_attr_dealloc(cxTreeFree, 1) 927 ptrdiff_t loc_prev, ptrdiff_t loc_next);
1040 cx_attr_export
1041 CxTree *cxTreeCreateWrapped(
1042 const CxAllocator *allocator,
1043 void *root,
1044 ptrdiff_t loc_parent,
1045 ptrdiff_t loc_children,
1046 ptrdiff_t loc_last_child,
1047 ptrdiff_t loc_prev,
1048 ptrdiff_t loc_next
1049 );
1050 928
1051 /** 929 /**
1052 * Inserts data into the tree. 930 * Inserts data into the tree.
1053 * 931 *
1054 * @remark For this function to work, the tree needs specified search and 932 * @remark For this function to work, the tree needs specified search and
1059 * @param data the data to insert 937 * @param data the data to insert
1060 * @retval zero success 938 * @retval zero success
1061 * @retval non-zero failure 939 * @retval non-zero failure
1062 */ 940 */
1063 cx_attr_nonnull 941 cx_attr_nonnull
1064 static inline int cxTreeInsert( 942 CX_EXPORT int cxTreeInsert(CxTree *tree, const void *data);
1065 CxTree *tree,
1066 const void *data
1067 ) {
1068 return tree->cl->insert_element(tree, data);
1069 }
1070 943
1071 /** 944 /**
1072 * Inserts elements provided by an iterator efficiently into the tree. 945 * Inserts elements provided by an iterator efficiently into the tree.
1073 * 946 *
1074 * @remark For this function to work, the tree needs specified search and 947 * @remark For this function to work, the tree needs specified search and
1079 * @param iter the iterator providing the elements 952 * @param iter the iterator providing the elements
1080 * @param n the maximum number of elements to insert 953 * @param n the maximum number of elements to insert
1081 * @return the number of elements that could be successfully inserted 954 * @return the number of elements that could be successfully inserted
1082 */ 955 */
1083 cx_attr_nonnull 956 cx_attr_nonnull
1084 static inline size_t cxTreeInsertIter( 957 CX_EXPORT size_t cxTreeInsertIter(CxTree *tree, CxIteratorBase *iter, size_t n);
1085 CxTree *tree,
1086 CxIteratorBase *iter,
1087 size_t n
1088 ) {
1089 return tree->cl->insert_many(tree, iter, n);
1090 }
1091 958
1092 /** 959 /**
1093 * Inserts an array of data efficiently into the tree. 960 * Inserts an array of data efficiently into the tree.
1094 * 961 *
1095 * @remark For this function to work, the tree needs specified search and 962 * @remark For this function to work, the tree needs specified search and
1101 * @param elem_size the size of each element in the array 968 * @param elem_size the size of each element in the array
1102 * @param n the number of elements in the array 969 * @param n the number of elements in the array
1103 * @return the number of elements that could be successfully inserted 970 * @return the number of elements that could be successfully inserted
1104 */ 971 */
1105 cx_attr_nonnull 972 cx_attr_nonnull
1106 static inline size_t cxTreeInsertArray( 973 CX_EXPORT size_t cxTreeInsertArray(CxTree *tree, const void *data, size_t elem_size, size_t n);
1107 CxTree *tree,
1108 const void *data,
1109 size_t elem_size,
1110 size_t n
1111 ) {
1112 if (n == 0) return 0;
1113 if (n == 1) return 0 == cxTreeInsert(tree, data) ? 1 : 0;
1114 CxIterator iter = cxIterator(data, elem_size, n);
1115 return cxTreeInsertIter(tree, cxIteratorRef(iter), n);
1116 }
1117 974
1118 /** 975 /**
1119 * Searches the data in the specified tree. 976 * Searches the data in the specified tree.
1120 * 977 *
1121 * @remark For this function to work, the tree needs a specified @c search_data 978 * @remark For this function to work, the tree needs a specified @c search_data
1124 * 981 *
1125 * @param tree the tree 982 * @param tree the tree
1126 * @param data the data to search for 983 * @param data the data to search for
1127 * @return the first matching node, or @c NULL when the data cannot be found 984 * @return the first matching node, or @c NULL when the data cannot be found
1128 */ 985 */
1129 cx_attr_nonnull 986 cx_attr_nonnull cx_attr_nodiscard
1130 cx_attr_nodiscard 987 CX_EXPORT void *cxTreeFind(CxTree *tree, const void *data);
1131 static inline void *cxTreeFind(
1132 CxTree *tree,
1133 const void *data
1134 ) {
1135 return tree->cl->find(tree, tree->root, data, 0);
1136 }
1137 988
1138 /** 989 /**
1139 * Searches the data in the specified subtree. 990 * Searches the data in the specified subtree.
1140 * 991 *
1141 * When @p max_depth is zero, the depth is not limited. 992 * When @p max_depth is zero, the depth is not limited.
1152 * @param data the data to search for 1003 * @param data the data to search for
1153 * @param subtree_root the node where to start 1004 * @param subtree_root the node where to start
1154 * @param max_depth the maximum search depth 1005 * @param max_depth the maximum search depth
1155 * @return the first matching node, or @c NULL when the data cannot be found 1006 * @return the first matching node, or @c NULL when the data cannot be found
1156 */ 1007 */
1157 cx_attr_nonnull 1008 cx_attr_nonnull cx_attr_nodiscard
1158 cx_attr_nodiscard 1009 CX_EXPORT void *cxTreeFindInSubtree(CxTree *tree, const void *data, void *subtree_root, size_t max_depth);
1159 static inline void *cxTreeFindInSubtree(
1160 CxTree *tree,
1161 const void *data,
1162 void *subtree_root,
1163 size_t max_depth
1164 ) {
1165 return tree->cl->find(tree, subtree_root, data, max_depth);
1166 }
1167 1010
1168 /** 1011 /**
1169 * Determines the size of the specified subtree. 1012 * Determines the size of the specified subtree.
1170 * 1013 *
1171 * @param tree the tree 1014 * @param tree the tree
1172 * @param subtree_root the root node of the subtree 1015 * @param subtree_root the root node of the subtree
1173 * @return the number of nodes in the specified subtree 1016 * @return the number of nodes in the specified subtree
1174 */ 1017 */
1175 cx_attr_nonnull 1018 cx_attr_nonnull cx_attr_nodiscard
1176 cx_attr_nodiscard 1019 CX_EXPORT size_t cxTreeSubtreeSize(CxTree *tree, void *subtree_root);
1177 cx_attr_export
1178 size_t cxTreeSubtreeSize(CxTree *tree, void *subtree_root);
1179 1020
1180 /** 1021 /**
1181 * Determines the depth of the specified subtree. 1022 * Determines the depth of the specified subtree.
1182 * 1023 *
1183 * @param tree the tree 1024 * @param tree the tree
1184 * @param subtree_root the root node of the subtree 1025 * @param subtree_root the root node of the subtree
1185 * @return the tree depth including the @p subtree_root 1026 * @return the tree depth including the @p subtree_root
1186 */ 1027 */
1187 cx_attr_nonnull 1028 cx_attr_nonnull cx_attr_nodiscard
1188 cx_attr_nodiscard 1029 CX_EXPORT size_t cxTreeSubtreeDepth(CxTree *tree, void *subtree_root);
1189 cx_attr_export
1190 size_t cxTreeSubtreeDepth(CxTree *tree, void *subtree_root);
1191 1030
1192 /** 1031 /**
1193 * Determines the size of the entire tree. 1032 * Determines the size of the entire tree.
1194 * 1033 *
1195 * @param tree the tree 1034 * @param tree the tree
1196 * @return the tree size, counting the root as one 1035 * @return the tree size, counting the root as one
1197 */ 1036 */
1198 cx_attr_nonnull 1037 cx_attr_nonnull cx_attr_nodiscard
1199 cx_attr_nodiscard 1038 CX_EXPORT size_t cxTreeSize(CxTree *tree);
1200 static inline size_t cxTreeSize(CxTree *tree) {
1201 return tree->size;
1202 }
1203 1039
1204 /** 1040 /**
1205 * Determines the depth of the entire tree. 1041 * Determines the depth of the entire tree.
1206 * 1042 *
1207 * @param tree the tree 1043 * @param tree the tree
1208 * @return the tree depth, counting the root as one 1044 * @return the tree depth, counting the root as one
1209 */ 1045 */
1210 cx_attr_nonnull 1046 cx_attr_nonnull cx_attr_nodiscard
1211 cx_attr_nodiscard 1047 CX_EXPORT size_t cxTreeDepth(CxTree *tree);
1212 cx_attr_export
1213 size_t cxTreeDepth(CxTree *tree);
1214 1048
1215 /** 1049 /**
1216 * Creates a depth-first iterator for the specified tree starting in @p node. 1050 * Creates a depth-first iterator for the specified tree starting in @p node.
1217 * 1051 *
1218 * If the node is not part of the tree, the behavior is undefined. 1052 * If the node is not part of the tree, the behavior is undefined.
1222 * @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
1223 * leaving the subtree 1057 * leaving the subtree
1224 * @return a tree iterator (depth-first) 1058 * @return a tree iterator (depth-first)
1225 * @see cxTreeVisit() 1059 * @see cxTreeVisit()
1226 */ 1060 */
1227 cx_attr_nonnull 1061 cx_attr_nonnull cx_attr_nodiscard
1228 cx_attr_nodiscard 1062 CX_EXPORT CxTreeIterator cxTreeIterateSubtree(CxTree *tree, void *node, bool visit_on_exit);
1229 static inline CxTreeIterator cxTreeIterateSubtree(
1230 CxTree *tree,
1231 void *node,
1232 bool visit_on_exit
1233 ) {
1234 return cx_tree_iterator(
1235 node, visit_on_exit,
1236 tree->loc_children, tree->loc_next
1237 );
1238 }
1239 1063
1240 /** 1064 /**
1241 * Creates a breadth-first iterator for the specified tree starting in @p node. 1065 * Creates a breadth-first iterator for the specified tree starting in @p node.
1242 * 1066 *
1243 * If the node is not part of the tree, the behavior is undefined. 1067 * If the node is not part of the tree, the behavior is undefined.
1245 * @param tree the tree to iterate 1069 * @param tree the tree to iterate
1246 * @param node the node where to start 1070 * @param node the node where to start
1247 * @return a tree visitor (a.k.a. breadth-first iterator) 1071 * @return a tree visitor (a.k.a. breadth-first iterator)
1248 * @see cxTreeIterate() 1072 * @see cxTreeIterate()
1249 */ 1073 */
1250 cx_attr_nonnull 1074 cx_attr_nonnull cx_attr_nodiscard
1251 cx_attr_nodiscard 1075 CX_EXPORT CxTreeVisitor cxTreeVisitSubtree(CxTree *tree, void *node);
1252 static inline CxTreeVisitor cxTreeVisitSubtree(CxTree *tree, void *node) {
1253 return cx_tree_visitor(
1254 node, tree->loc_children, tree->loc_next
1255 );
1256 }
1257 1076
1258 /** 1077 /**
1259 * Creates a depth-first iterator for the specified tree. 1078 * Creates a depth-first iterator for the specified tree.
1260 * 1079 *
1261 * @param tree the tree to iterate 1080 * @param tree the tree to iterate
1262 * @param visit_on_exit true, if the iterator shall visit a node again when 1081 * @param visit_on_exit true, if the iterator shall visit a node again when
1263 * leaving the subtree 1082 * leaving the subtree
1264 * @return a tree iterator (depth-first) 1083 * @return a tree iterator (depth-first)
1265 * @see cxTreeVisit() 1084 * @see cxTreeVisit()
1266 */ 1085 */
1267 cx_attr_nonnull 1086 cx_attr_nonnull cx_attr_nodiscard
1268 cx_attr_nodiscard 1087 CX_EXPORT CxTreeIterator cxTreeIterate(CxTree *tree, bool visit_on_exit);
1269 static inline CxTreeIterator cxTreeIterate(
1270 CxTree *tree,
1271 bool visit_on_exit
1272 ) {
1273 return cxTreeIterateSubtree(tree, tree->root, visit_on_exit);
1274 }
1275 1088
1276 /** 1089 /**
1277 * Creates a breadth-first iterator for the specified tree. 1090 * Creates a breadth-first iterator for the specified tree.
1278 * 1091 *
1279 * @param tree the tree to iterate 1092 * @param tree the tree to iterate
1280 * @return a tree visitor (a.k.a. breadth-first iterator) 1093 * @return a tree visitor (a.k.a. breadth-first iterator)
1281 * @see cxTreeIterate() 1094 * @see cxTreeIterate()
1282 */ 1095 */
1283 cx_attr_nonnull 1096 cx_attr_nonnull cx_attr_nodiscard
1284 cx_attr_nodiscard 1097 CxTreeVisitor cxTreeVisit(CxTree *tree);
1285 static inline CxTreeVisitor cxTreeVisit(CxTree *tree) {
1286 return cxTreeVisitSubtree(tree, tree->root);
1287 }
1288 1098
1289 /** 1099 /**
1290 * Sets the (new) parent of the specified child. 1100 * Sets the (new) parent of the specified child.
1291 * 1101 *
1292 * If the @p child is not already a member of the tree, this function behaves 1102 * If the @p child is not already a member of the tree, this function behaves
1296 * @param parent the (new) parent of the child 1106 * @param parent the (new) parent of the child
1297 * @param child the node to add 1107 * @param child the node to add
1298 * @see cxTreeAddChildNode() 1108 * @see cxTreeAddChildNode()
1299 */ 1109 */
1300 cx_attr_nonnull 1110 cx_attr_nonnull
1301 cx_attr_export 1111 CX_EXPORT void cxTreeSetParent(CxTree *tree, void *parent, void *child);
1302 void cxTreeSetParent(
1303 CxTree *tree,
1304 void *parent,
1305 void *child
1306 );
1307 1112
1308 /** 1113 /**
1309 * Adds a new node to the tree. 1114 * Adds a new node to the tree.
1310 * 1115 *
1311 * If the @p child is already a member of the tree, the behavior is undefined. 1116 * If the @p child is already a member of the tree, the behavior is undefined.
1319 * @param parent the parent of the node to add 1124 * @param parent the parent of the node to add
1320 * @param child the node to add 1125 * @param child the node to add
1321 * @see cxTreeSetParent() 1126 * @see cxTreeSetParent()
1322 */ 1127 */
1323 cx_attr_nonnull 1128 cx_attr_nonnull
1324 cx_attr_export 1129 CX_EXPORT void cxTreeAddChildNode(CxTree *tree, void *parent, void *child);
1325 void cxTreeAddChildNode(
1326 CxTree *tree,
1327 void *parent,
1328 void *child
1329 );
1330 1130
1331 /** 1131 /**
1332 * Creates a new node and adds it to the tree. 1132 * Creates a new node and adds it to the tree.
1333 * 1133 *
1334 * With this function you can decide where exactly the new node shall be added. 1134 * With this function you can decide where exactly the new node shall be added.
1344 * @param data the data that will be submitted to the create function 1144 * @param data the data that will be submitted to the create function
1345 * @return zero when the new node was created, non-zero on allocation failure 1145 * @return zero when the new node was created, non-zero on allocation failure
1346 * @see cxTreeInsert() 1146 * @see cxTreeInsert()
1347 */ 1147 */
1348 cx_attr_nonnull 1148 cx_attr_nonnull
1349 cx_attr_export 1149 CX_EXPORT int cxTreeAddChild(CxTree *tree, void *parent, const void *data);
1350 int cxTreeAddChild(
1351 CxTree *tree,
1352 void *parent,
1353 const void *data
1354 );
1355 1150
1356 /** 1151 /**
1357 * A function that is invoked when a node needs to be re-linked to a new parent. 1152 * A function that is invoked when a node needs to be re-linked to a new parent.
1358 * 1153 *
1359 * When a node is re-linked, sometimes the contents need to be updated. 1154 * When a node is re-linked, sometimes the contents need to be updated.
1363 * 1158 *
1364 * @param node the affected node 1159 * @param node the affected node
1365 * @param old_parent the old parent of the node 1160 * @param old_parent the old parent of the node
1366 * @param new_parent the new parent of the node 1161 * @param new_parent the new parent of the node
1367 */ 1162 */
1368 cx_attr_nonnull
1369 typedef void (*cx_tree_relink_func)( 1163 typedef void (*cx_tree_relink_func)(
1370 void *node, 1164 void *node,
1371 const void *old_parent, 1165 const void *old_parent,
1372 const void *new_parent 1166 const void *new_parent
1373 ); 1167 );
1385 * @param relink_func optional callback to update the content of each re-linked 1179 * @param relink_func optional callback to update the content of each re-linked
1386 * node 1180 * node
1387 * @return zero on success, non-zero if @p node is the root node of the tree 1181 * @return zero on success, non-zero if @p node is the root node of the tree
1388 */ 1182 */
1389 cx_attr_nonnull_arg(1, 2) 1183 cx_attr_nonnull_arg(1, 2)
1390 cx_attr_export 1184 CX_EXPORT int cxTreeRemoveNode(CxTree *tree, void *node, cx_tree_relink_func relink_func);
1391 int cxTreeRemoveNode(
1392 CxTree *tree,
1393 void *node,
1394 cx_tree_relink_func relink_func
1395 );
1396 1185
1397 /** 1186 /**
1398 * Removes a node and its subtree from the tree. 1187 * Removes a node and its subtree from the tree.
1399 * 1188 *
1400 * If the node is not part of the tree, the behavior is undefined. 1189 * If the node is not part of the tree, the behavior is undefined.
1404 * 1193 *
1405 * @param tree the tree 1194 * @param tree the tree
1406 * @param node the node to remove 1195 * @param node the node to remove
1407 */ 1196 */
1408 cx_attr_nonnull 1197 cx_attr_nonnull
1409 cx_attr_export 1198 CX_EXPORT void cxTreeRemoveSubtree(CxTree *tree, void *node);
1410 void cxTreeRemoveSubtree(CxTree *tree, void *node);
1411 1199
1412 /** 1200 /**
1413 * Destroys a node and re-links its children to its former parent. 1201 * Destroys a node and re-links its children to its former parent.
1414 * 1202 *
1415 * If the node is not part of the tree, the behavior is undefined. 1203 * If the node is not part of the tree, the behavior is undefined.
1426 * @param relink_func optional callback to update the content of each re-linked 1214 * @param relink_func optional callback to update the content of each re-linked
1427 * node 1215 * node
1428 * @return zero on success, non-zero if @p node is the root node of the tree 1216 * @return zero on success, non-zero if @p node is the root node of the tree
1429 */ 1217 */
1430 cx_attr_nonnull_arg(1, 2) 1218 cx_attr_nonnull_arg(1, 2)
1431 cx_attr_export 1219 CX_EXPORT int cxTreeDestroyNode(CxTree *tree, void *node, cx_tree_relink_func relink_func);
1432 int cxTreeDestroyNode(
1433 CxTree *tree,
1434 void *node,
1435 cx_tree_relink_func relink_func
1436 );
1437 1220
1438 #ifdef __cplusplus 1221 #ifdef __cplusplus
1439 } // extern "C" 1222 } // extern "C"
1440 #endif 1223 #endif
1441 1224

mercurial