cp_narytree

Section: libcprops - cp_narytree (3)
Updated: SEPTEMBER 2006
Index Return to Main Contents [view source]

NAME

cp_narytree - an in-memory btree implementation

DESCRIPTION

cp_narytree is an N-ary tree implementation. The order of the tree, i.e. the maximal number of child nodes a node can have, may be set at instantiation. In particular btrees of order 3 are equivalent to red-black trees. In a btree, each node must contain at least (order / 2) items, with the exception of the root node. This implies a certain degree of height balancing. Btrees allow creating a relatively flat tree, and are typically used where the cost involved in tree traversal is high, as in a disk access. However due to cache line optimizations in current processors, in-memory btrees may outperform other data structures for well chosen tree orders.

cp_narytree instances may be created with a specifiable degree of internal or external synchronization and entry memory management.

A tree is created with cp_narytree_create_by_option(3) and deallocated with cp_narytree_destroy(3). After creation behavior may be changed by calling cp_narytree_unset_mode(3) to set and unset mode bits. Mappings may be added with cp_narytree_insert(3), retrieved with cp_narytree_delete(3). For more details see the documentation for specific functions.

INTERFACE

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

cp_narytree *cp_narytree_create(int order, cp_compare_fn cmp);
cp_narytree *
      cp_narytree_create_by_option(int mode,
                                   int order,
                                   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_narytree_destroy(cp_narytree *tree);
void cp_narytree_destroy_custom(cp_narytree *tree,
cp_destructor_fn key_dtr,
cp_destructor_fn value_dtr);

void *cp_narytree_insert(cp_narytree *tree, void *key, void *value);
void *cp_narytree_get(cp_narytree *tree, void *key);
void *cp_narytree_delete(cp_narytree *tree, void *key);
int cp_narytree_contains(cp_narytree *tree, void *key);
int cp_narytree_callback(cp_narytree *tree,
cp_callback_fn callback,
void *prm)
long cp_narytree_count(cp_narytree *tree);

int cp_narytree_get_mode(cp_narytree *tree);
void cp_narytree_set_mode(cp_narytree *tree, int mode);
void cp_narytree_unset_mode(cp_narytree *tree, int mode);

int cp_narytree_lock(cp_narytree *tree, int type);
int cp_narytree_unlock(cp_narytree *tree);
int cp_narytree_rdlock(cp_narytree *tree);
int cp_narytree_wrlock(cp_narytree *tree);

This document was created by man2html, using the manual pages.
Time: 17:58:11 GMT, September 08, 2006

cp_narytree

NAME

DESCRIPTION

INTERFACE

SEE ALSO

Index