comparison: src/cx/tree.h
src/cx/tree.h
- changeset 859
- 6367456bf2d9
- parent 854
- fe0d69d72bcd
- child 860
- 558ed4c6abd0
- child 862
- 387414a7afd8
equal
deleted
inserted
replaced
| 858:d9ad7904c4c2 | 859:6367456bf2d9 |
|---|---|
| 45 #endif | 45 #endif |
| 46 | 46 |
| 47 /** | 47 /** |
| 48 * A depth-first tree iterator. | 48 * A depth-first tree iterator. |
| 49 * | 49 * |
| 50 * This iterator is not position-aware in a strict sense, as it does not assume a particular order of elements in the | 50 * This iterator is not position-aware in a strict sense, as it does not assume |
| 51 * tree. However, the iterator keeps track of the number of nodes it has passed in a counter variable. | 51 * a particular order of elements in the tree. However, the iterator keeps track |
| 52 * of the number of nodes it has passed in a counter variable. | |
| 52 * Each node, regardless of the number of passes, is counted only once. | 53 * Each node, regardless of the number of passes, is counted only once. |
| 53 * | 54 * |
| 54 * @note Objects that are pointed to by an iterator are mutable through that iterator. However, if the | 55 * @note Objects that are pointed to by an iterator are mutable through that |
| 55 * underlying data structure is mutated by other means than this iterator (e.g. elements added or removed), | 56 * iterator. However, if the |
| 56 * the iterator becomes invalid (regardless of what cxIteratorValid() returns). | 57 * underlying data structure is mutated by other means than this iterator (e.g. |
| 58 * elements added or removed), the iterator becomes invalid (regardless of what | |
| 59 * cxIteratorValid() returns). | |
| 57 * | 60 * |
| 58 * @see CxIterator | 61 * @see CxIterator |
| 59 */ | 62 */ |
| 60 typedef struct cx_tree_iterator_s { | 63 typedef struct cx_tree_iterator_s { |
| 61 /** | 64 /** |
| 141 }; | 144 }; |
| 142 | 145 |
| 143 /** | 146 /** |
| 144 * A breadth-first tree iterator. | 147 * A breadth-first tree iterator. |
| 145 * | 148 * |
| 146 * This iterator needs to maintain a visitor queue that will be automatically freed once the iterator becomes invalid. | 149 * This iterator needs to maintain a visitor queue that will be automatically |
| 147 * If you want to discard the iterator before, you MUST manually call cxTreeVisitorDispose(). | 150 * freed once the iterator becomes invalid. |
| 148 * | 151 * If you want to discard the iterator before, you MUST manually call |
| 149 * This iterator is not position-aware in a strict sense, as it does not assume a particular order of elements in the | 152 * cxTreeVisitorDispose(). |
| 150 * tree. However, the iterator keeps track of the number of nodes it has passed in a counter variable. | 153 * |
| 154 * This iterator is not position-aware in a strict sense, as it does not assume | |
| 155 * a particular order of elements in the tree. However, the iterator keeps track | |
| 156 * of the number of nodes it has passed in a counter variable. | |
| 151 * Each node, regardless of the number of passes, is counted only once. | 157 * Each node, regardless of the number of passes, is counted only once. |
| 152 * | 158 * |
| 153 * @note Objects that are pointed to by an iterator are mutable through that iterator. However, if the | 159 * @note Objects that are pointed to by an iterator are mutable through that |
| 154 * underlying data structure is mutated by other means than this iterator (e.g. elements added or removed), | 160 * iterator. However, if the |
| 155 * the iterator becomes invalid (regardless of what cxIteratorValid() returns). | 161 * underlying data structure is mutated by other means than this iterator (e.g. |
| 162 * elements added or removed), the iterator becomes invalid (regardless of what | |
| 163 * cxIteratorValid() returns). | |
| 156 * | 164 * |
| 157 * @see CxIterator | 165 * @see CxIterator |
| 158 */ | 166 */ |
| 159 typedef struct cx_tree_visitor_s { | 167 typedef struct cx_tree_visitor_s { |
| 160 /** | 168 /** |
| 296 * For example if a tree stores file path information, a node that is | 304 * For example if a tree stores file path information, a node that is |
| 297 * describing a parent directory of a filename that is searched, shall | 305 * describing a parent directory of a filename that is searched, shall |
| 298 * return a positive number to indicate that a child node might contain the | 306 * return a positive number to indicate that a child node might contain the |
| 299 * searched item. On the other hand, if the node denotes a path that is not a | 307 * searched item. On the other hand, if the node denotes a path that is not a |
| 300 * prefix of the searched filename, the function would return -1 to indicate | 308 * prefix of the searched filename, the function would return -1 to indicate |
| 301 * that * the search does not need to be continued in that branch. | 309 * that the search does not need to be continued in that branch. |
| 302 * | 310 * |
| 303 * @param node the node that is currently investigated | 311 * @param node the node that is currently investigated |
| 304 * @param data the data that is searched for | 312 * @param data the data that is searched for |
| 305 * | 313 * |
| 306 * @return 0 if the node contains the data, | 314 * @return 0 if the node contains the data, |
| 307 * positive if one of the children might contain the data, | 315 * positive if one of the children might contain the data, |
| 308 * negative if neither the node, nor the children contains the data | 316 * negative if neither the node, nor the children contains the data |
| 309 */ | 317 */ |
| 310 typedef int (*cx_tree_search_func)(void const *node, void const* data); | 318 typedef int (*cx_tree_search_func)(void const *node, void const *data); |
| 311 | 319 |
| 312 | 320 |
| 313 /** | 321 /** |
| 314 * Searches for data in a tree. | 322 * Searches for data in a tree. |
| 315 * | 323 * |
| 344 ); | 352 ); |
| 345 | 353 |
| 346 /** | 354 /** |
| 347 * Creates a depth-first iterator for a tree with the specified root node. | 355 * Creates a depth-first iterator for a tree with the specified root node. |
| 348 * | 356 * |
| 349 * @note A tree iterator needs to maintain a stack of visited nodes, which is allocated using stdlib malloc(). | 357 * @note A tree iterator needs to maintain a stack of visited nodes, which is |
| 350 * When the iterator becomes invalid, this memory is automatically released. However, if you wish to cancel the | 358 * allocated using stdlib malloc(). |
| 351 * iteration before the iterator becomes invalid by itself, you MUST call cxTreeIteratorDispose() manually to release | 359 * When the iterator becomes invalid, this memory is automatically released. |
| 360 * However, if you wish to cancel the iteration before the iterator becomes | |
| 361 * invalid by itself, you MUST call cxTreeIteratorDispose() manually to release | |
| 352 * the memory. | 362 * the memory. |
| 353 * | 363 * |
| 354 * @remark The returned iterator does not support cxIteratorFlagRemoval(). | 364 * @remark The returned iterator does not support cxIteratorFlagRemoval(). |
| 355 * | 365 * |
| 356 * @param root the root node | 366 * @param root the root node |
| 357 * @param visit_on_exit set to true, when the iterator shall visit a node again after processing all children | 367 * @param visit_on_exit set to true, when the iterator shall visit a node again |
| 368 * after processing all children | |
| 358 * @param loc_children offset in the node struct for the children linked list | 369 * @param loc_children offset in the node struct for the children linked list |
| 359 * @param loc_next offset in the node struct for the next pointer | 370 * @param loc_next offset in the node struct for the next pointer |
| 360 * @return the new tree iterator | 371 * @return the new tree iterator |
| 361 * @see cxTreeIteratorDispose() | 372 * @see cxTreeIteratorDispose() |
| 362 */ | 373 */ |
| 369 ); | 380 ); |
| 370 | 381 |
| 371 /** | 382 /** |
| 372 * Creates a breadth-first iterator for a tree with the specified root node. | 383 * Creates a breadth-first iterator for a tree with the specified root node. |
| 373 * | 384 * |
| 374 * @note A tree visitor needs to maintain a queue of to be visited nodes, which is allocated using stdlib malloc(). | 385 * @note A tree visitor needs to maintain a queue of to be visited nodes, which |
| 375 * When the visitor becomes invalid, this memory is automatically released. However, if you wish to cancel the | 386 * is allocated using stdlib malloc(). |
| 376 * iteration before the visitor becomes invalid by itself, you MUST call cxTreeVisitorDispose() manually to release | 387 * When the visitor becomes invalid, this memory is automatically released. |
| 388 * However, if you wish to cancel the iteration before the visitor becomes | |
| 389 * invalid by itself, you MUST call cxTreeVisitorDispose() manually to release | |
| 377 * the memory. | 390 * the memory. |
| 378 * | 391 * |
| 379 * @remark The returned iterator does not support cxIteratorFlagRemoval(). | 392 * @remark The returned iterator does not support cxIteratorFlagRemoval(). |
| 380 * | 393 * |
| 381 * @param root the root node | 394 * @param root the root node |
