主要移植了核心中的 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，如需轉載請自行聯系原作者