xref: /unit/src/nxt_rbtree.c (revision 48:3f9e9cf9b09b)
1 
2 /*
3  * Copyright (C) Igor Sysoev
4  * Copyright (C) NGINX, Inc.
5  */
6 
7 #include <nxt_main.h>
8 
9 
10 /*
11  * The red-black tree code is based on the algorithm described in
12  * the "Introduction to Algorithms" by Cormen, Leiserson and Rivest.
13  */
14 
15 
16 static void nxt_rbtree_insert_fixup(nxt_rbtree_node_t *node);
17 static void nxt_rbtree_delete_fixup(nxt_rbtree_t *tree,
18     nxt_rbtree_node_t *node);
19 nxt_inline void nxt_rbtree_left_rotate(nxt_rbtree_node_t *node);
20 nxt_inline void nxt_rbtree_right_rotate(nxt_rbtree_node_t *node);
21 nxt_inline void nxt_rbtree_parent_relink(nxt_rbtree_node_t *subst,
22     nxt_rbtree_node_t *node);
23 
24 
25 #define NXT_RBTREE_BLACK  0
26 #define NXT_RBTREE_RED    1
27 
28 
29 #define nxt_rbtree_comparison_callback(tree)                                  \
30     ((nxt_rbtree_compare_t) (tree)->sentinel.right)
31 
32 
33 void
34 nxt_rbtree_init(nxt_rbtree_t *tree, nxt_rbtree_compare_t compare)
35 {
36     /*
37      * The sentinel is used as a leaf node sentinel and as a tree root
38      * sentinel: it is a parent of a root node and the root node is
39      * the left child of the sentinel.  Combining two sentinels in one
40      * entry and the fact that the sentinel's left child is a root node
41      * simplifies nxt_rbtree_node_successor() and eliminates explicit
42      * root node test before or inside nxt_rbtree_min().
43      */
44 
45     /* The root is empty. */
46     tree->sentinel.left = &tree->sentinel;
47 
48     /*
49      * The sentinel's right child is never used so
50      * comparison callback can be safely stored here.
51      */
52     tree->sentinel.right = (void *) compare;
53 
54     /* The root and leaf sentinel must be black. */
55     tree->sentinel.color = NXT_RBTREE_BLACK;
56 }
57 
58 
59 void
60 nxt_rbtree_insert(nxt_rbtree_t *tree, nxt_rbtree_part_t *part)
61 {
62     nxt_rbtree_node_t     *node, *new_node, *sentinel, **child;
63     nxt_rbtree_compare_t  compare;
64 
65     new_node = (nxt_rbtree_node_t *) part;
66 
67     node = nxt_rbtree_root(tree);
68     sentinel = nxt_rbtree_sentinel(tree);
69 
70     new_node->left = sentinel;
71     new_node->right = sentinel;
72     new_node->color = NXT_RBTREE_RED;
73 
74     compare = (nxt_rbtree_compare_t) tree->sentinel.right;
75     child = &nxt_rbtree_root(tree);
76 
77     while (*child != sentinel) {
78         node = *child;
79 
80         nxt_prefetch(node->left);
81         nxt_prefetch(node->right);
82 
83         child = (compare(new_node, node) < 0) ? &node->left : &node->right;
84     }
85 
86     *child = new_node;
87     new_node->parent = node;
88 
89     nxt_rbtree_insert_fixup(new_node);
90 
91     node = nxt_rbtree_root(tree);
92     node->color = NXT_RBTREE_BLACK;
93 }
94 
95 
96 static void
97 nxt_rbtree_insert_fixup(nxt_rbtree_node_t *node)
98 {
99     nxt_rbtree_node_t  *parent, *grandparent, *uncle;
100 
101     /*
102      * Prefetching parent nodes does not help here because they are
103      * already traversed during insertion.
104      */
105 
106     for ( ;; ) {
107         parent = node->parent;
108 
109         /*
110          * Testing whether a node is a tree root is not required here since
111          * a root node's parent is the sentinel and it is always black.
112          */
113         if (parent->color == NXT_RBTREE_BLACK) {
114             return;
115         }
116 
117         grandparent = parent->parent;
118 
119         if (parent == grandparent->left) {
120             uncle = grandparent->right;
121 
122             if (uncle->color == NXT_RBTREE_BLACK) {
123 
124                 if (node == parent->right) {
125                     node = parent;
126                     nxt_rbtree_left_rotate(node);
127                 }
128 
129                 /*
130                  * nxt_rbtree_left_rotate() swaps parent and
131                  * child whilst keeps grandparent the same.
132                  */
133                 parent = node->parent;
134 
135                 parent->color = NXT_RBTREE_BLACK;
136                 grandparent->color = NXT_RBTREE_RED;
137 
138                 nxt_rbtree_right_rotate(grandparent);
139                 /*
140                  * nxt_rbtree_right_rotate() does not change node->parent
141                  * color which is now black, so testing color is not required
142                  * to return from function.
143                  */
144                 return;
145             }
146 
147         } else {
148             uncle = grandparent->left;
149 
150             if (uncle->color == NXT_RBTREE_BLACK) {
151 
152                 if (node == parent->left) {
153                     node = parent;
154                     nxt_rbtree_right_rotate(node);
155                 }
156 
157                 /* See the comment in the symmetric branch above. */
158                 parent = node->parent;
159 
160                 parent->color = NXT_RBTREE_BLACK;
161                 grandparent->color = NXT_RBTREE_RED;
162 
163                 nxt_rbtree_left_rotate(grandparent);
164 
165                 /* See the comment in the symmetric branch above. */
166                 return;
167             }
168         }
169 
170         uncle->color = NXT_RBTREE_BLACK;
171         parent->color = NXT_RBTREE_BLACK;
172         grandparent->color = NXT_RBTREE_RED;
173 
174         node = grandparent;
175     }
176 }
177 
178 
179 nxt_rbtree_node_t *
180 nxt_rbtree_find(nxt_rbtree_t *tree, nxt_rbtree_part_t *part)
181 {
182     intptr_t              n;
183     nxt_rbtree_node_t     *node, *next, *sentinel;
184     nxt_rbtree_compare_t  compare;
185 
186     node = (nxt_rbtree_node_t *) part;
187 
188     next = nxt_rbtree_root(tree);
189     sentinel = nxt_rbtree_sentinel(tree);
190     compare = nxt_rbtree_comparison_callback(tree);
191 
192     while (next != sentinel) {
193         nxt_prefetch(next->left);
194         nxt_prefetch(next->right);
195 
196         n = compare(node, next);
197 
198         if (n < 0) {
199             next = next->left;
200 
201         } else if (n > 0) {
202             next = next->right;
203 
204         } else {
205             return next;
206         }
207     }
208 
209     return NULL;
210 }
211 
212 
213 nxt_rbtree_node_t *
214 nxt_rbtree_find_less_or_equal(nxt_rbtree_t *tree, nxt_rbtree_part_t *part)
215 {
216     intptr_t              n;
217     nxt_rbtree_node_t     *node, *retval, *next, *sentinel;
218     nxt_rbtree_compare_t  compare;
219 
220     node = (nxt_rbtree_node_t *) part;
221 
222     retval = NULL;
223     next = nxt_rbtree_root(tree);
224     sentinel = nxt_rbtree_sentinel(tree);
225     compare = nxt_rbtree_comparison_callback(tree);
226 
227     while (next != sentinel) {
228         nxt_prefetch(next->left);
229         nxt_prefetch(next->right);
230 
231         n = compare(node, next);
232 
233         if (n < 0) {
234             next = next->left;
235 
236         } else if (n > 0) {
237             retval = next;
238             next = next->right;
239 
240         } else {
241             /* Exact match. */
242             return next;
243         }
244     }
245 
246     return retval;
247 }
248 
249 
250 nxt_rbtree_node_t *
251 nxt_rbtree_find_greater_or_equal(nxt_rbtree_t *tree, nxt_rbtree_part_t *part)
252 {
253     intptr_t              n;
254     nxt_rbtree_node_t     *node, *retval, *next, *sentinel;
255     nxt_rbtree_compare_t  compare;
256 
257     node = (nxt_rbtree_node_t *) part;
258 
259     retval = NULL;
260     next = nxt_rbtree_root(tree);
261     sentinel = nxt_rbtree_sentinel(tree);
262     compare = nxt_rbtree_comparison_callback(tree);
263 
264     while (next != sentinel) {
265         nxt_prefetch(next->left);
266         nxt_prefetch(next->right);
267 
268         n = compare(node, next);
269 
270         if (n < 0) {
271             retval = next;
272             next = next->left;
273 
274         } else if (n > 0) {
275             next = next->right;
276 
277         } else {
278             /* Exact match. */
279             return next;
280         }
281     }
282 
283     return retval;
284 }
285 
286 
287 void
288 nxt_rbtree_delete(nxt_rbtree_t *tree, nxt_rbtree_part_t *part)
289 {
290     uint8_t            color;
291     nxt_rbtree_node_t  *node, *sentinel, *subst, *child;
292 
293     node = (nxt_rbtree_node_t *) part;
294 
295     subst = node;
296     sentinel = nxt_rbtree_sentinel(tree);
297 
298     if (node->left == sentinel) {
299         child = node->right;
300 
301     } else if (node->right == sentinel) {
302         child = node->left;
303 
304     } else {
305         subst = nxt_rbtree_branch_min(tree, node->right);
306         child = subst->right;
307     }
308 
309     nxt_rbtree_parent_relink(child, subst);
310 
311     color = subst->color;
312 
313     if (subst != node) {
314         /* Move the subst node to the deleted node position in the tree. */
315 
316         subst->color = node->color;
317 
318         subst->left = node->left;
319         subst->left->parent = subst;
320 
321         subst->right = node->right;
322         subst->right->parent = subst;
323 
324         nxt_rbtree_parent_relink(subst, node);
325     }
326 
327 #if (NXT_DEBUG)
328     node->left = NULL;
329     node->right = NULL;
330     node->parent = NULL;
331 #endif
332 
333     if (color == NXT_RBTREE_BLACK) {
334         nxt_rbtree_delete_fixup(tree, child);
335     }
336 }
337 
338 
339 static void
340 nxt_rbtree_delete_fixup(nxt_rbtree_t *tree, nxt_rbtree_node_t *node)
341 {
342     nxt_rbtree_node_t  *parent, *sibling;
343 
344     while (node != nxt_rbtree_root(tree) && node->color == NXT_RBTREE_BLACK) {
345         /*
346          * Prefetching parent nodes does not help here according
347          * to microbenchmarks.
348          */
349 
350         parent = node->parent;
351 
352         if (node == parent->left) {
353             sibling = parent->right;
354 
355             if (sibling->color != NXT_RBTREE_BLACK) {
356 
357                 sibling->color = NXT_RBTREE_BLACK;
358                 parent->color = NXT_RBTREE_RED;
359 
360                 nxt_rbtree_left_rotate(parent);
361 
362                 sibling = parent->right;
363             }
364 
365             if (sibling->right->color == NXT_RBTREE_BLACK) {
366 
367                 sibling->color = NXT_RBTREE_RED;
368 
369                 if (sibling->left->color == NXT_RBTREE_BLACK) {
370                     node = parent;
371                     continue;
372                 }
373 
374                 sibling->left->color = NXT_RBTREE_BLACK;
375 
376                 nxt_rbtree_right_rotate(sibling);
377                 /*
378                  * If the node is the leaf sentinel then the right
379                  * rotate above changes its parent so a sibling below
380                  * becames the leaf sentinel as well and this causes
381                  * segmentation fault.  This is the reason why usual
382                  * red-black tree implementations with a leaf sentinel
383                  * which does not require to test leaf nodes at all
384                  * nevertheless test the leaf sentinel in the left and
385                  * right rotate procedures.  Since according to the
386                  * algorithm node->parent must not be changed by both
387                  * the left and right rotates above, it can be cached
388                  * in a local variable.  This not only eliminates the
389                  * sentinel test in nxt_rbtree_parent_relink() but also
390                  * decreases the code size because C forces to reload
391                  * non-restrict pointers.
392                  */
393                 sibling = parent->right;
394             }
395 
396             sibling->color = parent->color;
397             parent->color = NXT_RBTREE_BLACK;
398             sibling->right->color = NXT_RBTREE_BLACK;
399 
400             nxt_rbtree_left_rotate(parent);
401 
402             break;
403 
404         } else {
405             sibling = parent->left;
406 
407             if (sibling->color != NXT_RBTREE_BLACK) {
408 
409                 sibling->color = NXT_RBTREE_BLACK;
410                 parent->color = NXT_RBTREE_RED;
411 
412                 nxt_rbtree_right_rotate(parent);
413 
414                 sibling = parent->left;
415             }
416 
417             if (sibling->left->color == NXT_RBTREE_BLACK) {
418 
419                 sibling->color = NXT_RBTREE_RED;
420 
421                 if (sibling->right->color == NXT_RBTREE_BLACK) {
422                     node = parent;
423                     continue;
424                 }
425 
426                 sibling->right->color = NXT_RBTREE_BLACK;
427 
428                 nxt_rbtree_left_rotate(sibling);
429 
430                 /* See the comment in the symmetric branch above. */
431                 sibling = parent->left;
432             }
433 
434             sibling->color = parent->color;
435             parent->color = NXT_RBTREE_BLACK;
436             sibling->left->color = NXT_RBTREE_BLACK;
437 
438             nxt_rbtree_right_rotate(parent);
439 
440             break;
441         }
442     }
443 
444     node->color = NXT_RBTREE_BLACK;
445 }
446 
447 
448 nxt_inline void
449 nxt_rbtree_left_rotate(nxt_rbtree_node_t *node)
450 {
451     nxt_rbtree_node_t  *child;
452 
453     child = node->right;
454     node->right = child->left;
455     child->left->parent = node;
456     child->left = node;
457 
458     nxt_rbtree_parent_relink(child, node);
459 
460     node->parent = child;
461 }
462 
463 
464 nxt_inline void
465 nxt_rbtree_right_rotate(nxt_rbtree_node_t *node)
466 {
467     nxt_rbtree_node_t  *child;
468 
469     child = node->left;
470     node->left = child->right;
471     child->right->parent = node;
472     child->right = node;
473 
474     nxt_rbtree_parent_relink(child, node);
475 
476     node->parent = child;
477 }
478 
479 
480 /* Relink a parent from the node to the subst node. */
481 
482 nxt_inline void
483 nxt_rbtree_parent_relink(nxt_rbtree_node_t *subst, nxt_rbtree_node_t *node)
484 {
485     nxt_rbtree_node_t  *parent, **link;
486 
487     parent = node->parent;
488     /*
489      * The leaf sentinel's parent can be safely changed here.
490      * See the comment in nxt_rbtree_delete_fixup() for details.
491      */
492     subst->parent = parent;
493     /*
494      * If the node's parent is the root sentinel it is safely changed
495      * because the root sentinel's left child is the tree root.
496      */
497     link = (node == parent->left) ? &parent->left : &parent->right;
498     *link = subst;
499 }
500 
501 
502 nxt_rbtree_node_t *
503 nxt_rbtree_destroy_next(nxt_rbtree_t *tree, nxt_rbtree_node_t **next)
504 {
505     nxt_rbtree_node_t  *node, *subst, *parent, *sentinel;
506 
507     sentinel = nxt_rbtree_sentinel(tree);
508 
509     /* Find the leftmost node. */
510     for (node = *next; node->left != sentinel; node = node->left);
511 
512     /* Replace the leftmost node with its right child. */
513     subst = node->right;
514     parent = node->parent;
515 
516     parent->left = subst;
517     subst->parent = parent;
518 
519     /*
520      * The right child is used as the next start node.  If the right child
521      * is the sentinel then parent of the leftmost node is used as the next
522      * start node.  The parent of the root node is the sentinel so after
523      * the single root node will be replaced with the sentinel, the next
524      * start node will be equal to the sentinel and iteration will stop.
525      */
526     if (subst == sentinel) {
527         subst = parent;
528     }
529 
530     *next = subst;
531 
532     return node;
533 }
534