推荐 Linux 源码中的红黑树代码，适用于 MCU
本帖最后由 dukelec 于 2019-8-10 21:43 编辑上次介绍使用 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 多行）：
linux/lib/rbtree.c
v2.6.33-rc6 ~ v2.6.34-rc2
3e58974027b04e84f68b964ef368a6cd758e2f84
"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 比较类似，有端口号的概念，端口号也可以当作命令号。当收到数据，我需要快速查询端口相关信息。
// 用户对象
typedef struct {
rb_node_t node; // 红黑树节点
uint16_t port; // 端口号，做为红黑树的键值
list_head_t rx_head; // 其它用户数据
} cdnet_socket_t;
rb_root_t cdnet_sockets = RB_ROOT; // 初始化 rbtree 的根
// 用户需要为自定义对象添加搜寻函数，譬如这里是输入端口号，返回相关对象。这是一个通用的模板。
cdnet_socket_t *cdnet_socket_search(uint16_t port)
{
struct rb_root *root = &cdnet_sockets;
struct rb_node *node = root->rb_node;
while (node) {
cdnet_socket_t *sock = container_of(node, cdnet_socket_t, node);
if (port < sock->port)
node = node->rb_left;
else if (port > sock->port)
node = node->rb_right;
else
return sock;
}
return NULL;
}
// 用户添加插入方法，如果键值重复，会返回 -1 提示错误。这同样是模板。
int cdnet_socket_insert(cdnet_socket_t *sock)
{
struct rb_root *root = &cdnet_sockets;
struct rb_node **new = &(root->rb_node), *parent = NULL;
while (*new) {
cdnet_socket_t *this = container_of(*new, cdnet_socket_t, node);
parent = *new;
if (sock->port < this->port)
new = &((*new)->rb_left);
else if (sock->port > this->port)
new = &((*new)->rb_right);
else
return -1;
}
// add new node and rebalance tree
rb_link_node(&sock->node, parent, new);
rb_insert_color(&sock->node, root);
return 0;
}
// 还有删除和替换等都比较简单，譬如删除直接调用 rb_erase(struct rb_node *, struct rb_root *); 即可。
使用方法也可以参考标准 linux 的：https://www.infradead.org/~mchehab/kernel_docs/unsorted/rbtree.html （有字符串做键值的例子）。
库的代码：
github: https://github.com/dukelec/cdnet/tree/master/utils 目录下的 rbtree.c 和 rbtree.h 文件（该目录下，还有其它好东西，譬如本文涉及到的 container_of）。 前排膜拜
前排膜拜大佬 前排膜拜大佬 跟着大佬学习一下 我只是搬运工 跟着学习 学以致用，真好。 期待继续挖掘linux精髓 跟着学习 前排占座 python的dict的实现好像是hash map，红黑树恐怕只是渐近复杂度好，常数项可能比较大 brother_yan 发表于 2019-8-10 20:29
python的dict的实现好像是hash map，红黑树恐怕只是渐近复杂度好，常数项可能比较大 ...
是的，已更新，一楼描述 “基本” 改为 “很多”。
hash map 比较简单，但它的表比较耗内存，性能也要看运气，万一冲突比较多，中途被迫换个 hash 算法，或者调整表的大小，都是非常耗时的操作，实时性不好。 占个座学习一下 Linux 的高科技。 多谢分享！ 多谢分享，学习一下 跟着学习 虽然好像看不懂，还是mark一下。 学习学习下 高级，这个叫技术下放吧{:lol:} 膜拜大佬，红黑树 学习下 最近越来越觉得计算机科班的一些知识非常重要，数据结构、算法都是需要深挖，加强学习，多谢楼主。 meirenai 发表于 2019-8-11 13:17
最近越来越觉得计算机科班的一些知识非常重要，数据结构、算法都是需要深挖，加强学习，多谢楼主。 ...
现在硬件资源越来越丰富，慢慢的，那些高级玩法，也能耍得动了。 跟着大佬学习一下
跟着学习 摩拜大佬 这个必须mark一下，很实用 感谢分享，红黑树 摩拜大佬 用红黑树实现字典？有些没看明白 好东西，mark 占个座学习一下 Linux 的高科技
好东西，mark 不用考虑 GPL 的问题？ 如果考虑 GPL 的协议问题，可以使用 BSD 的红黑树实现。 好东西，学习了 上次 speck很受用，这个应该也不错。先标记，回头再来拜读，多谢分享~ 历害了。收藏以方便以后用。
历害了，用心学习 mark 学习了。 高手....... 本帖最后由 fnems 于 2019-8-27 23:26 编辑
我把楼主的rbtree重新封装了一下，代码贴在下面供参考。
说明：linux源码的实现上，红黑树是相对独立的实现，每个节点不能带tag（用户数据）。
因此楼主位的说明以及 https://www.infradead.org/~mchehab/kernel_docs/unsorted/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
#include "rbtree_wrap.h"
rbw_node_t* _rbw_search_node(rb_root_t* root, rbw_cmp_api cmp, void* key)
{
rb_node_t *node = root->rb_node;
while (node) {
rbw_node_t* rbw_node = (void*)container_of(node, rbw_node_t, rbnode);
int result = cmp(key, (void*)(rbw_node->payload));
if (result < 0)
node = node->rb_left;
else if (result > 0)
node = node->rb_right;
else
return rbw_node;
}
return NULL;
}
void* rbw_search(rb_root_t* root, rbw_cmp_api cmp, void* key)
{
rbw_node_t* rbw_node = _rbw_search_node(root, cmp, key);
if(rbw_node)
return rbw_node->payload;
return NULL;
}
int rbw_insert(rb_root_t *root, rbw_cmp_api cmp, rbw_keyof_api keyof, rbw_node_t* node, void* payload)
{
rb_node_t** rb_new = &(root->rb_node);
rb_node_t*rb_parent = NULL;
// Figure out where to put new node
while (*rb_new) {
rbw_node_t* rbw_node = (void*)container_of(*rb_new, rbw_node_t, rbnode);
int result = cmp(keyof(payload), (void*)(rbw_node->payload));
rb_parent = *rb_new;
if (result < 0)
rb_new = &((*rb_new)->rb_left);
else if (result > 0)
rb_new = &((*rb_new)->rb_right);
else
return 0;
}
// Add new node and rebalance tree
node->payload = payload;
rb_link_node(&node->rbnode, rb_parent, rb_new);
rb_insert_color(&node->rbnode, root);
return 1;
}
int rbw_remove(rb_root_t *root, rbw_cmp_api cmp, void* key)
{
rbw_node_t* rbw_node = _rbw_search_node(root, cmp, key);
if(rbw_node)
{
rb_erase(&rbw_node->rbnode, root);
return 1;
}
return 0;
}
rbtree_wrap.h
#ifndef _RBTREE_WRAP_H
#define _RBTREE_WRAP_H
#include "rbtree.h"
#ifndef offsetof
#define offsetof(TYPE, MEMBER) ((size_t)&((TYPE *)0)->MEMBER)
#endif
#ifndef container_of
#define container_of(ptr, type, member) \
((type *)((char *)(ptr) - offsetof(type, member)))
#endif
typedef void* (*rbw_keyof_api)(void* payload);
typedef int (*rbw_cmp_api)(void* key, void* payload);
typedef struct _rbw_node {
rb_node_t rbnode;
void*payload;
} rbw_node_t;
int rbw_insert(rb_root_t *root, rbw_cmp_api cmp, rbw_keyof_api keyof, rbw_node_t* node, void* payload);
int rbw_remove(rb_root_t *root, rbw_cmp_api cmp, void* key);
void* rbw_search(rb_root_t* root, rbw_cmp_api cmp, void* key);
#endif
如何使用：
比如用户有一组数据，定义如下
typedef struct userdata
{
char* name;
int id;
} userdata_t;
userdata_t userdata[] = {
(userdata_t){"Start", 1},
(userdata_t){"Felix", 5},
(userdata_t){"Batou", 3},
(userdata_t){"Maximum", 63},
(userdata_t){"Aramaki", 4},
(userdata_t){"Motoko", 2},
(userdata_t){"Togusa", 11},
};
用户代码需要针对userdata建立红黑树，则仅需要提供：
（1）红黑树根节点，以及额外的红黑树节点存储空间；
#define USERDATA_SZ sizeof(userdata)/sizeof(userdata_t )
rbw_node_t rbt_nodes;
rb_root_trbt_userdata;
（2）上述cmp、keyof两个回调函数。
当以结构体的name元素为键排序及检索时，
#define keyofkeyof_name
#define cmpcmp_name
void* keyof_name (void* payload)
{
user_t* puser = (user_t*)payload;
return puser->name;
}
int cmp_name (void* key, void* payload)
{
return strcmp((char*)key, (char*)keyof_name(payload));
}
当以结构体的id元素为键排序及检索时，
#define keyofkeyof_id
#define cmpcmp_id
void* keyof_id (void* payload)
{
user_t* puser = (user_t*)payload;
return &(puser->id);
}
int cmp_id (void* key, void* payload)
{
return *(int*)key - *(int*)keyof_id(payload);
}
树的建立过程：
for(int k=0; k<USERDATA_SZ; k++)
{
result = rbw_insert(&rbt_userdata, cmp, keyof, &rbt_nodes, &userdata);
}
树的查找：
// if cmp == cmp_name
userdata_t* pdata_motoko = (userdata_t*)rbw_search(&rbt_userdata, cmp_name, (void*)"Motoko");
// if cmp == cmp_id
int id_motoko = 2;
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 于 2019-8-27 22:04 编辑
fnems 发表于 2019-8-27 21:12
我把楼主的rbtree重新封装了一下，代码贴在下面供参考。
说明：linux源码的实现上，红黑树是相对独立的实 ...
我觉得你包的有点复杂，特别是 rbw_node_t 和其中的 payload 这种方式，背离了标准的 container_of 方式。
我改的话，只要把一樓的：
cdnet_socket_t *cdnet_socket_search(uint16_t port);
int cdnet_socket_insert(cdnet_socket_t *sock);
改为以下就好了：
// a_key 和 a 其中只有一个有效，另一个为 NULL
// rbw_search 调用时，用 a_key；rbw_insert 调用时用 a
typedef int (*rbw_cmp_f)(void* a_key, struct rb_node *a, struct rb_node *b);
struct rb_node *rbw_search(rb_root *root, rbw_cmp_f cmp, void *key);
int rbw_insert(rb_root *root, rbw_cmp_f cmp, struct rb_node *new);
本帖最后由 fnems 于 2019-8-27 22:12 编辑
dukelec 发表于 2019-8-27 21:57
我觉得你包的有点复杂，特别是 rbw_node_t 和其中的 payload 这种方式，背离了标准的 container_of 方式 ...
同意对比较回调函数的改写。
int rbw_insert(rb_root *root, rbw_cmp_f cmp, struct rb_node *new);这里，个人觉得把红黑树存储空间与用户数据存储空间分开比较好，所以多一个用于数据指针的参数int rbw_insert(rb_root *root, rbw_cmp_f cmp, struct rb_node *new, void* payload);
基于同样的考虑，struct rb_node *rbw_search(rb_root *root, rbw_cmp_f cmp, void *key);返回包含用户数据的红黑树节点，需要用户取出树中的数据，违背了红黑树与应用层代码分离的意图，所以我的接口直接返回payloadvoid* rbw_search(rb_root *root, rbw_cmp_f cmp, void *key);
班门弄斧，让大神见笑啦～ 个人感觉在单片机上引入红黑树简直是小题大做，能否激发她的性能有待观察{:lol:} 本帖最后由 dukelec 于 2019-8-27 22:41 编辑
fnems 发表于 2019-8-27 22:07
同意对比较回调函数的改写。
这里，个人觉得把红黑树存储空间与用户数据存储空间分开比较好，所以多一个 ...
这个你可以按照自己的意愿来操作。
我个人觉得不分开会简单一些，函数参数少一些，内存管理也只需要处理一份。
如果是第三方库的结构体，不能改其内容的情况下，可以在其外面包一层，这样也是支持我改的方法：只要提前初始化成员，再传给 rbw_insert 就好了。
关于 rbw_search 直接返回 rb_node * 给用户不是很方便，可以包一个宏转一下，这样也比每次用的时候都要强转要清爽。
rbw_insert 和 rbw_search 都建议包一个宏转一下，让参数和返回都不必强转。
在用户 struct 中，只是添加一个 rb_node 模块，也是模块化吧，代码并没有耦合在一起。Linux 内核普遍是这样操作。 哈哈哈，红黑树知识点，记录下 本帖最后由 fnems 于 2019-8-27 23:27 编辑
dukelec 发表于 2019-8-27 22:36
这个你可以按照自己的意愿来操作。
我个人觉得不分开会简单一些，函数参数少一些，内存管理也只需要处理 ...
rbw_insert 用宏转一下确实比我写的好，rbw_insert减少一个参数。向大神学习了
haffman1 发表于 2019-8-27 22:35
个人感觉在单片机上引入红黑树简直是小题大做，能否激发她的性能有待观察 ...
看问题规模。从10个元素中检索跟从200个元素中检索不是一个概念 本帖最后由 fnems 于 2019-8-27 23:56 编辑
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 于 2019-8-28 01:32 编辑
刚想起来，除此之外还有一种情况，需要排序的结构体是固定的配置信息，比较大，用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 函数，效率也高一些。 收藏了，虽然我看不懂， 学习了，项目中暂时还没找到适合的场景。 不错不错 ． 膜拜一下 不明觉厉，收藏 linux进程调试的精髓。 大佬，
虽然看不懂，先收藏 楼主有个问题请教一下，代码开始的这句“rb_root_t cdnet_sockets = RB_ROOT; // 初始化 rbtree 的根”， 是创建了红黑树的根节点吗？那用户定义的结构体 cdnet_socket_t ，也需要定义一个根变量 cdnet_socket_t g_cdnet_state 和 红黑树根节点cdnet_sockets关联起来吗，这个怎么关联呢？
可以，c++的map，python的dict，就是一个带索引的数组，可以当作迷你数据库用，比如存储姓名+学号，输入姓名返回学号，查找速度比遍历查找快。 我是一个大白菜 发表于 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. 初始化好了，后面就是调用使用了。
不用再考虑用户结构体创建一个根变量的问题了。 我是一个大白菜 发表于 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 操作的函數裡面了。
新的代碼，我增加 ...
好的，非常感谢 感谢分享 学习学习 跟着学习 Thank you !!!
页:
[1]