Implementation of a redblack tree. More...

#include "config.h"
#include "log.h"
#include "fptr_wlist.h"
#include "util/rbtree.h"

Defines
#define	BLACK 0
	Node colour black.
#define	RED 1
	Node colour red.
Functions
static void	rbtree_rotate_left (rbtree_t rbtree, rbnode_t node)
	rotate subtree left (to preserve redblack property)
static void	rbtree_rotate_right (rbtree_t rbtree, rbnode_t node)
	rotate subtree right (to preserve redblack property)
static void	rbtree_insert_fixup (rbtree_t rbtree, rbnode_t node)
	Fixup node colours when insert happened.
static void	rbtree_delete_fixup (rbtree_t rbtree, rbnode_t child, rbnode_t *child_parent)
	Fixup node colours when delete happened.
rbtree_t *	rbtree_create (int(cmpf)(const void , const void *))
	Create new tree (malloced) with given key compare function.
void	rbtree_init (rbtree_t rbtree, int(cmpf)(const void , const void ))
	Init a new tree (malloced by caller) with given key compare function.
rbnode_t *	rbtree_insert (rbtree_t rbtree, rbnode_t data)
	Insert data into the tree.
rbnode_t *	rbtree_search (rbtree_t rbtree, const void key)
	Find key in tree.
static void	swap_int8 (uint8_t x, uint8_t y)
	helpers for delete: swap node colours
static void	swap_np (rbnode_t x, rbnode_t y)
	helpers for delete: swap node pointers
static void	change_parent_ptr (rbtree_t rbtree, rbnode_t parent, rbnode_t old, rbnode_t new)
	Update parent pointers of child trees of 'parent'.
static void	change_child_ptr (rbnode_t child, rbnode_t old, rbnode_t *new)
	Update parent pointer of a node 'child'.
rbnode_t *	rbtree_delete (rbtree_t rbtree, const void key)
	Delete element from tree.
int	rbtree_find_less_equal (rbtree_t rbtree, const void key, rbnode_t **result)
	Find, but match does not have to be exact.
rbnode_t *	rbtree_first (rbtree_t *rbtree)
	Returns first (smallest) node in the tree.
rbnode_t *	rbtree_last (rbtree_t *rbtree)
	Returns last (largest) node in the tree.
rbnode_t *	rbtree_next (rbnode_t *node)
	Returns next larger node in the tree.
rbnode_t *	rbtree_previous (rbnode_t *node)
	Returns previous smaller node in the tree.
static void	traverse_post (void(func)(rbnode_t , void ), void arg, rbnode_t *node)
	recursive descent traverse
void	traverse_postorder (rbtree_t tree, void(func)(rbnode_t , void ), void *arg)
	Call function for all elements in the redblack tree, such that leaf elements are called before parent elements.
Variables
rbnode_t	rbtree_null_node
	the NULL node, global alloc

Detailed Description

Implementation of a redblack tree.

Function Documentation

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

References rbtree_init().

Referenced by forwards_apply_cfg(), outside_network_create(), read_create(), insert_lock(), main(), macro_store_create(), event_init(), and anchors_create().

void rbtree_init	(	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.

References rbtree_t::root, RBTREE_NULL, rbtree_t::count, and rbtree_t::cmp.

Referenced by ub_ctx_create(), local_zones_create(), local_zone_create(), mesh_create(), mesh_delete_all(), mesh_state_create(), mesh_detach_subs(), nsec3_hash_test(), rbtree_create(), name_tree_init(), addr_tree_init(), autr_global_create(), val_neg_create(), neg_setup_zone_node(), nsec3_prove_nameerror(), nsec3_prove_nodata(), nsec3_prove_wildcard(), nsec3_prove_nods(), nsec3_prove_nxornodata(), and rrset_canonical().

rbnode_t* rbtree_insert	(	rbtree_t *	rbtree,
		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.

References rbtree_t::root, RBTREE_NULL, fptr_ok, fptr_whitelist_rbtree_cmp(), rbtree_t::cmp, rbnode_t::key, rbnode_t::left, rbnode_t::right, rbnode_t::parent, rbnode_t::color, RED, rbtree_t::count, and rbtree_insert_fixup().

Referenced by forwards_insert_data(), context_new(), context_deserialize_new_query(), lz_enter_zone_dname(), lz_find_create_node(), local_zones_add_zone(), mesh_new_client(), mesh_new_callback(), mesh_new_prefetch(), mesh_attach_sub(), mesh_state_attachment(), mesh_walk_supers(), select_id(), serviced_create(), read_create(), insert_lock(), read_lock(), get_codeline(), macro_assign(), name_tree_insert(), addr_tree_insert(), autr_tp_create(), parse_var_line(), set_next_probe(), todo_probe(), anchor_new_ta(), neg_create_zone(), neg_insert_data(), nsec3_hash_name(), and canonical_sort().

rbnode_t* rbtree_search	(	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.

References rbtree_find_less_equal().

Referenced by need_hole_insert(), forwards_delete_zone(), find_id(), context_lookup_new_query(), context_deserialize_answer(), context_deserialize_cancel(), ub_cancel(), lz_find_node(), lz_exists(), local_zones_find(), local_data_answer(), mesh_area_find(), outnet_udp_cb(), lookup_serviced(), read_create(), read_lock(), get_codeline(), macro_getvar(), rbtree_delete(), name_tree_find(), set_next_probe(), anchor_find(), neg_find_zone(), neg_find_data(), and nsec3_hash_name().

rbnode_t* rbtree_delete	(	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

References rbtree_search(), rbtree_t::count, rbnode_t::left, RBTREE_NULL, rbnode_t::right, swap_int8(), rbnode_t::color, change_parent_ptr(), rbnode_t::parent, change_child_ptr(), swap_np(), log_assert, RED, BLACK, and rbtree_delete_fixup().

Referenced by forwards_delete_zone(), process_answer_detail(), ub_resolve(), ub_resolve_async(), ub_cancel(), add_bg_result(), libworker_bg_done_cb(), local_zones_del_zone(), del_empty_term(), mesh_state_delete(), mesh_detach_subs(), mesh_run(), outnet_udp_cb(), pending_delete(), serviced_callbacks(), outnet_serviced_query(), outnet_serviced_query_stop(), handle_timeouts(), autr_tp_create(), parse_var_line(), set_next_probe(), autr_tp_remove(), todo_probe(), anchors_assemble_rrsets(), neg_delete_zone(), and neg_delete_data().

int rbtree_find_less_equal	(	rbtree_t *	rbtree,
		const void *	key,
		rbnode_t **	result
	)

Find, but match does not have to be exact.

Parameters:

rbtree,:	tree to find in.
key,:	key to find position of.
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.

References log_assert, rbtree_t::root, fptr_ok, fptr_whitelist_rbtree_cmp(), rbtree_t::cmp, RBTREE_NULL, rbnode_t::key, rbnode_t::left, and rbnode_t::right.

Referenced by forwards_lookup(), forwards_next_root(), local_zones_lookup(), rbtree_search(), name_tree_lookup(), addr_tree_lookup(), name_tree_next_root(), anchors_lookup(), neg_closest_zone_parent(), neg_closest_data_parent(), and neg_closest_data().

rbnode_t* rbtree_first ( rbtree_t * rbtree )

Returns first (smallest) node in the tree.

Parameters:

rbtree,: tree

Returns:: : smallest element or NULL if tree empty.

References rbtree_t::root, rbnode_t::left, and RBTREE_NULL.

Referenced by forwards_next_root(), remove_item(), sumtrees_inuse(), handle_timeouts(), name_tree_next_root(), wait_probe_time(), todo_probe(), and anchors_assemble_rrsets().

rbnode_t* rbtree_last ( rbtree_t * rbtree )

Returns last (largest) node in the tree.

Parameters:

rbtree,: tree

Returns:: : largest element or NULL if tree empty.

References rbtree_t::root, rbnode_t::right, and RBTREE_NULL.

Referenced by neg_nsec3_getnc().

rbnode_t* rbtree_next ( rbnode_t * rbtree )

Returns next larger node in the tree.

Parameters:

rbtree,: tree

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

References rbnode_t::right, RBTREE_NULL, rbnode_t::left, and rbnode_t::parent.

Referenced by forwards_next_root(), set_kiddo_parents(), is_terminal(), remove_item(), name_tree_next_root(), anchors_assemble_rrsets(), and wipeout().

rbnode_t* rbtree_previous ( rbnode_t * rbtree )

Returns previous smaller node in the tree.

Parameters:

rbtree,: tree

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

References rbnode_t::left, RBTREE_NULL, rbnode_t::right, and rbnode_t::parent.

void traverse_postorder	(	rbtree_t *	tree,
		void()(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.

References traverse_post(), and rbtree_t::root.

Referenced by ub_ctx_delete(), local_zones_delete(), outside_network_delete(), macro_store_delete(), anchors_delete(), neg_clear_zones(), and neg_cache_delete().

Variable Documentation

rbnode_t rbtree_null_node

Initial value:

 {
        RBTREE_NULL,            
        RBTREE_NULL,            
        RBTREE_NULL,            
        NULL,                   
        BLACK                   
}

the NULL node, global alloc

the global empty node

Defines

Functions

Variables

Detailed Description

Function Documentation

Variable Documentation