Lines Matching refs:iter
316 static struct prio_tree_node *prio_tree_left(struct prio_tree_iter *iter,
319 if (prio_tree_left_empty(iter->cur))
322 get_index(iter->root, iter->cur->left, r_index, h_index);
324 if (iter->r_index <= *h_index) {
325 iter->cur = iter->cur->left;
326 iter->mask >>= 1;
327 if (iter->mask) {
328 if (iter->size_level)
329 iter->size_level++;
331 if (iter->size_level) {
332 BUG_ON(!prio_tree_left_empty(iter->cur));
333 BUG_ON(!prio_tree_right_empty(iter->cur));
334 iter->size_level++;
335 iter->mask = ULONG_MAX;
337 iter->size_level = 1;
338 iter->mask = 1UL << (BITS_PER_LONG - 1);
341 return iter->cur;
347 static struct prio_tree_node *prio_tree_right(struct prio_tree_iter *iter,
352 if (prio_tree_right_empty(iter->cur))
355 if (iter->size_level)
356 value = iter->value;
358 value = iter->value | iter->mask;
360 if (iter->h_index < value)
363 get_index(iter->root, iter->cur->right, r_index, h_index);
365 if (iter->r_index <= *h_index) {
366 iter->cur = iter->cur->right;
367 iter->mask >>= 1;
368 iter->value = value;
369 if (iter->mask) {
370 if (iter->size_level)
371 iter->size_level++;
373 if (iter->size_level) {
374 BUG_ON(!prio_tree_left_empty(iter->cur));
375 BUG_ON(!prio_tree_right_empty(iter->cur));
376 iter->size_level++;
377 iter->mask = ULONG_MAX;
379 iter->size_level = 1;
380 iter->mask = 1UL << (BITS_PER_LONG - 1);
383 return iter->cur;
389 static struct prio_tree_node *prio_tree_parent(struct prio_tree_iter *iter)
391 iter->cur = iter->cur->parent;
392 if (iter->mask == ULONG_MAX)
393 iter->mask = 1UL;
394 else if (iter->size_level == 1)
395 iter->mask = 1UL;
397 iter->mask <<= 1;
398 if (iter->size_level)
399 iter->size_level--;
400 if (!iter->size_level && (iter->value & iter->mask))
401 iter->value ^= iter->mask;
402 return iter->cur;
405 static inline int overlap(struct prio_tree_iter *iter,
408 return iter->h_index >= r_index && iter->r_index <= h_index;
418 static struct prio_tree_node *prio_tree_first(struct prio_tree_iter *iter)
423 INIT_PRIO_TREE_ITER(iter);
425 root = iter->root;
431 if (iter->r_index > h_index)
434 iter->mask = 1UL << (root->index_bits - 1);
435 iter->cur = root->prio_tree_node;
438 if (overlap(iter, r_index, h_index))
439 return iter->cur;
441 if (prio_tree_left(iter, &r_index, &h_index))
444 if (prio_tree_right(iter, &r_index, &h_index))
455 * Get the next prio_tree_node that overlaps with the input interval in iter
457 struct prio_tree_node *prio_tree_next(struct prio_tree_iter *iter)
461 if (iter->cur == NULL)
462 return prio_tree_first(iter);
465 while (prio_tree_left(iter, &r_index, &h_index))
466 if (overlap(iter, r_index, h_index))
467 return iter->cur;
469 while (!prio_tree_right(iter, &r_index, &h_index)) {
470 while (!prio_tree_root(iter->cur) &&
471 iter->cur->parent->right == iter->cur)
472 prio_tree_parent(iter);
474 if (prio_tree_root(iter->cur))
477 prio_tree_parent(iter);
480 if (overlap(iter, r_index, h_index))
481 return iter->cur;