1.设计数据结构
SylixOS内核中提供了简单的红黑树的操作，是裁剪自Linux的红黑树的代码。
1.1 定义红黑树root结点
通过LW_TREE_RB_ROOT定义一个root结点：
struct xxx_device {
/*
* some other members
*/
LW_TREE_RB_ROOT rb_root;
};
1.2 定义红黑树普通结点
通过LW_TREE_RB_NODE定义一个红黑树普通结点：
struct xxx_object {
/*
* some other members
*/
struct xxx_device *dev;
int size;
LW_TREE_RB_NODE rb_node;
};
2. 使用插入和删除
2.1 初始化红黑树root结点
初始化root结点很简单，直接赋值为0即可：
void xxx_device_init (struct xxx_device *device)
{
#define RB_ROOT (LW_TREE_RB_ROOT) { NULL, }
device->rb_root = RB_ROOT;
}
2.2 数据插入红黑树
不像BSD提供了插入红黑树的宏，Linux下插入红黑树得自己根据规则操作结点：
void xxx_object_insert_rb(struct xxx_object *obj)
{
struct xxx_device *dev = obj->dev;
LW_TREE_RB_NODE **iter = &dev->rb_root.TRBR_ptrbnNode;
LW_TREE_RB_NODE *parent = NULL;
struct xxx_object *iter_node;
while (*iter) {
parent = *iter;
iter_node = _TREE_ENTRY(*iter, struct xxx_object, rb_node);
//如果小，往左节点操作
if (obj->size < iter_node->size)
iter = _tree_rb_get_left_addr(*iter);
//如果大，往右节点操作
else if (obj->size > iter_node->size)
iter = _tree_rb_get_right_addr(*iter);
else
return;
}
_tree_rb_link_node(&obj->rb_node, parent, iter);
_Tree_Rb_Insert_Color(&obj->rb_node, &dev->rb_root);
}
其实这些步骤跟BSD中是差不多的，只不过BSD封装了一个宏给使用者，Linux下就比较苦逼了，啥都得自己干。
2.3 数据从红黑树中删除
使用_Tree_Rb_Erase函数实现这一功能：
void xxx_object_remove_rb(struct xxx_object *obj)
{
struct xxx_device *dev = obj->dev;
_Tree_Rb_Erase(&obj->rb_node, &dev->rb_root);
}
3. 查找数据
查找数据的逻辑是和BSD一样的：
struct xxx_object *xxx_object_lookup_rb (struct xxx_device *device, int size)
{
int cur_size;
LW_TREE_RB_NODE *iter;
struct xxx_object *node;
struct xxx_object *best = NULL;
iter = device->rb_root.TRBR_ptrbnNode;
while (iter) {
node = _TREE_ENTRY(iter, struct xxx_object, rb_node);
cur_size = node->size;
//如果要找的比当前的大，则搜索右节点
if (size > cur_size) {
iter = _tree_rb_get_right(iter);
//如果要找的比当前的小，则搜索左节点
} else if (size < cur_size) {
iter = _tree_rb_get_left(iter);
//如果大小相等，则表示找到
} else {
best = node;
break;
}
}
return best;
}
4. Linux红黑树示例
注意：使用Linux风格的红黑树，需要包含如下头文件：
#define __SYLIXOS_KERNEL #include <SylixOS.h> #include <kernel/tree/tree.h>
main.c代码和之前一样，运行结果如下：
obj[0] found, obj->size = 10 obj[1] found, obj->size = 20 obj[2] found, obj->size = 30 obj[3] found, obj->size = 40 obj[4] found, obj->size = 50 obj[5] found, obj->size = 60 obj[6] found, obj->size = 70 obj[7] found, obj->size = 80 obj[8] found, obj->size = 90 obj[9] found, obj->size = 100 obj[5] not found.
附源码：
linux_rbtree_test.c:
#include "linux_rbtree_test.h"
void xxx_device_init (struct xxx_device *device)
{
#define RB_ROOT (LW_TREE_RB_ROOT) { NULL, }
device->rb_root = RB_ROOT;
}
void xxx_object_insert_rb(struct xxx_object *obj)
{
struct xxx_device *dev = obj->dev;
LW_TREE_RB_NODE **iter = &dev->rb_root.TRBR_ptrbnNode;
LW_TREE_RB_NODE *parent = NULL;
struct xxx_object *iter_node;
while (*iter) {
parent = *iter;
iter_node = _TREE_ENTRY(*iter, struct xxx_object, rb_node);
//如果小，往左节点操作
if (obj->size < iter_node->size)
iter = _tree_rb_get_left_addr(*iter);
//如果大，往右节点操作
else if (obj->size > iter_node->size)
iter = _tree_rb_get_right_addr(*iter);
else
return;
}
_tree_rb_link_node(&obj->rb_node, parent, iter);
_Tree_Rb_Insert_Color(&obj->rb_node, &dev->rb_root);
}
void xxx_object_remove_rb(struct xxx_object *obj)
{
struct xxx_device *dev = obj->dev;
_Tree_Rb_Erase(&obj->rb_node, &dev->rb_root);
}
struct xxx_object *xxx_object_lookup_rb (struct xxx_device *device, int size)
{
int cur_size;
LW_TREE_RB_NODE *iter;
struct xxx_object *node;
struct xxx_object *best = NULL;
iter = device->rb_root.TRBR_ptrbnNode;
while (iter) {
node = _TREE_ENTRY(iter, struct xxx_object, rb_node);
cur_size = node->size;
//如果要找的比当前的大，则搜索右节点
if (size > cur_size) {
iter = _tree_rb_get_right(iter);
//如果要找的比当前的小，则搜索左节点
} else if (size < cur_size) {
iter = _tree_rb_get_left(iter);
//如果大小相等，则表示找到
} else {
best = node;
break;
}
}
return best;
}
linux_rbtree_test.h:
/*
* linux_rbtree_test.h
*
* Created on: Jun 28, 2019
* Author: databus
*/
#ifndef SRC_LINUX_RBTREE_TEST_H_
#define SRC_LINUX_RBTREE_TEST_H_
#define __SYLIXOS_KERNEL
#include <SylixOS.h>
#include <kernel/tree/tree.h>
struct xxx_object {
/*
* some other members
*/
struct xxx_device *dev;
int size;
LW_TREE_RB_NODE rb_node;
};
struct xxx_device {
/*
* some other members
*/
LW_TREE_RB_ROOT rb_root;
};
void xxx_device_init (struct xxx_device *device);
void xxx_object_insert_rb(struct xxx_object *obj);
void xxx_object_remove_rb(struct xxx_object *obj);
struct xxx_object *xxx_object_lookup_rb (struct xxx_device *device,int size);
#endif /* SRC_LINUX_RBTREE_TEST_H_ */
main.c:
/*
* main.c
*
* Created on: Jun 28, 2019
* Author: databus
*/
#include <stdio.h>
#include "linux_rbtree_test.h"
#define OBJ_NUM 10
#define INDEX_TO_SIZE(i) (10 * ((i) + 1))
void xxx_obj_init (struct xxx_device *dev, struct xxx_object *obj, int index)
{
obj->dev = dev;
obj->size = INDEX_TO_SIZE(index);
}
int main (int argc, char **argv)
{
struct xxx_device device;
struct xxx_object obj[OBJ_NUM];
struct xxx_object *lookup_obj = NULL;
int i;
xxx_device_init(&device);
for (i = 0; i < OBJ_NUM; i++) {
xxx_obj_init(&device, &obj[i], i);
xxx_object_insert_rb(&obj[i]);
}
for (i = 0; i < OBJ_NUM; i++) {
lookup_obj = xxx_object_lookup_rb(&device, INDEX_TO_SIZE(i));
if (lookup_obj) {
printf("obj[%d] found, obj->size = %d\n", i, lookup_obj->size);
} else {
printf("obj[%d] not found.\n", i);
}
lookup_obj = NULL;
}
xxx_object_remove_rb(&obj[OBJ_NUM / 2]);
lookup_obj = xxx_object_lookup_rb(&device, INDEX_TO_SIZE(OBJ_NUM / 2));
if (lookup_obj) {
printf("obj[%d] found, obj->size = %d\n", OBJ_NUM / 2, lookup_obj->size);
} else {
printf("obj[%d] not found.\n", OBJ_NUM / 2);
}
return (0);
}
评论