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