summaryrefslogtreecommitdiffstats
path: root/fluent-bit/lib/rbtree/rbtree.c
diff options
context:
space:
mode:
Diffstat (limited to 'fluent-bit/lib/rbtree/rbtree.c')
-rw-r--r--fluent-bit/lib/rbtree/rbtree.c811
1 files changed, 811 insertions, 0 deletions
diff --git a/fluent-bit/lib/rbtree/rbtree.c b/fluent-bit/lib/rbtree/rbtree.c
new file mode 100644
index 000000000..99e56e0c8
--- /dev/null
+++ b/fluent-bit/lib/rbtree/rbtree.c
@@ -0,0 +1,811 @@
+/*
+ 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
+ */
+
generated by cgit v1.2.3 (git 2.39.1) at 2025-02-12 06:15:11 +0000