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 red-black tree code is based on the algorithm described in
13 * the "Introduction to Algorithms" by Cormen, Leiserson and Rivest.
14 */
15
16
17 static ngx_inline void ngx_rbtree_left_rotate(ngx_rbtree_node_t **root,
18 ngx_rbtree_node_t *sentinel, ngx_rbtree_node_t *node);
19 static ngx_inline void ngx_rbtree_right_rotate(ngx_rbtree_node_t **root,
20 ngx_rbtree_node_t *sentinel, ngx_rbtree_node_t *node);
21
22
23 void
24 ngx_rbtree_insert(ngx_thread_volatile ngx_rbtree_t *tree,
25 ngx_rbtree_node_t *node)
26 {
27 ngx_rbtree_node_t **root, *temp, *sentinel;
28
29 /* a binary tree insert */
30
31 root = (ngx_rbtree_node_t **) &tree->root;
32 sentinel = tree->sentinel;
33
34 if (*root == sentinel) {
35 node->parent = NULL;
36 node->left = sentinel;
37 node->right = sentinel;
38 ngx_rbt_black(node);
39 *root = node;
40
41 return;
42 }
43
44 tree->insert(*root, node, sentinel);
45
46 /* re-balance tree */
47
48 while (node != *root && ngx_rbt_is_red(node->parent)) {
49
50 if (node->parent == node->parent->parent->left) {
51 temp = node->parent->parent->right;
52
53 if (ngx_rbt_is_red(temp)) {
54 ngx_rbt_black(node->parent);
55 ngx_rbt_black(temp);
56 ngx_rbt_red(node->parent->parent);
57 node = node->parent->parent;
58
59 } else {
60 if (node == node->parent->right) {
61 node = node->parent;
62 ngx_rbtree_left_rotate(root, sentinel, node);
63 }
64
65 ngx_rbt_black(node->parent);
66 ngx_rbt_red(node->parent->parent);
67 ngx_rbtree_right_rotate(root, sentinel, node->parent->parent);
68 }
69
70 } else {
71 temp = node->parent->parent->left;
72
73 if (ngx_rbt_is_red(temp)) {
74 ngx_rbt_black(node->parent);
75 ngx_rbt_black(temp);
76 ngx_rbt_red(node->parent->parent);
77 node = node->parent->parent;
78
79 } else {
80 if (node == node->parent->left) {
81 node = node->parent;
82 ngx_rbtree_right_rotate(root, sentinel, node);
83 }
84
85 ngx_rbt_black(node->parent);
86 ngx_rbt_red(node->parent->parent);
87 ngx_rbtree_left_rotate(root, sentinel, node->parent->parent);
88 }
89 }
90 }
91
92 ngx_rbt_black(*root);
93 }
94
95
96 void
97 ngx_rbtree_insert_value(ngx_rbtree_node_t *temp, ngx_rbtree_node_t *node,
98 ngx_rbtree_node_t *sentinel)
99 {
100 ngx_rbtree_node_t **p;
101
102 for ( ;; ) {
103
104 p = (node->key < temp->key) ? &temp->left : &temp->right;
105
106 if (*p == sentinel) {
107 break;
108 }
109
110 temp = *p;
111 }
112
113 *p = node;
114 node->parent = temp;
115 node->left = sentinel;
116 node->right = sentinel;
117 ngx_rbt_red(node);
118 }
119
120
121 void
122 ngx_rbtree_insert_timer_value(ngx_rbtree_node_t *temp, ngx_rbtree_node_t *node,
123 ngx_rbtree_node_t *sentinel)
124 {
125 ngx_rbtree_node_t **p;
126
127 for ( ;; ) {
128
129 /*
130 * Timer values
131 * 1) are spread in small range, usually several minutes,
132 * 2) and overflow each 49 days, if milliseconds are stored in 32 bits.
133 * The comparison takes into account that overflow.
134 */
135
136 /* node->key < temp->key */
137
138 p = ((ngx_rbtree_key_int_t) node->key - (ngx_rbtree_key_int_t) temp->key
139 < 0)
140 ? &temp->left : &temp->right;
141
142 if (*p == sentinel) {
143 break;
144 }
145
146 temp = *p;
147 }
148
149 *p = node;
150 node->parent = temp;
151 node->left = sentinel;
152 node->right = sentinel;
153 ngx_rbt_red(node);
154 }
155
156
157 void
158 ngx_rbtree_delete(ngx_thread_volatile ngx_rbtree_t *tree,
159 ngx_rbtree_node_t *node)
160 {
161 ngx_uint_t red;
162 ngx_rbtree_node_t **root, *sentinel, *subst, *temp, *w;
163
164 /* a binary tree delete */
165
166 root = (ngx_rbtree_node_t **) &tree->root;
167 sentinel = tree->sentinel;
168
169 if (node->left == sentinel) {
170 temp = node->right;
171 subst = node;
172
173 } else if (node->right == sentinel) {
174 temp = node->left;
175 subst = node;
176
177 } else {
178 subst = ngx_rbtree_min(node->right, sentinel);
179
180 if (subst->left != sentinel) {
181 temp = subst->left;
182 } else {
183 temp = subst->right;
184 }
185 }
186
187 if (subst == *root) {
188 *root = temp;
189 ngx_rbt_black(temp);
190
191 /* DEBUG stuff */
192 node->left = NULL;
193 node->right = NULL;
194 node->parent = NULL;
195 node->key = 0;
196
197 return;
198 }
199
200 red = ngx_rbt_is_red(subst);
201
202 if (subst == subst->parent->left) {
203 subst->parent->left = temp;
204
205 } else {
206 subst->parent->right = temp;
207 }
208
209 if (subst == node) {
210
211 temp->parent = subst->parent;
212
213 } else {
214
215 if (subst->parent == node) {
216 temp->parent = subst;
217
218 } else {
219 temp->parent = subst->parent;
220 }
221
222 subst->left = node->left;
223 subst->right = node->right;
224 subst->parent = node->parent;
225 ngx_rbt_copy_color(subst, node);
226
227 if (node == *root) {
228 *root = subst;
229
230 } else {
231 if (node == node->parent->left) {
232 node->parent->left = subst;
233 } else {
234 node->parent->right = subst;
235 }
236 }
237
238 if (subst->left != sentinel) {
239 subst->left->parent = subst;
240 }
241
242 if (subst->right != sentinel) {
243 subst->right->parent = subst;
244 }
245 }
246
247 /* DEBUG stuff */
248 node->left = NULL;
249 node->right = NULL;
250 node->parent = NULL;
251 node->key = 0;
252
253 if (red) {
254 return;
255 }
256
257 /* a delete fixup */
258
259 while (temp != *root && ngx_rbt_is_black(temp)) {
260
261 if (temp == temp->parent->left) {
262 w = temp->parent->right;
263
264 if (ngx_rbt_is_red(w)) {
265 ngx_rbt_black(w);
266 ngx_rbt_red(temp->parent);
267 ngx_rbtree_left_rotate(root, sentinel, temp->parent);
268 w = temp->parent->right;
269 }
270
271 if (ngx_rbt_is_black(w->left) && ngx_rbt_is_black(w->right)) {
272 ngx_rbt_red(w);
273 temp = temp->parent;
274
275 } else {
276 if (ngx_rbt_is_black(w->right)) {
277 ngx_rbt_black(w->left);
278 ngx_rbt_red(w);
279 ngx_rbtree_right_rotate(root, sentinel, w);
280 w = temp->parent->right;
281 }
282
283 ngx_rbt_copy_color(w, temp->parent);
284 ngx_rbt_black(temp->parent);
285 ngx_rbt_black(w->right);
286 ngx_rbtree_left_rotate(root, sentinel, temp->parent);
287 temp = *root;
288 }
289
290 } else {
291 w = temp->parent->left;
292
293 if (ngx_rbt_is_red(w)) {
294 ngx_rbt_black(w);
295 ngx_rbt_red(temp->parent);
296 ngx_rbtree_right_rotate(root, sentinel, temp->parent);
297 w = temp->parent->left;
298 }
299
300 if (ngx_rbt_is_black(w->left) && ngx_rbt_is_black(w->right)) {
301 ngx_rbt_red(w);
302 temp = temp->parent;
303
304 } else {
305 if (ngx_rbt_is_black(w->left)) {
306 ngx_rbt_black(w->right);
307 ngx_rbt_red(w);
308 ngx_rbtree_left_rotate(root, sentinel, w);
309 w = temp->parent->left;
310 }
311
312 ngx_rbt_copy_color(w, temp->parent);
313 ngx_rbt_black(temp->parent);
314 ngx_rbt_black(w->left);
315 ngx_rbtree_right_rotate(root, sentinel, temp->parent);
316 temp = *root;
317 }
318 }
319 }
320
321 ngx_rbt_black(temp);
322 }
323
324
325 static ngx_inline void
326 ngx_rbtree_left_rotate(ngx_rbtree_node_t **root, ngx_rbtree_node_t *sentinel,
327 ngx_rbtree_node_t *node)
328 {
329 ngx_rbtree_node_t *temp;
330
331 temp = node->right;
332 node->right = temp->left;
333
334 if (temp->left != sentinel) {
335 temp->left->parent = node;
336 }
337
338 temp->parent = node->parent;
339
340 if (node == *root) {
341 *root = temp;
342
343 } else if (node == node->parent->left) {
344 node->parent->left = temp;
345
346 } else {
347 node->parent->right = temp;
348 }
349
350 temp->left = node;
351 node->parent = temp;
352 }
353
354
355 static ngx_inline void
356 ngx_rbtree_right_rotate(ngx_rbtree_node_t **root, ngx_rbtree_node_t *sentinel,
357 ngx_rbtree_node_t *node)
358 {
359 ngx_rbtree_node_t *temp;
360
361 temp = node->left;
362 node->left = temp->right;
363
364 if (temp->right != sentinel) {
365 temp->right->parent = node;
366 }
367
368 temp->parent = node->parent;
369
370 if (node == *root) {
371 *root = temp;
372
373 } else if (node == node->parent->right) {
374 node->parent->right = temp;
375
376 } else {
377 node->parent->left = temp;
378 }
379
380 temp->right = node;
381 node->parent = temp;
382 }
383
This page was automatically generated by the
LXR engine.
Visit the LXR main site for more
information.