本文共 2800 字，大约阅读时间需要 9 分钟。
Linux内核红黑树的算法都定义在linux-2.6.38.8/include/linux/rbtree.h和linux-2.6.38.8/lib/rbtree.c两个文件中。
1、结构体
- 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_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)))); 这里的巧妙之处是使用成员rb_parent_color同时存储两种数据，一是其双亲结点的地址，另一是此结点的着色。__attribute__((aligned(sizeof(long))))属性保证了红黑树中的每个结点的首地址都是32位对齐的（在32位机上），也就是说每个结点首地址的bit[1]和bit[0]都是0，因此就可以使用bit[0]来存储结点的颜色属性而不干扰到其双亲结点首地址的存储。
PS: ptmalloc 代码中也用到这些特性，通过将一结构体进行地址对齐后，该结构体的首元素就可以节省出几个位用作他用。这种方法可以更高效地利用内存空间。
PS：为什么在rb_node中需要保存其父亲节点的首地址啊?因为内核中如果进行树的遍历，不可能用递归实现（递归容易造成栈溢出）。这样做，可以更好地转化为迭代来进行更好的树的遍历。
操作rb_parent_color的函数：
- #define rb_parent(r) ((struct rb_node *)((r)->rb_parent_color & ~3)) //获得其双亲结点的首地址
- #define rb_color(r) ((r)->rb_parent_color & 1) //获得颜色属性
- #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) //设置黑色属性
-
- static inline void rb_set_parent(struct rb_node *rb, struct rb_node *p)
- {
- rb->rb_parent_color = (rb->rb_parent_color & 3) | (unsigned long)p;
- }
- static inline void rb_set_color(struct rb_node *rb, int color)
- {
- rb->rb_parent_color = (rb->rb_parent_color & ~1) | color;
- }
红黑树的遍历：
4、遍历
rb_first和rb_next函数可组成中序遍历，即以升序遍历红黑树中的所有结点。
- struct rb_node *rb_first(const struct rb_root *root)
- {
- struct rb_node *n;
-
- n = root->rb_node;
- if (!n)
- return NULL;
- while (n->rb_left)
- n = n->rb_left;
- return n;
- }
-
- struct rb_node *rb_next(const struct rb_node *node)
- {
- struct rb_node *parent;
-
- if (rb_parent(node) == node)
- return NULL;
-
-
-
- if (node->rb_right) {
- node = node->rb_right;
- while (node->rb_left)
- node=node->rb_left;
- return (struct rb_node *)node;
- }
-
-
-
-
-
-
-
- while ((parent = rb_parent(node)) && node == parent->rb_right)
- node = parent;
-
- return parent;
- }
一个遍历的演示程序：
- void print_rbtree(struct rb_root *tree)
- {
- struct rb_node *node;
-
- for (node = rb_first(tree); node; node = rb_next(node))
- printf("%d ", rb_entry(node, struct mytype, my_node)->num);
-
- printf("\n");
- }
PS：linux内核中将这种遍历做成了STL迭代器的形式，从而更好地进行代码的复用。
PS：感觉linux 内核中还有些 for_each宏之类的东西，是想做成闭包的形式，也是模仿STL的思想，更好地进行代码复用。
转载地址：http://skrvb.baihongyu.com/