Mercurial > hg > nginx

comparison src/core/ngx_rbtree.c @ 207:6e0fef527732

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
nginx-0.0.1-2003-12-05-20:07:27 import
author Igor Sysoev <igor@sysoev.ru>
date Fri, 05 Dec 2003 17:07:27 +0000
parents 9aa426375256
children 679f60139863
comparison
equal deleted inserted replaced
206:9aa426375256 207:6e0fef527732
13 #define ngx_rbt_is_red(node) ((node)->color) 13 #define ngx_rbt_is_red(node) ((node)->color)
14 #define ngx_rbt_is_black(node) (!ngx_rbt_is_red(node)) 14 #define ngx_rbt_is_black(node) (!ngx_rbt_is_red(node))
15 #define ngx_rbt_copy_color(n1, n2) (n1->color = n2->color) 15 #define ngx_rbt_copy_color(n1, n2) (n1->color = n2->color)
16 16
17 17
18 ngx_inline void ngx_rbtree_left_rotate(ngx_rbtree_t **root, ngx_rbtree_t *node); 18 ngx_inline void ngx_rbtree_left_rotate(ngx_rbtree_t **root,
19 ngx_rbtree_t *sentinel,
20 ngx_rbtree_t *node);
19 ngx_inline void ngx_rbtree_right_rotate(ngx_rbtree_t **root, 21 ngx_inline void ngx_rbtree_right_rotate(ngx_rbtree_t **root,
22 ngx_rbtree_t *sentinel,
20 ngx_rbtree_t *node); 23 ngx_rbtree_t *node);
21 24
22 ngx_rbtree_t sentinel; 25
23 26 void ngx_rbtree_insert(ngx_rbtree_t **root, ngx_rbtree_t *sentinel,
24 27 ngx_rbtree_t *node)
25 void ngx_rbtree_insert(ngx_rbtree_t **root, ngx_rbtree_t *node)
26 { 28 {
27 ngx_rbtree_t *temp; 29 ngx_rbtree_t *temp;
28 30
29 /* a binary tree insert */ 31 /* a binary tree insert */
30 32
31 if (*root == &sentinel) { 33 if (*root == sentinel) {
32 node->parent = &sentinel; 34 node->parent = sentinel;
33 node->left = &sentinel; 35 node->left = sentinel;
34 node->right = &sentinel; 36 node->right = sentinel;
35 ngx_rbt_black(node); 37 ngx_rbt_black(node);
36 *root = node; 38 *root = node;
37 39
38 return; 40 return;
39 } 41 }
40 42
41 temp = *root; 43 temp = *root;
42 44
43 for ( ;; ) { 45 for ( ;; ) {
44 if (node->key < temp->key) { 46 if (node->key < temp->key) {
45 if (temp->left == &sentinel) { 47 if (temp->left == sentinel) {
46 temp->left = node; 48 temp->left = node;
47 break; 49 break;
48 } 50 }
49 51
50 temp = temp->left; 52 temp = temp->left;
51 continue; 53 continue;
52 } 54 }
53 55
54 if (temp->right == &sentinel) { 56 if (temp->right == sentinel) {
55 temp->right = node; 57 temp->right = node;
56 break; 58 break;
57 } 59 }
58 60
59 temp = temp->right; 61 temp = temp->right;
60 continue; 62 continue;
61 } 63 }
62 64
63 node->parent = temp; 65 node->parent = temp;
64 node->left = &sentinel; 66 node->left = sentinel;
65 node->right = &sentinel; 67 node->right = sentinel;
66 68
67 69
68 /* re-balance tree */ 70 /* re-balance tree */
69 71
70 ngx_rbt_red(node); 72 ngx_rbt_red(node);
81 node = node->parent->parent; 83 node = node->parent->parent;
82 84
83 } else { 85 } else {
84 if (node == node->parent->right) { 86 if (node == node->parent->right) {
85 node = node->parent; 87 node = node->parent;
86 ngx_rbtree_left_rotate(root, node); 88 ngx_rbtree_left_rotate(root, sentinel, node);
87 } 89 }
88 90
89 ngx_rbt_black(node->parent); 91 ngx_rbt_black(node->parent);
90 ngx_rbt_red(node->parent->parent); 92 ngx_rbt_red(node->parent->parent);
91 ngx_rbtree_right_rotate(root, node->parent->parent); 93 ngx_rbtree_right_rotate(root, sentinel, node->parent->parent);
92 } 94 }
93 95
94 } else { 96 } else {
95 temp = node->parent->parent->left; 97 temp = node->parent->parent->left;
96 98
101 node = node->parent->parent; 103 node = node->parent->parent;
102 104
103 } else { 105 } else {
104 if (node == node->parent->left) { 106 if (node == node->parent->left) {
105 node = node->parent; 107 node = node->parent;
106 ngx_rbtree_right_rotate(root, node); 108 ngx_rbtree_right_rotate(root, sentinel, node);
107 } 109 }
108 110
109 ngx_rbt_black(node->parent); 111 ngx_rbt_black(node->parent);
110 ngx_rbt_red(node->parent->parent); 112 ngx_rbt_red(node->parent->parent);
111 ngx_rbtree_left_rotate(root, node->parent->parent); 113 ngx_rbtree_left_rotate(root, sentinel, node->parent->parent);
112 } 114 }
113 } 115 }
114 116
115 } 117 }
116 118
117 ngx_rbt_black(*root); 119 ngx_rbt_black(*root);
118 } 120 }
119 121
120 122
121 void ngx_rbtree_delete(ngx_rbtree_t **root, ngx_rbtree_t *node) 123 void ngx_rbtree_delete(ngx_rbtree_t **root, ngx_rbtree_t *sentinel,
124 ngx_rbtree_t *node)
122 { 125 {
123 ngx_rbtree_t *subst, *temp, *w; 126 ngx_rbtree_t *subst, *temp, *w;
124 127
125 /* a binary tree delete */ 128 /* a binary tree delete */
126 129
127 if (node->left == &sentinel || node->right == &sentinel) { 130 if (node->left == sentinel || node->right == sentinel) {
128 subst = node; 131 subst = node;
129 132
130 } else { 133 } else {
131 134
132 /* find a node successor */ 135 /* find a node successor */
133 136
134 if (node->right == &sentinel) { 137 if (node->right == sentinel) {
135 temp = node; 138 temp = node;
136 subst = node->parent; 139 subst = node->parent;
137 140
138 while (subst != &sentinel && temp == subst->right) { 141 while (subst != sentinel && temp == subst->right) {
139 temp = subst; 142 temp = subst;
140 subst = subst->parent; 143 subst = subst->parent;
141 } 144 }
142 145
143 } else { 146 } else {
144 subst = ngx_rbtree_min(node->right); 147 subst = ngx_rbtree_min(node->right, sentinel);
145 } 148 }
146 } 149 }
147 150
148 if (subst->left != &sentinel) { 151 if (subst->left != sentinel) {
149 temp = subst->left; 152 temp = subst->left;
150 } else { 153 } else {
151 temp = subst->right; 154 temp = subst->right;
152 } 155 }
153 156
154 temp->parent = subst->parent; 157 temp->parent = subst->parent;
155 158
156 if (subst->parent == &sentinel) { 159 if (subst->parent == sentinel) {
157 *root = temp; 160 *root = temp;
158 161
159 } else if (subst == subst->parent->left) { 162 } else if (subst == subst->parent->left) {
160 subst->parent->left = temp; 163 subst->parent->left = temp;
161 164
172 return; 175 return;
173 } 176 }
174 177
175 /* a delete fixup */ 178 /* a delete fixup */
176 179
177 while (temp->parent != &sentinel && ngx_rbt_is_black(temp)) { 180 while (temp->parent != sentinel && ngx_rbt_is_black(temp)) {
178 if (temp == temp->parent->left) { 181 if (temp == temp->parent->left) {
179 w = temp->parent->right; 182 w = temp->parent->right;
180 183
181 if (ngx_rbt_is_red(w)) { 184 if (ngx_rbt_is_red(w)) {
182 ngx_rbt_black(w); 185 ngx_rbt_black(w);
183 ngx_rbt_red(temp->parent); 186 ngx_rbt_red(temp->parent);
184 ngx_rbtree_left_rotate(root, temp->parent); 187 ngx_rbtree_left_rotate(root, sentinel, temp->parent);
185 w = temp->parent->right; 188 w = temp->parent->right;
186 } 189 }
187 190
188 if (ngx_rbt_is_black(w->left) && ngx_rbt_is_black(w->right)) { 191 if (ngx_rbt_is_black(w->left) && ngx_rbt_is_black(w->right)) {
189 ngx_rbt_red(w); 192 ngx_rbt_red(w);
191 194
192 } else { 195 } else {
193 if (ngx_rbt_is_black(w->right)) { 196 if (ngx_rbt_is_black(w->right)) {
194 ngx_rbt_black(w->left); 197 ngx_rbt_black(w->left);
195 ngx_rbt_red(w); 198 ngx_rbt_red(w);
196 ngx_rbtree_right_rotate(root, w); 199 ngx_rbtree_right_rotate(root, sentinel, w);
197 w = temp->parent->right; 200 w = temp->parent->right;
198 } 201 }
199 202
200 ngx_rbt_copy_color(w, temp->parent); 203 ngx_rbt_copy_color(w, temp->parent);
201 ngx_rbt_black(temp->parent); 204 ngx_rbt_black(temp->parent);
202 ngx_rbt_black(w->right); 205 ngx_rbt_black(w->right);
203 ngx_rbtree_left_rotate(root, temp->parent); 206 ngx_rbtree_left_rotate(root, sentinel, temp->parent);
204 temp = *root; 207 temp = *root;
205 } 208 }
206 209
207 } else { 210 } else {
208 w = temp->parent->left; 211 w = temp->parent->left;
209 212
210 if (ngx_rbt_is_red(w)) { 213 if (ngx_rbt_is_red(w)) {
211 ngx_rbt_black(w); 214 ngx_rbt_black(w);
212 ngx_rbt_red(temp->parent); 215 ngx_rbt_red(temp->parent);
213 ngx_rbtree_right_rotate(root, temp->parent); 216 ngx_rbtree_right_rotate(root, sentinel, temp->parent);
214 w = temp->parent->left; 217 w = temp->parent->left;
215 } 218 }
216 219
217 if (ngx_rbt_is_black(w->right) && ngx_rbt_is_black(w->left)) { 220 if (ngx_rbt_is_black(w->right) && ngx_rbt_is_black(w->left)) {
218 ngx_rbt_red(w); 221 ngx_rbt_red(w);
220 223
221 } else { 224 } else {
222 if (ngx_rbt_is_black(w->left)) { 225 if (ngx_rbt_is_black(w->left)) {
223 ngx_rbt_black(w->right); 226 ngx_rbt_black(w->right);
224 ngx_rbt_red(w); 227 ngx_rbt_red(w);
225 ngx_rbtree_left_rotate(root, w); 228 ngx_rbtree_left_rotate(root, sentinel, w);
226 w = temp->parent->left; 229 w = temp->parent->left;
227 } 230 }
228 231
229 ngx_rbt_copy_color(w, temp->parent); 232 ngx_rbt_copy_color(w, temp->parent);
230 ngx_rbt_black(temp->parent); 233 ngx_rbt_black(temp->parent);
231 ngx_rbt_black(w->left); 234 ngx_rbt_black(w->left);
232 ngx_rbtree_right_rotate(root, temp->parent); 235 ngx_rbtree_right_rotate(root, sentinel, temp->parent);
233 temp = *root; 236 temp = *root;
234 } 237 }
235 } 238 }
236 } 239 }
237 240
238 ngx_rbt_black(temp); 241 ngx_rbt_black(temp);
239 } 242 }
240 243
241 244
242 ngx_inline void ngx_rbtree_left_rotate(ngx_rbtree_t **root, ngx_rbtree_t *node) 245 ngx_inline void ngx_rbtree_left_rotate(ngx_rbtree_t **root,
246 ngx_rbtree_t *sentinel,
247 ngx_rbtree_t *node)
243 { 248 {
244 ngx_rbtree_t *temp; 249 ngx_rbtree_t *temp;
245 250
246 temp = node->right; 251 temp = node->right;
247 node->right = temp->left; 252 node->right = temp->left;
248 253
249 if (temp->left != &sentinel) { 254 if (temp->left != sentinel) {
250 temp->left->parent = node; 255 temp->left->parent = node;
251 } 256 }
252 257
253 temp->parent = node->parent; 258 temp->parent = node->parent;
254 259
255 if (node->parent == &sentinel) { 260 if (node->parent == sentinel) {
256 *root = temp; 261 *root = temp;
257 262
258 } else if (node == node->parent->left) { 263 } else if (node == node->parent->left) {
259 node->parent->left = temp; 264 node->parent->left = temp;
260 265
265 temp->left = node; 270 temp->left = node;
266 node->parent = temp; 271 node->parent = temp;
267 } 272 }
268 273
269 274
270 ngx_inline void ngx_rbtree_right_rotate(ngx_rbtree_t **root, ngx_rbtree_t *node) 275 ngx_inline void ngx_rbtree_right_rotate(ngx_rbtree_t **root,
276 ngx_rbtree_t *sentinel,
277 ngx_rbtree_t *node)
271 { 278 {
272 ngx_rbtree_t *temp; 279 ngx_rbtree_t *temp;
273 280
274 temp = node->left; 281 temp = node->left;
275 node->left = temp->right; 282 node->left = temp->right;
276 283
277 if (temp->right != &sentinel) { 284 if (temp->right != sentinel) {
278 temp->right->parent = node; 285 temp->right->parent = node;
279 } 286 }
280 287
281 temp->parent = node->parent; 288 temp->parent = node->parent;
282 289
283 if (node->parent == &sentinel) { 290 if (node->parent == sentinel) {
284 *root = temp; 291 *root = temp;
285 292
286 } else if (node == node->parent->right) { 293 } else if (node == node->parent->right) {
287 node->parent->right = temp; 294 node->parent->right = temp;
288 295