tools/testing/selftests/bpf/libarena/src/rbtree.bpf.c

Source file repositories/reference/linux-study-clean/tools/testing/selftests/bpf/libarena/src/rbtree.bpf.c

File Facts

System
Linux kernel
Corpus path
tools/testing/selftests/bpf/libarena/src/rbtree.bpf.c
Extension
.c
Size
22879 bytes
Lines
1048
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

if (rbtree->root) {
			arena_stderr("WARNING: Destroying RB_NOALLOC tree with > 0 nodes");
			return -EBUSY;
		}

		goto out;
	}

	while (rbtree->root && can_loop) {
		ret = rb_remove(rbtree, rbtree->root->key);
		if (ret)
			break;
	}

out:
	arena_free(rbtree);
	return ret;
}

static inline int rbnode_dir(struct rbnode __arena *node)
{
	/* Arbitrarily choose a direction for the root. */
	if (unlikely(!node->parent))
		return 0;

	return (node->parent->left == node) ? 0 : 1;
}

/*
 * The __noinline is to prevent inlining from bloating the add
 * remove calls, in turn causing register splits and increasing
 * stack usage above what is permitted.
 */
__noinline
int rbnode_rotate(struct rbtree __arena *rbtree,
		  struct rbnode __arena *node, int dir)
{
	struct rbnode __arena *tmp, *parent;
	int parentdir;

	parent = node->parent;
	if (parent)
		parentdir = rbnode_dir(node);

	/* If we're doing a root change, are we the root? */
	if (unlikely(!parent && rbtree->root != node))
		return -EINVAL;

	/*
	 * Does the node we're turning into the root into exist?
	 * Note that the new root is on the opposite side of the
	 * rotation's direction.
	 */
	tmp = node->child[1 - dir];
	if (unlikely(!tmp))
		return -EINVAL;

	/* Steal the closest child of the new root. */
	node->child[1 - dir] = tmp->child[dir];
	if (node->child[1 - dir])
		node->child[1 - dir]->parent = node;

	/* Put the node below the new root.*/
	tmp->child[dir] = node;
	node->parent = tmp;

	tmp->parent = parent;
	if (parent)
		parent->child[parentdir] = tmp;
	else
		rbtree->root = tmp;

	return 0;
}

static
struct rbnode __arena *rbnode_find(struct rbnode __arena *subtree, u64 key)
{
	struct rbnode __arena *node = subtree;
	int dir;

	if (!subtree)
		return NULL;

	while (can_loop) {
		if (node->key == key)
			break;

		dir = (key < node->key) ? 0 : 1;

Annotation

Implementation Notes