Mercurial > hg > nginx

comparison src/core/ngx_rbtree.c @ 205:4a9a2b1dd6fa

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