/src/unit/src/nxt_rbtree.c

Source

/*
 * Copyright (C) Igor Sysoev
 * Copyright (C) NGINX, Inc.
 */

#include <nxt_main.h>


/*
 * The red-black tree code is based on the algorithm described in
 * the "Introduction to Algorithms" by Cormen, Leiserson and Rivest.
 */


static void nxt_rbtree_insert_fixup(nxt_rbtree_node_t *node);
static void nxt_rbtree_delete_fixup(nxt_rbtree_t *tree,
    nxt_rbtree_node_t *node);
nxt_inline void nxt_rbtree_left_rotate(nxt_rbtree_node_t *node);
nxt_inline void nxt_rbtree_right_rotate(nxt_rbtree_node_t *node);
nxt_inline void nxt_rbtree_parent_relink(nxt_rbtree_node_t *subst,
    nxt_rbtree_node_t *node);


#define NXT_RBTREE_BLACK  0
#define NXT_RBTREE_RED    1


#define nxt_rbtree_comparison_callback(tree)                                  \
    ((nxt_rbtree_compare_t) (tree)->sentinel.right)


void
nxt_rbtree_init(nxt_rbtree_t *tree, nxt_rbtree_compare_t compare)
{
    /*
     * The sentinel is used as a leaf node sentinel and as a tree root
     * sentinel: it is a parent of a root node and the root node is
     * the left child of the sentinel.  Combining two sentinels in one
     * entry and the fact that the sentinel's left child is a root node
     * simplifies nxt_rbtree_node_successor() and eliminates explicit
     * root node test before or inside nxt_rbtree_min().
     */

    /* The root is empty. */
    tree->sentinel.left = &tree->sentinel;

    /*
     * The sentinel's right child is never used so
     * comparison callback can be safely stored here.
     */
    tree->sentinel.right = (void *) compare;

    /* The root and leaf sentinel must be black. */
    tree->sentinel.color = NXT_RBTREE_BLACK;
}


void
nxt_rbtree_insert(nxt_rbtree_t *tree, nxt_rbtree_part_t *part)
{
    nxt_rbtree_node_t     *node, *new_node, *sentinel, **child;
    nxt_rbtree_compare_t  compare;

    new_node = (nxt_rbtree_node_t *) part;

    node = nxt_rbtree_root(tree);
    sentinel = nxt_rbtree_sentinel(tree);

    new_node->left = sentinel;
    new_node->right = sentinel;
    new_node->color = NXT_RBTREE_RED;

    compare = (nxt_rbtree_compare_t) tree->sentinel.right;
    child = &nxt_rbtree_root(tree);

    while (*child != sentinel) {
        node = *child;

        nxt_prefetch(node->left);
        nxt_prefetch(node->right);

        child = (compare(new_node, node) < 0) ? &node->left : &node->right;
    }

    *child = new_node;
    new_node->parent = node;

    nxt_rbtree_insert_fixup(new_node);

    node = nxt_rbtree_root(tree);
    node->color = NXT_RBTREE_BLACK;
}


static void
nxt_rbtree_insert_fixup(nxt_rbtree_node_t *node)
{
    nxt_rbtree_node_t  *parent, *grandparent, *uncle;

    /*
     * Prefetching parent nodes does not help here because they are
     * already traversed during insertion.
     */

    for ( ;; ) {
        parent = node->parent;

        /*
         * Testing whether a node is a tree root is not required here since
         * a root node's parent is the sentinel and it is always black.
         */
        if (parent->color == NXT_RBTREE_BLACK) {
            return;
        }

        grandparent = parent->parent;

        if (parent == grandparent->left) {
            uncle = grandparent->right;

            if (uncle->color == NXT_RBTREE_BLACK) {

                if (node == parent->right) {
                    node = parent;
                    nxt_rbtree_left_rotate(node);
                }

                /*
                 * nxt_rbtree_left_rotate() swaps parent and
                 * child whilst keeps grandparent the same.
                 */
                parent = node->parent;

                parent->color = NXT_RBTREE_BLACK;
                grandparent->color = NXT_RBTREE_RED;

                nxt_rbtree_right_rotate(grandparent);
                /*
                 * nxt_rbtree_right_rotate() does not change node->parent
                 * color which is now black, so testing color is not required
                 * to return from function.
                 */
                return;
            }

        } else {
            uncle = grandparent->left;

            if (uncle->color == NXT_RBTREE_BLACK) {

                if (node == parent->left) {
                    node = parent;
                    nxt_rbtree_right_rotate(node);
                }

                /* See the comment in the symmetric branch above. */
                parent = node->parent;

                parent->color = NXT_RBTREE_BLACK;
                grandparent->color = NXT_RBTREE_RED;

                nxt_rbtree_left_rotate(grandparent);

                /* See the comment in the symmetric branch above. */
                return;
            }
        }

        uncle->color = NXT_RBTREE_BLACK;
        parent->color = NXT_RBTREE_BLACK;
        grandparent->color = NXT_RBTREE_RED;

        node = grandparent;
    }
}


nxt_rbtree_node_t *
nxt_rbtree_find(nxt_rbtree_t *tree, nxt_rbtree_part_t *part)
{
    intptr_t              n;
    nxt_rbtree_node_t     *node, *next, *sentinel;
    nxt_rbtree_compare_t  compare;

    node = (nxt_rbtree_node_t *) part;

    next = nxt_rbtree_root(tree);
    sentinel = nxt_rbtree_sentinel(tree);
    compare = nxt_rbtree_comparison_callback(tree);

    while (next != sentinel) {
        nxt_prefetch(next->left);
        nxt_prefetch(next->right);

        n = compare(node, next);

        if (n < 0) {
            next = next->left;

        } else if (n > 0) {
            next = next->right;

        } else {
            return next;
        }
    }

    return NULL;
}


nxt_rbtree_node_t *
nxt_rbtree_find_less_or_equal(nxt_rbtree_t *tree, nxt_rbtree_part_t *part)
{
    intptr_t              n;
    nxt_rbtree_node_t     *node, *retval, *next, *sentinel;
    nxt_rbtree_compare_t  compare;

    node = (nxt_rbtree_node_t *) part;

    retval = NULL;
    next = nxt_rbtree_root(tree);
    sentinel = nxt_rbtree_sentinel(tree);
    compare = nxt_rbtree_comparison_callback(tree);

    while (next != sentinel) {
        nxt_prefetch(next->left);
        nxt_prefetch(next->right);

        n = compare(node, next);

        if (n < 0) {
            next = next->left;

        } else if (n > 0) {
            retval = next;
            next = next->right;

        } else {
            /* Exact match. */
            return next;
        }
    }

    return retval;
}


nxt_rbtree_node_t *
nxt_rbtree_find_greater_or_equal(nxt_rbtree_t *tree, nxt_rbtree_part_t *part)
{
    intptr_t              n;
    nxt_rbtree_node_t     *node, *retval, *next, *sentinel;
    nxt_rbtree_compare_t  compare;

    node = (nxt_rbtree_node_t *) part;

    retval = NULL;
    next = nxt_rbtree_root(tree);
    sentinel = nxt_rbtree_sentinel(tree);
    compare = nxt_rbtree_comparison_callback(tree);

    while (next != sentinel) {
        nxt_prefetch(next->left);
        nxt_prefetch(next->right);

        n = compare(node, next);

        if (n < 0) {
            retval = next;
            next = next->left;

        } else if (n > 0) {
            next = next->right;

        } else {
            /* Exact match. */
            return next;
        }
    }

    return retval;
}


void
nxt_rbtree_delete(nxt_rbtree_t *tree, nxt_rbtree_part_t *part)
{
    uint8_t            color;
    nxt_rbtree_node_t  *node, *sentinel, *subst, *child;

    node = (nxt_rbtree_node_t *) part;

    subst = node;
    sentinel = nxt_rbtree_sentinel(tree);

    if (node->left == sentinel) {
        child = node->right;

    } else if (node->right == sentinel) {
        child = node->left;

    } else {
        subst = nxt_rbtree_branch_min(tree, node->right);
        child = subst->right;
    }

    nxt_rbtree_parent_relink(child, subst);

    color = subst->color;

    if (subst != node) {
        /* Move the subst node to the deleted node position in the tree. */

        subst->color = node->color;

        subst->left = node->left;
        subst->left->parent = subst;

        subst->right = node->right;
        subst->right->parent = subst;

        nxt_rbtree_parent_relink(subst, node);
    }

#if (NXT_DEBUG)
    node->left = NULL;
    node->right = NULL;
    node->parent = NULL;
#endif

    if (color == NXT_RBTREE_BLACK) {
        nxt_rbtree_delete_fixup(tree, child);
    }
}


static void
nxt_rbtree_delete_fixup(nxt_rbtree_t *tree, nxt_rbtree_node_t *node)
{
    nxt_rbtree_node_t  *parent, *sibling;

    while (node != nxt_rbtree_root(tree) && node->color == NXT_RBTREE_BLACK) {
        /*
         * Prefetching parent nodes does not help here according
         * to microbenchmarks.
         */

        parent = node->parent;

        if (node == parent->left) {
            sibling = parent->right;

            if (sibling->color != NXT_RBTREE_BLACK) {

                sibling->color = NXT_RBTREE_BLACK;
                parent->color = NXT_RBTREE_RED;

                nxt_rbtree_left_rotate(parent);

                sibling = parent->right;
            }

            if (sibling->right->color == NXT_RBTREE_BLACK) {

                sibling->color = NXT_RBTREE_RED;

                if (sibling->left->color == NXT_RBTREE_BLACK) {
                    node = parent;
                    continue;
                }

                sibling->left->color = NXT_RBTREE_BLACK;

                nxt_rbtree_right_rotate(sibling);
                /*
                 * If the node is the leaf sentinel then the right
                 * rotate above changes its parent so a sibling below
                 * becames the leaf sentinel as well and this causes
                 * segmentation fault.  This is the reason why usual
                 * red-black tree implementations with a leaf sentinel
                 * which does not require to test leaf nodes at all
                 * nevertheless test the leaf sentinel in the left and
                 * right rotate procedures.  Since according to the
                 * algorithm node->parent must not be changed by both
                 * the left and right rotates above, it can be cached
                 * in a local variable.  This not only eliminates the
                 * sentinel test in nxt_rbtree_parent_relink() but also
                 * decreases the code size because C forces to reload
                 * non-restrict pointers.
                 */
                sibling = parent->right;
            }

            sibling->color = parent->color;
            parent->color = NXT_RBTREE_BLACK;
            sibling->right->color = NXT_RBTREE_BLACK;

            nxt_rbtree_left_rotate(parent);

            return;

        } else {
            sibling = parent->left;

            if (sibling->color != NXT_RBTREE_BLACK) {

                sibling->color = NXT_RBTREE_BLACK;
                parent->color = NXT_RBTREE_RED;

                nxt_rbtree_right_rotate(parent);

                sibling = parent->left;
            }

            if (sibling->left->color == NXT_RBTREE_BLACK) {

                sibling->color = NXT_RBTREE_RED;

                if (sibling->right->color == NXT_RBTREE_BLACK) {
                    node = parent;
                    continue;
                }

                sibling->right->color = NXT_RBTREE_BLACK;

                nxt_rbtree_left_rotate(sibling);

                /* See the comment in the symmetric branch above. */
                sibling = parent->left;
            }

            sibling->color = parent->color;
            parent->color = NXT_RBTREE_BLACK;
            sibling->left->color = NXT_RBTREE_BLACK;

            nxt_rbtree_right_rotate(parent);

            return;
        }
    }

    node->color = NXT_RBTREE_BLACK;
}


nxt_inline void
nxt_rbtree_left_rotate(nxt_rbtree_node_t *node)
{
    nxt_rbtree_node_t  *child;

    child = node->right;
    node->right = child->left;
    child->left->parent = node;
    child->left = node;

    nxt_rbtree_parent_relink(child, node);

    node->parent = child;
}


nxt_inline void
nxt_rbtree_right_rotate(nxt_rbtree_node_t *node)
{
    nxt_rbtree_node_t  *child;

    child = node->left;
    node->left = child->right;
    child->right->parent = node;
    child->right = node;

    nxt_rbtree_parent_relink(child, node);

    node->parent = child;
}


/* Relink a parent from the node to the subst node. */

nxt_inline void
nxt_rbtree_parent_relink(nxt_rbtree_node_t *subst, nxt_rbtree_node_t *node)
{
    nxt_rbtree_node_t  *parent, **link;

    parent = node->parent;
    /*
     * The leaf sentinel's parent can be safely changed here.
     * See the comment in nxt_rbtree_delete_fixup() for details.
     */
    subst->parent = parent;
    /*
     * If the node's parent is the root sentinel it is safely changed
     * because the root sentinel's left child is the tree root.
     */
    link = (node == parent->left) ? &parent->left : &parent->right;
    *link = subst;
}


nxt_rbtree_node_t *
nxt_rbtree_destroy_next(nxt_rbtree_t *tree, nxt_rbtree_node_t **next)
{
    nxt_rbtree_node_t  *node, *subst, *parent, *sentinel;

    sentinel = nxt_rbtree_sentinel(tree);

    /* Find the leftmost node. */
    for (node = *next; node->left != sentinel; node = node->left);

    /* Replace the leftmost node with its right child. */
    subst = node->right;
    parent = node->parent;

    parent->left = subst;
    subst->parent = parent;

    /*
     * The right child is used as the next start node.  If the right child
     * is the sentinel then parent of the leftmost node is used as the next
     * start node.  The parent of the root node is the sentinel so after
     * the single root node will be replaced with the sentinel, the next
     * start node will be equal to the sentinel and iteration will stop.
     */
    if (subst == sentinel) {
        subst = parent;
    }

    *next = subst;

    return node;
}

Coverage Report

Created: 2025-11-11 06:57

Line	Count	Source
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	0	#define NXT_RBTREE_BLACK 0
26	0	#define NXT_RBTREE_RED 1
27
28
29		#define nxt_rbtree_comparison_callback(tree) \
30	0	((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	0	{
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	0	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	0	tree->sentinel.right = (void *) compare;
53
54		/* The root and leaf sentinel must be black. */
55	0	tree->sentinel.color = NXT_RBTREE_BLACK;
56	0	}
57
58
59		void
60		nxt_rbtree_insert(nxt_rbtree_t tree, nxt_rbtree_part_t part)
61	0	{
62	0	nxt_rbtree_node_t node, new_node, sentinel, *child;
63	0	nxt_rbtree_compare_t compare;
64
65	0	new_node = (nxt_rbtree_node_t *) part;
66
67	0	node = nxt_rbtree_root(tree);
68	0	sentinel = nxt_rbtree_sentinel(tree);
69
70	0	new_node->left = sentinel;
71	0	new_node->right = sentinel;
72	0	new_node->color = NXT_RBTREE_RED;
73
74	0	compare = (nxt_rbtree_compare_t) tree->sentinel.right;
75	0	child = &nxt_rbtree_root(tree);
76
77	0	while (*child != sentinel) {
78	0	node = *child;
79
80	0	nxt_prefetch(node->left);
81	0	nxt_prefetch(node->right);
82
83	0	child = (compare(new_node, node) < 0) ? &node->left : &node->right;
84	0	}
85
86	0	*child = new_node;
87	0	new_node->parent = node;
88
89	0	nxt_rbtree_insert_fixup(new_node);
90
91	0	node = nxt_rbtree_root(tree);
92	0	node->color = NXT_RBTREE_BLACK;
93	0	}
94
95
96		static void
97		nxt_rbtree_insert_fixup(nxt_rbtree_node_t *node)
98	0	{
99	0	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	0	for ( ;; ) {
107	0	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	0	if (parent->color == NXT_RBTREE_BLACK) {
114	0	return;
115	0	}
116
117	0	grandparent = parent->parent;
118
119	0	if (parent == grandparent->left) {
120	0	uncle = grandparent->right;
121
122	0	if (uncle->color == NXT_RBTREE_BLACK) {
123
124	0	if (node == parent->right) {
125	0	node = parent;
126	0	nxt_rbtree_left_rotate(node);
127	0	}
128
129		/*
130		* nxt_rbtree_left_rotate() swaps parent and
131		* child whilst keeps grandparent the same.
132		*/
133	0	parent = node->parent;
134
135	0	parent->color = NXT_RBTREE_BLACK;
136	0	grandparent->color = NXT_RBTREE_RED;
137
138	0	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	0	return;
145	0	}
146
147	0	} else {
148	0	uncle = grandparent->left;
149
150	0	if (uncle->color == NXT_RBTREE_BLACK) {
151
152	0	if (node == parent->left) {
153	0	node = parent;
154	0	nxt_rbtree_right_rotate(node);
155	0	}
156
157		/* See the comment in the symmetric branch above. */
158	0	parent = node->parent;
159
160	0	parent->color = NXT_RBTREE_BLACK;
161	0	grandparent->color = NXT_RBTREE_RED;
162
163	0	nxt_rbtree_left_rotate(grandparent);
164
165		/* See the comment in the symmetric branch above. */
166	0	return;
167	0	}
168	0	}
169
170	0	uncle->color = NXT_RBTREE_BLACK;
171	0	parent->color = NXT_RBTREE_BLACK;
172	0	grandparent->color = NXT_RBTREE_RED;
173
174	0	node = grandparent;
175	0	}
176	0	}
177
178
179		nxt_rbtree_node_t *
180		nxt_rbtree_find(nxt_rbtree_t tree, nxt_rbtree_part_t part)
181	0	{
182	0	intptr_t n;
183	0	nxt_rbtree_node_t node, next, *sentinel;
184	0	nxt_rbtree_compare_t compare;
185
186	0	node = (nxt_rbtree_node_t *) part;
187
188	0	next = nxt_rbtree_root(tree);
189	0	sentinel = nxt_rbtree_sentinel(tree);
190	0	compare = nxt_rbtree_comparison_callback(tree);
191
192	0	while (next != sentinel) {
193	0	nxt_prefetch(next->left);
194	0	nxt_prefetch(next->right);
195
196	0	n = compare(node, next);
197
198	0	if (n < 0) {
199	0	next = next->left;
200
201	0	} else if (n > 0) {
202	0	next = next->right;
203
204	0	} else {
205	0	return next;
206	0	}
207	0	}
208
209	0	return NULL;
210	0	}
211
212
213		nxt_rbtree_node_t *
214		nxt_rbtree_find_less_or_equal(nxt_rbtree_t tree, nxt_rbtree_part_t part)
215	0	{
216	0	intptr_t n;
217	0	nxt_rbtree_node_t node, retval, next, sentinel;
218	0	nxt_rbtree_compare_t compare;
219
220	0	node = (nxt_rbtree_node_t *) part;
221
222	0	retval = NULL;
223	0	next = nxt_rbtree_root(tree);
224	0	sentinel = nxt_rbtree_sentinel(tree);
225	0	compare = nxt_rbtree_comparison_callback(tree);
226
227	0	while (next != sentinel) {
228	0	nxt_prefetch(next->left);
229	0	nxt_prefetch(next->right);
230
231	0	n = compare(node, next);
232
233	0	if (n < 0) {
234	0	next = next->left;
235
236	0	} else if (n > 0) {
237	0	retval = next;
238	0	next = next->right;
239
240	0	} else {
241		/* Exact match. */
242	0	return next;
243	0	}
244	0	}
245
246	0	return retval;
247	0	}
248
249
250		nxt_rbtree_node_t *
251		nxt_rbtree_find_greater_or_equal(nxt_rbtree_t tree, nxt_rbtree_part_t part)
252	0	{
253	0	intptr_t n;
254	0	nxt_rbtree_node_t node, retval, next, sentinel;
255	0	nxt_rbtree_compare_t compare;
256
257	0	node = (nxt_rbtree_node_t *) part;
258
259	0	retval = NULL;
260	0	next = nxt_rbtree_root(tree);
261	0	sentinel = nxt_rbtree_sentinel(tree);
262	0	compare = nxt_rbtree_comparison_callback(tree);
263
264	0	while (next != sentinel) {
265	0	nxt_prefetch(next->left);
266	0	nxt_prefetch(next->right);
267
268	0	n = compare(node, next);
269
270	0	if (n < 0) {
271	0	retval = next;
272	0	next = next->left;
273
274	0	} else if (n > 0) {
275	0	next = next->right;
276
277	0	} else {
278		/* Exact match. */
279	0	return next;
280	0	}
281	0	}
282
283	0	return retval;
284	0	}
285
286
287		void
288		nxt_rbtree_delete(nxt_rbtree_t tree, nxt_rbtree_part_t part)
289	0	{
290	0	uint8_t color;
291	0	nxt_rbtree_node_t node, sentinel, subst, child;
292
293	0	node = (nxt_rbtree_node_t *) part;
294
295	0	subst = node;
296	0	sentinel = nxt_rbtree_sentinel(tree);
297
298	0	if (node->left == sentinel) {
299	0	child = node->right;
300
301	0	} else if (node->right == sentinel) {
302	0	child = node->left;
303
304	0	} else {
305	0	subst = nxt_rbtree_branch_min(tree, node->right);
306	0	child = subst->right;
307	0	}
308
309	0	nxt_rbtree_parent_relink(child, subst);
310
311	0	color = subst->color;
312
313	0	if (subst != node) {
314		/* Move the subst node to the deleted node position in the tree. */
315
316	0	subst->color = node->color;
317
318	0	subst->left = node->left;
319	0	subst->left->parent = subst;
320
321	0	subst->right = node->right;
322	0	subst->right->parent = subst;
323
324	0	nxt_rbtree_parent_relink(subst, node);
325	0	}
326
327		#if (NXT_DEBUG)
328		node->left = NULL;
329		node->right = NULL;
330		node->parent = NULL;
331		#endif
332
333	0	if (color == NXT_RBTREE_BLACK) {
334	0	nxt_rbtree_delete_fixup(tree, child);
335	0	}
336	0	}
337
338
339		static void
340		nxt_rbtree_delete_fixup(nxt_rbtree_t tree, nxt_rbtree_node_t node)
341	0	{
342	0	nxt_rbtree_node_t parent, sibling;
343
344	0	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	0	parent = node->parent;
351
352	0	if (node == parent->left) {
353	0	sibling = parent->right;
354
355	0	if (sibling->color != NXT_RBTREE_BLACK) {
356
357	0	sibling->color = NXT_RBTREE_BLACK;
358	0	parent->color = NXT_RBTREE_RED;
359
360	0	nxt_rbtree_left_rotate(parent);
361
362	0	sibling = parent->right;
363	0	}
364
365	0	if (sibling->right->color == NXT_RBTREE_BLACK) {
366
367	0	sibling->color = NXT_RBTREE_RED;
368
369	0	if (sibling->left->color == NXT_RBTREE_BLACK) {
370	0	node = parent;
371	0	continue;
372	0	}
373
374	0	sibling->left->color = NXT_RBTREE_BLACK;
375
376	0	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	0	sibling = parent->right;
394	0	}
395
396	0	sibling->color = parent->color;
397	0	parent->color = NXT_RBTREE_BLACK;
398	0	sibling->right->color = NXT_RBTREE_BLACK;
399
400	0	nxt_rbtree_left_rotate(parent);
401
402	0	return;
403
404	0	} else {
405	0	sibling = parent->left;
406
407	0	if (sibling->color != NXT_RBTREE_BLACK) {
408
409	0	sibling->color = NXT_RBTREE_BLACK;
410	0	parent->color = NXT_RBTREE_RED;
411
412	0	nxt_rbtree_right_rotate(parent);
413
414	0	sibling = parent->left;
415	0	}
416
417	0	if (sibling->left->color == NXT_RBTREE_BLACK) {
418
419	0	sibling->color = NXT_RBTREE_RED;
420
421	0	if (sibling->right->color == NXT_RBTREE_BLACK) {
422	0	node = parent;
423	0	continue;
424	0	}
425
426	0	sibling->right->color = NXT_RBTREE_BLACK;
427
428	0	nxt_rbtree_left_rotate(sibling);
429
430		/* See the comment in the symmetric branch above. */
431	0	sibling = parent->left;
432	0	}
433
434	0	sibling->color = parent->color;
435	0	parent->color = NXT_RBTREE_BLACK;
436	0	sibling->left->color = NXT_RBTREE_BLACK;
437
438	0	nxt_rbtree_right_rotate(parent);
439
440	0	return;
441	0	}
442	0	}
443
444	0	node->color = NXT_RBTREE_BLACK;
445	0	}
446
447
448		nxt_inline void
449		nxt_rbtree_left_rotate(nxt_rbtree_node_t *node)
450	0	{
451	0	nxt_rbtree_node_t *child;
452
453	0	child = node->right;
454	0	node->right = child->left;
455	0	child->left->parent = node;
456	0	child->left = node;
457
458	0	nxt_rbtree_parent_relink(child, node);
459
460	0	node->parent = child;
461	0	}
462
463
464		nxt_inline void
465		nxt_rbtree_right_rotate(nxt_rbtree_node_t *node)
466	0	{
467	0	nxt_rbtree_node_t *child;
468
469	0	child = node->left;
470	0	node->left = child->right;
471	0	child->right->parent = node;
472	0	child->right = node;
473
474	0	nxt_rbtree_parent_relink(child, node);
475
476	0	node->parent = child;
477	0	}
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	0	{
485	0	nxt_rbtree_node_t parent, *link;
486
487	0	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	0	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	0	link = (node == parent->left) ? &parent->left : &parent->right;
498	0	*link = subst;
499	0	}
500
501
502		nxt_rbtree_node_t *
503		nxt_rbtree_destroy_next(nxt_rbtree_t tree, nxt_rbtree_node_t *next)
504	0	{
505	0	nxt_rbtree_node_t node, subst, parent, sentinel;
506
507	0	sentinel = nxt_rbtree_sentinel(tree);
508
509		/* Find the leftmost node. */
510	0	for (node = *next; node->left != sentinel; node = node->left);
511
512		/* Replace the leftmost node with its right child. */
513	0	subst = node->right;
514	0	parent = node->parent;
515
516	0	parent->left = subst;
517	0	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	0	if (subst == sentinel) {
527	0	subst = parent;
528	0	}
529
530	0	*next = subst;
531
532	0	return node;
533	0	}