297 static struct prio_tree_node *prio_tree_left(struct prio_tree_iter *iter,  in prio_tree_left()  argument
300 	if (prio_tree_left_empty(iter->cur))  in prio_tree_left()
303 	get_index(iter->cur->left, r_index, h_index);  in prio_tree_left()
305 	if (iter->r_index <= *h_index) {  in prio_tree_left()
306 		iter->cur = iter->cur->left;  in prio_tree_left()
307 		iter->mask >>= 1;  in prio_tree_left()
308 		if (iter->mask) {  in prio_tree_left()
309 			if (iter->size_level)  in prio_tree_left()
310 				iter->size_level++;  in prio_tree_left()
312 			if (iter->size_level) {  in prio_tree_left()
313 				assert(prio_tree_left_empty(iter->cur));  in prio_tree_left()
314 				assert(prio_tree_right_empty(iter->cur));  in prio_tree_left()
315 				iter->size_level++;  in prio_tree_left()
316 				iter->mask = ULONG_MAX;  in prio_tree_left()
318 				iter->size_level = 1;  in prio_tree_left()
319 				iter->mask = 1UL << (BITS_PER_LONG - 1);  in prio_tree_left()
322 		return iter->cur;  in prio_tree_left()
328 static struct prio_tree_node *prio_tree_right(struct prio_tree_iter *iter,  in prio_tree_right()  argument
333 	if (prio_tree_right_empty(iter->cur))  in prio_tree_right()
336 	if (iter->size_level)  in prio_tree_right()
337 		value = iter->value;  in prio_tree_right()
339 		value = iter->value | iter->mask;  in prio_tree_right()
341 	if (iter->h_index < value)  in prio_tree_right()
344 	get_index(iter->cur->right, r_index, h_index);  in prio_tree_right()
346 	if (iter->r_index <= *h_index) {  in prio_tree_right()
347 		iter->cur = iter->cur->right;  in prio_tree_right()
348 		iter->mask >>= 1;  in prio_tree_right()
349 		iter->value = value;  in prio_tree_right()
350 		if (iter->mask) {  in prio_tree_right()
351 			if (iter->size_level)  in prio_tree_right()
352 				iter->size_level++;  in prio_tree_right()
354 			if (iter->size_level) {  in prio_tree_right()
355 				assert(prio_tree_left_empty(iter->cur));  in prio_tree_right()
356 				assert(prio_tree_right_empty(iter->cur));  in prio_tree_right()
357 				iter->size_level++;  in prio_tree_right()
358 				iter->mask = ULONG_MAX;  in prio_tree_right()
360 				iter->size_level = 1;  in prio_tree_right()
361 				iter->mask = 1UL << (BITS_PER_LONG - 1);  in prio_tree_right()
364 		return iter->cur;  in prio_tree_right()
370 static struct prio_tree_node *prio_tree_parent(struct prio_tree_iter *iter)  in prio_tree_parent()  argument
372 	iter->cur = iter->cur->parent;  in prio_tree_parent()
373 	if (iter->mask == ULONG_MAX)  in prio_tree_parent()
374 		iter->mask = 1UL;  in prio_tree_parent()
375 	else if (iter->size_level == 1)  in prio_tree_parent()
376 		iter->mask = 1UL;  in prio_tree_parent()
378 		iter->mask <<= 1;  in prio_tree_parent()
379 	if (iter->size_level)  in prio_tree_parent()
380 		iter->size_level--;  in prio_tree_parent()
381 	if (!iter->size_level && (iter->value & iter->mask))  in prio_tree_parent()
382 		iter->value ^= iter->mask;  in prio_tree_parent()
383 	return iter->cur;  in prio_tree_parent()
386 static inline int overlap(struct prio_tree_iter *iter,  in overlap()  argument
389 	return iter->h_index >= r_index && iter->r_index <= h_index;  in overlap()
399 static struct prio_tree_node *prio_tree_first(struct prio_tree_iter *iter)  in prio_tree_first()  argument
404 	INIT_PRIO_TREE_ITER(iter);  in prio_tree_first()
406 	root = iter->root;  in prio_tree_first()
412 	if (iter->r_index > h_index)  in prio_tree_first()
415 	iter->mask = 1UL << (root->index_bits - 1);  in prio_tree_first()
416 	iter->cur = root->prio_tree_node;  in prio_tree_first()
419 		if (overlap(iter, r_index, h_index))  in prio_tree_first()
420 			return iter->cur;  in prio_tree_first()
422 		if (prio_tree_left(iter, &r_index, &h_index))  in prio_tree_first()
425 		if (prio_tree_right(iter, &r_index, &h_index))  in prio_tree_first()
438 struct prio_tree_node *prio_tree_next(struct prio_tree_iter *iter)  in prio_tree_next()  argument
442 	if (iter->cur == NULL)  in prio_tree_next()
443 		return prio_tree_first(iter);  in prio_tree_next()
446 	while (prio_tree_left(iter, &r_index, &h_index))  in prio_tree_next()
447 		if (overlap(iter, r_index, h_index))  in prio_tree_next()
448 			return iter->cur;  in prio_tree_next()
450 	while (!prio_tree_right(iter, &r_index, &h_index)) {  in prio_tree_next()
451 	    	while (!prio_tree_root(iter->cur) &&  in prio_tree_next()
452 				iter->cur->parent->right == iter->cur)  in prio_tree_next()
453 			prio_tree_parent(iter);  in prio_tree_next()
455 		if (prio_tree_root(iter->cur))  in prio_tree_next()
458 		prio_tree_parent(iter);  in prio_tree_next()
461 	if (overlap(iter, r_index, h_index))  in prio_tree_next()
462 		return iter->cur;  in prio_tree_next()