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

include/linux/radix-tree.h

lib/radix-tree.c

首先說(shuō)明一下什么是 radix tree ，Radix tree 是一個(gè) 壓縮 trie， trie 是一種通過(guò)保存關(guān)聯(lián)數(shù)組（associative array）來(lái)提供 關(guān)鍵字-值（key-value） 存儲(chǔ)與查找的數(shù)據(jù)結(jié)構(gòu)。通常關(guān)鍵字是字符串，不過(guò)也可以是其他數(shù)據(jù)類(lèi)型。 Trie 結(jié)構(gòu)的節(jié)點(diǎn)與 n-tree 不同，其節(jié)點(diǎn)中并不存儲(chǔ)關(guān)鍵字，取而代之的是存儲(chǔ)單個(gè)字符標(biāo)簽。關(guān)鍵字查找時(shí)，通過(guò)從樹(shù)的根開(kāi)始遍歷關(guān)鍵字相關(guān)的所有字符標(biāo)簽節(jié)點(diǎn)，直至到達(dá)最終的葉子節(jié)點(diǎn)。下面是個(gè)例子：

+-----------+|||" "| | |+------+-----------+------+||||+----v------++-----v-----+|||||g||c| | | | |+-----------++-----------+||||+----v------++-----v-----+|||||o||a| | | | |+-----------++-----------+||+-----v-----+|||t| | |+-----------+

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

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

||

|" "|

|?????????? |

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

||

||

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

||||

|g||c|

|?????????? |????????????|?????????? |

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

||

||

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

||||

|o||a|

|?????????? |????????????|?????????? |

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

|

|

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

||

|t|

|?????????? |

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

這個(gè)例子中，我們可以看到 trie所存儲(chǔ)的關(guān)鍵字信息 go 與 cat，壓縮 trie 或 radix tree 與 trie 所不同的是，對(duì)于只有一個(gè)孩子的中間節(jié)點(diǎn)將被壓縮。

Linux 內(nèi)核中的 Radix 樹(shù)將值映射為整型關(guān)鍵字，Radix 的數(shù)據(jù)結(jié)構(gòu)定義在 include/linux/radix-tree.h 文件中 :

C

struct radix_tree_root { unsigned int height; gfp_t gfp_mask; struct radix_tree_node __rcu *rnode;};

1

2

3

4

5

struct radix_tree_root {

unsigned int????????????height;

gfp_t?????????????????? gfp_mask;

struct radix_tree_node??__rcu *rnode;

};

上面這個(gè)是 radix 樹(shù)的 root 節(jié)點(diǎn)的結(jié)構(gòu)體，它包括三個(gè)成員：

height：從葉節(jié)點(diǎn)向上計(jì)算出的樹(shù)高度。

gfp_mask：內(nèi)存申請(qǐng)的標(biāo)識(shí)。

rnode：子節(jié)點(diǎn)指針。

這里首先要討論的結(jié)構(gòu)體成員是 gfp_mask :

Linux 底層的內(nèi)存申請(qǐng)接口需要提供一類(lèi)標(biāo)識(shí)（flag） – gfp_mask ，用于描述內(nèi)存申請(qǐng)的行為。這個(gè)以 GFP_ 前綴開(kāi)頭的內(nèi)存申請(qǐng)控制標(biāo)識(shí)主要包括，GFP_NOIO 禁止所有 IO 操作但允許睡眠等待內(nèi)存，__GFP_HIGHMEM 允許申請(qǐng)內(nèi)核的高端內(nèi)存，GFP_ATOMIC 高優(yōu)先級(jí)申請(qǐng)內(nèi)存且操作不允許被睡眠。

接下來(lái)說(shuō)的節(jié)結(jié)構(gòu)體成員是rnode：

C

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];};

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

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)體中包括這幾個(gè)內(nèi)容，節(jié)點(diǎn)與父節(jié)點(diǎn)的偏移以及到樹(shù)底端的高度、子節(jié)點(diǎn)的個(gè)數(shù)、節(jié)點(diǎn)的存儲(chǔ)數(shù)據(jù)域，具體描述如下：

path：與父節(jié)點(diǎn)的偏移以及到樹(shù)底端的高度

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

parent：父節(jié)點(diǎn)的指針。

private_data：存儲(chǔ)數(shù)據(jù)內(nèi)容緩沖區(qū)。

rcu_head：用于節(jié)點(diǎn)釋放的 RCU 鏈表。

private_list – 存儲(chǔ)數(shù)據(jù)。

結(jié)構(gòu)體 radix_tree_node 的最后兩個(gè)成員 tags 與 slots 是非常重要且需要特別注意的。每個(gè) Radix 樹(shù)節(jié)點(diǎn)都可以包括一個(gè)指向存儲(chǔ)數(shù)據(jù)指針的 slots 集合，空閑 slots 的指針指向 NULL。 Linux 內(nèi)核的 Radix 樹(shù)結(jié)構(gòu)體中還包含用于記錄節(jié)點(diǎn)存儲(chǔ)狀態(tài)的標(biāo)簽 tags 成員，標(biāo)簽通過(guò)位設(shè)置指示 Radix 樹(shù)的數(shù)據(jù)存儲(chǔ)狀態(tài)。

至此，我們了解到 radix 樹(shù)的結(jié)構(gòu)，接下來(lái)看一下 radix 樹(shù)所提供的 API。

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

我們從數(shù)據(jù)結(jié)構(gòu)的初始化開(kāi)始看，radix 樹(shù)支持兩種方式初始化。

第一個(gè)是使用宏 RADIX_TREE ：

C

RADIX_TREE(name, gfp_mask);

1

RADIX_TREE(name, gfp_mask);

正如你看到，只需要提供 name 參數(shù)，就能夠使用 RADIX_TREE 宏完成 radix 的定義以及初始化，RADIX_TREE 宏的實(shí)現(xiàn)非常簡(jiǎn)單：

C

#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, }

1

2

3

4

5

6

7

8

#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 宏首先使用 name 定義了一個(gè) radix_tree_root 實(shí)例，并用 RADIX_TREE_INIT 宏帶參數(shù) mask 進(jìn)行初始化。宏 RADIX_TREE_INIT 將 radix_tree_root 初始化為默認(rèn)屬性，并將 gfp_mask 初始化為入?yún)?mask 。

第二種方式是手工定義 radix_tree_root 變量，之后再使用 mask 調(diào)用 INIT_RADIX_TREE 宏對(duì)變量進(jìn)行初始化。

C

struct radix_tree_root my_radix_tree;INIT_RADIX_TREE(my_tree, gfp_mask_for_my_radix_tree);

1

2

struct radix_tree_root my_radix_tree;

INIT_RADIX_TREE(my_tree, gfp_mask_for_my_radix_tree);

INIT_RADIX_TREE 宏定義：

C

#define INIT_RADIX_TREE(root, mask) do { (root)->height = 0; (root)->gfp_mask = (mask); (root)->rnode = NULL; } while (0)

1

2

3

4

5

6

#define INIT_RADIX_TREE(root, mask)??

do {????????????????????????????????

(root)->height = 0;??????????

(root)->gfp_mask = (mask);??

(root)->rnode = NULL;????????

} while (0)

宏 INIT_RADIX_TREE 所初始化的屬性與 RADIX_TREE_INIT 一致

接下來(lái)是 radix 樹(shù)的節(jié)點(diǎn)插入以及刪除，這兩個(gè)函數(shù)：

radix_tree_insert;

radix_tree_delete.

第一個(gè)函數(shù) radix_tree_insert 需要三個(gè)入?yún)ⅲ?/p>

radix 樹(shù) root 節(jié)點(diǎn)結(jié)構(gòu)

索引關(guān)鍵字

需要插入存儲(chǔ)的數(shù)據(jù)

第二個(gè)函數(shù) radix_tree_delete 除了不需要存儲(chǔ)數(shù)據(jù)參數(shù)外，其他與 radix_tree_insert 一致。

radix 樹(shù)的查找實(shí)現(xiàn)有以下幾個(gè)函數(shù)：

radix_tree_lookup;

radix_tree_gang_lookup;

radix_tree_lookup_slot;

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

radix 樹(shù) root 節(jié)點(diǎn)結(jié)構(gòu)

索引關(guān)鍵字

這個(gè)函數(shù)通過(guò)給定的關(guān)鍵字查找 radix 樹(shù)，并返關(guān)鍵字所對(duì)應(yīng)的結(jié)點(diǎn)。

第二個(gè)函數(shù) radix_tree_gang_lookup 具有以下特征：

C

unsigned int radix_tree_gang_lookup(struct radix_tree_root *root, void **results, unsigned long first_index, unsigned int max_items);

1

2

3

4

unsigned int radix_tree_gang_lookup(struct radix_tree_root *root,

void **results,

unsigned long first_index,

unsigned int max_items);

函數(shù)返回查找到記錄的條目數(shù)，并根據(jù)關(guān)鍵字進(jìn)行排序，返回的總結(jié)點(diǎn)數(shù)不超過(guò)入?yún)?max_items 的大小。

最后一個(gè)函數(shù) radix_tree_lookup_slot 返回結(jié)點(diǎn) slot 中所存儲(chǔ)的數(shù)據(jù)。

鏈接

Radix tree

Trie

?