Merging upstream version 1.46.3.

Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>

4 files changed, 0 insertions, 1282 deletions

diff --git a/fluent-bit/lib/rbtree/CMakeLists.txt b/fluent-bit/lib/rbtree/CMakeLists.txt
deleted file mode 100644
index 739260e2c..000000000
--- a/fluent-bit/lib/rbtree/CMakeLists.txt
+++ /dev/null
@@ -1,5 +0,0 @@
-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
deleted file mode 100644
index 00851601e..000000000
--- a/fluent-bit/lib/rbtree/README.md
+++ /dev/null
@@ -1,7 +0,0 @@
-[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
deleted file mode 100644
index 99e56e0c8..000000000
--- a/fluent-bit/lib/rbtree/rbtree.c
+++ /dev/null
@@ -1,811 +0,0 @@
-/*
-  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
deleted file mode 100644
index ef2f61e7d..000000000
--- a/fluent-bit/lib/rbtree/rbtree.h
+++ /dev/null
@@ -1,459 +0,0 @@
-#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__ */
-