rb.c

Go to the documentation of this file.

/*
 *   This program is free software; you can redistribute it and/or modify
 *   it under the terms of the GNU General Public License as published by
 *   the Free Software Foundation; either version 2 of the License, or
 *   (at your option) any later version.
 *
 *   This program is distributed in the hope that it will be useful,
 *   but WITHOUT ANY WARRANTY; without even the implied warranty of
 *   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *   GNU General Public License for more details.
 *
 *   You should have received a copy of the GNU General Public License
 *   along with this program; if not, write to the Free Software
 *   Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301, USA
 */
 
/** Red/black tree implementation
 *
 * @file src/lib/util/rb.c
 *
 * @copyright 2021 Arran Cudbard-Bell (a.cudbardb@freeradius.org)
 * @copyright 2004,2006 The FreeRADIUS server project
 */
RCSID("$Id: 770134614aa8d35bfd952bd8108cef0fd438a3c4 $")
 
#include <freeradius-devel/util/rb.h>
#include <freeradius-devel/util/strerror.h>
 
#define NIL &sentinel      /* all leafs are sentinels */
static fr_rb_node_t sentinel = { NIL, NIL, NULL, NULL, BLACK, false };
 
#ifndef NDEBUG
#  define RB_MAGIC (0x5ad09c42)
#endif
 
static int insert_node(fr_rb_node_t **existing, fr_rb_tree_t *tree, void *data) CC_HINT(nonnull(2,3));
 
static inline CC_HINT(always_inline) void node_data_free(fr_rb_tree_t const *tree, fr_rb_node_t *node)
{
        if (!tree->data_free || unlikely(node->being_freed)) return;
 
        node->being_freed = true;
        tree->data_free(node->data);
}
 
/** Return the fr_rb_node_t that was allocated as part of the data structure
 */
static fr_rb_node_t *_node_inline_alloc(fr_rb_tree_t const *tree, void *data)
{
        return (fr_rb_node_t *)((uintptr_t)data + tree->offset);
}
 
/** Clear the fr_rb_node_t that was allocated as part of the data structure
 */
static void _node_inline_free(fr_rb_tree_t const *tree, fr_rb_node_t *node, bool free_data)
{
        if (free_data && tree->data_free) {
                node_data_free(tree, node);
        } else {
                memset(node, 0, sizeof(fr_rb_node_t));  /* makes "still in tree?" checks easier */
        }
}
 
/** Allocate a new fr_rb_node_t on the heap
 */
static fr_rb_node_t *_node_heap_alloc(fr_rb_tree_t const *tree, UNUSED void *data)
{
        return talloc_zero(tree->node_ctx, fr_rb_node_t);
}
 
/** Clear the fr_rb_node_t that was allocated as part of the data structure
 */
static void _node_heap_free(fr_rb_tree_t const *tree, fr_rb_node_t *node, bool free_data)
{
        if (free_data) node_data_free(tree, node);
        talloc_free(node);
}
 
/** Walks the tree to delete all nodes Does NOT re-balance it!
 *
 */
static void free_walker(fr_rb_tree_t *tree, fr_rb_node_t *x)
{
        if (x->left != NIL) free_walker(tree, x->left);
        if (x->right != NIL) free_walker(tree, x->right);
 
        tree->node_free(tree, x, true);
}
 
/** Free the rbtree cleaning up any nodes
 *
 * Walk the tree deleting nodes, then free any children of the tree.
 *
 * @note If the destructor of a talloc descendent needs to lookup any
 *      information in the tree, it will be unavailable at the point
 *      of freeing.  We could fix this by introducing a pre-free callback
 *      which gets called before any of the nodes are deleted.
 *
 * @param[in] tree to tree.
 * @return
 *      - 0 if tree was freed.
 *      - -1 if tree is already being freed.
 */
static int _tree_free(fr_rb_tree_t *tree)
{
        /*
         *      Prevent duplicate frees
         */
        if (unlikely(tree->being_freed)) return -1;
        tree->being_freed = true;
 
        /*
         *      walk the tree, deleting the nodes...
         */
        if ((tree->root != NIL) && tree->data_free) free_walker(tree, tree->root);
 
        /*
         *      Ensure all dependents on the tree run their
         *      destructors.  The tree at this point should
         *      and any tree operations should be empty.
         */
        talloc_free_children(tree);
 
#ifndef NDEBUG
        tree->magic = 0;
#endif
        tree->root = NIL;
        tree->num_elements = 0;
 
        return 0;
}
 
/** Initialise a new RED-BLACK tree
 *
 * @param[out] tree             to initialise.
 * @param[in] node_ctx          the ctx used to allocate #fr_rb_node_t if the
 *                              tree isn't using inline #fr_rb_node_t.
 * @param[in] offset            offsetof the #fr_rb_node_t field in the data being inserted.
 *                              If < 0, nodes will be allocated on the heap.
 * @param[in] type              Talloc type of structures being inserted, may be NULL.
 * @param[in] data_cmp          Comparator function for ordering data in the tree.
 * @param[in] data_free         Free function to call whenever data is deleted or replaced.
 * @return
 *      - -1 on error.
 *      - 0 on success.
 */
int _fr_rb_init(fr_rb_tree_t *tree, TALLOC_CTX *node_ctx,
                ssize_t offset, char const *type,
                fr_cmp_t data_cmp, fr_free_t data_free)
{
 
        if (unlikely(offset >= UINT16_MAX)) {
                fr_strerror_printf("Inline fr_rb_node_t offset too large.  "
                                   "Expected <= %zu, got %zd", (size_t) UINT16_MAX, offset);
                return -1;
        }
 
        *tree = (fr_rb_tree_t) {
#ifndef NDEBUG
                .magic = RB_MAGIC,
#endif
                .root = NIL,
                .node_ctx = node_ctx,
                .offset = offset < 0 ? 0 : (uint16_t)offset,
                .type = type,
                .data_cmp = data_cmp,
                .data_free = data_free,
        };
 
        /*
         *      Use inline nodes
         */
        if (offset >= 0) {
                tree->node_alloc = _node_inline_alloc;
                tree->node_free = _node_inline_free;
        /*
         *      Allocate node data on the heap
         */
        } else {
                tree->node_alloc = _node_heap_alloc;
                tree->node_free = _node_heap_free;
        }
 
        return 0;
}
 
/** Alloc a new RED-BLACK tree
 *
 * @param[in] ctx               to allocate the tree in.
 *                              Only the tree is allocated in this context, the memory
 *                              for the #fr_rb_node_t is allocated as part of the data
 *                              being inserted into the tree.
 * @param[in] offset            offsetof the #fr_rb_node_t field in the data being inserted.
 *                              If < 0, nodes will be allocated on the heap.
 * @param[in] type              Talloc type of structures being inserted, may be NULL.
 * @param[in] data_cmp          Comparator function for ordering data in the tree.
 * @param[in] data_free         Free function to call whenever data is deleted or replaced.
 * @return
 *      - A new tree on success.
 *      - NULL on failure.
 */
fr_rb_tree_t *_fr_rb_alloc(TALLOC_CTX *ctx,
                           ssize_t offset, char const *type,
                           fr_cmp_t data_cmp, fr_free_t data_free)
{
        fr_rb_tree_t *tree;
 
        tree = talloc(ctx, fr_rb_tree_t);
        if (unlikely(!tree)) return NULL;
 
        if (unlikely(_fr_rb_init(tree, tree, offset, type, data_cmp, data_free) < 0)) {
                talloc_free(tree);
                return NULL;
        }
 
        talloc_set_destructor(tree, _tree_free);
 
        return tree;
}
 
/** Rotate Node x to left
 *
 */
static inline CC_HINT(always_inline) void rotate_left(fr_rb_tree_t *tree, fr_rb_node_t *x)
{
 
        fr_rb_node_t *y = x->right;
 
        /* establish x->right link */
        x->right = y->left;
        if (y->left != NIL) y->left->parent = x;
 
        /* establish y->parent link */
        if (y != NIL) y->parent = x->parent;
        if (x->parent != NIL) {
                if (x == x->parent->left) {
                        x->parent->left = y;
                } else {
                        x->parent->right = y;
                }
        } else {
                tree->root = y;
        }
 
        /* link x and y */
        y->left = x;
        if (x != NIL) x->parent = y;
}
 
/** Rotate Node x to right
 *
 */
static inline CC_HINT(always_inline) void rotate_right(fr_rb_tree_t *tree, fr_rb_node_t *x)
{
        fr_rb_node_t *y = x->left;
 
        /* establish x->left link */
        x->left = y->right;
        if (y->right != NIL) y->right->parent = x;
 
        /* establish y->parent link */
        if (y != NIL) y->parent = x->parent;
        if (x->parent != NIL) {
                if (x == x->parent->right) {
                        x->parent->right = y;
                } else {
                        x->parent->left = y;
                }
        } else {
                tree->root = y;
        }
 
        /* link x and y */
        y->right = x;
        if (x != NIL) x->parent = y;
}
 
/** Maintain red-black tree balance after inserting node x
 *
 */
static inline CC_HINT(always_inline) void insert_fixup(fr_rb_tree_t *tree, fr_rb_node_t *x)
{
        /* check RED-BLACK properties */
        while ((x != tree->root) && (x->parent->colour == RED)) {
                /* we have a violation */
                if (x->parent == x->parent->parent->left) {
                        fr_rb_node_t *y = x->parent->parent->right;
                        if (y->colour == RED) {
                                /* uncle is RED */
                                x->parent->colour = BLACK;
                                y->colour = BLACK;
                                x->parent->parent->colour = RED;
                                x = x->parent->parent;
                        } else {
                                /* uncle is BLACK */
                                if (x == x->parent->right) {
                                        /* make x a left child */
                                        x = x->parent;
                                        rotate_left(tree, x);
                                }
 
                                /* recolour and rotate */
                                x->parent->colour = BLACK;
                                x->parent->parent->colour = RED;
                                rotate_right(tree, x->parent->parent);
                        }
                } else {
                        /* mirror image of above code */
                        fr_rb_node_t *y = x->parent->parent->left;
                        if (y->colour == RED) {
                                /* uncle is RED */
                                x->parent->colour = BLACK;
                                y->colour = BLACK;
                                x->parent->parent->colour = RED;
                                x = x->parent->parent;
                        } else {
                                /* uncle is BLACK */
                                if (x == x->parent->left) {
                                        x = x->parent;
                                        rotate_right(tree, x);
                                }
 
                                x->parent->colour = BLACK;
                                x->parent->parent->colour = RED;
                                rotate_left(tree, x->parent->parent);
                        }
                }
        }
 
        tree->root->colour = BLACK;
}
 
 
/** Insert an element into the tree
 *
 * @param[out] existing         if a node exists, and existing is not NULL
 *                              this will be populated with the node.
 * @param[in] tree              to search in.
 * @param[in] data              to search for.
 * @return
 *      - 1 on existing (with existing populated).
 *      - 0 on success.
 *      - -1 on failure.
 */
static int insert_node(fr_rb_node_t **existing, fr_rb_tree_t *tree, void *data)
{
        fr_rb_node_t *current, *parent, *x;
        fr_cmp_ret_t last_result = CMP_EQ;
 
        if (unlikely(tree->being_freed)) return -1;
 
#ifndef TALLOC_GET_TYPE_ABORT_NOOP
        if (tree->type) (void)_talloc_get_type_abort(data, tree->type, __location__);
#endif
 
        /* find where node belongs */
        current = tree->root;
        parent = NIL;
        while (current != NIL) {
                fr_cmp_ret_t result;
 
                /*
                 *      See if two entries are identical.
                 */
                result = tree->data_cmp(data, current->data);
                if (unlikely(result == CMP_ERR)) return -1;
                if (result == CMP_EQ) {
                        if (existing) *existing = current;
                        return 1;
                }
 
                parent = current;
                last_result = result;
                current = (result == CMP_LT) ? current->left : current->right;
        }
 
        /* setup new node */
        x = tree->node_alloc(tree, data);
        if (unlikely(!x)) return -1;
 
        *x = (fr_rb_node_t){
                .data = data,
                .parent = parent,
                .left = NIL,
                .right = NIL,
                .colour = RED
        };
 
        /* insert node in tree, on the side the final descent comparison chose */
        if (parent != NIL) {
                if (last_result == CMP_LT) {
                        parent->left = x;
                } else {
                        parent->right = x;
                }
        } else {
                tree->root = x;
        }
 
        insert_fixup(tree, x);
 
        tree->num_elements++;
 
        return 0;
}
 
/** Maintain RED-BLACK tree balance after deleting node x
 *
 */
static void delete_fixup(fr_rb_tree_t *tree, fr_rb_node_t *x, fr_rb_node_t *parent)
{
        while (x != tree->root && x->colour == BLACK) {
                if (x == parent->left) {
                        fr_rb_node_t *w = parent->right;
                        if (w->colour == RED) {
                                w->colour = BLACK;
                                parent->colour = RED; /* parent != NIL? */
                                rotate_left(tree, parent);
                                w = parent->right;
                        }
                        if ((w->left->colour == BLACK) && (w->right->colour == BLACK)) {
                                if (w != NIL) w->colour = RED;
                                x = parent;
                                parent = x->parent;
                        } else {
                                if (w->right->colour == BLACK) {
                                        if (w->left != NIL) w->left->colour = BLACK;
                                        w->colour = RED;
                                        rotate_right(tree, w);
                                        w = parent->right;
                                }
                                w->colour = parent->colour;
                                if (parent != NIL) parent->colour = BLACK;
                                if (w->right->colour != BLACK) {
                                        w->right->colour = BLACK;
                                }
                                rotate_left(tree, parent);
                                x = tree->root;
                        }
                } else {
                        fr_rb_node_t *w = parent->left;
                        if (w->colour == RED) {
                                w->colour = BLACK;
                                parent->colour = RED; /* parent != NIL? */
                                rotate_right(tree, parent);
                                w = parent->left;
                        }
                        if ((w->right->colour == BLACK) && (w->left->colour == BLACK)) {
                                if (w != NIL) w->colour = RED;
                                x = parent;
                                parent = x->parent;
                        } else {
                                if (w->left->colour == BLACK) {
                                        if (w->right != NIL) w->right->colour = BLACK;
                                        w->colour = RED;
                                        rotate_left(tree, w);
                                        w = parent->left;
                                }
                                w->colour = parent->colour;
                                if (parent != NIL) parent->colour = BLACK;
                                if (w->left->colour != BLACK) {
                                        w->left->colour = BLACK;
                                }
                                rotate_right(tree, parent);
                                x = tree->root;
                        }
                }
        }
        if (x != NIL) x->colour = BLACK; /* Avoid cache-dirty on NIL */
}
 
/** Delete an element (z) from the tree
 *
 */
static void delete_internal(fr_rb_tree_t *tree, fr_rb_node_t *z, bool free_data)
{
        fr_rb_node_t *x, *y;
        fr_rb_node_t *parent;
 
        if (!z || z == NIL) return;
 
        if (z->left == NIL || z->right == NIL) {
                /* y has a NIL node as a child */
                y = z;
        } else {
                /* find tree successor with a NIL node as a child */
                y = z->right;
                while (y->left != NIL) y = y->left;
        }
 
        /* x is y's only child */
        if (y->left != NIL) {
                x = y->left;
        } else {
                x = y->right;   /* may be NIL! */
        }
 
        /* remove y from the parent chain */
        parent = y->parent;
        if (x != NIL) x->parent = parent;
 
        if (parent != NIL) {
                if (y == parent->left) {
                        parent->left = x;
                } else {
                        parent->right = x;
                }
        } else {
                tree->root = x;
        }
 
        if (y != z) {
                void *y_data = y->data;
 
                if ((y->colour == BLACK) && parent) delete_fixup(tree, x, parent);
 
                /*
                 *      The user structure in y->data May include a
                 *      pointer to y.  In that case, we CANNOT delete
                 *      y.  Instead, we copy z (which is now in the
                 *      tree) to y, and fix up the parent/child
                 *      pointers.
                 */
                memcpy(y, z, sizeof(*y));
                y->data = y_data;
 
                if (y->parent == NIL) {
                        tree->root = y;
                } else {
                        if (y->parent->left == z) y->parent->left = y;
                        if (y->parent->right == z) y->parent->right = y;
                }
                if (y->left->parent == z) y->left->parent = y;
                if (y->right->parent == z) y->right->parent = y;
 
                tree->node_free(tree, z, free_data);
        } else {
                if (y->colour == BLACK) delete_fixup(tree, x, parent);
 
                tree->node_free(tree, y, free_data);
        }
 
        tree->num_elements--;
}
 
 
/* Find user data, returning the node
 *
 */
static inline CC_HINT(always_inline) int find_node(fr_rb_node_t **found, fr_rb_tree_t const *tree, void const *data)
{
        fr_rb_node_t *current;
 
        *found = NULL;
        if (unlikely(tree->being_freed)) return 0;
 
        current = tree->root;
 
        while (current != NIL) {
                fr_cmp_ret_t result = tree->data_cmp(data, current->data);
 
                if (unlikely(result == CMP_ERR)) return -1;
                if (result == CMP_EQ) {
                        *found = current;
                        return 0;
                }
 
                current = (result == CMP_LT) ? current->left : current->right;
        }
 
        return 0;
}
 
/** Find an element in the tree, returning the data, not the node
 *
 * @param[out] found    the matching element, or NULL if no element matched.
 * @param[in] tree to search in.
 * @param[in] data to find.
 * @return
 *      - 0 the comparison sequence succeeded, check found for the result.
 *      - -1 the comparator errored, retrieve the error with fr_strerror.
 *
 * @hidecallergraph
 */
CC_NO_UBSAN(function) /* UBSAN: false positive - htrie call with first argument of void * trips --fsanitize=function */
int fr_rb_find(void **found, fr_rb_tree_t const *tree, void const *data)
{
        fr_rb_node_t    *x;
 
        *found = NULL;
        if (unlikely(tree->being_freed)) return 0;
        if (unlikely(find_node(&x, tree, data) < 0)) return -1;
        if (x) *found = x->data;
 
        return 0;
}
 
/** Attempt to find current data in the tree, if it does not exist insert it
 *
 * @param[out] found    Pre-existing data we found.
 * @param[in] tree      to search/insert into.
 * @param[in] data      to find.
 * @return
 *      - 1 if existing data was found, found will be populated.
 *      - 0 if no existing data was found.
 *      - -1 on insert or comparator error, retrieve the error with fr_strerror.
 */
int fr_rb_find_or_insert(void **found, fr_rb_tree_t *tree, void const *data)
{
        fr_rb_node_t    *existing;
 
        switch (insert_node(&existing, tree, UNCONST(void *, data))) {
        case 1:
                if (found) *found = existing->data;
                return 1;
 
        case 0:
                if (found) *found = NULL;
                return 0;
 
        default:
                if (found) *found = NULL;
                return -1;
        }
}
 
/** Insert data into a tree
 *
 * @param[in] tree      to insert data into.
 * @param[in] data      to insert.
 * @return
 *      - 0 if data was inserted.
 *      - 1 if data already existed and was not inserted.
 *      - -1 on comparator or allocation error, retrieve the error with fr_strerror.
 */
CC_NO_UBSAN(function) /* UBSAN: false positive - htrie call with first argument of void * trips --fsanitize=function */
int fr_rb_insert(fr_rb_tree_t *tree, void const *data)
{
        return insert_node(NULL, tree, UNCONST(void *, data));
}
 
/** Replace old data with new data, OR insert if there is no old
 *
 * @param[out] old      data that was replaced.  If this argument
 *                      is not NULL, then the old data will not
 *                      be freed, even if a free function is
 *                      configured.
 * @param[in] tree      to insert data into.
 * @param[in] data      to replace.
 * @return
 *      - 1 if data was replaced.
 *      - 0 if data was inserted.
 *      - -1 if we failed to replace data, retrieve the error with fr_strerror.
 */
CC_NO_UBSAN(function) /* UBSAN: false positive - htrie call with first argument of void * trips --fsanitize=function */
int fr_rb_replace(void **old, fr_rb_tree_t *tree, void const *data)
{
        fr_rb_node_t    *node;
 
        switch (insert_node(&node, tree, UNCONST(void *, data))) {
        case 1: /* Something exists */
        {
                void    *old_data = node->data;
                int     ret = 1;
 
                /*
                 *      If the fr_node_t is inline with the
                 *      data structure, we need to delete
                 *      the old node out of the tree, and
                 *      perform a normal insert operation.
                 */
                if (tree->node_alloc == _node_inline_alloc) {
                        delete_internal(tree, node, false);
 
                        /*
                         *      The re-insert repeats comparisons which just succeeded,
                         *      so a failure means the comparator is non-deterministic
                         *      or allocation failed.  The old data has already been
                         *      unlinked; it is still handed to the caller (or freed)
                         *      below so it isn't leaked.
                         */
                        if (!fr_cond_assert_msg(insert_node(NULL, tree, UNCONST(void *, data)) == 0,
                                                "re-insert failed after delete")) {
                                ret = -1;
                        }
                } else {
                        node->data = UNCONST(void *, data);
                }
 
                if (old) {
                        *old = old_data;
                } else if (tree->data_free) {
                        tree->data_free(old_data);
                }
                return ret;
        }
        case 0: /* New node was inserted - There was no pre-existing node */
                if (old) *old = NULL;
                return 0;
 
        default:
                if (old) *old = NULL;
                return -1;
        }
}
 
/** Remove an entry from the tree, without freeing the data
 *
 * @param[out] removed  the data we removed, if any.  May be NULL.
 * @param[in] tree      to remove data from.
 * @param[in] data      to remove.
 * @return
 *      - 0 if we removed data, removed is populated.
 *      - 1 if we couldn't find any matching data.
 *      - -1 if the comparator errored, retrieve the error with fr_strerror.
 */
CC_NO_UBSAN(function) /* UBSAN: false positive - htrie call with first argument of void * trips --fsanitize=function */
int fr_rb_remove(void **removed, fr_rb_tree_t *tree, void const *data)
{
        fr_rb_node_t    *node;
 
        if (removed) *removed = NULL;
        if (unlikely(tree->being_freed)) return 1;
        if (unlikely(find_node(&node, tree, data) < 0)) return -1;
        if (!node) return 1;
 
        if (unlikely(node->being_freed)) {
                if (removed) *removed = node->data;
                return 0;
        }
 
        if (removed) *removed = node->data;
        delete_internal(tree, node, false);     /* nullified node->data */
        return 0;
}
 
/** Remove an entry from the tree, using the node structure, without freeing the data
 *
 * This function can help where multiple items may be in the
 * tree with the same comparator value.
 *
 * @param[in] tree      to remove data from.
 * @param[in] node      to remove.
 * @return
 *      - The user data we removed.
 *      - NULL if the user data wasn't in the tree.
 */
void *fr_rb_remove_by_inline_node(fr_rb_tree_t *tree, fr_rb_node_t *node)
{
        void            *node_data;
 
        if (!fr_rb_node_inline_in_tree(node)) return NULL;
        node_data = node->data;
        delete_internal(tree, node, false);     /* nullified node->data */
        return node_data;
}
 
/** Remove node and free data (if a free function was specified)
 *
 * @param[in] tree      to remove data from.
 * @param[in] data      to remove/free.
 * @return
 *      - true if we removed data.
 *      - false if we couldn't find any matching data.
 */
CC_NO_UBSAN(function) /* UBSAN: false positive - htrie call with first argument of void * trips --fsanitize=function */
int fr_rb_delete(fr_rb_tree_t *tree, void const *data)
{
        fr_rb_node_t    *node;
 
        if (unlikely(tree->being_freed)) return 1;
        if (unlikely(find_node(&node, tree, data) < 0)) return -1;
        if (!node) return 1;
 
        if (unlikely(node->being_freed)) return 0;
 
        delete_internal(tree, node, tree->data_free);
 
        return 0;
}
 
/** Remove node and free data (if a free function was specified)
 *
 * This function can help where multiple items may be in the
 * tree with the same comparator value.
 *
 * @param[in] tree      to remove data from.
 * @param[in] node      to remove/free.
 * @return
 *      - true if we removed data.
 *      - false if we couldn't find any matching data.
 */
bool fr_rb_delete_by_inline_node(fr_rb_tree_t *tree, fr_rb_node_t *node)
{
        if (!fr_rb_node_inline_in_tree(node)) return false;
 
        delete_internal(tree, node, true);
 
        return true;
}
 
/** Return how many nodes there are in a tree
 *
 * @param[in] tree      to return node count for.
 */
CC_NO_UBSAN(function) /* UBSAN: false positive - htrie call with first argument of void * trips --fsanitize=function */
uint32_t fr_rb_num_elements(fr_rb_tree_t *tree)
{
        return tree->num_elements;
}
 
void *fr_rb_first(fr_rb_tree_t *tree)
{
        fr_rb_node_t *x = tree->root;
 
        if (x == NIL) return NULL;
 
        /*
         *      First node is the leftmost
         */
        while (x->left != NIL) x = x->left;
 
        return x->data;
}
 
 
void *fr_rb_last(fr_rb_tree_t *tree)
{
        fr_rb_node_t *x = tree->root;
 
        if (x == NIL) return NULL;
 
        /*
         *      Last node is the rightmost
         */
        while (x->right != NIL) x = x->right;
 
        return x->data;
}
 
 
/** Initialise an in-order iterator
 *
 * @param[in] tree      to iterate over.
 * @param[out] iter     to initialise.
 * @return
 *      - The first node.  Mutex will be held.
 *      - NULL if the tree is empty.
 */
void *fr_rb_iter_init_inorder(fr_rb_tree_t *tree, fr_rb_iter_inorder_t *iter)
{
        fr_rb_node_t *x = tree->root;
 
        if (x == NIL) return NULL;
 
        /*
         *      First node is the leftmost
         */
        while (x->left != NIL) x = x->left;
 
        *iter = (fr_rb_iter_inorder_t){
                .node = x
        };
 
        return x->data;
}
 
/** Return the next node
 *
 * @param[in] tree      to iterate over.
 * @param[in] iter      previously initialised with #fr_rb_iter_init_inorder
 * @return
 *      - The next node.
 *      - NULL if no more nodes remain.
 */
void *fr_rb_iter_next_inorder(UNUSED fr_rb_tree_t *tree, fr_rb_iter_inorder_t *iter)
{
        fr_rb_node_t *x = iter->node, *y;
 
        /*
         *      Catch callers repeatedly calling iterator
         *      at the end.
         */
        if (unlikely(iter->node == NIL)) return NULL;
 
        /*
         *      fr_rb_iter_delete() has already deleted this node,
         *      and saved the next one for us. (We check for NULL;
         *      NIL just means we're at the end.)
         */
        if (!iter->node) {
                iter->node = iter->next;
                iter->next = NULL;
                return iter->node->data;
        }
 
        if (x->right != NIL) {
                x = x->right;
 
                while (x->left != NIL) x = x->left;
                iter->node = x;
 
                return x->data;
        }
 
        y = x;
        x = x->parent;
        while ((x != NIL) && (y == x->right)) {
                y = x;
                x = x->parent;
        }
 
        iter->node = x;
 
        return x->data;
}
 
/** Remove the current node from the tree
 *
 * @note Only makes sense for in-order traversals.
 *
 * @param[in] tree      to iterate over.
 * @param[in] iter      previously initialised with #fr_rb_iter_init_inorder
 */
void fr_rb_iter_delete_inorder(fr_rb_tree_t *tree, fr_rb_iter_inorder_t *iter)
{
        fr_rb_node_t *x = iter->node;
 
        if (unlikely(x == NIL)) return;
        (void) fr_rb_iter_next_inorder(tree, iter);
        iter->next = iter->node;
        iter->node = NULL;
        delete_internal(tree, x, true);
}
 
/** Initialise a pre-order iterator
 *
 * @param[in] tree      to iterate over.
 * @param[out] iter     to initialise.
 * @return
 *      - The first node.  Mutex will be held.
 *      - NULL if the tree is empty.
 */
void *fr_rb_iter_init_preorder(fr_rb_tree_t *tree, fr_rb_iter_preorder_t *iter)
{
        fr_rb_node_t *x = tree->root;
 
        if (x == NIL) return NULL;
 
        /*
         *      First, the root.
         */
        *iter = (fr_rb_iter_preorder_t){
                .node = x
        };
 
        return x->data;
}
 
/** Return the next node
 *
 * @param[in] tree      to iterate over.
 * @param[in] iter      previously initialised with #fr_rb_iter_init_preorder
 * @return
 *      - The next node.
 *      - NULL if no more nodes remain.
 */
void *fr_rb_iter_next_preorder(UNUSED fr_rb_tree_t *tree, fr_rb_iter_preorder_t *iter)
{
        fr_rb_node_t *x = iter->node, *y;
 
        /*
         *      Catch callers repeatedly calling iterator
         *      at the end.
         */
        if (unlikely(iter->node == NIL)) return NULL;
 
        /*
         * Next is a child of the just-returned node, if it has one.
         * (Left child first.)
         */
        if (x->left != NIL) {
                x = x->left;
                iter->node = x;
                return x->data;
        }
        if (x->right != NIL) {
                x = x->right;
                iter->node = x;
                return x->data;
        }
 
        /*
         * Otherwise, the nearest ancestor's unreturned right
         * child, if one exists.
         */
        for (; (y = x->parent) != NIL; x = y) {
                if (y->right != NIL && y->right != x) {
                        x = y->right;
                        iter->node = x;
                        return x->data;
                }
        }
 
        /*
         * None of the above? We're done.
         */
        iter->node = NIL;
 
        return NULL;
}
 
/** Initialise a post-order iterator
 *
 * @param[in] tree      to iterate over.
 * @param[out] iter     to initialise.
 * @return
 *      - The first node.
 *      - NULL if the tree is empty.
 */
void *fr_rb_iter_init_postorder(fr_rb_tree_t *tree, fr_rb_iter_postorder_t *iter)
{
        fr_rb_node_t *x = tree->root;
 
        if (x == NIL) return NULL;
 
        /*
         *      First: the deepest leaf to the left (jogging to the
         *      right if there's a right child but no left).
         */
        for (;;) {
                for (; x->left != NIL; x = x->left) ;
                if (x->right == NIL) break;
                x = x->right;
        }
 
        *iter = (fr_rb_iter_postorder_t){
                .node = x
        };
 
        return x->data;
}
 
/** Return the next node
 *
 * @param[in] tree      to iterate over.
 * @param[in] iter      previously initialised with #fr_rb_iter_init_postorder
 * @return
 *      - The next node.
 *      - NULL if no more nodes remain.
 */
void *fr_rb_iter_next_postorder(UNUSED fr_rb_tree_t *tree, fr_rb_iter_postorder_t *iter)
{
        fr_rb_node_t *x = iter->node, *y;
 
        /*
         *      Catch callers repeatedly calling iterator
         *      at the end.
         */
        if (unlikely(iter->node == NIL)) return NULL;
 
        /*
         *      This is postorder, so a just-returned node's
         *      descendants have all been returned. If there
         *      is another node, it's an ancestor or one of
         *      its not-yet-returned descendants...but if
         *      we're at the root, we're done.
         */
        y = x->parent;
        if (y == NIL) {
                iter->node = NIL;
                return NULL;
        }
 
        /*
         * Return the parent if it has no right child, or it has one but
         * it's been returned.
         */
        if (y->right == NIL || y->right == x) {
                iter->node = y;
                return y->data;
        }
 
        /*
         * Otherwise, it's as if we're starting over with the right child.
         */
        x = y->right;
        for (;;) {
                for (; x->left != NIL; x = x->left) ;
                if (x->right == NIL) break;
                x = x->right;
        }
 
        iter->node = x;
        return x->data;
}
 
#define DEF_RB_FLATTEN_FUNC(_order) \
int fr_rb_flatten_##_order(TALLOC_CTX *ctx, void **out[], fr_rb_tree_t *tree) \
{ \
        uint32_t num = fr_rb_num_elements(tree), i; \
        fr_rb_iter_##_order##_t iter; \
        void *item, **list; \
        if (unlikely(!(list = talloc_array(ctx, void *, num)))) return -1; \
        for (item = fr_rb_iter_init_##_order(tree, &iter), i = 0; \
             item; \
             item = fr_rb_iter_next_##_order(tree, &iter), i++) list[i] = item; \
        *out = list; \
        return 0; \
}
DEF_RB_FLATTEN_FUNC(preorder)
DEF_RB_FLATTEN_FUNC(postorder)
DEF_RB_FLATTEN_FUNC(inorder)