rbtree.c File Reference

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_trbtree_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_trbtree_insert (rbtree_t *rbtree, rbnode_t *data)
 Insert data into the tree.
rbnode_trbtree_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_trbtree_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_trbtree_first (rbtree_t *rbtree)
 Returns first (smallest) node in the tree.
rbnode_trbtree_last (rbtree_t *rbtree)
 Returns last (largest) node in the tree.
rbnode_trbtree_next (rbnode_t *node)
 Returns next larger node in the tree.
rbnode_trbtree_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 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.

Parameters:
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_delete_all(), 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().

rbnode_t* rbtree_insert ( rbtree_t rbtree,
rbnode_t data 
)

rbnode_t* rbtree_search ( rbtree_t rbtree,
const void *  key 
)

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

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 rbnode_t::left, RBTREE_NULL, and rbtree_t::root.

Referenced by anchors_assemble_rrsets(), remove_item(), and sumtrees_inuse().

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_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:
rbtree,: tree
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(), is_terminal(), remove_item(), set_kiddo_parents(), 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, 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:
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(), neg_cache_delete(), neg_clear_zones(), outside_network_delete(), and ub_ctx_delete().


Variable Documentation

Initial value:

 {
        RBTREE_NULL,            
        RBTREE_NULL,            
        RBTREE_NULL,            
        NULL,                   
        BLACK                   
}
the NULL node, global alloc

the global empty node


Generated on Tue Oct 13 06:46:32 2009 for unbound by  doxygen 1.5.9