正如你所知道的，Linux內(nèi)核提供了許多不同的庫(kù)和函數(shù)，它們實(shí)現(xiàn)了不同的數(shù)據(jù)結(jié)構(gòu)和算法。在這部分，我們將研究其中一種數(shù)據(jù)結(jié)構(gòu)——基數(shù)樹(shù)Radix tree。在 Linux 內(nèi)核中，有兩個(gè)文件與基數(shù)樹(shù)的實(shí)現(xiàn)和API相關(guān)：

include/linux/radix-tree.h

lib/radix-tree.c

讓我們先說(shuō)說(shuō)什么是 基數(shù)樹(shù) 吧。基數(shù)樹(shù)是一種?壓縮的字典樹(shù)compressed trie?，而字典樹(shù)是實(shí)現(xiàn)了關(guān)聯(lián)數(shù)組接口并允許以 鍵值對(duì) 方式存儲(chǔ)值的一種數(shù)據(jù)結(jié)構(gòu)。這里的鍵通常是字符串，但可以使用任意數(shù)據(jù)類型。字典樹(shù)因?yàn)樗墓?jié)點(diǎn)而與 n叉樹(shù) 不同。字典樹(shù)的節(jié)點(diǎn)不存儲(chǔ)鍵，而是存儲(chǔ)單個(gè)字符的標(biāo)簽。與一個(gè)給定節(jié)點(diǎn)關(guān)聯(lián)的鍵可以通過(guò)從根遍歷到該節(jié)點(diǎn)獲得。舉個(gè)例子：

+-----------+

| |

| " " |

| |

+------+-----------+------+

| |

| |

+----v------+ +-----v-----+

| | | |

| g | | c |

| | | |

+-----------+ +-----------+

| |

| |

+----v------+ +-----v-----+

| | | |

| o | | a |

| | | |

+-----------+ +-----------+

|

|

+-----v-----+

| |

| t |

| |

+-----------+

因此在這個(gè)例子中，我們可以看到一個(gè)有著兩個(gè)鍵 go 和 cat 的 字典樹(shù) 。壓縮的字典樹(shù)也叫做 基數(shù)樹(shù) ，它和 字典樹(shù) 的不同之處在于，所有只有一個(gè)子節(jié)點(diǎn)的中間節(jié)點(diǎn)都被刪除。

Linux 內(nèi)核中的基數(shù)樹(shù)是把值映射到整形鍵的一種數(shù)據(jù)結(jié)構(gòu)。include/linux/radix-tree.h文件中的以下結(jié)構(gòu)體描述了基數(shù)樹(shù)：

struct radix_tree_root {

unsigned int height;

gfp_t gfp_mask;

struct radix_tree_node __rcu *rnode;

};

這個(gè)結(jié)構(gòu)體描述了一個(gè)基數(shù)樹(shù)的根，它包含了3個(gè)域成員：

height - 樹(shù)的高度;

gfp_mask - 告知如何執(zhí)行動(dòng)態(tài)內(nèi)存分配;

rnode - 孩子節(jié)點(diǎn)指針.

我們第一個(gè)要討論的字段是 gfp_mask ：

底層內(nèi)核的內(nèi)存動(dòng)態(tài)分配函數(shù)以一組標(biāo)志作為 gfp_mask ，用于描述如何執(zhí)行動(dòng)態(tài)內(nèi)存分配。這些控制分配進(jìn)程的 GFP_ 標(biāo)志擁有以下值：( GF_NOIO 標(biāo)志)意味著睡眠以及等待內(nèi)存，( __GFP_HIGHMEM 標(biāo)志)意味著高端內(nèi)存能夠被使用，( GFP_ATOMIC 標(biāo)志)意味著分配進(jìn)程擁有高優(yōu)先級(jí)并不能睡眠等等。

GFP_NOIO - 睡眠等待內(nèi)存

__GFP_HIGHMEM - 高端內(nèi)存能夠被使用;

GFP_ATOMIC - 分配進(jìn)程擁有高優(yōu)先級(jí)并且不能睡眠;

等等。

下一個(gè)字段是rnode：

struct radix_tree_node {

unsigned int path;

unsigned int count;

union {

struct {

struct radix_tree_node *parent;

void *private_data;

};

struct rcu_head rcu_head;

};

/* For tree user */

struct list_head private_list;

void __rcu *slots[RADIX_TREE_MAP_SIZE];

unsigned long tags[RADIX_TREE_MAX_TAGS][RADIX_TREE_TAG_LONGS];

};

這個(gè)結(jié)構(gòu)體包含的信息有父節(jié)點(diǎn)中的偏移以及到底端(葉節(jié)點(diǎn))的高度、子節(jié)點(diǎn)的個(gè)數(shù)以及用于訪問(wèn)和釋放節(jié)點(diǎn)的字段成員。這些字段成員描述如下：

path - 父節(jié)點(diǎn)中的偏移和到底端(葉節(jié)點(diǎn))的高度

count - 子節(jié)點(diǎn)的個(gè)數(shù);

parent - 父節(jié)點(diǎn)指針;

private_data - 由樹(shù)的用戶使用;

rcu_head - 用于釋放節(jié)點(diǎn);

private_list - 由樹(shù)的用戶使用;

radix_tree_node 的最后兩個(gè)成員—— tags 和 slots 非常重要且令人關(guān)注。Linux 內(nèi)核基數(shù)樹(shù)的每個(gè)節(jié)點(diǎn)都包含了一組指針槽slots，槽里存儲(chǔ)著指向數(shù)據(jù)的指針。在Linux內(nèi)核基數(shù)樹(shù)的實(shí)現(xiàn)中，空槽存儲(chǔ)的是 NULL 。Linux內(nèi)核中的基數(shù)樹(shù)也支持標(biāo)簽tags，它與 radix_tree_node 結(jié)構(gòu)體的 tags 字段相關(guān)聯(lián)。有了標(biāo)簽，我們就可以對(duì)基數(shù)樹(shù)中存儲(chǔ)的記錄以單個(gè)比特位bit進(jìn)行設(shè)置。

既然我們了解了基數(shù)樹(shù)的結(jié)構(gòu)，那么該是時(shí)候看一下它的API了。

Linux內(nèi)核基數(shù)樹(shù)API

我們從結(jié)構(gòu)體的初始化開(kāi)始。有兩種方法初始化一個(gè)新的基數(shù)樹(shù)。第一種是使用 RADIX_TREE 宏：

RADIX_TREE(name, gfp_mask);

正如你所看到的，我們傳遞了 name 參數(shù)，所以通過(guò) RADIX_TREE 宏，我們能夠定義和初始化基數(shù)樹(shù)為給定的名字。RADIX_TREE 的實(shí)現(xiàn)很簡(jiǎn)單：

#define RADIX_TREE(name, mask)

struct radix_tree_root name = RADIX_TREE_INIT(mask)

#define RADIX_TREE_INIT(mask) {

.height = 0,

.gfp_mask = (mask),

.rnode = NULL,

}

在 RADIX_TREE 宏的開(kāi)始，我們使用給定的名字定義 radix_tree_root 結(jié)構(gòu)體實(shí)例，并使用給定的 mask 調(diào)用 RADIX_TREE_INIT 宏。 而 RADIX_TREE_INIT 宏則是使用默認(rèn)值和給定的mask對(duì) radix_tree_root 結(jié)構(gòu)體進(jìn)行了初始化。

第二種方法是手動(dòng)定義radix_tree_root結(jié)構(gòu)體，并且將它和mask傳給 INIT_RADIX_TREE 宏：

struct radix_tree_root my_radix_tree;

INIT_RADIX_TREE(my_tree, gfp_mask_for_my_radix_tree);

INIT_RADIX_TREE 宏的定義如下:

#define INIT_RADIX_TREE(root, mask)

do {

(root)->height = 0;

(root)->gfp_mask = (mask);

(root)->rnode = NULL;

} while (0)

和RADIX_TREE_INIT宏所做的初始化工作一樣，INIT_RADIX_TREE 宏使用默認(rèn)值和給定的 mask 完成初始化工作。

接下來(lái)是用于向基數(shù)樹(shù)插入和刪除數(shù)據(jù)的兩個(gè)函數(shù)：

radix_tree_insert;

radix_tree_delete;

第一個(gè)函數(shù) radix_tree_insert 需要3個(gè)參數(shù)：

基數(shù)樹(shù)的根;

索引鍵;

插入的數(shù)據(jù);

radix_tree_delete 函數(shù)需要和 radix_tree_insert 一樣的一組參數(shù)，但是不需要傳入要?jiǎng)h除的數(shù)據(jù)。

基數(shù)樹(shù)的搜索以兩種方法實(shí)現(xiàn)：

radix_tree_lookup;

radix_tree_gang_lookup;

radix_tree_lookup_slot.

第一個(gè)函數(shù)radix_tree_lookup需要兩個(gè)參數(shù)：

基數(shù)樹(shù)的根;

索引鍵;

這個(gè)函數(shù)嘗試在樹(shù)中查找給定的鍵，并返回和該鍵相關(guān)聯(lián)的記錄。第二個(gè)函數(shù) radix_tree_gang_lookup 有以下的函數(shù)簽名：

unsigned int radix_tree_gang_lookup(struct radix_tree_root *root,

void **results,

unsigned long first_index,

unsigned int max_items);

它返回的是記錄的個(gè)數(shù)。 results 中的結(jié)果，按鍵排序，并從第一個(gè)索引開(kāi)始。返回的記錄個(gè)數(shù)將不會(huì)超過(guò) max_items 的值。

最后一個(gè)函數(shù)radix_tree_lookup_slot將會(huì)返回包含數(shù)據(jù)的指針槽。

?