推荐 Linux 源码中的红黑树代码，适用于 MCU

dukelec

上次介绍使用 Linux 的 speck 加密代码用于 MCU： https://www.amobbs.com/thread-5715264-1-1.html
另外有介绍 Linux 的学习方法：https://www.amobbs.com/thread-5715819-1-1.html （1 楼）

这次介绍红黑树代码，代码同样取自相对老一点的内核，因为最新代码，高级功能 augmented rbtrees 耦合的比较紧密，不方便剥离，我只用到最基础的功能。（新代码红黑树算法有图形注释，更直观。）
代码取自版本我有备注在整理后的 c 文件中（c 文件总共 300 多行）：

1.   linux/lib/rbtree.c
   
2.   v2.6.33-rc6 ~ v2.6.34-rc2
   
3.   3e58974027b04e84f68b964ef368a6cd758e2f84
   
4.   "doc: fix typo in comment explaining rb_tree usage"

复制代码

在 MCU 中用过 rbtree 的人应该不多，我先简单介绍下什么时候会用到。

譬如，你的板子有 485 通讯，定义了很多命令，譬如 100 条，如果命令号连续，从 0 开始，我们可以定义一个 100 大小的数组，可直接查询到相应的处理代码，
然而，为了扩展性，我们的命令号通常不连续，有很大的空洞，没法用上述数组方法，因为太浪费空间。

所以，很多人会弄一个数组或者链表，每个元素存放命令号和对应信息，然后 for 循环查找，更简单的是代码写死，用 switch 或 if else 一个个查询。
但这样，每次从头开始查，效率比较低，此时可以考虑用 rbtree，可以很高效的查询到相关命令信息。

其实，高级语言的 dict 词典，很多都是用 rbtree 的方式实现，你提供一个索引，dict 就返回相关信息，所以，当你写 MCU 代码时，想用 dict 的时候，都可以用 rbtree 实现。
（python dict 用的是 hash map，比较耗内存，不太适用 MCU。）

下面是代码使用方法示范，譬如我的 cdnet，它跟 udp 比较类似，有端口号的概念，端口号也可以当作命令号。当收到数据，我需要快速查询端口相关信息。

1. // 用户对象
   
2. typedef struct {
   
3.     rb_node_t       node; // 红黑树节点
   
4.     uint16_t        port; // 端口号，做为红黑树的键值
   
5.     list_head_t     rx_head; // 其它用户数据
   
6. } cdnet_socket_t;

复制代码

1. 
   
2. rb_root_t cdnet_sockets = RB_ROOT; // 初始化 rbtree 的根
   
3. 
   
4. // 用户需要为自定义对象添加搜寻函数，譬如这里是输入端口号，返回相关对象。这是一个通用的模板。
   
5. cdnet_socket_t *cdnet_socket_search(uint16_t port)
   
6. {
   
7.     struct rb_root *root = &cdnet_sockets;
   
8.     struct rb_node *node = root->rb_node;
   
9. 
   
10.     while (node) {
    
11.         cdnet_socket_t *sock = container_of(node, cdnet_socket_t, node);
    
12. 
    
13.         if (port < sock->port)
    
14.             node = node->rb_left;
    
15.         else if (port > sock->port)
    
16.             node = node->rb_right;
    
17.         else
    
18.             return sock;
    
19.     }
    
20.     return NULL;
    
21. }
    
22. 
    
23. // 用户添加插入方法，如果键值重复，会返回 -1 提示错误。这同样是模板。
    
24. int cdnet_socket_insert(cdnet_socket_t *sock)
    
25. {
    
26.     struct rb_root *root = &cdnet_sockets;
    
27.     struct rb_node **new = &(root->rb_node), *parent = NULL;
    
28. 
    
29.     while (*new) {
    
30.         cdnet_socket_t *this = container_of(*new, cdnet_socket_t, node);
    
31. 
    
32.         parent = *new;
    
33.         if (sock->port < this->port)
    
34.             new = &((*new)->rb_left);
    
35.         else if (sock->port > this->port)
    
36.             new = &((*new)->rb_right);
    
37.         else
    
38.             return -1;
    
39.     }
    
40. 
    
41.     // add new node and rebalance tree
    
42.     rb_link_node(&sock->node, parent, new);
    
43.     rb_insert_color(&sock->node, root);
    
44.     return 0;
    
45. }
    
46. 
    
47. // 还有删除和替换等都比较简单，譬如删除直接调用 rb_erase(struct rb_node *, struct rb_root *); 即可。

复制代码

使用方法也可以参考标准 linux 的：https://www.infradead.org/~mcheh ... nsorted/rbtree.html （有字符串做键值的例子）。

库的代码：
github: https://github.com/dukelec/cdnet/tree/master/utils 目录下的 rbtree.c 和 rbtree.h 文件（该目录下，还有其它好东西，譬如本文涉及到的 container_of）。

vtte

前排膜拜

chaplin1999

前排膜拜大佬

zzm24

前排膜拜大佬

我是一个大白菜

跟着大佬学习一下

dukelec

我只是搬运工

jordonwu

跟着学习

一号纵队

学以致用，真好。

FireBrain

期待继续挖掘linux精髓

Excellence

跟着学习

dragonbbc

前排占座

brother_yan

python的dict的实现好像是hash map，红黑树恐怕只是渐近复杂度好，常数项可能比较大

dukelec

brother_yan 发表于 2019-8-10 20:29
python的dict的实现好像是hash map，红黑树恐怕只是渐近复杂度好，常数项可能比较大 ...

是的，已更新，一楼描述 “基本” 改为 “很多”。
hash map 比较简单，但它的表比较耗内存，性能也要看运气，万一冲突比较多，中途被迫换个 hash 算法，或者调整表的大小，都是非常耗时的操作，实时性不好。

security

占个座学习一下 Linux 的高科技。

szyusong@163

多谢分享！

Pupil

多谢分享，学习一下

sh0568

跟着学习

powerlabor001

虽然好像看不懂，还是mark一下。

huangguimina4

学习学习下

didadida

高级，这个叫技术下放吧

mikewang011

膜拜大佬，红黑树 学习下

meirenai

最近越来越觉得计算机科班的一些知识非常重要，数据结构、算法都是需要深挖，加强学习，多谢楼主。

security

meirenai 发表于 2019-8-11 13:17
最近越来越觉得计算机科班的一些知识非常重要，数据结构、算法都是需要深挖，加强学习，多谢楼主。 ...

现在硬件资源越来越丰富，慢慢的，那些高级玩法，也能耍得动了。

dreambox

跟着大佬学习一下

xiaomu

跟着学习

love_zjb

摩拜大佬

hkchenhao

这个必须mark一下，很实用

mypc16888

感谢分享，红黑树

yanyanyan168

摩拜大佬

gsq19920418

用红黑树实现字典？有些没看明白

weif40423p

好东西，mark

迅得电子

占个座学习一下 Linux 的高科技

myhonour

好东西，mark

abutter

不用考虑 GPL 的问题？

abutter

如果考虑 GPL 的协议问题，可以使用 BSD 的红黑树实现。

makathy

好东西，学习了

heimareed

上次 speck很受用，这个应该也不错。先标记，回头再来拜读，多谢分享~

wuhuijiang

历害了。收藏以方便以后用。

john_8

历害了，用心学习

jsplyy

mark                           

lyping1987

学习了。

ycii

高手.......

fnems

我把楼主的rbtree重新封装了一下，代码贴在下面供参考。

说明：linux源码的实现上，红黑树是相对独立的实现，每个节点不能带tag（用户数据）。
因此楼主位的说明以及 https://www.infradead.org/~mcheh ... nsorted/rbtree.html 页面的示例都是用户根据应用环境编写针对性的适配层代码（adapter，或称胶水代码）。

这样做有一个弊端，就是适配层与应用环境高度耦合。举个例子，在管理通讯接口上检索节点可能是通过端口号（数值）；而在检索以字符串命名的设备上检索是通过字符串进行的。
同样的红黑树库，需要两套查找、插入、删除的适配层。

为了消除这个弊端而做的重新封装（wrap），就是为了将适配层与应用环境剥离，实现一个相对比较通用的适配层。这种剥离方式参考了stdlib标准库里面qsort将比较函数作为回调（callback）的做法。
需要剥离的使用环境的因素包括：
（1）用户数据结构的格式（使用环境下用户结构体的定义）
（2）用户数据结构中用来排序的键（即用户结构体中使用哪种类型、哪个成员来排序）
（3）用户数据结构的排序规则（按数值，按字符串，按某种函数计算值等）

剥离方法：细节见源码。
经过重新封装后的接口：
（1）红黑树插入节点：
int rbw_insert(rb_root_t* root, rbw_cmp_api cmp, rbw_keyof_api keyof, rbw_node_t* node, void* payload);
其中root是红黑树句柄，node是红黑树节点（需要用户分配存储区），payload是用户结构体；
这个接口用到了两个回调函数，分别是
(a) cmp，比较回调函数，原型是typedef int  (*rbw_cmp_api)  (void* key, void* payload); 传入参数key是用来比较的键值，payload是用户结构体，返回值负数表示key小于payload->key，正数表示key大于payload->key，0表示key等于payload->key。
(b) keyof，取键值回调函数，原型是typedef void* (*rbw_keyof_api)(void* payload); 传入参数payload是用户结构体，返回值是payload中的key。

（2）红黑树中删除带有特定键值的节点：
int rbw_remove(rb_root_t* root, rbw_cmp_api cmp, void* key);
其中root是红黑树句柄，key是待删除节点的键值，cmp是上述比较回调函数。

（3）查找特定键值的节点：
void* rbw_search(rb_root_t* root, rbw_cmp_api cmp, void* key);
其中root是红黑树句柄，key是待查找的键值，cmp是上述比较回调函数；返回值是具有键值key的用户结构体payload。

rbtree_wrap.c

1. #include "rbtree_wrap.h"
   
2. 
   
3. rbw_node_t* _rbw_search_node(rb_root_t* root, rbw_cmp_api cmp, void* key)
   
4. {
   
5.   rb_node_t *node = root->rb_node;
   
6.   while (node) {
   
7.     rbw_node_t* rbw_node = (void*)container_of(node, rbw_node_t, rbnode);
   
8.     int result = cmp(key, (void*)(rbw_node->payload));
   
9.     if (result < 0)
   
10.       node = node->rb_left;
    
11.     else if (result > 0)
    
12.       node = node->rb_right;
    
13.     else
    
14.       return rbw_node;
    
15.   }
    
16.   return NULL;
    
17. }
    
18. 
    
19. void* rbw_search(rb_root_t* root, rbw_cmp_api cmp, void* key)
    
20. {
    
21.   rbw_node_t* rbw_node = _rbw_search_node(root, cmp, key);
    
22.   if(rbw_node)
    
23.     return rbw_node->payload;
    
24.   return NULL;
    
25. }
    
26. 
    
27. int rbw_insert(rb_root_t *root, rbw_cmp_api cmp, rbw_keyof_api keyof, rbw_node_t* node, void* payload)
    
28. {
    
29.   rb_node_t** rb_new = &(root->rb_node);
    
30.   rb_node_t*  rb_parent = NULL;
    
31.   // Figure out where to put new node
    
32.   while (*rb_new) {
    
33.     rbw_node_t* rbw_node = (void*)container_of(*rb_new, rbw_node_t, rbnode);
    
34.     int result = cmp(keyof(payload), (void*)(rbw_node->payload));
    
35.     rb_parent = *rb_new;
    
36.     if (result < 0)
    
37.       rb_new = &((*rb_new)->rb_left);
    
38.     else if (result > 0)
    
39.       rb_new = &((*rb_new)->rb_right);
    
40.     else
    
41.       return 0;
    
42.   }
    
43.   // Add new node and rebalance tree
    
44.   node->payload = payload;
    
45.   rb_link_node(&node->rbnode, rb_parent, rb_new);
    
46.   rb_insert_color(&node->rbnode, root);
    
47.   return 1;
    
48. }
    
49. 
    
50. int rbw_remove(rb_root_t *root, rbw_cmp_api cmp, void* key)
    
51. {
    
52.   rbw_node_t* rbw_node = _rbw_search_node(root, cmp, key);
    
53.   if(rbw_node)
    
54.   {
    
55.     rb_erase(&rbw_node->rbnode, root);
    
56.     return 1;
    
57.   }
    
58.   return 0;
    
59. }

复制代码

rbtree_wrap.h

1. #ifndef _RBTREE_WRAP_H
   
2. #define _RBTREE_WRAP_H
   
3. 
   
4. #include "rbtree.h"
   
5. 
   
6. #ifndef offsetof
   
7. #define offsetof(TYPE, MEMBER) ((size_t)&((TYPE *)0)->MEMBER)
   
8. #endif
   
9. 
   
10. #ifndef container_of
    
11. #define container_of(ptr, type, member) \
    
12.    ((type *)((char *)(ptr) - offsetof(type, member)))
    
13. #endif
    
14. 
    
15. typedef void* (*rbw_keyof_api)(void* payload);
    
16. typedef int   (*rbw_cmp_api)  (void* key, void* payload);
    
17. 
    
18. typedef struct _rbw_node {
    
19.   rb_node_t rbnode;
    
20.   void*  payload;
    
21. } rbw_node_t;
    
22. 
    
23. int   rbw_insert(rb_root_t *root, rbw_cmp_api cmp, rbw_keyof_api keyof, rbw_node_t* node, void* payload);
    
24. int   rbw_remove(rb_root_t *root, rbw_cmp_api cmp, void* key);
    
25. void* rbw_search(rb_root_t* root, rbw_cmp_api cmp, void* key);
    
26. 
    
27. #endif

复制代码

如何使用：
比如用户有一组数据，定义如下

1. typedef struct userdata
   
2. {
   
3.   char* name;
   
4.   int id;
   
5. } userdata_t;
   
6. 
   
7. userdata_t userdata[] = {
   
8.   (userdata_t){"Start",    1},
   
9.   (userdata_t){"Felix",    5},
   
10.   (userdata_t){"Batou",   3},
    
11.   (userdata_t){"Maximum", 63},
    
12.   (userdata_t){"Aramaki",   4},
    
13.   (userdata_t){"Motoko",     2},
    
14.   (userdata_t){"Togusa",   11},
    
15. };

复制代码

用户代码需要针对userdata建立红黑树，则仅需要提供：
（1）红黑树根节点，以及额外的红黑树节点存储空间；

1. #define USERDATA_SZ sizeof(userdata)/sizeof(userdata_t )
   
2. 
   
3. rbw_node_t rbt_nodes[USERDATA_SZ ];
   
4. rb_root_t  rbt_userdata;

复制代码

（2）上述cmp、keyof两个回调函数。
当以结构体的name元素为键排序及检索时，

1. #define keyof  keyof_name
   
2. #define cmp  cmp_name
   
3. void* keyof_name (void* payload)
   
4. {
   
5.   user_t* puser = (user_t*)payload;
   
6.   return puser->name;
   
7. }
   
8. 
   
9. int cmp_name (void* key, void* payload)
   
10. {
    
11.   return strcmp((char*)key, (char*)keyof_name(payload));
    
12. }

复制代码

当以结构体的id元素为键排序及检索时，

1. #define keyof  keyof_id
   
2. #define cmp  cmp_id
   
3. void* keyof_id (void* payload)
   
4. {
   
5.   user_t* puser = (user_t*)payload;
   
6.   return &(puser->id);
   
7. }
   
8. 
   
9. int cmp_id (void* key, void* payload)
   
10. {
    
11.   return *(int*)key - *(int*)keyof_id(payload);
    
12. }

复制代码

树的建立过程：

1. for(int k=0; k<USERDATA_SZ; k++)
   
2. {
   
3.   result = rbw_insert(&rbt_userdata, cmp, keyof, &rbt_nodes[k], &userdata[k]);
   
4. }

复制代码

树的查找：

1. // if cmp == cmp_name
   
2.   userdata_t* pdata_motoko = (userdata_t*)rbw_search(&rbt_userdata, cmp_name, (void*)"Motoko");
   
3. // if cmp == cmp_id
   
4.   int id_motoko = 2;
   
5.   userdata_t* pdata_motoko = (userdata_t*)rbw_search(&rbt_userdata, cmp_id, (void*)&id_motoko );

复制代码

注意，树节点的插入、删除与检索使用的回调函数必须匹配。即使用cmp_name、keyof_name建立的红黑树，不能使用cmp_id来检索、删除，否则会无法找到节点。

从例子代码能看到，这种封装还有一个微弱的好处，就是不需要改变使用环境下的结构体定义。
当不使用红黑树时，通过从头到尾查找的笨办法也能实现检索；使用红黑树时，红黑树的结构存在于rbt_nodes结构体中，userdata_t结构体没有一点变化。
这个特性对于某些协同开发，或者上游固定不能更改的环境是有利的。

dukelec

fnems 发表于 2019-8-27 21:12
我把楼主的rbtree重新封装了一下，代码贴在下面供参考。

说明：linux源码的实现上，红黑树是相对独立的实 ...

我觉得你包的有点复杂，特别是 rbw_node_t 和其中的 payload 这种方式，背离了标准的 container_of 方式。

我改的话，只要把一樓的：

1. cdnet_socket_t *cdnet_socket_search(uint16_t port);
   
2. int cdnet_socket_insert(cdnet_socket_t *sock);

复制代码

改为以下就好了：

1. // a_key 和 a 其中只有一个有效，另一个为 NULL
   
2. // rbw_search 调用时，用 a_key；rbw_insert 调用时用 a
   
3. typedef int (*rbw_cmp_f)(void* a_key, struct rb_node *a, struct rb_node *b);
   
4. 
   
5. struct rb_node *rbw_search(rb_root *root, rbw_cmp_f cmp, void *key);
   
6. int rbw_insert(rb_root *root, rbw_cmp_f cmp, struct rb_node *new);

复制代码

fnems

dukelec 发表于 2019-8-27 21:57
我觉得你包的有点复杂，特别是 rbw_node_t 和其中的 payload 这种方式，背离了标准的 container_of 方式 ...

同意对比较回调函数的改写。

1. int rbw_insert(rb_root *root, rbw_cmp_f cmp, struct rb_node *new);

复制代码

这里，个人觉得把红黑树存储空间与用户数据存储空间分开比较好，所以多一个用于数据指针的参数

1. int rbw_insert(rb_root *root, rbw_cmp_f cmp, struct rb_node *new, void* payload);

复制代码

基于同样的考虑，

1. struct rb_node *rbw_search(rb_root *root, rbw_cmp_f cmp, void *key);

复制代码

返回包含用户数据的红黑树节点，需要用户取出树中的数据，违背了红黑树与应用层代码分离的意图，所以我的接口直接返回payload

1. void* rbw_search(rb_root *root, rbw_cmp_f cmp, void *key);

复制代码

班门弄斧，让大神见笑啦～

haffman1

个人感觉在单片机上引入红黑树简直是小题大做，能否激发她的性能有待观察

dukelec

fnems 发表于 2019-8-27 22:07
同意对比较回调函数的改写。

这里，个人觉得把红黑树存储空间与用户数据存储空间分开比较好，所以多一个 ...

这个你可以按照自己的意愿来操作。

我个人觉得不分开会简单一些，函数参数少一些，内存管理也只需要处理一份。

如果是第三方库的结构体，不能改其内容的情况下，可以在其外面包一层，这样也是支持我改的方法：只要提前初始化成员，再传给 rbw_insert 就好了。

关于 rbw_search 直接返回 rb_node * 给用户不是很方便，可以包一个宏转一下，这样也比每次用的时候都要强转要清爽。
rbw_insert 和 rbw_search 都建议包一个宏转一下，让参数和返回都不必强转。

在用户 struct 中，只是添加一个 rb_node 模块，也是模块化吧，代码并没有耦合在一起。Linux 内核普遍是这样操作。

tianbianren

哈哈哈，红黑树知识点，记录下

fnems

dukelec 发表于 2019-8-27 22:36
这个你可以按照自己的意愿来操作。

我个人觉得不分开会简单一些，函数参数少一些，内存管理也只需要处理 ...

rbw_insert 用宏转一下确实比我写的好，rbw_insert减少一个参数。向大神学习了

fnems

haffman1 发表于 2019-8-27 22:35
个人感觉在单片机上引入红黑树简直是小题大做，能否激发她的性能有待观察 ...

看问题规模。从10个元素中检索跟从200个元素中检索不是一个概念

fnems

dukelec 发表于 2019-8-27 22:36
这个你可以按照自己的意愿来操作。

我个人觉得不分开会简单一些，函数参数少一些，内存管理也只需要处理 ...

第三方库的结构体，不能改其内容的情况下

刚想起来，除此之外还有一种情况，需要排序的结构体是固定的配置信息，比较大，用const定义在了ROM空间内。这样就需要单独存放的红黑树，运行在RAM空间。

在用户 struct 中，只是添加一个 rb_node 模块

在rbw_insert时，如果传入用户 struct，需要知道用户struct的rb_node 在哪里来调用rb_link_node；
如果传入rb_node元素，也需要知道用户struct的定义，由rb_node获得用户struct，传给rbw_cmp_f。
所以在wrap中还是需要更多信息来剥离用户层

其实我觉得最好的解决方法是在 rb_node中加tag，链接到用户struct。不过我又不想改这个红黑树源码，所以才封装的 [手动笑哭表情]

dukelec

刚想起来，除此之外还有一种情况，需要排序的结构体是固定的配置信息，比较大，用const定义在了ROM空间内。这样就需要单独存放的红黑树，运行在RAM空间。

定义一个 struct 存放到 ram，该 struct 中，用指针指向 rom 中数据即可。

在rbw_insert时，如果传入用户 struct，需要知道用户struct的rb_node 在哪里来调用rb_link_node；

用户不直接调用 rbw_insert，而是调用一个宏（最好是用 static inline 的函数），传 struct 给宏，宏取出 rb_node 地址给 rbw_insert.

如果传入rb_node元素，也需要知道用户struct的定义，由rb_node获得用户struct，传给rbw_cmp_f。

宏是场合相关的，它知道用户struct 的类型，通过取子成员 和 container_of 进行相互转换。
传给 cmp 函数的也是 rb_node 地址，cmp 内部通过 container_of 转到用户 struct, 因为 cmp 函数是知道用户 struct 类型的。

最终是否要抽象这么一层还是要看具体场合，其实按照 1 楼的方式，也不会浪费多少空间。而且不用调用 cmp 函数，效率也高一些。

jjj

收藏了，虽然我看不懂，

expresschs

学习了，项目中暂时还没找到适合的场景。

wuhuijiang

不错不错　．

batou

膜拜一下

fengyunyu

不明觉厉，收藏

wmlovetoday

linux进程调试的精髓。

QL攻城狮

大佬，
虽然看不懂，先收藏

我是一个大白菜

楼主有个问题请教一下，代码开始的这句“rb_root_t cdnet_sockets = RB_ROOT; // 初始化 rbtree 的根”， 是创建了红黑树的根节点吗？那用户定义的结构体 cdnet_socket_t ，也需要定义一个根变量 cdnet_socket_t g_cdnet_state 和 红黑树根节点cdnet_sockets关联起来吗，这个怎么关联呢？

qwe2231695

可以，c++的map，python的dict，就是一个带索引的数组，可以当作迷你数据库用，比如存储姓名+学号，输入姓名返回学号，查找速度比遍历查找快。

dukelec

我是一个大白菜 发表于 2021-12-14 22:16
楼主有个问题请教一下，代码开始的这句“rb_root_t cdnet_sockets = RB_ROOT; // 初始化 rbtree 的根”，  ...

rb_root_t 是定義樹根
rb_node_t 是定義樹梢

對於一個紅黑樹，樹根 的實例 只有 1 個，而 樹梢 的實例的數量不限

用戶的數據是捆綁在 樹梢 上的，所以用戶數據的定義和 樹根 沒有關係

至於用戶的數據是如何捆綁在 樹梢 上，和普通鏈表的 node 一樣，一般有兩種形式：

初級 mcu 程序員常用的方法是，在 node 的定義裏面，定義一個 void * 類型的指針，用這個指針指向用戶數據的結構體
（或者是把 node 的定義和 用戶數據 混裝在單個 struct 結構裏面，鏈表程序在處理 node 的時候，只讀寫最開頭和鏈表相關的 struct 成員）

而 linux kernel 的 c 語言的面向對象的方式更優雅，定義一個包含 rb_node_t 成員的用戶 struct，rb_node_t 成員可以在用戶 struct 的任何位置，開頭、中間、或結尾
對於紅黑樹的相關操作，只需要操作這個用戶 struct 內的 rb_node_t 成員，而不用理會這個 rb_node_t 其實是被一個更大的用戶 struct 所包含
等拿到想要的 rb_node_t 節點後，如果想繼續拿到包裹它的用戶 struct，則使用 container_of 獲取 用戶 struct 的實例地址

以上，container_of 就是 linux kernel 的 c 語言面向對象編程的核心所在，你可以搜尋 container_of 查找更多相關資料

我是一个大白菜

dukelec 发表于 2021-12-14 23:33
rb_root_t 是定義樹根
rb_node_t 是定義樹梢

非常感谢您的指导。我这么理解您看对不对，我要使用这个红黑树的时候，1.定义好我自己的用户数据结构体包含了rb_node_t 这个类型的成员；2. 初始化红黑树的时候，按照我的key，调用函数cdnet_socket_insert(cdnet_socket_t *sock) ，插入用户数据；3. 初始化好了，后面就是调用使用了。
不用再考虑用户结构体创建一个根变量的问题了。

dukelec

我是一个大白菜 发表于 2021-12-15 09:23
非常感谢您的指导。我这么理解您看对不对，我要使用这个红黑树的时候，1.定义好我自己的用户数据结构体包 ...

是的，之前的這個 cdnet socket 只有一個 根，所以寫死在 socket 操作的函數裡面了。

新的代碼，我增加了一個網路的 name space 對象，每個 name space 包含一個獨立的 根 實例，你也可以參考一下：
https://github.com/dukelec/cdnet/blob/master/dispatch/helper.c

我是一个大白菜

dukelec 发表于 2021-12-15 09:43
是的，之前的這個 cdnet socket 只有一個 根，所以寫死在 socket 操作的函數裡面了。

新的代碼，我增加 ...

好的，非常感谢

luckywlpyy

感谢分享

rube

学习学习

liang16888

跟着学习 Thank you !!!