[系统运维]红黑树(red black tree)在linux中的应用(六)

1. 概览

??红黑树的实现原理还是比较复杂的，本章不打算涉及。下面是内核文档对红黑树的简单介绍。

  Red-black trees are a type of self-balancing binary search tree, used for
storing sortable key/value data pairs.  This differs from radix trees (which
are used to efficiently store sparse arrays and thus use long integer indexes
to insert/access/delete nodes) and hash tables (which are not kept sorted to
be easily traversed in order, and must be tuned for a specific size and
hash function where rbtrees scale gracefully storing arbitrary keys).
  Red-black trees are similar to AVL trees, but provide faster real-time bounded
worst case performance for insertion and deletion (at most two rotations and
three rotations, respectively, to balance the tree), with slightly slower
(but still O(log n)) lookup time.

在内核中几个已应用的场景

• The deadline and CFQ I/O schedulers employ rbtrees to track requests;
• the packet CD/DVD driver;
• The high-resolution timer code uses an rbtree to organize outstanding timer requests;
• The ext3 filesystem tracks directory entries in a red-black tree.
• Virtual memory areas (VMAs) are tracked with red-black trees, as are epoll file descriptors, cryptographic keys, and network packets in the “hierarchical token bucket” scheduler.

2. 红黑树的优势

??对于红黑树的使用者而言，选择它的两个主要原因如下
????a) 可以实现键值对的数据类型，即使用key来查找到其对于的数据。
????b) 查找非常的快，即使数据量成指数级的增长的时候依然很快。其查找的时间复杂度是O(lgx)，下面是lgx的曲线图
??横坐标x代表项目数量，纵坐标y代表所花费的时间，从上图也能清晰的看出，随着横坐标x的增加，纵坐标y增加的其实是很少的。所以红黑树的快是有理论依据的。
??下面是红黑树的示意图

3.在linux中使用示例

??示例程序用于展示树的一些基本操作，例如增删改查。

3.1 树的创建

struct my_map{
	char *name;
	struct rb_root my_root;
};

??使用my_map来代表一棵树，rb_root则是linux中对红黑树根节点的抽象表示，其定义如下

//tools\include\linux\rbtree.h
struct rb_root {
	struct rb_node *rb_node;
};

??对于根下面的所有节点，则使用rb_node对其抽象，其定义如下

//tools\include\linux\rbtree.h
struct rb_node {
	unsigned long  __rb_parent_color;
	struct rb_node *rb_right;
	struct rb_node *rb_left;
} __attribute__((aligned(sizeof(long))));

??使用的时候只需要将rb_node内嵌到我们自定义的数据结构中即可，示例如下

#define BUFFER_MAX_SIZE	20
struct my_data{
	int key;
	u8 buf[BUFFER_MAX_SIZE];
	struct rb_node nodes;
};

??my_data则是示例代码中的自定义数据，其参数说明如下
????key
??????红黑树内部排序的依据，其值唯一。在查找的时候可以依据该值获取到对于的自定义数据。
????buf
??????存储任意数据，由于是示例代码，就初始化为名字即可。
??下面是树根的初始化

static struct my_map *gs_map;
rbtree_test_drv_init
	gs_map->name = "flagstaff's map";
	gs_map->my_root = RB_ROOT;

??命名没什么好说的，在kernel中对根节点的初始化推荐使用宏RB_ROOT，其定义如下

//tools\include\linux\rbtree.h
#define RB_ROOT	(struct rb_root) { NULL, }

??本质就是初始化其内部的rb_node为NULL。

3.2 添加节点到红黑树

??在红黑树中，我们将较小的key值放到左节点，较大的放到右节点。下面是实现代码

static int insert_item_to_mymap(struct rb_root *tree_root, struct my_data *item) {
	struct rb_node **inserted_point = &(tree_root->rb_node);
	struct rb_node *parent = NULL;

	while(*inserted_point) {
		struct my_data *tmp_item = rb_entry(*inserted_point, struct my_data, nodes);
		parent = *inserted_point;

		if(item->key < tmp_item->key)
			inserted_point = &((*inserted_point)->rb_left);
		else if(item->key > tmp_item->key)
			inserted_point = &((*inserted_point)->rb_right);
		else
			return 1;
	}
	rb_link_node(&item->nodes, parent, inserted_point);
	rb_insert_color(&item->nodes, tree_root);
	return 0;
}

??对于第一次插入操作是不会进入循环的，因为根节点被RB_ROOT所初始化了，其rb_node为空。

//tools\include\linux\rbtree.h
#define RB_ROOT	(struct rb_root) { NULL, }

??对于第二次及以后的操作，进循环后，会为新item根据其key值找到合适位置(inserted_point)然后插入，如果这个棵树中存在相同的key值了则返回插入失败。rb_entry用于获取根据rb_node的指针来获取用户自定义项，其内部就是container_of。

//tools\include\linux\rbtree.h
#define	rb_entry(ptr, type, member) container_of(ptr, type, member)

3.2.1 下面是使用代码

用于分配MAP_SIZE_MAX个my_data并初始化，将其插入树gs_map->my_root中。

#define MAP_SIZE_MAX	10
    for( count = 0; count < MAP_SIZE_MAX; ++count) {
        struct my_data *mydata = kzalloc(sizeof(struct my_data),GFP_KERNEL);
        mydata->key = count;
        sprintf(mydata->buf, "my_data_%d", mydata->key);
        insert_item_to_mymap(&gs_map->my_root, mydata)
    }
    ...
    show_my_tree(&gs_map->my_root);

3.2.2 运行结果

[64721.007442] rbtreeTest:rbtree_test_drv_init,133:start tree flagstaff's map
[64721.007449] rbtreeTest:rbtree_test_drv_init,133:[key]0, [buf]my_data_0
[64721.007455] rbtreeTest:rbtree_test_drv_init,133:[key]1, [buf]my_data_1
[64721.007460] rbtreeTest:rbtree_test_drv_init,133:[key]2, [buf]my_data_2
[64721.007467] rbtreeTest:rbtree_test_drv_init,133:[key]3, [buf]my_data_3
[64721.007474] rbtreeTest:rbtree_test_drv_init,133:[key]4, [buf]my_data_4
[64721.007480] rbtreeTest:rbtree_test_drv_init,133:[key]5, [buf]my_data_5
[64721.007487] rbtreeTest:rbtree_test_drv_init,133:[key]6, [buf]my_data_6
[64721.007493] rbtreeTest:rbtree_test_drv_init,133:[key]7, [buf]my_data_7
[64721.007500] rbtreeTest:rbtree_test_drv_init,133:[key]8, [buf]my_data_8
[64721.007506] rbtreeTest:rbtree_test_drv_init,133:[key]9, [buf]my_data_9
[64721.007512] rbtreeTest:rbtree_test_drv_init,133:end tree flagstaff's map

3.3 根据键值(key)从树中获取item

3.3.1 示例代码如下

static struct my_data *get_data(struct rb_root *root, int key) {
	struct rb_node *node = root->rb_node;

	while(node){
		struct my_data *tmp_data = rb_entry(node, struct my_data, nodes);
		if(key < tmp_data->key)
			node = node->rb_left;
		else if(key > tmp_data->key)
			node = node->rb_right;
		else
			return tmp_data;
	}
	return NULL;
}

data = get_data(&gs_map->my_root, MAP_SIZE_MAX/3);
show_one_item(data);

??在书中根据key查找item也是通过key是否对等来判断的，只查找路径个插入的策略是一致的。如果没找到则直接返回NULL

3.3.2 执行结果如下

board:/ # [64721.007433] rbtreeTest:rbtree_test_drv_init,130:[key]3, [buf]my_data_3

3.4 树的遍历

??遍历树红黑树需要用到内核提供的两个接口，rb_first用于返回这棵树的第一个节点，其定义如下

/*
 * This function returns the first node (in sort order) of the tree.
 * lib\rbtree.c
 */
struct rb_node *rb_first(const struct rb_root *root)
{
	struct rb_node	*n;

	n = root->rb_node;
	if (!n)
		return NULL;
	while (n->rb_left)
		n = n->rb_left;
	return n;
}

??另一个接口则是 rb_next，用于返回给定节点的下一个节点，其定义如下

//lib\rbtree.c
struct rb_node *rb_next(const struct rb_node *node)
{
	struct rb_node *parent;
	if (node->rb_right) {
		node = node->rb_right;
		while (node->rb_left)
			node=node->rb_left;
		return (struct rb_node *)node;
	}
	while ((parent = rb_parent(node)) && node == parent->rb_right)
		node = parent;
	return parent;
}

??有了内核提供的两个接口，遍历一棵树就很简单了，代码如下

#define show_one_item(item) \
	if(!IS_ERR_OR_NULL(item)) \
		RBTREE_TEST_INFO("[key]%d, [buf]%s", item->key, item->buf);

#define show_my_tree(root) \
{	struct rb_node *node; \
	struct my_map *map; \
	RBTREE_TEST_INFO("the root is err."); \
	map = container_of(root, struct my_map, my_root); \
	RBTREE_TEST_INFO("start tree %s", map->name); \
	for(node = rb_first(root); node; node = rb_next(node)) \
		show_one_item(rb_entry(node, struct my_data, nodes)); \
}

??使用宏来实现，是为了调试时打印行数准确。

3.5 擦除树中的一个节点

rb_erase(&data->nodes, &gs_map->my_root);
show_my_tree(&gs_map->my_root);
kzfree(data);
data = NULL;

??调用接口rb_erase只是把对于的数据从树中摘下来，但是内存并不会释放掉的，所以要记得释放掉，防止内存泄露。
??执行结果如下

[64721.007519] rbtreeTest:rbtree_test_drv_init,137:start tree flagstaff's map
[64721.007525] rbtreeTest:rbtree_test_drv_init,137:[key]0, [buf]my_data_0
[64721.007531] rbtreeTest:rbtree_test_drv_init,137:[key]1, [buf]my_data_1
[64721.007537] rbtreeTest:rbtree_test_drv_init,137:[key]2, [buf]my_data_2
[64721.007543] rbtreeTest:rbtree_test_drv_init,137:[key]4, [buf]my_data_4
[64721.007549] rbtreeTest:rbtree_test_drv_init,137:[key]5, [buf]my_data_5
[64721.007555] rbtreeTest:rbtree_test_drv_init,137:[key]6, [buf]my_data_6
[64721.007561] rbtreeTest:rbtree_test_drv_init,137:[key]7, [buf]my_data_7
[64721.007567] rbtreeTest:rbtree_test_drv_init,137:[key]8, [buf]my_data_8
[64721.007573] rbtreeTest:rbtree_test_drv_init,137:[key]9, [buf]my_data_9
[64721.007579] rbtreeTest:rbtree_test_drv_init,137:end tree flagstaff's map

??可见对于key值为3的item已经被移除了。

3.6 替换一个树节点

#define REPLACED_KEY	(MAP_SIZE_MAX / 2)
	replace_item = kzalloc(sizeof(struct my_data), GFP_KERNEL);
	if(replace_item != NULL){
		replace_item->key = REPLACED_KEY;
		sprintf(replace_item->buf, "my_data_%d repleaced", REPLACED_KEY);
	}
	data = get_data(&gs_map->my_root, REPLACED_KEY);
	if(data != NULL)
		rb_replace_node(&data->nodes, &replace_item->nodes, &gs_map->my_root);
	kzfree(data);
	data = NULL;
	show_my_tree(&gs_map->my_root);

??代码实现上很简单，创建一个my_data并且初始化其key值为即将要被替换的item的key值，此处的key值一定要保持一致，否则会破坏红黑树的结构。被替换下来的数据也只是从树上被摘下来，并不会释放内存，所以别忘记。
??执行结果如下

[64721.007587] rbtreeTest:rbtree_test_drv_init,151:start tree flagstaff's map
[64721.007592] rbtreeTest:rbtree_test_drv_init,151:[key]0, [buf]my_data_0
[64721.007598] rbtreeTest:rbtree_test_drv_init,151:[key]1, [buf]my_data_1
[64721.007603] rbtreeTest:rbtree_test_drv_init,151:[key]2, [buf]my_data_2
[64721.007609] rbtreeTest:rbtree_test_drv_init,151:[key]4, [buf]my_data_4
[64721.007614] rbtreeTest:rbtree_test_drv_init,151:[key]5, [buf]my_data_5 repleaced
[64721.007620] rbtreeTest:rbtree_test_drv_init,151:[key]6, [buf]my_data_6
[64721.007626] rbtreeTest:rbtree_test_drv_init,151:[key]7, [buf]my_data_7
[64721.007631] rbtreeTest:rbtree_test_drv_init,151:[key]8, [buf]my_data_8
[64721.007636] rbtreeTest:rbtree_test_drv_init,151:[key]9, [buf]my_data_9
[64721.007642] rbtreeTest:rbtree_test_drv_init,151:end tree flagstaff's map

3.7 树占用内存的释放

rbtree_test_drv_exit
 	struct rb_root *root = &gs_map->my_root;
	struct rb_node *node = rb_first(root);
	struct my_data *data;

	//1.release every item
	while(node){
		data = rb_entry(node, struct my_data, nodes);
		RBTREE_TEST_INFO("free the following item --->");
		show_one_item(data);

		rb_erase(node, root);
		node = rb_next(node);
		kzfree(data);
	}

	//2.release rbtree
	if(gs_map != NULL){
		RBTREE_TEST_INFO("free tree %s", gs_map->name);
		kzfree(gs_map);
		gs_map = NULL;
	}   

??在树不再被需要后，则要释放其占用的内存，实现也很简单，再遍历的过程中逐个释放即可。
??执行结果如下

board:/ # rmmod rbtreeTest
[64747.962566] rbtreeTest:rbtree_test_drv_exit,164:free the following item --->
[64747.962597] rbtreeTest:rbtree_test_drv_exit,165:[key]0, [buf]my_data_0
[64747.962615] rbtreeTest:rbtree_test_drv_exit,164:free the following item --->
[64747.962630] rbtreeTest:rbtree_test_drv_exit,165:[key]1, [buf]my_data_1
[64747.962641] rbtreeTest:rbtree_test_drv_exit,164:free the following item --->
[64747.962655] rbtreeTest:rbtree_test_drv_exit,165:[key]2, [buf]my_data_2
[64747.962669] rbtreeTest:rbtree_test_drv_exit,164:free the following item --->
[64747.962684] rbtreeTest:rbtree_test_drv_exit,165:[key]4, [buf]my_data_4
[64747.962696] rbtreeTest:rbtree_test_drv_exit,164:free the following item --->
[64747.962711] rbtreeTest:rbtree_test_drv_exit,165:[key]5, [buf]my_data_5 repleaced
[64747.962723] rbtreeTest:rbtree_test_drv_exit,164:free the following item --->
[64747.962844] rbtreeTest:rbtree_test_drv_exit,165:[key]6, [buf]my_data_6
[64747.962855] rbtreeTest:rbtree_test_drv_exit,164:free the following item --->
[64747.962862] rbtreeTest:rbtree_test_drv_exit,165:[key]7, [buf]my_data_7
[64747.962870] rbtreeTest:rbtree_test_drv_exit,164:free the following item --->
[64747.962876] rbtreeTest:rbtree_test_drv_exit,165:[key]8, [buf]my_data_8
[64747.962882] rbtreeTest:rbtree_test_drv_exit,164:free the following item --->
[64747.962889] rbtreeTest:rbtree_test_drv_exit,165:[key]9, [buf]my_data_9
[64747.962896] rbtreeTest:rbtree_test_drv_exit,174:free tree flagstaff's map

4.完整源码

rbtree

https://gitee.com/solo-king/linux-kernel-base-usage/blob/master/flagstaff/rbtreeTest.c

创作打卡挑战赛

赢取流量/现金/CSDN周边激励大奖