Linux内核Radix Tree（三）：API介绍

1.     单值查找radix_tree_lookup

函数radix_tree_lookup执行查找操作，查找方法是：从叶子到树顶，通过数组索引键值值查看数组元素的方法，一层层地查找slot。其列出如下

void *radix_tree_lookup(struct radix_tree_root *root, unsigned long index)
{
unsigned int height, shift;
struct radix_tree_node *node, **slot;

node =
rcu_dereference(root->rnode); /*获取根结点*/
if (node == NULL)
return NULL;

/*间接指针指向结点而非数据条目，通过设置root->rnode的低位表示是否是间指针。对于间接指针来说，树高度值root->height大于0，但是RCU查找需要测试间接指针，因为root->height 值不可靠。这种问题仅的RCU下需要考虑*/
if (!radix_tree_is_indirect_ptr(node)) { /*非间接指针，说明只有根结点*/
if (index > 0)
return NULL;
return node;
}

/*获取真正结点指针，因为根结点指针的第0位设置为1表示为间接指针。当使用结点指针时，必须将第0位设置为0，因为地址以字对齐*/
node = radix_tree_indirect_to_ptr(node);

height =
node->height;
if (index > radix_tree_maxindex(height)) /*索引键值不能超过最大索引值*/
return NULL;

/*每层索引偏移值为RADIX_TREE_MAP_SHIFT，叶子索引值偏移基数为（树高-1）*每层索引偏移值*/
shift = (height-1) * RADIX_TREE_MAP_SHIFT;

do { /*从叶子到树顶，通过树路径组成的索引查找指定索引键值的slot*/
slot = (struct radix_tree_node
**)(node->slots + ((index>>shift) & RADIX_TREE_MAP_MASK)); /*如：slots +1*/
node = rcu_dereference(*slot);
if (node == NULL)
return NULL;

shift -= RADIX_TREE_MAP_SHIFT; /*向上移一层，再迭代查找*/
height--;
} while (height > 0);

return node;
}

2.
多值查找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)
{
unsigned long max_index;
struct radix_tree_node *node;
unsigned long cur_index = first_index;
unsigned int ret;

node =
rcu_dereference(root->rnode);
if (!node)
return 0;

if
(!radix_tree_is_indirect_ptr(node)) { /*如果为非间接指针，表示只有根节点*/
if (first_index > 0)
return 0;
results[0] = node;
return 1;
}
node = radix_tree_indirect_to_ptr(node); /*清除用于间接指针标识的第0位*/

max_index =
radix_tree_maxindex(node->height); /*获取树的最大索引键值*/

ret = 0;
while (ret < max_items) { /* max_items为查找的最大条目数*/
unsigned int nr_found;
unsigned long next_index; /* 下一个搜索的索引键值*/

if (cur_index > max_index) /*已查询完所需查询的索引键值*/
break;
nr_found = __lookup(node, results +
ret, cur_index,
max_items - ret, &next_index);
ret += nr_found;
if (next_index == 0)
break;
cur_index = next_index;
}

return ret;
}

static unsigned int
__lookup(struct radix_tree_node *slot, void **results, unsigned long index,
unsigned int max_items, unsigned long *next_index)
{
unsigned int nr_found = 0;
unsigned int shift, height;
unsigned long i;

height =
slot->height;
if (height == 0)
goto out;
/*所有叶子slot的索引键值基数偏移*/
shift = (height-1) * RADIX_TREE_MAP_SHIFT;

/*从底层向树顶层，
for ( ; height > 1; height--) { /*从叶子向树顶查找*/
i = (index >> shift) &
RADIX_TREE_MAP_MASK;
for (;;) { /*遍历每一层的各个路径，由树顶到当前层一条路径组成索引键值*/
/*如果slot不为空，那么它挂有子结点，跳出本循环，进入子结点层进行本循环*/
if
(slot->slots[i] != NULL)

break;
/*如果slot为空，就跳过slot对应的所有索引键值*/
/*清除索引号低位.将索引号与该层slot的起始索引号对齐*/
index &=
~((1UL << shift) - 1);
/*跳过一个slot的索引键值数*/
index += 1UL <<
shift;
if (index == 0)

goto out; /* 32-bit wraparound */
i++; /*找到多个slot*/
if (i ==
RADIX_TREE_MAP_SIZE)

goto out;
}

shift
-= RADIX_TREE_MAP_SHIFT; /*向上移一层，基数偏移减少*/
slot =
rcu_dereference(slot->slots[i]);
if (slot == NULL)
goto out;

}

/* 返回找到的多个slot*/
for (i = index & RADIX_TREE_MAP_MASK; i <
RADIX_TREE_MAP_SIZE; i++) {
struct radix_tree_node *node;
index++;
node = slot->slots[i];
if (node) {

results[nr_found++] = rcu_dereference(node);
if (nr_found ==
max_items)

goto out;
}
}
out:
*next_index = index;
return nr_found;
}

3.     插入操作radix_tree_insert

函数radix_tree_insert找到索引键值对应的结点，将item加到该结点的slot指针上。其列出如下：

int radix_tree_insert(struct
radix_tree_root *root, unsigned long index, void *item)
{
struct radix_tree_node *node = NULL, *slot;
unsigned int height, shift;
int offset;
int error;

BUG_ON(radix_tree_is_indirect_ptr(item));

/* 如果树的高度不够，就扩展树。函数radix_tree_maxindex计算树高容纳的最大索引*/
if (index > radix_tree_maxindex(root->height)) {
error = radix_tree_extend(root,
index);
if (error)
return
error;
}

slot =
radix_tree_indirect_to_ptr(root->rnode);

height =
root->height;
shift = (height-1) * RADIX_TREE_MAP_SHIFT; /*计算偏移基数*/

offset = 0;
while (height > 0) {
if (slot == NULL) { /*如果slot为空，则需要加入孩子结点*/
/* 分配slot */
if (!(slot =
radix_tree_node_alloc(root)))

return -ENOMEM;

slot->height = height;
if (node)
{/*添加slot*/

rcu_assign_pointer(node->slots[offset], slot);

node->count++;
} else

rcu_assign_pointer(root->rnode,radix_tree_ptr_to_indirect(slot));
}

/* 进入上一层*/
offset = (index >> shift)
& RADIX_TREE_MAP_MASK;
node = slot;
slot = node->slots[offset];
shift -= RADIX_TREE_MAP_SHIFT;
height--;
}
/*如果index对应的slot已有映射页面，返回-EEXIST*/
if (slot != NULL)
return -EEXIST;

if (node) {
node->count++; /*增加子结点的计数*/
rcu_assign_pointer(node->slots[offset],
item);
BUG_ON(tag_get(node, 0, offset));
BUG_ON(tag_get(node, 1, offset));
} else { /*为顶层结点*/
rcu_assign_pointer(root->rnode,
item);
BUG_ON(root_tag_get(root, 0));
BUG_ON(root_tag_get(root, 1));
}

return 0;
}

4.     扩展树radix_tree_extend

如果当前树高度不足以存放index，就需要扩展树，扩展方法是在旧树顶上加新的根结点，并将原根结点的tag信息移到新根结点的第1个slot。函数radix_tree_extend 列出如下：
static int radix_tree_extend(struct radix_tree_root *root, unsigned long index)
{
struct radix_tree_node *node;
unsigned int height;
int tag;

/* 计算扩展的深度*/
height = root->height + 1;
/*如果index超过树高所容纳的最大索引值，树高递增*/
while (index > radix_tree_maxindex(height))
height++;

/*到这里已计算好合适的高度height*/
if (root->rnode == NULL) { /*只有根结点，设置好树高度就可返回*/
root->height = height;
goto out;
}

/*将当前树扩展到高度height*/
do {
unsigned int newheight;
if (!(node =
radix_tree_node_alloc(root))) /*分配一个结点*/
return
-ENOMEM;

/* 增加树高，在树顶点之上增加一个结点*/
node->slots[0] =
radix_tree_indirect_to_ptr(root->rnode);

/*传播tag信息到新根结点*/
/*以前的根结点现成为新顶结点的第1个插槽。 如果以前的根结点打上了tag，就将新增结点的第1个插槽对应的子节点打上相应的tag*/
for (tag = 0; tag <
RADIX_TREE_MAX_TAGS; tag++) {
if
(root_tag_get(root, tag))

tag_set(node, tag, 0);
}

newheight = root->height+1;
node->height = newheight;
node->count = 1;
node =
radix_tree_ptr_to_indirect(node);
rcu_assign_pointer(root->rnode,
node);
root->height = newheight;
} while (height > root->height);
out:
return 0;
}

5.
删除操作radix_tree_delete

函数radix_tree_delete删除index对应的条目，并返回删除条目的地址。其列出如下：
void *radix_tree_delete(struct radix_tree_root *root, unsigned long index)
{
/*数组path用于保存路径上的结点及索引偏移值*/
struct radix_tree_path path[RADIX_TREE_MAX_PATH + 1], *pathp
= path;
struct radix_tree_node *slot = NULL;
struct radix_tree_node *to_free;
unsigned int height, shift;
int tag;
int offset;

height =
root->height;
if (index > radix_tree_maxindex(height)) /*index不能超过树的最大索引值*/
goto out;

slot = root->rnode;
if (height == 0) { /*只有根结点*/
root_tag_clear_all(root);
root->rnode = NULL;
goto out;
}
slot = radix_tree_indirect_to_ptr(slot);

shift = (height - 1) *
RADIX_TREE_MAP_SHIFT;
pathp->node = NULL;
/*获取删除条目的路径*/
/*将index从根到叶子的路径所经过的结点及相应索引偏移值存放在数组pathp中*/
do {
if (slot == NULL)
goto out;

pathp++;
offset = (index >> shift)
& RADIX_TREE_MAP_MASK;
pathp->offset = offset;
pathp->node = slot;
slot = slot->slots[offset];
shift -= RADIX_TREE_MAP_SHIFT;
height--;
} while (height > 0);

if (slot == NULL)
goto out;

/*清除与删除条目相关的所有标签*/
for (tag = 0; tag < RADIX_TREE_MAX_TAGS; tag++) {
if (tag_get(pathp->node, tag,
pathp->offset))

radix_tree_tag_clear(root, index, tag);
}

to_free = NULL;
/*释放不再需要的结点 */
while (pathp->node) { /*删除

pathp->node->slots[pathp->offset] = NULL; /*清除slot*/
pathp->node->count--; /*孩子数量减1*/
/*调用RCU机制的函数call_rcu在最后一个引用结束时延迟释放结点to_free */
if (to_free)

radix_tree_node_free(to_free);

if (pathp->node->count) { /*还有孩子存在*/
if (pathp->node
== radix_tree_indirect_to_ptr(root->rnode)) /*为根结点的孩子*/

radix_tree_shrink(root); /*树缩小*/
goto out;
}

/*释放有0个slot的结点 */
to_free = pathp->node;
pathp--;

}
/*运行到这里，说明是根结点*/
root_tag_clear_all(root);
root->height = 0;
root->rnode = NULL;
if (to_free)
radix_tree_node_free(to_free);

out:
return slot;
}

6.
压缩树radix_tree_shrink

函数radix_tree_shrink缩小树的高度到最小。其列出如下：

static inline void radix_tree_shrink(struct
radix_tree_root *root)
{
/* 尝试缩小树的高度*/
while (root->height > 0) {
struct radix_tree_node *to_free =
root->rnode;
void *newptr;

BUG_ON(!radix_tree_is_indirect_ptr(to_free));
to_free =
radix_tree_indirect_to_ptr(to_free);

/*候选结点多于一个孩子或孩子不在最左边slot，不能缩小树的高度，跳出循环*/
if (to_free->count != 1)
break;
if (!to_free->slots[0])
break;

/*不需要调用rcu_assign_pointer()，因为仅从树的一部分到另一部分移动结点。如果释放旧指针的引用to_free->slots[0]是安全的，那么释放新指针的引用root->rnode也是安全的*/
newptr = to_free->slots[0];
if (root->height > 1)
newptr =
radix_tree_ptr_to_indirect(newptr);
root->rnode = newptr;
root->height--;
/* 仅释放0结点*/
tag_clear(to_free, 0, 0);
tag_clear(to_free, 1, 0);
to_free->slots[0] = NULL;
to_free->count = 0;
radix_tree_node_free(to_free);
}
}