Mercurial > hg > nginx-ranges
comparison src/core/ngx_rbtree.c @ 0:f0b350454894 NGINX_0_1_0
nginx 0.1.0
*) The first public version.
author | Igor Sysoev <http://sysoev.ru> |
---|---|
date | Mon, 04 Oct 2004 00:00:00 +0400 |
parents | |
children | 74b1868dd3cd |
comparison
equal
deleted
inserted
replaced
-1:000000000000 | 0:f0b350454894 |
---|---|
1 | |
2 /* | |
3 * Copyright (C) Igor Sysoev | |
4 */ | |
5 | |
6 | |
7 #include <ngx_config.h> | |
8 #include <ngx_core.h> | |
9 | |
10 | |
11 /* | |
12 * The code is based on the algorithm described in the "Introduction | |
13 * to Algorithms" by Cormen, Leiserson and Rivest. | |
14 */ | |
15 | |
16 #define ngx_rbt_red(node) ((node)->color = 1) | |
17 #define ngx_rbt_black(node) ((node)->color = 0) | |
18 #define ngx_rbt_is_red(node) ((node)->color) | |
19 #define ngx_rbt_is_black(node) (!ngx_rbt_is_red(node)) | |
20 #define ngx_rbt_copy_color(n1, n2) (n1->color = n2->color) | |
21 | |
22 | |
23 ngx_inline void ngx_rbtree_left_rotate(ngx_rbtree_t **root, | |
24 ngx_rbtree_t *sentinel, | |
25 ngx_rbtree_t *node); | |
26 ngx_inline void ngx_rbtree_right_rotate(ngx_rbtree_t **root, | |
27 ngx_rbtree_t *sentinel, | |
28 ngx_rbtree_t *node); | |
29 | |
30 | |
31 void ngx_rbtree_insert(ngx_rbtree_t **root, ngx_rbtree_t *sentinel, | |
32 ngx_rbtree_t *node) | |
33 { | |
34 ngx_rbtree_t *temp; | |
35 | |
36 /* a binary tree insert */ | |
37 | |
38 if (*root == sentinel) { | |
39 node->parent = NULL; | |
40 node->left = sentinel; | |
41 node->right = sentinel; | |
42 ngx_rbt_black(node); | |
43 *root = node; | |
44 | |
45 return; | |
46 } | |
47 | |
48 temp = *root; | |
49 | |
50 for ( ;; ) { | |
51 if (node->key < temp->key) { | |
52 if (temp->left == sentinel) { | |
53 temp->left = node; | |
54 break; | |
55 } | |
56 | |
57 temp = temp->left; | |
58 continue; | |
59 } | |
60 | |
61 if (temp->right == sentinel) { | |
62 temp->right = node; | |
63 break; | |
64 } | |
65 | |
66 temp = temp->right; | |
67 continue; | |
68 } | |
69 | |
70 node->parent = temp; | |
71 node->left = sentinel; | |
72 node->right = sentinel; | |
73 | |
74 | |
75 /* re-balance tree */ | |
76 | |
77 ngx_rbt_red(node); | |
78 | |
79 while (node != *root && ngx_rbt_is_red(node->parent)) { | |
80 | |
81 if (node->parent == node->parent->parent->left) { | |
82 temp = node->parent->parent->right; | |
83 | |
84 if (ngx_rbt_is_red(temp)) { | |
85 ngx_rbt_black(node->parent); | |
86 ngx_rbt_black(temp); | |
87 ngx_rbt_red(node->parent->parent); | |
88 node = node->parent->parent; | |
89 | |
90 } else { | |
91 if (node == node->parent->right) { | |
92 node = node->parent; | |
93 ngx_rbtree_left_rotate(root, sentinel, node); | |
94 } | |
95 | |
96 ngx_rbt_black(node->parent); | |
97 ngx_rbt_red(node->parent->parent); | |
98 ngx_rbtree_right_rotate(root, sentinel, node->parent->parent); | |
99 } | |
100 | |
101 } else { | |
102 temp = node->parent->parent->left; | |
103 | |
104 if (ngx_rbt_is_red(temp)) { | |
105 ngx_rbt_black(node->parent); | |
106 ngx_rbt_black(temp); | |
107 ngx_rbt_red(node->parent->parent); | |
108 node = node->parent->parent; | |
109 | |
110 } else { | |
111 if (node == node->parent->left) { | |
112 node = node->parent; | |
113 ngx_rbtree_right_rotate(root, sentinel, node); | |
114 } | |
115 | |
116 ngx_rbt_black(node->parent); | |
117 ngx_rbt_red(node->parent->parent); | |
118 ngx_rbtree_left_rotate(root, sentinel, node->parent->parent); | |
119 } | |
120 } | |
121 | |
122 } | |
123 | |
124 ngx_rbt_black(*root); | |
125 } | |
126 | |
127 | |
128 void ngx_rbtree_delete(ngx_rbtree_t **root, ngx_rbtree_t *sentinel, | |
129 ngx_rbtree_t *node) | |
130 { | |
131 ngx_int_t is_red; | |
132 ngx_rbtree_t *subst, *temp, *w; | |
133 | |
134 /* a binary tree delete */ | |
135 | |
136 if (node->left == sentinel) { | |
137 temp = node->right; | |
138 subst = node; | |
139 | |
140 } else if (node->right == sentinel) { | |
141 temp = node->left; | |
142 subst = node; | |
143 | |
144 } else { | |
145 subst = ngx_rbtree_min(node->right, sentinel); | |
146 | |
147 if (subst->left != sentinel) { | |
148 temp = subst->left; | |
149 } else { | |
150 temp = subst->right; | |
151 } | |
152 } | |
153 | |
154 if (subst == *root) { | |
155 *root = temp; | |
156 ngx_rbt_black(temp); | |
157 | |
158 /* DEBUG stuff */ | |
159 node->left = NULL; | |
160 node->right = NULL; | |
161 node->parent = NULL; | |
162 node->key = 0; | |
163 | |
164 return; | |
165 } | |
166 | |
167 is_red = ngx_rbt_is_red(subst); | |
168 | |
169 if (subst == subst->parent->left) { | |
170 subst->parent->left = temp; | |
171 | |
172 } else { | |
173 subst->parent->right = temp; | |
174 } | |
175 | |
176 if (subst == node) { | |
177 | |
178 temp->parent = subst->parent; | |
179 | |
180 } else { | |
181 | |
182 if (subst->parent == node) { | |
183 temp->parent = subst; | |
184 | |
185 } else { | |
186 temp->parent = subst->parent; | |
187 } | |
188 | |
189 subst->left = node->left; | |
190 subst->right = node->right; | |
191 subst->parent = node->parent; | |
192 ngx_rbt_copy_color(subst, node); | |
193 | |
194 if (node == *root) { | |
195 *root = subst; | |
196 | |
197 } else { | |
198 if (node == node->parent->left) { | |
199 node->parent->left = subst; | |
200 } else { | |
201 node->parent->right = subst; | |
202 } | |
203 } | |
204 | |
205 if (subst->left != sentinel) { | |
206 subst->left->parent = subst; | |
207 } | |
208 | |
209 if (subst->right != sentinel) { | |
210 subst->right->parent = subst; | |
211 } | |
212 | |
213 /* DEBUG stuff */ | |
214 node->left = NULL; | |
215 node->right = NULL; | |
216 node->parent = NULL; | |
217 node->key = 0; | |
218 } | |
219 | |
220 if (is_red) { | |
221 return; | |
222 } | |
223 | |
224 /* a delete fixup */ | |
225 | |
226 while (temp != *root && ngx_rbt_is_black(temp)) { | |
227 | |
228 if (temp == temp->parent->left) { | |
229 w = temp->parent->right; | |
230 | |
231 if (ngx_rbt_is_red(w)) { | |
232 ngx_rbt_black(w); | |
233 ngx_rbt_red(temp->parent); | |
234 ngx_rbtree_left_rotate(root, sentinel, temp->parent); | |
235 w = temp->parent->right; | |
236 } | |
237 | |
238 if (ngx_rbt_is_black(w->left) && ngx_rbt_is_black(w->right)) { | |
239 ngx_rbt_red(w); | |
240 temp = temp->parent; | |
241 | |
242 } else { | |
243 if (ngx_rbt_is_black(w->right)) { | |
244 ngx_rbt_black(w->left); | |
245 ngx_rbt_red(w); | |
246 ngx_rbtree_right_rotate(root, sentinel, w); | |
247 w = temp->parent->right; | |
248 } | |
249 | |
250 ngx_rbt_copy_color(w, temp->parent); | |
251 ngx_rbt_black(temp->parent); | |
252 ngx_rbt_black(w->right); | |
253 ngx_rbtree_left_rotate(root, sentinel, temp->parent); | |
254 temp = *root; | |
255 } | |
256 | |
257 } else { | |
258 w = temp->parent->left; | |
259 | |
260 if (ngx_rbt_is_red(w)) { | |
261 ngx_rbt_black(w); | |
262 ngx_rbt_red(temp->parent); | |
263 ngx_rbtree_right_rotate(root, sentinel, temp->parent); | |
264 w = temp->parent->left; | |
265 } | |
266 | |
267 if (ngx_rbt_is_black(w->left) && ngx_rbt_is_black(w->right)) { | |
268 ngx_rbt_red(w); | |
269 temp = temp->parent; | |
270 | |
271 } else { | |
272 if (ngx_rbt_is_black(w->left)) { | |
273 ngx_rbt_black(w->right); | |
274 ngx_rbt_red(w); | |
275 ngx_rbtree_left_rotate(root, sentinel, w); | |
276 w = temp->parent->left; | |
277 } | |
278 | |
279 ngx_rbt_copy_color(w, temp->parent); | |
280 ngx_rbt_black(temp->parent); | |
281 ngx_rbt_black(w->left); | |
282 ngx_rbtree_right_rotate(root, sentinel, temp->parent); | |
283 temp = *root; | |
284 } | |
285 } | |
286 } | |
287 | |
288 ngx_rbt_black(temp); | |
289 } | |
290 | |
291 | |
292 ngx_inline void ngx_rbtree_left_rotate(ngx_rbtree_t **root, | |
293 ngx_rbtree_t *sentinel, | |
294 ngx_rbtree_t *node) | |
295 { | |
296 ngx_rbtree_t *temp; | |
297 | |
298 temp = node->right; | |
299 node->right = temp->left; | |
300 | |
301 if (temp->left != sentinel) { | |
302 temp->left->parent = node; | |
303 } | |
304 | |
305 temp->parent = node->parent; | |
306 | |
307 if (node == *root) { | |
308 *root = temp; | |
309 | |
310 } else if (node == node->parent->left) { | |
311 node->parent->left = temp; | |
312 | |
313 } else { | |
314 node->parent->right = temp; | |
315 } | |
316 | |
317 temp->left = node; | |
318 node->parent = temp; | |
319 } | |
320 | |
321 | |
322 ngx_inline void ngx_rbtree_right_rotate(ngx_rbtree_t **root, | |
323 ngx_rbtree_t *sentinel, | |
324 ngx_rbtree_t *node) | |
325 { | |
326 ngx_rbtree_t *temp; | |
327 | |
328 temp = node->left; | |
329 node->left = temp->right; | |
330 | |
331 if (temp->right != sentinel) { | |
332 temp->right->parent = node; | |
333 } | |
334 | |
335 temp->parent = node->parent; | |
336 | |
337 if (node == *root) { | |
338 *root = temp; | |
339 | |
340 } else if (node == node->parent->right) { | |
341 node->parent->right = temp; | |
342 | |
343 } else { | |
344 node->parent->left = temp; | |
345 } | |
346 | |
347 temp->right = node; | |
348 node->parent = temp; | |
349 } |