菜鳥nginx源碼剖析資料結構篇（四）紅黑樹ngx_rbtree_t

Author：Echo Chen（陳斌）
Email：[email protected]
Blog：Blog.csdn.net/chen19870707

Date：October 27h, 2014

1.ngx_rbtree優勢和特點

ngx_rbtree是一種使用紅黑樹實作的關聯容器，關于紅黑樹的特性，在《手把手實作紅黑樹》已經詳細介紹，這裡就隻探讨ngx_rbtree與衆不同的地方；ngx_rbtree紅黑樹容器中的元素都是有序的，支援快速索引，插入，删除操作，也支援範圍查詢，周遊操作，應用非常廣泛。

2.源代碼位置

頭檔案：http://trac.nginx.org/nginx/browser/nginx/src/core/ngx_rbtree.h

源檔案：http://trac.nginx.org/nginx/browser/nginx/src/core/ngx_rbtree.c

3.資料結構定義

可以看到ngx_rbtree的結點ngx_rbtree_node_t結構跟一般的紅黑樹差不多，都是由鍵值key、左孩子left、右孩子right、父親結點parent、顔色值color，不同的是ngx_rbtree_node_t這裡多了一個data，但根據官方文檔記在，由于data隻有一個位元組，表示太少，很少使用到。

1: typedef struct ngx_rbtree_node_s  ngx_rbtree_node_t;

2:

3: struct ngx_rbtree_node_s {

4:     ngx_rbtree_key_t       key;

5:     ngx_rbtree_node_t     *left;

6:     ngx_rbtree_node_t     *right;

7:     ngx_rbtree_node_t     *parent;

8:     u_char                 color;

9:     u_char                 data;

10: };

ngx_rbtree_t的結構也與一般紅黑樹相同，右root結點和哨兵葉子結點（sentinel）組成，不同的是這裡多了一個函數指針inserter，它決定了在添加結點是新加還是替換。

1: typedef struct ngx_rbtree_s  ngx_rbtree_t;

2:

3: typedef void (*ngx_rbtree_insert_pt) (ngx_rbtree_node_t *root,

4:     ngx_rbtree_node_t *node, ngx_rbtree_node_t *sentinel);

5:

6: struct ngx_rbtree_s {

7:     ngx_rbtree_node_t     *root;

8:     ngx_rbtree_node_t     *sentinel;

9:     ngx_rbtree_insert_pt   insert;

10: };

4.ngx_rbtree初始化 ngx_rbtree_init

其中tree為ngx_rbtree_t類型，即為紅黑樹，s為ngx_rbtree_node_t，是rbtree的根節點，i即為上節提到的決定插入是新結點還是替換的函數指針。首先将根節點塗成黑色（紅黑樹基本性質），然後把紅黑樹的根節點和哨兵結點都指向這個結點。

1: #define ngx_rbtree_init(tree, s, i)                                           \

2:     ngx_rbtree_sentinel_init(s);                                              \

3:     (tree)->root = s;                                                         \

4:     (tree)->sentinel = s;                                                     \

5:     (tree)->insert = i

6:

7: #define ngx_rbtree_sentinel_init(node)  ngx_rbt_black(node)

5.ngx_rbtree 左旋 ngx_rbtree_left_rotate 和右旋 ngx_rbtree_right_rotate

可以看到，經典代碼總是永恒的，ngx_rbtree的左旋右旋也是參考《算法導論》導論中的步驟和僞代碼，對照我自己的實作的《手把手實作紅黑樹》，與我自己實作的左旋右旋代碼基本一緻，我圖解了詳細的過程，有不清楚的可以參考《手把手實作紅黑樹》。

1: static ngx_inline void

2: ngx_rbtree_left_rotate(ngx_rbtree_node_t **root, ngx_rbtree_node_t *sentinel,

3:     ngx_rbtree_node_t *node)

4: {

5:     ngx_rbtree_node_t  *temp;

6:

7:     temp = node->right;

8:     node->right = temp->left;

9:

10:     if (temp->left != sentinel) {

11:         temp->left->parent = node;

12:     }

13:

14:     temp->parent = node->parent;

15:

16:     if (node == *root) {

17:         *root = temp;

18:

19:     } else if (node == node->parent->left) {

20:         node->parent->left = temp;

21:

22:     } else {

23:         node->parent->right = temp;

24:     }

25:

26:     temp->left = node;

27:     node->parent = temp;

28: }

1: static ngx_inline void

2: ngx_rbtree_right_rotate(ngx_rbtree_node_t **root, ngx_rbtree_node_t *sentinel,

3:     ngx_rbtree_node_t *node)

4: {

5:     ngx_rbtree_node_t  *temp;

6:

7:     temp = node->left;

8:     node->left = temp->right;

9:

10:     if (temp->right != sentinel) {

11:         temp->right->parent = node;

12:     }

13:

14:     temp->parent = node->parent;

15:

16:     if (node == *root) {

17:         *root = temp;

18:

19:     } else if (node == node->parent->right) {

20:         node->parent->right = temp;

21:

22:     } else {

23:         node->parent->left = temp;

24:     }

25:

26:     temp->right = node;

27:     node->parent = temp;

28: }

6.ngx_rbtree插入 ngx_rbtree_insert

ngx_rbtree_insert也是分為兩步，插入和調整，由于這兩項都在《手把手實作紅黑樹》中做了詳細解釋，這裡就不在啰嗦，這裡值得一提的是，還記得node_rbtree_t 結構中的insert指針嗎？這裡就是通過這個函數指針來實作的插入。一個小小的技巧就實作了多态；并且它給出了唯一值和時間類型的key 插入方法，可以滿足一般需求，使用者也可以實作自己的插入方法。

void
ngx_rbtree_insert(ngx_thread_volatile ngx_rbtree_t *tree,
    ngx_rbtree_node_t *node)
{
    ngx_rbtree_node_t  **root, *temp, *sentinel;

    /* a binary tree insert */

    root = (ngx_rbtree_node_t **) &tree->root;
    sentinel = tree->sentinel;

    if (*root == sentinel) {
        node->parent = NULL;
        node->left = sentinel;
        node->right = sentinel;
        ngx_rbt_black(node);
        *root = node;

        return;
    }

    tree->insert(*root, node, sentinel);

    /* re-balance tree */

    while (node != *root && ngx_rbt_is_red(node->parent)) {

        if (node->parent == node->parent->parent->left) {
            temp = node->parent->parent->right;

            if (ngx_rbt_is_red(temp)) {
                ngx_rbt_black(node->parent);
                ngx_rbt_black(temp);
                ngx_rbt_red(node->parent->parent);
                node = node->parent->parent;

            } else {
                if (node == node->parent->right) {
                    node = node->parent;
                    ngx_rbtree_left_rotate(root, sentinel, node);
                }

                ngx_rbt_black(node->parent);
                ngx_rbt_red(node->parent->parent);
                ngx_rbtree_right_rotate(root, sentinel, node->parent->parent);
            }

        } else {
            temp = node->parent->parent->left;

            if (ngx_rbt_is_red(temp)) {
                ngx_rbt_black(node->parent);
                ngx_rbt_black(temp);
                ngx_rbt_red(node->parent->parent);
                node = node->parent->parent;

            } else {
                if (node == node->parent->left) {
                    node = node->parent;
                    ngx_rbtree_right_rotate(root, sentinel, node);
                }

                ngx_rbt_black(node->parent);
                ngx_rbt_red(node->parent->parent);
                ngx_rbtree_left_rotate(root, sentinel, node->parent->parent);
            }
        }
    }

    ngx_rbt_black(*root);
}

6.1 唯一值類型插入

這個即為一般紅黑樹的插入方法，循環，如果插入的值比目前節點小，就進入左子樹，否則進入右子樹，直至遇到葉子結點，葉子節點就是要鍊入紅黑樹的位置。

1: void

2: ngx_rbtree_insert_value(ngx_rbtree_node_t *temp, ngx_rbtree_node_t *node,

3:     ngx_rbtree_node_t *sentinel)

4: {

5:     ngx_rbtree_node_t  **p;

6:

7:     for ( ;; ) {

8:

9:         p = (node->key < temp->key) ? &temp->left : &temp->right;

10:

11:         if (*p == sentinel) {

12:             break;

13:         }

14:

15:         temp = *p;

16:     }

17:

18:     *p = node;

19:     node->parent = temp;

20:     node->left = sentinel;

21:     node->right = sentinel;

22:     ngx_rbt_red(node);

23: }

菜鳥nginx源碼剖析資料結構篇（四）紅黑樹ngx_rbtree_t

如果有相等的結點，會直接被覆寫，如上圖插入key為2的結點，則當tmp 為2的結點時，p為葉子周遊結束，這樣p就會被覆寫為新的值。

6.2 唯一時間類型插入

唯一差別就是判斷大小時，采用了兩個值相減，避免溢出。

1: typedef ngx_int_t   ngx_rbtree_key_int_t;

2: void

3: ngx_rbtree_insert_timer_value(ngx_rbtree_node_t *temp, ngx_rbtree_node_t *node,

4:     ngx_rbtree_node_t *sentinel)

5: {

6:     ngx_rbtree_node_t  **p;

7:

8:     for ( ;; ) {

9:

10:         /*

11:          * Timer values

12:          * 1) are spread in small range, usually several minutes,

13:          * 2) and overflow each 49 days, if milliseconds are stored in 32 bits.

14:          * The comparison takes into account that overflow.

15:          */

16:

17:         /*  node->key < temp->key */

18:

19:         p = ((ngx_rbtree_key_int_t) (node->key - temp->key) < 0)

20:             ? &temp->left : &temp->right;

21:

22:         if (*p == sentinel) {

23:             break;

24:         }

25:

26:         temp = *p;

27:     }

28:

29:     *p = node;

30:     node->parent = temp;

31:     node->left = sentinel;

32:     node->right = sentinel;

33:     ngx_rbt_red(node);

34: }

7.ngx_rbtree删除ngx_rbtree_delete

也是按照《算法導論》上的步驟，先删除後調整，在《手把手實作紅黑樹》已介紹，請參考

1: void

2: ngx_rbtree_delete_delete(ngx_thread_volatile ngx_rbtree_t *tree,

3:     ngx_rbtree_node_t *node)

4: {

5:     ngx_uint_t           red;

6:     ngx_rbtree_node_t  **root, *sentinel, *subst, *temp, *w;

7:

8:     /* a binary tree delete */

9:

10:     root = (ngx_rbtree_node_t **) &tree->root;

11:     sentinel = tree->sentinel;

12:

13:     if (node->left == sentinel) {

14:         temp = node->right;

15:         subst = node;

16:

17:     } else if (node->right == sentinel) {

18:         temp = node->left;

19:         subst = node;

20:

21:     } else {

22:         subst = ngx_rbtree_min(node->right, sentinel);

23:

24:         if (subst->left != sentinel) {

25:             temp = subst->left;

26:         } else {

27:             temp = subst->right;

28:         }

29:     }

30:

31:     if (subst == *root) {

32:         *root = temp;

33:         ngx_rbt_black(temp);

34:

35:         /* DEBUG stuff */

36:         node->left = NULL;

37:         node->right = NULL;

38:         node->parent = NULL;

39:         node->key = 0;

40:

41:         return;

42:     }

43:

44:     red = ngx_rbt_is_red(subst);

45:

46:     if (subst == subst->parent->left) {

47:         subst->parent->left = temp;

48:

49:     } else {

50:         subst->parent->right = temp;

51:     }

52:

53:     if (subst == node) {

54:

55:         temp->parent = subst->parent;

56:

57:     } else {

58:

59:         if (subst->parent == node) {

60:             temp->parent = subst;

61:

62:         } else {

63:             temp->parent = subst->parent;

64:         }

65:

66:         subst->left = node->left;

67:         subst->right = node->right;

68:         subst->parent = node->parent;

69:         ngx_rbt_copy_color(subst, node);

70:

71:         if (node == *root) {

72:             *root = subst;

73:

74:         } else {

75:             if (node == node->parent->left) {

76:                 node->parent->left = subst;

77:             } else {

78:                 node->parent->right = subst;

79:             }

80:         }

81:

82:         if (subst->left != sentinel) {

83:             subst->left->parent = subst;

84:         }

85:

86:         if (subst->right != sentinel) {

87:             subst->right->parent = subst;

88:         }

89:     }

90:

91:     /* DEBUG stuff */

92:     node->left = NULL;

93:     node->right = NULL;

94:     node->parent = NULL;

95:     node->key = 0;

96:

97:     if (red) {

98:         return;

99:     }

100:

101:     /* a delete fixup */

102:

103:     while (temp != *root && ngx_rbt_is_black(temp)) {

104:

105:         if (temp == temp->parent->left) {

106:             w = temp->parent->right;

107:

108:             if (ngx_rbt_is_red(w)) {

109:                 ngx_rbt_black(w);

110:                 ngx_rbt_red(temp->parent);

111:                 ngx_rbtree_left_rotate(root, sentinel, temp->parent);

112:                 w = temp->parent->right;

113:             }

114:

115:             if (ngx_rbt_is_black(w->left) && ngx_rbt_is_black(w->right)) {

116:                 ngx_rbt_red(w);

117:                 temp = temp->parent;

118:

119:             } else {

120:                 if (ngx_rbt_is_black(w->right)) {

121:                     ngx_rbt_black(w->left);

122:                     ngx_rbt_red(w);

123:                     ngx_rbtree_right_rotate(root, sentinel, w);

124:                     w = temp->parent->right;

125:                 }

126:

127:                 ngx_rbt_copy_color(w, temp->parent);

128:                 ngx_rbt_black(temp->parent);

129:                 ngx_rbt_black(w->right);

130:                 ngx_rbtree_left_rotate(root, sentinel, temp->parent);

131:                 temp = *root;

132:             }

133:

134:         } else {

135:             w = temp->parent->left;

136:

137:             if (ngx_rbt_is_red(w)) {

138:                 ngx_rbt_black(w);

139:                 ngx_rbt_red(temp->parent);

140:                 ngx_rbtree_right_rotate(root, sentinel, temp->parent);

141:                 w = temp->parent->left;

142:             }

143:

144:             if (ngx_rbt_is_black(w->left) && ngx_rbt_is_black(w->right)) {

145:                 ngx_rbt_red(w);

146:                 temp = temp->parent;

147:

148:             } else {

149:                 if (ngx_rbt_is_black(w->left)) {

150:                     ngx_rbt_black(w->right);

151:                     ngx_rbt_red(w);

152:                     ngx_rbtree_left_rotate(root, sentinel, w);

153:                     w = temp->parent->left;

154:                 }

155:

156:                 ngx_rbt_copy_color(w, temp->parent);

157:                 ngx_rbt_black(temp->parent);

158:                 ngx_rbt_black(w->left);

159:                 ngx_rbtree_right_rotate(root, sentinel, temp->parent);

160:                 temp = *root;

161:             }

162:         }

163:     }

164:

165:     ngx_rbt_black(temp);

166: }

8.實戰

由于ngx_rbtree_t未牽涉到記憶體池，是以非常容易抽出來使用，如下為實作了插入、列印最小值、删除的例子

1: #include <iostream>

2: #include <algorithm>

3: #include <pthread.h>

4: #include <time.h>

5: #include <stdio.h>

6: #include <errno.h>

7: #include <string.h>

8: #include "ngx_queue.h"

9: #include "ngx_rbtree.h"

10:

11:

12: int main()

13: {

14:

15:     ngx_rbtree_t tree;

16:     ngx_rbtree_node_t sentinel;

17:

18:     ngx_rbtree_init(&tree,&sentinel,ngx_rbtree_insert_value);

19:

20:     ngx_rbtree_node_t *rbnode = new ngx_rbtree_node_t[100];

21:     for(int i = 99; i >= 0 ;i--)

22:     {

23:         rbnode[i].key = i;

24:         rbnode[i].parent = NULL;

25:         rbnode[i].left = NULL;

26:         rbnode[i].right = NULL;

27:         ngx_rbtree_insert(&tree,&rbnode[i]);

28:     }

29:

30:     for(int i = 0; i < 100;i++)

31:     {

32:          ngx_rbtree_node_t *p = ngx_rbtree_min(tree.root,&sentinel);

33:          std::cout << p->key << "  ";

34:          ngx_rbtree_delete(&tree,p);

35:      }

36:

37:

38:     delete[] rbnode;

39:

40:     return 0;

41: }

運作結果：

菜鳥nginx源碼剖析資料結構篇（四）紅黑樹ngx_rbtree_t

Echo Chen：Blog.csdn.net/chen19870707

菜鳥nginx源碼剖析資料結構篇（四）紅黑樹ngx_rbtree_t

1.ngx_rbtree優勢和特點

2.源代碼位置

3.資料結構定義

4.ngx_rbtree初始化 ngx_rbtree_init

5.ngx_rbtree 左旋 ngx_rbtree_left_rotate 和右旋 ngx_rbtree_right_rotate

6.ngx_rbtree插入 ngx_rbtree_insert

6.1 唯一值類型插入

6.2 唯一時間類型插入

7.ngx_rbtree删除ngx_rbtree_delete

8.實戰

繼續閱讀

swmm與lisflood-fp源碼如何一起編譯 CMake指令

Windows下VS開發環境環境安裝工程項目設定關于Debug和Release的提示

一文看懂字元串的加減乘除

Ubuntu修改nginx将多個域名分别配置到伺服器不同端口

C++ 第十五周報告1--《冒泡法排序》

C++實作簡單順序表

修改or隐藏nginx版本号

Nginx安全改動：隐藏Nginx版本号背景解決serve_tokens指令參考

版本号隐藏

Nginx服務優化（版本隐藏、版本号僞裝、逾時管理、程序管理、日志分割）Nginx服務優化未完待續

nginx location中斜線的位置的重要性

C經典書籍筆記——C陷阱與缺陷②(文法陷阱之優先級)一、錯誤案列二、優先級規律

線性表之順序表的實作

C++判斷素數、求最大公約數代碼判斷一個數是否為素數求兩個數的最大公約數

SequoiaDB巨杉資料庫C++驅動概述

菜鳥nginx源碼剖析資料結構篇（四）紅黑樹ngx_rbtree_t

1.ngx_rbtree優勢和特點

2.源代碼位置

3.資料結構定義

4.ngx_rbtree初始化 ngx_rbtree_init

5.ngx_rbtree 左旋 ngx_rbtree_left_rotate 和 右旋 ngx_rbtree_right_rotate

6.ngx_rbtree插入 ngx_rbtree_insert

6.1 唯一值類型插入

6.2 唯一時間類型插入

7.ngx_rbtree删除ngx_rbtree_delete

8.實戰

繼續閱讀

5.ngx_rbtree 左旋 ngx_rbtree_left_rotate 和右旋 ngx_rbtree_right_rotate