/src/open5gs/lib/core/ogs-rbtree.c

Source
/*
 * Copyright (C) 2019 by Sukchan Lee <acetcom@gmail.com>
 *
 * This file is part of Open5GS.
 *
 * This program is free software: you can redistribute it and/or modify
 * it under the terms of the GNU Affero General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program.  If not, see <https://www.gnu.org/licenses/>.
 */

#include "ogs-core.h"

static ogs_inline void rb_change_child(ogs_rbtree_t *tree,
        ogs_rbnode_t *old, ogs_rbnode_t *new, ogs_rbnode_t *parent)
{
    if (parent) {
        if (old == parent->left)
            parent->left = new;
        else
            parent->right = new;
    } else {
        tree->root = new;
    }
}

static ogs_inline void rb_replace_node(ogs_rbtree_t *tree,
        ogs_rbnode_t *old, ogs_rbnode_t *new, ogs_rbnode_t *parent)
{
    rb_change_child(tree, old, new, parent);

    if (new)
        new->parent = parent;
}

/*
 * Example - Left rotate at A
 *
 *       A            B 
 *      / \          / \
 *     B   C  <--   D   A
 *    / \ / \      / \ / \
 *   D  3 4  5    1  2 3  C
 *  / \                  / \
 * 1   2                1   2
 */
static void rb_rotate_left(ogs_rbtree_t *tree, ogs_rbnode_t *node)
{
    ogs_rbnode_t *right = node->right;
    node->right = right->left;
    if (right->left)
        right->left->parent = node;

    rb_replace_node(tree, node, right, node->parent);

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

/*
 * Example - right rotate at A
 *
 *       A            B 
 *      / \          / \
 *     B   C  -->   D   A
 *    / \ / \      / \ / \
 *   D  3 4  5    1  2 3  C
 *  / \                  / \
 * 1   2                1   2
 */
static void rb_rotate_right(ogs_rbtree_t *tree, ogs_rbnode_t *node)
{
    ogs_rbnode_t *left = node->left;
    node->left = left->right;
    if (left->right)
        left->right->parent = node;

    rb_replace_node(tree, node, left, node->parent);

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

void ogs_rbtree_insert_color(ogs_rbtree_t *tree, void *rb_node)
{
    ogs_rbnode_t *node = rb_node;
    ogs_rbnode_t *parent;
    ogs_assert(tree);
    ogs_assert(node);

    while ((parent = node->parent) && parent->color == OGS_RBTREE_RED) {
        ogs_rbnode_t *gparent = parent->parent;
        ogs_assert(gparent);

        /* parent == grandparent's left child */
        if (parent == gparent->left) {
            ogs_rbnode_t *uncle = gparent->right;

            if (uncle && uncle->color == OGS_RBTREE_RED) {
                /*
                 * node's uncle == red (color flips)
                 *
                 *       G            g
                 *      / \          / \
                 *     p   u  -->   P   U
                 *    /            /
                 *   n            n
                 */
                uncle->color = OGS_RBTREE_BLACK;
                parent->color = OGS_RBTREE_BLACK;

                gparent->color = OGS_RBTREE_RED;

                node = gparent;
            } else {
                /* node's uncle == black */
                if (node == parent->right) {
                    /*
                     * node == the parent's right child,
                     * (left rotate at parent)
                     *
                     *      G             G
                     *     / \           / \
                     *    p   U  -->    p   U
                     *     \           /
                     *      n         n
                     */
                    node = node->parent;
                    rb_rotate_left(tree, node);
                }

                /*
                 * Now we're the left child
                 * (right rotate at grand parent)
                 *
                 *      g           P
                 *     / \         / \
                 *    P   U  -->  n   g
                 *   /                 \
                 *  n                   U
                 */
                node->parent->color = OGS_RBTREE_BLACK;
                gparent->color = OGS_RBTREE_RED;
                rb_rotate_right(tree, gparent);
            }
        /* parent  == grandparent's right child */
        } else {
            ogs_rbnode_t *uncle = gparent->left;

            if (uncle && uncle->color == OGS_RBTREE_RED) {
                /*
                 * node's uncle == red (color flips)
                 *
                 *       G            g
                 *      / \          / \
                 *     u   p  -->   U   P
                 *          \            \
                 *           n            n
                 */
                uncle->color = OGS_RBTREE_BLACK;
                parent->color = OGS_RBTREE_BLACK;

                gparent->color = OGS_RBTREE_RED;

                node = gparent;
            } else {
                /* node's uncle == black */
                if (node == parent->left) {
                    /*
                     * node == the parent's left child,
                     * (right rotate at parent)
                     *
                     *      G             G
                     *     / \           / \
                     *    p   U  -->    p   U
                     *   /               \
                     *  n                 n
                     */
                    node = node->parent;
                    rb_rotate_right(tree, node);
                }

                /*
                 * Now we're the right child,
                 * (left rotate at grand parent)
                 *
                 *      g           P
                 *     / \         / \
                 *    P   U  -->  n   g
                 *     \               \
                 *      n               U
                 */
                node->parent->color = OGS_RBTREE_BLACK;
                gparent->color = OGS_RBTREE_RED;
                rb_rotate_left(tree, gparent);
            }
        }
    }

    ogs_assert(tree->root);
    tree->root->color = OGS_RBTREE_BLACK;
}

static void rb_delete_color(
    ogs_rbtree_t *tree, ogs_rbnode_t *node, ogs_rbnode_t *parent)
{
    ogs_rbnode_t *sibling;
    ogs_assert(tree);

#define rb_is_black(r) ((!r) || (r)->color == OGS_RBTREE_BLACK)
    while (node != tree->root && rb_is_black(node)) {
        if (node == parent->left) {
            sibling = parent->right;
            if (sibling->color == OGS_RBTREE_RED) {
                /*
                 * Case 1 - left rotate at parent
                 *
                 *     P               S
                 *    / \             / \
                 *   N   s    -->    p   Sr
                 *      / \         / \
                 *     Sl  Sr      N   Sl
                 */
                sibling->color = OGS_RBTREE_BLACK;
                parent->color = OGS_RBTREE_RED;
                rb_rotate_left(tree, parent);
                sibling = parent->right;
            }
            if (rb_is_black(sibling->left) && rb_is_black(sibling->right)) {
                /*
                 * Case 2 - sibling color flip
                 * (p could be either color here)
                 *
                 *    (p)           (p)
                 *    / \           / \
                 *   N   S    -->  N   s
                 *      / \           / \
                 *     Sl  Sr        Sl  Sr
                 */
                sibling->color = OGS_RBTREE_RED;
                node = parent;
                parent = node->parent;
            } else {
                if (rb_is_black(sibling->right)) {
                    /*
                     * Case 3 - right rotate at sibling
                     * (p could be either color here)
                     *
                     *   (p)           (p)
                     *   / \           / \
                     *  N   S    -->  N   Sl
                     *     / \             \
                     *    sl  Sr            s
                     *                       \
                     *                        Sr
                     */
                    sibling->left->color = OGS_RBTREE_BLACK;
                    sibling->color = OGS_RBTREE_RED;
                    rb_rotate_right(tree, sibling);
                    sibling = parent->right;
                }
                /*
                 * Case 4 - left rotate at parent + color flips
                 * (p and sl could be either color here.
                 *  After rotation, p becomes black, s acquires
                 *  p's color, and sl keeps its color)
                 *
                 *      (p)             (s)
                 *      / \             / \
                 *     N   S     -->   P   Sr
                 *        / \         / \
                 *      (sl) sr      N  (sl)
                 */
                sibling->color = parent->color;
                parent->color = OGS_RBTREE_BLACK;
                sibling->right->color = OGS_RBTREE_BLACK;
                rb_rotate_left(tree, parent);
                node = tree->root;
            }
        } else {
            sibling = parent->left;
            if (sibling->color == OGS_RBTREE_RED) {
                sibling->color = OGS_RBTREE_BLACK;
                parent->color = OGS_RBTREE_RED;
                /* Case 1 - right rotate at parent */
                rb_rotate_right(tree, parent);
                sibling = parent->left;
            }
            if (rb_is_black(sibling->left) && rb_is_black(sibling->right)) {
                /* Case 2 - sibling color flip */
                sibling->color = OGS_RBTREE_RED;
                node = parent;
                parent = node->parent;
            } else {
                if (rb_is_black(sibling->left)) {
                    sibling->right->color = OGS_RBTREE_BLACK;
                    sibling->color = OGS_RBTREE_RED;
                    /* Case 3 - left rotate at sibling */
                    rb_rotate_left(tree, sibling);
                    sibling = parent->left;
                }
                /* Case 4 - right rotate at parent + color flips */
                sibling->color = parent->color;
                parent->color = OGS_RBTREE_BLACK;
                sibling->left->color = OGS_RBTREE_BLACK;
                rb_rotate_right(tree, parent);
                node = tree->root;
            }
        }
    }
    if (node)
        node->color = OGS_RBTREE_BLACK;
}

void ogs_rbtree_delete(ogs_rbtree_t *tree, void *rb_node)
{
    ogs_rbnode_t *node = rb_node;
    ogs_rbnode_t *child, *parent;
    ogs_rbtree_color_e color;
    ogs_assert(tree);
    ogs_assert(node);

    if (!node->left) {
        child = node->right;
        parent = node->parent;
        color = node->color;

        rb_replace_node(tree, node, child, parent);
    } else if (!node->right) {
        child = node->left;
        parent = node->parent;
        color = node->color;

        rb_replace_node(tree, node, child, parent);
    } else {
        ogs_rbnode_t *new = ogs_rbtree_min(node->right);

        child = new->right;
        parent = new->parent;
        color = new->color;

        new->left = node->left;
        node->left->parent = new;

        if (parent == node) {
            parent = new;
        } else {
            if (child) {
                child->parent = parent;
            }
            parent->left = child;

            new->right = node->right;
            node->right->parent = new;
        }

        new->color = node->color;

        rb_replace_node(tree, node, new, node->parent);
    }

    if (color == OGS_RBTREE_BLACK)
        rb_delete_color(tree, child, parent);
}

void *ogs_rbtree_first(const ogs_rbtree_t *tree)
{
    ogs_rbnode_t *node;
    ogs_assert(tree);

    node = tree->root;
    if (!node)
        return NULL;

    return ogs_rbtree_min(node);
}

void *ogs_rbtree_last(const ogs_rbtree_t *tree)
{
    ogs_rbnode_t *node;
    ogs_assert(tree);

    node = tree->root;
    if (!node)
        return NULL;

    return ogs_rbtree_max(node);
}

#define rb_empty_node(node) ((node)->parent == (node))

void *ogs_rbtree_next(const void *rb_node)
{
    const ogs_rbnode_t *node = rb_node;
    ogs_rbnode_t *parent;
    ogs_assert(node);

    if (rb_empty_node(node))
        return NULL;

    if (node->right)
        return ogs_rbtree_min(node->right);

    while ((parent = node->parent) && node == parent->right)
        node = parent;

    return parent;
}

void *ogs_rbtree_prev(const void *rb_node)
{
    const ogs_rbnode_t *node = rb_node;
    ogs_rbnode_t *parent;
    ogs_assert(node);

    if (rb_empty_node(node))
        return NULL;

    if (node->left)
        return ogs_rbtree_max(node->left);

    while ((parent = node->parent) && node == parent->left)
        node = parent;

    return parent;
}

Coverage Report

Created: 2025-12-31 06:44

Line	Count	Source
1		/*
2		* Copyright (C) 2019 by Sukchan Lee <acetcom@gmail.com>
3		*
4		* This file is part of Open5GS.
5		*
6		* This program is free software: you can redistribute it and/or modify
7		* it under the terms of the GNU Affero General Public License as published by
8		* the Free Software Foundation, either version 3 of the License, or
9		* (at your option) any later version.
10		*
11		* This program is distributed in the hope that it will be useful,
12		* but WITHOUT ANY WARRANTY; without even the implied warranty of
13		* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14		* GNU General Public License for more details.
15		*
16		* You should have received a copy of the GNU General Public License
17		* along with this program. If not, see <https://www.gnu.org/licenses/>.
18		*/
19
20		#include "ogs-core.h"
21
22		static ogs_inline void rb_change_child(ogs_rbtree_t *tree,
23		ogs_rbnode_t old, ogs_rbnode_t new, ogs_rbnode_t *parent)
24	4.95k	{
25	4.95k	if (parent) {
26	4.42k	if (old == parent->left)
27	1.98k	parent->left = new;
28	2.43k	else
29	2.43k	parent->right = new;
30	4.42k	} else {
31	526	tree->root = new;
32	526	}
33	4.95k	}
34
35		static ogs_inline void rb_replace_node(ogs_rbtree_t *tree,
36		ogs_rbnode_t old, ogs_rbnode_t new, ogs_rbnode_t *parent)
37	4.95k	{
38	4.95k	rb_change_child(tree, old, new, parent);
39
40	4.95k	if (new)
41	4.95k	new->parent = parent;
42	4.95k	}
43
44		/*
45		* Example - Left rotate at A
46		*
47		* A B
48		* / \ / \
49		* B C <-- D A
50		* / \ / \ / \ / \
51		* D 3 4 5 1 2 3 C
52		* / \ / \
53		* 1 2 1 2
54		*/
55		static void rb_rotate_left(ogs_rbtree_t tree, ogs_rbnode_t node)
56	2.78k	{
57	2.78k	ogs_rbnode_t *right = node->right;
58	2.78k	node->right = right->left;
59	2.78k	if (right->left)
60	985	right->left->parent = node;
61
62	2.78k	rb_replace_node(tree, node, right, node->parent);
63
64	2.78k	right->left = node;
65	2.78k	node->parent = right;
66	2.78k	}
67
68		/*
69		* Example - right rotate at A
70		*
71		* A B
72		* / \ / \
73		* B C --> D A
74		* / \ / \ / \ / \
75		* D 3 4 5 1 2 3 C
76		* / \ / \
77		* 1 2 1 2
78		*/
79		static void rb_rotate_right(ogs_rbtree_t tree, ogs_rbnode_t node)
80	2.16k	{
81	2.16k	ogs_rbnode_t *left = node->left;
82	2.16k	node->left = left->right;
83	2.16k	if (left->right)
84	602	left->right->parent = node;
85
86	2.16k	rb_replace_node(tree, node, left, node->parent);
87
88	2.16k	left->right = node;
89	2.16k	node->parent = left;
90	2.16k	}
91
92		void ogs_rbtree_insert_color(ogs_rbtree_t tree, void rb_node)
93	6.43k	{
94	6.43k	ogs_rbnode_t *node = rb_node;
95	6.43k	ogs_rbnode_t *parent;
96	6.43k	ogs_assert(tree);
97	6.43k	ogs_assert(node);
98
99	12.9k	while ((parent = node->parent) && parent->color == OGS_RBTREE_RED) {
100	6.54k	ogs_rbnode_t *gparent = parent->parent;
101	6.54k	ogs_assert(gparent);
102
103		/* parent == grandparent's left child */
104	6.54k	if (parent == gparent->left) {
105	2.56k	ogs_rbnode_t *uncle = gparent->right;
106
107	2.56k	if (uncle && uncle->color == OGS_RBTREE_RED) {
108		/*
109		* node's uncle == red (color flips)
110		*
111		* G g
112		* / \ / \
113		* p u --> P U
114		* / /
115		* n n
116		*/
117	1.06k	uncle->color = OGS_RBTREE_BLACK;
118	1.06k	parent->color = OGS_RBTREE_BLACK;
119
120	1.06k	gparent->color = OGS_RBTREE_RED;
121
122	1.06k	node = gparent;
123	1.50k	} else {
124		/* node's uncle == black */
125	1.50k	if (node == parent->right) {
126		/*
127		* node == the parent's right child,
128		* (left rotate at parent)
129		*
130		* G G
131		* / \ / \
132		* p U --> p U
133		* \ /
134		* n n
135		*/
136	938	node = node->parent;
137	938	rb_rotate_left(tree, node);
138	938	}
139
140		/*
141		* Now we're the left child
142		* (right rotate at grand parent)
143		*
144		* g P
145		* / \ / \
146		* P U --> n g
147		* / \
148		* n U
149		*/
150	1.50k	node->parent->color = OGS_RBTREE_BLACK;
151	1.50k	gparent->color = OGS_RBTREE_RED;
152	1.50k	rb_rotate_right(tree, gparent);
153	1.50k	}
154		/* parent == grandparent's right child */
155	3.97k	} else {
156	3.97k	ogs_rbnode_t *uncle = gparent->left;
157
158	3.97k	if (uncle && uncle->color == OGS_RBTREE_RED) {
159		/*
160		* node's uncle == red (color flips)
161		*
162		* G g
163		* / \ / \
164		* u p --> U P
165		* \ \
166		* n n
167		*/
168	2.12k	uncle->color = OGS_RBTREE_BLACK;
169	2.12k	parent->color = OGS_RBTREE_BLACK;
170
171	2.12k	gparent->color = OGS_RBTREE_RED;
172
173	2.12k	node = gparent;
174	2.12k	} else {
175		/* node's uncle == black */
176	1.85k	if (node == parent->left) {
177		/*
178		* node == the parent's left child,
179		* (right rotate at parent)
180		*
181		* G G
182		* / \ / \
183		* p U --> p U
184		* / \
185		* n n
186		*/
187	659	node = node->parent;
188	659	rb_rotate_right(tree, node);
189	659	}
190
191		/*
192		* Now we're the right child,
193		* (left rotate at grand parent)
194		*
195		* g P
196		* / \ / \
197		* P U --> n g
198		* \ \
199		* n U
200		*/
201	1.85k	node->parent->color = OGS_RBTREE_BLACK;
202	1.85k	gparent->color = OGS_RBTREE_RED;
203	1.85k	rb_rotate_left(tree, gparent);
204	1.85k	}
205	3.97k	}
206	6.54k	}
207
208	6.43k	ogs_assert(tree->root);
209	6.43k	tree->root->color = OGS_RBTREE_BLACK;
210	6.43k	}
211
212		static void rb_delete_color(
213		ogs_rbtree_t tree, ogs_rbnode_t node, ogs_rbnode_t *parent)
214	0	{
215	0	ogs_rbnode_t *sibling;
216	0	ogs_assert(tree);
217
218	0	#define rb_is_black(r) ((!r) \|\| (r)->color == OGS_RBTREE_BLACK)
219	0	while (node != tree->root && rb_is_black(node)) {
220	0	if (node == parent->left) {
221	0	sibling = parent->right;
222	0	if (sibling->color == OGS_RBTREE_RED) {
223		/*
224		* Case 1 - left rotate at parent
225		*
226		* P S
227		* / \ / \
228		* N s --> p Sr
229		* / \ / \
230		* Sl Sr N Sl
231		*/
232	0	sibling->color = OGS_RBTREE_BLACK;
233	0	parent->color = OGS_RBTREE_RED;
234	0	rb_rotate_left(tree, parent);
235	0	sibling = parent->right;
236	0	}
237	0	if (rb_is_black(sibling->left) && rb_is_black(sibling->right)) {
238		/*
239		* Case 2 - sibling color flip
240		* (p could be either color here)
241		*
242		* (p) (p)
243		* / \ / \
244		* N S --> N s
245		* / \ / \
246		* Sl Sr Sl Sr
247		*/
248	0	sibling->color = OGS_RBTREE_RED;
249	0	node = parent;
250	0	parent = node->parent;
251	0	} else {
252	0	if (rb_is_black(sibling->right)) {
253		/*
254		* Case 3 - right rotate at sibling
255		* (p could be either color here)
256		*
257		* (p) (p)
258		* / \ / \
259		* N S --> N Sl
260		* / \ \
261		* sl Sr s
262		* \
263		* Sr
264		*/
265	0	sibling->left->color = OGS_RBTREE_BLACK;
266	0	sibling->color = OGS_RBTREE_RED;
267	0	rb_rotate_right(tree, sibling);
268	0	sibling = parent->right;
269	0	}
270		/*
271		* Case 4 - left rotate at parent + color flips
272		* (p and sl could be either color here.
273		* After rotation, p becomes black, s acquires
274		* p's color, and sl keeps its color)
275		*
276		* (p) (s)
277		* / \ / \
278		* N S --> P Sr
279		* / \ / \
280		* (sl) sr N (sl)
281		*/
282	0	sibling->color = parent->color;
283	0	parent->color = OGS_RBTREE_BLACK;
284	0	sibling->right->color = OGS_RBTREE_BLACK;
285	0	rb_rotate_left(tree, parent);
286	0	node = tree->root;
287	0	}
288	0	} else {
289	0	sibling = parent->left;
290	0	if (sibling->color == OGS_RBTREE_RED) {
291	0	sibling->color = OGS_RBTREE_BLACK;
292	0	parent->color = OGS_RBTREE_RED;
293		/* Case 1 - right rotate at parent */
294	0	rb_rotate_right(tree, parent);
295	0	sibling = parent->left;
296	0	}
297	0	if (rb_is_black(sibling->left) && rb_is_black(sibling->right)) {
298		/* Case 2 - sibling color flip */
299	0	sibling->color = OGS_RBTREE_RED;
300	0	node = parent;
301	0	parent = node->parent;
302	0	} else {
303	0	if (rb_is_black(sibling->left)) {
304	0	sibling->right->color = OGS_RBTREE_BLACK;
305	0	sibling->color = OGS_RBTREE_RED;
306		/* Case 3 - left rotate at sibling */
307	0	rb_rotate_left(tree, sibling);
308	0	sibling = parent->left;
309	0	}
310		/* Case 4 - right rotate at parent + color flips */
311	0	sibling->color = parent->color;
312	0	parent->color = OGS_RBTREE_BLACK;
313	0	sibling->left->color = OGS_RBTREE_BLACK;
314	0	rb_rotate_right(tree, parent);
315	0	node = tree->root;
316	0	}
317	0	}
318	0	}
319	0	if (node)
320	0	node->color = OGS_RBTREE_BLACK;
321	0	}
322
323		void ogs_rbtree_delete(ogs_rbtree_t tree, void rb_node)
324	0	{
325	0	ogs_rbnode_t *node = rb_node;
326	0	ogs_rbnode_t child, parent;
327	0	ogs_rbtree_color_e color;
328	0	ogs_assert(tree);
329	0	ogs_assert(node);
330
331	0	if (!node->left) {
332	0	child = node->right;
333	0	parent = node->parent;
334	0	color = node->color;
335
336	0	rb_replace_node(tree, node, child, parent);
337	0	} else if (!node->right) {
338	0	child = node->left;
339	0	parent = node->parent;
340	0	color = node->color;
341
342	0	rb_replace_node(tree, node, child, parent);
343	0	} else {
344	0	ogs_rbnode_t *new = ogs_rbtree_min(node->right);
345
346	0	child = new->right;
347	0	parent = new->parent;
348	0	color = new->color;
349
350	0	new->left = node->left;
351	0	node->left->parent = new;
352
353	0	if (parent == node) {
354	0	parent = new;
355	0	} else {
356	0	if (child) {
357	0	child->parent = parent;
358	0	}
359	0	parent->left = child;
360
361	0	new->right = node->right;
362	0	node->right->parent = new;
363	0	}
364
365	0	new->color = node->color;
366
367	0	rb_replace_node(tree, node, new, node->parent);
368	0	}
369
370	0	if (color == OGS_RBTREE_BLACK)
371	0	rb_delete_color(tree, child, parent);
372	0	}
373
374		void ogs_rbtree_first(const ogs_rbtree_t tree)
375	0	{
376	0	ogs_rbnode_t *node;
377	0	ogs_assert(tree);
378
379	0	node = tree->root;
380	0	if (!node)
381	0	return NULL;
382
383	0	return ogs_rbtree_min(node);
384	0	}
385
386		void ogs_rbtree_last(const ogs_rbtree_t tree)
387	0	{
388	0	ogs_rbnode_t *node;
389	0	ogs_assert(tree);
390
391	0	node = tree->root;
392	0	if (!node)
393	0	return NULL;
394
395	0	return ogs_rbtree_max(node);
396	0	}
397
398	0	#define rb_empty_node(node) ((node)->parent == (node))
399
400		void ogs_rbtree_next(const void rb_node)
401	0	{
402	0	const ogs_rbnode_t *node = rb_node;
403	0	ogs_rbnode_t *parent;
404	0	ogs_assert(node);
405
406	0	if (rb_empty_node(node))
407	0	return NULL;
408
409	0	if (node->right)
410	0	return ogs_rbtree_min(node->right);
411
412	0	while ((parent = node->parent) && node == parent->right)
413	0	node = parent;
414
415	0	return parent;
416	0	}
417
418		void ogs_rbtree_prev(const void rb_node)
419	0	{
420	0	const ogs_rbnode_t *node = rb_node;
421	0	ogs_rbnode_t *parent;
422	0	ogs_assert(node);
423
424	0	if (rb_empty_node(node))
425	0	return NULL;
426
427	0	if (node->left)
428	0	return ogs_rbtree_max(node->left);
429
430	0	while ((parent = node->parent) && node == parent->left)
431	0	node = parent;
432
433	0	return parent;
434	0	}