Mauerer app03.tex V1 - 09/04/2008 6:11pm Page 1220
Appendix C: Notes on C
struct radix_tree_node *node;
unsigned int height;
int tag;
/* Figure out what the height should be. */
height = root->height + 1;
while (index > radix_tree_maxindex(height))
height++;
if (root->rnode == NULL) {
root->height = height;
goto out;
}
do {
if (!(node = radix_tree_node_alloc(root)))
return -ENOMEM;
/* Increase the height. */
node->slots[0] = radix_tree_indirect_to_ptr(root->rnode)
/* Propagate the aggregated tag info into the new root */
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;
}
Depending on the new maximum index, it may be necessary to add more than one level to the tree.
The tree is expanded from the top because there is then no need to copy elements. An additional node
is inserted between the root and the previous top node for each new level. Because node branches are
allocated automatically when new elements are inserted, the kernel need not concern itself with this task.
The kernel provides theradix_tree_lookupfunction to find an element in a radix tree by reference to its
key as shown here:
lib/radix-tree.c
void *radix_tree_lookup(struct radix_tree_root *root, unsigned long index)
{
unsigned int height, shift;
struct radix_tree_node *node, **slot;
