xref: /unit/src/test/nxt_rbtree1.c (revision 2673:08b48a5ad55d)
1 
2 /*
3  * Copyright (C) Igor Sysoev
4  * Copyright (C) NGINX, Inc.
5  */
6 
7 
8 #include <nxt_main.h>
9 #include "nxt_rbtree1.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 nxt_inline void nxt_rbtree1_left_rotate(nxt_rbtree1_node_t **root,
19     nxt_rbtree1_node_t *sentinel, nxt_rbtree1_node_t *node);
20 nxt_inline void nxt_rbtree1_right_rotate(nxt_rbtree1_node_t **root,
21     nxt_rbtree1_node_t *sentinel, nxt_rbtree1_node_t *node);
22 
23 
24 void
nxt_rbtree1_insert(nxt_rbtree1_t * tree,nxt_rbtree1_node_t * node)25 nxt_rbtree1_insert(nxt_rbtree1_t *tree, nxt_rbtree1_node_t *node)
26 {
27     nxt_rbtree1_node_t  **root, *temp, *sentinel;
28 
29     /* a binary tree insert */
30 
31     root = (nxt_rbtree1_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         nxt_rbtree1_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 && nxt_rbtree1_is_red(node->parent)) {
49 
50         if (node->parent == node->parent->parent->left) {
51             temp = node->parent->parent->right;
52 
53             if (nxt_rbtree1_is_red(temp)) {
54                 nxt_rbtree1_black(node->parent);
55                 nxt_rbtree1_black(temp);
56                 nxt_rbtree1_red(node->parent->parent);
57                 node = node->parent->parent;
58 
59             } else {
60                 if (node == node->parent->right) {
61                     node = node->parent;
62                     nxt_rbtree1_left_rotate(root, sentinel, node);
63                 }
64 
65                 nxt_rbtree1_black(node->parent);
66                 nxt_rbtree1_red(node->parent->parent);
67                 nxt_rbtree1_right_rotate(root, sentinel, node->parent->parent);
68             }
69 
70         } else {
71             temp = node->parent->parent->left;
72 
73             if (nxt_rbtree1_is_red(temp)) {
74                 nxt_rbtree1_black(node->parent);
75                 nxt_rbtree1_black(temp);
76                 nxt_rbtree1_red(node->parent->parent);
77                 node = node->parent->parent;
78 
79             } else {
80                 if (node == node->parent->left) {
81                     node = node->parent;
82                     nxt_rbtree1_right_rotate(root, sentinel, node);
83                 }
84 
85                 nxt_rbtree1_black(node->parent);
86                 nxt_rbtree1_red(node->parent->parent);
87                 nxt_rbtree1_left_rotate(root, sentinel, node->parent->parent);
88             }
89         }
90     }
91 
92     nxt_rbtree1_black(*root);
93 }
94 
95 
96 void
nxt_rbtree1_insert_value(nxt_rbtree1_node_t * temp,nxt_rbtree1_node_t * node,nxt_rbtree1_node_t * sentinel)97 nxt_rbtree1_insert_value(nxt_rbtree1_node_t *temp, nxt_rbtree1_node_t *node,
98     nxt_rbtree1_node_t *sentinel)
99 {
100     nxt_rbtree1_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     nxt_rbtree1_red(node);
118 }
119 
120 
121 void
nxt_rbtree1_insert_timer_value(nxt_rbtree1_node_t * temp,nxt_rbtree1_node_t * node,nxt_rbtree1_node_t * sentinel)122 nxt_rbtree1_insert_timer_value(nxt_rbtree1_node_t *temp,
123     nxt_rbtree1_node_t *node, nxt_rbtree1_node_t *sentinel)
124 {
125     nxt_rbtree1_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 = ((nxt_rbtree1_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     nxt_rbtree1_red(node);
153 }
154 
155 
156 void
nxt_rbtree1_delete(nxt_rbtree1_t * tree,nxt_rbtree1_node_t * node)157 nxt_rbtree1_delete(nxt_rbtree1_t *tree, nxt_rbtree1_node_t *node)
158 {
159     nxt_uint_t      red;
160     nxt_rbtree1_node_t  **root, *sentinel, *subst, *temp, *w;
161 
162     /* a binary tree delete */
163 
164     root = (nxt_rbtree1_node_t **) &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 = nxt_rbtree1_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         nxt_rbtree1_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 = nxt_rbtree1_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         nxt_rbtree1_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 && nxt_rbtree1_is_black(temp)) {
258 
259         if (temp == temp->parent->left) {
260             w = temp->parent->right;
261 
262             if (nxt_rbtree1_is_red(w)) {
263                 nxt_rbtree1_black(w);
264                 nxt_rbtree1_red(temp->parent);
265                 nxt_rbtree1_left_rotate(root, sentinel, temp->parent);
266                 w = temp->parent->right;
267             }
268 
269             if (nxt_rbtree1_is_black(w->left) && nxt_rbtree1_is_black(w->right))
270             {
271                 nxt_rbtree1_red(w);
272                 temp = temp->parent;
273 
274             } else {
275                 if (nxt_rbtree1_is_black(w->right)) {
276                     nxt_rbtree1_black(w->left);
277                     nxt_rbtree1_red(w);
278                     nxt_rbtree1_right_rotate(root, sentinel, w);
279                     w = temp->parent->right;
280                 }
281 
282                 nxt_rbtree1_copy_color(w, temp->parent);
283                 nxt_rbtree1_black(temp->parent);
284                 nxt_rbtree1_black(w->right);
285                 nxt_rbtree1_left_rotate(root, sentinel, temp->parent);
286                 temp = *root;
287             }
288 
289         } else {
290             w = temp->parent->left;
291 
292             if (nxt_rbtree1_is_red(w)) {
293                 nxt_rbtree1_black(w);
294                 nxt_rbtree1_red(temp->parent);
295                 nxt_rbtree1_right_rotate(root, sentinel, temp->parent);
296                 w = temp->parent->left;
297             }
298 
299             if (nxt_rbtree1_is_black(w->left) && nxt_rbtree1_is_black(w->right))
300             {
301                 nxt_rbtree1_red(w);
302                 temp = temp->parent;
303 
304             } else {
305                 if (nxt_rbtree1_is_black(w->left)) {
306                     nxt_rbtree1_black(w->right);
307                     nxt_rbtree1_red(w);
308                     nxt_rbtree1_left_rotate(root, sentinel, w);
309                     w = temp->parent->left;
310                 }
311 
312                 nxt_rbtree1_copy_color(w, temp->parent);
313                 nxt_rbtree1_black(temp->parent);
314                 nxt_rbtree1_black(w->left);
315                 nxt_rbtree1_right_rotate(root, sentinel, temp->parent);
316                 temp = *root;
317             }
318         }
319     }
320 
321     nxt_rbtree1_black(temp);
322 }
323 
324 
325 nxt_inline void
nxt_rbtree1_left_rotate(nxt_rbtree1_node_t ** root,nxt_rbtree1_node_t * sentinel,nxt_rbtree1_node_t * node)326 nxt_rbtree1_left_rotate(nxt_rbtree1_node_t **root, nxt_rbtree1_node_t *sentinel,
327     nxt_rbtree1_node_t *node)
328 {
329     nxt_rbtree1_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 nxt_inline void
nxt_rbtree1_right_rotate(nxt_rbtree1_node_t ** root,nxt_rbtree1_node_t * sentinel,nxt_rbtree1_node_t * node)356 nxt_rbtree1_right_rotate(nxt_rbtree1_node_t **root,
357     nxt_rbtree1_node_t *sentinel, nxt_rbtree1_node_t *node)
358 {
359     nxt_rbtree1_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