Kernel数据结构移植(list和rbtree)

王朝学院·作者佚名  2016-05-27
窄屏简体版  字體: 小  |  中  |  大  |  超大  

Kernel数据结构移植(list和rbtree)主要移植了内核中的 list,rbtree。使得这2个数据结构在用户态程序中也能使用。

同时用 cpputest 对移植后的代码进行了测试。(测试代码其实也是使用这2个数据结构的方法)

内核代码的如下文件:(内核版本 v3.2 debian 7.5源码)

include/linux/list.h (删除了 hlist 相关内容)include/linux/rbtree.hlib/rbtree.c对上面的代码进行了一些简化,只留了常用的函数。同时删除了其中和内核相关的部分。

主要内容:

list 介绍 (循环双向链表)rbtree 介绍

1. list 介绍 (循环双向链表)1.1 简介Linux中的链表用法与一般数据结构书中介绍的用法有些不一样。

Linux内核中,为了保证链表的通用性,将链表的节点结构单独抽取了出来,也就是将链表的结构和链表的数据分开定义。

一般数据结构的书中介绍到的链表都是将链表的数据和链表的结构一起定义的。

注:具体介绍可以我之前的博客参见:http://www.cnblogs.com/wang_yb/archive/2013/04/16/3023892.html 中的 1.2节

里面很重要的一点就是:链表结构和数据分开后,是如何通过链表节点结构来获取数据的?

带有safe的函数或者宏都是可以用于多线程的

1.2 修改部分删除了hlist相关内容修改了 list_del 函数: 将 LIST_POISON1 和 LIST_POISON2 改成了 NULL删除了 list_empty_careful: 用户空间用不上删除 __list_for_each: 和 list_for_each 重复删除 list_PRepare_entry: 暂时不需要删除 list_safe_reset_next: 暂时不需要删除 list_rotate_left: 暂时不需要所有变量 new 改为了 newnode: new 是 c++ 关键字,用CppUTest进行测试时无法编译

1.3 list.h 对外的接口No.

主要 函数

说明

1.

list_add

在 head 之后追加一个节点

2.

list_add_tail

在 head 之前追加一个节点, 也就是在末尾追加一个节点

3.

list_del

删除一个节点, 并将这个节点的next, prev 置为 NULL

4.

list_del_init

删除一个节点并初始化删除的节点

5.

list_replace

替换一个节点

6.

list_replace_init

替换一个节点, 并初始化被替换的节点

7.

list_move

移动节点到 head 之后

8.

list_move_tail

移动节点到 head 之前

9.

list_is_last

判断节点是否是链表中最后一个

10.

list_empty

判断链表是否为空 (即, 是否只有 head 节点)

11.

list_is_singular

判断链表中是否只有一个节点 (除了 head 之外)

12.

list_cut_position

将1个链表截断为2个链表

13.

list_splice

将2个链表合并为1个链表, @list中的所有节点(不包括list)加入到 head 之后

14.

list_splice_tail

将2个链表合并为1个链表, @list中的所有节点(不包括list)加入到 head 之前

15.

list_splice_init

同 list_splice, 最后会初始化 @list

16.

list_splice_tail_init

同 list_splice_tail, 最后会初始化 @list

No.

主要 宏

说明

1.

list_entry

获取包含此节点的 struct

2.

list_first_entry

获取包含此节点的 首个 struct

3.

list_for_each

从 head节点之后一个节点开始向后循环

4.

list_for_each_prev

从 head节点之前一个节点开始向前循环

5.

list_for_each_safe

list_for_each 的安全版本, 即, 循环时即使有其它线程删除节点也可正常运行

6.

list_for_each_prev_safe

list_for_each_prev 的安全版本

7.

list_for_each_entry

同 list_for_each, 只是参数不同

8.

list_for_each_entry_reverse

同 list_for_each_prev, 只是参数不同

9.

list_for_each_entry_continue

同 list_for_each_entry, 但不是从头(head)开始循环的

10.

list_for_each_entry_continue_reverse

同 list_for_each_entry_reverse, 但不是从头(head)开始循环的

11.

list_for_each_entry_from

从指定位置开始向后循环

12.

list_for_each_entry_safe

list_for_each_entry 的安全版本

13.

list_for_each_entry_safe_continue

list_for_each_entry_continue 的安全版本

14.

list_for_each_entry_safe_from

list_for_each_entry_from 的安全版本

15.

list_for_each_entry_safe_reverse

list_for_each_entry_reverse 的安全版本

1.4 使用示例 - 测试 list.h 中所有的list操作构造如下场景,用来测试上述列出的所有的 list 操作:

1. 构造用来测试的 struct:(为了使得测试结果一目了然,struct尽量简单)

struct test_struct {int num; struct list_head head;};

2. 逐个函数进行测试,使用测试框架 cppUTest

3. 宏 相关的暂时没有测试

4. 运行测试非常简单(前提是得安装 cpputest)

make./test_list -v

2. rbtree 介绍1.1 简介红黑树是一种自平衡的二叉搜索树。红黑树是有序的。

注: 具体介绍可以我之前的博客参见:http://www.cnblogs.com/wang_yb/archive/2013/04/16/3023892.html 中的 第4节

这里只补充一点,红黑树虽然有些复杂,但是它的查找,插入,删除操作的效率还不错。查找,插入,删除的时间复杂度都是O(log n) n是树中元素数目

1.2 修改部分为了是 rbtree 更加简单,暂时删除了以下内容:

删除了函数指针的定义 typedef rb_augment_f删除了 rb_augment_insert删除了 rb_augment_erase_begin删除了 rb_augment_erase_end删除了 rb_link_node

1.3 rbtree.h 对外接口注意: rbtree 的对外接口中没有插入node的接口,只有在插入node之后改变node颜色的接口

可能是由于node的顺序因具体struct而异,所以没法统一实现

No.

主要 函数

说明

1.

rb_set_parent

设置父节点的地址

2.

rb_set_color

设置节点颜色

3.

rb_init_node

初始化节点

4.

rb_insert_color

设置新插入节点的颜色

5.

rb_erase

删除一个节点

6.

rb_next

返回当前节点的下一个节点

7.

rb_prev

返回当前节点的上一个节点

8.

rb_first

返回第一个叶子节点(也就是最左边的叶子节点)

9.

rb_last

返回最后一个叶子节点(也就是最右边的叶子节点)

10.

rb_replace_node

替换rbtree中的一个node(只是简单的替换,没有管替换的颜色对不对,数据的顺序对不对)

No.

主要 宏

说明

1.

rb_parent

获取父节点的地址

2.

rb_color

节点的颜色

3.

rb_is_red

是否红节点

4.

rb_is_black

是否黑节点

5.

rb_set_red

设置节点为红色

6.

rb_set_black

设置节点为黑色

7.

RB_ROOT

初始化根节点

8.

rb_entry

获取包含rbtree node的struct

9.

RB_EMPTY_ROOT

判断是否只有根节点

10.

RB_EMPTY_NODE

判断节点是否刚初始化,还没有加到树中

11.

RB_CLEAR_NODE

设置节点的父节点也指向自己

1.4 rbtree.c 补充说明rbtree.c 中函数都比较简单,比较复杂的是 rb_insert_color 和 rb_erase

这2个函数还涉及其它未公开的函数 __rb_rotate_left, __rb_rotate_right, __rb_erase_color

1. __rb_rotate_left : 左旋,即,以参数 node 为中心点,逆时针旋转。左旋可以调整右子树的高度

下面的4副图演示了左旋时,struct rb_node 的 left 和 right 指针的变化。

下图是最复杂的一种情况,即所有相关节点的左右子树不为空的情况

2. __rb_rotate_right : 右旋,即,以参数 node 为中心点,顺时针旋转。右旋可以调整左子树的高度

下面的4副图演示了右旋时,struct rb_node 的 left 和 right 指针的变化。

下图是最复杂的一种情况,即所有相关节点的左右子树不为空的情况

3. rb_erase : 删除节点,调用 __rb_erase_color 调整颜色

下图演示删除节点时,struct rb_node 的 left 和 right 指针的变化。

下图是最复杂的一种情况,即所有相关节点的左右子树不为空的情况

4. __rb_erase_color : 删除节点后,调整被删除节点后节点的颜色

被删除节点 A 的位置由被删除节点的下一个节点 B(即被删除节点的右子树中最左的节点)替换。

调整的颜色就是 B 节点的 child 和 parent

删除时各种情况的分析参见:http://zh.wikipedia.org/wiki/红黑树

5. rb_insert_color : 设置新插入节点的颜色,调整rbtree的平衡

插入的位置需要自己定义,这个函数只是调整插入后节点的颜色

插入时各种情况的分析参见:http://zh.wikipedia.org/wiki/红黑树

1.5 使用示例构造如下场景,用来测试上述列出的所有的 rbtree 操作:

1. 构造用来测试的 struct:(为了使得测试结果一目了然,struct尽量简单)

struct test_struct { int num; struct rb_node node;};

2. 逐个函数进行测试,使用测试框架 cppUTest

3. 宏 相关的暂时没有测试

4. 运行测试非常简单(前提是得安装 cpputest)

make./test_rbtree -v

相关测试代码下载

 
 
免责声明:本文为网络用户发布,其观点仅代表作者个人观点,与本站无关,本站仅提供信息存储服务。文中陈述内容未经本站证实,其真实性、完整性、及时性本站不作任何保证或承诺,请读者仅作参考,并请自行核实相关内容。
 
© 2005- 王朝網路 版權所有 導航