#defineRADIX_TREE_MAP_MASK（RADIX_TREE_MAP_SIZE-1）
/*定义slot数占用的long类型长度个数，每个slot用位图1位进行标记，如：
64个slot时，值为2*/
#defineRADIX_TREE_TAG_LONGS\
（（RADIX_TREE_MAP_SIZE+BITS_PER_LONG-1）/BITS_PER_LONG）
（3）结点结构
树的根结点结构radix_tree_root列出如下（在include/linux/radix-tree.h中）：
#defineRADIX_TREE_MAX_TAGS2/*每个slot需要的最大标签位数*/
/*根结点的标签存放在gfp_mask中，通过__GFP_BITS_SHIFT移位得到*/
structradix_tree_root{
unsignedintheight;/*从叶子向上计算的树高度*/
gfp_tgfp_mask;
/*间接指针指向结点而非数据条目，通过设置root->rnode的低位表示是否是间指针*/
structradix_tree_node*rnode;
#ifdefCONFIG_RADIX_TREE_CONCURRENT
structradix_tree_context*context;
structtask_struct*owner;
#endif
};
结构radix_tree_context列出如下：
structradix_tree_context{
structradix_tree_root*root;
#ifdefCONFIG_RADIX_TREE_CONCURRENT
spinlock_t*locked;
#endif
}
树的结点结构radix_tree_node列出如下（在lib/radix-tree.c中）：
structradix_tree_node{
unsignedintheight;/*从叶子向上计算的树高度*/
unsignedintcount;/*非叶子结点含有一个count域，表示出现在该结点的孩子的数量*/
structrcu_headrcu_head;
void*slots[RADIX_TREE_MAP_SIZE];/*结点的slot指针*/
/*结点标签数组=每个slot需要的最大标签位数*slot数所需的long类型变量数*/
unsignedlongtags[RADIX_TREE_MAX_TAGS][RADIX_TREE_TAG_LONGS];
};
Linux内核radix树高度是可变的，它依赖于存储的索引键值。
radix树查询必须知道树高度，以便知道结点的slot是指向叶子结点的指针还是结点的其他层。
Linux在结点结构中有成员height存入树高度信息。
Linuxradix树的独特特征是标签扩展。
图2显示了有2个标签，分别表示打开和关闭。
这些标签是结点结构的成员tags，该标签用一个位图实现，在加锁的情况下设置和清除。
每个标签基本上是一个在radix树顶层上的位图序号。
标签与群查询一起用来在给定的范围内查找给定标签集的页。
标签在每结点位图中维护，在每个给定的级别上，可以判定下一个级别是否至少有一个标签集。
图2带有2位图标签指示的8位radix树
在结点结构radix_tree_node中，tags域是一个二维数组，每个slot用2位标识，这是一个典型的用空间换时间的应用。
tags域用于记录该结点下面的子结点有没有相应的标志位。
目前RADIX_TREE_MAX_TAGS为2，表示只记录两个标志，其中tags[0]为PAGE_CACHE_DIRTY，tags[1]为PAGE_CACHE_WRITEBACK。
如果当前节点的tags[0]值为1，那么它的子树节点就存在PAGE_CACHE_DIRTY节点，否则这个子树分枝就不存在着这样的节点，就不必再查找这个子树了。
比如在查找PG_dirty的页面时，就不需要遍历整个树，而可以跳过那些tags[0]为0值的子树，这样就提高了查找效率。
“加标签查询”是返回有指定标签集radix树条目的查询，可以查询设置了标签的条目。
加标签查询可以并行执行，但它们需要通过设置或清除标签从操作上互斥。
（4）并行操作的优化
Linuxradix树并行操作包括并行查询和并行修改，其中，并行修改在标准内核中未完没有实现，需要通过打补丁获得该功能。
并行操作说明如下：
∙RCU并发查询
通过使用RCU，RCURadix树可以进行完全并发的查询操作。
RCU从根本上要求原子操作地移动指针从数据结构的一个版本到新的版本，保持旧版本直到系统经过静止状态。
在静止状态点，旧版本数据结构已没有用户，因此可以被安全释放。
RCUradix树的修改操作之间还需要串行化，但是查询不再需要与修改操作串行化。
∙并发修改
RCU可使RCUradix树查询完全并行化，但修改操作成了“瓶颈”。
这可通过将全树的锁破碎成较小的锁进行改善，再明显的方法是对结点进行加锁而非对整个树加锁。
radix树修改操作可分为单向和双向操作。
单向操作仅执行从根节点和叶子结点的单方向指针移动，它包括插入、更新和设置标签操作。
双向操作较复杂，它需要在指针移到叶子后又回移，它包括删除和清除标签操作。
梯级加锁（LadderLocking）和锁耦合（Lock-Coupling）技术常用于数据库方面，允许单向遍历结点加锁的树（双向可能产生死锁）。
如果所有的修改者从树顶到树底进行修改，并且修改的结点持有锁，那么，向下遍历时对孩子加锁，在孩子被锁住时再释放该结点锁。
在这种情况下并发操作是可能的，因为只要根结点解锁，另一个操作就可以自上向下进行。
如果两操作的路径没有相同操作结点，后一个操作可能在前一个操作完成之前完成。
最坏的情况是流水线操作，但这还是比串行化操作好很多。
双向操作包括删除和清除标签操作，分别说明如下：
1）清除标签
在radix树中清除一个标签包括向下遍历树、查找定位条目和清除条目标签的操作。
只要孩子结点没有打标签的条目，就可以向上遍历结点清除标签。
结束条件是：
如果遍历遇到一个结点，在清除一个标签后，它还有一个或多个条目带有标签集，就可以结束向上遍历。
为了与向下遍历期间有同样的结束点，将终止条件改为：
向上遍历将在有比清除标签数更多标签的结点处结束。
这样，不论何时遇到这样的结点，将作为上遍历树的结束点。
2）删除元素
删除元素在删除无用结点时还需要删除该条目的所有标签。
它的终止条件需要满足这两个方面。
向上回退遍历树时需要满足下面的条件：
当遇到一个非空结点且没有无用的标签时应终止向上回退遍历树。
在向下遍历树时鉴别此点的条件是：
当遇到有超过2个孩子的结点、并且每个标签来说结点有多于一个标签条目被清除时，结束向上遍历。
该条件用来鉴别向上回退遍历的终止点。
（5）radix树API说明
∙声明和初始化radix树
声明和初始化radix树的方法列出如下：
#include
/*gfp_mask表示如何执行内存分配，如果操作（如：
插入）以原子性上下文中执行，其值为GFP_ATOMIC*/
RADIX_TREE（name,gfp_mask）;/*声明和初始化名为name的树*/
structradix_tree_rootmy_tree;
INIT_RADIX_TREE（my_tree,gfp_mask）;
∙插入条目
插入条目的函数定义列出如下：
intradix_tree_insert（structradix_tree_root*root,unsignedlongindex,void*item）
函数radix_tree_insert插入条目item到树root中，如果插入条目中内存分配错误，将返回错误-ENOMEM。
该函数不能覆盖写正存在的条目。
如果索引键值index已存在于树中，返回错误-EEXIST。
插入操作成功是，返回0。
对于插入条目操作失败将引起严重问题的场合，下面的一对函数可避免插入操作失败：
intradix_tree_preload（gfp_tgfp_mask）;
voidradix_tree_preload_end（void）;
函数radix_tree_preload尝试用给定的gfp_mask分配足够的内存，保证下一个插入操作不会失败。
在调用插入操作函数之前调用此函数，分配的结构将存放在每CPU变量中。
函数radix_tree_preload操作成功后，将完毕内核抢占。
因此，在插入操作完成之后，用户应调用函数radix_tree_preload_end打开内核抢占。
∙删除条目
删除条目的函数定义列出如下：
void*radix_tree_delete（structradix_tree_root*root,unsignedlongindex）
函数radix_tree_delete删除与索引键值index相关的条目，如果删除条目在树中，返回该条目的指针，否则返回NULL。
∙查询操作
用于查询操作的函数定义列出如下：
/*在树中查找指定键值的条目，查找成功，返回该条目的指针，否则，返回NULL*/
void*radix_tree_lookup（structradix_tree_root*root,unsignedlongindex）;
/*返回指向slot的指针，该slot含有指向查找到条目的指针*/
void**radix_tree_lookup_slot（structradix_tree_root*root,unsignedlongindex）;
/*查询返回max_items条目在results中。
查询时键值索引从first_index开始*/
radix_tree_gang_lookup（structradix_tree_root*root,void**results,unsignedlongfirst_index,unsignedintmax_items）;
∙标签操作
与标签操作相关的函数说明列出如下：
/*将键值index对应的条目设置标签tag，返回值为设置标签的条目*/
void*radix_tree_tag_set（structradix_tree_root*root,unsignedlongindex,unsignedinttag）;
/*从键值index对应的条目清除标签tag，返回值为清除标签的条目*/
void*radix_tree_tag_clear（structradix_tree_root*root,unsignedlongindex,unsignedinttag）;
/*检查键值index对应的条目是否为标签tag，如果键值不存在，返回0，如果键值存在，但标签未设置，返回-1；如果键值存在，且标签已设置，返回1*/
intradix_tree_tag_get（structradix_tree_root*root,unsignedlongindex,unsignedinttag）;
/*从first_index起查询树root中标签值为tag的条目，在results中返回*/
unsignedintradix_tree_gang_lookup_tag（structradix_tree_root*root,void**results,unsignedlongfirst_index,unsignedintmax_items,unsignedinttag）;
/*如果树root中有任何条目使用tag标签，返回键值*/
intradix_tree_tagged（structradix_tree_root*root,unsignedinttag）;
（6）并行操作使用radix树API的方法
∙查询获取slot操作
查询操作支持RCU无阻塞并行读操作，因此，需要遵循RCU的用法加RCU读锁，还需要将rcu_dereference（）用于获得的slot，在写（或更新）操作时，需要给新的slot使用rcu_assign_pointer（）。
查询操作的使用方法列出如下：
structpage**slot,*page;
rcu_read_lock（）;
slot=radix_tree_lookup_slot（&mapping->page_tree,index）;
page=rcu_dereference（*slot）;
rcu_read_unlock（）;
∙查询修改slot操作
Linux内核的radix树需要打补丁才支持并发修改。
查询仅有一个全局状态：
RCU静止状态，并发修改需要跟踪持有什么锁。
锁状态对于操作来说必须是外部的，因此，我们需要实例化一个本地上下文跟踪这些锁。
查询修改slot的方法列出如下：
structpage**slot;
DEFINE_RADIX_TREE_CONTEXT（ctx,&mapping->page_tree）;
radix_tree_lock（&ctx）;/*锁住了根结点*/
/*ctx.tree代替&mapping->page_tree作为根，可以传递上下文
slot=radix_tree_lookup_slot（tx.tree,index）;
rcu_assign_pointer（*slot,new_page）;
radix_tree_unlock（&ctx）;
radix树API函数radix_tree_lookup_slot含有锁从树顶向下移动机制，锁移动的代码部分列出如下：
void**radix_tree_lookup_slot（structradix_tree*root,unsignedlongindex）
{
...
RADIX_TREE_CONTEXT（context,root）;/*提供上下文和实际的root指针*、
...
do{
...
/*从树顶向下移动锁*/
radix_ladder_lock（context,node）;
...
}while（height>0）;
...
}
（7）radix树API的实现
树的操作通常包括查找、插入、删除和树调整，下面分别说明radix树这些操作的实现。
∙查找单个条目
radix树通过索引键值进行查询，如图1所示，它按路径组成索引键值，图中3级结点对应3段6位表示的索引值，图中key对应的叶子slot的索引键值为“2,63,1”。
通过叶子slot的指针slot[1]就可得到所存储的数据item。
因此，查询迭代时，需要将索引键值“2,63,1”移去高2层“2,63”，得到叶子slot的指针索引键值“1”。
图1一个3级结点的radix树及其键值表示
函数radix_tree_lookup执行查找操作，查找方法是：
从叶子到树顶，通过数组索引键值值查看数组元素的方法，一层层地查找slot。
其列出如下（在lib/radix-tree.c中）：
void*radix_tree_lookup（structradix_tree_root*root,unsignedlongindex）
{
unsignedintheight,shift;
structradix_tree_node*node,**slot;
node=rcu_dereference（root->rnode）;/*获取根结点*/
if（node==NULL）
returnNULL;
/*间接指针指向结点而非数据条目，通过设置root->rnode的低位表示是否是间指针。
对于间接指针来说，树高度值root->height大于0，但是RCU查找需要测试间接指针，因为root->height值不可靠。
这种问题仅的RCU下需要考虑*/
if（!
radix_tree_is_indirect_ptr（node））{/*非间接指针，说明只有根结点*/
if（index>0）
returnNULL;
returnnode;
}
/*获取真正结点指针，因为根结点指针的第0位设置为1表示为间接指针。
当使用结点指针时，必须将第0位设置为0，因为地址以字对齐*/
node=radix_tree_indirect_to_ptr（node）;
height=node->height;
if（index>radix_tree_maxindex（height））/*索引键值不能超过最大索引值*/
returnNULL;
/*每层索引偏移值为RADIX_TREE_MAP_SHIFT，叶子索引值偏移基数为（树高-1）*每层索引偏移值*/
shift=（height-1）*RADIX_TREE_MAP_SHIFT;
do{/*从叶子到树顶，通过树路径组成的索引查找指定索引键值的slot*/
slot=（structradix_tree_node**）（node->slots+（（index>>shift）&RADIX_TREE_MAP_MASK））;/*如：
slots+1*/
node=rcu_dereference（*slot）;
if（node==NULL）
returnNULL;
shift-=RADIX_TREE_MAP_SHIFT;/*向上移一层，再迭代查找*/
height--;
}while（height>0）;
returnnode;
}
∙查找多个条目
函数radix_tree_gang_lookup执行多个索引键值的查找，其列出如下：
unsignedintradix_tree_gang_lookup（structradix_tree_root*root,void**results,unsignedlongfirst_index,unsignedintmax_items）
{
unsignedlongmax_index;
structradix_tree_node*node;
unsignedlongcur_index=first_index;
unsignedintret;
node=rcu_dereference（root->rnode）;
if（!
node）
return0;
if（!
radix_tree_is_indirect_ptr（node））{/*如果为非间接指针，表示只有根节点*
升级会员 