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 |
Implementation taken from NSD 3.0.5, adjusted for use in unbound (memory allocation, logging and so on).
#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))
with type is the type of a pointer to that struct.
Referenced by addr_tree_init_parents(), anchors_assemble_rrsets(), check_neg_invariants(), check_order(), checkzonetree(), find_in_subsub(), fwd_init_parents(), init_parents(), local_zone_out(), local_zones_print(), mesh_detach_subs(), mesh_get_mem(), mesh_log_list(), mesh_state_delete(), mesh_walk_supers(), name_tree_init_parents(), outnet_get_mem(), print_neg_cache(), printstats(), rrset_canonical(), search_cycle(), sum_subtree_inuse(), sum_zone_subtree_inuse(), sumtrees_all(), and sumtrees_inuse().
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).
rbtree_t* rbtree_create | ( | int(*)(const void *, const void *) | cmpf | ) |
Create new tree (malloced) with given key compare function.
cmpf,: | compare function (like strcmp) takes pointers to two keys. |
References rbtree_init().
Referenced by anchors_create(), forwards_apply_cfg(), insert_lock(), main(), outside_network_create(), and read_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.
rbtree,: | uninitialised memory for new tree, returned empty. | |
cmpf,: | compare function (like strcmp) takes pointers to two keys. |
References rbtree_t::cmp, rbtree_t::count, RBTREE_NULL, and rbtree_t::root.
Referenced by addr_tree_init(), local_zone_create(), local_zones_create(), mesh_create(), mesh_detach_subs(), mesh_state_create(), name_tree_init(), neg_setup_zone_node(), nsec3_hash_test(), nsec3_prove_nameerror(), nsec3_prove_nodata(), nsec3_prove_nods(), nsec3_prove_nxornodata(), nsec3_prove_wildcard(), rbtree_create(), rrset_canonical(), ub_ctx_create(), and val_neg_create().
Insert data into the tree.
rbtree,: | tree to insert to. | |
data,: | element to insert. |
References rbtree_t::cmp, rbnode_t::color, rbtree_t::count, fptr_ok, fptr_whitelist_rbtree_cmp(), rbnode_t::key, rbnode_t::left, rbnode_t::parent, rbtree_insert_fixup(), RBTREE_NULL, RED, rbnode_t::right, and rbtree_t::root.
Referenced by addr_tree_insert(), anchor_new_ta(), canonical_sort(), context_deserialize_new_query(), context_new(), forwards_insert(), get_codeline(), insert_lock(), local_zones_add_zone(), lz_enter_zone_dname(), lz_find_create_node(), mesh_attach_sub(), mesh_new_callback(), mesh_new_client(), mesh_state_attachment(), mesh_walk_supers(), name_tree_insert(), neg_create_zone(), neg_insert_data(), nsec3_hash_name(), read_create(), read_lock(), select_id(), and serviced_create().
Delete element from tree.
rbtree,: | tree to delete from. | |
key,: | key of item to delete. |
References BLACK, change_child_ptr(), change_parent_ptr(), rbnode_t::color, rbtree_t::count, rbnode_t::left, log_assert, rbnode_t::parent, rbtree_delete_fixup(), RBTREE_NULL, rbtree_search(), RED, rbnode_t::right, swap_int8(), and swap_np().
Referenced by add_bg_result(), del_empty_term(), libworker_bg_done_cb(), local_zones_del_zone(), mesh_detach_subs(), mesh_run(), mesh_state_delete(), neg_delete_data(), neg_delete_zone(), outnet_serviced_query(), outnet_serviced_query_stop(), outnet_udp_cb(), pending_delete(), process_answer_detail(), serviced_callbacks(), ub_cancel(), ub_resolve(), and ub_resolve_async().
Find key in tree.
Returns NULL if not found.
rbtree,: | tree to find in. | |
key,: | key that must match. |
References rbtree_find_less_equal().
Referenced by anchor_find(), context_deserialize_answer(), context_deserialize_cancel(), context_lookup_new_query(), find_id(), get_codeline(), local_data_answer(), local_zones_find(), lookup_serviced(), lz_exists(), lz_find_node(), mesh_area_find(), name_tree_find(), neg_find_data(), neg_find_zone(), nsec3_hash_name(), outnet_udp_cb(), rbtree_delete(), read_create(), read_lock(), and ub_cancel().
Find, but match does not have to be exact.
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. |
References rbtree_t::cmp, fptr_ok, fptr_whitelist_rbtree_cmp(), rbnode_t::key, rbnode_t::left, log_assert, RBTREE_NULL, rbnode_t::right, and rbtree_t::root.
Referenced by addr_tree_lookup(), anchors_lookup(), forwards_lookup(), local_zones_lookup(), name_tree_lookup(), neg_closest_data(), neg_closest_data_parent(), neg_closest_zone_parent(), and rbtree_search().
Returns first (smallest) node in the tree.
rbtree,: | tree |
References rbnode_t::left, RBTREE_NULL, and rbtree_t::root.
Referenced by remove_item(), and sumtrees_inuse().
Returns last (largest) node in the tree.
rbtree,: | tree |
References RBTREE_NULL, rbnode_t::right, and rbtree_t::root.
Referenced by neg_nsec3_getnc().
Returns next larger node in the tree.
rbtree,: | tree |
References rbnode_t::left, rbnode_t::parent, RBTREE_NULL, and rbnode_t::right.
Referenced by is_terminal(), remove_item(), set_kiddo_parents(), and wipeout().
Returns previous smaller node in the tree.
rbtree,: | tree |
References rbnode_t::left, rbnode_t::parent, RBTREE_NULL, and rbnode_t::right.
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.
tree,: | the tree | |
func,: | function called with element and user arg. The function must not alter the rbtree. | |
arg,: | user argument. |
References rbtree_t::root, and traverse_post().
Referenced by local_zones_delete(), mesh_delete(), neg_cache_delete(), neg_clear_zones(), outside_network_delete(), and ub_ctx_delete().