comparison: src/tree.c
src/tree.c
- changeset 830
- c4dae6fe6d5b
- parent 826
- 21840975d541
- child 833
- 5c926801f052
equal
deleted
inserted
replaced
| 829:7d4e31d295af | 830:c4dae6fe6d5b |
|---|---|
| 167 // free the working queue and return | 167 // free the working queue and return |
| 168 #undef workq_add | 168 #undef workq_add |
| 169 free(work); | 169 free(work); |
| 170 return ret; | 170 return ret; |
| 171 } | 171 } |
| 172 | |
| 173 static bool cx_tree_iter_valid(void const *it) { | |
| 174 struct cx_tree_iterator_s const *iter = it; | |
| 175 return iter->node != NULL; | |
| 176 } | |
| 177 | |
| 178 static void *cx_tree_iter_current(void const *it) { | |
| 179 struct cx_tree_iterator_s const *iter = it; | |
| 180 return iter->node; | |
| 181 } | |
| 182 | |
| 183 static void cx_tree_iter_stack_add( | |
| 184 struct cx_tree_iterator_s *iter, | |
| 185 void *node | |
| 186 ) { | |
| 187 cx_array_add(&iter->stack, &iter->depth, &iter->stack_capacity, | |
| 188 sizeof(void*), &node, cx_array_default_reallocator); | |
| 189 } | |
| 190 | |
| 191 static void cx_tree_iter_next(void *it) { | |
| 192 struct cx_tree_iterator_s *iter = it; | |
| 193 // TODO: support mutating iterator | |
| 194 | |
| 195 // TODO: implement | |
| 196 } | |
| 197 | |
| 198 | |
| 199 CxTreeIterator cx_tree_iterator( | |
| 200 void *root, | |
| 201 int passes, | |
| 202 ptrdiff_t loc_children, | |
| 203 ptrdiff_t loc_next | |
| 204 ) { | |
| 205 CxTreeIterator iter; | |
| 206 iter.loc_children = loc_children; | |
| 207 iter.loc_next = loc_next; | |
| 208 iter.requested_passes = passes; | |
| 209 | |
| 210 // invalidate iterator immediately when passes is invalid | |
| 211 if ((passes & (CX_TREE_ITERATOR_ENTER | | |
| 212 CX_TREE_ITERATOR_NEXT_CHILD | | |
| 213 CX_TREE_ITERATOR_EXIT)) == 0) { | |
| 214 iter.stack = NULL; | |
| 215 iter.node = NULL; | |
| 216 return iter; | |
| 217 } | |
| 218 | |
| 219 // allocate stack | |
| 220 iter.stack_capacity = 16; | |
| 221 iter.stack = malloc(sizeof(void *) * 16); | |
| 222 iter.depth = 0; | |
| 223 | |
| 224 // determine start | |
| 225 if ((passes & CX_TREE_ITERATOR_ENTER) == 0) { | |
| 226 // we have to skip the first "entering" passes | |
| 227 void *s = NULL; | |
| 228 void *n = root; | |
| 229 iter.counter = 0; | |
| 230 do { | |
| 231 iter.counter++; | |
| 232 iter.source = s; | |
| 233 iter.node = n; | |
| 234 cx_tree_iter_stack_add(&iter, n); | |
| 235 s = n; | |
| 236 n = tree_children(n); | |
| 237 } while (n != NULL); | |
| 238 // found a leaf node s (might be root itself if it has no children) | |
| 239 | |
| 240 // check if there is a sibling | |
| 241 n = tree_next(s); | |
| 242 | |
| 243 if (n == NULL) { | |
| 244 // no sibling found, exit back to parent node | |
| 245 // TODO: implement | |
| 246 } else { | |
| 247 // there is a sibling | |
| 248 if ((passes & CX_TREE_ITERATOR_EXIT) == 0) { | |
| 249 // no exit requested, conclude that only next_child is requested | |
| 250 iter.source = s; | |
| 251 iter.node = n; | |
| 252 iter.counter++; | |
| 253 iter.current_pass = CX_TREE_ITERATOR_NEXT_CHILD; | |
| 254 } else { | |
| 255 // exit requested, so we have found our first pass | |
| 256 // iter.node and iter.source are still correct | |
| 257 iter.current_pass = CX_TREE_ITERATOR_EXIT; | |
| 258 } | |
| 259 } | |
| 260 } else { | |
| 261 // enter passes are requested, we can start by entering the root node | |
| 262 iter.source = NULL; | |
| 263 iter.node = root; | |
| 264 iter.current_pass = CX_TREE_ITERATOR_ENTER; | |
| 265 iter.counter = 1; | |
| 266 iter.depth = 1; | |
| 267 iter.stack[0] = root; | |
| 268 } | |
| 269 | |
| 270 // assign base iterator functions | |
| 271 iter.base.mutating = false; | |
| 272 iter.base.remove = false; | |
| 273 iter.base.current_impl = NULL; | |
| 274 iter.base.valid = cx_tree_iter_valid; | |
| 275 iter.base.next = cx_tree_iter_next; | |
| 276 iter.base.current = cx_tree_iter_current; | |
| 277 | |
| 278 return iter; | |
| 279 } |
