1
2 /*
3 * Copyright (C) Igor Sysoev
4 * Copyright (C) Nginx, Inc.
5 */
6
7
8 #include <ngx_config.h>
9 #include <ngx_core.h>
10
11
12 /*
13 * The red-black tree code is based on the algorithm described in
14 * the "Introduction to Algorithms" by Cormen, Leiserson and Rivest.
15 */
16
17
18 static ngx_inline void ngx_rbtree_left_rotate(ngx_rbtree_node_t **root,
19 ngx_rbtree_node_t *sentinel, ngx_rbtree_node_t *node);
20 static ngx_inline void ngx_rbtree_right_rotate(ngx_rbtree_node_t **root,
21 ngx_rbtree_node_t *sentinel, ngx_rbtree_node_t *node);
22
23
24 void
ngx_rbtree_insert(ngx_rbtree_t * tree,ngx_rbtree_node_t * node)25 ngx_rbtree_insert(ngx_rbtree_t *tree, ngx_rbtree_node_t *node)
26 {
27 ngx_rbtree_node_t **root, *temp, *sentinel;
28
29 /* a binary tree insert */
30
31 root = &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
ngx_rbtree_insert_value(ngx_rbtree_node_t * temp,ngx_rbtree_node_t * node,ngx_rbtree_node_t * sentinel)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
ngx_rbtree_insert_timer_value(ngx_rbtree_node_t * temp,ngx_rbtree_node_t * node,ngx_rbtree_node_t * sentinel)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 - temp->key) < 0)
139 ? &temp->left : &temp->right;
140
141 if (*p == sentinel) {
142 break;
143 }
144
145 temp = *p;
146 }
147
148 *p = node;
149 node->parent = temp;
150 node->left = sentinel;
151 node->right = sentinel;
152 ngx_rbt_red(node);
153 }
154
155
156 void
ngx_rbtree_delete(ngx_rbtree_t * tree,ngx_rbtree_node_t * node)157 ngx_rbtree_delete(ngx_rbtree_t *tree, ngx_rbtree_node_t *node)
158 {
159 ngx_uint_t red;
160 ngx_rbtree_node_t **root, *sentinel, *subst, *temp, *w;
161
162 /* a binary tree delete */
163
164 root = &tree->root;
165 sentinel = tree->sentinel;
166
167 if (node->left == sentinel) {
168 temp = node->right;
169 subst = node;
170
171 } else if (node->right == sentinel) {
172 temp = node->left;
173 subst = node;
174
175 } else {
176 subst = ngx_rbtree_min(node->right, sentinel);
177
178 if (subst->left != sentinel) {
179 temp = subst->left;
180 } else {
181 temp = subst->right;
182 }
183 }
184
185 if (subst == *root) {
186 *root = temp;
187 ngx_rbt_black(temp);
188
189 /* DEBUG stuff */
190 node->left = NULL;
191 node->right = NULL;
192 node->parent = NULL;
193 node->key = 0;
194
195 return;
196 }
197
198 red = ngx_rbt_is_red(subst);
199
200 if (subst == subst->parent->left) {
201 subst->parent->left = temp;
202
203 } else {
204 subst->parent->right = temp;
205 }
206
207 if (subst == node) {
208
209 temp->parent = subst->parent;
210
211 } else {
212
213 if (subst->parent == node) {
214 temp->parent = subst;
215
216 } else {
217 temp->parent = subst->parent;
218 }
219
220 subst->left = node->left;
221 subst->right = node->right;
222 subst->parent = node->parent;
223 ngx_rbt_copy_color(subst, node);
224
225 if (node == *root) {
226 *root = subst;
227
228 } else {
229 if (node == node->parent->left) {
230 node->parent->left = subst;
231 } else {
232 node->parent->right = subst;
233 }
234 }
235
236 if (subst->left != sentinel) {
237 subst->left->parent = subst;
238 }
239
240 if (subst->right != sentinel) {
241 subst->right->parent = subst;
242 }
243 }
244
245 /* DEBUG stuff */
246 node->left = NULL;
247 node->right = NULL;
248 node->parent = NULL;
249 node->key = 0;
250
251 if (red) {
252 return;
253 }
254
255 /* a delete fixup */
256
257 while (temp != *root && ngx_rbt_is_black(temp)) {
258
259 if (temp == temp->parent->left) {
260 w = temp->parent->right;
261
262 if (ngx_rbt_is_red(w)) {
263 ngx_rbt_black(w);
264 ngx_rbt_red(temp->parent);
265 ngx_rbtree_left_rotate(root, sentinel, temp->parent);
266 w = temp->parent->right;
267 }
268
269 if (ngx_rbt_is_black(w->left) && ngx_rbt_is_black(w->right)) {
270 ngx_rbt_red(w);
271 temp = temp->parent;
272
273 } else {
274 if (ngx_rbt_is_black(w->right)) {
275 ngx_rbt_black(w->left);
276 ngx_rbt_red(w);
277 ngx_rbtree_right_rotate(root, sentinel, w);
278 w = temp->parent->right;
279 }
280
281 ngx_rbt_copy_color(w, temp->parent);
282 ngx_rbt_black(temp->parent);
283 ngx_rbt_black(w->right);
284 ngx_rbtree_left_rotate(root, sentinel, temp->parent);
285 temp = *root;
286 }
287
288 } else {
289 w = temp->parent->left;
290
291 if (ngx_rbt_is_red(w)) {
292 ngx_rbt_black(w);
293 ngx_rbt_red(temp->parent);
294 ngx_rbtree_right_rotate(root, sentinel, temp->parent);
295 w = temp->parent->left;
296 }
297
298 if (ngx_rbt_is_black(w->left) && ngx_rbt_is_black(w->right)) {
299 ngx_rbt_red(w);
300 temp = temp->parent;
301
302 } else {
303 if (ngx_rbt_is_black(w->left)) {
304 ngx_rbt_black(w->right);
305 ngx_rbt_red(w);
306 ngx_rbtree_left_rotate(root, sentinel, w);
307 w = temp->parent->left;
308 }
309
310 ngx_rbt_copy_color(w, temp->parent);
311 ngx_rbt_black(temp->parent);
312 ngx_rbt_black(w->left);
313 ngx_rbtree_right_rotate(root, sentinel, temp->parent);
314 temp = *root;
315 }
316 }
317 }
318
319 ngx_rbt_black(temp);
320 }
321
322
323 static ngx_inline void
ngx_rbtree_left_rotate(ngx_rbtree_node_t ** root,ngx_rbtree_node_t * sentinel,ngx_rbtree_node_t * node)324 ngx_rbtree_left_rotate(ngx_rbtree_node_t **root, ngx_rbtree_node_t *sentinel,
325 ngx_rbtree_node_t *node)
326 {
327 ngx_rbtree_node_t *temp;
328
329 temp = node->right;
330 node->right = temp->left;
331
332 if (temp->left != sentinel) {
333 temp->left->parent = node;
334 }
335
336 temp->parent = node->parent;
337
338 if (node == *root) {
339 *root = temp;
340
341 } else if (node == node->parent->left) {
342 node->parent->left = temp;
343
344 } else {
345 node->parent->right = temp;
346 }
347
348 temp->left = node;
349 node->parent = temp;
350 }
351
352
353 static ngx_inline void
ngx_rbtree_right_rotate(ngx_rbtree_node_t ** root,ngx_rbtree_node_t * sentinel,ngx_rbtree_node_t * node)354 ngx_rbtree_right_rotate(ngx_rbtree_node_t **root, ngx_rbtree_node_t *sentinel,
355 ngx_rbtree_node_t *node)
356 {
357 ngx_rbtree_node_t *temp;
358
359 temp = node->left;
360 node->left = temp->right;
361
362 if (temp->right != sentinel) {
363 temp->right->parent = node;
364 }
365
366 temp->parent = node->parent;
367
368 if (node == *root) {
369 *root = temp;
370
371 } else if (node == node->parent->right) {
372 node->parent->right = temp;
373
374 } else {
375 node->parent->left = temp;
376 }
377
378 temp->right = node;
379 node->parent = temp;
380 }
381
382
383 ngx_rbtree_node_t *
ngx_rbtree_next(ngx_rbtree_t * tree,ngx_rbtree_node_t * node)384 ngx_rbtree_next(ngx_rbtree_t *tree, ngx_rbtree_node_t *node)
385 {
386 ngx_rbtree_node_t *root, *sentinel, *parent;
387
388 sentinel = tree->sentinel;
389
390 if (node->right != sentinel) {
391 return ngx_rbtree_min(node->right, sentinel);
392 }
393
394 root = tree->root;
395
396 for ( ;; ) {
397 parent = node->parent;
398
399 if (node == root) {
400 return NULL;
401 }
402
403 if (node == parent->left) {
404 return parent;
405 }
406
407 node = parent;
408 }
409 }
410