Implementation of a redblack tree. More...

Macros
#define	BLACK 0
	Node colour black. More...

#define	RED 1
	Node colour red. More...

Functions
ldns_rbtree_t *	ldns_rbtree_create (int(cmpf)(const void , const void *))
	Create new tree (malloced) with given key compare function. More...

void	ldns_rbtree_init (ldns_rbtree_t rbtree, int(cmpf)(const void , const void ))
	Init a new tree (malloced by caller) with given key compare function. More...

void	ldns_rbtree_free (ldns_rbtree_t *rbtree)
	Free the complete tree (but not its keys) More...

void	ldns_rbtree_insert_vref (ldns_rbnode_t data, void rbtree)
	Insert data into the tree (reversed arguments, for use as callback) More...

ldns_rbnode_t *	ldns_rbtree_insert (ldns_rbtree_t rbtree, ldns_rbnode_t data)
	Insert data into the tree. More...

ldns_rbnode_t *	ldns_rbtree_search (ldns_rbtree_t rbtree, const void key)
	Find key in tree. More...

ldns_rbnode_t *	ldns_rbtree_delete (ldns_rbtree_t rbtree, const void key)
	Delete element from tree. More...

int	ldns_rbtree_find_less_equal (ldns_rbtree_t rbtree, const void key, ldns_rbnode_t **result)
	Find, but match does not have to be exact. More...

ldns_rbnode_t *	ldns_rbtree_first (const ldns_rbtree_t *rbtree)
	Returns first (smallest) node in the tree. More...

ldns_rbnode_t *	ldns_rbtree_last (const ldns_rbtree_t *rbtree)
	Returns last (largest) node in the tree. More...

ldns_rbnode_t *	ldns_rbtree_next (ldns_rbnode_t *node)
	Returns next larger node in the tree. More...

ldns_rbnode_t *	ldns_rbtree_previous (ldns_rbnode_t *node)
	Returns previous smaller node in the tree. More...

ldns_rbtree_t *	ldns_rbtree_split (ldns_rbtree_t *tree, size_t elements)
	split off elements number of elements from the start of the name tree and return a new tree More...

void	ldns_rbtree_join (ldns_rbtree_t tree1, ldns_rbtree_t tree2)
	add all node from the second tree to the first (removing them from the second), and fix up nsec(3)s if present More...

void	ldns_traverse_postorder (ldns_rbtree_t tree, void(func)(ldns_rbnode_t , void ), void *arg)
	Call function for all elements in the redblack tree, such that leaf elements are called before parent elements. More...

Variables
ldns_rbnode_t	ldns_rbtree_null_node
	the NULL node, global alloc More...

Detailed Description

Implementation of a redblack tree.

Definition in file rbtree.c.

Macro Definition Documentation

◆ BLACK

#define BLACK 0

Node colour black.

Definition at line 50 of file rbtree.c.

◆ RED

#define RED 1

Node colour red.

Definition at line 52 of file rbtree.c.

Function Documentation

◆ ldns_rbtree_create()

ldns_rbtree_t* ldns_rbtree_create ( int(*)(const void *, const void *) cmpf )

Create new tree (malloced) with given key compare function.

Parameters

cmpf	compare function (like strcmp) takes pointers to two keys.

Returns: : new tree, empty.

Definition at line 80 of file rbtree.c.

References LDNS_MALLOC, and ldns_rbtree_init().

◆ ldns_rbtree_init()

void ldns_rbtree_init	(	ldns_rbtree_t *	rbtree,
		int()(const void , const void *)	cmpf
	)

Init a new tree (malloced by caller) with given key compare function.

Parameters

rbtree	uninitialised memory for new tree, returned empty.
cmpf	compare function (like strcmp) takes pointers to two keys.

Definition at line 97 of file rbtree.c.

References ldns_rbtree_t::cmp, ldns_rbtree_t::count, LDNS_RBTREE_NULL, and ldns_rbtree_t::root.

◆ ldns_rbtree_free()

void ldns_rbtree_free ( ldns_rbtree_t * rbtree )

Free the complete tree (but not its keys)

Parameters

rbtree The tree to free

Definition at line 106 of file rbtree.c.

References LDNS_FREE.

◆ ldns_rbtree_insert_vref()

void ldns_rbtree_insert_vref	(	ldns_rbnode_t *	data,
		void *	rbtree
	)

Insert data into the tree (reversed arguments, for use as callback)

Parameters

[in]	data	element to insert
[out]	rbtree	tree to insert in to

Returns: data ptr or NULL if key is already present

Definition at line 229 of file rbtree.c.

References ldns_rbtree_insert().

◆ ldns_rbtree_insert()

ldns_rbnode_t* ldns_rbtree_insert	(	ldns_rbtree_t *	rbtree,
		ldns_rbnode_t *	data
	)

Insert data into the tree.

Parameters

rbtree	tree to insert to.
data	element to insert.

Returns: : data ptr or NULL if key already present.

Definition at line 242 of file rbtree.c.

References ldns_rbtree_t::cmp, ldns_rbnode_t::color, ldns_rbtree_t::count, ldns_rbnode_t::key, LDNS_RBTREE_NULL, ldns_rbnode_t::left, ldns_rbnode_t::parent, RED, ldns_rbnode_t::right, and ldns_rbtree_t::root.

◆ ldns_rbtree_search()

ldns_rbnode_t* ldns_rbtree_search	(	ldns_rbtree_t *	rbtree,
		const void *	key
	)

Find key in tree.

Returns NULL if not found.

Parameters

rbtree	tree to find in.
key	key that must match.

Returns: : node that fits or NULL.

Definition at line 294 of file rbtree.c.

References ldns_rbtree_find_less_equal().

◆ ldns_rbtree_delete()

ldns_rbnode_t* ldns_rbtree_delete	(	ldns_rbtree_t *	rbtree,
		const void *	key
	)

Delete element from tree.

Parameters

rbtree	tree to delete from.
key	key of item to delete.

Returns: : node that is now unlinked from the tree. User to delete it. returns 0 if node not present

Definition at line 336 of file rbtree.c.

References ldns_rbtree_t::count, LDNS_RBTREE_NULL, ldns_rbtree_search(), ldns_rbnode_t::left, and ldns_rbnode_t::right.

◆ ldns_rbtree_find_less_equal()

int ldns_rbtree_find_less_equal	(	ldns_rbtree_t *	rbtree,
		const void *	key,
		ldns_rbnode_t **	result
	)

Find, but match does not have to be exact.

Parameters

	rbtree	tree to find in.
	key	key to find position of.
[out]	result	set to the exact node if present, otherwise to element that precedes the position of key in the tree. NULL if no smaller element.

Returns: : true if exact match in result. Else result points to <= element, or NULL if key is smaller than the smallest key.

Definition at line 514 of file rbtree.c.

References ldns_rbtree_t::cmp, ldns_rbnode_t::key, LDNS_RBTREE_NULL, ldns_rbnode_t::left, ldns_rbnode_t::right, and ldns_rbtree_t::root.

◆ ldns_rbtree_first()

ldns_rbnode_t* ldns_rbtree_first ( const ldns_rbtree_t * rbtree )

Returns first (smallest) node in the tree.

Parameters

rbtree tree

Returns: : smallest element or NULL if tree empty.

Definition at line 548 of file rbtree.c.

References LDNS_RBTREE_NULL, ldns_rbnode_t::left, and ldns_rbtree_t::root.

◆ ldns_rbtree_last()

ldns_rbnode_t* ldns_rbtree_last ( const ldns_rbtree_t * rbtree )

Returns last (largest) node in the tree.

Parameters

rbtree tree

Returns: : largest element or NULL if tree empty.

Definition at line 559 of file rbtree.c.

References LDNS_RBTREE_NULL, ldns_rbnode_t::right, and ldns_rbtree_t::root.

◆ ldns_rbtree_next()

ldns_rbnode_t* ldns_rbtree_next ( ldns_rbnode_t * rbtree )

Returns next larger node in the tree.

Parameters

rbtree tree

Returns: : next larger element or NULL if no larger in tree.

Definition at line 574 of file rbtree.c.

References LDNS_RBTREE_NULL, ldns_rbnode_t::left, ldns_rbnode_t::parent, and ldns_rbnode_t::right.

◆ ldns_rbtree_previous()

ldns_rbnode_t* ldns_rbtree_previous ( ldns_rbnode_t * rbtree )

Returns previous smaller node in the tree.

Parameters

rbtree tree

Returns: : previous smaller element or NULL if no previous in tree.

Definition at line 595 of file rbtree.c.

References LDNS_RBTREE_NULL, ldns_rbnode_t::left, ldns_rbnode_t::parent, and ldns_rbnode_t::right.

◆ ldns_rbtree_split()

ldns_rbtree_t* ldns_rbtree_split	(	ldns_rbtree_t *	tree,
		size_t	elements
	)

split off elements number of elements from the start of the name tree and return a new tree

split off 'elements' number of elements from the start of the name tree and return a new tree containing those elements

Definition at line 620 of file rbtree.c.

References ldns_rbtree_t::cmp, ldns_rbnode_t::key, ldns_rbtree_create(), ldns_rbtree_delete(), ldns_rbtree_first(), ldns_rbtree_insert(), and LDNS_RBTREE_NULL.

◆ ldns_rbtree_join()

void ldns_rbtree_join	(	ldns_rbtree_t *	tree1,
		ldns_rbtree_t *	tree2
	)

add all node from the second tree to the first (removing them from the second), and fix up nsec(3)s if present

Definition at line 646 of file rbtree.c.

References ldns_rbtree_insert_vref(), and ldns_traverse_postorder().

◆ ldns_traverse_postorder()

void ldns_traverse_postorder	(	ldns_rbtree_t *	tree,
		void()(ldns_rbnode_t , void *)	func,
		void *	arg
	)

Call function for all elements in the redblack tree, such that leaf elements are called before parent elements.

So that all elements can be safely free()d. Note that your function must not remove the nodes from the tree. Since that may trigger rebalances of the rbtree.

Parameters

tree	the tree
func	function called with element and user arg. The function must not alter the rbtree.
arg	user argument.

Definition at line 666 of file rbtree.c.

Variable Documentation

◆ ldns_rbtree_null_node

ldns_rbnode_t ldns_rbtree_null_node

Initial value:

= {
         &ldns_rbtree_null_node ,       
         &ldns_rbtree_null_node ,       
         &ldns_rbtree_null_node ,       
        NULL,                   
        NULL,               
         0                   
}

the NULL node, global alloc

the global empty node

Definition at line 55 of file rbtree.c.

Macros

Functions

Variables

Detailed Description

Macro Definition Documentation

◆ BLACK

◆ RED

Function Documentation

◆ ldns_rbtree_create()

◆ ldns_rbtree_init()

◆ ldns_rbtree_free()

◆ ldns_rbtree_insert_vref()

◆ ldns_rbtree_insert()

◆ ldns_rbtree_search()

◆ ldns_rbtree_delete()

◆ ldns_rbtree_find_less_equal()

◆ ldns_rbtree_first()

◆ ldns_rbtree_last()

◆ ldns_rbtree_next()

◆ ldns_rbtree_previous()

◆ ldns_rbtree_split()

◆ ldns_rbtree_join()

◆ ldns_traverse_postorder()

Variable Documentation

◆ ldns_rbtree_null_node