comparison: src/cx/tree.h
src/cx/tree.h
- changeset 1180
- 4c3a69b9723a
- parent 1109
- 89ec23988b88
equal
deleted
inserted
replaced
| 1179:ca4c6f590a08 | 1180:4c3a69b9723a |
|---|---|
| 261 * @param loc_prev optional offset in the node struct for the prev pointer | 261 * @param loc_prev optional offset in the node struct for the prev pointer |
| 262 * @param loc_next offset in the node struct for the next pointer | 262 * @param loc_next offset in the node struct for the next pointer |
| 263 * @see cx_tree_unlink() | 263 * @see cx_tree_unlink() |
| 264 */ | 264 */ |
| 265 cx_attr_nonnull | 265 cx_attr_nonnull |
| 266 cx_attr_export | |
| 266 void cx_tree_link( | 267 void cx_tree_link( |
| 267 void *parent, | 268 void *parent, |
| 268 void *node, | 269 void *node, |
| 269 ptrdiff_t loc_parent, | 270 ptrdiff_t loc_parent, |
| 270 ptrdiff_t loc_children, | 271 ptrdiff_t loc_children, |
| 286 * @param loc_prev optional offset in the node struct for the prev pointer | 287 * @param loc_prev optional offset in the node struct for the prev pointer |
| 287 * @param loc_next offset in the node struct for the next pointer | 288 * @param loc_next offset in the node struct for the next pointer |
| 288 * @see cx_tree_link() | 289 * @see cx_tree_link() |
| 289 */ | 290 */ |
| 290 cx_attr_nonnull | 291 cx_attr_nonnull |
| 292 cx_attr_export | |
| 291 void cx_tree_unlink( | 293 void cx_tree_unlink( |
| 292 void *node, | 294 void *node, |
| 293 ptrdiff_t loc_parent, | 295 ptrdiff_t loc_parent, |
| 294 ptrdiff_t loc_children, | 296 ptrdiff_t loc_children, |
| 295 ptrdiff_t loc_last_child, | 297 ptrdiff_t loc_last_child, |
| 385 * could contain the node (but doesn't right now), negative if the tree does not | 387 * could contain the node (but doesn't right now), negative if the tree does not |
| 386 * contain any node that might be related to the searched data | 388 * contain any node that might be related to the searched data |
| 387 */ | 389 */ |
| 388 cx_attr_nonnull | 390 cx_attr_nonnull |
| 389 cx_attr_access_w(5) | 391 cx_attr_access_w(5) |
| 392 cx_attr_export | |
| 390 int cx_tree_search_data( | 393 int cx_tree_search_data( |
| 391 const void *root, | 394 const void *root, |
| 392 size_t depth, | 395 size_t depth, |
| 393 const void *data, | 396 const void *data, |
| 394 cx_tree_search_data_func sfunc, | 397 cx_tree_search_data_func sfunc, |
| 421 * could contain the node (but doesn't right now), negative if the tree does not | 424 * could contain the node (but doesn't right now), negative if the tree does not |
| 422 * contain any node that might be related to the searched data | 425 * contain any node that might be related to the searched data |
| 423 */ | 426 */ |
| 424 cx_attr_nonnull | 427 cx_attr_nonnull |
| 425 cx_attr_access_w(5) | 428 cx_attr_access_w(5) |
| 429 cx_attr_export | |
| 426 int cx_tree_search( | 430 int cx_tree_search( |
| 427 const void *root, | 431 const void *root, |
| 428 size_t depth, | 432 size_t depth, |
| 429 const void *node, | 433 const void *node, |
| 430 cx_tree_search_func sfunc, | 434 cx_tree_search_func sfunc, |
| 452 * @param loc_next offset in the node struct for the next pointer | 456 * @param loc_next offset in the node struct for the next pointer |
| 453 * @return the new tree iterator | 457 * @return the new tree iterator |
| 454 * @see cxTreeIteratorDispose() | 458 * @see cxTreeIteratorDispose() |
| 455 */ | 459 */ |
| 456 cx_attr_nodiscard | 460 cx_attr_nodiscard |
| 461 cx_attr_export | |
| 457 CxTreeIterator cx_tree_iterator( | 462 CxTreeIterator cx_tree_iterator( |
| 458 void *root, | 463 void *root, |
| 459 bool visit_on_exit, | 464 bool visit_on_exit, |
| 460 ptrdiff_t loc_children, | 465 ptrdiff_t loc_children, |
| 461 ptrdiff_t loc_next | 466 ptrdiff_t loc_next |
| 478 * @param loc_next offset in the node struct for the next pointer | 483 * @param loc_next offset in the node struct for the next pointer |
| 479 * @return the new tree visitor | 484 * @return the new tree visitor |
| 480 * @see cxTreeVisitorDispose() | 485 * @see cxTreeVisitorDispose() |
| 481 */ | 486 */ |
| 482 cx_attr_nodiscard | 487 cx_attr_nodiscard |
| 488 cx_attr_export | |
| 483 CxTreeVisitor cx_tree_visitor( | 489 CxTreeVisitor cx_tree_visitor( |
| 484 void *root, | 490 void *root, |
| 485 ptrdiff_t loc_children, | 491 ptrdiff_t loc_children, |
| 486 ptrdiff_t loc_next | 492 ptrdiff_t loc_next |
| 487 ); | 493 ); |
| 503 * The local search depth for a new subtree when adding multiple elements. | 509 * The local search depth for a new subtree when adding multiple elements. |
| 504 * The default value is 3. | 510 * The default value is 3. |
| 505 * This variable is used by #cx_tree_add_array() and #cx_tree_add_iter() to | 511 * This variable is used by #cx_tree_add_array() and #cx_tree_add_iter() to |
| 506 * implement optimized insertion of multiple elements into a tree. | 512 * implement optimized insertion of multiple elements into a tree. |
| 507 */ | 513 */ |
| 514 cx_attr_export | |
| 508 extern unsigned int cx_tree_add_look_around_depth; | 515 extern unsigned int cx_tree_add_look_around_depth; |
| 509 | 516 |
| 510 /** | 517 /** |
| 511 * Adds multiple elements efficiently to a tree. | 518 * Adds multiple elements efficiently to a tree. |
| 512 * | 519 * |
| 545 * @return the number of nodes created and added | 552 * @return the number of nodes created and added |
| 546 * @see cx_tree_add() | 553 * @see cx_tree_add() |
| 547 */ | 554 */ |
| 548 cx_attr_nonnull_arg(1, 3, 4, 6, 7) | 555 cx_attr_nonnull_arg(1, 3, 4, 6, 7) |
| 549 cx_attr_access_w(6) | 556 cx_attr_access_w(6) |
| 557 cx_attr_export | |
| 550 size_t cx_tree_add_iter( | 558 size_t cx_tree_add_iter( |
| 551 struct cx_iterator_base_s *iter, | 559 struct cx_iterator_base_s *iter, |
| 552 size_t num, | 560 size_t num, |
| 553 cx_tree_search_func sfunc, | 561 cx_tree_search_func sfunc, |
| 554 cx_tree_node_create_func cfunc, | 562 cx_tree_node_create_func cfunc, |
| 599 * @return the number of array elements successfully processed | 607 * @return the number of array elements successfully processed |
| 600 * @see cx_tree_add() | 608 * @see cx_tree_add() |
| 601 */ | 609 */ |
| 602 cx_attr_nonnull_arg(1, 4, 5, 7, 8) | 610 cx_attr_nonnull_arg(1, 4, 5, 7, 8) |
| 603 cx_attr_access_w(7) | 611 cx_attr_access_w(7) |
| 612 cx_attr_export | |
| 604 size_t cx_tree_add_array( | 613 size_t cx_tree_add_array( |
| 605 const void *src, | 614 const void *src, |
| 606 size_t num, | 615 size_t num, |
| 607 size_t elem_size, | 616 size_t elem_size, |
| 608 cx_tree_search_func sfunc, | 617 cx_tree_search_func sfunc, |
| 662 * @return zero when a new node was created and added to the tree, | 671 * @return zero when a new node was created and added to the tree, |
| 663 * non-zero otherwise | 672 * non-zero otherwise |
| 664 */ | 673 */ |
| 665 cx_attr_nonnull_arg(1, 2, 3, 5, 6) | 674 cx_attr_nonnull_arg(1, 2, 3, 5, 6) |
| 666 cx_attr_access_w(5) | 675 cx_attr_access_w(5) |
| 676 cx_attr_export | |
| 667 int cx_tree_add( | 677 int cx_tree_add( |
| 668 const void *src, | 678 const void *src, |
| 669 cx_tree_search_func sfunc, | 679 cx_tree_search_func sfunc, |
| 670 cx_tree_node_create_func cfunc, | 680 cx_tree_node_create_func cfunc, |
| 671 void *cdata, | 681 void *cdata, |
| 892 * @param tree the tree | 902 * @param tree the tree |
| 893 * @param node the node to remove | 903 * @param node the node to remove |
| 894 * @see cxTreeFree() | 904 * @see cxTreeFree() |
| 895 */ | 905 */ |
| 896 cx_attr_nonnull | 906 cx_attr_nonnull |
| 907 cx_attr_export | |
| 897 void cxTreeDestroySubtree(CxTree *tree, void *node); | 908 void cxTreeDestroySubtree(CxTree *tree, void *node); |
| 898 | 909 |
| 899 | 910 |
| 900 /** | 911 /** |
| 901 * Destroys the tree contents. | 912 * Destroys the tree contents. |
| 930 * that would cause a double-free in most scenarios where the advanced | 941 * that would cause a double-free in most scenarios where the advanced |
| 931 * destructor is already freeing the memory. | 942 * destructor is already freeing the memory. |
| 932 * | 943 * |
| 933 * @param tree the tree to free | 944 * @param tree the tree to free |
| 934 */ | 945 */ |
| 946 cx_attr_export | |
| 935 void cxTreeFree(CxTree *tree); | 947 void cxTreeFree(CxTree *tree); |
| 936 | 948 |
| 937 /** | 949 /** |
| 938 * Creates a new tree structure based on the specified layout. | 950 * Creates a new tree structure based on the specified layout. |
| 939 * | 951 * |
| 960 */ | 972 */ |
| 961 cx_attr_nonnull_arg(2, 3, 4) | 973 cx_attr_nonnull_arg(2, 3, 4) |
| 962 cx_attr_nodiscard | 974 cx_attr_nodiscard |
| 963 cx_attr_malloc | 975 cx_attr_malloc |
| 964 cx_attr_dealloc(cxTreeFree, 1) | 976 cx_attr_dealloc(cxTreeFree, 1) |
| 977 cx_attr_export | |
| 965 CxTree *cxTreeCreate( | 978 CxTree *cxTreeCreate( |
| 966 const CxAllocator *allocator, | 979 const CxAllocator *allocator, |
| 967 cx_tree_node_create_func create_func, | 980 cx_tree_node_create_func create_func, |
| 968 cx_tree_search_func search_func, | 981 cx_tree_search_func search_func, |
| 969 cx_tree_search_data_func search_data_func, | 982 cx_tree_search_data_func search_data_func, |
| 1020 */ | 1033 */ |
| 1021 cx_attr_nonnull_arg(2) | 1034 cx_attr_nonnull_arg(2) |
| 1022 cx_attr_nodiscard | 1035 cx_attr_nodiscard |
| 1023 cx_attr_malloc | 1036 cx_attr_malloc |
| 1024 cx_attr_dealloc(cxTreeFree, 1) | 1037 cx_attr_dealloc(cxTreeFree, 1) |
| 1038 cx_attr_export | |
| 1025 CxTree *cxTreeCreateWrapped( | 1039 CxTree *cxTreeCreateWrapped( |
| 1026 const CxAllocator *allocator, | 1040 const CxAllocator *allocator, |
| 1027 void *root, | 1041 void *root, |
| 1028 ptrdiff_t loc_parent, | 1042 ptrdiff_t loc_parent, |
| 1029 ptrdiff_t loc_children, | 1043 ptrdiff_t loc_children, |
| 1156 * @param subtree_root the root node of the subtree | 1170 * @param subtree_root the root node of the subtree |
| 1157 * @return the number of nodes in the specified subtree | 1171 * @return the number of nodes in the specified subtree |
| 1158 */ | 1172 */ |
| 1159 cx_attr_nonnull | 1173 cx_attr_nonnull |
| 1160 cx_attr_nodiscard | 1174 cx_attr_nodiscard |
| 1175 cx_attr_export | |
| 1161 size_t cxTreeSubtreeSize(CxTree *tree, void *subtree_root); | 1176 size_t cxTreeSubtreeSize(CxTree *tree, void *subtree_root); |
| 1162 | 1177 |
| 1163 /** | 1178 /** |
| 1164 * Determines the depth of the specified subtree. | 1179 * Determines the depth of the specified subtree. |
| 1165 * | 1180 * |
| 1167 * @param subtree_root the root node of the subtree | 1182 * @param subtree_root the root node of the subtree |
| 1168 * @return the tree depth including the @p subtree_root | 1183 * @return the tree depth including the @p subtree_root |
| 1169 */ | 1184 */ |
| 1170 cx_attr_nonnull | 1185 cx_attr_nonnull |
| 1171 cx_attr_nodiscard | 1186 cx_attr_nodiscard |
| 1187 cx_attr_export | |
| 1172 size_t cxTreeSubtreeDepth(CxTree *tree, void *subtree_root); | 1188 size_t cxTreeSubtreeDepth(CxTree *tree, void *subtree_root); |
| 1173 | 1189 |
| 1174 /** | 1190 /** |
| 1175 * Determines the depth of the entire tree. | 1191 * Determines the depth of the entire tree. |
| 1176 * | 1192 * |
| 1177 * @param tree the tree | 1193 * @param tree the tree |
| 1178 * @return the tree depth, counting the root as one | 1194 * @return the tree depth, counting the root as one |
| 1179 */ | 1195 */ |
| 1180 cx_attr_nonnull | 1196 cx_attr_nonnull |
| 1181 cx_attr_nodiscard | 1197 cx_attr_nodiscard |
| 1198 cx_attr_export | |
| 1182 size_t cxTreeDepth(CxTree *tree); | 1199 size_t cxTreeDepth(CxTree *tree); |
| 1183 | 1200 |
| 1184 /** | 1201 /** |
| 1185 * Creates a depth-first iterator for the specified tree starting in @p node. | 1202 * Creates a depth-first iterator for the specified tree starting in @p node. |
| 1186 * | 1203 * |
| 1265 * @param parent the (new) parent of the child | 1282 * @param parent the (new) parent of the child |
| 1266 * @param child the node to add | 1283 * @param child the node to add |
| 1267 * @see cxTreeAddChildNode() | 1284 * @see cxTreeAddChildNode() |
| 1268 */ | 1285 */ |
| 1269 cx_attr_nonnull | 1286 cx_attr_nonnull |
| 1287 cx_attr_export | |
| 1270 void cxTreeSetParent( | 1288 void cxTreeSetParent( |
| 1271 CxTree *tree, | 1289 CxTree *tree, |
| 1272 void *parent, | 1290 void *parent, |
| 1273 void *child | 1291 void *child |
| 1274 ); | 1292 ); |
| 1287 * @param parent the parent of the node to add | 1305 * @param parent the parent of the node to add |
| 1288 * @param child the node to add | 1306 * @param child the node to add |
| 1289 * @see cxTreeSetParent() | 1307 * @see cxTreeSetParent() |
| 1290 */ | 1308 */ |
| 1291 cx_attr_nonnull | 1309 cx_attr_nonnull |
| 1310 cx_attr_export | |
| 1292 void cxTreeAddChildNode( | 1311 void cxTreeAddChildNode( |
| 1293 CxTree *tree, | 1312 CxTree *tree, |
| 1294 void *parent, | 1313 void *parent, |
| 1295 void *child | 1314 void *child |
| 1296 ); | 1315 ); |
| 1311 * @param data the data that will be submitted to the create function | 1330 * @param data the data that will be submitted to the create function |
| 1312 * @return zero when the new node was created, non-zero on allocation failure | 1331 * @return zero when the new node was created, non-zero on allocation failure |
| 1313 * @see cxTreeInsert() | 1332 * @see cxTreeInsert() |
| 1314 */ | 1333 */ |
| 1315 cx_attr_nonnull | 1334 cx_attr_nonnull |
| 1335 cx_attr_export | |
| 1316 int cxTreeAddChild( | 1336 int cxTreeAddChild( |
| 1317 CxTree *tree, | 1337 CxTree *tree, |
| 1318 void *parent, | 1338 void *parent, |
| 1319 const void *data | 1339 const void *data |
| 1320 ); | 1340 ); |
| 1351 * @param relink_func optional callback to update the content of each re-linked | 1371 * @param relink_func optional callback to update the content of each re-linked |
| 1352 * node | 1372 * node |
| 1353 * @return zero on success, non-zero if @p node is the root node of the tree | 1373 * @return zero on success, non-zero if @p node is the root node of the tree |
| 1354 */ | 1374 */ |
| 1355 cx_attr_nonnull_arg(1, 2) | 1375 cx_attr_nonnull_arg(1, 2) |
| 1376 cx_attr_export | |
| 1356 int cxTreeRemoveNode( | 1377 int cxTreeRemoveNode( |
| 1357 CxTree *tree, | 1378 CxTree *tree, |
| 1358 void *node, | 1379 void *node, |
| 1359 cx_tree_relink_func relink_func | 1380 cx_tree_relink_func relink_func |
| 1360 ); | 1381 ); |
| 1369 * | 1390 * |
| 1370 * @param tree the tree | 1391 * @param tree the tree |
| 1371 * @param node the node to remove | 1392 * @param node the node to remove |
| 1372 */ | 1393 */ |
| 1373 cx_attr_nonnull | 1394 cx_attr_nonnull |
| 1395 cx_attr_export | |
| 1374 void cxTreeRemoveSubtree(CxTree *tree, void *node); | 1396 void cxTreeRemoveSubtree(CxTree *tree, void *node); |
| 1375 | 1397 |
| 1376 /** | 1398 /** |
| 1377 * Destroys a node and re-links its children to its former parent. | 1399 * Destroys a node and re-links its children to its former parent. |
| 1378 * | 1400 * |
| 1390 * @param relink_func optional callback to update the content of each re-linked | 1412 * @param relink_func optional callback to update the content of each re-linked |
| 1391 * node | 1413 * node |
| 1392 * @return zero on success, non-zero if @p node is the root node of the tree | 1414 * @return zero on success, non-zero if @p node is the root node of the tree |
| 1393 */ | 1415 */ |
| 1394 cx_attr_nonnull_arg(1, 2) | 1416 cx_attr_nonnull_arg(1, 2) |
| 1417 cx_attr_export | |
| 1395 int cxTreeDestroyNode( | 1418 int cxTreeDestroyNode( |
| 1396 CxTree *tree, | 1419 CxTree *tree, |
| 1397 void *node, | 1420 void *node, |
| 1398 cx_tree_relink_func relink_func | 1421 cx_tree_relink_func relink_func |
| 1399 ); | 1422 ); |
