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)
	Remove node and free data (if a free function was specified) More...

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)
	Find an element in the tree, returning the data, not the node. More...

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)
	Insert data into a tree. More...

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)
	Return how many nodes there are in a tree. More...

void *	fr_rb_remove (fr_rb_tree_t tree, void const data)
	Remove an entry from the tree, without freeing the data. More...

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))
	Replace old data with new data, OR insert if there is no old. More...

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
	)

Remove node and free data (if a free function was specified)

Parameters

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

Returns

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

Definition at line 736 of file rb.c.

Here is the call graph for this function:

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

Find an element in the tree, returning the data, not the node.

Parameters

[in]	tree	to search in.
[in]	data	to find.

Returns

User data matching the data passed in.
NULL if nothing matched passed data.

Definition at line 576 of file rb.c.

Here is the call graph for this function:

◆ 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 597 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 780 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
	)

Insert data into a tree.

Parameters

[in]	tree	to insert data into.
[in]	data	to insert.

Returns

true if data was inserted.
false if data already existed and was not inserted.

Definition at line 624 of file rb.c.

Here is the call graph for this function:

◆ 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 892 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 818 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 988 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 911 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 844 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 1019 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 935 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 795 of file rb.c.

Here is the caller graph for this function:

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

Return how many nodes there are in a tree.

Parameters

[in] tree to return node count for.

Definition at line 775 of file rb.c.

Here is the caller graph for this function:

◆ fr_rb_remove()

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

Remove an entry from the tree, without freeing the data.

Parameters

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

Returns

The user data we removed.
NULL if we couldn't find any matching data.

Definition at line 691 of file rb.c.

Here is the call graph for this function:

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

Replace old data with new data, OR insert if there is no old.

Parameters

[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.
[in]	tree	to insert data into.
[in]	data	to replace.

Returns

1 if data was replaced.
0 if data was inserted.
-1 if we failed to replace data

Definition at line 644 of file rb.c.

Here is the call graph for this function:

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