[翻译]Linux 内核里的数据结构 —— 基数树

[翻译]Linux 内核里的数据结构 —— 基数树

大家好,又见面了,我是你们的朋友全栈君。

Linux 内核里的数据结构 —— 基数树

基数树 Radix tree

正如你所知道的,Linux内核提供了许多不同的库和函数,它们实现了不同的数据结构和算法。在这部分,我们将研究其中一种数据结构——基数树 Radix tree。在 Linux 内核中,有两个文件与基数树的实现和API相关:

让我们先说说什么是 基数树 吧。基数树是一种 压缩的字典树 (compressed trie) ,而字典树是实现了关联数组接口并允许以 键值对 方式存储值的一种数据结构。这里的键通常是字符串,但可以使用任意数据类型。字典树因为它的节点而与 n叉树 不同。字典树的节点不存储键,而是存储单个字符的标签。与一个给定节点关联的键可以通过从根遍历到该节点获得。举个例子:

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

因此在这个例子中,我们可以看到一个有着两个键 gocat字典树 。压缩的字典树也叫做 基数树 ,它和 字典树 的不同之处在于,所有只有一个子节点的中间节点都被删除。

Linux 内核中的基数树是把值映射到整形键的一种数据结构。include/linux/radix-tree.h文件中的以下结构体描述了基数树:

struct radix_tree_root {
         unsigned int            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 {
        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 – 用于释放节点;
  • private_list – 由树的用户使用;

radix_tree_node 的最后两个成员—— tagsslots 非常重要且令人关注。Linux 内核基数树的每个节点都包含了一组指针槽( slots ),槽里存储着指向数据的指针。在Linux内核基数树的实现中,空槽存储的是 NULL 。Linux内核中的基数树也支持标签( tags ),它与 radix_tree_node 结构体的 tags 字段相关联。有了标签,我们就可以对基数树中存储的记录以单个比特位( bit )进行设置。

既然我们了解了基数树的结构,那么该是时候看一下它的API了。

Linux内核基数树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 有以下的函数签名:

unsigned int radix_tree_gang_lookup(struct radix_tree_root *root,
                                    void **results,
                                    unsigned long first_index,
                                    unsigned int max_items);

它返回的是记录的个数。 results 中的结果,按键排序,并从第一个索引开始。返回的记录个数将不会超过 max_items 的值。

最后一个函数radix_tree_lookup_slot将会返回包含数据的指针槽。

链接


via: https://github.com/0xAX/linux-insides/blob/master/DataStructures/radix-tree.md

转载于:https://www.cnblogs.com/cposture/p/9029030.html

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/107517.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • SpringMVC学习—使用ajax返回Json出现乱码解决方法[通俗易懂]

    在使用ajax请求后台访问数据的数据,后台返回的数据是乱码,带??问号的乱码,之前还一直没有遇到过,在这里记录整理一下,贴出解决代码!

  • idea正版在线激活码破解方法「建议收藏」

    idea正版在线激活码破解方法,https://javaforall.cn/100143.html。详细ieda激活码不妨到全栈程序员必看教程网一起来了解一下吧!

  • PCI与PCIe学习之二——软件篇

    PCI与PCIe学习之二——软件篇文章转载自:点击打开链接本篇主要介绍PCI和PCIe的软件界面和UEFI对PCI的支持。PCI/PCIe软件界面1。配置空间PCIspec规定了PCI设备必须提供的单独地址空间:配置空间(configurationspace),前64个字节(其地址范围为0x00~0x3F)是所有PCI设备必须支持的(有不少简单的设备也仅支持这些),此外PCI/PCI-X还扩展了…

  • 数据分析sql面试必会6题经典_经典的SQL语句面试题「建议收藏」

    数据分析sql面试必会6题经典_经典的SQL语句面试题「建议收藏」2015-11-1506:30:02阅读(383)Student(S#,Sname,Sage,Ssex)学生表Course(C#,Cname,T#)课程表SC(S#,C#,score)成绩表Teacher(T#,Tname)教师表问题:1、查询“001”课程比“002”课程成绩高的所有学生的学号;selecta.S#from(selects#,scorefromSCwhe…

  • APP开发防套路秘籍!

    APP开发防套路秘籍!在互联网软件开发行业混迹多年,深知这个行业的水有多深。就拿APP开发来说,市场上APP开发外包公司实在太多了,大中小都应有尽有,稍不留神,就很容易被“不正规”的公司给套路了。为此,整理了一份“三要一不”防套路秘籍,一起来学习下吧!1.要整体外包大多数企业,想要开发一款APP,都会首选外包这种方式。而外包又有两种形式,即整体外包和半外包。顾名思义,整体外包就是将UI、前端、后台都交给一个外包公司…

  • Linux ioctl FIONREAD 和select 使用

    Linux ioctl FIONREAD 和select 使用LinuxioctlFIONREAD和select使用使用select与ioctl判断socketclient是否断开的方式(1)ioctl+FIONREADintnsel=select(maxfd+1,&(rfds),NULL,NULL,&timeout);if(-1!=ioctl(clientfd,FIONREAD,&nread)){if(nread!=0){result=readable;}else{resul

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号