Red-black tree

Red-black tree is a kind of balanced binary tree. It has good properties. The nodes in the tree are ordered, and because it is balanced, it is also searched. There is no very bad situation, and the time complexity of binary tree based operations is O(log(N)). The Linux kernel uses a red-black tree to maintain memory blocks when managing vm_area_struct.

First look at the definition of red and black trees in include/linux/rbtree.h, as follows:

struct rb_node

{

unsigned long rb_parent_color;

#define RB_RED 0

#define RB_BLACK 1

struct rb_node *rb_right;

struct rb_node *rb_left;

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

struct rb_root is just a wrapper for struct rb_node* The advantage is that it does not seem to pass the secondary pointer. Yes, very simple. Look at the following important macros. Careful you will find that rb_parent_color is not that simple. Andrea Arcangeli uses a small trick here, but it's great. As the name implies, this member actually contains a pointer to the parent and the color of this node! How did it do it? Very simple, alignment works. Since it is the sizeof (long) size alignment, then on the IA-32, the lower two bits of the address of any rb_node structure must be zero. Instead of being empty, it is better to use them to represent the color. In fact, one is enough.

This way, to extract the parent pointer, just clear the lower two bits of the rb_parent_color member:

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

To take the color, just look at the last bit:

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

Testing colors and setting colors is also a matter of course. Special mention is made to the following inline function:

static inline void rb_link_node(struct rb_node * node, struct rb_node * parent, struct rb_node ** rb_link);

It sets parent to the parent node of node and lets rb_link point to node.

We focus on lib/rbtree.c and look at some of the important algorithms associated with red-black trees. Before we start, let's recall the rules of the red-black tree:

1. Each node is either red or black;

2. The root node must be Black;

3. Red nodes If the child has children, their children must be black;

4. Each path from the root node to the leaf must contain the same number of black nodes. .

These four rules can limit a sorting tree to be balanced.

__rb_rotate_left is a left-hand rotation of the node node in the tree rooted at root, and __rb_rotate_right is right-handed. These two functions are for subsequent insert and delete services, rather than providing an interface to the outside.

The newly inserted nodes are set to leaves, dyed red, if the above rules are broken after insertion, the color and rotation can be restored, and the binary tree is rebalanced. The interface function for the insert operation is

void rb_insert_color(struct rb_node *node, struct rb_root *root);

It puts the determined parent node The node node of the point is integrated into the red-black tree rooted at root. The analysis of the specific algorithm can refer to Section 14.3 in [1]. The implementation here is almost exactly the same as the one in the book. How to determine the node's parent node should be done manually by calling rb_insert_color. It is worth pointing out that although the insert operation requires a loop iteration, the total number of rotations will not exceed twice! So the efficiency is still very optimistic.

The deletion operation is more or less troublesome. It must first perform the deletion like "Ordinary Binary Search Tree", and then judge whether to execute further according to the color of the deleted node. Operation. The interface to be deleted is:

void rb_erase(struct rb_node *node, struct rb_root *root);

In fact, it does not actually delete node Instead, just let it break away from the tree rooted at root, and finally it has to decide whether to call __rb_erase_color to adjust. For the explanation of the specific algorithm, refer to Sections 13.3 and 14.4 of [1], RB-DELETE-FIXUP in the corresponding book of __rb_erase_color, and the implementation here is basically the same as that in the book.

The remaining interfaces are simpler.

struct rb_node *rb_first(struct rb_root *root);

Find and return the smallest one in the tree rooted at root Node, as long as you go from the root node to the left.

struct rb_node *rb_last(struct rb_root *root);

is to find and return the largest one, keep going to the right.

struct rb_node *rb_next(struct rb_node *node);

Returning the succession of node in the tree is a bit more complicated. If the right child of node is not empty, it only needs to return the smallest node in the right subtree of node; if it is empty, it should look up and find the node of the left child of the father of the overlapping node, return Parent node. If the above has reached the root node, it returns NULL.

struct rb_node *rb_prev(struct rb_node *node);

Returns the precursor of node and is symmetric with the operation in rb_next.

void rb_replace_node(struct rb_node *victim, struct rb_node *new, struct rb_root *root);

Replace root with root The victim node in the tree.

A typical example of a red-black tree interface is as follows:

static inline struct page * rb_search_page_cache(struct inode * inode,

unsigned long offset)

{

struct rb_node * n = inode->i_rb_page_cache.rb_node;

struct page * page;

while (n)

{

page = rb_entry(n, struct page, rb_page_cache);

if (offset < page->offset)

n = n->rb_left;

else if (offset > page->offset)

n = n- >rb_right;

else

return page;