ngx_rbtree.c revision e18a033b
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
18static ngx_inline void ngx_rbtree_left_rotate(ngx_rbtree_node_t **root,
19    ngx_rbtree_node_t *sentinel, ngx_rbtree_node_t *node);
20static 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
24void
25ngx_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
96void
97ngx_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
121void
122ngx_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
156void
157ngx_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
323static ngx_inline void
324ngx_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
353static ngx_inline void
354ngx_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
383ngx_rbtree_node_t *
384ngx_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