tools/testing/selftests/bpf/libarena/include/libarena/rbtree.h

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

File Facts

System
Linux kernel
Corpus path
tools/testing/selftests/bpf/libarena/include/libarena/rbtree.h
Extension
.h
Size
2122 bytes
Lines
84
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 rbnode {
	struct rbnode __arena *parent;
	union {
		struct {
			struct rbnode __arena *left;
			struct rbnode __arena *right;
		};

		struct rbnode __arena *child[2];
	};
	uint64_t key;
	/* Used as a linked list or to store KV pairs. */
	union {
		struct rbnode __arena *next;
		uint64_t value;
	};
	bool is_red;
};

/*
 * Does the rbtree allocate its own nodes, or do they get
 * allocated by the caller?
 */
enum rbtree_alloc {
	RB_ALLOC,
	RB_NOALLOC,
};

/*
 * Specify the behavior of rbtree insertions when the key is
 * already present in the tree.
 *
 * RB_DEFAULT: Default behavior, reject the new insert.
 *
 * RB_UPDATE: Update the existing value in the rbtree.
 * This updates the node itself, not just the value in
 * the existing node.
 *
 * RB_DUPLICATE: Allow nodes with identical keys in the rbtree.
 * Finding/popping/removing a key acts on any of the nodes
 * with the appropriate key - there is no ordering by time
 * of insertion.
 */
enum rbtree_insert_mode {
	RB_DEFAULT,
	RB_UPDATE,
	RB_DUPLICATE,
};

struct rbtree {
	struct rbnode __arena *root;
	enum rbtree_alloc alloc;
	enum rbtree_insert_mode insert;
};

#ifdef __BPF__
struct rbtree __arena *rb_create(enum rbtree_alloc alloc, enum rbtree_insert_mode insert);

int rb_destroy(struct rbtree __arena *rbtree);
int rb_insert(struct rbtree __arena *rbtree, u64 key, u64 value);
int rb_remove(struct rbtree __arena *rbtree, u64 key);
int rb_find(struct rbtree __arena *rbtree, u64 key, u64 *value);
int rb_print(struct rbtree __arena *rbtree);
int rb_least(struct rbtree __arena *rbtree, u64 *key, u64 *value);
int rb_pop(struct rbtree __arena *rbtree, u64 *key, u64 *value);

int rb_insert_node(struct rbtree __arena *rbtree, struct rbnode __arena *node);
int rb_remove_node(struct rbtree __arena *rbtree, struct rbnode __arena *node);

struct rbnode __arena *rb_node_alloc(u64 key, u64 value);
void rb_node_free(struct rbnode __arena *rbnode);

int rb_integrity_check(struct rbtree __arena *rbtree);

#endif /* __BPF__ */

Annotation

Implementation Notes