Mauerer app03.tex V1 - 09/04/2008 6:11pm Page 1219Appendix C: Notes on C
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;
if (node) {
rcu_assign_pointer(node->slots[offset], slot);
node->count++;
} else
rcu_assign_pointer(root->rnode,
radix_tree_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)
} else {
rcu_assign_pointer(root->rnode, item);
}return 0;
}If the descriptor of the element is larger than the current number of elements that can be processed, the
tree must be enlarged; this is described later in this section.
The code traverses the tree from top to bottom starting at the root, and the path is defined solely by the
key being searched. Depending on the position in the tree, certain parts of the key are selected to find
the matching entry in theslotarray that leads to the next lower tree level. This corresponds exactly to
the characteristics of radix trees. The tree is traversed in order to allocate tree branches not yet present.
When this is done, the tree height doesnotchange, because the tree can grow only in its width. The new
entry is inserted in the matching slot once the code has reached level 0. Since the tree is protected by the
RCU mechanism, the data pointers must not be assigned directly, but only viarcu_assign_pointeras
discussed in Chapter 5.
The height of the tree is modified byradix_tree_extend— which is called, if needed, at the start of the
function. It is defined as follows in the kernel sources:
lib/radix-tree.c
static int radix_tree_extend(struct radix_tree_root *root, unsigned long index)
{