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