Linux內核數據結構：Radix 樹

正如你所知道的， Linux 內核通過許多不同庫以及函數提供各種數據結構以及算法。這個部分我們將介紹其中一個數據結構Radix tree。Linux 內核中有兩個文件與 radix tree 的實現和 API 相關：

include/linux/radix-tree.h

lib/radix-tree.c

首先說明一下什么是 radix tree ，Radix tree 是一個壓縮 trie， trie 是一種通過保存關聯數組（associative array）來提供關鍵字-值（key-value）存儲與查找的數據結構。通常關鍵字是字符串，不過也可以是其他數據類型。 Trie 結構的節點與 n-tree 不同，其節點中并不存儲關鍵字，取而代之的是存儲單個字符標簽。關鍵字查找時，通過從樹的根開始遍歷關鍵字相關的所有字符標簽節點，直至到達最終的葉子節點。下面是個例子：

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

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

|" "|

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

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

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

||||

|g||c|

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

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

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

||||

|o||a|

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

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

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

|t|

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

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

這個例子中，我們可以看到 trie所存儲的關鍵字信息 go 與 cat，壓縮 trie 或 radix tree 與 trie 所不同的是，對于只有一個孩子的中間節點將被壓縮。

Linux 內核中的 Radix 樹將值映射為整型關鍵字，Radix 的數據結構定義在 include/linux/radix-tree.h 文件中 :

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

struct radix_tree_root {

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

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

struct radix_tree_node??__rcu *rnode;

};

上面這個是 radix 樹的 root 節點的結構體，它包括三個成員：

height：從葉節點向上計算出的樹高度。

gfp_mask：內存申請的標識。

rnode：子節點指針。

這里首先要討論的結構體成員是 gfp_mask :

Linux 底層的內存申請接口需要提供一類標識（flag） – gfp_mask ，用于描述內存申請的行為。這個以 GFP_ 前綴開頭的內存申請控制標識主要包括，GFP_NOIO 禁止所有 IO 操作但允許睡眠等待內存，__GFP_HIGHMEM 允許申請內核的高端內存，GFP_ATOMIC 高優先級申請內存且操作不允許被睡眠。

接下來說的節結構體成員是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];};

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

};

這個結構體中包括這幾個內容，節點與父節點的偏移以及到樹底端的高度、子節點的個數、節點的存儲數據域，具體描述如下：

path：與父節點的偏移以及到樹底端的高度

count：子節點的個數。

parent：父節點的指針。

private_data：存儲數據內容緩沖區。

rcu_head：用于節點釋放的 RCU 鏈表。

private_list – 存儲數據。

結構體 radix_tree_node 的最后兩個成員 tags 與 slots 是非常重要且需要特別注意的。每個 Radix 樹節點都可以包括一個指向存儲數據指針的 slots 集合，空閑 slots 的指針指向 NULL。 Linux 內核的 Radix 樹結構體中還包含用于記錄節點存儲狀態的標簽 tags 成員，標簽通過位設置指示 Radix 樹的數據存儲狀態。

至此，我們了解到 radix 樹的結構，接下來看一下 radix 樹所提供的 API。

Linux 內核 radix 樹 API

我們從數據結構的初始化開始看，radix 樹支持兩種方式初始化。

第一個是使用宏 RADIX_TREE ：

RADIX_TREE(name, gfp_mask);

正如你看到，只需要提供 name 參數，就能夠使用 RADIX_TREE 宏完成 radix 的定義以及初始化，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, }

#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 宏帶參數 mask 進行初始化。宏 RADIX_TREE_INIT 將 radix_tree_root 初始化為默認屬性，并將 gfp_mask 初始化為入參 mask 。

第二種方式是手工定義 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);

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)

#define INIT_RADIX_TREE(root, mask)??

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

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

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

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

} while (0)