電子發(fā)燒友App
正如你所知道的， Linux 內(nèi)核通過許多不同庫以及函數(shù)提供各種數(shù)據(jù)結(jié)構以及算法。這個部分我們將介紹其中一個數(shù)據(jù)結(jié)構Radix tree。Linux 內(nèi)核中有兩個文件與 radix tree 的實現(xiàn)和 API 相關：
include/linux/radix-tree.h
lib/radix-tree.c
首先說明一下什么是 radix tree ，Radix tree 是一個 壓縮 trie， trie 是一種通過保存關聯(lián)數(shù)組（associative array）來提供 關鍵字-值（key-value） 存儲與查找的數(shù)據(jù)結(jié)構。通常關鍵字是字符串，不過也可以是其他數(shù)據(jù)類型。 Trie 結(jié)構的節(jié)點與 n-tree 不同，其節(jié)點中并不存儲關鍵字，取而代之的是存儲單個字符標簽。關鍵字查找時，通過從樹的根開始遍歷關鍵字相關的所有字符標簽節(jié)點，直至到達最終的葉子節(jié)點。下面是個例子：
+-----------+|||" "| | |+------+-----------+------+||||+----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|
|?????????? |
+-----------+
這個例子中，我們可以看到 trie所存儲的關鍵字信息 go 與 cat，壓縮 trie 或 radix tree 與 trie 所不同的是，對于只有一個孩子的中間節(jié)點將被壓縮。
Linux 內(nèi)核中的 Radix 樹將值映射為整型關鍵字，Radix 的數(shù)據(jù)結(jié)構定義在 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;
};
上面這個是 radix 樹的 root 節(jié)點的結(jié)構體，它包括三個成員：
height：從葉節(jié)點向上計算出的樹高度。
gfp_mask：內(nèi)存申請的標識。
rnode：子節(jié)點指針。
這里首先要討論的結(jié)構體成員是 gfp_mask :
Linux 底層的內(nèi)存申請接口需要提供一類標識（flag） – gfp_mask ，用于描述內(nèi)存申請的行為。這個以 GFP_ 前綴開頭的內(nèi)存申請控制標識主要包括，GFP_NOIO 禁止所有 IO 操作但允許睡眠等待內(nèi)存，__GFP_HIGHMEM 允許申請內(nèi)核的高端內(nèi)存，GFP_ATOMIC 高優(yōu)先級申請內(nèi)存且操作不允許被睡眠。
接下來說的節(jié)結(jié)構體成員是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];
};
這個結(jié)構體中包括這幾個內(nèi)容，節(jié)點與父節(jié)點的偏移以及到樹底端的高度、子節(jié)點的個數(shù)、節(jié)點的存儲數(shù)據(jù)域，具體描述如下：
path：與父節(jié)點的偏移以及到樹底端的高度
count：子節(jié)點的個數(shù)。
parent：父節(jié)點的指針。
private_data：存儲數(shù)據(jù)內(nèi)容緩沖區(qū)。
rcu_head：用于節(jié)點釋放的 RCU 鏈表。
private_list – 存儲數(shù)據(jù)。
結(jié)構體 radix_tree_node 的最后兩個成員 tags 與 slots 是非常重要且需要特別注意的。每個 Radix 樹節(jié)點都可以包括一個指向存儲數(shù)據(jù)指針的 slots 集合，空閑 slots 的指針指向 NULL。 Linux 內(nèi)核的 Radix 樹結(jié)構體中還包含用于記錄節(jié)點存儲狀態(tài)的標簽 tags 成員，標簽通過位設置指示 Radix 樹的數(shù)據(jù)存儲狀態(tài)。
至此，我們了解到 radix 樹的結(jié)構，接下來看一下 radix 樹所提供的 API。
Linux 內(nèi)核 radix 樹 API
我們從數(shù)據(jù)結(jié)構的初始化開始看，radix 樹支持兩種方式初始化。
第一個是使用宏 RADIX_TREE ：
C
RADIX_TREE(name, gfp_mask);
1
RADIX_TREE(name, gfp_mask);
正如你看到，只需要提供 name 參數(shù)，就能夠使用 RADIX_TREE 宏完成 radix 的定義以及初始化，RADIX_TREE 宏的實現(xià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 定義了一個 radix_tree_root 實例，并用 RADIX_TREE_INIT 宏帶參數(shù) mask 進行初始化。宏 RADIX_TREE_INIT 將 radix_tree_root 初始化為默認屬性，并將 gfp_mask 初始化為入?yún)?mask 。
第二種方式是手工定義 radix_tree_root 變量，之后再使用 mask 調(diào)用 INIT_RADIX_TREE 宏對變量進行初始化。
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 一致
接下來是 radix 樹的節(jié)點插入以及刪除，這兩個函數(shù)：
radix_tree_insert;
radix_tree_delete.
第一個函數(shù) radix_tree_insert 需要三個入?yún)ⅲ?/p>
radix 樹 root 節(jié)點結(jié)構
索引關鍵字
需要插入存儲的數(shù)據(jù)
第二個函數(shù) radix_tree_delete 除了不需要存儲數(shù)據(jù)參數(shù)外，其他與 radix_tree_insert 一致。
radix 樹的查找實現(xiàn)有以下幾個函數(shù)：
radix_tree_lookup;
radix_tree_gang_lookup;
radix_tree_lookup_slot;
第一個函數(shù) radix_tree_lookup 需要兩個參數(shù)：
radix 樹 root 節(jié)點結(jié)構
索引關鍵字
這個函數(shù)通過給定的關鍵字查找 radix 樹，并返關鍵字所對應的結(jié)點。
第二個函數(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ù)關鍵字進行排序，返回的總結(jié)點數(shù)不超過入?yún)?max_items 的大小。
最后一個函數(shù) radix_tree_lookup_slot 返回結(jié)點 slot 中所存儲的數(shù)據(jù)。
鏈接
Radix tree
Trie
?
工商網(wǎng)監(jiān)
評論