Cross Reference: /external/fio/lib/prio

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