Red/black tree implementation. More...

#include <freeradius-devel/util/rb.h>
#include <freeradius-devel/util/strerror.h>

Include dependency graph for rb.c:

Macros
#define	DEF_RB_FLATTEN_FUNC(_order)

#define	NIL &sentinel /* all leafs are sentinels */

#define	RB_MAGIC (0x5ad09c42)

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

static fr_rb_node_t *	_node_heap_alloc (fr_rb_tree_t const tree, UNUSED void data)
	Allocate a new fr_rb_node_t on the heap. More...

static void	_node_heap_free (fr_rb_tree_t const tree, fr_rb_node_t node, bool free_data)
	Clear the fr_rb_node_t that was allocated as part of the data structure. More...

static fr_rb_node_t *	_node_inline_alloc (fr_rb_tree_t const tree, void data)
	Return the fr_rb_node_t that was allocated as part of the data structure. More...

static void	_node_inline_free (fr_rb_tree_t const tree, fr_rb_node_t node, bool free_data)
	Clear the fr_rb_node_t that was allocated as part of the data structure. More...

static int	_tree_free (fr_rb_tree_t *tree)
	Free the rbtree cleaning up any nodes. More...

	CC_NO_UBSAN (function)
	Find an element in the tree, returning the data, not the node. More...

static void	delete_fixup (fr_rb_tree_t tree, fr_rb_node_t x, fr_rb_node_t *parent)
	Maintain RED-BLACK tree balance after deleting node x. More...

static void	delete_internal (fr_rb_tree_t tree, fr_rb_node_t z, bool free_data)
	Delete an element (z) from the tree. More...

static fr_rb_node_t *	find_node (fr_rb_tree_t const 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...

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)

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)

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

static void	free_walker (fr_rb_tree_t tree, fr_rb_node_t x)
	Walks the tree to delete all nodes Does NOT re-balance it! More...

static void	insert_fixup (fr_rb_tree_t tree, fr_rb_node_t x)
	Maintain red-black tree balance after inserting node x. More...

static int	insert_node (fr_rb_node_t *existing, fr_rb_tree_t tree, void *data)
	Insert an element into the tree. More...

static void	node_data_free (fr_rb_tree_t const tree, fr_rb_node_t node)

static void	rotate_left (fr_rb_tree_t tree, fr_rb_node_t x)
	Rotate Node x to left. More...

static void	rotate_right (fr_rb_tree_t tree, fr_rb_node_t x)
	Rotate Node x to right. More...

Variables
static fr_rb_node_t	sentinel = { NIL, NIL, NULL, NULL, BLACK, false }

Detailed Description

Red/black tree implementation.

Copyright: 2021 Arran Cudbard-Bell (a.cud.nosp@m.bard.nosp@m.b@fre.nosp@m.erad.nosp@m.ius.o.nosp@m.rg); 2004,2006 The FreeRADIUS server project

Definition in file rb.c.

Macro Definition Documentation

◆ DEF_RB_FLATTEN_FUNC

#define DEF_RB_FLATTEN_FUNC ( _order )

Value:

int fr_rb_flatten_##_order(TALLOC_CTX *ctx, void **out[], fr_rb_tree_t *tree) \
{ \
        uint32_t num = fr_rb_num_elements(tree), i; \
        fr_rb_iter_##_order##_t iter; \
        void *item, **list; \
        if (unlikely(!(list = talloc_array(ctx, void *, num)))) return -1; \
        for (item = fr_rb_iter_init_##_order(&iter, tree), i = 0; \
             item; \
             item = fr_rb_iter_next_##_order(&iter), i++) list[i] = item; \
        *out = list; \
        return 0; \
}

Definition at line 1071 of file rb.c.

◆ NIL

#define NIL &sentinel /* all leafs are sentinels */

Definition at line 29 of file rb.c.

◆ RB_MAGIC

#define RB_MAGIC (0x5ad09c42)

Definition at line 33 of file rb.c.

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:

◆ _node_heap_alloc()

static fr_rb_node_t* _node_heap_alloc	(	fr_rb_tree_t const *	tree,
		UNUSED void *	data
	)

static

Allocate a new fr_rb_node_t on the heap.

Definition at line 66 of file rb.c.

Here is the caller graph for this function:

◆ _node_heap_free()

static void _node_heap_free	(	fr_rb_tree_t const *	tree,
		fr_rb_node_t *	node,
		bool	free_data
	)

static

Clear the fr_rb_node_t that was allocated as part of the data structure.

Definition at line 73 of file rb.c.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ _node_inline_alloc()

static fr_rb_node_t* _node_inline_alloc	(	fr_rb_tree_t const *	tree,
		void *	data
	)

static

Return the fr_rb_node_t that was allocated as part of the data structure.

Definition at line 48 of file rb.c.

Here is the caller graph for this function:

◆ _node_inline_free()

static void _node_inline_free	(	fr_rb_tree_t const *	tree,
		fr_rb_node_t *	node,
		bool	free_data
	)

static

Clear the fr_rb_node_t that was allocated as part of the data structure.

Definition at line 55 of file rb.c.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ _tree_free()

static int _tree_free ( fr_rb_tree_t * tree )

static

Free the rbtree cleaning up any nodes.

Walk the tree deleting nodes, then free any children of the tree.

Note: If the destructor of a talloc descendent needs to lookup any information in the tree, it will be unavailable at the point of freeing. We could fix this by introducing a pre-free callback which gets called before any of the nodes are deleted.

Parameters

[in] tree to tree.

Returns

0 if tree was freed.
-1 if tree is already being freed.

Definition at line 104 of file rb.c.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ CC_NO_UBSAN()

CC_NO_UBSAN ( function )

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

Return how many nodes there are in a tree.

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

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

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

Insert data into a tree.

Parameters

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

Returns

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

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.

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

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.

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.

Parameters

[in] tree to return node count for.

Definition at line 576 of file rb.c.

Here is the call graph for this function:

◆ delete_fixup()

static void delete_fixup	(	fr_rb_tree_t *	tree,
		fr_rb_node_t *	x,
		fr_rb_node_t *	parent
	)

static

Maintain RED-BLACK tree balance after deleting node x.

Definition at line 407 of file rb.c.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ delete_internal()

static void delete_internal	(	fr_rb_tree_t *	tree,
		fr_rb_node_t *	z,
		bool	free_data
	)

static

Delete an element (z) from the tree.

Definition at line 472 of file rb.c.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ find_node()

static fr_rb_node_t* find_node	(	fr_rb_tree_t const *	tree,
		void const *	data
	)

inlinestatic

Definition at line 547 of file rb.c.

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

◆ free_walker()

static void free_walker	(	fr_rb_tree_t *	tree,
		fr_rb_node_t *	x
	)

static

Walks the tree to delete all nodes Does NOT re-balance it!

Definition at line 82 of file rb.c.

Here is the caller graph for this function:

◆ insert_fixup()

static void insert_fixup	(	fr_rb_tree_t *	tree,
		fr_rb_node_t *	x
	)

inlinestatic

Maintain red-black tree balance after inserting node x.

Definition at line 281 of file rb.c.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ insert_node()

static int insert_node	(	fr_rb_node_t **	existing,
		fr_rb_tree_t *	tree,
		void *	data
	)

static

Insert an element into the tree.

Parameters

[out]	existing	if a node exists, and existing is not NULL this will be populated with the node.
[in]	tree	to search in.
[in]	data	to search for.

Returns

1 on existing (with existing populated).
0 on success.
-1 on failure.

Definition at line 345 of file rb.c.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ node_data_free()

static void node_data_free	(	fr_rb_tree_t const *	tree,
		fr_rb_node_t *	node
	)

inlinestatic

Definition at line 38 of file rb.c.

Here is the caller graph for this function:

◆ rotate_left()

static void rotate_left	(	fr_rb_tree_t *	tree,
		fr_rb_node_t *	x
	)

inlinestatic

Rotate Node x to left.

Definition at line 224 of file rb.c.

Here is the caller graph for this function:

◆ rotate_right()

static void rotate_right	(	fr_rb_tree_t *	tree,
		fr_rb_node_t *	x
	)

inlinestatic

Rotate Node x to right.

Definition at line 253 of file rb.c.

Here is the caller graph for this function:

Variable Documentation

◆ sentinel

fr_rb_node_t sentinel = { NIL, NIL, NULL, NULL, BLACK, false }

static

Definition at line 30 of file rb.c.

Macros

Functions

Variables

Detailed Description

Macro Definition Documentation

◆ DEF_RB_FLATTEN_FUNC

◆ NIL

◆ RB_MAGIC

Function Documentation

◆ _fr_rb_alloc()

◆ _fr_rb_init()

◆ _node_heap_alloc()

◆ _node_heap_free()

◆ _node_inline_alloc()

◆ _node_inline_free()

◆ _tree_free()

◆ CC_NO_UBSAN()

◆ delete_fixup()

◆ delete_internal()

◆ find_node()

◆ fr_rb_delete_by_inline_node()

◆ fr_rb_find_or_insert()

◆ fr_rb_first()

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

◆ free_walker()

◆ insert_fixup()

◆ insert_node()

◆ node_data_free()

◆ rotate_left()

◆ rotate_right()

Variable Documentation

◆ sentinel