rb.c File Reference

Red/black tree implementation. More...

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

Include dependency graph for rb.c:

Go to the source code of this file.

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.
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.
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.
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.
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.
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.
static int	_tree_free (fr_rb_tree_t *tree)
	Free the rbtree cleaning up any nodes.
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.
static void	delete_internal (fr_rb_tree_t *tree, fr_rb_node_t *z, bool free_data)
	Delete an element (z) from the tree.
static fr_rb_node_t *	find_node (fr_rb_tree_t const *tree, void const *data)
bool	fr_rb_delete (fr_rb_tree_t *tree, void const *data)
	Remove node and free data (if a free function was specified)
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)
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.
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.
void *	fr_rb_first (fr_rb_tree_t *tree)
bool	fr_rb_insert (fr_rb_tree_t *tree, void const *data)
	Insert data into a tree.
void	fr_rb_iter_delete_inorder (fr_rb_iter_inorder_t *iter)
	Remove the current node from the tree.
void *	fr_rb_iter_init_inorder (fr_rb_iter_inorder_t *iter, fr_rb_tree_t *tree)
	Initialise an in-order iterator.
void *	fr_rb_iter_init_postorder (fr_rb_iter_postorder_t *iter, fr_rb_tree_t *tree)
	Initialise a post-order iterator.
void *	fr_rb_iter_init_preorder (fr_rb_iter_preorder_t *iter, fr_rb_tree_t *tree)
	Initialise a pre-order iterator.
void *	fr_rb_iter_next_inorder (fr_rb_iter_inorder_t *iter)
	Return the next node.
void *	fr_rb_iter_next_postorder (fr_rb_iter_postorder_t *iter)
	Return the next node.
void *	fr_rb_iter_next_preorder (fr_rb_iter_preorder_t *iter)
	Return the next node.
void *	fr_rb_last (fr_rb_tree_t *tree)
uint32_t	fr_rb_num_elements (fr_rb_tree_t *tree)
	Return how many nodes there are in a tree.
void *	fr_rb_remove (fr_rb_tree_t *tree, void const *data)
	Remove an entry from the tree, without freeing the 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.
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.
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!
static void	insert_fixup (fr_rb_tree_t *tree, fr_rb_node_t *x)
	Maintain red-black tree balance after inserting node x.
static int	insert_node (fr_rb_node_t **existing, fr_rb_tree_t *tree, void *data)
	Insert an element into the tree.
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.
static void	rotate_right (fr_rb_tree_t *tree, fr_rb_node_t *x)
	Rotate Node x to right.

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:

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

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

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 577 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 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_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 626 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 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_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 781 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 695 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 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
	)

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 647 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 call graph for this function:

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.