|
发表于 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
- #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[USERDATA_SZ ];
- rb_root_t rbt_userdata;
复制代码
(2)上述cmp、keyof两个回调函数。
当以结构体的name元素为键排序及检索时,
- #define keyof keyof_name
- #define cmp cmp_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 keyof keyof_id
- #define cmp cmp_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[k], &userdata[k]);
- }
复制代码
树的查找:
- // 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结构体没有一点变化。
这个特性对于某些协同开发,或者上游固定不能更改的环境是有利的。 |
|