tools/testing/selftests/kvm/lib/sparsebit.c

Source file repositories/reference/linux-study-clean/tools/testing/selftests/kvm/lib/sparsebit.c

File Facts

System
Linux kernel
Corpus path
tools/testing/selftests/kvm/lib/sparsebit.c
Extension
.c
Size
59049 bytes
Lines
2085
Domain
Support Tooling And Documentation
Bucket
tools
Inferred role
Support Tooling And Documentation: implementation source
Status
source implementation candidate

Why This File Exists

Repository support layer: documentation, build tooling, samples, user-space helper tools, generated initramfs support, licenses, and validation utilities.

Dependency Surface

Detected Declarations

Annotated Snippet

struct node {
	struct node *parent;
	struct node *left;
	struct node *right;
	sparsebit_idx_t idx; /* index of least-significant bit in mask */
	sparsebit_num_t num_after; /* num contiguously set after mask */
	mask_t mask;
};

struct sparsebit {
	/*
	 * Points to root node of the binary search
	 * tree.  Equal to NULL when no bits are set in
	 * the entire sparsebit array.
	 */
	struct node *root;

	/*
	 * A redundant count of the total number of bits set.  Used for
	 * diagnostic purposes and to change the time complexity of
	 * sparsebit_num_set() from O(n) to O(1).
	 * Note: Due to overflow, a value of 0 means none or all set.
	 */
	sparsebit_num_t num_set;
};

/* Returns the number of set bits described by the settings
 * of the node pointed to by nodep.
 */
static sparsebit_num_t node_num_set(struct node *nodep)
{
	return nodep->num_after + __builtin_popcount(nodep->mask);
}

/* Returns a pointer to the node that describes the
 * lowest bit index.
 */
static struct node *node_first(const struct sparsebit *s)
{
	struct node *nodep;

	for (nodep = s->root; nodep && nodep->left; nodep = nodep->left)
		;

	return nodep;
}

/* Returns a pointer to the node that describes the
 * lowest bit index > the index of the node pointed to by np.
 * Returns NULL if no node with a higher index exists.
 */
static struct node *node_next(const struct sparsebit *s, struct node *np)
{
	struct node *nodep = np;

	/*
	 * If current node has a right child, next node is the left-most
	 * of the right child.
	 */
	if (nodep->right) {
		for (nodep = nodep->right; nodep->left; nodep = nodep->left)
			;
		return nodep;
	}

	/*
	 * No right child.  Go up until node is left child of a parent.
	 * That parent is then the next node.
	 */
	while (nodep->parent && nodep == nodep->parent->right)
		nodep = nodep->parent;

	return nodep->parent;
}

/* Searches for and returns a pointer to the node that describes the
 * highest index < the index of the node pointed to by np.
 * Returns NULL if no node with a lower index exists.
 */
static struct node *node_prev(const struct sparsebit *s, struct node *np)
{
	struct node *nodep = np;

	/*
	 * If current node has a left child, next node is the right-most
	 * of the left child.
	 */
	if (nodep->left) {
		for (nodep = nodep->left; nodep->right; nodep = nodep->right)
			;

Annotation

Implementation Notes