radix树是2.6内核中的增加的重要结构，是各种页面操作文件操作的重要结构之一。
头节点：
struct radix_tree_root {
unsigned int height; //树高度
gfp_t gfp_mask;
struct radix_tree_node *rnode;
};
节点：
struct radix_tree_node {
unsigned int count; //slots数组中非NULL项个数
void *slots[RADIX_TREE_MAP_SIZE]; //存储radix_tree_node的指针（非叶节点）或page结构指针（叶节点）
unsigned long tags[RADIX_TREE_TAGS][RADIX_TREE_TAG_LONGS]; //用以存储上面slots中指针内容指向结构的flag
//前面为每个项的标志位个数，后面位项的个数
};
几个常见操作：
//===================================================================================
//初始化:在slab中分配一个cache存放radix_tree_node
void __init radix_tree_init(void)
{
radix_tree_node_cachep = kmem_cache_create("radix_tree_node",
sizeof(struct radix_tree_node), 0,
SLAB_PANIC, radix_tree_node_ctor, NULL);
radix_tree_init_maxindex(); //初始化height_to_maxindex[]数组
hotcpu_notifier(radix_tree_callback, 0);
}
//计算每个height中最大index，初始化height_to_maxindex[]数组
static __init void radix_tree_init_maxindex(void)
{
unsigned int i;
for (i = 0; i < ARRAY_SIZE(height_to_maxindex); i++)
height_to_maxindex[i] = __maxindex(i);
}
static __init unsigned long __maxindex(unsigned int height)
{
unsigned int tmp = height * RADIX_TREE_MAP_SHIFT;
//不明白为什么不用 (~0UL >> (RADIX_TREE_INDEX_BITS - tmp ))
unsigned long index = (~0UL >> (RADIX_TREE_INDEX_BITS - tmp - 1)) >> 1;
if (tmp >= RADIX_TREE_INDEX_BITS)
index = ~0UL; //height为6时候最大为0xFFFFFFFF
return index;
}
//===================================================================================
/**
* radix_tree_insert - insert into a radix tree
* @root: radix tree root
* @index: index key （倘若是page结构指针就是其线性地址）
* @item: item to insert(可以是page的指针或node的指针)
*
* Insert an item into the radix tree at position @index.
*/
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;
/* 倘若index与根结点指向节点都为空，或index超过树的最大容量 */
if ((!index && !root->rnode) ||
index > radix_tree_maxindex(root->height)) {
error = radix_tree_extend(root, index); //扩展树
if (error)
return error;
}
slot = root->rnode;
height = root->height;
shift = (height-1) * RADIX_TREE_MAP_SHIFT; //计算偏移量 RADIX_TREE_MAP_SHIFT为6
offset = 0; /* uninitialised var warning */
do {
if (slot == NULL) {
/* 加入一个子节点 */
if (!(slot = radix_tree_node_alloc(root)))
return -ENOMEM;
if (node) {
node->slots[offset] = slot;
node->count++;
} else
root->rnode = slot; //为根节点建立一个子节点
}
/* Go a level down */
offset = (index >> shift) & RADIX_TREE_MAP_MASK;//计算index
node = slot;
slot = node->slots[offset];
shift -= RADIX_TREE_MAP_SHIFT;
height--;
} while (height > 0);
if (slot != NULL)
return -EEXIST;
BUG_ON(!node);
node->count++;
node->slots[offset] = item;
BUG_ON(tag_get(node, 0, offset));
BUG_ON(tag_get(node, 1, offset));
return 0;
}
//=======================================================================================
很简单的取得slots数组中的对应index的指针的指针
static inline void **__lookup_slot(struct radix_tree_root *root,
unsigned long index)
{
unsigned int height, shift;
struct radix_tree_node **slot;
height = root->height;
if (index > radix_tree_maxindex(height))
return NULL;
shift = (height-1) * RADIX_TREE_MAP_SHIFT;
slot = &root->rnode;
while (height > 0) {
if (*slot == NULL)
return NULL;
slot = (struct radix_tree_node **)
((*slot)->slots +
((index >> shift) & RADIX_TREE_MAP_MASK));
shift -= RADIX_TREE_MAP_SHIFT;
height--;
}
return (void **)slot;
}
//=======================================================================================
//顾名思义通过index取得存储指针的slot
void **radix_tree_lookup_slot(struct radix_tree_root *root, unsigned long index)
{
return __lookup_slot(root, index);
}
EXPORT_SYMBOL(radix_tree_lookup_slot);
//顾名思义通过index取得slot中的指针
void *radix_tree_lookup(struct radix_tree_root *root, unsigned long index)
{
void **slot;
slot = __lookup_slot(root, index);
return slot != NULL ? *slot : NULL;
}
//=======================================================================================
/**
* radix_tree_delete - delete an item from a radix tree
* @root: radix tree root
* @index: index key
*
* Remove the item at @index from the radix tree rooted at @root.
*
* Returns the address of the deleted item, or NULL if it was not present.
*/
void *radix_tree_delete(struct radix_tree_root *root, unsigned long index)
{
struct radix_tree_path path[RADIX_TREE_MAX_PATH], *pathp = path;
struct radix_tree_path *orig_pathp;
struct radix_tree_node *slot;
unsigned int height, shift;
void *ret = NULL;
char tags[RADIX_TREE_TAGS];
int nr_cleared_tags;
int tag;
int offset;
height = root->height;
if (index > radix_tree_maxindex(height))
goto out;
shift = (height - 1) * RADIX_TREE_MAP_SHIFT;
pathp->node = NULL;
slot = root->rnode;
for ( ; height > 0; height--) {
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;
}
ret = slot;
if (ret == NULL)
goto out;
orig_pathp = pathp;
/*
* Clear all tags associated with the just-deleted item
*/
nr_cleared_tags = 0;
for (tag = 0; tag < RADIX_TREE_TAGS; tag++) {
tags[tag] = 1;
if (tag_get(pathp->node, tag, pathp->offset)) {
tag_clear(pathp->node, tag, pathp->offset);
if (!any_tag_set(pathp->node, tag)) {
tags[tag] = 0;
nr_cleared_tags++;
}
}
}
for (pathp--; nr_cleared_tags && pathp->node; pathp--) {
for (tag = 0; tag < RADIX_TREE_TAGS; tag++) {
if (tags[tag])
continue;
tag_clear(pathp->node, tag, pathp->offset);
if (any_tag_set(pathp->node, tag)) {
tags[tag] = 1;
nr_cleared_tags--;
}
}
}
/* Now free the nodes we do not need anymore */
for (pathp = orig_pathp; pathp->node; pathp--) {
pathp->node->slots[pathp->offset] = NULL;
pathp->node->count--;
if (pathp->node->count) {
if (pathp->node == root->rnode)
radix_tree_shrink(root);
goto out;
}
/* Node with zero slots in use so free it */
radix_tree_node_free(pathp->node);
}
root->rnode = NULL;
root->height = 0;
out:
return ret;
}
Trackback: http://tb.donews.net/TrackBack.aspx?PostId=1008752