主要移植了内核中的 list，rbtree。使得这2个数据结构在用户态程序中也能使用。
同时用 cpputest 对移植后的代码进行了测试。（测试代码其实也是使用这2个数据结构的方法）
内核代码的如下文件：(内核版本 v3.2 debian 7.5源码)
include/linux/list.h (删除了 hlist 相关内容)
include/linux/rbtree.h
lib/rbtree.c
对上面的代码进行了一些简化，只留了常用的函数。同时删除了其中和内核相关的部分。
主要内容：
list 介绍 （循环双向链表）
rbtree 介绍
Linux中的链表用法与一般数据结构书中介绍的用法有些不一样。
Linux内核中，为了保证链表的通用性，将链表的节点结构单独抽取了出来，也就是将链表的结构和链表的数据分开定义。
一般数据结构的书中介绍到的链表都是将链表的数据和链表的结构一起定义的。
里面很重要的一点就是：链表结构和数据分开后，是如何通过链表节点结构来获取数据的？
带有safe的函数或者宏都是可以用于多线程的
删除了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进行测试时无法编译
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
主要 宏
list_entry
获取包含此节点的 struct
list_first_entry
获取包含此节点的 首个 struct
list_for_each
从 head节点之后一个节点开始向后循环
list_for_each_prev
从 head节点之前一个节点开始向前循环
list_for_each_safe
list_for_each 的安全版本, 即, 循环时即使有其它线程删除节点也可正常运行
list_for_each_prev_safe
list_for_each_prev 的安全版本
list_for_each_entry
同 list_for_each, 只是参数不同
list_for_each_entry_reverse
同 list_for_each_prev, 只是参数不同
list_for_each_entry_continue
同 list_for_each_entry, 但不是从头(head)开始循环的
list_for_each_entry_continue_reverse
同 list_for_each_entry_reverse, 但不是从头(head)开始循环的
list_for_each_entry_from
从指定位置开始向后循环
list_for_each_entry_safe
list_for_each_entry 的安全版本
list_for_each_entry_safe_continue
list_for_each_entry_continue 的安全版本
list_for_each_entry_safe_from
list_for_each_entry_from 的安全版本
list_for_each_entry_safe_reverse
list_for_each_entry_reverse 的安全版本
构造如下场景，用来测试上述列出的所有的 list 操作：
1. 构造用来测试的 struct：（为了使得测试结果一目了然，struct尽量简单）
2. 逐个函数进行测试，使用测试框架 cppUTest
3. 宏 相关的暂时没有测试
4. 运行测试非常简单（前提是得安装 cpputest）
红黑树是一种自平衡的二叉搜索树。红黑树是有序的。
这里只补充一点，红黑树虽然有些复杂，但是它的查找，插入，删除操作的效率还不错。查找，插入，删除的时间复杂度都是O(log n) n是树中元素数目
为了是 rbtree 更加简单，暂时删除了以下内容：
删除了函数指针的定义 typedef rb_augment_f
删除了 rb_augment_insert
删除了 rb_augment_erase_begin
删除了 rb_augment_erase_end
删除了 rb_link_node
注意： rbtree 的对外接口中没有插入node的接口，只有在插入node之后改变node颜色的接口
可能是由于node的顺序因具体struct而异，所以没法统一实现
rb_set_parent
设置父节点的地址
rb_set_color
设置节点颜色
rb_init_node
初始化节点
rb_insert_color
设置新插入节点的颜色
rb_erase
删除一个节点
rb_next
返回当前节点的下一个节点
rb_prev
返回当前节点的上一个节点
rb_first
返回第一个叶子节点（也就是最左边的叶子节点）
rb_last
返回最后一个叶子节点（也就是最右边的叶子节点）
rb_replace_node
替换rbtree中的一个node（只是简单的替换，没有管替换的颜色对不对，数据的顺序对不对）
rb_parent
获取父节点的地址
rb_color
节点的颜色
rb_is_red
是否红节点
rb_is_black
是否黑节点
rb_set_red
设置节点为红色
rb_set_black
设置节点为黑色
RB_ROOT
初始化根节点
rb_entry
获取包含rbtree node的struct
RB_EMPTY_ROOT
判断是否只有根节点
RB_EMPTY_NODE
判断节点是否刚初始化，还没有加到树中
RB_CLEAR_NODE
设置节点的父节点也指向自己
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
5. rb_insert_color : 设置新插入节点的颜色，调整rbtree的平衡
插入的位置需要自己定义，这个函数只是调整插入后节点的颜色
构造如下场景，用来测试上述列出的所有的 rbtree 操作：
<a href="http://files.cnblogs.com/wang_yb/kernel-list-rbtree.zip">相关测试代码下载</a>
本文转自wang_yb博客园博客，原文链接：http://www.cnblogs.com/wang_yb/p/3818517.html，如需转载请自行联系原作者