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 |