Trie
正如你所知道的,Linux內核提供了許多不同的庫和函數,它們實現了不同的數據結構和算法。在這部分,我們將研究其中一種數據結構——基數樹(Radix tree)。在 Linux 內核中,有兩個文件與基數樹的實現和API相關:
讓我們先說說什麼是 基數樹
吧。基數樹是一種 壓縮的字典樹 (compressed trie) ,而字典樹是實現了關聯數組接口並允許以 鍵值對
方式存儲值的一種數據結構。這裡的鍵通常是字符串,但可以使用任意數據類型。字典樹因為它的節點而與 n叉樹
不同。字典樹的節點不存儲鍵,而是存儲單個字符的標簽。與一個給定節點關聯的鍵可以通過從根遍歷到該節點獲得。舉個例子:
+-----------+
||
|" "|
||
+------+-----------+------+
||
||
+----v------++-----v-----+
||||
| g || c |
||||
+-----------++-----------+
||
||
+----v------++-----v-----+
||||
| o || a |
||||
+-----------++-----------+
|
|
+-----v-----+
||
| t |
||
+-----------+
因此在這個例子中,我們可以看到一個有著兩個鍵 go
和 cat
的 字典樹
。壓縮的字典樹也叫做 基數樹
,它和 字典樹
的不同之處在於,所有只有一個子節點的中間節點都被刪除。
Linux 內核中的基數樹是把值映射到整形鍵的一種數據結構。include/linux/radix-tree.h文件中的以下結構體描述了基數樹:
struct radix_tree_root {
unsignedint height;
gfp_t gfp_mask;
struct radix_tree_node __rcu *rnode;
};
這個結構體描述了一個基數樹的根,它包含了3個域成員:
height
- 樹的高度;gfp_mask
- 告知如何執行動態內存分配;rnode
- 孩子節點指針.我們第一個要討論的字段是 gfp_mask
:
底層內核的內存動態分配函數以一組標志作為 gfp_mask
,用於描述如何執行動態內存分配。這些控制分配進程的 GFP_
標志擁有以下值:( GF_NOIO
標志)意味著睡眠以及等待內存,( __GFP_HIGHMEM
標志)意味著高端內存能夠被使用,( GFP_ATOMIC
標志)意味著分配進程擁有高優先級並不能睡眠等等。
GFP_NOIO
- 睡眠等待內存__GFP_HIGHMEM
- 高端內存能夠被使用;GFP_ATOMIC
- 分配進程擁有高優先級並且不能睡眠;等等。
下一個字段是rnode
:
struct radix_tree_node {
unsignedint path;
unsignedint 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];
unsignedlong tags[RADIX_TREE_MAX_TAGS][RADIX_TREE_TAG_LONGS];
};
這個結構體包含的信息有父節點中的偏移以及到底端(葉節點)的高度、子節點的個數以及用於訪問和釋放節點的字段成員。這些字段成員描述如下:
path
- 父節點中的偏移和到底端(葉節點)的高度count
- 子節點的個數;parent
- 父節點指針;private_data
- 由樹的用戶使用;rcu_head
- 用於釋放節點;private_list
- 由樹的用戶使用;radix_tree_node
的最後兩個成員—— tags
和 slots
非常重要且令人關注。Linux 內核基數樹的每個節點都包含了一組指針槽( slots ),槽裡存儲著指向數據的指針。在Linux內核基數樹的實現中,空槽存儲的是 NULL
。Linux內核中的基數樹也支持標簽( tags ),它與 radix_tree_node
結構體的 tags
字段相關聯。有了標簽,我們就可以對基數樹中存儲的記錄以單個比特位( bit )進行設置。
既然我們了解了基數樹的結構,那麼該是時候看一下它的API了。
我們從結構體的初始化開始。有兩種方法初始化一個新的基數樹。第一種是使用 RADIX_TREE
宏:
RADIX_TREE(name, gfp_mask);
正如你所看到的,我們傳遞了 name
參數,所以通過 RADIX_TREE
宏,我們能夠定義和初始化基數樹為給定的名字。RADIX_TREE
的實現很簡單:
#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 完成初始化工作。
接下來是用於向基數樹插入和刪除數據的兩個函數:
radix_tree_insert
;radix_tree_delete
;第一個函數 radix_tree_insert
需要3個參數:
radix_tree_delete
函數需要和 radix_tree_insert
一樣的一組參數,但是不需要傳入要刪除的數據。
基數樹的搜索以兩種方法實現:
radix_tree_lookup
;radix_tree_gang_lookup
;radix_tree_lookup_slot
.第一個函數radix_tree_lookup
需要兩個參數:
這個函數嘗試在樹中查找給定的鍵,並返回和該鍵相關聯的記錄。第二個函數 radix_tree_gang_lookup
有以下的函數簽名:
unsignedint radix_tree_gang_lookup(struct radix_tree_root *root,
void**results,
unsignedlong first_index,
unsignedint max_items);
它返回的是記錄的個數。 results
中的結果,按鍵排序,並從第一個索引開始。返回的記錄個數將不會超過 max_items
的值。
最後一個函數radix_tree_lookup_slot
將會返回包含數據的指針槽。
via: https://github.com/0xAX/linux-insides/blob/master/DataStructures/radix-tree.md
作者:[0xAX] 譯者:cposture 校對:Mr小眼兒
本文由 LCTT 原創翻譯,Linux中國 榮譽推出