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 */ |
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. |
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. |
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. |