Mercurial > hg > nginx
comparison src/core/ngx_rbtree.c @ 207:6e0fef527732
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 |