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