SylixOS之BSD红黑树

1. 设计数据结构

使用红黑树的主要目的是为了加速查找数据，我们先来看一看使用链表而不是红黑树方式组织数据时该如何设计数据结构。

1.1 平常的链表方式

我们能想到一种很简单的数据结构：

struct xxx_object {
    struct list_head head;
    int key;
}

通过xxx_object中的head成员将各个xxx_object链成链表，查找的时候遍历链表，通过对比key值来找到对应的数据。

1.2 BSD红黑树方式

使用BSD红黑树时一般需要设计两种数据结构，A数据结构需要包含红黑树的根结点，B数据结构需要包含红黑树的普通结点。

1.2.1 定义红黑树root结点

BSD提供了一个RB_HEAD的宏来定义一个root结点，所以我们的A数据结构设计如下：

struct xxx_device {
    /*
     *  some other members
     */

    RB_HEAD(bsd_rb_name, xxx_object) rb_root;
};

RB_HEAD宏有两个成员，解释如下：

• bsd_rb_name：表示红黑树的名字，红黑树插入和删除操作都需要这个名字。
• xxx_object：包含红黑树普通结点的数据结构的类型，也就是B数据结构的类型。

这样xxx_device中的rb_root就表示红黑树的root结点了。

1.2.2 定义红黑树普通结点

BSD提供了一个RB_ENTRY的宏来定义一个普通结点，所以我们的B数据结构设计如下：

struct xxx_object {
    /*
     *  some other members
     */
    struct xxx_device   *dev;
    int                  size;

    RB_ENTRY(xxx_object) rb_node;
};

RB_ENTRY宏只有一个成员，就是B数据结构的类型，xxx_object中的size其实就是查找时用的key。

那么这里有个疑问，如果两个xxx_object的key值一样呢，后插入的xxx_object会覆盖之前插入的吗？实际情况是，如果key值一样，后一个数据根本不会被插入到红黑树中。所以在插入的时候保证每个xxx_object的size都不一样，那么在查找的时候就能找出来。

2. 使用插入和删除

2.1定义插入和删除等函数

BSD提供了一个RB_GENERATE宏用于生成红黑树插入、删除等功能函数，我们可以在c源文件的最开始放置如下代码：

RB_GENERATE(bsd_rb_name, xxx_object, rb_node, xxx_object_cmp_rb_tree_items);

RB_GENERATE宏四个成员的意思如下：

• bsd_rb_name：红黑树的名字。
• xxx_object：包含红黑树普通结点的数据结构类型，也就是B数据结构类型。
• rb_node：在xxx_object中包含的红黑树普通结点成员的名字。
• xxx_object_cmp_rb_tree_items：这是一个红黑树插入时用到的回调函数，用于定义插入时的规则。

xxx_object_cmp_rb_tree_items函数声明如下：

int xxx_object_cmp_rb_tree_items(struct xxx_object *node, struct xxx_object *father_node);

node表示要操作的数据结点，father_node表示被插入的数据结点，当node结点插入到father_node结点后，就形成了父子结点的关系。
  这个回调函数可以返回三种数值，分别如下：

• 返回值<0，表示将node结点和father_node的左结点继续比较。
• 返回值>0，表示将node结点和father_node的右结点继续比较。
• 返回值=0，表示比较结束。

根据这个说明，我们设计如下规则：

• 如果node的size比father_node的size小，返回-1。
• 如果node的size比father_node的size大，返回1。
• 如果node的size和father_node的size相同，返回0。

根据如上的规则，xxx_object_cmp_rb_tree_items的代码如下：

int xxx_object_cmp_rb_tree_items(struct xxx_object *node, struct xxx_object *father_node)
{
    //将小的往左节点操作
    if (node->size < father_node->size) {
        return (-1);
    //将大的往右节点操作
    } else if (node->size > father_node->size) {
        return (1);
    //如果相等则不操作
    } else {
        return (0);
    }
}

这样插入完毕后，对于任意一个结点而言，比结点小的都在左边，比结点大的都在右边。

2.2 初始化红黑树root结点

BSD提供了RB_INIT宏用于初始化root结点，对应的代码如下：

void xxx_device_init (struct xxx_device *device)
{
    RB_INIT(&device->rb_root);
}

这个宏很简单，不做阐述。

2.3 数据插入红黑树

BSD提供了RB_INSERT宏用于将数据插入到红黑树中，对应的代码如下：

void xxx_object_insert_rb(struct xxx_object *obj)
{
    struct xxx_device *dev = obj->dev;

    RB_INSERT(bsd_rb_name, &dev->rb_root, obj);
}

RB_INSERT宏的三个成员说明如下：

• bsd_rb_name：红黑树的名字。
• &dev->rb_root：红黑树root结点地址。
• obj：要插入的包含红黑树普通结点的数据。

2.4 数据从红黑树中删除

BSD提供了RB_REMOVE宏用于将数据从红黑树中删除，对应的代码如下：

void xxx_object_remove_rb(struct xxx_object *obj)
{
    struct xxx_device *dev = obj->dev;

    RB_REMOVE(bsd_rb_name, &dev->rb_root, obj);
}

RB_REMOVE宏的三个成员和RB_INSERT宏的三个成员是一样的。

3. 查找数据

struct xxx_object *xxx_object_lookup_rb (struct xxx_device *device, int size)
{
    int cur_size;
    struct xxx_object *bo;
    struct xxx_object *best_bo = NULL;

    bo = RB_ROOT(&device->rb_root);
    while (bo != NULL) {
        cur_size = bo->size;
        //如果要找的比当前的大，则搜索右节点
        if (size > cur_size) {
            bo = RB_RIGHT(bo, rb_node);
        //如果要找的比当前的小，则搜索左节点
        } else if (size < cur_size) {
            bo = RB_LEFT(bo, rb_node);
        //如果大小相等，则表示找到
        } else {
            best_bo = bo;
            break;
        }
    }

    return best_bo;
}

对于其中的几个宏的说明如下：

RB_ROOT、RB_RIGHT、RB_LEFT这三个宏都是通过红黑树结点来获取到实际的数据。

• RB_ROOT：通过root结点获取到第一个包含红黑树普通结点的数据。
• RB_RIGHT：获取当前结点右子结点的数据。
• RB_LEFT：获取当前结点左子结点的数据。

RB_RIGHT和RB_LEFT宏的两个成员说明如下：

• bo：当前数据地址。
• rb_node：当前数据中包含的红黑树普通结点的成员名字。

可以看出，查找数据的规则是和数据插入时的规则是一一对应的，所以只要定义好插入和查找的规则，就能在红黑树中快速的查找到数据。

4. BSD红黑树示例

注意：使用BSD提供的红黑树，需要包含如下头文件：

#include <sys/tree.h>

main.c文件如下：

#include <stdio.h>
#include "bsd_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);
}

• 每一个object的size的值初始化为10的倍数
• 将所有object插入到红黑树中后，通过size(key)寻找每一个object，并输出查找结果信息
• 在红黑树中删除一个object，然后再查找这个object，输出查找结果信息

该例子的运行结果如下：

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.

5. BSD红黑树查找时间

我们稍微修改下源码，计算下在1000万个数据中寻找某个数据需要的时间。首先看下测试机器的配置：

CPU         : Intel(R) Core(TM) i3-6100 CPU @ 3.70GHz
CPU Family  : x86(R) 32-Bits
CPU Endian  : Little-endian
CPU Cores   : 4
CPU Active  : 4
PWR Level   : Top level
CACHE       : L1 D-CACHE 32KB L1 I-CACHE 32KB L2 U-CACHE 256KB L3 U-CACHE 3MB
PACKET      : Standard PC Compatibles (32-Bits)
BogoMIPS  0 : 7314.00
BogoMIPS  1 : 7380.00
BogoMIPS  2 : 7380.00
BogoMIPS  3 : 7380.00

测试代码如下：

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include "bsd_rbtree_test.h"

#define OBJ_NUM             1000 * 10000
#define INDEX_TO_SIZE(i)    (10 * ((i) + 1))

long cal_time (struct timeval *tv1, struct timeval *tv2)
{
    INT64 time1 = tv1->tv_sec * 1000 * 1000 + tv1->tv_usec;
    INT64 time2 = tv2->tv_sec * 1000 * 1000 + tv2->tv_usec;

    return (long)(time2 - time1);
}

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 timeval tv1, tv2;
    struct xxx_device device;
    struct xxx_object *obj;
    struct xxx_object *lookup_obj = NULL;
    int i, index_lookup;

    xxx_device_init(&device);

    obj = malloc(OBJ_NUM * sizeof(*obj));
    for (i = 0; i < OBJ_NUM; i++) {
        xxx_obj_init(&device, &obj[i], i);
        xxx_object_insert_rb(&obj[i]);
    }

    index_lookup = OBJ_NUM / 2;
    gettimeofday(&tv1, NULL);
    lookup_obj = xxx_object_lookup_rb(&device, INDEX_TO_SIZE(index_lookup));
    gettimeofday(&tv2, NULL);
    if (lookup_obj) {
        printf("obj[%d] found, obj->size = %d\n", index_lookup, lookup_obj->size);
        printf("time use : %ld usec.\n", cal_time(&tv1, &tv2));
    } else {
        printf("obj[%d] not found.\n", i);
    }

    return  (0);
}

运行结果如下：

obj[5000000] found, obj->size = 50000010
time use : 2 usec.

可以看出，在1000万个数据中寻找一个数据只需要2us，这个速度还是很快的。

 

附源码：

bsd_rbtree_test.c:

#include <stdio.h>
#include "bsd_rbtree_test.h"

int xxx_object_cmp_rb_tree_items(struct xxx_object *node, struct xxx_object *father_node);
RB_GENERATE(bsd_rb_name, xxx_object, rb_node, xxx_object_cmp_rb_tree_items);

int xxx_object_cmp_rb_tree_items(struct xxx_object *node, struct xxx_object *father_node)
{
    //将小的往左节点操作
    if (node->size < father_node->size) {
        return (-1);
    //将大的往右节点操作
    } else if (node->size > father_node->size) {
        return (1);
    //如果相等则不操作
    } else {
        return (0);
    }
}

void xxx_device_init (struct xxx_device *device)
{
    RB_INIT(&device->rb_root);
}

void xxx_object_insert_rb(struct xxx_object *obj)
{
    struct xxx_device *dev = obj->dev;

    RB_INSERT(bsd_rb_name, &dev->rb_root, obj);
}

void xxx_object_remove_rb(struct xxx_object *obj)
{
    struct xxx_device *dev = obj->dev;

    RB_REMOVE(bsd_rb_name, &dev->rb_root, obj);
}

struct xxx_object *xxx_object_lookup_rb (struct xxx_device *device, int size)
{
    int cur_size;
    struct xxx_object *bo;
    struct xxx_object *best_bo = NULL;

    bo = RB_ROOT(&device->rb_root);
    while (bo != NULL) {
        cur_size = bo->size;
        //如果要找的比当前的大，则搜索右节点
        if (size > cur_size) {
            bo = RB_RIGHT(bo, rb_node);
        //如果要找的比当前的小，则搜索左节点
        } else if (size < cur_size) {
            bo = RB_LEFT(bo, rb_node);
        //如果大小相等，则表示找到
        } else {
            best_bo = bo;
            break;
        }
    }

    return best_bo;
}

bsd_rbtree_test.h:

/*
 * bsd_rbtree_test.h
 *
 *  Created on: Jun 27, 2019
 *      Author: databus
 */

#ifndef SRC_BSD_RBTREE_TEST_H_
#define SRC_BSD_RBTREE_TEST_H_

#include <sys/tree.h>

struct xxx_device;

struct xxx_object {
    /*
     *  some other members
     */
    struct xxx_device   *dev;
    int                  size;

    RB_ENTRY(xxx_object) rb_node;
};

struct xxx_device {
    /*
     *  some other members
     */

    RB_HEAD(bsd_rb_name, xxx_object) 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_BSD_RBTREE_TEST_H_ */

main.c:

/*
 * main.c
 *
 *  Created on: Jun 28, 2019
 *      Author: databus
 */
#include <stdio.h>
#include "bsd_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);
}