Linux內(nèi)核中的紅黑樹

Godbach

引用鏈接：http://www.kerneltravel.net/jiaoliu/kern-rbtree.html

紅黑樹是平衡二叉樹的一種，它有很好的性質(zhì)，樹中的結(jié)點(diǎn)都是有序的，而且因為它本身就是平衡的，所以查找也不會出現(xiàn)非常惡劣的情況，基于二叉樹的操作的時間復(fù)雜度是O(log(N))。Linux內(nèi)核在管理vm_area_struct時就是采用了紅黑樹來維護(hù)內(nèi)存塊的。

先到include/linux/rbtree.h中看一下紅黑樹的一些定義，如下：

1. struct rb_node
   
2. {
   
3.         unsigned long  rb_parent_color;
   
4. #define        RB_RED                0
   
5. #define        RB_BLACK        1
   
6.         struct rb_node *rb_right;
   
7.         struct rb_node *rb_left;
   
8. } __attribute__((aligned(sizeof(long))));

復(fù)制代碼

struct rb_root只是struct rb_node*的一個包裝，這樣做的好處是看起來不用傳遞二級指針了。不錯，很簡單。再看一下下面幾個重要的宏，細(xì)心的你一定會發(fā)現(xiàn)，rb_parent_color其實沒那么簡單，Andrea Arcangeli在這里使用了一個小的技巧，不過非常棒。正如名字所暗示，這個成員其實包含指向parent的指針和此結(jié)點(diǎn)的顏色！它是怎么做到的呢？很簡單，對齊起了作用。既然是sizeof(long)大小的對齊，那么在IA-32上，任何rb_node結(jié)構(gòu)體的地址的低兩位肯定都是零，與其空著不用，還不如用它們表示顏色，反正顏色就兩種，其實一位就已經(jīng)夠了。

這樣，提取parent指針只要把rb_parent_color成員的低兩位清零即可：

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

復(fù)制代碼

取顏色只要看最后一位即可：

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

復(fù)制代碼

測試顏色和設(shè)置顏色也是水到渠成的事了。需要特別指出的是下面的一個內(nèi)聯(lián)函數(shù)：

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

復(fù)制代碼

它把parent設(shè)為node的父結(jié)點(diǎn)，并且讓rb_link指向node。

我們把重點(diǎn)集中在lib/rbtree.c上，看看一些和紅黑樹相關(guān)的重要算法。開始之前我們一起回憶一下紅黑樹的規(guī)則：


1. 每個結(jié)點(diǎn)要么是紅色要么是黑色；

2. 根結(jié)點(diǎn)必須是黑色；

3. 紅結(jié)點(diǎn)如果有孩子，其孩子必須都是黑色；

4. 從根結(jié)點(diǎn)到葉子的每條路徑必須包含相同數(shù)目的黑結(jié)點(diǎn)。

這四條規(guī)則可以限制一棵排序樹是平衡的。

__rb_rotate_left是把以root為根的樹中的node結(jié)點(diǎn)進(jìn)行左旋，__rb_rotate_right是進(jìn)行右旋。這兩個函數(shù)是為后面的插入和刪除服務(wù)，而不是為外部提供接口。

新插入的結(jié)點(diǎn)都設(shè)為葉子，染成紅色，插入后如果破壞了上述規(guī)則，通過調(diào)整顏色和旋轉(zhuǎn)可以恢復(fù)，二叉樹又重新平衡。插入操作的接口函數(shù)是

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

復(fù)制代碼

它把已確定父結(jié)點(diǎn)的node結(jié)點(diǎn)融入到以root為根的紅黑樹中，具體算法的分析可以參考[1]中第14.3節(jié)，這里的實現(xiàn)和書中的講解幾乎完全一樣。怎么確定node的父結(jié)點(diǎn)應(yīng)該在調(diào)用rb_insert_color之前通過手工迭帶完成。值得指出的一點(diǎn)是，雖然插入操作需要一個循環(huán)迭代，但是總的旋轉(zhuǎn)次數(shù)不會超過兩次！所以效率還是很樂觀的。

刪除操作多多少少都有點(diǎn)麻煩，它要先執(zhí)行像普通二叉查找樹的“刪除”，然后根據(jù)刪除結(jié)點(diǎn)的顏色來判斷是否執(zhí)行進(jìn)一步的操作。刪除的接口是：

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

復(fù)制代碼

其實它并沒有真正刪除node，而只是讓它和以root為根的樹脫離關(guān)系，最后它還要判斷是否調(diào)用__rb_erase_color來調(diào)整。具體算法的講解看參考[1]中第13.3和14.4節(jié)，__rb_erase_color對應(yīng)書中的RB-DELETE-FIXUP，此處的實現(xiàn)和書上也基本上一致。

其余的幾個接口就比較簡單了。

1. struct rb_node *rb_first(struct rb_root *root);

復(fù)制代碼

在以root為根的樹中找出并返回最小的那個結(jié)點(diǎn)，只要從根結(jié)點(diǎn)一直向左走就是了。

1. struct rb_node *rb_last(struct rb_root *root);

復(fù)制代碼

是找出并返回最大的那個，一直向右走。

1. struct rb_node *rb_next(struct rb_node *node);

復(fù)制代碼

返回node在樹中的后繼，這個稍微復(fù)雜一點(diǎn)。如果node的右孩子不為空，它只要返回node的右子樹中最小的結(jié)點(diǎn)即可；如果為空，它要向上查找，找到迭帶結(jié)點(diǎn)是其父親的左孩子的結(jié)點(diǎn)，返回父結(jié)點(diǎn)。如果一直上述到了根結(jié)點(diǎn)，返回NULL。

1. struct rb_node *rb_prev(struct rb_node *node);

復(fù)制代碼

返回node的前驅(qū)，和rb_next中的操作對稱。

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

復(fù)制代碼

用new替換以root為根的樹中的victim結(jié)點(diǎn)。

紅黑樹接口使用的一個典型例子如下：

1. static inline struct page * rb_search_page_cache(struct inode * inode,
   
2.                                                  unsigned long offset)
   
3. {
   
4.         struct rb_node * n = inode->i_rb_page_cache.rb_node;
   
5.         struct page * page;
   
6. 
   
7.         while (n)
   
8.         {
   
9.                 page = rb_entry(n, struct page, rb_page_cache);
   
10. 
    
11.                 if (offset < page->offset)
    
12.                         n = n->rb_left;
    
13.                 else if (offset > page->offset)
    
14.                         n = n->rb_right;
    
15.                 else
    
16.                         return page;
    
17.         }
    
18.         return NULL;
    
19. }
    
20. 
    
21. static inline struct page * __rb_insert_page_cache(struct inode * inode,
    
22.                                                    unsigned long offset,
    
23.                                                    struct rb_node * node)
    
24. {
    
25.         struct rb_node ** p = &inode->i_rb_page_cache.rb_node;
    
26.         struct rb_node * parent = NULL;
    
27.         struct page * page;
    
28. 
    
29.         while (*p)
    
30.         {
    
31.                 parent = *p;
    
32.                 page = rb_entry(parent, struct page, rb_page_cache);
    
33. 
    
34.                 if (offset < page->offset)
    
35.                         p = &(*p)->rb_left;
    
36.                 else if (offset > page->offset)
    
37.                         p = &(*p)->rb_right;
    
38.                 else
    
39.                         return page;
    
40.         }
    
41. 
    
42.         rb_link_node(node, parent, p);
    
43. 
    
44.         return NULL;
    
45. }
    
46. 
    
47. static inline struct page * rb_insert_page_cache(struct inode * inode,
    
48.                                                  unsigned long offset,
    
49.                                                  struct rb_node * node)
    
50. {
    
51.         struct page * ret;
    
52.         if ((ret = __rb_insert_page_cache(inode, offset, node)))
    
53.                 goto out;
    
54.         rb_insert_color(node, &inode->i_rb_page_cache);
    
55. out:
    
56.         return ret;
    
57. }

復(fù)制代碼

因為紅黑樹的這些良好性質(zhì)和實現(xiàn)中接口的簡易性，它被廣泛應(yīng)用到內(nèi)核編程中，大大提高了內(nèi)核的效率。



參考資料：


1. Introduction to Algorithms, Thomas H. Cormen, Charles E. Leiserson, and Ronald L. Rivest, MIT Press.

2. Understanding the Linux Kernel, 3rd Edition, Daniel P. Bovet, Marco Cesati, O'Reilly.

3. Linux Kernel 2.6.19 source code.

[ 本帖最后由 Godbach 于 2009-2-25 16:34 編輯 ]

Godbach

轉(zhuǎn)過來一篇介紹內(nèi)核中紅黑樹接口的文章。

scutan

學(xué)習(xí)了，謝謝版主。

Godbach

呵呵，這兩天因為要使用，所以得研究一下。大家一起交流。

Godbach

如果哪位朋友使用內(nèi)核的紅黑樹接口寫了一些程序，方便的話拿上來大家一起學(xué)習(xí)一下

Godbach

2.4.20內(nèi)核中使用紅黑樹的好像就mmap等。2.6中使用的更廣泛一些

emmoblin

紅黑樹在內(nèi)核中有很多應(yīng)用。
數(shù)據(jù)庫中也應(yīng)用的很多

Godbach

是啊。emmoblin兄對這方面有研究吧，什么時候分享一下。

platinum

內(nèi)核 QoS 的 HTB 分層令牌桶用了 RBTREE，Godbach 可以參考一下

dreamice

rbtree現(xiàn)在用得越來越廣了，連進(jìn)程調(diào)度都使用了紅黑樹，前面學(xué)了一下，看來還需要深入掌握這個東西。