/src/njs/src/njs_rbtree.c

Source

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


#include <njs_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 njs_rbtree_insert_fixup(njs_rbtree_node_t *node);
static void njs_rbtree_delete_fixup(njs_rbtree_t *tree,
    njs_rbtree_node_t *node);
njs_inline void njs_rbtree_left_rotate(njs_rbtree_node_t *node);
njs_inline void njs_rbtree_right_rotate(njs_rbtree_node_t *node);
njs_inline void njs_rbtree_parent_relink(njs_rbtree_node_t *subst,
    njs_rbtree_node_t *node);


#define NJS_RBTREE_BLACK  0
#define NJS_RBTREE_RED    1


#define njs_rbtree_comparison_callback(tree)                                  \
    ((njs_rbtree_compare_t) (tree)->sentinel.right)


void
njs_rbtree_init(njs_rbtree_t *tree, njs_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 njs_rbtree_node_successor() and eliminates explicit
     * root node test before or inside njs_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 = NJS_RBTREE_BLACK;
}


void
njs_rbtree_insert(njs_rbtree_t *tree, njs_rbtree_part_t *part)
{
    njs_rbtree_node_t     *node, *new_node, *sentinel, **child;
    njs_rbtree_compare_t  compare;

    new_node = (njs_rbtree_node_t *) part;

    node = njs_rbtree_root(tree);
    sentinel = njs_rbtree_sentinel(tree);

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

    compare = (njs_rbtree_compare_t) tree->sentinel.right;
    child = &njs_rbtree_root(tree);

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

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

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

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

    njs_rbtree_insert_fixup(new_node);

    node = njs_rbtree_root(tree);
    node->color = NJS_RBTREE_BLACK;
}


static void
njs_rbtree_insert_fixup(njs_rbtree_node_t *node)
{
    njs_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 == NJS_RBTREE_BLACK) {
            return;
        }

        grandparent = parent->parent;

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

            if (uncle->color == NJS_RBTREE_BLACK) {

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

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

                parent->color = NJS_RBTREE_BLACK;
                grandparent->color = NJS_RBTREE_RED;

                njs_rbtree_right_rotate(grandparent);
                /*
                 * njs_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 == NJS_RBTREE_BLACK) {

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

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

                parent->color = NJS_RBTREE_BLACK;
                grandparent->color = NJS_RBTREE_RED;

                njs_rbtree_left_rotate(grandparent);

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

        uncle->color = NJS_RBTREE_BLACK;
        parent->color = NJS_RBTREE_BLACK;
        grandparent->color = NJS_RBTREE_RED;

        node = grandparent;
    }
}


njs_rbtree_node_t *
njs_rbtree_find(njs_rbtree_t *tree, njs_rbtree_part_t *part)
{
    intptr_t              n;
    njs_rbtree_node_t     *node, *next, *sentinel;
    njs_rbtree_compare_t  compare;

    node = (njs_rbtree_node_t *) part;

    next = njs_rbtree_root(tree);
    sentinel = njs_rbtree_sentinel(tree);
    compare = njs_rbtree_comparison_callback(tree);

    while (next != sentinel) {
        njs_prefetch(next->left);
        njs_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;
}


njs_rbtree_node_t *
njs_rbtree_find_less_or_equal(njs_rbtree_t *tree, njs_rbtree_part_t *part)
{
    intptr_t              n;
    njs_rbtree_node_t     *node, *retval, *next, *sentinel;
    njs_rbtree_compare_t  compare;

    node = (njs_rbtree_node_t *) part;

    retval = NULL;
    next = njs_rbtree_root(tree);
    sentinel = njs_rbtree_sentinel(tree);
    compare = njs_rbtree_comparison_callback(tree);

    while (next != sentinel) {
        njs_prefetch(next->left);
        njs_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;
}


njs_rbtree_node_t *
njs_rbtree_find_greater_or_equal(njs_rbtree_t *tree, njs_rbtree_part_t *part)
{
    intptr_t              n;
    njs_rbtree_node_t     *node, *retval, *next, *sentinel;
    njs_rbtree_compare_t  compare;

    node = (njs_rbtree_node_t *) part;

    retval = NULL;
    next = njs_rbtree_root(tree);
    sentinel = njs_rbtree_sentinel(tree);
    compare = njs_rbtree_comparison_callback(tree);

    while (next != sentinel) {
        njs_prefetch(next->left);
        njs_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
njs_rbtree_delete(njs_rbtree_t *tree, njs_rbtree_part_t *part)
{
    uint8_t            color;
    njs_rbtree_node_t  *node, *sentinel, *subst, *child;

    node = (njs_rbtree_node_t *) part;

    subst = node;
    sentinel = njs_rbtree_sentinel(tree);

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

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

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

    njs_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;

        njs_rbtree_parent_relink(subst, node);
    }

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

    if (color == NJS_RBTREE_BLACK) {
        njs_rbtree_delete_fixup(tree, child);
    }
}


static void
njs_rbtree_delete_fixup(njs_rbtree_t *tree, njs_rbtree_node_t *node)
{
    njs_rbtree_node_t  *parent, *sibling;

    while (node != njs_rbtree_root(tree) && node->color == NJS_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 != NJS_RBTREE_BLACK) {

                sibling->color = NJS_RBTREE_BLACK;
                parent->color = NJS_RBTREE_RED;

                njs_rbtree_left_rotate(parent);

                sibling = parent->right;
            }

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

                sibling->color = NJS_RBTREE_RED;

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

                sibling->left->color = NJS_RBTREE_BLACK;

                njs_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 njs_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 = NJS_RBTREE_BLACK;
            sibling->right->color = NJS_RBTREE_BLACK;

            njs_rbtree_left_rotate(parent);

            return;

        } else {
            sibling = parent->left;

            if (sibling->color != NJS_RBTREE_BLACK) {

                sibling->color = NJS_RBTREE_BLACK;
                parent->color = NJS_RBTREE_RED;

                njs_rbtree_right_rotate(parent);

                sibling = parent->left;
            }

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

                sibling->color = NJS_RBTREE_RED;

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

                sibling->right->color = NJS_RBTREE_BLACK;

                njs_rbtree_left_rotate(sibling);

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

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

            njs_rbtree_right_rotate(parent);

            return;
        }
    }

    node->color = NJS_RBTREE_BLACK;
}


njs_inline void
njs_rbtree_left_rotate(njs_rbtree_node_t *node)
{
    njs_rbtree_node_t  *child;

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

    njs_rbtree_parent_relink(child, node);

    node->parent = child;
}


njs_inline void
njs_rbtree_right_rotate(njs_rbtree_node_t *node)
{
    njs_rbtree_node_t  *child;

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

    njs_rbtree_parent_relink(child, node);

    node->parent = child;
}


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

njs_inline void
njs_rbtree_parent_relink(njs_rbtree_node_t *subst, njs_rbtree_node_t *node)
{
    njs_rbtree_node_t  *parent, **link;

    parent = node->parent;
    /*
     * The leaf sentinel's parent can be safely changed here.
     * See the comment in njs_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;
}


njs_rbtree_node_t *
njs_rbtree_destroy_next(njs_rbtree_t *tree, njs_rbtree_node_t **next)
{
    njs_rbtree_node_t  *node, *subst, *parent, *sentinel;

    sentinel = njs_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: 2026-08-13 07:20

Line	Count	Source
1
2		/*
3		* Copyright (C) Igor Sysoev
4		* Copyright (C) NGINX, Inc.
5		*/
6
7
8		#include <njs_main.h>
9
10
11		/*
12		* The red-black tree code is based on the algorithm described in
13		* the "Introduction to Algorithms" by Cormen, Leiserson and Rivest.
14		*/
15
16
17		static void njs_rbtree_insert_fixup(njs_rbtree_node_t *node);
18		static void njs_rbtree_delete_fixup(njs_rbtree_t *tree,
19		njs_rbtree_node_t *node);
20		njs_inline void njs_rbtree_left_rotate(njs_rbtree_node_t *node);
21		njs_inline void njs_rbtree_right_rotate(njs_rbtree_node_t *node);
22		njs_inline void njs_rbtree_parent_relink(njs_rbtree_node_t *subst,
23		njs_rbtree_node_t *node);
24
25
26	43.9M	#define NJS_RBTREE_BLACK 0
27	14.9M	#define NJS_RBTREE_RED 1
28
29
30		#define njs_rbtree_comparison_callback(tree) \
31	17.8M	((njs_rbtree_compare_t) (tree)->sentinel.right)
32
33
34		void
35		njs_rbtree_init(njs_rbtree_t *tree, njs_rbtree_compare_t compare)
36	3.41M	{
37		/*
38		* The sentinel is used as a leaf node sentinel and as a tree root
39		* sentinel: it is a parent of a root node and the root node is
40		* the left child of the sentinel. Combining two sentinels in one
41		* entry and the fact that the sentinel's left child is a root node
42		* simplifies njs_rbtree_node_successor() and eliminates explicit
43		* root node test before or inside njs_rbtree_min().
44		*/
45
46		/* The root is empty. */
47	3.41M	tree->sentinel.left = &tree->sentinel;
48
49		/*
50		* The sentinel's right child is never used so
51		* comparison callback can be safely stored here.
52		*/
53	3.41M	tree->sentinel.right = (void *) compare;
54
55		/* The root and leaf sentinel must be black. */
56	3.41M	tree->sentinel.color = NJS_RBTREE_BLACK;
57	3.41M	}
58
59
60		void
61		njs_rbtree_insert(njs_rbtree_t tree, njs_rbtree_part_t part)
62	7.80M	{
63	7.80M	njs_rbtree_node_t node, new_node, sentinel, *child;
64	7.80M	njs_rbtree_compare_t compare;
65
66	7.80M	new_node = (njs_rbtree_node_t *) part;
67
68	7.80M	node = njs_rbtree_root(tree);
69	7.80M	sentinel = njs_rbtree_sentinel(tree);
70
71	7.80M	new_node->left = sentinel;
72	7.80M	new_node->right = sentinel;
73	7.80M	new_node->color = NJS_RBTREE_RED;
74
75	7.80M	compare = (njs_rbtree_compare_t) tree->sentinel.right;
76	7.80M	child = &njs_rbtree_root(tree);
77
78	68.8M	while (*child != sentinel) {
79	61.0M	node = *child;
80
81	61.0M	njs_prefetch(node->left);
82	61.0M	njs_prefetch(node->right);
83
84	61.0M	child = (compare(new_node, node) < 0) ? &node->left : &node->right;
85	61.0M	}
86
87	7.80M	*child = new_node;
88	7.80M	new_node->parent = node;
89
90	7.80M	njs_rbtree_insert_fixup(new_node);
91
92	7.80M	node = njs_rbtree_root(tree);
93	7.80M	node->color = NJS_RBTREE_BLACK;
94	7.80M	}
95
96
97		static void
98		njs_rbtree_insert_fixup(njs_rbtree_node_t *node)
99	7.80M	{
100	7.80M	njs_rbtree_node_t parent, grandparent, *uncle;
101
102		/*
103		* Prefetching parent nodes does not help here because they are
104		* already traversed during insertion.
105		*/
106
107	10.7M	for ( ;; ) {
108	10.7M	parent = node->parent;
109
110		/*
111		* Testing whether a node is a tree root is not required here since
112		* a root node's parent is the sentinel and it is always black.
113		*/
114	10.7M	if (parent->color == NJS_RBTREE_BLACK) {
115	4.51M	return;
116	4.51M	}
117
118	6.25M	grandparent = parent->parent;
119
120	6.25M	if (parent == grandparent->left) {
121	936k	uncle = grandparent->right;
122
123	936k	if (uncle->color == NJS_RBTREE_BLACK) {
124
125	811k	if (node == parent->right) {
126	767k	node = parent;
127	767k	njs_rbtree_left_rotate(node);
128	767k	}
129
130		/*
131		* njs_rbtree_left_rotate() swaps parent and
132		* child whilst keeps grandparent the same.
133		*/
134	811k	parent = node->parent;
135
136	811k	parent->color = NJS_RBTREE_BLACK;
137	811k	grandparent->color = NJS_RBTREE_RED;
138
139	811k	njs_rbtree_right_rotate(grandparent);
140		/*
141		* njs_rbtree_right_rotate() does not change node->parent
142		* color which is now black, so testing color is not required
143		* to return from function.
144		*/
145	811k	return;
146	811k	}
147
148	5.32M	} else {
149	5.32M	uncle = grandparent->left;
150
151	5.32M	if (uncle->color == NJS_RBTREE_BLACK) {
152
153	2.48M	if (node == parent->left) {
154	64.7k	node = parent;
155	64.7k	njs_rbtree_right_rotate(node);
156	64.7k	}
157
158		/* See the comment in the symmetric branch above. */
159	2.48M	parent = node->parent;
160
161	2.48M	parent->color = NJS_RBTREE_BLACK;
162	2.48M	grandparent->color = NJS_RBTREE_RED;
163
164	2.48M	njs_rbtree_left_rotate(grandparent);
165
166		/* See the comment in the symmetric branch above. */
167	2.48M	return;
168	2.48M	}
169	5.32M	}
170
171	2.96M	uncle->color = NJS_RBTREE_BLACK;
172	2.96M	parent->color = NJS_RBTREE_BLACK;
173	2.96M	grandparent->color = NJS_RBTREE_RED;
174
175	2.96M	node = grandparent;
176	2.96M	}
177	7.80M	}
178
179
180		njs_rbtree_node_t *
181		njs_rbtree_find(njs_rbtree_t tree, njs_rbtree_part_t part)
182	17.8M	{
183	17.8M	intptr_t n;
184	17.8M	njs_rbtree_node_t node, next, *sentinel;
185	17.8M	njs_rbtree_compare_t compare;
186
187	17.8M	node = (njs_rbtree_node_t *) part;
188
189	17.8M	next = njs_rbtree_root(tree);
190	17.8M	sentinel = njs_rbtree_sentinel(tree);
191	17.8M	compare = njs_rbtree_comparison_callback(tree);
192
193	36.8M	while (next != sentinel) {
194	20.7M	njs_prefetch(next->left);
195	20.7M	njs_prefetch(next->right);
196
197	20.7M	n = compare(node, next);
198
199	20.7M	if (n < 0) {
200	3.25M	next = next->left;
201
202	17.4M	} else if (n > 0) {
203	15.7M	next = next->right;
204
205	15.7M	} else {
206	1.73M	return next;
207	1.73M	}
208	20.7M	}
209
210	16.1M	return NULL;
211	17.8M	}
212
213
214		njs_rbtree_node_t *
215		njs_rbtree_find_less_or_equal(njs_rbtree_t tree, njs_rbtree_part_t part)
216	0	{
217	0	intptr_t n;
218	0	njs_rbtree_node_t node, retval, next, sentinel;
219	0	njs_rbtree_compare_t compare;
220
221	0	node = (njs_rbtree_node_t *) part;
222
223	0	retval = NULL;
224	0	next = njs_rbtree_root(tree);
225	0	sentinel = njs_rbtree_sentinel(tree);
226	0	compare = njs_rbtree_comparison_callback(tree);
227
228	0	while (next != sentinel) {
229	0	njs_prefetch(next->left);
230	0	njs_prefetch(next->right);
231
232	0	n = compare(node, next);
233
234	0	if (n < 0) {
235	0	next = next->left;
236
237	0	} else if (n > 0) {
238	0	retval = next;
239	0	next = next->right;
240
241	0	} else {
242		/* Exact match. */
243	0	return next;
244	0	}
245	0	}
246
247	0	return retval;
248	0	}
249
250
251		njs_rbtree_node_t *
252		njs_rbtree_find_greater_or_equal(njs_rbtree_t tree, njs_rbtree_part_t part)
253	0	{
254	0	intptr_t n;
255	0	njs_rbtree_node_t node, retval, next, sentinel;
256	0	njs_rbtree_compare_t compare;
257
258	0	node = (njs_rbtree_node_t *) part;
259
260	0	retval = NULL;
261	0	next = njs_rbtree_root(tree);
262	0	sentinel = njs_rbtree_sentinel(tree);
263	0	compare = njs_rbtree_comparison_callback(tree);
264
265	0	while (next != sentinel) {
266	0	njs_prefetch(next->left);
267	0	njs_prefetch(next->right);
268
269	0	n = compare(node, next);
270
271	0	if (n < 0) {
272	0	retval = next;
273	0	next = next->left;
274
275	0	} else if (n > 0) {
276	0	next = next->right;
277
278	0	} else {
279		/* Exact match. */
280	0	return next;
281	0	}
282	0	}
283
284	0	return retval;
285	0	}
286
287
288		void
289		njs_rbtree_delete(njs_rbtree_t tree, njs_rbtree_part_t part)
290	1.78M	{
291	1.78M	uint8_t color;
292	1.78M	njs_rbtree_node_t node, sentinel, subst, child;
293
294	1.78M	node = (njs_rbtree_node_t *) part;
295
296	1.78M	subst = node;
297	1.78M	sentinel = njs_rbtree_sentinel(tree);
298
299	1.78M	if (node->left == sentinel) {
300	1.17M	child = node->right;
301
302	1.17M	} else if (node->right == sentinel) {
303	52.4k	child = node->left;
304
305	560k	} else {
306	560k	subst = njs_rbtree_branch_min(tree, node->right);
307	560k	child = subst->right;
308	560k	}
309
310	1.78M	njs_rbtree_parent_relink(child, subst);
311
312	1.78M	color = subst->color;
313
314	1.78M	if (subst != node) {
315		/* Move the subst node to the deleted node position in the tree. */
316
317	560k	subst->color = node->color;
318
319	560k	subst->left = node->left;
320	560k	subst->left->parent = subst;
321
322	560k	subst->right = node->right;
323	560k	subst->right->parent = subst;
324
325	560k	njs_rbtree_parent_relink(subst, node);
326	560k	}
327
328		#if (NJS_DEBUG)
329		node->left = NULL;
330		node->right = NULL;
331		node->parent = NULL;
332		#endif
333
334	1.78M	if (color == NJS_RBTREE_BLACK) {
335	800k	njs_rbtree_delete_fixup(tree, child);
336	800k	}
337	1.78M	}
338
339
340		static void
341		njs_rbtree_delete_fixup(njs_rbtree_t tree, njs_rbtree_node_t node)
342	800k	{
343	800k	njs_rbtree_node_t parent, sibling;
344
345	1.42M	while (node != njs_rbtree_root(tree) && node->color == NJS_RBTREE_BLACK) {
346		/*
347		* Prefetching parent nodes does not help here according
348		* to microbenchmarks.
349		*/
350	738k	parent = node->parent;
351
352	738k	if (node == parent->left) {
353	525k	sibling = parent->right;
354
355	525k	if (sibling->color != NJS_RBTREE_BLACK) {
356
357	182k	sibling->color = NJS_RBTREE_BLACK;
358	182k	parent->color = NJS_RBTREE_RED;
359
360	182k	njs_rbtree_left_rotate(parent);
361
362	182k	sibling = parent->right;
363	182k	}
364
365	525k	if (sibling->right->color == NJS_RBTREE_BLACK) {
366
367	508k	sibling->color = NJS_RBTREE_RED;
368
369	508k	if (sibling->left->color == NJS_RBTREE_BLACK) {
370	498k	node = parent;
371	498k	continue;
372	498k	}
373
374	9.80k	sibling->left->color = NJS_RBTREE_BLACK;
375
376	9.80k	njs_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 njs_rbtree_parent_relink() but also
390		* decreases the code size because C forces to reload
391		* non-restrict pointers.
392		*/
393	9.80k	sibling = parent->right;
394	9.80k	}
395
396	26.6k	sibling->color = parent->color;
397	26.6k	parent->color = NJS_RBTREE_BLACK;
398	26.6k	sibling->right->color = NJS_RBTREE_BLACK;
399
400	26.6k	njs_rbtree_left_rotate(parent);
401
402	26.6k	return;
403
404	525k	} else {
405	213k	sibling = parent->left;
406
407	213k	if (sibling->color != NJS_RBTREE_BLACK) {
408
409	28.3k	sibling->color = NJS_RBTREE_BLACK;
410	28.3k	parent->color = NJS_RBTREE_RED;
411
412	28.3k	njs_rbtree_right_rotate(parent);
413
414	28.3k	sibling = parent->left;
415	28.3k	}
416
417	213k	if (sibling->left->color == NJS_RBTREE_BLACK) {
418
419	157k	sibling->color = NJS_RBTREE_RED;
420
421	157k	if (sibling->right->color == NJS_RBTREE_BLACK) {
422	121k	node = parent;
423	121k	continue;
424	121k	}
425
426	35.3k	sibling->right->color = NJS_RBTREE_BLACK;
427
428	35.3k	njs_rbtree_left_rotate(sibling);
429
430		/* See the comment in the symmetric branch above. */
431	35.3k	sibling = parent->left;
432	35.3k	}
433
434	91.1k	sibling->color = parent->color;
435	91.1k	parent->color = NJS_RBTREE_BLACK;
436	91.1k	sibling->left->color = NJS_RBTREE_BLACK;
437
438	91.1k	njs_rbtree_right_rotate(parent);
439
440	91.1k	return;
441	213k	}
442	738k	}
443
444	682k	node->color = NJS_RBTREE_BLACK;
445	682k	}
446
447
448		njs_inline void
449		njs_rbtree_left_rotate(njs_rbtree_node_t *node)
450	3.49M	{
451	3.49M	njs_rbtree_node_t *child;
452
453	3.49M	child = node->right;
454	3.49M	node->right = child->left;
455	3.49M	child->left->parent = node;
456	3.49M	child->left = node;
457
458	3.49M	njs_rbtree_parent_relink(child, node);
459
460	3.49M	node->parent = child;
461	3.49M	}
462
463
464		njs_inline void
465		njs_rbtree_right_rotate(njs_rbtree_node_t *node)
466	1.00M	{
467	1.00M	njs_rbtree_node_t *child;
468
469	1.00M	child = node->left;
470	1.00M	node->left = child->right;
471	1.00M	child->right->parent = node;
472	1.00M	child->right = node;
473
474	1.00M	njs_rbtree_parent_relink(child, node);
475
476	1.00M	node->parent = child;
477	1.00M	}
478
479
480		/* Relink a parent from the node to the subst node. */
481
482		njs_inline void
483		njs_rbtree_parent_relink(njs_rbtree_node_t subst, njs_rbtree_node_t node)
484	6.84M	{
485	6.84M	njs_rbtree_node_t parent, *link;
486
487	6.84M	parent = node->parent;
488		/*
489		* The leaf sentinel's parent can be safely changed here.
490		* See the comment in njs_rbtree_delete_fixup() for details.
491		*/
492	6.84M	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	6.84M	link = (node == parent->left) ? &parent->left : &parent->right;
498	6.84M	*link = subst;
499	6.84M	}
500
501
502		njs_rbtree_node_t *
503		njs_rbtree_destroy_next(njs_rbtree_t tree, njs_rbtree_node_t *next)
504	2.02M	{
505	2.02M	njs_rbtree_node_t node, subst, parent, sentinel;
506
507	2.02M	sentinel = njs_rbtree_sentinel(tree);
508
509		/* Find the leftmost node. */
510	3.02M	for (node = *next; node->left != sentinel; node = node->left);
511
512		/* Replace the leftmost node with its right child. */
513	2.02M	subst = node->right;
514	2.02M	parent = node->parent;
515
516	2.02M	parent->left = subst;
517	2.02M	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	2.02M	if (subst == sentinel) {
527	1.01M	subst = parent;
528	1.01M	}
529
530	2.02M	*next = subst;
531
532	2.02M	return node;
533	2.02M	}