Linux Kernel Architecture

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

Appendix C: Notes on C

❑ If a node is red, both children must be black. It therefore follows that there may be no two con-

secutive red nodes on any path from the root of the tree to any leaf, but there may be any number

of black nodes.

❑ The number of black nodes on a simple path from a node to a leaf is the same for all leaves.

One advantage of red-black trees is that all important tree operations (inserting, deleting, and
searching for elements) can be performed inO(logn)steps,wherenis the number of elements in
the tree.

To represent the nodes of an RB tree, the data structure needs not only pointers to the children and a
field to hold the useful data, but also an element to hold color information. The kernel implements this
by means of the following definition:

<rbtree.h>

#define RB_RED 0

#define RB_BLACK 1

struct rb_node

{

unsigned long rb_parent_color;

int rb_color;

struct rb_node *rb_right;

struct rb_node *rb_left;

} __attribute__((aligned(sizeof(long))));

Although this is not directly visible in the definition, the kernel maintains an additional pointer
to the parent node. It is hidden inrb_parent_color: Only one bit is needed to represent two
colors, and this information is contained in the lowest bit ofrb_parent_color.Therestofthe
variable is used to hold the parent pointer. This is possible because pointers are on all architectures
at least aligned on 4-byte boundaries, so the two lowest-valued bits are guaranteed to be 0 .Itis,
however, essential that the kernel masks out the color information before de-referencing the pointer
as follows:

<rbtree.h>

#define rb_parent(r) ((struct rb_node *)((r)->rb_parent_color & ~3))

The color information must also be obtained with a special macro as shown here:

<rbtree.h>

#define rb_color(r) ((r)->rb_parent_color & 1)

Additionally, the kernel provides convenience functions that distinguish red and black nodes and allow
to set the node color as follows:

<rbtree.h>

#define rb_is_red(r) (!rb_color(r))

#define rb_is_black(r) rb_color(r)

#define rb_set_red(r) do { (r)->rb_parent_color &= ~1; } while (0)

#define rb_set_black(r) do { (r)->rb_parent_color |= 1; } while (0)

The useful data associated with a node is not linked to it by means of a further element — instead,
the kernel uses the container mechanism (which you’ve seen in the context of list implementation) to