lib/interval_tree.c

Source file repositories/reference/linux-study-clean/lib/interval_tree.c

File Facts

System
Linux kernel
Corpus path
lib/interval_tree.c
Extension
.c
Size
4605 bytes
Lines
157
Domain
Kernel Services
Bucket
lib
Inferred role
Kernel Services: exported/initcall integration point
Status
integration implementation candidate

Why This File Exists

Shared kernel service surface used by multiple subsystems, including helpers, cryptography, virtualization support, and async I/O infrastructure.

Dependency Surface

Detected Declarations

Annotated Snippet

if (iter->last_used >= iter->last_index) {
			iter->last_used = iter->last_index;
			iter->nodes[0] = NULL;
			iter->nodes[1] = NULL;
		}
		iter->is_hole = 0;
		return;
	}

	if (!iter->nodes[1]) {
		/* Trailing hole */
		iter->start_hole = iter->nodes[0]->last + 1;
		iter->last_hole = iter->last_index;
		iter->nodes[0] = NULL;
		iter->is_hole = 1;
		return;
	}

	/* must have both nodes[0] and [1], interior hole */
	iter->start_hole = iter->nodes[0]->last + 1;
	iter->last_hole = iter->nodes[1]->start - 1;
	iter->is_hole = 1;
	interval_tree_span_iter_next_gap(iter);
}
EXPORT_SYMBOL_GPL(interval_tree_span_iter_next);

/*
 * Advance the iterator index to a specific position. The returned used/hole is
 * updated to start at new_index. This is faster than calling
 * interval_tree_span_iter_first() as it can avoid full searches in several
 * cases where the iterator is already set.
 */
void interval_tree_span_iter_advance(struct interval_tree_span_iter *iter,
				     struct rb_root_cached *itree,
				     unsigned long new_index)
{
	if (iter->is_hole == -1)
		return;

	iter->first_index = new_index;
	if (new_index > iter->last_index) {
		iter->is_hole = -1;
		return;
	}

	/* Rely on the union aliasing hole/used */
	if (iter->start_hole <= new_index && new_index <= iter->last_hole) {
		iter->start_hole = new_index;
		return;
	}
	if (new_index == iter->last_hole + 1)
		interval_tree_span_iter_next(iter);
	else
		interval_tree_span_iter_first(iter, itree, new_index,
					      iter->last_index);
}
EXPORT_SYMBOL_GPL(interval_tree_span_iter_advance);
#endif

Annotation

Implementation Notes