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