新秀nginx源代码分析数据结构篇（四）红黑树ngx_rbtree_t

全栈程序员站长

发布于 2022-07-06 09:47:24

3300

发布于 2022-07-06 09:47:24

文章被收录于专栏：全栈程序员必看

大家好，又见面了，我是全栈君。

新秀nginx源代码分析数据结构篇（四）红黑树ngx_rbtree_t

Author：Echo Chen（陈斌）
Email：chenb19870707@gmail.com
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: }

假设有相等的结点。会直接被覆盖，如上图插入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未牵涉到内存池，所以很easy抽出来使用，例如以下为实现了插入、打印最小值、删除的样例 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: } 执行结果：