主要移植了內(nèi)核中的 list，rbtree。使得這2個(gè)數(shù)據(jù)結(jié)構(gòu)在用戶(hù)態(tài)程序中也能使用。

同時(shí)用 cpputest 對(duì)移植后的代碼進(jìn)行了測(cè)試。（測(cè)試代碼其實(shí)也是使用這2個(gè)數(shù)據(jù)結(jié)構(gòu)的方法）

內(nèi)核代碼的如下文件：(內(nèi)核版本 v3.2 debian 7.5源碼)

1. include/linux/list.h (刪除了 hlist 相關(guān)內(nèi)容)
2. include/linux/rbtree.h
3. lib/rbtree.c

對(duì)上面的代碼進(jìn)行了一些簡(jiǎn)化，只留了常用的函數(shù)。同時(shí)刪除了其中和內(nèi)核相關(guān)的部分。

主要內(nèi)容：

• list 介紹 （循環(huán)雙向鏈表）
• rbtree 介紹

Linux中的鏈表用法與一般數(shù)據(jù)結(jié)構(gòu)書(shū)中介紹的用法有些不一樣。

Linux內(nèi)核中，為了保證鏈表的通用性，將鏈表的節(jié)點(diǎn)結(jié)構(gòu)單獨(dú)抽取了出來(lái)，也就是將鏈表的結(jié)構(gòu)和鏈表的數(shù)據(jù)分開(kāi)定義。

一般數(shù)據(jù)結(jié)構(gòu)的書(shū)中介紹到的鏈表都是將鏈表的數(shù)據(jù)和鏈表的結(jié)構(gòu)一起定義的。

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

里面很重要的一點(diǎn)就是：鏈表結(jié)構(gòu)和數(shù)據(jù)分開(kāi)后，是如何通過(guò)鏈表節(jié)點(diǎn)結(jié)構(gòu)來(lái)獲取數(shù)據(jù)的？

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

1. 刪除了hlist相關(guān)內(nèi)容
2. 修改了 list_del 函數(shù): 將 LIST_POISON1 和 LIST_POISON2 改成了 NULL
3. 刪除了 list_empty_careful: 用戶(hù)空間用不上
4. 刪除 __list_for_each: 和 list_for_each 重復(fù)
5. 刪除 list_PRepare_entry: 暫時(shí)不需要
6. 刪除 list_safe_reset_next: 暫時(shí)不需要
7. 刪除 list_rotate_left: 暫時(shí)不需要
8. 所有變量 new 改為了 newnode: new 是 c++ 關(guān)鍵字，用CppUTest進(jìn)行測(cè)試時(shí)無(wú)法編譯

構(gòu)造如下場(chǎng)景，用來(lái)測(cè)試上述列出的所有的 list 操作：

1. 構(gòu)造用來(lái)測(cè)試的 struct：（為了使得測(cè)試結(jié)果一目了然，struct盡量簡(jiǎn)單）

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

2. 逐個(gè)函數(shù)進(jìn)行測(cè)試，使用測(cè)試框架 cppUTest

3. 宏 相關(guān)的暫時(shí)沒(méi)有測(cè)試

4. 運(yùn)行測(cè)試非常簡(jiǎn)單（前提是得安裝 cpputest）

make./test_list -v

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

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

這里只補(bǔ)充一點(diǎn)，紅黑樹(shù)雖然有些復(fù)雜，但是它的查找，插入，刪除操作的效率還不錯(cuò)。查找，插入，刪除的時(shí)間復(fù)雜度都是O(log n) n是樹(shù)中元素?cái)?shù)目

為了是 rbtree 更加簡(jiǎn)單，暫時(shí)刪除了以下內(nèi)容：

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

注意： rbtree 的對(duì)外接口中沒(méi)有插入node的接口，只有在插入node之后改變node顏色的接口

可能是由于node的順序因具體struct而異，所以沒(méi)法統(tǒng)一實(shí)現(xiàn)

rbtree.c 中函數(shù)都比較簡(jiǎn)單，比較復(fù)雜的是 rb_insert_color 和 rb_erase

這2個(gè)函數(shù)還涉及其它未公開(kāi)的函數(shù) __rb_rotate_left, __rb_rotate_right, __rb_erase_color

1. __rb_rotate_left : 左旋，即，以參數(shù) node 為中心點(diǎn)，逆時(shí)針旋轉(zhuǎn)。左旋可以調(diào)整右子樹(shù)的高度

下面的4副圖演示了左旋時(shí)，struct rb_node 的 left 和 right 指針的變化。

下圖是最復(fù)雜的一種情況，即所有相關(guān)節(jié)點(diǎn)的左右子樹(shù)不為空的情況

2. __rb_rotate_right : 右旋，即，以參數(shù) node 為中心點(diǎn)，順時(shí)針旋轉(zhuǎn)。右旋可以調(diào)整左子樹(shù)的高度

下面的4副圖演示了右旋時(shí)，struct rb_node 的 left 和 right 指針的變化。

下圖是最復(fù)雜的一種情況，即所有相關(guān)節(jié)點(diǎn)的左右子樹(shù)不為空的情況

3. rb_erase : 刪除節(jié)點(diǎn)，調(diào)用 __rb_erase_color 調(diào)整顏色

下圖演示刪除節(jié)點(diǎn)時(shí)，struct rb_node 的 left 和 right 指針的變化。

下圖是最復(fù)雜的一種情況，即所有相關(guān)節(jié)點(diǎn)的左右子樹(shù)不為空的情況

4. __rb_erase_color : 刪除節(jié)點(diǎn)后，調(diào)整被刪除節(jié)點(diǎn)后節(jié)點(diǎn)的顏色

被刪除節(jié)點(diǎn) A 的位置由被刪除節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn) B（即被刪除節(jié)點(diǎn)的右子樹(shù)中最左的節(jié)點(diǎn)）替換。

調(diào)整的顏色就是 B 節(jié)點(diǎn)的 child 和 parent

刪除時(shí)各種情況的分析參見(jiàn)：http://zh.wikipedia.org/wiki/紅黑樹(shù)

5. rb_insert_color : 設(shè)置新插入節(jié)點(diǎn)的顏色，調(diào)整rbtree的平衡

插入的位置需要自己定義，這個(gè)函數(shù)只是調(diào)整插入后節(jié)點(diǎn)的顏色

插入時(shí)各種情況的分析參見(jiàn)：http://zh.wikipedia.org/wiki/紅黑樹(shù)

構(gòu)造如下場(chǎng)景，用來(lái)測(cè)試上述列出的所有的 rbtree 操作：

1. 構(gòu)造用來(lái)測(cè)試的 struct：（為了使得測(cè)試結(jié)果一目了然，struct盡量簡(jiǎn)單）

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

2. 逐個(gè)函數(shù)進(jìn)行測(cè)試，使用測(cè)試框架 cppUTest

3. 宏 相關(guān)的暫時(shí)沒(méi)有測(cè)試

4. 運(yùn)行測(cè)試非常簡(jiǎn)單（前提是得安裝 cpputest）

make./test_rbtree -v

相關(guān)測(cè)試代碼下載