/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-10-10 06:52

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	182k	#define NXT_RBTREE_BLACK 0
26	62.4k	#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	55.6k	{
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	55.6k	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	55.6k	tree->sentinel.right = (void *) compare;
53
54		/* The root and leaf sentinel must be black. */
55	55.6k	tree->sentinel.color = NXT_RBTREE_BLACK;
56	55.6k	}
57
58
59		void
60		nxt_rbtree_insert(nxt_rbtree_t tree, nxt_rbtree_part_t part)
61	60.1k	{
62	60.1k	nxt_rbtree_node_t node, new_node, sentinel, *child;
63	60.1k	nxt_rbtree_compare_t compare;
64
65	60.1k	new_node = (nxt_rbtree_node_t *) part;
66
67	60.1k	node = nxt_rbtree_root(tree);
68	60.1k	sentinel = nxt_rbtree_sentinel(tree);
69
70	60.1k	new_node->left = sentinel;
71	60.1k	new_node->right = sentinel;
72	60.1k	new_node->color = NXT_RBTREE_RED;
73
74	60.1k	compare = (nxt_rbtree_compare_t) tree->sentinel.right;
75	60.1k	child = &nxt_rbtree_root(tree);
76
77	74.4k	while (*child != sentinel) {
78	14.2k	node = *child;
79
80	14.2k	nxt_prefetch(node->left);
81	14.2k	nxt_prefetch(node->right);
82
83	14.2k	child = (compare(new_node, node) < 0) ? &node->left : &node->right;
84	14.2k	}
85
86	60.1k	*child = new_node;
87	60.1k	new_node->parent = node;
88
89	60.1k	nxt_rbtree_insert_fixup(new_node);
90
91	60.1k	node = nxt_rbtree_root(tree);
92	60.1k	node->color = NXT_RBTREE_BLACK;
93	60.1k	}
94
95
96		static void
97		nxt_rbtree_insert_fixup(nxt_rbtree_node_t *node)
98	60.1k	{
99	60.1k	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	60.9k	for ( ;; ) {
107	60.9k	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	60.9k	if (parent->color == NXT_RBTREE_BLACK) {
114	58.7k	return;
115	58.7k	}
116
117	2.20k	grandparent = parent->parent;
118
119	2.20k	if (parent == grandparent->left) {
120	814	uncle = grandparent->right;
121
122	814	if (uncle->color == NXT_RBTREE_BLACK) {
123
124	439	if (node == parent->right) {
125	206	node = parent;
126	206	nxt_rbtree_left_rotate(node);
127	206	}
128
129		/*
130		* nxt_rbtree_left_rotate() swaps parent and
131		* child whilst keeps grandparent the same.
132		*/
133	439	parent = node->parent;
134
135	439	parent->color = NXT_RBTREE_BLACK;
136	439	grandparent->color = NXT_RBTREE_RED;
137
138	439	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	439	return;
145	439	}
146
147	1.39k	} else {
148	1.39k	uncle = grandparent->left;
149
150	1.39k	if (uncle->color == NXT_RBTREE_BLACK) {
151
152	1.01k	if (node == parent->left) {
153	423	node = parent;
154	423	nxt_rbtree_right_rotate(node);
155	423	}
156
157		/* See the comment in the symmetric branch above. */
158	1.01k	parent = node->parent;
159
160	1.01k	parent->color = NXT_RBTREE_BLACK;
161	1.01k	grandparent->color = NXT_RBTREE_RED;
162
163	1.01k	nxt_rbtree_left_rotate(grandparent);
164
165		/* See the comment in the symmetric branch above. */
166	1.01k	return;
167	1.01k	}
168	1.39k	}
169
170	754	uncle->color = NXT_RBTREE_BLACK;
171	754	parent->color = NXT_RBTREE_BLACK;
172	754	grandparent->color = NXT_RBTREE_RED;
173
174	754	node = grandparent;
175	754	}
176	60.1k	}
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	204	{
290	204	uint8_t color;
291	204	nxt_rbtree_node_t node, sentinel, subst, child;
292
293	204	node = (nxt_rbtree_node_t *) part;
294
295	204	subst = node;
296	204	sentinel = nxt_rbtree_sentinel(tree);
297
298	204	if (node->left == sentinel) {
299	132	child = node->right;
300
301	132	} else if (node->right == sentinel) {
302	19	child = node->left;
303
304	53	} else {
305	53	subst = nxt_rbtree_branch_min(tree, node->right);
306	53	child = subst->right;
307	53	}
308
309	204	nxt_rbtree_parent_relink(child, subst);
310
311	204	color = subst->color;
312
313	204	if (subst != node) {
314		/* Move the subst node to the deleted node position in the tree. */
315
316	53	subst->color = node->color;
317
318	53	subst->left = node->left;
319	53	subst->left->parent = subst;
320
321	53	subst->right = node->right;
322	53	subst->right->parent = subst;
323
324	53	nxt_rbtree_parent_relink(subst, node);
325	53	}
326
327		#if (NXT_DEBUG)
328		node->left = NULL;
329		node->right = NULL;
330		node->parent = NULL;
331		#endif
332
333	204	if (color == NXT_RBTREE_BLACK) {
334	111	nxt_rbtree_delete_fixup(tree, child);
335	111	}
336	204	}
337
338
339		static void
340		nxt_rbtree_delete_fixup(nxt_rbtree_t tree, nxt_rbtree_node_t node)
341	111	{
342	111	nxt_rbtree_node_t parent, sibling;
343
344	114	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	37	parent = node->parent;
351
352	37	if (node == parent->left) {
353	22	sibling = parent->right;
354
355	22	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	22	if (sibling->right->color == NXT_RBTREE_BLACK) {
366
367	12	sibling->color = NXT_RBTREE_RED;
368
369	12	if (sibling->left->color == NXT_RBTREE_BLACK) {
370	0	node = parent;
371	0	continue;
372	0	}
373
374	12	sibling->left->color = NXT_RBTREE_BLACK;
375
376	12	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	12	sibling = parent->right;
394	12	}
395
396	22	sibling->color = parent->color;
397	22	parent->color = NXT_RBTREE_BLACK;
398	22	sibling->right->color = NXT_RBTREE_BLACK;
399
400	22	nxt_rbtree_left_rotate(parent);
401
402	22	return;
403
404	22	} else {
405	15	sibling = parent->left;
406
407	15	if (sibling->color != NXT_RBTREE_BLACK) {
408
409	2	sibling->color = NXT_RBTREE_BLACK;
410	2	parent->color = NXT_RBTREE_RED;
411
412	2	nxt_rbtree_right_rotate(parent);
413
414	2	sibling = parent->left;
415	2	}
416
417	15	if (sibling->left->color == NXT_RBTREE_BLACK) {
418
419	8	sibling->color = NXT_RBTREE_RED;
420
421	8	if (sibling->right->color == NXT_RBTREE_BLACK) {
422	3	node = parent;
423	3	continue;
424	3	}
425
426	5	sibling->right->color = NXT_RBTREE_BLACK;
427
428	5	nxt_rbtree_left_rotate(sibling);
429
430		/* See the comment in the symmetric branch above. */
431	5	sibling = parent->left;
432	5	}
433
434	12	sibling->color = parent->color;
435	12	parent->color = NXT_RBTREE_BLACK;
436	12	sibling->left->color = NXT_RBTREE_BLACK;
437
438	12	nxt_rbtree_right_rotate(parent);
439
440	12	return;
441	15	}
442	37	}
443
444	77	node->color = NXT_RBTREE_BLACK;
445	77	}
446
447
448		nxt_inline void
449		nxt_rbtree_left_rotate(nxt_rbtree_node_t *node)
450	1.24k	{
451	1.24k	nxt_rbtree_node_t *child;
452
453	1.24k	child = node->right;
454	1.24k	node->right = child->left;
455	1.24k	child->left->parent = node;
456	1.24k	child->left = node;
457
458	1.24k	nxt_rbtree_parent_relink(child, node);
459
460	1.24k	node->parent = child;
461	1.24k	}
462
463
464		nxt_inline void
465		nxt_rbtree_right_rotate(nxt_rbtree_node_t *node)
466	888	{
467	888	nxt_rbtree_node_t *child;
468
469	888	child = node->left;
470	888	node->left = child->right;
471	888	child->right->parent = node;
472	888	child->right = node;
473
474	888	nxt_rbtree_parent_relink(child, node);
475
476	888	node->parent = child;
477	888	}
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	2.39k	{
485	2.39k	nxt_rbtree_node_t parent, *link;
486
487	2.39k	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	2.39k	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	2.39k	link = (node == parent->left) ? &parent->left : &parent->right;
498	2.39k	*link = subst;
499	2.39k	}
500
501
502		nxt_rbtree_node_t *
503		nxt_rbtree_destroy_next(nxt_rbtree_t tree, nxt_rbtree_node_t *next)
504	59.9k	{
505	59.9k	nxt_rbtree_node_t node, subst, parent, sentinel;
506
507	59.9k	sentinel = nxt_rbtree_sentinel(tree);
508
509		/* Find the leftmost node. */
510	62.2k	for (node = *next; node->left != sentinel; node = node->left);
511
512		/* Replace the leftmost node with its right child. */
513	59.9k	subst = node->right;
514	59.9k	parent = node->parent;
515
516	59.9k	parent->left = subst;
517	59.9k	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	59.9k	if (subst == sentinel) {
527	52.1k	subst = parent;
528	52.1k	}
529
530	59.9k	*next = subst;
531
532	59.9k	return node;
533	59.9k	}