概述 链接到标题

链表的搜索时间复杂度为 O(N) ，在链表管理的成员规模变大时，搜索的算法成本变大。对于这种情况，Zephyr 提供了一个红黑树实现，对于大小为 N 的树，搜索和删除操作的时间复杂度为 O(log2(N)) 。在 Zephyr 中内核调度算法和 p4wq 中使用了红黑树。

Zephyr 中红黑树的实现代码为：

  • zephyr/include/zephyr/sys/p4wq.h
  • zephyr/lib/os/rb.c

Zephyr 实现的是一个传统的红黑树，其算法不是本文的讨论重点，这里只列出一些 Zephyr 的实现要点：

  • 从树根到任何叶子的路径长度不超过其他叶子路径长度的两倍
  • 红色子节点不能有红色子节点
  • Zephyr 的旋转并不只是简单的交换节点内部数据指针实现，还有更为复杂的边缘条件处理
  • Zephyr 的树节点只包含两个指针，空间开销和双向链表一样 ( 通常的实现会有 3 个指针，多一个指向父节点 )

结构体 链接到标题

树 链接到标题

使用 struct rbtree 管理红黑树，对于红黑树外部只设置 lessthan_fn,其它的为内部管理使用：

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 */
};

节点 链接到标题

使用 struct rbnode 管理树节点

struct rbnode {
    /** @cond INTERNAL_HIDDEN */
    struct rbnode *children [2];
    /** @endcond */
};

与 Zephyr 的链表一样，rbtree 中的节点存在于用户管理的内存中的结构，因此使用树前要先定义用户节点

struct user_rbnode {
    struct rbnode rbnode;
    sys_dlist_t dlnode;
    uint32_t priority;
    void *data;
};

需要注意：与用户可以直接通过链表节点遍历链表不一样，rbnode 中的数据是完全不透明的，用户无法提取二叉树拓扑进行「手动」遍历。

初始化 链接到标题

使用 struct rbtree 管理红黑树，对于该结构，没有特定的 API 进行初始化，对该结构成员赋值 0。赋值时需要提供比较函数来帮助红黑树进行排序判断：

typedef bool ( *rb_lessthan_t ) ( struct rbnode *a, struct rbnode *b ) ;

当比较函数认为节点 a「小于」节点 b 时此函数应返回布尔值 True。但注意，树中的节点不允许「相等」，必须具有固定顺序才能使红黑树算法正常工作。

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;
}

典型的初始化过程

struct rbtree rb;
memset ( &rb, 0, sizeof ( struct rbtree )) ;
rb.lessthan_fn = rb_lessthan;

操作 链接到标题

使用 rb_insert ( ) 插入节点， rb_remove ( ) 删除节点。由 rb_get_min ( ) 和 rb_get_max ( ) 完成对树中的「第一个」和「最后一个」节点的访问 ( 在比较函数定义的顺序的意义上 ) 。另外还提供 rb_contains ( ) 来判断节点是否属于指定的树。如果属于则返回 True, 示例代码如下:

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 ) ;

//此时 min 是 n1, max 是 n6，和插入的时间顺序无关，只和比较顺序有关
struct rbnode* min = rb_get_min ( &rb ) ;
struct rbnode* max = rb_get_max ( &rb ) ;

//此时 n1 还在树中，exist = True
bool exist = rb_contains ( &rb, &n1.rbnode ) ;

//移除最大和最小节点
rb_remove ( &rb, &n1.rbnode ) ;
rb_remove ( &rb, &n6.rbnode ) ;

//此时 n1 已从树中删除，exist = False
exist = rb_contains ( &rb, &n1.rbnode ) ;

//此时 min 是 n2, max 是 n5
min = rb_get_min ( &rb ) ;
max = rb_get_max ( &rb ) ;

遍历 链接到标题

Zephyr 提供了两种机制来遍历 rbtree 中的所有节点。一种是 rb_walk ( ) ，在调用时指定回调 typedef void ( *rb_visit_t ) ( struct rbnode *node, void *cookie ) ; 访问函数，树代码按顺序为每个节点调用该函数。这样做的优点是实现非常简单，但对用户来说 API 会稍显繁琐。还要注意的是 rb_walk ( ) 是一个递归实现。示例代码如下：


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 ) ;

另一种是遍历宏 RB_FOR_EACH 和 RB_FOR_EACH_CONTAINER，它与链表的类似，使用嵌套代码块，并且是非递归的，默认情况下需要节点数对数大小的堆栈空间 ( 可以根据需要配置为使用固定/最大大小的缓冲区，以避免动态分配 )RB_FOR_EACH_CONTAINER 为指向用户容器的指针进行遍历，一般情况下都只会使用这一个

struct user_rbnode *au;
RB_FOR_EACH_CONTAINER ( &rb, au, rbnode ) {
             printf ( "Node %p priority %u cookie ( tree ) %p\n", au, au->priority, rb ) ;
        }

参考 链接到标题

https://docs.zephyrproject.org/3.5.0/kernel/data_structures/rbtree.html