/src/freeradius-server/src/freeradius-devel/util/rb.h

Source
#pragma once
/*
 *   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.h
 *
 * @copyright 2016 The FreeRADIUS server project
 */
RCSIDH(fr_rb_h, "$Id: 2f5ea0ab87e701d079421a487b9a647b7d375205 $")

#ifdef __cplusplus
extern "C" {
#endif

#include <freeradius-devel/util/misc.h>


/* Red-Black tree description */
typedef enum {
  BLACK,
  RED
} fr_rb_colour_t;

typedef struct fr_rb_node_s fr_rb_node_t;
struct fr_rb_node_s {
  fr_rb_node_t    *left;    //!< Left child
  fr_rb_node_t    *right;   //!< Right child
  fr_rb_node_t    *parent;  //!< Parent
  void      *data;    //!< data stored in node

  fr_rb_colour_t    colour;   //!< Node colour (BLACK, RED)
  bool      being_freed;  //!< Disable frees if we're currently calling
            ///< a free function.
};

typedef struct fr_rb_tree_s fr_rb_tree_t;

/** Callback used to alloc rbnodes
 *
 * @param[in] tree  to allocate the node for.
 * @param[in] data  associated with node.
 */
typedef fr_rb_node_t *(* rb_node_alloc_t)(fr_rb_tree_t const *tree, void *data);

/** Callback used to free rbnodes
 *
 * @param[in] tree  that owns the node.
 * @param[in] node  to free.
 * @param[in] free_data free user data.
 */
typedef void (* rb_node_free_t)(fr_rb_tree_t const *tree, fr_rb_node_t *node, bool free_data);

/** The main red black tree structure
 *
 */
struct fr_rb_tree_s {
#ifndef NDEBUG
  uint32_t    magic;
#endif

  fr_rb_node_t    *root;    //!< Root of the rbtree.

  TALLOC_CTX    *node_ctx;  //!< Talloc ctx to allocate nodes in.

  char const    *type;    //!< Talloc type to check elements against.

  fr_cmp_t    data_cmp; //!< Callback to compare node data.
  fr_free_t   data_free;  //!< Callback to free node data.

  rb_node_alloc_t   node_alloc; //!< Callback to allocate a new node.
  rb_node_free_t    node_free;  //!< Callback to free a node.

  /*
   *  Try and pack these more efficiently
   *  by grouping them together.
   */
  uint16_t    offset;   //!< Where's the fr_rb_node_t is located in
            ///< the structure being inserted.
  bool      being_freed;  //!< Prevent double frees in talloc_destructor.
  uint32_t    num_elements; //!< How many elements are inside the tree.
};

/** Initialises a red black that verifies elements are of a specific talloc type
 *
 * This variant allocates an #fr_rb_node_t on the heap.  This allows the data
 * structure to be inserted into multiple trees.
 *
 * @param[out] _tree    to initialise.
 * @param[in] _node_ctx   to tie tree lifetime to.
 *        If ctx is freed, tree will free any nodes, calling the
 *        free function if set.
 * @param[in] _type   of item being stored in the tree, e.g. fr_value_box_t.
 * @param[in] _data_cmp   Callback to compare node data.
 * @param[in] _data_free  Optional function used to free data if tree nodes are
 *        deleted or replaced.
 * @return
 *  - A new rbtree on success.
 *  - NULL on failure.
 */
#define   fr_rb_talloc_init(_tree, _node_ctx, _type, _data_cmp, _data_free) \
    _fr_rb_init(_tree, _node_ctx, -1, #_type, _data_cmp, _data_free)

/** Initialises a red black tree
 *
 * This variant initiates an #fr_rb_node_t on the heap.  This allows the data structure
 * to be inserted into multiple trees.
 *
 * @param[out] _tree    to initialise.
 * @param[in] _node_ctx   to tie tree lifetime to.
 *        If ctx is freed, tree will free any nodes, calling the
 *        free function if set.
 * @param[in] _data_cmp   Callback to compare node data.
 * @param[in] _data_free  Optional function used to free data if tree nodes are
 *        deleted or replaced.
 * @return
 *  - A new rbtree on success.
 *  - NULL on failure.
 */
#define   fr_rb_init(_tree, _node_ctx, _data_cmp, _data_free) \
    _fr_rb_init(_tree, _node_ctx, -1, NULL, _data_cmp, _data_free)

/** Initialises a red black that verifies elements are of a specific talloc type
 *
 * This variant stores #fr_rb_node_t data inline with the data structure to avoid
 * initiating #fr_rb_node_t on the heap.
 *
 * It is suitable for use where the data structure will only be inserted into a
 * fixed set of trees.
 *
 * @param[out] _tree    to initialise.
 * @param[in] _type   of item being stored in the tree, e.g. fr_value_box_t.
 * @param[in] _field    Containing the #fr_rb_node_t within item being stored.
 * @param[in] _data_cmp   Callback to compare node data.
 * @param[in] _data_free  Optional function used to free data if tree nodes are
 *        deleted or replaced.
 * @return
 *  - A new rbtree on success.
 *  - NULL on failure.
 */
#define   fr_rb_inline_talloc_init(_tree, _type, _field, _data_cmp, _data_free) \
    _Generic((((_type *)0)->_field), \
      fr_rb_node_t: _fr_rb_init(_tree, NULL, offsetof(_type, _field), #_type, _data_cmp, _data_free) \
    )

/** Initialises a red black tree
 *
 * This variant stores #fr_rb_node_t data inline with the data structure to avoid
 * initiating #fr_rb_node_t on the heap.
 *
 * It is suitable for use where the data structure will only be inserted into a
 * fixed set of trees.
 *
 * @param[out] _tree    to initialise.
 * @param[in] _type   of item being stored in the tree, e.g. fr_value_box_t.
 * @param[in] _field    Containing the #fr_rb_node_t within item being stored.
 * @param[in] _data_cmp   Callback to compare node data.
 * @param[in] _data_free  Optional function used to free data if tree nodes are
 *        deleted or replaced.
 * @return
 *  - 0 on success.
 *  - -1 on failure.
 */
#define   fr_rb_inline_init(_tree, _type, _field, _data_cmp, _data_free) \
    _Generic((((_type *)0)->_field), \
      fr_rb_node_t: _fr_rb_init(_tree, NULL, offsetof(_type, _field), NULL, _data_cmp, _data_free) \
    )

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);

/** Allocs a red black that verifies elements are of a specific talloc type
 *
 * This variant allocates an #fr_rb_node_t on the heap.  This allows the data structure
 * to be inserted into multiple trees.
 *
 * @param[in] _ctx    to tie tree lifetime to.
 *        If ctx is freed, tree will free any nodes, calling the
 *        free function if set.
 * @param[in] _type   of item being stored in the tree, e.g. fr_value_box_t.
 * @param[in] _data_cmp   Callback to compare node data.
 * @param[in] _data_free  Optional function used to free data if tree nodes are
 *        deleted or replaced.
 * @return
 *  - A new rbtree on success.
 *  - NULL on failure.
 */
#define   fr_rb_talloc_alloc(_ctx, _type, _data_cmp, _data_free) \
    _fr_rb_alloc(_ctx, -1, #_type, _data_cmp, _data_free)

/** Allocs a red black tree
 *
 * This variant allocates an #fr_rb_node_t on the heap.  This allows the data structure
 * to be inserted into multiple trees.
 *
 * @param[in] _ctx    to tie tree lifetime to.
 *        If ctx is freed, tree will free any nodes, calling the
 *        free function if set.
 * @param[in] _data_cmp   Callback to compare node data.
 * @param[in] _data_free  Optional function used to free data if tree nodes are
 *        deleted or replaced.
 * @return
 *  - A new rbtree on success.
 *  - NULL on failure.
 */
#define   fr_rb_alloc(_ctx, _data_cmp, _data_free) \
    _fr_rb_alloc(_ctx, -1, NULL, _data_cmp, _data_free)

/** Allocs a red black that verifies elements are of a specific talloc type
 *
 * This variant stores #fr_rb_node_t data inline with the data structure to avoid
 * allocating #fr_rb_node_t on the heap.
 *
 * It is suitable for use where the data structure will only be inserted into a fixed
 * set of trees.
 *
 * @param[in] _ctx    to tie tree lifetime to.
 *        If ctx is freed, tree will free any nodes, calling the
 *        free function if set.
 * @param[in] _type   of item being stored in the tree, e.g. fr_value_box_t.
 * @param[in] _field    Containing the #fr_rb_node_t within item being stored.
 * @param[in] _data_cmp   Callback to compare node data.
 * @param[in] _data_free  Optional function used to free data if tree nodes are
 *        deleted or replaced.
 * @return
 *  - A new rbtree on success.
 *  - NULL on failure.
 */
#define   fr_rb_inline_talloc_alloc(_ctx, _type, _field, _data_cmp, _data_free) \
    _Generic((((_type *)0)->_field), \
      fr_rb_node_t: _fr_rb_alloc(_ctx, offsetof(_type, _field), #_type, _data_cmp, _data_free) \
    )

/** Allocs a red black tree
 *
 * This variant stores #fr_rb_node_t data inline with the data structure to avoid
 * allocating #fr_rb_node_t on the heap.
 *
 * It is suitable for use where the data structure will only be inserted into a fixed
 * set of trees.
 *
 * @param[in] _ctx    to tie tree lifetime to.
 *        If ctx is freed, tree will free any nodes, calling the
 *        free function if set.
 * @param[in] _type   of item being stored in the tree, e.g. fr_value_box_t.
 * @param[in] _field    Containing the #fr_rb_node_t within item being stored.
 * @param[in] _data_cmp   Callback to compare node data.
 * @param[in] _data_free  Optional function used to free data if tree nodes are
 *        deleted or replaced.
 * @return
 *  - A new rbtree on success.
 *  - NULL on failure.
 */
#define   fr_rb_inline_alloc(_ctx, _type, _field, _data_cmp, _data_free) \
    _Generic((((_type *)0)->_field), \
      fr_rb_node_t: _fr_rb_alloc(_ctx, offsetof(_type, _field), NULL, _data_cmp, _data_free) \
    )

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) CC_HINT(warn_unused_result);

/** @hidecallergraph */
void    *fr_rb_find(fr_rb_tree_t const *tree, void const *data) CC_HINT(nonnull);

int   fr_rb_find_or_insert(void **found, fr_rb_tree_t *tree, void const *data) CC_HINT(nonnull(2,3));

bool    fr_rb_insert(fr_rb_tree_t *tree, void const *data) CC_HINT(nonnull);

int   fr_rb_replace(void **old, fr_rb_tree_t *tree, void const *data) CC_HINT(nonnull(2,3));

void    *fr_rb_remove(fr_rb_tree_t *tree, void const *data) CC_HINT(nonnull);

void    *fr_rb_remove_by_inline_node(fr_rb_tree_t *tree, fr_rb_node_t *node) CC_HINT(nonnull);

bool    fr_rb_delete(fr_rb_tree_t *tree, void const *data) CC_HINT(nonnull);

bool    fr_rb_delete_by_inline_node(fr_rb_tree_t *tree, fr_rb_node_t *node) CC_HINT(nonnull);

uint32_t  fr_rb_num_elements(fr_rb_tree_t *tree) CC_HINT(nonnull);

void    *fr_rb_first(fr_rb_tree_t *tree) CC_HINT(nonnull);

void    *fr_rb_last(fr_rb_tree_t *tree) CC_HINT(nonnull);

/** Check to see if an item is in a tree by examining its inline #fr_rb_node_t
 *
 * This works because we use NIL sentinels to represent the absence of a child
 * or parent.  When the node is initialised all these fields should be NULL
 * and when it's removed from the tree, the "free" function for inline nodes
 * also sets all of these back to NULL.
 *
 * @param[in] node  to check.
 * @return
 *  - true if node is in the tree.
 *  - talse if node is not in the tree.
 */
static inline bool fr_rb_node_inline_in_tree(fr_rb_node_t const *node)
{
  return (node->left && node->right && node->parent && !node->being_freed);
}

/** Iterator structure for in-order traversal of an rbtree
 */
typedef struct {
  fr_rb_node_t  *node;      ///< current node--set to NULL (not NIL) by fr_rb_iter_delete()
  fr_rb_node_t  *next;      ///< if non-NULL, next node cached by fr_rb_iter_delete()
} fr_rb_iter_inorder_t;

void    *fr_rb_iter_init_inorder(fr_rb_tree_t *tree, fr_rb_iter_inorder_t *iter) CC_HINT(nonnull);

void    *fr_rb_iter_next_inorder(fr_rb_tree_t *tree, fr_rb_iter_inorder_t *iter) CC_HINT(nonnull);

void    fr_rb_iter_delete_inorder(fr_rb_tree_t *tree, fr_rb_iter_inorder_t *iter) CC_HINT(nonnull);

#define fr_rb_inorder_foreach(_tree, _type, _iter) \
{ \
  fr_rb_iter_inorder_t _state; \
  for (_type *_iter = fr_rb_iter_init_inorder(_tree, &_state); _iter; _iter = fr_rb_iter_next_inorder(_tree, &_state))

/** Iterator structure for pre-order traversal of an rbtree
 */
typedef struct {
  fr_rb_node_t  *node;      ///< current node
} fr_rb_iter_preorder_t;

void    *fr_rb_iter_init_preorder(fr_rb_tree_t *tree, fr_rb_iter_preorder_t *iter) CC_HINT(nonnull);

void    *fr_rb_iter_next_preorder(fr_rb_tree_t *tree, fr_rb_iter_preorder_t *iter) CC_HINT(nonnull);

#define fr_rb_preorder_foreach(_tree, _type, _iter) \
{ \
  fr_rb_iter_preorder_t _state; \
  for (_type *_iter = fr_rb_iter_init_preorder(_tree, &_state); _iter; _iter = fr_rb_iter_next_preorder(_tree, &_state))

/** Iterator structure for post-order traversal of an rbtree
 */
typedef struct {
  fr_rb_node_t  *node;      ///< current node
} fr_rb_iter_postorder_t;

void    *fr_rb_iter_init_postorder(fr_rb_tree_t *tree, fr_rb_iter_postorder_t *iter) CC_HINT(nonnull);

void    *fr_rb_iter_next_postorder(fr_rb_tree_t *tree, fr_rb_iter_postorder_t *iter) CC_HINT(nonnull);

#define fr_rb_postorder_foreach(_tree, _type, _iter) \
{ \
  fr_rb_iter_postorder_t _state; \
  for (_type *_iter = fr_rb_iter_init_postorder(_tree, &_state); _iter; _iter = fr_rb_iter_next_postorder(_tree, &_state))

int   fr_rb_flatten_inorder(TALLOC_CTX *ctx, void **out[], fr_rb_tree_t *tree);

int   fr_rb_flatten_preorder(TALLOC_CTX *ctx, void **out[], fr_rb_tree_t *tree);

int   fr_rb_flatten_postorder(TALLOC_CTX *ctx, void **out[], fr_rb_tree_t *tree);
#ifdef __cplusplus
}
#endif

Coverage Report

Created: 2026-04-12 06:36