Overview
The search time complexity of a linked list is O(N). As the number of members managed by the linked list increases, the algorithmic cost of searching increases. To address this, Zephyr provides an implementation of a red-black tree, where the time complexity for search and delete operations is O(log2(N)) for a tree of size N. In Zephyr, the kernel scheduling algorithm and p4wq utilize the red-black tree.
The implementation code for the red-black tree in Zephyr is:
-
zephyr/include/zephyr/sys/p4wq.h -
zephyr/lib/os/rb.c
Zephyr implements a traditional red-black tree, and the algorithm is not the focus of this article. Here are some key points of Zephyr’s implementation:
-
The path length from the root of the tree to any leaf does not exceed twice the path length of any other leaf. -
A red node cannot have a red child. -
Zephyr’s rotations are not just simple exchanges of node internal data pointers; they also involve more complex edge condition handling. -
Zephyr’s tree nodes only contain two pointers, resulting in space overhead similar to a doubly linked list (a typical implementation would have three pointers, with one pointing to the parent node).
Structures
Tree
Manage the red-black tree using struct rbtree. Only lessthan_fn is set externally for the red-black tree; the others are for internal management:
struct rbtree {
/** Root node of the tree */
struct rbnode *root;
/** Comparison function for nodes in the tree */
rb_lessthan_t lessthan_fn;
/** @cond INTERNAL_HIDDEN */
int max_depth;
# ifdef CONFIG_MISRA_SANE
struct rbnode *iter_stack [Z_MAX_RBTREE_DEPTH];
unsigned char iter_left [Z_MAX_RBTREE_DEPTH];
# endif
/** @endcond */
};
Node
Manage tree nodes using struct rbnode
struct rbnode {
/** @cond INTERNAL_HIDDEN */
struct rbnode *children [2];
/** @endcond */
};
Similar to Zephyr’s linked list, the nodes in rbtree exist in user-managed memory structures, so user nodes must be defined before using the tree.
struct user_rbnode {
struct rbnode rbnode;
sys_dlist_t dlnode;
uint32_t priority;
void *data;
};
Note: Unlike users being able to traverse a linked list directly through linked list nodes, the data in rbnode is completely opaque, and users cannot extract the binary tree topology for “manual” traversal.
Initialization
Manage the red-black tree using struct rbtree. There is no specific API for initializing this structure; its members should be assigned a value of 0. When assigning, it is necessary to provide a comparison function to assist the red-black tree in sorting:
typedef bool ( *rb_lessthan_t ) ( struct rbnode *a, struct rbnode *b );
When the comparison function considers node a to be “less than” node b, this function should return the boolean value True. However, note that nodes in the tree must not be “equal”; they must have a fixed order for the red-black tree algorithm to function correctly.
static bool rb_lessthan ( struct rbnode *a, struct rbnode *b )
{
struct user_rbnode *au = CONTAINER_OF ( a, struct user_rbnode, rbnode );
struct user_rbnode *bu = CONTAINER_OF ( b, struct user_rbnode, rbnode );
if ( au->priority != bu->priority ) {
return au->priority > bu->priority;
}
return ( uintptr_t ) a <( uintptr_t ) b;
}
A typical initialization process:
struct rbtree rb;
memset ( &rb, 0, sizeof ( struct rbtree ));
rb.lessthan_fn = rb_lessthan;
Operations
Use rb_insert ( ) to insert nodes and rb_remove ( ) to delete nodes. Access the “first” and “last” nodes in the tree (in the order defined by the comparison function) using rb_get_min ( ) and rb_get_max ( ). Additionally, rb_contains ( ) is provided to determine if a node belongs to a specified tree. If it does, it returns True. Example code is as follows:
struct user_rbnode n1 = {.priority = 1};
struct user_rbnode n2 = {.priority = 2};
struct user_rbnode n3 = {.priority = 3};
struct user_rbnode n4 = {.priority = 4};
struct user_rbnode n5 = {.priority = 5};
struct user_rbnode n6 = {.priority = 6};
rb_insert ( &rb, &n3.rbnode );
rb_insert ( &rb, &n4.rbnode );
rb_insert ( &rb, &n1.rbnode );
rb_insert ( &rb, &n6.rbnode );
rb_insert ( &rb, &n5.rbnode );
rb_insert ( &rb, &n2.rbnode );
// At this point, min is n1, max is n6, which is independent of the order of insertion, only related to the comparison order.
struct rbnode* min = rb_get_min ( &rb );
struct rbnode* max = rb_get_max ( &rb );
// At this point, n1 is still in the tree, exist = True
bool exist = rb_contains ( &rb, &n1.rbnode );
// Remove the maximum and minimum nodes
rb_remove ( &rb, &n1.rbnode );
rb_remove ( &rb, &n6.rbnode );
// At this point, n1 has been deleted from the tree, exist = False
exist = rb_contains ( &rb, &n1.rbnode );
// At this point, min is n2, max is n5
min = rb_get_min ( &rb );
max = rb_get_max ( &rb );
Traversal
Zephyr provides two mechanisms to traverse all nodes in the rbtree. One is rb_walk ( ), which specifies a callback typedef void ( *rb_visit_t ) ( struct rbnode *node, void *cookie ); access function when called, and the tree code calls this function for each node in order. The advantage of this approach is that it is very simple to implement, but the API may seem a bit cumbersome for users. It should also be noted that rb_walk ( ) is a recursive implementation. Example code is as follows:
void rb_visit ( struct rbnode *node, void *cookie )
{
struct user_rbnode *au = CONTAINER_OF ( a, struct user_rbnode, rbnode );
printf ( "Node %p priority %u cookie ( tree ) %p\n", au, au->priority, cookie );
}
rb_walk ( &rb, rb_visit, &rb );
The other method is the traversal macros RB_FOR_EACH and RB_FOR_EACH_CONTAINER, which are similar to linked lists, using nested code blocks, and are non-recursive. By default, they require logarithmic size stack space for the number of nodes (can be configured to use a fixed/maximum size buffer as needed to avoid dynamic allocation). RB_FOR_EACH_CONTAINER traverses pointers to user containers and is generally the one used.
struct user_rbnode *au;
RB_FOR_EACH_CONTAINER ( &rb, au, rbnode ) {
printf ( "Node %p priority %u cookie ( tree ) %p\n", au, au->priority, rb );
}
References
https://docs.zephyrproject.org/3.5.0/kernel/data_structures/rbtree.html