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

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

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

1. include/linux/list.h  (删除了 hlist 相关内容)
2. include/linux/rbtree.h
3. lib/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 修改部分

1. 删除了hlist相关内容
2. 修改了 list_del 函数: 将 LIST_POISON1 和 LIST_POISON2 改成了 NULL
3. 删除了 list_empty_careful: 用户空间用不上
4. 删除 __list_for_each: 和 list_for_each 重复
5. 删除 list_prepare_entry: 暂时不需要
6. 删除 list_safe_reset_next: 暂时不需要
7. 删除 list_rotate_left: 暂时不需要
8. 所有变量 new 改为了 newnode: new 是 c++ 关键字，用CppUTest进行测试时无法编译

1.3 list.h 对外的接口

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 更加简单，暂时删除了以下内容：

1. 删除了函数指针的定义 typedef rb_augment_f
2. 删除了 rb_augment_insert
3. 删除了 rb_augment_erase_begin
4. 删除了 rb_augment_erase_end
5. 删除了 rb_link_node

1.3 rbtree.h 对外接口

注意： rbtree 的对外接口中没有插入node的接口，只有在插入node之后改变node颜色的接口

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

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

相关测试代码下载

本文转自wang_yb博客园博客，原文链接：http://www.cnblogs.com/wang_yb/p/3818517.html，如需转载请自行联系原作者