電子發(fā)燒友App
正如你所知道的，Linux內核提供了許多不同的庫和函數(shù)，它們實現(xiàn)了不同的數(shù)據(jù)結構和算法。在這部分，我們將研究其中一種數(shù)據(jù)結構——基數(shù)樹Radix tree。在 Linux 內核中，有兩個文件與基數(shù)樹的實現(xiàn)和API相關：
include/linux/radix-tree.h
lib/radix-tree.c
讓我們先說說什么是 基數(shù)樹 吧?；鶖?shù)樹是一種?壓縮的字典樹compressed trie?，而字典樹是實現(xiàn)了關聯(lián)數(shù)組接口并允許以 鍵值對 方式存儲值的一種數(shù)據(jù)結構。這里的鍵通常是字符串，但可以使用任意數(shù)據(jù)類型。字典樹因為它的節(jié)點而與 n叉樹 不同。字典樹的節(jié)點不存儲鍵，而是存儲單個字符的標簽。與一個給定節(jié)點關聯(lián)的鍵可以通過從根遍歷到該節(jié)點獲得。舉個例子：
+-----------+
| |
| " " |
| |
+------+-----------+------+
| |
| |
+----v------+ +-----v-----+
| | | |
| g | | c |
| | | |
+-----------+ +-----------+
| |
| |
+----v------+ +-----v-----+
| | | |
| o | | a |
| | | |
+-----------+ +-----------+
|
|
+-----v-----+
| |
| t |
| |
+-----------+
因此在這個例子中，我們可以看到一個有著兩個鍵 go 和 cat 的 字典樹 。壓縮的字典樹也叫做 基數(shù)樹 ，它和 字典樹 的不同之處在于，所有只有一個子節(jié)點的中間節(jié)點都被刪除。
Linux 內核中的基數(shù)樹是把值映射到整形鍵的一種數(shù)據(jù)結構。include/linux/radix-tree.h文件中的以下結構體描述了基數(shù)樹：
struct radix_tree_root {
unsigned int height;
gfp_t gfp_mask;
struct radix_tree_node __rcu *rnode;
};
這個結構體描述了一個基數(shù)樹的根，它包含了3個域成員：
height - 樹的高度;
gfp_mask - 告知如何執(zhí)行動態(tài)內存分配;
rnode - 孩子節(jié)點指針.
我們第一個要討論的字段是 gfp_mask ：
底層內核的內存動態(tài)分配函數(shù)以一組標志作為 gfp_mask ，用于描述如何執(zhí)行動態(tài)內存分配。這些控制分配進程的 GFP_ 標志擁有以下值：( GF_NOIO 標志)意味著睡眠以及等待內存，( __GFP_HIGHMEM 標志)意味著高端內存能夠被使用，( GFP_ATOMIC 標志)意味著分配進程擁有高優(yōu)先級并不能睡眠等等。
GFP_NOIO - 睡眠等待內存
__GFP_HIGHMEM - 高端內存能夠被使用;
GFP_ATOMIC - 分配進程擁有高優(yōu)先級并且不能睡眠;
等等。
下一個字段是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];
};
這個結構體包含的信息有父節(jié)點中的偏移以及到底端(葉節(jié)點)的高度、子節(jié)點的個數(shù)以及用于訪問和釋放節(jié)點的字段成員。這些字段成員描述如下：
path - 父節(jié)點中的偏移和到底端(葉節(jié)點)的高度
count - 子節(jié)點的個數(shù);
parent - 父節(jié)點指針;
private_data - 由樹的用戶使用;
rcu_head - 用于釋放節(jié)點;
private_list - 由樹的用戶使用;
radix_tree_node 的最后兩個成員—— tags 和 slots 非常重要且令人關注。Linux 內核基數(shù)樹的每個節(jié)點都包含了一組指針槽slots，槽里存儲著指向數(shù)據(jù)的指針。在Linux內核基數(shù)樹的實現(xiàn)中，空槽存儲的是 NULL 。Linux內核中的基數(shù)樹也支持標簽tags，它與 radix_tree_node 結構體的 tags 字段相關聯(lián)。有了標簽，我們就可以對基數(shù)樹中存儲的記錄以單個比特位bit進行設置。
既然我們了解了基數(shù)樹的結構，那么該是時候看一下它的API了。
Linux內核基數(shù)樹API
我們從結構體的初始化開始。有兩種方法初始化一個新的基數(shù)樹。第一種是使用 RADIX_TREE 宏：
RADIX_TREE(name, gfp_mask);
正如你所看到的，我們傳遞了 name 參數(shù)，所以通過 RADIX_TREE 宏，我們能夠定義和初始化基數(shù)樹為給定的名字。RADIX_TREE 的實現(xià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 宏的開始，我們使用給定的名字定義 radix_tree_root 結構體實例，并使用給定的 mask 調用 RADIX_TREE_INIT 宏。 而 RADIX_TREE_INIT 宏則是使用默認值和給定的mask對 radix_tree_root 結構體進行了初始化。
第二種方法是手動定義radix_tree_root結構體，并且將它和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 宏使用默認值和給定的 mask 完成初始化工作。
接下來是用于向基數(shù)樹插入和刪除數(shù)據(jù)的兩個函數(shù)：
radix_tree_insert;
radix_tree_delete;
第一個函數(shù) radix_tree_insert 需要3個參數(shù)：
基數(shù)樹的根;
索引鍵;
插入的數(shù)據(jù);
radix_tree_delete 函數(shù)需要和 radix_tree_insert 一樣的一組參數(shù)，但是不需要傳入要刪除的數(shù)據(jù)。
基數(shù)樹的搜索以兩種方法實現(xiàn)：
radix_tree_lookup;
radix_tree_gang_lookup;
radix_tree_lookup_slot.
第一個函數(shù)radix_tree_lookup需要兩個參數(shù)：
基數(shù)樹的根;
索引鍵;
這個函數(shù)嘗試在樹中查找給定的鍵，并返回和該鍵相關聯(lián)的記錄。第二個函數(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);
它返回的是記錄的個數(shù)。 results 中的結果，按鍵排序，并從第一個索引開始。返回的記錄個數(shù)將不會超過 max_items 的值。
最后一個函數(shù)radix_tree_lookup_slot將會返回包含數(shù)據(jù)的指針槽。
?
工商網(wǎng)監(jiān)
評論