Data Structures | Macros | Typedefs | Functions | Variables
rbtree.h File Reference

Red black tree. More...

Data Structures

struct  rbnode_t
 The rbnode_t struct definition. More...
 
struct  rbtree_t
 definition for tree struct More...
 

Macros

#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. More...
 

Typedefs

typedef struct rbnode_t rbnode_t
 This structure must be the first member of the data structure in the rbtree. More...
 
typedef struct rbtree_t rbtree_t
 An entire red black tree.
 

Functions

rbtree_trbtree_create (int(*cmpf)(const void *, const void *))
 Create new tree (malloced) with given key compare function. More...
 
void rbtree_init (rbtree_t *rbtree, int(*cmpf)(const void *, const void *))
 Init a new tree (malloced by caller) with given key compare function. More...
 
rbnode_trbtree_insert (rbtree_t *rbtree, rbnode_t *data)
 Insert data into the tree. More...
 
rbnode_trbtree_delete (rbtree_t *rbtree, const void *key)
 Delete element from tree. More...
 
rbnode_trbtree_search (rbtree_t *rbtree, const void *key)
 Find key in tree. More...
 
int rbtree_find_less_equal (rbtree_t *rbtree, const void *key, rbnode_t **result)
 Find, but match does not have to be exact. More...
 
rbnode_trbtree_first (rbtree_t *rbtree)
 Returns first (smallest) node in the tree. More...
 
rbnode_trbtree_last (rbtree_t *rbtree)
 Returns last (largest) node in the tree. More...
 
rbnode_trbtree_next (rbnode_t *rbtree)
 Returns next larger node in the tree. More...
 
rbnode_trbtree_previous (rbnode_t *rbtree)
 Returns previous smaller node in the tree. More...
 
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. More...
 

Variables

rbnode_t rbtree_null_node
 the global empty node More...
 

Detailed Description

Red black tree.

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

Macro Definition 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))
rbnode_t * rbtree_first(rbtree_t *rbtree)
Returns first (smallest) node in the tree.
Definition: rbtree.c:544
#define RBTREE_NULL
The nullpointer, points to empty node.
Definition: rbtree.h:69
rbnode_t * rbtree_next(rbnode_t *rbtree)
Returns next larger node in the tree.
Definition: rbtree.c:566
The rbnode_t struct definition.
Definition: rbtree.h:55

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 addr_tree_init_parents(), anchors_get_mem(), anchors_init_parents_locked(), autr_debug_print(), check_neg_invariants(), check_order(), checkzonetree(), do_dump_requestlist(), do_list_forwards(), do_list_local_data(), do_list_local_zones(), do_list_stubs(), find_in_subsub(), forwards_get_mem(), fwd_init_parents(), get_mesh_status(), hints_get_mem(), init_parents(), local_zone_out(), local_zones_print(), macro_print_debug(), 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().

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
cmpfcompare function (like strcmp) takes pointers to two keys.
Returns
: new tree, empty.

References rbtree_init().

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

void rbtree_init ( rbtree_t rbtree,
int(*)(const void *, const void *)  cmpf 
)
rbnode_t* rbtree_insert ( rbtree_t rbtree,
rbnode_t data 
)
rbnode_t* rbtree_delete ( rbtree_t rbtree,
const void *  key 
)
rbnode_t* rbtree_search ( rbtree_t rbtree,
const void *  key 
)
int rbtree_find_less_equal ( rbtree_t rbtree,
const void *  key,
rbnode_t **  result 
)

Find, but match does not have to be exact.

Parameters
rbtreetree to find in.
keykey to find position of.
resultset 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 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(), forwards_next_root(), local_zones_lookup(), name_tree_lookup(), name_tree_next_root(), neg_closest_data(), neg_closest_data_parent(), neg_closest_zone_parent(), and rbtree_search().

rbnode_t* rbtree_first ( rbtree_t rbtree)

Returns first (smallest) node in the tree.

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

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

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

rbnode_t* rbtree_last ( rbtree_t rbtree)

Returns last (largest) node in the tree.

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

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

Referenced by neg_nsec3_getnc().

rbnode_t* rbtree_next ( rbnode_t rbtree)

Returns next larger node in the tree.

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

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

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

rbnode_t* rbtree_previous ( rbnode_t rbtree)

Returns previous smaller node in the tree.

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

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

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
treethe tree
funcfunction called with element and user arg. The function must not alter the rbtree.
arguser argument.

References rbtree_t::root, and traverse_post().

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

Variable Documentation

rbnode_t rbtree_null_node

the global empty node

the global empty node