comparison: src/cx/tree.h
src/cx/tree.h
- changeset 827
- 13b40a598d16
- parent 826
- 21840975d541
- child 828
- 88fa3381206d
equal
deleted
inserted
replaced
| 826:21840975d541 | 827:13b40a598d16 |
|---|---|
| 36 #ifndef UCX_TREE_H | 36 #ifndef UCX_TREE_H |
| 37 #define UCX_TREE_H | 37 #define UCX_TREE_H |
| 38 | 38 |
| 39 #include "common.h" | 39 #include "common.h" |
| 40 | 40 |
| 41 #include "iterator.h" | |
| 42 | |
| 41 #ifdef __cplusplus | 43 #ifdef __cplusplus |
| 42 extern "C" { | 44 extern "C" { |
| 43 #endif | 45 #endif |
| 44 | 46 |
| 47 /** | |
| 48 * When entering a node. | |
| 49 */ | |
| 50 #define CX_TREE_ITERATOR_ENTER 0x1 | |
| 51 /** | |
| 52 * When advancing to the next child. | |
| 53 */ | |
| 54 #define CX_TREE_ITERATOR_NEXT_CHILD 0x2 | |
| 55 /** | |
| 56 * When exiting the node. | |
| 57 */ | |
| 58 #define CX_TREE_ITERATOR_EXIT 0x4 | |
| 59 | |
| 60 /** | |
| 61 * Tree iterator. | |
| 62 * | |
| 63 * This iterator is not position-aware in a strict sense, as it does not assume a particular order of elements in the | |
| 64 * tree. However, the iterator keeps track of the number of nodes it has passed in a counter variable. | |
| 65 * Each node, regardless of the number of passes, is counted only once. | |
| 66 * | |
| 67 * @note Objects that are pointed to by an iterator are mutable through that iterator. However, if the | |
| 68 * iterator is based on a collection and the underlying collection is mutated by other means than this iterator | |
| 69 * (e.g. elements added or removed), the iterator becomes invalid (regardless of what cxIteratorValid() returns) | |
| 70 * and MUST be re-obtained from the collection. | |
| 71 * | |
| 72 * @see CxIterator | |
| 73 */ | |
| 74 typedef struct cx_tree_iterator_s { | |
| 75 /** | |
| 76 * The base properties of this iterator. | |
| 77 */ | |
| 78 struct cx_iterator_base_s base; | |
| 79 /** | |
| 80 * The passes that are requested by this iterator. | |
| 81 * A combination of the flags #CX_TREE_ITERATOR_ENTER, #CX_TREE_ITERATOR_NEXT_CHILD, #CX_TREE_ITERATOR_EXIT. | |
| 82 * | |
| 83 * Changing the value after beginning the iteration is unspecified. | |
| 84 */ | |
| 85 uint8_t requested_passes; | |
| 86 /** | |
| 87 * The current pass. | |
| 88 * | |
| 89 * @see CX_TREE_ITERATOR_ENTER | |
| 90 * @see CX_TREE_ITERATOR_NEXT_CHILD | |
| 91 * @see CX_TREE_ITERATOR_EXIT | |
| 92 */ | |
| 93 uint8_t current_pass; | |
| 94 /** | |
| 95 * Offset in the node struct for the children linked list. | |
| 96 */ | |
| 97 off_t loc_children; | |
| 98 /** | |
| 99 * Offset in the node struct for the next pointer. | |
| 100 */ | |
| 101 off_t loc_next; | |
| 102 /** | |
| 103 * The total number of distinct nodes that have been passed so far. | |
| 104 */ | |
| 105 size_t counter; | |
| 106 /** | |
| 107 * The currently observed node. | |
| 108 * | |
| 109 * This is the same what cxIteratorCurrent() would return. | |
| 110 */ | |
| 111 void *node; | |
| 112 /** | |
| 113 * The node where we came from. | |
| 114 * | |
| 115 * - When entering the root node, this is \c NULL. | |
| 116 * - When entering another node, this is the node's parent. | |
| 117 * - When advancing to the next child, this is the previous child. | |
| 118 */ | |
| 119 void *source; | |
| 120 /** | |
| 121 * Internal stack. | |
| 122 * Will be automatically freed once the iterator becomes invalid. | |
| 123 * | |
| 124 * If you want to discard the iterator before, you need to manually | |
| 125 * call cxTreeIteratorDispose(). | |
| 126 */ | |
| 127 void **stack; | |
| 128 } CxTreeIterator; | |
| 129 | |
| 130 /** | |
| 131 * Releases internal memory of the given tree iterator. | |
| 132 * @param iter the iterator | |
| 133 */ | |
| 134 static inline void cxTreeIteratorDispose(CxTreeIterator *iter) { | |
| 135 free(iter->stack); | |
| 136 } | |
| 45 | 137 |
| 46 /** | 138 /** |
| 47 * Links a node to a (new) parent. | 139 * Links a node to a (new) parent. |
| 48 * | 140 * |
| 49 * If the node has already a parent, it is unlinked, first. | 141 * If the node has already a parent, it is unlinked, first. |
