Linux 内核数据结构:Radix 树
作者:网络转载 发布时间:[ 2015/8/26 13:17:34 ] 推荐标签:操作系统
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,
}
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);
INIT_RADIX_TREE 宏定义:
#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 具有以下特征:
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 中所存储的数据。
本文内容不用于商业目的,如涉及知识产权问题,请权利人联系SPASVO小编(021-61079698-8054),我们将立即处理,马上删除。
相关推荐
Linux下开源的DDR压力测试工具曝Linux恶意软件:让树莓派设备挖掘数字货币linux系统中不同颜色的文件夹及根目录介绍软件测试工程师必知必会Linux命令Linux下DNS服务器配置如何成为不可替代的Linux运维工程师?详解Linux进程(作业)的查看和杀死Linux 日志定时轮询流程详解比特币勒索病毒不只Windows系统有,Linux版的来了Linux日志定时轮询流程详解Linux iommu和vfio概念空间解构Linux系统如何低于TCP洪水攻击Linux无损调整分区大小Linux下防火墙配置实例Linux使用Jexus托管Asp.Net Core应用程序Linux中引号的那些事
更新发布
功能测试和接口测试的区别
2023/3/23 14:23:39如何写好测试用例文档
2023/3/22 16:17:39常用的选择回归测试的方式有哪些?
2022/6/14 16:14:27测试流程中需要重点把关几个过程?
2021/10/18 15:37:44性能测试的七种方法
2021/9/17 15:19:29全链路压测优化思路
2021/9/14 15:42:25性能测试流程浅谈
2021/5/28 17:25:47常见的APP性能测试指标
2021/5/8 17:01:11热门文章
常见的移动App Bug??崩溃的测试用例设计如何用Jmeter做压力测试QC使用说明APP压力测试入门教程移动app测试中的主要问题jenkins+testng+ant+webdriver持续集成测试使用JMeter进行HTTP负载测试Selenium 2.0 WebDriver 使用指南