Linux Kernel Architecture

Mauerer app03.tex V1 - 09/04/2008 6:11pm Page 1216

Appendix C: Notes on C

implement the node as part of the useful data. The following macro is provided to get to the useful data

starting at a node:

<rbtree.h>

#define rb_entry(ptr, type, member) container_of(ptr, type, member)

To ensure that RB tree implementation is generally available and is not restricted to memory manage-

ment, the kernel provides only general standard functions for manipulating trees (rotation operations,

for example) — these are implemented inlib/rbtree.c.

For example, the Ext3 filesystem uses RB trees to sortdirectory entries in RAM. As already described,

data items are implemented as containers of the nodes.

fs/ext3/dir.c

struct fname {

__u32 hash;

__u32 minor_hash;

struct rb_node rb_hash;

struct fname *next;

__u32 inode;

__u8 name_len;

__u8 file_type;

char name[0];

};

Search and insert operations must be provided by all subsystems that use red-black trees. Searching

is performed in the same way as normal searches in an organized binary tree and can therefore be

implemented very easily. The insertion routine must place new elements in the tree as red leaves

(rb_link_nodecan be used to do this). Therb_insert_colorstandard function must then be invoked

to rebalance the tree so that it still complies with the previously described rules.<rbtree.h>includes

examples on which the functions to be provided can be based.

C.2.10 Radix Trees

The second tree implementation provided in libraryform in the kernel makes use of radix trees to orga-

nize data in memory. Radix trees differ from other trees because it is not necessary to compare the entire

key at every branch, but only part of the key with the stored value of the node when performing search

operations. This results in slightly different worst-case and average-case behavior than in other imple-

mentations, which are described in detail in the corresponding textbooks on algorithms. Also, radix trees

are not particularly difficult to implement, which adds to their attraction.

Thenodedatastructureisdefinedasfollowsinthekernelsources:

lib/radix-tree.c

#define RADIX_TREE_MAP_SHIFT (CONFIG_BASE_SMALL? 4 : 6)

#define RADIX_TREE_MAP_SIZE (1UL << RADIX_TREE_MAP_SHIFT)

#define RADIX_TREE_MAP_MASK (RADIX_TREE_MAP_SIZE-1)

struct radix_tree_node {

unsigned int height; /* Height from the bottom */

unsigned int count;

struct rcu_head rcu_head;