主要移植了內核中的 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 介紹

Linux中的鏈表用法與一般數據結構書中介紹的用法有些不一樣。

Linux內核中，為了保證鏈表的通用性，將鏈表的節點結構單獨抽取了出來，也就是將鏈表的結構和鏈表的數據分開定義。

一般數據結構的書中介紹到的鏈表都是將鏈表的數據和鏈表的結構一起定義的。

注：具體介紹可以我之前的博客參見：http://www.CUOXin.com/wang_yb/archive/2013/04/16/3023892.html 中的 1.2節

里面很重要的一點就是：鏈表結構和數據分開后，是如何通過鏈表節點結構來獲取數據的？

帶有safe的函數或者宏都是可以用于多線程的

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進行測試時無法編譯

構造如下場景，用來測試上述列出的所有的 list 操作：

1. 構造用來測試的 struct：（為了使得測試結果一目了然，struct盡量簡單）

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

2. 逐個函數進行測試，使用測試框架 cppUTest

3. 宏 相關的暫時沒有測試

4. 運行測試非常簡單（前提是得安裝 cpputest）

make./test_list -v

紅黑樹是一種自平衡的二叉搜索樹。紅黑樹是有序的。

注: 具體介紹可以我之前的博客參見：http://www.CUOXin.com/wang_yb/archive/2013/04/16/3023892.html 中的 第4節

這里只補充一點，紅黑樹雖然有些復雜，但是它的查找，插入，刪除操作的效率還不錯。查找，插入，刪除的時間復雜度都是O(log n) n是樹中元素數目

為了是 rbtree 更加簡單，暫時刪除了以下內容：

1. 刪除了函數指針的定義 typedef rb_augment_f
2. 刪除了 rb_augment_insert
3. 刪除了 rb_augment_erase_begin
4. 刪除了 rb_augment_erase_end
5. 刪除了 rb_link_node

注意： rbtree 的對外接口中沒有插入node的接口，只有在插入node之后改變node顏色的接口

可能是由于node的順序因具體struct而異，所以沒法統一實現

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/紅黑樹

構造如下場景，用來測試上述列出的所有的 rbtree 操作：

1. 構造用來測試的 struct：（為了使得測試結果一目了然，struct盡量簡單）

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

2. 逐個函數進行測試，使用測試框架 cppUTest

3. 宏 相關的暫時沒有測試

4. 運行測試非常簡單（前提是得安裝 cpputest）

make./test_rbtree -v

相關測試代碼下載