diff options
Diffstat (limited to 'fluent-bit/lib/rbtree')
| -rw-r--r-- | fluent-bit/lib/rbtree/CMakeLists.txt | 5 | ||||
| -rw-r--r-- | fluent-bit/lib/rbtree/README.md | 7 | ||||
| -rw-r--r-- | fluent-bit/lib/rbtree/rbtree.c | 811 | ||||
| -rw-r--r-- | fluent-bit/lib/rbtree/rbtree.h | 459 |
4 files changed, 1282 insertions, 0 deletions
diff --git a/fluent-bit/lib/rbtree/CMakeLists.txt b/fluent-bit/lib/rbtree/CMakeLists.txt new file mode 100644 index 000000000..739260e2c --- /dev/null +++ b/fluent-bit/lib/rbtree/CMakeLists.txt @@ -0,0 +1,5 @@ +set(src + rbtree.c + ) + +add_library(rbtree STATIC ${src}) diff --git a/fluent-bit/lib/rbtree/README.md b/fluent-bit/lib/rbtree/README.md new file mode 100644 index 000000000..00851601e --- /dev/null +++ b/fluent-bit/lib/rbtree/README.md @@ -0,0 +1,7 @@ +[Taken from: https://github.com/pvachon/rbtree] + +A simple, intrusive, zero-allocation Red-Black tree implementation. + +Designed exclusively for systems where determinism is needed. + +Licensed under a 2-clause BSD license for the sake of simplicity. 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 + */ + diff --git a/fluent-bit/lib/rbtree/rbtree.h b/fluent-bit/lib/rbtree/rbtree.h new file mode 100644 index 000000000..ef2f61e7d --- /dev/null +++ b/fluent-bit/lib/rbtree/rbtree.h @@ -0,0 +1,459 @@ +#ifndef __INCLUDED_RBTREE_H__ +#define __INCLUDED_RBTREE_H__ + +/** \file rbtree.h + * Declaration of associated structures and functions for a simple, intrusive + * red-black tree implementation. + */ + +#ifdef __cplusplus +extern "C" { +#endif /* __cplusplus */ + +#include <stdlib.h> +#include <assert.h> + +/** \defgroup rb_tree_compiler_prims Compiler Abstractions + * Primitives used to abstract compiler-specific syntax for common details used in + * providing hints to the compiler for optimization or linker details. + * @{ + */ + +/** + * Macro to check if a given assertion about an argument is true + */ +#define RB_ASSERT_ARG(x) \ + do { \ + if (RB_UNLIKELY(!(x))) { \ + assert(#x && 0); \ + return RB_BAD_ARG; \ + } \ + } while (0) + +/** + * The tagged branch is unlikely to be taken + */ +#ifdef _MSC_VER +#define RB_UNLIKELY(x) (!!(x)) +#else +#define RB_UNLIKELY(x) __builtin_expect(!!(x), 0) +#endif +/**@}*/ + +/** \defgroup rb_tree_state State Structures + * Structures that are used to represent state of a red-black tree, including the + * state of the tree itself, comparison functions used to determine how the tree + * is to be traversed, and representations of red-black tree nodes themselves. + * @{ + */ + +/** + * Structure that represents a node in a red-black tree. Embed this in your own + * structure in order to add your structure to the given red-black tree. + * Users of the rb_tree_node would embed it something like + * \code{.c} + struct my_sample_struct { + char *name; + int data; + struct rb_tree_node rnode; + }; + * \endcode + * + * \note No user of `struct rb_tree_node` should ever modify or inspect any + * members of the structure. + */ +struct rb_tree_node { + /** + * The left child (`NULL` if empty) + */ + struct rb_tree_node *left; + + /** + * The right child (`NULL` if empty) + */ + struct rb_tree_node *right; + + /** + * The parent of this node (`NULL` if at root) + */ + struct rb_tree_node *parent; + + /** + * The key for this node + */ + const void *key; + + /** + * The color of the node + */ + int color; +}; + +/** + * Pointer to a function to compare two keys, and returns as follows: + * - (0, +inf] if lhs > rhs + * - 0 if lhs == rhs + * - [-inf, 0) if lhs < rhs + */ +typedef int (*rb_cmp_func_t)(const void *lhs, const void *rhs); + +/** + * Pointer to a comparison function that allows passing along state. + * Return values are interpreted as follows: + * (0, +inf] if lhs > rhs + * 0 if lhs == rhs + * [-inf, 0) if lhs < rhs + */ +typedef int (*rb_cmp_func_ex_t)(void *state, const void *lhs, const void *rhs); + +/** + * Structure representing an RB tree's associated state. Contains all + * the information needed to manage the lifecycle of a RB tree. + * \note Typically users should not directly manipulate the structure, + * but rather use the provided accessor functions. + */ +struct rb_tree { + /** + * The root of the tree + */ + struct rb_tree_node *root; + + /** + * Predicate used for traversing the tree + */ + rb_cmp_func_ex_t compare; + + /** + * The right-most node of the rb-tree + */ + struct rb_tree_node *rightmost; + + /** + * Private state that can be used by the rb-tree owner + */ + void *state; +}; + +/**@} rb_tree_state */ + +/** \defgroup rb_result Function Results and Error Handling + * @{ + */ +/** \typedef rb_result_t + * Value of a returned result code from a red-black tree function. + */ +typedef int rb_result_t; + +/** \defgroup rb_result_code Result Codes + * Error codes that can be returned from any function that returns an rb_result_t. + * @{ + */ + +/** + * Function was successful + */ +#define RB_OK 0x0 +/** + * Element was not found + */ +#define RB_NOT_FOUND 0x1 +/** + * Bad argument provided to function (typically unexpected NULL) + */ +#define RB_BAD_ARG 0x2 +/** + * Node is a duplicate of an existing node + */ +#define RB_DUPLICATE 0x3 + +/**@} rb_result_code */ +/**@} rb_result */ + +/** \brief Helper to get a pointer to a containing structure. + * Given a pointer to an rb_tree_node, a target type and a member name, + * return a pointer to the structure containing the `struct rb_tree_node`. + * \code{.c} + struct sample { + const char *name; + struct rb_tree_node node; + }; + + void test(void) + { + struct sample samp = { .name = "Test 123" }; + struct rb_tree_node *samp_node = &(samp.node); + struct sample *samp2 = RB_CONTAINER_OF(samp_node, struct sample, node); + + assert(&samp == samp2); + } + * \endcode + * \param x The pointer to the node + * \param type The type of the containing structure + * \param memb The name of the `struct rb_tree_node` in the containing structure + * \return Pointer to the containing structure of the specified type + */ +#define RB_CONTAINER_OF(x, type, memb) \ + ({ \ + const __typeof__( ((type *)0)->memb ) *__member = (x); \ + (type *)( (char *)__member - __offsetof__(type, memb) ); \ + }) + + +/** \defgroup rb_functions Functions for Manipulating Red-Black Trees + * All functions associated with manipulating Red-Black trees using `struct rb_tree`, + * inluding lifecycle functions and member manipulation and state checking functions. + * @{ + */ + +/** + * \brief Construct a new, empty red-black tree, with extended state + * Given a region of memory at least the size of a struct rb_tree to + * store the red-black tree metadata, update it to contain an initialized, empty + * red-black tree, with given private state. + * \param tree Pointer to the new tree. + * \param compare Function used to traverse the tree. + * \param state The private state to be passed to the compare function + * \return RB_OK on success, an error code otherwise + */ +rb_result_t rb_tree_new_ex(struct rb_tree *tree, rb_cmp_func_ex_t compare, void *state); + +/** + * \brief Construct a new, empty red-black tree. + * Given a region of memory at least the size of a struct rb_tree to + * store the red-black tree metadata, update it to contain an initialized, empty + * red-black tree. + * \param tree Pointer to the new tree. + * \param compare Function used to traverse the tree. + * \return RB_OK on success, an error code otherwise + */ +rb_result_t rb_tree_new(struct rb_tree *tree, + rb_cmp_func_t compare); + +/** + * \brief Destroy a Red-Black tree. + * Clean up the state structure, clearing out the state of the tree + * so that it no longer can be used. + * \note Assumes that external callers will deallocate all nodes through + * some application-specific mechanism. + * \param tree The reference to the pointer to the tree itself. + * \return RB_OK on success, an error code otherwise + */ +rb_result_t rb_tree_destroy(struct rb_tree *tree); + +/** + * \brief Check if an red-black tree is empty (has no nodes). + * If no nodes are present, returns a non-zero value in `is_empty` -- returns + * 0 if there are nodes present. + * \param tree The tree to check + * \param is_empty nonzero on true, 0 otherwise + * \return RB_OK on success, an error code otherwise + */ +rb_result_t rb_tree_empty(struct rb_tree *tree, int *is_empty); + +/** + * \brief Find a node in the Red-Black tree given the specified key. + * Given a key, search the RB-tree iteratively until the specified key is found. + * This traversal is in O(log n) time, per the properties of a binary search tree. + * \param tree The RB-tree to search + * \param key The key to search for + * \param value a reference to a pointer to receive the pointer to the rb_tree_node if key is found + * \return RB_OK on success, an error code otherwise + */ +rb_result_t rb_tree_find(struct rb_tree *tree, + const void *key, + struct rb_tree_node **value); + +/** + * \brief Insert a node into the tree. + * Given a node and key, insert the node into the red-black tree and rebalance + * the tree if appropriate. Insertion is O(log n) time, with two tree traversals + * possible -- one for insertion (guaranteed) and one for rebalancing. + * \param tree the RB tree to insert the node into + * \param key The key for the node (must live as long as the node itself is in the tree) + * \param node the node to be inserted into the tree + * \return RB_OK on sucess, an error code otherwise + */ +rb_result_t rb_tree_insert(struct rb_tree *tree, + const void *key, + struct rb_tree_node *node); + +/** + * \brief Remove the specified node from the Red-Black tree. + * Given a pointer to the node, splice the node out of the tree, then, if applicable + * rebalance the tree so the Red-Black properties are maintained. + * \param tree The tree we want to remove the node from + * \param node The the node we want to remove + * \return RB_OK on success, an error code otherwise + */ +rb_result_t rb_tree_remove(struct rb_tree *tree, + struct rb_tree_node *node); + +/** + * \brief Find a node. If not found, insert the candidate. + * Find a node with the given key. If the node is found, return it by + * reference, without modifying the tree. If the node is not found, + * insert the provided candidate node. + * \note This function always will return in *value the node inserted + * or the existing node. If you want to check if the candidate + * node was inserted, check if `*value == new_candidate` + * + * \param tree The tree in question + * \param key The key to search for + * \param new_candidate The candidate node to insert + * \param value The value at the given location + * \return RB_OK on success, an error code otherwise + */ +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); + +/** + * \brief Find a node. If not found, insert the candidate. + * Find a node with the given key. If the node is found, return it by + * reference, without modifying the tree. If the node is not found, + * insert the provided candidate node. + * \note This function always will return in *value the node inserted + * or the existing node. If you want to check if the candidate + * node was inserted, check if `*value == new_candidate` + * + * \param tree The tree in question + * \param key The key to search for + * \param new_candidate The candidate node to insert + * \param value The value at the given location + * + * \return RB_OK on success, an error code otherwise + */ +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); +/** + * \brief Get the rightmost (greatest relative to predicate) node. + * Return the rightmost (i.e. greatest relative to predicate) node of the Red-Black tree. + */ +static inline +rb_result_t rb_tree_get_rightmost(struct rb_tree *tree, + struct rb_tree_node **rightmost) +{ + if ( (NULL == tree) || (NULL == rightmost) ) { + return RB_BAD_ARG; + } + + *rightmost = tree->rightmost; + + return RB_OK; +} + + +/** + * Find the minimum of the given tree/subtree rooted at the given node. + */ +static inline +rb_result_t __rb_tree_find_minimum(struct rb_tree_node *root, + struct rb_tree_node **min) +{ + struct rb_tree_node *x = root; + + while (x->left != NULL) { + x = x->left; + } + + *min = x; + + return RB_OK; +} + +/** + * Find the maximum of the given tree/subtree rooted at the given node. + */ +static inline +rb_result_t __rb_tree_find_maximum(struct rb_tree_node *root, + struct rb_tree_node **max) +{ + struct rb_tree_node *x = root; + + while (x->right != NULL) { + x = x->right; + } + + *max = x; + + return RB_OK; +} + +/** + * Find the successor (greater than, relative to predicate) node of the given node. + */ +static inline +rb_result_t rb_tree_find_successor(struct rb_tree *tree, + struct rb_tree_node *node, + struct rb_tree_node **successor) +{ + rb_result_t ret = RB_OK; + + RB_ASSERT_ARG(tree != NULL); + RB_ASSERT_ARG(node != NULL); + RB_ASSERT_ARG(successor != NULL); + + struct rb_tree_node *x = node; + + if (x->right != NULL) { + __rb_tree_find_minimum(x->right, successor); + goto done; + } + + struct rb_tree_node *y = x->parent; + + while (y != NULL && (x == y->right)) { + x = y; + y = y->parent; + } + + *successor = y; + +done: + return ret; +} + +/** + * Find the predecessor (less than, relative to predicate) node of the given node. + */ +static inline +rb_result_t rb_tree_find_predecessor(struct rb_tree *tree, + struct rb_tree_node *node, + struct rb_tree_node **pred) +{ + rb_result_t ret = RB_OK; + struct rb_tree_node *x = node; + + RB_ASSERT_ARG(tree != NULL); + RB_ASSERT_ARG(node != NULL); + RB_ASSERT_ARG(pred != NULL); + + if (x->left != NULL) { + __rb_tree_find_maximum(x->left, pred); + goto done; + } + + struct rb_tree_node *y = x->parent; + + while (y != NULL && (x == y->left)) { + x = y; + y = y->parent; + } + + *pred = y; + +done: + return ret; +} + +/**@} rb_functions */ + +#ifdef __cplusplus +} // extern "C" +#endif /* __cplusplus */ + +#endif /* __INCLUDED_RBTREE_H__ */ + |