Red/black tree implementation. More...

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

Include dependency graph for rb.h:

Data Structures
struct	fr_rb_iter_inorder_t
	Iterator structure for in-order traversal of an rbtree. More...

struct	fr_rb_iter_postorder_t
	Iterator structure for post-order traversal of an rbtree. More...

struct	fr_rb_iter_preorder_t
	Iterator structure for pre-order traversal of an rbtree. More...

struct	fr_rb_node_s

struct	fr_rb_tree_s
	The main red black tree structure. More...

Macros
#define	fr_rb_alloc(_ctx, _data_cmp, _data_free) _fr_rb_alloc(_ctx, -1, NULL, _data_cmp, _data_free)
	Allocs a red black tree. More...

#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 tree. More...

#define	fr_rb_inline_alloc(_ctx, _type, _field, _data_cmp, _data_free)
	Allocs a red black tree. More...

#define	fr_rb_inline_init(_tree, _type, _field, _data_cmp, _data_free)
	Initialises a red black tree. More...

#define	fr_rb_inline_talloc_alloc(_ctx, _type, _field, _data_cmp, _data_free)
	Allocs a red black that verifies elements are of a specific talloc type. More...

#define	fr_rb_inline_talloc_init(_tree, _type, _field, _data_cmp, _data_free)
	Initialises a red black that verifies elements are of a specific talloc type. More...

#define	fr_rb_inorder_foreach(_tree, _type, _iter)

#define	fr_rb_postorder_foreach(_tree, _type, _iter)

#define	fr_rb_preorder_foreach(_tree, _type, _iter)

#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 that verifies elements are of a specific talloc type. More...

#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 that verifies elements are of a specific talloc type. More...

Typedefs
typedef struct fr_rb_node_s	fr_rb_node_t

typedef struct fr_rb_tree_s	fr_rb_tree_t

typedef fr_rb_node_t (	rb_node_alloc_t) (fr_rb_tree_t const tree, void data)
	Callback used to alloc rbnodes. More...

typedef void(*	rb_node_free_t) (fr_rb_tree_t const tree, fr_rb_node_t node, bool free_data)
	Callback used to free rbnodes. More...

Enumerations
enum	fr_rb_colour_t { BLACK , RED }

Functions
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)
	Alloc a new RED-BLACK tree. More...

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)
	Initialise a new RED-BLACK tree. More...

bool	fr_rb_delete (fr_rb_tree_t tree, void const data)

bool	fr_rb_delete_by_inline_node (fr_rb_tree_t tree, fr_rb_node_t node)
	Remove node and free data (if a free function was specified) More...

void *	fr_rb_find (fr_rb_tree_t const tree, void const data)

int	fr_rb_find_or_insert (void *found, fr_rb_tree_t tree, void const *data))
	Attempt to find current data in the tree, if it does not exist insert it. More...

void *	fr_rb_first (fr_rb_tree_t *tree)

int	fr_rb_flatten_inorder (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)

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

bool	fr_rb_insert (fr_rb_tree_t tree, void const data)

void	fr_rb_iter_delete_inorder (fr_rb_iter_inorder_t *iter)
	Remove the current node from the tree. More...

void *	fr_rb_iter_init_inorder (fr_rb_iter_inorder_t iter, fr_rb_tree_t tree)
	Initialise an in-order iterator. More...

void *	fr_rb_iter_init_postorder (fr_rb_iter_postorder_t iter, fr_rb_tree_t tree)
	Initialise a post-order iterator. More...

void *	fr_rb_iter_init_preorder (fr_rb_iter_preorder_t iter, fr_rb_tree_t tree)
	Initialise a pre-order iterator. More...

void *	fr_rb_iter_next_inorder (fr_rb_iter_inorder_t *iter)
	Return the next node. More...

void *	fr_rb_iter_next_postorder (fr_rb_iter_postorder_t *iter)
	Return the next node. More...

void *	fr_rb_iter_next_preorder (fr_rb_iter_preorder_t *iter)
	Return the next node. More...

void *	fr_rb_last (fr_rb_tree_t *tree)

static bool	fr_rb_node_inline_in_tree (fr_rb_node_t const *node)
	Check to see if an item is in a tree by examining its inline fr_rb_node_t. More...

uint32_t	fr_rb_num_elements (fr_rb_tree_t *tree)

void *	fr_rb_remove (fr_rb_tree_t tree, void const data)

void *	fr_rb_remove_by_inline_node (fr_rb_tree_t tree, fr_rb_node_t node)
	Remove an entry from the tree, using the node structure, without freeing the data. More...

int	fr_rb_replace (void *old, fr_rb_tree_t tree, void const *data))

Detailed Description

Red/black tree implementation.

Copyright: 2016 The FreeRADIUS server project

Definition in file rb.h.

Data Structure Documentation

◆ fr_rb_iter_inorder_t

struct fr_rb_iter_inorder_t

Iterator structure for in-order traversal of an rbtree.

Definition at line 321 of file rb.h.

Collaboration diagram for fr_rb_iter_inorder_t:

Data Fields
fr_rb_node_t *	next	if non-NULL, next node cached by fr_rb_iter_delete()
fr_rb_node_t *	node	current node–set to NULL (not NIL) by fr_rb_iter_delete()
fr_rb_tree_t *	tree	Tree being iterated over.

◆ fr_rb_iter_postorder_t

struct fr_rb_iter_postorder_t

Iterator structure for post-order traversal of an rbtree.

Definition at line 356 of file rb.h.

Collaboration diagram for fr_rb_iter_postorder_t:

Data Fields
fr_rb_node_t *	node	current node
fr_rb_tree_t *	tree	Tree being iterated over.

◆ fr_rb_iter_preorder_t

struct fr_rb_iter_preorder_t

Iterator structure for pre-order traversal of an rbtree.

Definition at line 340 of file rb.h.

Collaboration diagram for fr_rb_iter_preorder_t:

Data Fields
fr_rb_node_t *	node	current node
fr_rb_tree_t *	tree	Tree being iterated over.

◆ fr_rb_node_s

struct fr_rb_node_s

Definition at line 42 of file rb.h.

Collaboration diagram for fr_rb_node_s:

Data Fields
bool	being_freed	Disable frees if we're currently calling a free function.
fr_rb_colour_t	colour	Node colour (BLACK, RED)
void *	data	data stored in node
fr_rb_node_t *	left	Left child.
fr_rb_node_t *	parent	Parent.
fr_rb_node_t *	right	Right child.

◆ fr_rb_tree_s

struct fr_rb_tree_s

The main red black tree structure.

Definition at line 73 of file rb.h.

Collaboration diagram for fr_rb_tree_s:

Data Fields
bool	being_freed	Prevent double frees in talloc_destructor.
fr_cmp_t	data_cmp	Callback to compare node data.
fr_free_t	data_free	Callback to free node data.
uint32_t	magic
rb_node_alloc_t	node_alloc	Callback to allocate a new node.
TALLOC_CTX *	node_ctx	Talloc ctx to allocate nodes in.
rb_node_free_t	node_free	Callback to free a node.
uint32_t	num_elements	How many elements are inside the tree.
uint16_t	offset	Where's the fr_rb_node_t is located in the structure being inserted.
fr_rb_node_t *	root	Root of the rbtree.
char const *	type	Talloc type to check elements against.

Macro Definition Documentation

◆ fr_rb_alloc

#define fr_rb_alloc	(	_ctx,
		_data_cmp,
		_data_free
	)	_fr_rb_alloc(_ctx, -1, NULL, _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.

Parameters

[in]	_ctx	to tie tree lifetime to. If ctx is freed, tree will free any nodes, calling the free function if set.
[in]	_data_cmp	Callback to compare node data.
[in]	_data_free	Optional function used to free data if tree nodes are deleted or replaced.

Returns

A new rbtree on success.
NULL on failure.

Definition at line 223 of file rb.h.

◆ fr_rb_init

#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 tree.

This variant initiates an fr_rb_node_t on the heap. This allows the data structure to be inserted into multiple trees.

Parameters

[out]	_tree	to initialise.
[in]	_node_ctx	to tie tree lifetime to. If ctx is freed, tree will free any nodes, calling the free function if set.
[in]	_data_cmp	Callback to compare node data.
[in]	_data_free	Optional function used to free data if tree nodes are deleted or replaced.

Returns

A new rbtree on success.
NULL on failure.

Definition at line 136 of file rb.h.

◆ fr_rb_inline_alloc

#define fr_rb_inline_alloc	(	_ctx,
		_type,
		_field,
		_data_cmp,
		_data_free
	)

Value:

                _Generic((((_type *)0)->_field), \
                        fr_rb_node_t: _fr_rb_alloc(_ctx, offsetof(_type, _field), NULL, _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.

Parameters

[in]	_ctx	to tie tree lifetime to. If ctx is freed, tree will free any nodes, calling the free function if set.
[in]	_type	of item being stored in the tree, e.g. fr_value_box_t.
[in]	_field	Containing the fr_rb_node_t within item being stored.
[in]	_data_cmp	Callback to compare node data.
[in]	_data_free	Optional function used to free data if tree nodes are deleted or replaced.

Returns

A new rbtree on success.
NULL on failure.

Definition at line 271 of file rb.h.

◆ fr_rb_inline_init

#define fr_rb_inline_init	(	_tree,
		_type,
		_field,
		_data_cmp,
		_data_free
	)

Value:

                _Generic((((_type *)0)->_field), \
                        fr_rb_node_t: _fr_rb_init(_tree, NULL, offsetof(_type, _field), NULL, _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.

Parameters

[out]	_tree	to initialise.
[in]	_type	of item being stored in the tree, e.g. fr_value_box_t.
[in]	_field	Containing the fr_rb_node_t within item being stored.
[in]	_data_cmp	Callback to compare node data.
[in]	_data_free	Optional function used to free data if tree nodes are deleted or replaced.

Returns

A new rbtree on success.
NULL on failure.

Definition at line 180 of file rb.h.

◆ fr_rb_inline_talloc_alloc

#define fr_rb_inline_talloc_alloc	(	_ctx,
		_type,
		_field,
		_data_cmp,
		_data_free
	)

Value:

                _Generic((((_type *)0)->_field), \
                        fr_rb_node_t: _fr_rb_alloc(_ctx, offsetof(_type, _field), #_type, _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.

Parameters

[in]	_ctx	to tie tree lifetime to. If ctx is freed, tree will free any nodes, calling the free function if set.
[in]	_type	of item being stored in the tree, e.g. fr_value_box_t.
[in]	_field	Containing the fr_rb_node_t within item being stored.
[in]	_data_cmp	Callback to compare node data.
[in]	_data_free	Optional function used to free data if tree nodes are deleted or replaced.

Returns

A new rbtree on success.
NULL on failure.

Definition at line 246 of file rb.h.

◆ fr_rb_inline_talloc_init

#define fr_rb_inline_talloc_init	(	_tree,
		_type,
		_field,
		_data_cmp,
		_data_free
	)

Value:

                _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 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.

Parameters

[out]	_tree	to initialise.
[in]	_type	of item being stored in the tree, e.g. fr_value_box_t.
[in]	_field	Containing the fr_rb_node_t within item being stored.
[in]	_data_cmp	Callback to compare node data.
[in]	_data_free	Optional function used to free data if tree nodes are deleted or replaced.

Returns

A new rbtree on success.
NULL on failure.

Definition at line 157 of file rb.h.

◆ fr_rb_inorder_foreach

#define fr_rb_inorder_foreach	(	_tree,
		_type,
		_iter
	)

Value:

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

Definition at line 333 of file rb.h.

◆ fr_rb_postorder_foreach

#define fr_rb_postorder_foreach	(	_tree,
		_type,
		_iter
	)

Value:

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

Definition at line 365 of file rb.h.

◆ fr_rb_preorder_foreach

#define fr_rb_preorder_foreach	(	_tree,
		_type,
		_iter
	)

Value:

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

Definition at line 349 of file rb.h.

◆ fr_rb_talloc_alloc

#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 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.

Parameters

[in]	_ctx	to tie tree lifetime to. If ctx is freed, tree will free any nodes, calling the free function if set.
[in]	_type	of item being stored in the tree, e.g. fr_value_box_t.
[in]	_data_cmp	Callback to compare node data.
[in]	_data_free	Optional function used to free data if tree nodes are deleted or replaced.

Returns

A new rbtree on success.
NULL on failure.

Definition at line 205 of file rb.h.

◆ fr_rb_talloc_init

#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 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.

Parameters

[out]	_tree	to initialise.
[in]	_node_ctx	to tie tree lifetime to. If ctx is freed, tree will free any nodes, calling the free function if set.
[in]	_type	of item being stored in the tree, e.g. fr_value_box_t.
[in]	_data_cmp	Callback to compare node data.
[in]	_data_free	Optional function used to free data if tree nodes are deleted or replaced.

Returns

A new rbtree on success.
NULL on failure.

Definition at line 117 of file rb.h.

Typedef Documentation

◆ fr_rb_node_t

typedef struct fr_rb_node_s fr_rb_node_t

Definition at line 1 of file rb.h.

◆ fr_rb_tree_t

typedef struct fr_rb_tree_s fr_rb_tree_t

Definition at line 1 of file rb.h.

◆ rb_node_alloc_t

typedef fr_rb_node_t*(* rb_node_alloc_t) (fr_rb_tree_t const *tree, void *data)

Callback used to alloc rbnodes.

Parameters

[in]	tree	to allocate the node for.
[in]	data	associated with node.

Definition at line 60 of file rb.h.

◆ rb_node_free_t

typedef void(* rb_node_free_t) (fr_rb_tree_t const *tree, fr_rb_node_t *node, bool free_data)

Callback used to free rbnodes.

Parameters

[in]	tree	that owns the node.
[in]	node	to free.
[in]	free_data	free user data.

Definition at line 68 of file rb.h.

Enumeration Type Documentation

◆ fr_rb_colour_t

enum fr_rb_colour_t

Enumerator
BLACK
RED

Definition at line 36 of file rb.h.

Function Documentation

◆ _fr_rb_alloc()

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
	)

Alloc a new RED-BLACK tree.

Parameters

[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.
[in]	offset	offsetof the fr_rb_node_t field in the data being inserted. If < 0, nodes will be allocated on the heap.
[in]	type	Talloc type of structures being inserted, may be NULL.
[in]	data_cmp	Comparator function for ordering data in the tree.
[in]	data_free	Free function to call whenever data is deleted or replaced.

Returns

A new tree on success.
NULL on failure.

Definition at line 202 of file rb.c.

Here is the call graph for this function:

◆ _fr_rb_init()

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
	)

Initialise a new RED-BLACK tree.

Parameters

[out]	tree	to initialise.
[in]	node_ctx	the ctx used to allocate fr_rb_node_t if the tree isn't using inline fr_rb_node_t.
[in]	offset	offsetof the fr_rb_node_t field in the data being inserted. If < 0, nodes will be allocated on the heap.
[in]	type	Talloc type of structures being inserted, may be NULL.
[in]	data_cmp	Comparator function for ordering data in the tree.
[in]	data_free	Free function to call whenever data is deleted or replaced.

Returns

-1 on error.
0 on success.

Definition at line 147 of file rb.c.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ fr_rb_delete()

bool fr_rb_delete	(	fr_rb_tree_t *	tree,
		void const *	data
	)

Here is the caller graph for this function:

◆ fr_rb_delete_by_inline_node()

bool fr_rb_delete_by_inline_node	(	fr_rb_tree_t *	tree,
		fr_rb_node_t *	node
	)

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.

Parameters

[in]	tree	to remove data from.
[in]	node	to remove/free.

Returns

true if we removed data.
false if we couldn't find any matching data.

Definition at line 767 of file rb.c.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ fr_rb_find()

void* fr_rb_find	(	fr_rb_tree_t const *	tree,
		void const *	data
	)

◆ fr_rb_find_or_insert()

int fr_rb_find_or_insert	(	void **	found,
		fr_rb_tree_t *	tree,
		void const *	data
	)

Attempt to find current data in the tree, if it does not exist insert it.

Parameters

[out]	found	Pre-existing data we found.
[in]	tree	to search/insert into.
[in]	data	to find.

Returns

1 if existing data was found, found will be populated.
0 if no existing data was found.
-1 on insert error.

Definition at line 598 of file rb.c.

Here is the call graph for this function:

◆ fr_rb_first()

void* fr_rb_first ( fr_rb_tree_t * tree )

Definition at line 786 of file rb.c.

Here is the caller graph for this function:

◆ fr_rb_flatten_inorder()

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

Here is the caller graph for this function:

◆ fr_rb_flatten_postorder()

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

◆ fr_rb_flatten_preorder()

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

◆ fr_rb_insert()

bool fr_rb_insert	(	fr_rb_tree_t *	tree,
		void const *	data
	)

◆ fr_rb_iter_delete_inorder()

void fr_rb_iter_delete_inorder ( fr_rb_iter_inorder_t * iter )

Remove the current node from the tree.

Note: Only makes sense for in-order traversals.

Parameters

[in] iter previously initialised with fr_rb_iter_init_inorder

Definition at line 898 of file rb.c.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ fr_rb_iter_init_inorder()

void* fr_rb_iter_init_inorder	(	fr_rb_iter_inorder_t *	iter,
		fr_rb_tree_t *	tree
	)

Initialise an in-order iterator.

Parameters

[out]	iter	to initialise.
[in]	tree	to iterate over.

Returns

The first node. Mutex will be held.
NULL if the tree is empty.

Definition at line 824 of file rb.c.

Here is the caller graph for this function:

◆ fr_rb_iter_init_postorder()

void* fr_rb_iter_init_postorder	(	fr_rb_iter_postorder_t *	iter,
		fr_rb_tree_t *	tree
	)

Initialise a post-order iterator.

Parameters

[out]	iter	to initialise.
[in]	tree	to iterate over.

Returns

The first node.
NULL if the tree is empty.

Definition at line 994 of file rb.c.

Here is the caller graph for this function:

◆ fr_rb_iter_init_preorder()

void* fr_rb_iter_init_preorder	(	fr_rb_iter_preorder_t *	iter,
		fr_rb_tree_t *	tree
	)

Initialise a pre-order iterator.

Parameters

[out]	iter	to initialise.
[in]	tree	to iterate over.

Returns

The first node. Mutex will be held.
NULL if the tree is empty.

Definition at line 917 of file rb.c.

Here is the caller graph for this function:

◆ fr_rb_iter_next_inorder()

void* fr_rb_iter_next_inorder ( fr_rb_iter_inorder_t * iter )

Return the next node.

Parameters

[in] iter previously initialised with fr_rb_iter_init_inorder

Returns

The next node.
NULL if no more nodes remain.

Definition at line 850 of file rb.c.

Here is the caller graph for this function:

◆ fr_rb_iter_next_postorder()

void* fr_rb_iter_next_postorder ( fr_rb_iter_postorder_t * iter )

Return the next node.

Parameters

[in] iter previously initialised with fr_rb_iter_init_postorder

Returns

The next node.
NULL if no more nodes remain.

Definition at line 1025 of file rb.c.

Here is the caller graph for this function:

◆ fr_rb_iter_next_preorder()

void* fr_rb_iter_next_preorder ( fr_rb_iter_preorder_t * iter )

Return the next node.

Parameters

[in] iter previously initialised with fr_rb_iter_init_preorder

Returns

The next node.
NULL if no more nodes remain.

Definition at line 941 of file rb.c.

Here is the caller graph for this function:

◆ fr_rb_last()

void* fr_rb_last ( fr_rb_tree_t * tree )

Definition at line 801 of file rb.c.

◆ fr_rb_node_inline_in_tree()

static bool fr_rb_node_inline_in_tree ( fr_rb_node_t const * node )

inlinestatic

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.

Parameters

[in] node to check.

Returns

true if node is in the tree.
talse if node is not in the tree.

Definition at line 314 of file rb.h.

Here is the caller graph for this function:

◆ fr_rb_num_elements()

uint32_t fr_rb_num_elements ( fr_rb_tree_t * tree )

Here is the caller graph for this function:

◆ fr_rb_remove()

void* fr_rb_remove	(	fr_rb_tree_t *	tree,
		void const *	data
	)

Here is the caller graph for this function:

◆ fr_rb_remove_by_inline_node()

void* fr_rb_remove_by_inline_node	(	fr_rb_tree_t *	tree,
		fr_rb_node_t *	node
	)

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.

Parameters

[in]	tree	to remove data from.
[in]	node	to remove.

Returns

The user data we removed.
NULL if the user data wasn't in the tree.

Definition at line 722 of file rb.c.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ fr_rb_replace()

int fr_rb_replace	(	void **	old,
		fr_rb_tree_t *	tree,
		void const *	data
	)

Here is the caller graph for this function:

Data Structures

Macros

Typedefs

Enumerations

Functions

Detailed Description

Data Structure Documentation

◆ fr_rb_iter_inorder_t

◆ fr_rb_iter_postorder_t

◆ fr_rb_iter_preorder_t

◆ fr_rb_node_s

◆ fr_rb_tree_s

Macro Definition Documentation

◆ fr_rb_alloc

◆ fr_rb_init

◆ fr_rb_inline_alloc

◆ fr_rb_inline_init

◆ fr_rb_inline_talloc_alloc

◆ fr_rb_inline_talloc_init

◆ fr_rb_inorder_foreach

◆ fr_rb_postorder_foreach

◆ fr_rb_preorder_foreach

◆ fr_rb_talloc_alloc

◆ fr_rb_talloc_init

Typedef Documentation

◆ fr_rb_node_t

◆ fr_rb_tree_t

◆ rb_node_alloc_t

◆ rb_node_free_t

Enumeration Type Documentation

◆ fr_rb_colour_t

Function Documentation

◆ _fr_rb_alloc()

◆ _fr_rb_init()

◆ fr_rb_delete()

◆ fr_rb_delete_by_inline_node()

◆ fr_rb_find()

◆ fr_rb_find_or_insert()

◆ fr_rb_first()

◆ fr_rb_flatten_inorder()

◆ fr_rb_flatten_postorder()

◆ fr_rb_flatten_preorder()

◆ fr_rb_insert()

◆ fr_rb_iter_delete_inorder()

◆ fr_rb_iter_init_inorder()

◆ fr_rb_iter_init_postorder()

◆ fr_rb_iter_init_preorder()

◆ fr_rb_iter_next_inorder()

◆ fr_rb_iter_next_postorder()

◆ fr_rb_iter_next_preorder()

◆ fr_rb_last()

◆ fr_rb_node_inline_in_tree()

◆ fr_rb_num_elements()

◆ fr_rb_remove()

◆ fr_rb_remove_by_inline_node()

◆ fr_rb_replace()