Mercurial > hg > nginx-ranges

comparison src/core/ngx_rbtree.c @ 0:f0b350454894 NGINX_0_1_0

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
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 }