搜索
bottom↓
回复: 64

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

  [复制链接]

出200入1068汤圆

发表于 2019-8-10 16:31:55 | 显示全部楼层 |阅读模式
本帖最后由 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 多行):
  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. rb_root_t cdnet_sockets = RB_ROOT; // 初始化 rbtree 的根

  2. // 用户需要为自定义对象添加搜寻函数,譬如这里是输入端口号,返回相关对象。这是一个通用的模板。
  3. cdnet_socket_t *cdnet_socket_search(uint16_t port)
  4. {
  5.     struct rb_root *root = &cdnet_sockets;
  6.     struct rb_node *node = root->rb_node;

  7.     while (node) {
  8.         cdnet_socket_t *sock = container_of(node, cdnet_socket_t, node);

  9.         if (port < sock->port)
  10.             node = node->rb_left;
  11.         else if (port > sock->port)
  12.             node = node->rb_right;
  13.         else
  14.             return sock;
  15.     }
  16.     return NULL;
  17. }

  18. // 用户添加插入方法,如果键值重复,会返回 -1 提示错误。这同样是模板。
  19. int cdnet_socket_insert(cdnet_socket_t *sock)
  20. {
  21.     struct rb_root *root = &cdnet_sockets;
  22.     struct rb_node **new = &(root->rb_node), *parent = NULL;

  23.     while (*new) {
  24.         cdnet_socket_t *this = container_of(*new, cdnet_socket_t, node);

  25.         parent = *new;
  26.         if (sock->port < this->port)
  27.             new = &((*new)->rb_left);
  28.         else if (sock->port > this->port)
  29.             new = &((*new)->rb_right);
  30.         else
  31.             return -1;
  32.     }

  33.     // add new node and rebalance tree
  34.     rb_link_node(&sock->node, parent, new);
  35.     rb_insert_color(&sock->node, root);
  36.     return 0;
  37. }

  38. // 还有删除和替换等都比较简单,譬如删除直接调用 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)。

本帖子中包含更多资源

您需要 登录 才可以下载或查看,没有帐号?注册

x

出0入24汤圆

发表于 2019-8-10 16:35:27 来自手机 | 显示全部楼层
前排膜拜

出0入0汤圆

发表于 2019-8-10 16:43:29 | 显示全部楼层

前排膜拜大佬

出0入0汤圆

发表于 2019-8-10 17:00:06 | 显示全部楼层
前排膜拜大佬

出0入42汤圆

发表于 2019-8-10 17:39:33 来自手机 | 显示全部楼层
跟着大佬学习一下

出200入1068汤圆

 楼主| 发表于 2019-8-10 17:47:01 来自手机 | 显示全部楼层
我只是搬运工

出0入0汤圆

发表于 2019-8-10 18:29:32 来自手机 | 显示全部楼层
跟着学习

出0入0汤圆

发表于 2019-8-10 18:36:47 | 显示全部楼层
学以致用,真好。

出0入0汤圆

发表于 2019-8-10 18:42:50 来自手机 | 显示全部楼层
期待继续挖掘linux精髓

出0入0汤圆

发表于 2019-8-10 19:29:39 | 显示全部楼层
跟着学习

出0入0汤圆

发表于 2019-8-10 20:07:04 | 显示全部楼层
前排占座

出10入284汤圆

发表于 2019-8-10 20:29:25 来自手机 | 显示全部楼层
python的dict的实现好像是hash map,红黑树恐怕只是渐近复杂度好,常数项可能比较大

出200入1068汤圆

 楼主| 发表于 2019-8-10 21:48:50 | 显示全部楼层
brother_yan 发表于 2019-8-10 20:29
python的dict的实现好像是hash map,红黑树恐怕只是渐近复杂度好,常数项可能比较大 ...

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

出0入8汤圆

发表于 2019-8-10 22:04:12 来自手机 | 显示全部楼层
占个座学习一下 Linux 的高科技。

出0入10汤圆

发表于 2019-8-10 22:22:26 来自手机 | 显示全部楼层
多谢分享!

出0入0汤圆

发表于 2019-8-11 08:14:34 来自手机 | 显示全部楼层
多谢分享,学习一下

出0入0汤圆

发表于 2019-8-11 09:06:06 | 显示全部楼层
跟着学习

出0入0汤圆

发表于 2019-8-11 09:25:47 | 显示全部楼层
虽然好像看不懂,还是mark一下。

出0入0汤圆

发表于 2019-8-11 09:31:53 来自手机 | 显示全部楼层
学习学习下

出0入0汤圆

发表于 2019-8-11 10:53:23 | 显示全部楼层
高级,这个叫技术下放吧

出0入0汤圆

发表于 2019-8-11 12:58:23 来自手机 | 显示全部楼层
膜拜大佬,红黑树 学习下

出0入0汤圆

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

出0入8汤圆

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

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

出0入0汤圆

发表于 2019-8-12 11:17:03 | 显示全部楼层
跟着大佬学习一下

出0入0汤圆

发表于 2019-8-12 12:24:14 | 显示全部楼层

跟着学习

出0入0汤圆

发表于 2019-8-12 12:44:29 来自手机 | 显示全部楼层
摩拜大佬

出0入0汤圆

发表于 2019-8-12 14:28:24 | 显示全部楼层
这个必须mark一下,很实用

出0入0汤圆

发表于 2019-8-13 07:41:26 来自手机 | 显示全部楼层
感谢分享,红黑树

出90入102汤圆

发表于 2019-8-13 07:47:04 | 显示全部楼层
摩拜大佬

出0入0汤圆

发表于 2019-8-13 09:11:40 | 显示全部楼层
用红黑树实现字典?有些没看明白

出0入0汤圆

发表于 2019-8-13 10:20:46 | 显示全部楼层
好东西,mark

出0入0汤圆

发表于 2019-8-13 10:39:59 | 显示全部楼层
占个座学习一下 Linux 的高科技

出0入0汤圆

发表于 2019-8-13 10:51:33 | 显示全部楼层

好东西,mark

出0入12汤圆

发表于 2019-8-13 10:55:24 | 显示全部楼层
不用考虑 GPL 的问题?

出0入12汤圆

发表于 2019-8-13 10:55:57 | 显示全部楼层
如果考虑 GPL 的协议问题,可以使用 BSD 的红黑树实现。

出0入0汤圆

发表于 2019-8-13 13:39:39 | 显示全部楼层
好东西,学习了

出0入0汤圆

发表于 2019-8-26 23:10:46 | 显示全部楼层
上次 speck很受用,这个应该也不错。先标记,回头再来拜读,多谢分享~

出0入0汤圆

发表于 2019-8-27 07:16:59 | 显示全部楼层
历害了。收藏以方便以后用。

出0入0汤圆

发表于 2019-8-27 08:18:05 | 显示全部楼层

历害了,用心学习

出0入0汤圆

发表于 2019-8-27 13:39:12 | 显示全部楼层
mark                           

出135入222汤圆

发表于 2019-8-27 13:45:50 | 显示全部楼层
学习了。

出0入0汤圆

发表于 2019-8-27 13:47:49 来自手机 | 显示全部楼层
高手.......

出0入0汤圆

发表于 2019-8-27 21:12:37 | 显示全部楼层
本帖最后由 fnems 于 2019-8-27 23:26 编辑

我把楼主的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. rbw_node_t* _rbw_search_node(rb_root_t* root, rbw_cmp_api cmp, void* key)
  3. {
  4.   rb_node_t *node = root->rb_node;
  5.   while (node) {
  6.     rbw_node_t* rbw_node = (void*)container_of(node, rbw_node_t, rbnode);
  7.     int result = cmp(key, (void*)(rbw_node->payload));
  8.     if (result < 0)
  9.       node = node->rb_left;
  10.     else if (result > 0)
  11.       node = node->rb_right;
  12.     else
  13.       return rbw_node;
  14.   }
  15.   return NULL;
  16. }

  17. void* rbw_search(rb_root_t* root, rbw_cmp_api cmp, void* key)
  18. {
  19.   rbw_node_t* rbw_node = _rbw_search_node(root, cmp, key);
  20.   if(rbw_node)
  21.     return rbw_node->payload;
  22.   return NULL;
  23. }

  24. int rbw_insert(rb_root_t *root, rbw_cmp_api cmp, rbw_keyof_api keyof, rbw_node_t* node, void* payload)
  25. {
  26.   rb_node_t** rb_new = &(root->rb_node);
  27.   rb_node_t*  rb_parent = NULL;
  28.   // Figure out where to put new node
  29.   while (*rb_new) {
  30.     rbw_node_t* rbw_node = (void*)container_of(*rb_new, rbw_node_t, rbnode);
  31.     int result = cmp(keyof(payload), (void*)(rbw_node->payload));
  32.     rb_parent = *rb_new;
  33.     if (result < 0)
  34.       rb_new = &((*rb_new)->rb_left);
  35.     else if (result > 0)
  36.       rb_new = &((*rb_new)->rb_right);
  37.     else
  38.       return 0;
  39.   }
  40.   // Add new node and rebalance tree
  41.   node->payload = payload;
  42.   rb_link_node(&node->rbnode, rb_parent, rb_new);
  43.   rb_insert_color(&node->rbnode, root);
  44.   return 1;
  45. }

  46. int rbw_remove(rb_root_t *root, rbw_cmp_api cmp, void* key)
  47. {
  48.   rbw_node_t* rbw_node = _rbw_search_node(root, cmp, key);
  49.   if(rbw_node)
  50.   {
  51.     rb_erase(&rbw_node->rbnode, root);
  52.     return 1;
  53.   }
  54.   return 0;
  55. }
复制代码


rbtree_wrap.h
  1. #ifndef _RBTREE_WRAP_H
  2. #define _RBTREE_WRAP_H

  3. #include "rbtree.h"

  4. #ifndef offsetof
  5. #define offsetof(TYPE, MEMBER) ((size_t)&((TYPE *)0)->MEMBER)
  6. #endif

  7. #ifndef container_of
  8. #define container_of(ptr, type, member) \
  9.    ((type *)((char *)(ptr) - offsetof(type, member)))
  10. #endif

  11. typedef void* (*rbw_keyof_api)(void* payload);
  12. typedef int   (*rbw_cmp_api)  (void* key, void* payload);

  13. typedef struct _rbw_node {
  14.   rb_node_t rbnode;
  15.   void*  payload;
  16. } rbw_node_t;

  17. int   rbw_insert(rb_root_t *root, rbw_cmp_api cmp, rbw_keyof_api keyof, rbw_node_t* node, void* payload);
  18. int   rbw_remove(rb_root_t *root, rbw_cmp_api cmp, void* key);
  19. void* rbw_search(rb_root_t* root, rbw_cmp_api cmp, void* key);

  20. #endif
复制代码


如何使用:
比如用户有一组数据,定义如下
  1. typedef struct userdata
  2. {
  3.   char* name;
  4.   int id;
  5. } userdata_t;

  6. userdata_t userdata[] = {
  7.   (userdata_t){"Start",    1},
  8.   (userdata_t){"Felix",    5},
  9.   (userdata_t){"Batou",   3},
  10.   (userdata_t){"Maximum", 63},
  11.   (userdata_t){"Aramaki",   4},
  12.   (userdata_t){"Motoko",     2},
  13.   (userdata_t){"Togusa",   11},
  14. };
复制代码


用户代码需要针对userdata建立红黑树,则仅需要提供:
(1)红黑树根节点,以及额外的红黑树节点存储空间;
  1. #define USERDATA_SZ sizeof(userdata)/sizeof(userdata_t )

  2. rbw_node_t rbt_nodes[USERDATA_SZ ];
  3. 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. int cmp_name (void* key, void* payload)
  9. {
  10.   return strcmp((char*)key, (char*)keyof_name(payload));
  11. }
复制代码


当以结构体的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. int cmp_id (void* key, void* payload)
  9. {
  10.   return *(int*)key - *(int*)keyof_id(payload);
  11. }
复制代码



树的建立过程:
  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结构体没有一点变化。
这个特性对于某些协同开发,或者上游固定不能更改的环境是有利的。

出200入1068汤圆

 楼主| 发表于 2019-8-27 21:57:11 | 显示全部楼层
本帖最后由 dukelec 于 2019-8-27 22:04 编辑
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. struct rb_node *rbw_search(rb_root *root, rbw_cmp_f cmp, void *key);
  5. int rbw_insert(rb_root *root, rbw_cmp_f cmp, struct rb_node *new);
复制代码

出0入0汤圆

发表于 2019-8-27 22:07:15 | 显示全部楼层
本帖最后由 fnems 于 2019-8-27 22:12 编辑
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);
复制代码


班门弄斧,让大神见笑啦~

出0入0汤圆

发表于 2019-8-27 22:35:52 | 显示全部楼层
个人感觉在单片机上引入红黑树简直是小题大做,能否激发她的性能有待观察

出200入1068汤圆

 楼主| 发表于 2019-8-27 22:36:06 | 显示全部楼层
本帖最后由 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 内核普遍是这样操作。

出0入0汤圆

发表于 2019-8-27 22:47:32 | 显示全部楼层
哈哈哈,红黑树知识点,记录下

出0入0汤圆

发表于 2019-8-27 23:01:08 | 显示全部楼层
本帖最后由 fnems 于 2019-8-27 23:27 编辑
dukelec 发表于 2019-8-27 22:36
这个你可以按照自己的意愿来操作。

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

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

出0入0汤圆

发表于 2019-8-27 23:09:51 | 显示全部楼层
haffman1 发表于 2019-8-27 22:35
个人感觉在单片机上引入红黑树简直是小题大做,能否激发她的性能有待观察 ...

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

出0入0汤圆

发表于 2019-8-27 23:27:59 | 显示全部楼层
本帖最后由 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。不过我又不想改这个红黑树源码,所以才封装的 [手动笑哭表情]

出200入1068汤圆

 楼主| 发表于 2019-8-28 00:47:02 | 显示全部楼层
本帖最后由 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 函数,效率也高一些。

出0入0汤圆

发表于 2019-8-28 13:36:09 | 显示全部楼层
收藏了,虽然我看不懂,

出0入0汤圆

发表于 2019-11-25 11:59:11 | 显示全部楼层
学习了,项目中暂时还没找到适合的场景。

出0入0汤圆

发表于 2020-7-25 12:15:27 | 显示全部楼层
不错不错 .

出0入4汤圆

发表于 2020-8-13 19:25:45 | 显示全部楼层
膜拜一下

出100入101汤圆

发表于 2020-9-17 08:39:54 | 显示全部楼层
不明觉厉,收藏

出0入0汤圆

发表于 2021-3-5 17:05:15 | 显示全部楼层
linux进程调试的精髓。

出0入0汤圆

发表于 2021-3-16 15:00:54 | 显示全部楼层
大佬,
虽然看不懂,先收藏

出0入42汤圆

发表于 2021-12-14 22:16:31 | 显示全部楼层
楼主有个问题请教一下,代码开始的这句“rb_root_t cdnet_sockets = RB_ROOT; // 初始化 rbtree 的根”, 是创建了红黑树的根节点吗?那用户定义的结构体 cdnet_socket_t ,也需要定义一个根变量 cdnet_socket_t g_cdnet_state 和 红黑树根节点cdnet_sockets关联起来吗,这个怎么关联呢?

出80入34汤圆

发表于 2021-12-14 22:49:37 | 显示全部楼层
可以,c++的map,python的dict,就是一个带索引的数组,可以当作迷你数据库用,比如存储姓名+学号,输入姓名返回学号,查找速度比遍历查找快。

出200入1068汤圆

 楼主| 发表于 2021-12-14 23:33:33 | 显示全部楼层
我是一个大白菜 发表于 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 查找更多相關資料

出0入42汤圆

发表于 2021-12-15 09:23:59 | 显示全部楼层
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. 初始化好了,后面就是调用使用了。
不用再考虑用户结构体创建一个根变量的问题了。

出200入1068汤圆

 楼主| 发表于 2021-12-15 09:43:23 来自手机 | 显示全部楼层
我是一个大白菜 发表于 2021-12-15 09:23
非常感谢您的指导。我这么理解您看对不对,我要使用这个红黑树的时候,1.定义好我自己的用户数据结构体包 ...

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

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

出0入42汤圆

发表于 2021-12-15 10:13:24 | 显示全部楼层
dukelec 发表于 2021-12-15 09:43
是的,之前的這個 cdnet socket 只有一個 根,所以寫死在 socket 操作的函數裡面了。

新的代碼,我增加 ...

好的,非常感谢
回帖提示: 反政府言论将被立即封锁ID 在按“提交”前,请自问一下:我这样表达会给举报吗,会给自己惹麻烦吗? 另外:尽量不要使用Mark、顶等没有意义的回复。不得大量使用大字体和彩色字。
您需要登录后才可以回帖 登录 | 注册

本版积分规则

手机版|Archiver|amobbs.com 阿莫电子论坛 ( 公安交互式论坛备案:44190002001997 粤ICP备09047143号 )

GMT+8, 2022-7-3 09:51

© Since 2004 www.amobbs.com, 原www.ourdev.cn, 原www.ouravr.com

快速回复 返回顶部 返回列表