rb.h File Reference

#include "common.h"
#include "vector.h"
#include "mempool.h"

Go to the source code of this file.

Data Structures

struct  _cp_rbnode
struct  _cp_rbtree
#define RB_RED   0
#define RB_BLACK   1
#define cp_rbtree_rdlock(tree)   (cp_rbtree_lock((tree), COLLECTION_LOCK_READ))
#define cp_rbtree_wrlock(tree)   (cp_rbtree_lock((tree), COLLECTION_LOCK_WRITE))
typedef CPROPS_DLL struct
_cp_rbnode 
cp_rbnode
typedef CPROPS_DLL struct
_cp_rbtree 
cp_rbtree
CPROPS_DLL cp_rbnode * cp_rbnode_create (void *key, void *value, struct _cp_mempool *pool)
CPROPS_DLL void cp_rbtree_destroy_node (struct _cp_rbtree *owner, cp_rbnode *node)
CPROPS_DLL void cp_rbtree_destroy_node_deep (struct _cp_rbtree *owner, cp_rbnode *node)
CPROPS_DLL cp_rbtree * cp_rbtree_create (cp_compare_fn cmp)
CPROPS_DLL cp_rbtree * cp_rbtree_create_by_option (int mode, cp_compare_fn cmp, cp_copy_fn key_copy, cp_destructor_fn key_dtr, cp_copy_fn val_copy, cp_destructor_fn val_dtr)
CPROPS_DLL cp_rbtree * cp_rbtree_create_multiple (int mode, cp_compare_fn cmp, cp_copy_fn key_copy, cp_destructor_fn key_dtr, cp_copy_fn val_copy, cp_destructor_fn val_dtr, cp_mapping_cmp_fn map_cmp)
CPROPS_DLL void cp_rbtree_destroy (cp_rbtree *tree)
CPROPS_DLL void cp_rbtree_destroy_custom (cp_rbtree *tree, cp_destructor_fn key_dtr, cp_destructor_fn val_dtr)
CPROPS_DLL void * cp_rbtree_insert (cp_rbtree *tree, void *key, void *value)
CPROPS_DLL void * cp_rbtree_get (cp_rbtree *tree, void *key)
CPROPS_DLL void * cp_rbtree_find (cp_rbtree *tree, void *key, cp_op op)
CPROPS_DLL int cp_rbtree_contains (cp_rbtree *tree, void *key)
CPROPS_DLL void * cp_rbtree_delete (cp_rbtree *tree, void *key)
CPROPS_DLL int cp_rbtree_callback_preorder (cp_rbtree *tree, cp_callback_fn callback, void *prm)
CPROPS_DLL int cp_rbtree_callback (cp_rbtree *tree, cp_callback_fn callback, void *prm)
CPROPS_DLL int cp_rbtree_callback_postorder (cp_rbtree *tree, cp_callback_fn callback, void *prm)
CPROPS_DLL int cp_rbtree_count (cp_rbtree *tree)
CPROPS_DLL int cp_rbtree_lock (cp_rbtree *tree, int type)
CPROPS_DLL int cp_rbtree_unlock (cp_rbtree *tree)
CPROPS_DLL int cp_rbtree_get_mode (cp_rbtree *tree)
CPROPS_DLL int cp_rbtree_set_mode (cp_rbtree *tree, int mode)
CPROPS_DLL int cp_rbtree_unset_mode (cp_rbtree *tree, int mode)
CPROPS_DLL void cp_rbtree_dump (cp_rbtree *tree)
CPROPS_DLL int cp_rbtree_use_mempool (cp_rbtree *tree, cp_mempool *pool)
CPROPS_DLL int cp_rbtree_share_mempool (cp_rbtree *tree, struct _cp_shared_mempool *pool)


Detailed Description

red-black tree definitions. Red-black trees are self balancing binary trees. red-black trees guarantee a O(log n) time for tree operations. An advantage over AVL trees is in that insertion and deletion require a small number of rotations (2 or 3) at the most.

First introduced by Rudolf Bayer in Symmetric Binary B-Trees: Data Structures and Maintenance Algorithms, 1972. The 'red-black' terminology is due to Leo J. Guibas and Robert Sedgewick: A Dichromatic Framework for Balanced Trees, 1978.

Definition in file rb.h.


Function Documentation

CPROPS_DLL void cp_rbtree_dump ( cp_rbtree *  tree  ) 

print tree to stdout

Definition at line 1128 of file rb.c.

References COLLECTION_MODE_MULTIPLE_VALUES.


Generated on Mon Dec 5 23:00:22 2011 for cprops by  doxygen 1.4.7