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| | |+-----------+
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 intheight;
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 intpath;
unsigned intcount;
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
如何利用区块链技术优化电力物联网建设？
苹果16 Pro将搭载骁龙X75基带，实现5G领先
特斯拉为吸全世界锂电建千兆工厂 八大优势凸显
谷歌CEO施密特称搜索、位置和社交是未来和趋势
工业传感器选型的六大基本原则
Linux内核数据结构：Radix 树
中国的良心企业一方有难八方支援 京东连夜驰援九寨沟地震灾区
14埃米节点暗示离原子极限不远了
鸿利智汇子公司取得两项LED发明专利证书
装载机秤称重传感器的详细介绍
AHU风墙空调系统运行模式
一文看懂日本电产马达的腾飞历程
简易且廉价的Mp3或IPod扬声器的制作
物联网为敏捷开发框架增添价值
能降噪也能提噪的AR耳机—Here One推迟到明年2月份上市
IC Insights：预计今年下半年全球DRAM营收将较上半年骤减40%
风口之后5G之前的VR将迎来回暖期
路由器网络接口解析
朗锐智科X86智能相机信息揭露
海尔H-2516,2916TV状态信号无彩色技改
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 intheight;
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 intpath;
unsigned intcount;
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
如何利用区块链技术优化电力物联网建设？
苹果16 Pro将搭载骁龙X75基带，实现5G领先
特斯拉为吸全世界锂电建千兆工厂 八大优势凸显
谷歌CEO施密特称搜索、位置和社交是未来和趋势
工业传感器选型的六大基本原则
Linux内核数据结构：Radix 树
中国的良心企业一方有难八方支援 京东连夜驰援九寨沟地震灾区
14埃米节点暗示离原子极限不远了
鸿利智汇子公司取得两项LED发明专利证书
装载机秤称重传感器的详细介绍
AHU风墙空调系统运行模式
一文看懂日本电产马达的腾飞历程
简易且廉价的Mp3或IPod扬声器的制作
物联网为敏捷开发框架增添价值
能降噪也能提噪的AR耳机—Here One推迟到明年2月份上市
IC Insights：预计今年下半年全球DRAM营收将较上半年骤减40%
风口之后5G之前的VR将迎来回暖期
路由器网络接口解析
朗锐智科X86智能相机信息揭露
海尔H-2516,2916TV状态信号无彩色技改