SylixOS之Linux红黑树

gewenbin
gewenbin
gewenbin
188
文章
15
评论
2020年12月26日12:43:21 评论 574

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);
}
gewenbin
  • 本文由 发表于 2020年12月26日12:43:21
  • 转载请务必保留本文链接:http://www.databusworld.cn/9761.html
匿名

发表评论

匿名网友 填写信息

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: