正如你所知道的， 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| | |+———–+
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 所不同的是，关于只要一个孩子的中心节点将被紧缩。
Linux 内核中的 Radix 树将值映射为整型关键字，Radix 的数据结构界说在 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 节点的结构体，它包括三个成员：
height：从叶节点向上计算出的树高度。
gfp_mask：内存请求的标识。
rnode：子节点指针。
这儿首要要评论的结构体成员是 gfp_mask :
Linux 底层的内存请求接口需求供给一类标识（flag） – gfp_mask ，用于描绘内存请求的行为。这个以 GFP_ 前缀最初的内存请求操控标识首要包括，GFP_NOIO 制止一切 IO 操作但答应睡觉等候内存，__GFP_HIGHMEM 答应请求内核的高端内存，GFP_ATOMIC 高优先级请求内存且操作不答应被睡觉。
接下来说的节结构体成员是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];
};
这个结构体中包括这几个内容，节点与父节点的偏移以及到树底端的高度、子节点的个数、节点的存储数据域，详细描绘如下：
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 ：
C
RADIX_TREE(name, gfp_mask);
1
RADIX_TREE(name, gfp_mask);
正如你看到，只需求供给 name 参数，就可以运用 RADIX_TREE 宏完结 radix 的界说以及初始化，RADIX_TREE 宏的完结十分简略：
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 宏带参数 mask 进行初始化。宏 RADIX_TREE_INIT 将 radix_tree_root 初始化为默许特点，并将 gfp_mask 初始化为入参 mask 。
第二种方法是手艺界说 radix_tree_root 变量，之后再运用 mask 调用 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 树的节点刺进以及删去，这两个函数：
radix_tree_insert;
radix_tree_delete.
第一个函数 radix_tree_insert 需求三个入参：
radix 树 root 节点结构
索引关键字
需求刺进存储的数据
第二个函数 radix_tree_delete 除了不需求存储数据参数外，其他与 radix_tree_insert 共同。
radix 树的查找完结有以下几个函数：
radix_tree_lookup;
radix_tree_gang_lookup;
radix_tree_lookup_slot;
第一个函数 radix_tree_lookup 需求两个参数：
radix 树 root 节点结构
索引关键字
这个函数经过给定的关键字查找 radix 树，并返关键字所对应的结点。
第二个函数 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);
函数回来查找到记载的条目数，并依据关键字进行排序，回来的总结点数不超过入参 max_items 的巨细。
最终一个函数 radix_tree_lookup_slot 回来结点 slot 中所存储的数据。
链接
Radix tree
Trie
