NAME

cp_rbtree - an red-black tree implementation

DESCRIPTION

cp_rbtree is a general purpose red-black tree implementation. red-black trees are height balanced binary trees with a guaranteed lookup complexity of O(log n). Red black trees are typically somewhat faster than AVL trees for insertion and deletion operations, and possibly somewhat slower for lookups.
Instances may be created with a specifiable degree of internal or external synchronization and entry memory management.

A tree is created with cp_rbtree_create(3) or cp_rbtree_create_by_option(3) and deallocated with cp_rbtree_destroy(3). After creation behavior may be changed by calling cp_rbtree_set_mode(3) and cp_rbtree_unset_mode(3) to set and unset mode bits. Mappings may be added with cp_rbtree_insert(3), retrieved with cp_rbtree_get(3) and removed with cp_rbtree_delete(3). For more details see the documentation for specific functions.

INTERFACE

the following is a summary of functions provided by <cprops/rb.h>.

cp_rbtree *cp_rbtree_create(cp_compare_fn cmp);
cp_rbtree * cp_rbtree_create_by_option(int mode, cp_compare_fn compare_fn, cp_copy_fn copy_key, cp_destructor_fn free_key); cp_copy_fn copy_value cp_destructor_fn free_value);

void cp_rbtree_destroy(cp_rbtree *tree);
void cp_rbtree_destroy_custom(cp_rbtree *tree, cp_destructor_fn dk, cp_destructor_fn dv);

int cp_rbtree_callback_preorder(cp_rbtree *tree, cp_callback_fn callback, void *prm);
int cp_rbtree_callback(cp_rbtree *tree, cp_callback_fn callback, void *prm);
int cp_rbtree_callback_postorder(cp_rbtree *tree, cp_callback_fn callback, void *prm);

void *cp_rbtree_insert(cp_rbtree *tree, void *key, void *value);
void *cp_rbtree_get(cp_rbtree *tree, void *key);
void *cp_rbtree_delete(cp_rbtree *tree, void *key);
int cp_rbtree_contains(cp_rbtree *tree, void *key);
long cp_rbtree_count(cp_rbtree *tree);

int cp_rbtree_get_mode(cp_rbtree *tree);
void cp_rbtree_set_mode(cp_rbtree *tree, int mode);
void cp_rbtree_unset_mode(cp_rbtree *tree, int mode);

int cp_rbtree_lock(cp_rbtree *tree, int type);
int cp_rbtree_unlock(cp_rbtree *tree);
int cp_rbtree_rdlock(cp_rbtree *tree);
int cp_rbtree_wrlock(cp_rbtree *tree);

SEE ALSO

cp_rbtree_create(3), cp_rbtree_insert(3), cp_rbtree_lock(3), cp_rbtree_set_mode(3), cprops(3)