基樹(shù)
內(nèi)核中的基樹(shù)的節(jié)點(diǎn)蹲盘，使用struct radix_tree_node來(lái)表示股毫，其源代碼如下：
struct radix_tree_node {
unsigned int height; /* Height from the bottom */
unsigned int count; /* 子節(jié)點(diǎn)的個(gè)數(shù) */
union {
struct radix_tree_node *parent; /* Used when ascending tree */
struct rcu_head rcu_head; /* Used when freeing node */
};
void __rcu *slots[RADIX_TREE_MAP_SIZE];
unsigned long tags[RADIX_TREE_MAX_TAGS][RADIX_TREE_TAG_LONGS];
};
/* root tags are stored in gfp_mask, shifted by __GFP_BITS_SHIFT */
struct radix_tree_root {
unsigned int height;
gfp_t gfp_mask;
struct radix_tree_node __rcu *rnode;
};
slots是指向各個(gè)孩子節(jié)點(diǎn)的指針，RADIX_TREE_MAP_SIZE通常為64（跟宏定義有關(guān)召衔，我們以64為例來(lái)說(shuō)明）铃诬。
tags顧名思義是標(biāo)簽，代表此節(jié)點(diǎn)的所有孩子節(jié)點(diǎn)的標(biāo)簽苍凛。tags是二維數(shù)組趣席，RADIX_TREE_MAX_TAGS定義為3，即最多支持3種標(biāo)簽醇蝴。RADIX_TREE_TAG_LONGS的長(zhǎng)度使得可以放下所有子節(jié)點(diǎn)的tag（一個(gè)tag占1位）宣肚。
一個(gè)典型的基樹(shù)如下圖所示：
不得不說(shuō)，本來(lái)簡(jiǎn)單的數(shù)據(jù)結(jié)構(gòu)悠栓，加上了RCU的機(jī)制后霉涨，總是有點(diǎn)難以理解。
初始化
跟Linux內(nèi)核中其它的數(shù)據(jù)結(jié)構(gòu)類(lèi)似闸迷，兩種初始化方式：
#define RADIX_TREE(name, mask) \
struct radix_tree_root name = RADIX_TREE_INIT(mask)
#define INIT_RADIX_TREE(root, mask) \
do { \
(root)->height = 0; \
(root)->gfp_mask = (mask); \
(root)->rnode = NULL; \
} while (0)
查找
/*
* is_slot == 1 : search for the slot.
* is_slot == 0 : search for the node.
*/
static void *radix_tree_lookup_element(struct radix_tree_root *root,
unsigned long index, int is_slot)
{
unsigned int height, shift;
struct radix_tree_node *node, **slot;
node = rcu_dereference_raw(root->rnode);
if (node == NULL)
return NULL;
if (!radix_tree_is_indirect_ptr(node)) {
if (index > 0)
return NULL;
return is_slot ? (void *)&root->rnode : node;
}
node = indirect_to_ptr(node);
height = node->height;
if (index > radix_tree_maxindex(height))
return NULL;
shift = (height-1) * RADIX_TREE_MAP_SHIFT;
do {
slot = (struct radix_tree_node **)
(node->slots + ((index>>shift) & RADIX_TREE_MAP_MASK));
node = rcu_dereference_raw(*slot);
if (node == NULL)
return NULL;
shift -= RADIX_TREE_MAP_SHIFT;
height--;
} while (height > 0);
return is_slot ? (void *)slot : indirect_to_ptr(node);
}
/**
* radix_tree_lookup - perform lookup operation on a radix tree
* @root: radix tree root
* @index: index key
*
* Lookup the item at the position @index in the radix tree @root.
*
* This function can be called under rcu_read_lock, however the caller
* must manage lifetimes of leaf nodes (eg. RCU may also be used to free
* them safely). No RCU barriers are required to access or modify the
* returned item, however.
*/
void *radix_tree_lookup(struct radix_tree_root *root, unsigned long index)
{
return radix_tree_lookup_element(root, index, 0);
}
查找的過(guò)程嵌纲，就是把index從高位開(kāi)始，每6位（以64位機(jī)器為例）為一個(gè)單位腥沽，分隔成一個(gè)個(gè)的slot index逮走，然后從radix樹(shù)的根往下搜索的過(guò)程，整體還是比較好理解的今阳。暫時(shí)忽略indirect_to_prt师溅，rcu_dereference_raw這幾個(gè)函數(shù)茅信，這不影響對(duì)整體流程的理解。
插入
/**
* radix_tree_insert - insert into a radix tree
* @root: radix tree root
* @index: index key
* @item: item to insert
*
* 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;
BUG_ON(radix_tree_is_indirect_ptr(item));
/* Make sure the tree is high enough. */
if (index > radix_tree_maxindex(root->height)) {
error = radix_tree_extend(root, index);
if (error)
return error;
}
slot = indirect_to_ptr(root->rnode);
height = root->height;
shift = (height-1) * RADIX_TREE_MAP_SHIFT;
offset = 0; /* uninitialised var warning */
while (height > 0) {
if (slot == NULL) {
/* Have to add a child node. */
if (!(slot = radix_tree_node_alloc(root)))
return -ENOMEM;
slot->height = height;
slot->parent = node;
if (node) {
rcu_assign_pointer(node->slots[offset], slot);
node->count++;
} else
rcu_assign_pointer(root->rnode, ptr_to_indirect(slot));
}
/* Go a level down */
offset = (index >> shift) & RADIX_TREE_MAP_MASK;
node = slot;
slot = node->slots[offset];
shift -= RADIX_TREE_MAP_SHIFT;
height--;
}
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;
}
插入的過(guò)程跟查找的過(guò)程非常相似其實(shí)墓臭，就是沿著樹(shù)從上到下地找蘸鲸，某個(gè)位置沒(méi)有元素就創(chuàng)建元素，直到出錯(cuò)或者把元素放到指定的slot中窿锉。
Tag
內(nèi)核的radix tree支持Tag功能酌摇，就是給某個(gè)元素打一個(gè)tag。這個(gè)tag會(huì)影響該元素到基樹(shù)根上所有元素嗡载。這樣通過(guò)查看根元素是否有這個(gè)tag窑多，就能判斷根元素下的子元素中是否存在這種tag的元素。另外內(nèi)核的基樹(shù)提供了迭代所有設(shè)置過(guò)tag的元素的方法：radix_tree_for_each_tagged洼滚。
