/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: c53c14e0844957beaf7bf00a4bd5381e6c59dcce $")

#ifdef __cplusplus
extern "C" {
#endif

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

#include <stdbool.h>
#include <stdint.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
 *  - A new rbtree on success.
 *  - NULL 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-02-26 06:38

Line	Count	Source
1		#pragma once
2		/*
3		* This program is free software; you can redistribute it and/or modify
4		* it under the terms of the GNU General Public License as published by
5		* the Free Software Foundation; either version 2 of the License, or
6		* (at your option) any later version.
7		*
8		* This program is distributed in the hope that it will be useful,
9		* but WITHOUT ANY WARRANTY; without even the implied warranty of
10		* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
11		* GNU General Public License for more details.
12		*
13		* You should have received a copy of the GNU General Public License
14		* along with this program; if not, write to the Free Software
15		* Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301, USA
16		*/
17
18		/** Red/black tree implementation
19		*
20		* @file src/lib/util/rb.h
21		*
22		* @copyright 2016 The FreeRADIUS server project
23		*/
24		RCSIDH(fr_rb_h, "$Id: c53c14e0844957beaf7bf00a4bd5381e6c59dcce $")
25
26		#ifdef __cplusplus
27		extern "C" {
28		#endif
29
30		#include <freeradius-devel/util/misc.h>
31
32		#include <stdbool.h>
33		#include <stdint.h>
34
35		/* Red-Black tree description */
36		typedef enum {
37		BLACK,
38		RED
39		} fr_rb_colour_t;
40
41		typedef struct fr_rb_node_s fr_rb_node_t;
42		struct fr_rb_node_s {
43		fr_rb_node_t *left; //!< Left child
44		fr_rb_node_t *right; //!< Right child
45		fr_rb_node_t *parent; //!< Parent
46		void *data; //!< data stored in node
47
48		fr_rb_colour_t colour; //!< Node colour (BLACK, RED)
49		bool being_freed; //!< Disable frees if we're currently calling
50		///< a free function.
51		};
52
53		typedef struct fr_rb_tree_s fr_rb_tree_t;
54
55		/** Callback used to alloc rbnodes
56		*
57		* @param[in] tree to allocate the node for.
58		* @param[in] data associated with node.
59		*/
60		typedef fr_rb_node_t ( rb_node_alloc_t)(fr_rb_tree_t const tree, void data);
61
62		/** Callback used to free rbnodes
63		*
64		* @param[in] tree that owns the node.
65		* @param[in] node to free.
66		* @param[in] free_data free user data.
67		*/
68		typedef void (* rb_node_free_t)(fr_rb_tree_t const tree, fr_rb_node_t node, bool free_data);
69
70		/** The main red black tree structure
71		*
72		*/
73		struct fr_rb_tree_s {
74		#ifndef NDEBUG
75		uint32_t magic;
76		#endif
77
78		fr_rb_node_t *root; //!< Root of the rbtree.
79
80		TALLOC_CTX *node_ctx; //!< Talloc ctx to allocate nodes in.
81
82		char const *type; //!< Talloc type to check elements against.
83
84		fr_cmp_t data_cmp; //!< Callback to compare node data.
85		fr_free_t data_free; //!< Callback to free node data.
86
87		rb_node_alloc_t node_alloc; //!< Callback to allocate a new node.
88		rb_node_free_t node_free; //!< Callback to free a node.
89
90		/*
91		* Try and pack these more efficiently
92		* by grouping them together.
93		*/
94		uint16_t offset; //!< Where's the fr_rb_node_t is located in
95		///< the structure being inserted.
96		bool being_freed; //!< Prevent double frees in talloc_destructor.
97		uint32_t num_elements; //!< How many elements are inside the tree.
98		};
99
100		/** Initialises a red black that verifies elements are of a specific talloc type
101		*
102		* This variant allocates an #fr_rb_node_t on the heap. This allows the data
103		* structure to be inserted into multiple trees.
104		*
105		* @param[out] _tree to initialise.
106		* @param[in] _node_ctx to tie tree lifetime to.
107		* If ctx is freed, tree will free any nodes, calling the
108		* free function if set.
109		* @param[in] _type of item being stored in the tree, e.g. fr_value_box_t.
110		* @param[in] _data_cmp Callback to compare node data.
111		* @param[in] _data_free Optional function used to free data if tree nodes are
112		* deleted or replaced.
113		* @return
114		* - A new rbtree on success.
115		* - NULL on failure.
116		*/
117		#define fr_rb_talloc_init(_tree, _node_ctx, _type, _data_cmp, _data_free) \
118		_fr_rb_init(_tree, _node_ctx, -1, #_type, _data_cmp, _data_free)
119
120		/** Initialises a red black tree
121		*
122		* This variant initiates an #fr_rb_node_t on the heap. This allows the data structure
123		* to be inserted into multiple trees.
124		*
125		* @param[out] _tree to initialise.
126		* @param[in] _node_ctx to tie tree lifetime to.
127		* If ctx is freed, tree will free any nodes, calling the
128		* free function if set.
129		* @param[in] _data_cmp Callback to compare node data.
130		* @param[in] _data_free Optional function used to free data if tree nodes are
131		* deleted or replaced.
132		* @return
133		* - A new rbtree on success.
134		* - NULL on failure.
135		*/
136		#define fr_rb_init(_tree, _node_ctx, _data_cmp, _data_free) \
137		_fr_rb_init(_tree, _node_ctx, -1, NULL, _data_cmp, _data_free)
138
139		/** Initialises a red black that verifies elements are of a specific talloc type
140		*
141		* This variant stores #fr_rb_node_t data inline with the data structure to avoid
142		* initiating #fr_rb_node_t on the heap.
143		*
144		* It is suitable for use where the data structure will only be inserted into a
145		* fixed set of trees.
146		*
147		* @param[out] _tree to initialise.
148		* @param[in] _type of item being stored in the tree, e.g. fr_value_box_t.
149		* @param[in] _field Containing the #fr_rb_node_t within item being stored.
150		* @param[in] _data_cmp Callback to compare node data.
151		* @param[in] _data_free Optional function used to free data if tree nodes are
152		* deleted or replaced.
153		* @return
154		* - A new rbtree on success.
155		* - NULL on failure.
156		*/
157		#define fr_rb_inline_talloc_init(_tree, _type, _field, _data_cmp, _data_free) \
158		_Generic((((_type *)0)->_field), \
159		fr_rb_node_t: _fr_rb_init(_tree, NULL, offsetof(_type, _field), #_type, _data_cmp, _data_free) \
160		)
161
162		/** Initialises a red black tree
163		*
164		* This variant stores #fr_rb_node_t data inline with the data structure to avoid
165		* initiating #fr_rb_node_t on the heap.
166		*
167		* It is suitable for use where the data structure will only be inserted into a
168		* fixed set of trees.
169		*
170		* @param[out] _tree to initialise.
171		* @param[in] _type of item being stored in the tree, e.g. fr_value_box_t.
172		* @param[in] _field Containing the #fr_rb_node_t within item being stored.
173		* @param[in] _data_cmp Callback to compare node data.
174		* @param[in] _data_free Optional function used to free data if tree nodes are
175		* deleted or replaced.
176		* @return
177		* - A new rbtree on success.
178		* - NULL on failure.
179		*/
180		#define fr_rb_inline_init(_tree, _type, _field, _data_cmp, _data_free) \
181		_Generic((((_type *)0)->_field), \
182		fr_rb_node_t: _fr_rb_init(_tree, NULL, offsetof(_type, _field), NULL, _data_cmp, _data_free) \
183		)
184
185		int _fr_rb_init(fr_rb_tree_t tree, TALLOC_CTX node_ctx,
186		ssize_t offset, char const *type,
187		fr_cmp_t data_cmp, fr_free_t data_free);
188
189		/** Allocs a red black that verifies elements are of a specific talloc type
190		*
191		* This variant allocates an #fr_rb_node_t on the heap. This allows the data structure
192		* to be inserted into multiple trees.
193		*
194		* @param[in] _ctx to tie tree lifetime to.
195		* If ctx is freed, tree will free any nodes, calling the
196		* free function if set.
197		* @param[in] _type of item being stored in the tree, e.g. fr_value_box_t.
198		* @param[in] _data_cmp Callback to compare node data.
199		* @param[in] _data_free Optional function used to free data if tree nodes are
200		* deleted or replaced.
201		* @return
202		* - A new rbtree on success.
203		* - NULL on failure.
204		*/
205		#define fr_rb_talloc_alloc(_ctx, _type, _data_cmp, _data_free) \
206		_fr_rb_alloc(_ctx, -1, #_type, _data_cmp, _data_free)
207
208		/** Allocs a red black tree
209		*
210		* This variant allocates an #fr_rb_node_t on the heap. This allows the data structure
211		* to be inserted into multiple trees.
212		*
213		* @param[in] _ctx to tie tree lifetime to.
214		* If ctx is freed, tree will free any nodes, calling the
215		* free function if set.
216		* @param[in] _data_cmp Callback to compare node data.
217		* @param[in] _data_free Optional function used to free data if tree nodes are
218		* deleted or replaced.
219		* @return
220		* - A new rbtree on success.
221		* - NULL on failure.
222		*/
223		#define fr_rb_alloc(_ctx, _data_cmp, _data_free) \
224	0	_fr_rb_alloc(_ctx, -1, NULL, _data_cmp, _data_free)
225
226		/** Allocs a red black that verifies elements are of a specific talloc type
227		*
228		* This variant stores #fr_rb_node_t data inline with the data structure to avoid
229		* allocating #fr_rb_node_t on the heap.
230		*
231		* It is suitable for use where the data structure will only be inserted into a fixed
232		* set of trees.
233		*
234		* @param[in] _ctx to tie tree lifetime to.
235		* If ctx is freed, tree will free any nodes, calling the
236		* free function if set.
237		* @param[in] _type of item being stored in the tree, e.g. fr_value_box_t.
238		* @param[in] _field Containing the #fr_rb_node_t within item being stored.
239		* @param[in] _data_cmp Callback to compare node data.
240		* @param[in] _data_free Optional function used to free data if tree nodes are
241		* deleted or replaced.
242		* @return
243		* - A new rbtree on success.
244		* - NULL on failure.
245		*/
246		#define fr_rb_inline_talloc_alloc(_ctx, _type, _field, _data_cmp, _data_free) \
247	43	_Generic((((_type *)0)->_field), \
248	43	fr_rb_node_t: _fr_rb_alloc(_ctx, offsetof(_type, _field), #_type, _data_cmp, _data_free) \
249	43	)
250
251		/** Allocs a red black tree
252		*
253		* This variant stores #fr_rb_node_t data inline with the data structure to avoid
254		* allocating #fr_rb_node_t on the heap.
255		*
256		* It is suitable for use where the data structure will only be inserted into a fixed
257		* set of trees.
258		*
259		* @param[in] _ctx to tie tree lifetime to.
260		* If ctx is freed, tree will free any nodes, calling the
261		* free function if set.
262		* @param[in] _type of item being stored in the tree, e.g. fr_value_box_t.
263		* @param[in] _field Containing the #fr_rb_node_t within item being stored.
264		* @param[in] _data_cmp Callback to compare node data.
265		* @param[in] _data_free Optional function used to free data if tree nodes are
266		* deleted or replaced.
267		* @return
268		* - A new rbtree on success.
269		* - NULL on failure.
270		*/
271		#define fr_rb_inline_alloc(_ctx, _type, _field, _data_cmp, _data_free) \
272	38	_Generic((((_type *)0)->_field), \
273	38	fr_rb_node_t: _fr_rb_alloc(_ctx, offsetof(_type, _field), NULL, _data_cmp, _data_free) \
274	38	)
275
276		fr_rb_tree_t _fr_rb_alloc(TALLOC_CTX ctx, ssize_t offset, char const *type,
277		fr_cmp_t data_cmp, fr_free_t data_free) CC_HINT(warn_unused_result);
278
279		/** @hidecallergraph */
280		void fr_rb_find(fr_rb_tree_t const tree, void const *data) CC_HINT(nonnull);
281
282		int fr_rb_find_or_insert(void *found, fr_rb_tree_t tree, void const *data) CC_HINT(nonnull(2,3));
283
284		bool fr_rb_insert(fr_rb_tree_t tree, void const data) CC_HINT(nonnull);
285
286		int fr_rb_replace(void *old, fr_rb_tree_t tree, void const *data) CC_HINT(nonnull(2,3));
287
288		void fr_rb_remove(fr_rb_tree_t tree, void const *data) CC_HINT(nonnull);
289
290		void fr_rb_remove_by_inline_node(fr_rb_tree_t tree, fr_rb_node_t *node) CC_HINT(nonnull);
291
292		bool fr_rb_delete(fr_rb_tree_t tree, void const data) CC_HINT(nonnull);
293
294		bool fr_rb_delete_by_inline_node(fr_rb_tree_t tree, fr_rb_node_t node) CC_HINT(nonnull);
295
296		uint32_t fr_rb_num_elements(fr_rb_tree_t *tree) CC_HINT(nonnull);
297
298		void fr_rb_first(fr_rb_tree_t tree) CC_HINT(nonnull);
299
300		void fr_rb_last(fr_rb_tree_t tree) CC_HINT(nonnull);
301
302		/** Check to see if an item is in a tree by examining its inline #fr_rb_node_t
303		*
304		* This works because we use NIL sentinels to represent the absence of a child
305		* or parent. When the node is initialised all these fields should be NULL
306		* and when it's removed from the tree, the "free" function for inline nodes
307		* also sets all of these back to NULL.
308		*
309		* @param[in] node to check.
310		* @return
311		* - true if node is in the tree.
312		* - talse if node is not in the tree.
313		*/
314		static inline bool fr_rb_node_inline_in_tree(fr_rb_node_t const *node)
315	0	{
316	0	return (node->left && node->right && node->parent && !node->being_freed);
317	0	} Unexecuted instantiation: fuzzer_dhcpv6.c:fr_rb_node_inline_in_tree Unexecuted instantiation: fuzzer_util.c:fr_rb_node_inline_in_tree Unexecuted instantiation: fuzzer_dhcpv4.c:fr_rb_node_inline_in_tree Unexecuted instantiation: fuzzer_cbor.c:fr_rb_node_inline_in_tree Unexecuted instantiation: fuzzer_der.c:fr_rb_node_inline_in_tree Unexecuted instantiation: fuzzer_dns.c:fr_rb_node_inline_in_tree Unexecuted instantiation: fuzzer_tacacs.c:fr_rb_node_inline_in_tree Unexecuted instantiation: fuzzer_bfd.c:fr_rb_node_inline_in_tree Unexecuted instantiation: fuzzer_radius.c:fr_rb_node_inline_in_tree Unexecuted instantiation: fuzzer_tftp.c:fr_rb_node_inline_in_tree Unexecuted instantiation: fuzzer_vmps.c:fr_rb_node_inline_in_tree Unexecuted instantiation: base32.c:fr_rb_node_inline_in_tree Unexecuted instantiation: base64.c:fr_rb_node_inline_in_tree Unexecuted instantiation: calc.c:fr_rb_node_inline_in_tree Unexecuted instantiation: cbor.c:fr_rb_node_inline_in_tree Unexecuted instantiation: decode.c:fr_rb_node_inline_in_tree Unexecuted instantiation: dict_ext.c:fr_rb_node_inline_in_tree Unexecuted instantiation: dict_fixup.c:fr_rb_node_inline_in_tree Unexecuted instantiation: dict_print.c:fr_rb_node_inline_in_tree Unexecuted instantiation: dict_test.c:fr_rb_node_inline_in_tree Unexecuted instantiation: dict_tokenize.c:fr_rb_node_inline_in_tree Unexecuted instantiation: dict_unknown.c:fr_rb_node_inline_in_tree Unexecuted instantiation: dict_util.c:fr_rb_node_inline_in_tree Unexecuted instantiation: dict_validate.c:fr_rb_node_inline_in_tree Unexecuted instantiation: dl.c:fr_rb_node_inline_in_tree Unexecuted instantiation: dns.c:fr_rb_node_inline_in_tree Unexecuted instantiation: edit.c:fr_rb_node_inline_in_tree Unexecuted instantiation: encode.c:fr_rb_node_inline_in_tree Unexecuted instantiation: event.c:fr_rb_node_inline_in_tree Unexecuted instantiation: timer.c:fr_rb_node_inline_in_tree Unexecuted instantiation: file.c:fr_rb_node_inline_in_tree Unexecuted instantiation: htrie.c:fr_rb_node_inline_in_tree Unexecuted instantiation: inet.c:fr_rb_node_inline_in_tree Unexecuted instantiation: log.c:fr_rb_node_inline_in_tree Unexecuted instantiation: packet.c:fr_rb_node_inline_in_tree Unexecuted instantiation: pair.c:fr_rb_node_inline_in_tree Unexecuted instantiation: pair_inline.c:fr_rb_node_inline_in_tree Unexecuted instantiation: pair_legacy.c:fr_rb_node_inline_in_tree Unexecuted instantiation: pair_print.c:fr_rb_node_inline_in_tree Unexecuted instantiation: pair_tokenize.c:fr_rb_node_inline_in_tree Unexecuted instantiation: print.c:fr_rb_node_inline_in_tree Unexecuted instantiation: proto.c:fr_rb_node_inline_in_tree Unexecuted instantiation: rb.c:fr_rb_node_inline_in_tree Unexecuted instantiation: rb_expire.c:fr_rb_node_inline_in_tree Unexecuted instantiation: regex.c:fr_rb_node_inline_in_tree Unexecuted instantiation: socket.c:fr_rb_node_inline_in_tree Unexecuted instantiation: stats.c:fr_rb_node_inline_in_tree Unexecuted instantiation: struct.c:fr_rb_node_inline_in_tree Unexecuted instantiation: trie.c:fr_rb_node_inline_in_tree Unexecuted instantiation: types.c:fr_rb_node_inline_in_tree Unexecuted instantiation: uri.c:fr_rb_node_inline_in_tree Unexecuted instantiation: value.c:fr_rb_node_inline_in_tree Unexecuted instantiation: fuzzer.c:fr_rb_node_inline_in_tree Unexecuted instantiation: base.c:fr_rb_node_inline_in_tree Unexecuted instantiation: raw.c:fr_rb_node_inline_in_tree Unexecuted instantiation: udp.c:fr_rb_node_inline_in_tree Unexecuted instantiation: list.c:fr_rb_node_inline_in_tree Unexecuted instantiation: tcp.c:fr_rb_node_inline_in_tree Unexecuted instantiation: abinary.c:fr_rb_node_inline_in_tree Unexecuted instantiation: vmps.c:fr_rb_node_inline_in_tree
318
319		/** Iterator structure for in-order traversal of an rbtree
320		*/
321		typedef struct {
322		fr_rb_node_t *node; ///< current node--set to NULL (not NIL) by fr_rb_iter_delete()
323		fr_rb_node_t *next; ///< if non-NULL, next node cached by fr_rb_iter_delete()
324		} fr_rb_iter_inorder_t;
325
326		void fr_rb_iter_init_inorder(fr_rb_tree_t tree, fr_rb_iter_inorder_t *iter) CC_HINT(nonnull);
327
328		void fr_rb_iter_next_inorder(fr_rb_tree_t tree, fr_rb_iter_inorder_t *iter) CC_HINT(nonnull);
329
330		void fr_rb_iter_delete_inorder(fr_rb_tree_t tree, fr_rb_iter_inorder_t iter) CC_HINT(nonnull);
331
332		#define fr_rb_inorder_foreach(_tree, _type, _iter) \
333		{ \
334		fr_rb_iter_inorder_t _state; \
335		for (_type *_iter = fr_rb_iter_init_inorder(_tree, &_state); _iter; _iter = fr_rb_iter_next_inorder(_tree, &_state))
336
337		/** Iterator structure for pre-order traversal of an rbtree
338		*/
339		typedef struct {
340		fr_rb_node_t *node; ///< current node
341		} fr_rb_iter_preorder_t;
342
343		void fr_rb_iter_init_preorder(fr_rb_tree_t tree, fr_rb_iter_preorder_t *iter) CC_HINT(nonnull);
344
345		void fr_rb_iter_next_preorder(fr_rb_tree_t tree, fr_rb_iter_preorder_t *iter) CC_HINT(nonnull);
346
347		#define fr_rb_preorder_foreach(_tree, _type, _iter) \
348		{ \
349		fr_rb_iter_preorder_t _state; \
350		for (_type *_iter = fr_rb_iter_init_preorder(_tree, &_state); _iter; _iter = fr_rb_iter_next_preorder(_tree, &_state))
351
352		/** Iterator structure for post-order traversal of an rbtree
353		*/
354		typedef struct {
355		fr_rb_node_t *node; ///< current node
356		} fr_rb_iter_postorder_t;
357
358		void fr_rb_iter_init_postorder(fr_rb_tree_t tree, fr_rb_iter_postorder_t *iter) CC_HINT(nonnull);
359
360		void fr_rb_iter_next_postorder(fr_rb_tree_t tree, fr_rb_iter_postorder_t *iter) CC_HINT(nonnull);
361
362		#define fr_rb_postorder_foreach(_tree, _type, _iter) \
363		{ \
364		fr_rb_iter_postorder_t _state; \
365		for (_type *_iter = fr_rb_iter_init_postorder(_tree, &_state); _iter; _iter = fr_rb_iter_next_postorder(_tree, &_state))
366
367		int fr_rb_flatten_inorder(TALLOC_CTX ctx, void out[], fr_rb_tree_t tree);
368
369		int fr_rb_flatten_preorder(TALLOC_CTX ctx, void out[], fr_rb_tree_t tree);
370
371		int fr_rb_flatten_postorder(TALLOC_CTX ctx, void out[], fr_rb_tree_t tree);
372		#ifdef __cplusplus
373		}
374		#endif