/src/fluent-bit/lib/monkey/deps/rbtree/rbtree.c

Source (jump to first uncovered line)
/*
  Copyright (c) 2013, Phil Vachon <phil@cowpig.ca>
  All rights reserved.

  Redistribution and use in source and binary forms, with or without
  modification, are permitted provided that the following conditions
  are met:

  - Redistributions of source code must retain the above copyright notice,
  this list of conditions and the following disclaimer.

  - Redistributions in binary form must reproduce the above copyright notice,
  this list of conditions and the following disclaimer in the documentation
  and/or other materials provided with the distribution.

  THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
  TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
  PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR
  CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
  EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
  PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS;
  OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
  WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR
  OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
  ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */

/** \defgroup rb_tree_implementation Implementation Details
 * All the implementation details for the red-black tree, including functions for
 * the maintenance of tree properties.
 * @{
 */

/** \file rbtree.c
 * An implementation of an intrusive red-black self-balancing tree, that can
 * be used to implement red-black trees in situations where memory allocation
 * is not an option.
 *
 * This file exclusively contains implementation details for the red-black tree, so
 * probably is not of much interest to most people.
 *
 * \see rbtree.h
 * \see rb_tree
 * \see rb_tree_node
 */

#include <rbtree.h>

#include <stdlib.h>
#include <string.h>

/** \defgroup rb_tree_colors Colors for the red-black tree nodes
 * @{
 */

/**
 * Node is black
 */
#define COLOR_BLACK         0x0

/**
 * Node is red
 */
#define COLOR_RED           0x1
/**@}*/

static
int __rb_tree_cmp_mapper(void *state, const void *lhs, const void *rhs)
{
    rb_cmp_func_t cmp = state;
    return cmp(lhs, rhs);
}

rb_result_t rb_tree_new_ex(struct rb_tree *tree,
                           rb_cmp_func_ex_t compare,
                           void *state)
{
    rb_result_t ret = RB_OK;

    RB_ASSERT_ARG(tree != NULL);
    RB_ASSERT_ARG(compare != NULL);

    tree->root = NULL;
    tree->compare = compare;
    tree->state = state;
    tree->rightmost = NULL;

    return ret;
}

rb_result_t rb_tree_new(struct rb_tree *tree,
                        rb_cmp_func_t compare)
{
    RB_ASSERT_ARG(tree != NULL);
    RB_ASSERT_ARG(compare != NULL);

    return rb_tree_new_ex(tree, __rb_tree_cmp_mapper, (void *)compare);
}

rb_result_t rb_tree_destroy(struct rb_tree *tree)
{
    rb_result_t ret = RB_OK;

    RB_ASSERT_ARG(tree != NULL);

    memset(tree, 0, sizeof(struct rb_tree));

    return ret;
}

rb_result_t rb_tree_empty(struct rb_tree *tree,
                          int *is_empty)
{
    rb_result_t ret = RB_OK;

    RB_ASSERT_ARG(tree != NULL);
    RB_ASSERT_ARG(is_empty != NULL);

    *is_empty = !!(tree->root == NULL);

    return ret;
}

rb_result_t rb_tree_find(struct rb_tree *tree,
                         const void *key,
                         struct rb_tree_node **value)
{
    rb_result_t ret = RB_OK;

    RB_ASSERT_ARG(tree != NULL);
    RB_ASSERT_ARG(value != NULL);

    *value = NULL;

    if (RB_UNLIKELY(tree->root == NULL)) {
        ret = RB_NOT_FOUND;
        goto done;
    }

    struct rb_tree_node *node = tree->root;

    while (node != NULL) {
        int compare = tree->compare(tree->state, key, node->key);

        if (compare < 0) {
            node = node->left;
        } else if (compare == 0) {
            break; /* We found our node */
        } else {
            /* Otherwise, we want the right node, and continue iteration */
            node = node->right;
        }
    }

    if (node == NULL) {
        ret = RB_NOT_FOUND;
        goto done;
    }

    /* Return the node we found */
    *value = node;

done:
    return ret;
}

/* Helper function to get a node's sibling */
static inline
struct rb_tree_node *__helper_get_sibling(struct rb_tree_node *node)
{
    if (node->parent == NULL) {
        return NULL;
    }

    struct rb_tree_node *parent = node->parent;

    if (node == parent->left) {
        return parent->right;
    } else {
        return parent->left;
    }
}

/* Helper function to get a node's grandparent */
static inline
struct rb_tree_node *__helper_get_grandparent(struct rb_tree_node *node)
{
    if (node->parent == NULL) {
        return NULL;
    }

    struct rb_tree_node *parent_node = node->parent;

    return parent_node->parent;
}

/* Helper function to get a node's uncle */
static inline
struct rb_tree_node *__helper_get_uncle(struct rb_tree_node *node)
{
    struct rb_tree_node *grandparent = __helper_get_grandparent(node);

    if (grandparent == NULL) {
        return NULL;
    }

    if (node->parent == grandparent->left) {
        return grandparent->right;
    } else {
        return grandparent->left;
    }
}

/* Helper function to do a left rotation of a given node */
static inline
void __helper_rotate_left(struct rb_tree *tree,
                          struct rb_tree_node *node)
{
    struct rb_tree_node *x = node;
    struct rb_tree_node *y = x->right;

    x->right = y->left;

    if (y->left != NULL) {
        struct rb_tree_node *yleft = y->left;
        yleft->parent = x;
    }

    y->parent = x->parent;

    if (x->parent == NULL) {
        tree->root = y;
    } else {
        struct rb_tree_node *xp = x->parent;
        if (x == xp->left) {
            xp->left = y;
        } else {
            xp->right = y;
        }
    }

    y->left = x;
    x->parent = y;
}

/* Helper function to do a right rotation of a given node */
static inline
void __helper_rotate_right(struct rb_tree *tree,
                           struct rb_tree_node *node)
{
    struct rb_tree_node *x = node;
    struct rb_tree_node *y = x->left;

    x->left = y->right;

    if (y->right != NULL) {
        struct rb_tree_node *yright = y->right;
        yright->parent = x;
    }

    y->parent = x->parent;

    if (x->parent == NULL) {
        tree->root = y;
    } else {
        struct rb_tree_node *xp = x->parent;
        if (x == xp->left) {
            xp->left = y;
        } else {
            xp->right = y;
        }
    }

    y->right = x;
    x->parent = y;
}

/* Function to perform a RB tree rebalancing after an insertion */
static
void __helper_rb_tree_insert_rebalance(struct rb_tree *tree,
                                       struct rb_tree_node *node)
{
    struct rb_tree_node *new_node_parent = node->parent;

    if (new_node_parent != NULL && new_node_parent->color != COLOR_BLACK) {
        struct rb_tree_node *pnode = node;

        /* Iterate until we're at the root (which we just color black) or
         * until we the parent node is no longer red.
         */
        while ((tree->root != pnode) && (pnode->parent != NULL) &&
                    (pnode->parent->color == COLOR_RED))
        {
            struct rb_tree_node *parent = pnode->parent;
            struct rb_tree_node *grandparent = __helper_get_grandparent(pnode);
            struct rb_tree_node *uncle = NULL;
            int uncle_is_left;

            assert(pnode->color == COLOR_RED);

            if (parent == grandparent->left) {
                uncle_is_left = 0;
                uncle = grandparent->right;
            } else {
                uncle_is_left = 1;
                uncle = grandparent->left;
            }

            /* Case 1: Uncle is not black */
            if (uncle && uncle->color == COLOR_RED) {
                /* Color parent and uncle black */
                parent->color = COLOR_BLACK;
                uncle->color = COLOR_BLACK;

                /* Color Grandparent as Black */
                grandparent->color = COLOR_RED;
                pnode = grandparent;
                /* Continue iteration, processing grandparent */
            } else {
                /* Case 2 - node's parent is red, but uncle is black */
                if (!uncle_is_left && parent->right == pnode) {
                    pnode = pnode->parent;
                    __helper_rotate_left(tree, pnode);
                } else if (uncle_is_left && parent->left == pnode) {
                    pnode = pnode->parent;
                    __helper_rotate_right(tree, pnode);
                }

                /* Case 3 - Recolor and rotate*/
                parent = pnode->parent;
                parent->color = COLOR_BLACK;

                grandparent = __helper_get_grandparent(pnode);
                grandparent->color = COLOR_RED;
                if (!uncle_is_left) {
                    __helper_rotate_right(tree, grandparent);
                } else {
                    __helper_rotate_left(tree, grandparent);
                }
            }
        }

        /* Make sure the tree root is black (Case 1: Continued) */
        struct rb_tree_node *tree_root = tree->root;
        tree_root->color = COLOR_BLACK;
    }
}

rb_result_t rb_tree_insert(struct rb_tree *tree,
                           const void *key,
                           struct rb_tree_node *node)
{
    rb_result_t ret = RB_OK;

    int rightmost = 1;
    struct rb_tree_node *nd = NULL;

    RB_ASSERT_ARG(tree != NULL);
    RB_ASSERT_ARG(node != NULL);

    node->left = NULL;
    node->right = NULL;
    node->parent = NULL;
    node->key = key;

    /* Case 1: Simplest case -- tree is empty */
    if (RB_UNLIKELY(tree->root == NULL)) {
        tree->root = node;
        tree->rightmost = node;
        node->color = COLOR_BLACK;
        goto done;
    }

    /* Otherwise, insert the node as you would typically in a BST */
    nd = tree->root;
    node->color = COLOR_RED;

    rightmost = 1;

    /* Insert a node into the tree as you normally would */
    while (nd != NULL) {
        int compare = tree->compare(tree->state, node->key, nd->key);

        if (compare == 0) {
            ret = RB_DUPLICATE;
            goto done;
        }

        if (compare < 0) {
            rightmost = 0;
            if (nd->left == NULL) {
                nd->left = node;
                break;
            } else {
                nd = nd->left;
            }
        } else {
            if (nd->right == NULL) {
                nd->right = node;
                break;
            } else {
                nd = nd->right;
            }
        }
    }

    node->parent = nd;

    if (1 == rightmost) {
        tree->rightmost = node;
    }

    /* Rebalance the tree about the node we just added */
    __helper_rb_tree_insert_rebalance(tree, node);

done:
    return ret;
}

rb_result_t rb_tree_find_or_insert(struct rb_tree *tree,
                                   void *key,
                                   struct rb_tree_node *new_candidate,
                                   struct rb_tree_node **value)
{
    rb_result_t ret = RB_OK;

    RB_ASSERT_ARG(tree != NULL);
    RB_ASSERT_ARG(value != NULL);
    RB_ASSERT_ARG(new_candidate != NULL);

    *value = NULL;
    new_candidate->key = key;

    struct rb_tree_node *node = tree->root;

    /* Case 1: Tree is empty, so we just insert the node */
    if (RB_UNLIKELY(tree->root == NULL)) {
        tree->root = new_candidate;
        tree->rightmost = new_candidate;
        new_candidate->color = COLOR_BLACK;
        node = new_candidate;
        goto done;
    }

    struct rb_tree_node *node_prev = NULL;
    int dir = 0, rightmost = 1;
    while (node != NULL) {
        int compare = tree->compare(tree->state, key, node->key);

        if (compare < 0) {
            node_prev = node;
            dir = 0;
            node = node->left;
            rightmost = 0;
        } else if (compare == 0) {
            break; /* We found our node */
        } else {
            /* Otherwise, we want the right node, and continue iteration */
            node_prev = node;
            dir = 1;
            node = node->right;
        }
    }

    /* Case 2 - we didn't find the node, so insert the candidate */
    if (node == NULL) {
        if (dir == 0) {
            rightmost = 0;
            node_prev->left = new_candidate;
        } else {
            node_prev->right = new_candidate;
        }

        new_candidate->parent = node_prev;

        node = new_candidate;
        node->color = COLOR_RED;

        if (1 == rightmost) {
            tree->rightmost = new_candidate;
        }

        /* Rebalance the tree, preserving rb properties */
        __helper_rb_tree_insert_rebalance(tree, node);
    }

done:
    /* Return the node we found */
    *value = node;

    return ret;
}

/**
 * Find the minimum of the subtree starting at node
 */
static
struct rb_tree_node *__helper_rb_tree_find_minimum(struct rb_tree_node *node)
{
    struct rb_tree_node *x = node;

    while (x->left != NULL) {
        x = x->left;
    }

    return x;
}

static
struct rb_tree_node *__helper_rb_tree_find_maximum(struct rb_tree_node *node)
{
    struct rb_tree_node *x = node;

    while (x->right != NULL) {
        x = x->right;
    }

    return x;
}

static
struct rb_tree_node *__helper_rb_tree_find_successor(struct rb_tree_node *node)
{
    struct rb_tree_node *x = node;

    if (x->right != NULL) {
        return __helper_rb_tree_find_minimum(x->right);
    }

    struct rb_tree_node *y = x->parent;

    while (y != NULL && x == y->right) {
        x = y;
        y = y->parent;
    }

    return y;
}

static
struct rb_tree_node *__helper_rb_tree_find_predecessor(struct rb_tree_node *node)
{
    struct rb_tree_node *x = node;

    if (x->left != NULL) {
        return __helper_rb_tree_find_maximum(x->left);
    }

    struct rb_tree_node *y = x->parent;

    while (y != NULL && x == y->left) {
        x = y;
        y = y->parent;
    }

    return y;
}


/* Replace x with y, inserting y where x previously was */
static
void __helper_rb_tree_swap_node(struct rb_tree *tree,
                                struct rb_tree_node *x,
                                struct rb_tree_node *y)
{
    struct rb_tree_node *left = x->left;
    struct rb_tree_node *right = x->right;
    struct rb_tree_node *parent = x->parent;

    y->parent = parent;

    if (parent != NULL) {
        if (parent->left == x) {
            parent->left = y;
        } else {
            parent->right = y;
        }
    } else {
        if (tree->root == x) {
            tree->root = y;
        }
    }

    y->right = right;
    if (right != NULL) {
        right->parent = y;
    }
    x->right = NULL;

    y->left = left;
    if (left != NULL) {
        left->parent = y;
    }
    x->left = NULL;

    y->color = x->color;
    x->parent = NULL;
}

static
void __helper_rb_tree_delete_rebalance(struct rb_tree *tree,
                                       struct rb_tree_node *node,
                                       struct rb_tree_node *parent,
                                       int node_is_left)
{
    struct rb_tree_node *x = node;
    struct rb_tree_node *xp = parent;
    int is_left = node_is_left;

    while (x != tree->root && (x == NULL || x->color == COLOR_BLACK)) {
        struct rb_tree_node *w = is_left ? xp->right : xp->left;    /* Sibling */

        if (w != NULL && w->color == COLOR_RED) {
            /* Case 1: */
            w->color = COLOR_BLACK;
            xp->color = COLOR_RED;
            if (is_left) {
                __helper_rotate_left(tree, xp);
            } else {
                __helper_rotate_right(tree, xp);
            }
            w = is_left ? xp->right : xp->left;
        }

        struct rb_tree_node *wleft = w != NULL ? w->left : NULL;
        struct rb_tree_node *wright = w != NULL ? w->right : NULL;
        if ( (wleft == NULL || wleft->color == COLOR_BLACK) &&
             (wright == NULL || wright->color == COLOR_BLACK) )
        {
            /* Case 2: */
            if (w != NULL) {
                w->color = COLOR_RED;
            }
            x = xp;
            xp = x->parent;
            is_left = xp && (x == xp->left);
        } else {
            if (is_left && (wright == NULL || wright->color == COLOR_BLACK)) {
                /* Case 3a: */
                w->color = COLOR_RED;
                if (wleft) {
                    wleft->color = COLOR_BLACK;
                }
                __helper_rotate_right(tree, w);
                w = xp->right;
            } else if (!is_left && (wleft == NULL || wleft->color == COLOR_BLACK)) {
                /* Case 3b: */
                w->color = COLOR_RED;
                if (wright) {
                    wright->color = COLOR_BLACK;
                }
                __helper_rotate_left(tree, w);
                w = xp->left;
            }

            /* Case 4: */
            wleft = w->left;
            wright = w->right;

            w->color = xp->color;
            xp->color = COLOR_BLACK;

            if (is_left && wright != NULL) {
                wright->color = COLOR_BLACK;
                __helper_rotate_left(tree, xp);
            } else if (!is_left && wleft != NULL) {
                wleft->color = COLOR_BLACK;
                __helper_rotate_right(tree, xp);
            }
            x = tree->root;
        }
    }

    if (x != NULL) {
        x->color = COLOR_BLACK;
    }
}

rb_result_t rb_tree_remove(struct rb_tree *tree,
                           struct rb_tree_node *node)
{
    rb_result_t ret = RB_OK;

    RB_ASSERT_ARG(tree != NULL);
    RB_ASSERT_ARG(node != NULL);

    struct rb_tree_node *y;


    if (node->left == NULL || node->right == NULL) {
        y = node;
        if (node == tree->rightmost) {
            /* The new rightmost item is our successor */
            tree->rightmost = __helper_rb_tree_find_predecessor(node);
        }
    } else {
        y = __helper_rb_tree_find_successor(node);
    }

    struct rb_tree_node *x, *xp;

    if (y->left != NULL) {
        x = y->left;
    } else {
        x = y->right;
    }

    if (x != NULL) {
        x->parent = y->parent;
        xp = x->parent;
    } else {
        xp = y->parent;
    }

    int is_left = 0;
    if (y->parent == NULL) {
        tree->root = x;
        xp = NULL;
    } else {
        struct rb_tree_node *yp = y->parent;
        if (y == yp->left) {
            yp->left = x;
            is_left = 1;
        } else {
            yp->right = x;
            is_left = 0;
        }
    }

    int y_color = y->color;

    /* Swap in the node */
    if (y != node) {
        __helper_rb_tree_swap_node(tree, node, y);
        if (xp == node) {
            xp = y;
        }
    }

    if (y_color == COLOR_BLACK) {
        __helper_rb_tree_delete_rebalance(tree, x, xp, is_left);
    }

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

    return ret;
}

/**
 * \mainpage An Intrusive Red-Black Tree
 *
 * The goal of this implementation is to be both easy to use, but also
 * sufficiently powerful enough to perform all the operations that one might
 * typically want to do with a red-black tree.
 *
 * To make a structure usable with an rb_tree, you must embed the structure
 * struct rb_tree_node. 
 * \code
    struct my_sample_struct {
        const char *name;
        int data;
        struct rb_tree_node rnode;
    };
 * \endcode
 * \note `rb_tree_node` need not be initialized -- it is initialized during the
 *       insertion operation.
 *
 * Next, you must declare a comparison function that, given a pointer to two
 * keys, returns a value less than 0 if the left-hand side is less than the
 * right-hand side, 0 if the left-hand side is equal to the right-hand side,
 * or greater than 0 if the left-hand side is greater than the left-hand side.
 *
 * A simple example for a string might use the `strcmp(3)` function directly,
 * as such:
 *
 * \code
    int my_sample_struct_compare_keys(void *lhs, void *rhs)
    {
        return strcmp((const char *)lhs, (const char *)rhs);
    }
 * \endcode
 * \note the function you create for your comparison function must conform to
 *       rb_cmp_func_t, or the compiler will generate a warning and, if you're
 *       unlucky, you will fail catastrophically at a later date.
 *
 * Then, to create a new, empty red-black tree, call rb_tree_new, as so:
 * \code
    struct rb_tree my_rb_tree;
    if (rb_tree_new(&my_rb_tree, my_sample_struct_compare_keys) != RB_OK) {
        exit(EXIT_FAILURE);
    }
 * \endcode
 *
 * Items can be added to the red-black tree using the function `rb_tree_insert`:
 * \code
    struct my_sample_struct node = { .name = "test1", .date = 42 };
    if (rb_tree_insert(&my_rb_tree, node.name, &(node.rnode)) != RB_OK) {
        printf("Failed to insert a node into the RB tree!\n");
        exit(EXIT_FAILURE);
    }
 * \endcode
 *
 * \see rb_tree
 * \see rb_tree_node
 * \see rb_functions
 * \see rbtree.h
 */


Coverage Report

Created: 2025-09-04 07:51

Line	Count	Source (jump to first uncovered line)
1		/*
2		Copyright (c) 2013, Phil Vachon <phil@cowpig.ca>
3		All rights reserved.
4
5		Redistribution and use in source and binary forms, with or without
6		modification, are permitted provided that the following conditions
7		are met:
8
9		- Redistributions of source code must retain the above copyright notice,
10		this list of conditions and the following disclaimer.
11
12		- Redistributions in binary form must reproduce the above copyright notice,
13		this list of conditions and the following disclaimer in the documentation
14		and/or other materials provided with the distribution.
15
16		THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
17		"AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
18		TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
19		PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR
20		CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
21		EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
22		PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS;
23		OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
24		WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR
25		OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
26		ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
27		*/
28
29		/** \defgroup rb_tree_implementation Implementation Details
30		* All the implementation details for the red-black tree, including functions for
31		* the maintenance of tree properties.
32		* @{
33		*/
34
35		/** \file rbtree.c
36		* An implementation of an intrusive red-black self-balancing tree, that can
37		* be used to implement red-black trees in situations where memory allocation
38		* is not an option.
39		*
40		* This file exclusively contains implementation details for the red-black tree, so
41		* probably is not of much interest to most people.
42		*
43		* \see rbtree.h
44		* \see rb_tree
45		* \see rb_tree_node
46		*/
47
48		#include <rbtree.h>
49
50		#include <stdlib.h>
51		#include <string.h>
52
53		/** \defgroup rb_tree_colors Colors for the red-black tree nodes
54		* @{
55		*/
56
57		/**
58		* Node is black
59		*/
60	0	#define COLOR_BLACK 0x0
61
62		/**
63		* Node is red
64		*/
65	0	#define COLOR_RED 0x1
66		/*@}/
67
68		static
69		int __rb_tree_cmp_mapper(void state, const void lhs, const void *rhs)
70	0	{
71	0	rb_cmp_func_t cmp = state;
72	0	return cmp(lhs, rhs);
73	0	}
74
75		rb_result_t rb_tree_new_ex(struct rb_tree *tree,
76		rb_cmp_func_ex_t compare,
77		void *state)
78	0	{
79	0	rb_result_t ret = RB_OK;
80
81	0	RB_ASSERT_ARG(tree != NULL);
82	0	RB_ASSERT_ARG(compare != NULL);
83
84	0	tree->root = NULL;
85	0	tree->compare = compare;
86	0	tree->state = state;
87	0	tree->rightmost = NULL;
88
89	0	return ret;
90	0	}
91
92		rb_result_t rb_tree_new(struct rb_tree *tree,
93		rb_cmp_func_t compare)
94	0	{
95	0	RB_ASSERT_ARG(tree != NULL);
96	0	RB_ASSERT_ARG(compare != NULL);
97
98	0	return rb_tree_new_ex(tree, __rb_tree_cmp_mapper, (void *)compare);
99	0	}
100
101		rb_result_t rb_tree_destroy(struct rb_tree *tree)
102	0	{
103	0	rb_result_t ret = RB_OK;
104
105	0	RB_ASSERT_ARG(tree != NULL);
106
107	0	memset(tree, 0, sizeof(struct rb_tree));
108
109	0	return ret;
110	0	}
111
112		rb_result_t rb_tree_empty(struct rb_tree *tree,
113		int *is_empty)
114	0	{
115	0	rb_result_t ret = RB_OK;
116
117	0	RB_ASSERT_ARG(tree != NULL);
118	0	RB_ASSERT_ARG(is_empty != NULL);
119
120	0	*is_empty = !!(tree->root == NULL);
121
122	0	return ret;
123	0	}
124
125		rb_result_t rb_tree_find(struct rb_tree *tree,
126		const void *key,
127		struct rb_tree_node **value)
128	0	{
129	0	rb_result_t ret = RB_OK;
130
131	0	RB_ASSERT_ARG(tree != NULL);
132	0	RB_ASSERT_ARG(value != NULL);
133
134	0	*value = NULL;
135
136	0	if (RB_UNLIKELY(tree->root == NULL)) {
137	0	ret = RB_NOT_FOUND;
138	0	goto done;
139	0	}
140
141	0	struct rb_tree_node *node = tree->root;
142
143	0	while (node != NULL) {
144	0	int compare = tree->compare(tree->state, key, node->key);
145
146	0	if (compare < 0) {
147	0	node = node->left;
148	0	} else if (compare == 0) {
149	0	break; /* We found our node */
150	0	} else {
151		/* Otherwise, we want the right node, and continue iteration */
152	0	node = node->right;
153	0	}
154	0	}
155
156	0	if (node == NULL) {
157	0	ret = RB_NOT_FOUND;
158	0	goto done;
159	0	}
160
161		/* Return the node we found */
162	0	*value = node;
163
164	0	done:
165	0	return ret;
166	0	}
167
168		/* Helper function to get a node's sibling */
169		static inline
170		struct rb_tree_node __helper_get_sibling(struct rb_tree_node node)
171	0	{
172	0	if (node->parent == NULL) {
173	0	return NULL;
174	0	}
175	0
176	0	struct rb_tree_node *parent = node->parent;
177	0
178	0	if (node == parent->left) {
179	0	return parent->right;
180	0	} else {
181	0	return parent->left;
182	0	}
183	0	}
184
185		/* Helper function to get a node's grandparent */
186		static inline
187		struct rb_tree_node __helper_get_grandparent(struct rb_tree_node node)
188	0	{
189	0	if (node->parent == NULL) {
190	0	return NULL;
191	0	}
192
193	0	struct rb_tree_node *parent_node = node->parent;
194
195	0	return parent_node->parent;
196	0	}
197
198		/* Helper function to get a node's uncle */
199		static inline
200		struct rb_tree_node __helper_get_uncle(struct rb_tree_node node)
201	0	{
202	0	struct rb_tree_node *grandparent = __helper_get_grandparent(node);
203	0
204	0	if (grandparent == NULL) {
205	0	return NULL;
206	0	}
207	0
208	0	if (node->parent == grandparent->left) {
209	0	return grandparent->right;
210	0	} else {
211	0	return grandparent->left;
212	0	}
213	0	}
214
215		/* Helper function to do a left rotation of a given node */
216		static inline
217		void __helper_rotate_left(struct rb_tree *tree,
218		struct rb_tree_node *node)
219	0	{
220	0	struct rb_tree_node *x = node;
221	0	struct rb_tree_node *y = x->right;
222
223	0	x->right = y->left;
224
225	0	if (y->left != NULL) {
226	0	struct rb_tree_node *yleft = y->left;
227	0	yleft->parent = x;
228	0	}
229
230	0	y->parent = x->parent;
231
232	0	if (x->parent == NULL) {
233	0	tree->root = y;
234	0	} else {
235	0	struct rb_tree_node *xp = x->parent;
236	0	if (x == xp->left) {
237	0	xp->left = y;
238	0	} else {
239	0	xp->right = y;
240	0	}
241	0	}
242
243	0	y->left = x;
244	0	x->parent = y;
245	0	}
246
247		/* Helper function to do a right rotation of a given node */
248		static inline
249		void __helper_rotate_right(struct rb_tree *tree,
250		struct rb_tree_node *node)
251	0	{
252	0	struct rb_tree_node *x = node;
253	0	struct rb_tree_node *y = x->left;
254
255	0	x->left = y->right;
256
257	0	if (y->right != NULL) {
258	0	struct rb_tree_node *yright = y->right;
259	0	yright->parent = x;
260	0	}
261
262	0	y->parent = x->parent;
263
264	0	if (x->parent == NULL) {
265	0	tree->root = y;
266	0	} else {
267	0	struct rb_tree_node *xp = x->parent;
268	0	if (x == xp->left) {
269	0	xp->left = y;
270	0	} else {
271	0	xp->right = y;
272	0	}
273	0	}
274
275	0	y->right = x;
276	0	x->parent = y;
277	0	}
278
279		/* Function to perform a RB tree rebalancing after an insertion */
280		static
281		void __helper_rb_tree_insert_rebalance(struct rb_tree *tree,
282		struct rb_tree_node *node)
283	0	{
284	0	struct rb_tree_node *new_node_parent = node->parent;
285
286	0	if (new_node_parent != NULL && new_node_parent->color != COLOR_BLACK) {
287	0	struct rb_tree_node *pnode = node;
288
289		/* Iterate until we're at the root (which we just color black) or
290		* until we the parent node is no longer red.
291		*/
292	0	while ((tree->root != pnode) && (pnode->parent != NULL) &&
293	0	(pnode->parent->color == COLOR_RED))
294	0	{
295	0	struct rb_tree_node *parent = pnode->parent;
296	0	struct rb_tree_node *grandparent = __helper_get_grandparent(pnode);
297	0	struct rb_tree_node *uncle = NULL;
298	0	int uncle_is_left;
299
300	0	assert(pnode->color == COLOR_RED);
301
302	0	if (parent == grandparent->left) {
303	0	uncle_is_left = 0;
304	0	uncle = grandparent->right;
305	0	} else {
306	0	uncle_is_left = 1;
307	0	uncle = grandparent->left;
308	0	}
309
310		/* Case 1: Uncle is not black */
311	0	if (uncle && uncle->color == COLOR_RED) {
312		/* Color parent and uncle black */
313	0	parent->color = COLOR_BLACK;
314	0	uncle->color = COLOR_BLACK;
315
316		/* Color Grandparent as Black */
317	0	grandparent->color = COLOR_RED;
318	0	pnode = grandparent;
319		/* Continue iteration, processing grandparent */
320	0	} else {
321		/* Case 2 - node's parent is red, but uncle is black */
322	0	if (!uncle_is_left && parent->right == pnode) {
323	0	pnode = pnode->parent;
324	0	__helper_rotate_left(tree, pnode);
325	0	} else if (uncle_is_left && parent->left == pnode) {
326	0	pnode = pnode->parent;
327	0	__helper_rotate_right(tree, pnode);
328	0	}
329
330		/* Case 3 - Recolor and rotate*/
331	0	parent = pnode->parent;
332	0	parent->color = COLOR_BLACK;
333
334	0	grandparent = __helper_get_grandparent(pnode);
335	0	grandparent->color = COLOR_RED;
336	0	if (!uncle_is_left) {
337	0	__helper_rotate_right(tree, grandparent);
338	0	} else {
339	0	__helper_rotate_left(tree, grandparent);
340	0	}
341	0	}
342	0	}
343
344		/* Make sure the tree root is black (Case 1: Continued) */
345	0	struct rb_tree_node *tree_root = tree->root;
346	0	tree_root->color = COLOR_BLACK;
347	0	}
348	0	}
349
350		rb_result_t rb_tree_insert(struct rb_tree *tree,
351		const void *key,
352		struct rb_tree_node *node)
353	0	{
354	0	rb_result_t ret = RB_OK;
355
356	0	int rightmost = 1;
357	0	struct rb_tree_node *nd = NULL;
358
359	0	RB_ASSERT_ARG(tree != NULL);
360	0	RB_ASSERT_ARG(node != NULL);
361
362	0	node->left = NULL;
363	0	node->right = NULL;
364	0	node->parent = NULL;
365	0	node->key = key;
366
367		/* Case 1: Simplest case -- tree is empty */
368	0	if (RB_UNLIKELY(tree->root == NULL)) {
369	0	tree->root = node;
370	0	tree->rightmost = node;
371	0	node->color = COLOR_BLACK;
372	0	goto done;
373	0	}
374
375		/* Otherwise, insert the node as you would typically in a BST */
376	0	nd = tree->root;
377	0	node->color = COLOR_RED;
378
379	0	rightmost = 1;
380
381		/* Insert a node into the tree as you normally would */
382	0	while (nd != NULL) {
383	0	int compare = tree->compare(tree->state, node->key, nd->key);
384
385	0	if (compare == 0) {
386	0	ret = RB_DUPLICATE;
387	0	goto done;
388	0	}
389
390	0	if (compare < 0) {
391	0	rightmost = 0;
392	0	if (nd->left == NULL) {
393	0	nd->left = node;
394	0	break;
395	0	} else {
396	0	nd = nd->left;
397	0	}
398	0	} else {
399	0	if (nd->right == NULL) {
400	0	nd->right = node;
401	0	break;
402	0	} else {
403	0	nd = nd->right;
404	0	}
405	0	}
406	0	}
407
408	0	node->parent = nd;
409
410	0	if (1 == rightmost) {
411	0	tree->rightmost = node;
412	0	}
413
414		/* Rebalance the tree about the node we just added */
415	0	__helper_rb_tree_insert_rebalance(tree, node);
416
417	0	done:
418	0	return ret;
419	0	}
420
421		rb_result_t rb_tree_find_or_insert(struct rb_tree *tree,
422		void *key,
423		struct rb_tree_node *new_candidate,
424		struct rb_tree_node **value)
425	0	{
426	0	rb_result_t ret = RB_OK;
427
428	0	RB_ASSERT_ARG(tree != NULL);
429	0	RB_ASSERT_ARG(value != NULL);
430	0	RB_ASSERT_ARG(new_candidate != NULL);
431
432	0	*value = NULL;
433	0	new_candidate->key = key;
434
435	0	struct rb_tree_node *node = tree->root;
436
437		/* Case 1: Tree is empty, so we just insert the node */
438	0	if (RB_UNLIKELY(tree->root == NULL)) {
439	0	tree->root = new_candidate;
440	0	tree->rightmost = new_candidate;
441	0	new_candidate->color = COLOR_BLACK;
442	0	node = new_candidate;
443	0	goto done;
444	0	}
445
446	0	struct rb_tree_node *node_prev = NULL;
447	0	int dir = 0, rightmost = 1;
448	0	while (node != NULL) {
449	0	int compare = tree->compare(tree->state, key, node->key);
450
451	0	if (compare < 0) {
452	0	node_prev = node;
453	0	dir = 0;
454	0	node = node->left;
455	0	rightmost = 0;
456	0	} else if (compare == 0) {
457	0	break; /* We found our node */
458	0	} else {
459		/* Otherwise, we want the right node, and continue iteration */
460	0	node_prev = node;
461	0	dir = 1;
462	0	node = node->right;
463	0	}
464	0	}
465
466		/* Case 2 - we didn't find the node, so insert the candidate */
467	0	if (node == NULL) {
468	0	if (dir == 0) {
469	0	rightmost = 0;
470	0	node_prev->left = new_candidate;
471	0	} else {
472	0	node_prev->right = new_candidate;
473	0	}
474
475	0	new_candidate->parent = node_prev;
476
477	0	node = new_candidate;
478	0	node->color = COLOR_RED;
479
480	0	if (1 == rightmost) {
481	0	tree->rightmost = new_candidate;
482	0	}
483
484		/* Rebalance the tree, preserving rb properties */
485	0	__helper_rb_tree_insert_rebalance(tree, node);
486	0	}
487
488	0	done:
489		/* Return the node we found */
490	0	*value = node;
491
492	0	return ret;
493	0	}
494
495		/**
496		* Find the minimum of the subtree starting at node
497		*/
498		static
499		struct rb_tree_node __helper_rb_tree_find_minimum(struct rb_tree_node node)
500	0	{
501	0	struct rb_tree_node *x = node;
502
503	0	while (x->left != NULL) {
504	0	x = x->left;
505	0	}
506
507	0	return x;
508	0	}
509
510		static
511		struct rb_tree_node __helper_rb_tree_find_maximum(struct rb_tree_node node)
512	0	{
513	0	struct rb_tree_node *x = node;
514
515	0	while (x->right != NULL) {
516	0	x = x->right;
517	0	}
518
519	0	return x;
520	0	}
521
522		static
523		struct rb_tree_node __helper_rb_tree_find_successor(struct rb_tree_node node)
524	0	{
525	0	struct rb_tree_node *x = node;
526
527	0	if (x->right != NULL) {
528	0	return __helper_rb_tree_find_minimum(x->right);
529	0	}
530
531	0	struct rb_tree_node *y = x->parent;
532
533	0	while (y != NULL && x == y->right) {
534	0	x = y;
535	0	y = y->parent;
536	0	}
537
538	0	return y;
539	0	}
540
541		static
542		struct rb_tree_node __helper_rb_tree_find_predecessor(struct rb_tree_node node)
543	0	{
544	0	struct rb_tree_node *x = node;
545
546	0	if (x->left != NULL) {
547	0	return __helper_rb_tree_find_maximum(x->left);
548	0	}
549
550	0	struct rb_tree_node *y = x->parent;
551
552	0	while (y != NULL && x == y->left) {
553	0	x = y;
554	0	y = y->parent;
555	0	}
556
557	0	return y;
558	0	}
559
560
561		/* Replace x with y, inserting y where x previously was */
562		static
563		void __helper_rb_tree_swap_node(struct rb_tree *tree,
564		struct rb_tree_node *x,
565		struct rb_tree_node *y)
566	0	{
567	0	struct rb_tree_node *left = x->left;
568	0	struct rb_tree_node *right = x->right;
569	0	struct rb_tree_node *parent = x->parent;
570
571	0	y->parent = parent;
572
573	0	if (parent != NULL) {
574	0	if (parent->left == x) {
575	0	parent->left = y;
576	0	} else {
577	0	parent->right = y;
578	0	}
579	0	} else {
580	0	if (tree->root == x) {
581	0	tree->root = y;
582	0	}
583	0	}
584
585	0	y->right = right;
586	0	if (right != NULL) {
587	0	right->parent = y;
588	0	}
589	0	x->right = NULL;
590
591	0	y->left = left;
592	0	if (left != NULL) {
593	0	left->parent = y;
594	0	}
595	0	x->left = NULL;
596
597	0	y->color = x->color;
598	0	x->parent = NULL;
599	0	}
600
601		static
602		void __helper_rb_tree_delete_rebalance(struct rb_tree *tree,
603		struct rb_tree_node *node,
604		struct rb_tree_node *parent,
605		int node_is_left)
606	0	{
607	0	struct rb_tree_node *x = node;
608	0	struct rb_tree_node *xp = parent;
609	0	int is_left = node_is_left;
610
611	0	while (x != tree->root && (x == NULL \|\| x->color == COLOR_BLACK)) {
612	0	struct rb_tree_node w = is_left ? xp->right : xp->left; / Sibling */
613
614	0	if (w != NULL && w->color == COLOR_RED) {
615		/* Case 1: */
616	0	w->color = COLOR_BLACK;
617	0	xp->color = COLOR_RED;
618	0	if (is_left) {
619	0	__helper_rotate_left(tree, xp);
620	0	} else {
621	0	__helper_rotate_right(tree, xp);
622	0	}
623	0	w = is_left ? xp->right : xp->left;
624	0	}
625
626	0	struct rb_tree_node *wleft = w != NULL ? w->left : NULL;
627	0	struct rb_tree_node *wright = w != NULL ? w->right : NULL;
628	0	if ( (wleft == NULL \|\| wleft->color == COLOR_BLACK) &&
629	0	(wright == NULL \|\| wright->color == COLOR_BLACK) )
630	0	{
631		/* Case 2: */
632	0	if (w != NULL) {
633	0	w->color = COLOR_RED;
634	0	}
635	0	x = xp;
636	0	xp = x->parent;
637	0	is_left = xp && (x == xp->left);
638	0	} else {
639	0	if (is_left && (wright == NULL \|\| wright->color == COLOR_BLACK)) {
640		/* Case 3a: */
641	0	w->color = COLOR_RED;
642	0	if (wleft) {
643	0	wleft->color = COLOR_BLACK;
644	0	}
645	0	__helper_rotate_right(tree, w);
646	0	w = xp->right;
647	0	} else if (!is_left && (wleft == NULL \|\| wleft->color == COLOR_BLACK)) {
648		/* Case 3b: */
649	0	w->color = COLOR_RED;
650	0	if (wright) {
651	0	wright->color = COLOR_BLACK;
652	0	}
653	0	__helper_rotate_left(tree, w);
654	0	w = xp->left;
655	0	}
656
657		/* Case 4: */
658	0	wleft = w->left;
659	0	wright = w->right;
660
661	0	w->color = xp->color;
662	0	xp->color = COLOR_BLACK;
663
664	0	if (is_left && wright != NULL) {
665	0	wright->color = COLOR_BLACK;
666	0	__helper_rotate_left(tree, xp);
667	0	} else if (!is_left && wleft != NULL) {
668	0	wleft->color = COLOR_BLACK;
669	0	__helper_rotate_right(tree, xp);
670	0	}
671	0	x = tree->root;
672	0	}
673	0	}
674
675	0	if (x != NULL) {
676	0	x->color = COLOR_BLACK;
677	0	}
678	0	}
679
680		rb_result_t rb_tree_remove(struct rb_tree *tree,
681		struct rb_tree_node *node)
682	0	{
683	0	rb_result_t ret = RB_OK;
684
685	0	RB_ASSERT_ARG(tree != NULL);
686	0	RB_ASSERT_ARG(node != NULL);
687
688	0	struct rb_tree_node *y;
689
690
691	0	if (node->left == NULL \|\| node->right == NULL) {
692	0	y = node;
693	0	if (node == tree->rightmost) {
694		/* The new rightmost item is our successor */
695	0	tree->rightmost = __helper_rb_tree_find_predecessor(node);
696	0	}
697	0	} else {
698	0	y = __helper_rb_tree_find_successor(node);
699	0	}
700
701	0	struct rb_tree_node x, xp;
702
703	0	if (y->left != NULL) {
704	0	x = y->left;
705	0	} else {
706	0	x = y->right;
707	0	}
708
709	0	if (x != NULL) {
710	0	x->parent = y->parent;
711	0	xp = x->parent;
712	0	} else {
713	0	xp = y->parent;
714	0	}
715
716	0	int is_left = 0;
717	0	if (y->parent == NULL) {
718	0	tree->root = x;
719	0	xp = NULL;
720	0	} else {
721	0	struct rb_tree_node *yp = y->parent;
722	0	if (y == yp->left) {
723	0	yp->left = x;
724	0	is_left = 1;
725	0	} else {
726	0	yp->right = x;
727	0	is_left = 0;
728	0	}
729	0	}
730
731	0	int y_color = y->color;
732
733		/* Swap in the node */
734	0	if (y != node) {
735	0	__helper_rb_tree_swap_node(tree, node, y);
736	0	if (xp == node) {
737	0	xp = y;
738	0	}
739	0	}
740
741	0	if (y_color == COLOR_BLACK) {
742	0	__helper_rb_tree_delete_rebalance(tree, x, xp, is_left);
743	0	}
744
745	0	node->parent = NULL;
746	0	node->left = NULL;
747	0	node->right = NULL;
748
749	0	return ret;
750	0	}
751
752		/**
753		* \mainpage An Intrusive Red-Black Tree
754		*
755		* The goal of this implementation is to be both easy to use, but also
756		* sufficiently powerful enough to perform all the operations that one might
757		* typically want to do with a red-black tree.
758		*
759		* To make a structure usable with an rb_tree, you must embed the structure
760		* struct rb_tree_node.
761		* \code
762		struct my_sample_struct {
763		const char *name;
764		int data;
765		struct rb_tree_node rnode;
766		};
767		* \endcode
768		* \note `rb_tree_node` need not be initialized -- it is initialized during the
769		* insertion operation.
770		*
771		* Next, you must declare a comparison function that, given a pointer to two
772		* keys, returns a value less than 0 if the left-hand side is less than the
773		* right-hand side, 0 if the left-hand side is equal to the right-hand side,
774		* or greater than 0 if the left-hand side is greater than the left-hand side.
775		*
776		* A simple example for a string might use the `strcmp(3)` function directly,
777		* as such:
778		*
779		* \code
780		int my_sample_struct_compare_keys(void lhs, void rhs)
781		{
782		return strcmp((const char )lhs, (const char )rhs);
783		}
784		* \endcode
785		* \note the function you create for your comparison function must conform to
786		* rb_cmp_func_t, or the compiler will generate a warning and, if you're
787		* unlucky, you will fail catastrophically at a later date.
788		*
789		* Then, to create a new, empty red-black tree, call rb_tree_new, as so:
790		* \code
791		struct rb_tree my_rb_tree;
792		if (rb_tree_new(&my_rb_tree, my_sample_struct_compare_keys) != RB_OK) {
793		exit(EXIT_FAILURE);
794		}
795		* \endcode
796		*
797		* Items can be added to the red-black tree using the function `rb_tree_insert`:
798		* \code
799		struct my_sample_struct node = { .name = "test1", .date = 42 };
800		if (rb_tree_insert(&my_rb_tree, node.name, &(node.rnode)) != RB_OK) {
801		printf("Failed to insert a node into the RB tree!\n");
802		exit(EXIT_FAILURE);
803		}
804		* \endcode
805		*
806		* \see rb_tree
807		* \see rb_tree_node
808		* \see rb_functions
809		* \see rbtree.h
810		*/
811