Red black tree. More...

Data Structures
struct	rbnode_t
	The rbnode_t struct definition. More...
struct	rbtree_t
	definition for tree struct More...
Defines
#define	RBTREE_NULL &rbtree_null_node
	The nullpointer, points to empty node.
#define	RBTREE_FOR(node, type, rbtree)
	Call with node=variable of struct* with rbnode_t as first element.
Typedefs
typedef struct rbnode_t	rbnode_t
	This structure must be the first member of the data structure in the rbtree.
typedef struct rbtree_t	rbtree_t
	An entire red black tree.
Functions
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_delete (rbtree_t rbtree, const void key)
	Delete element from tree.
rbnode_t *	rbtree_search (rbtree_t rbtree, const void key)
	Find key in 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 *rbtree)
	Returns next larger node in the tree.
rbnode_t *	rbtree_previous (rbnode_t *rbtree)
	Returns previous smaller node in the tree.
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 global empty node

Detailed Description

Red black tree.

Implementation taken from NSD 3.0.5, adjusted for use in unbound (memory allocation, logging and so on).

Define Documentation

#define RBTREE_FOR	(	node,
		type,
		rbtree
	)

Value:

for(node=(type)rbtree_first(rbtree); \
                (rbnode_t*)node != RBTREE_NULL; \
                node = (type)rbtree_next((rbnode_t*)node))

Call with node=variable of struct* with rbnode_t as first element.

with type is the type of a pointer to that struct.

Referenced by get_mesh_status(), do_dump_requestlist(), do_list_forwards(), do_list_stubs(), do_list_local_zones(), do_list_local_data(), fwd_init_parents(), init_parents(), local_zone_out(), local_zones_print(), mesh_state_delete(), find_in_subsub(), mesh_detach_subs(), mesh_walk_supers(), mesh_log_list(), mesh_get_mem(), outnet_get_mem(), search_cycle(), check_order(), printstats(), macro_print_debug(), print_neg_cache(), sumtrees_all(), sumtrees_inuse(), sum_subtree_inuse(), sum_zone_subtree_inuse(), checkzonetree(), check_neg_invariants(), addr_tree_init_parents(), name_tree_init_parents(), autr_debug_print(), anchors_init_parents_locked(), and rrset_canonical().

Typedef Documentation

typedef struct rbnode_t rbnode_t

This structure must be the first member of the data structure in the rbtree.

This allows easy casting between an rbnode_t and the user data (poor man's inheritance).

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

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

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

Data Structures

Defines

Typedefs

Functions

Variables

Detailed Description

Define Documentation

Typedef Documentation

Function Documentation