Mauerer app03.tex V1 - 09/04/2008 6:11pm Page 1218
Appendix C: Notes on C
lib/radix-tree.c
static __init unsigned long __maxindex(unsigned int height)
{
unsigned int width = height * RADIX_TREE_MAP_SHIFT;
int shift = RADIX_TREE_INDEX_BITS - width;
if (shift < 0)
return ~0UL;
if (shift >= BITS_PER_LONG)
return 0UL;
return ~0UL >> shift;
}
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);
}
At runtime, only simple array lookup is needed, and this can be done very quickly. This is important
because the maximum number of elements for a given tree height needs to be computed frequently.
The elements contained in the tree are characterized by a descriptor that accepts continuous values from
0 up to the maximum number of elements that can currently be stored in the tree as follows:
radix_tree_insertis used to insert a new element in a radix tree as follows:
lib/radix-tree.c
static inline void *radix_tree_indirect_to_ptr(void *ptr)
{
return (void *)((unsigned long)ptr & ~RADIX_TREE_INDIRECT_PTR);
}
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;
/* 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 = radix_tree_indirect_to_ptr(root->rnode)
height = root->height;
shift = (height-1) * RADIX_TREE_MAP_SHIFT;
