rb.h

Go to the documentation of this file.
00001 #ifndef _CP_RB_H
00002 #define _CP_RB_H
00003 
00019 #include "common.h"
00020 
00021 __BEGIN_DECLS
00022 
00023 #include "vector.h"
00024 #include "mempool.h"
00025 
00026 struct _cp_rbtree;
00027 
00028 #define RB_RED    0
00029 #define RB_BLACK  1
00030 
00031 typedef CPROPS_DLL struct _cp_rbnode
00032 {
00033     void *key;
00034     void *value;
00035 
00036     /* balance maintainance - color is either 'red' or 'black' */
00037     int color;
00038 
00039     struct _cp_rbnode *left;
00040     struct _cp_rbnode *right;
00041     struct _cp_rbnode *up;
00042 } cp_rbnode;
00043 
00044 /* (internal) allocate a new node */
00045 CPROPS_DLL
00046 cp_rbnode *cp_rbnode_create(void *key, void *value, struct _cp_mempool *pool);
00047 /* (internal) deallocate a node */
00048 CPROPS_DLL
00049 void cp_rbtree_destroy_node(struct _cp_rbtree *owner, cp_rbnode *node);
00050 /* (internal) deallocate a node and its subnodes */
00051 CPROPS_DLL
00052 void cp_rbtree_destroy_node_deep(struct _cp_rbtree *owner, cp_rbnode *node);
00053 
00054 /* tree wrapper object */
00055 typedef CPROPS_DLL struct _cp_rbtree
00056 {
00057     cp_rbnode *root;             /* root node */
00058     
00059     int items;                   /* item count */
00060 
00061     int mode;                    /* mode flags */
00062     cp_compare_fn cmp;           /* key comparison function */
00063     cp_copy_fn key_copy;         /* key copy function */
00064     cp_destructor_fn key_dtr;    /* key destructor */
00065     cp_copy_fn value_copy;       /* value copy function */
00066     cp_destructor_fn value_dtr;  /* value destructor */
00067     cp_mapping_cmp_fn map_cmp;   /* mapping comparison function for multiple
00068                                     value entry deletion */
00069 
00070     cp_lock *lock;
00071     cp_thread txowner;           /* set if a transaction is in progress */
00072     int txtype;                  /* lock type */
00073 
00074     cp_mempool *mempool;         /* optional memory pool */
00075 } cp_rbtree;
00076 
00077 /* 
00078  * default create function - equivalent to create_by_option with mode 
00079  * COLLECTION_MODE_NOSYNC
00080  */
00081 CPROPS_DLL
00082 cp_rbtree *cp_rbtree_create(cp_compare_fn cmp);
00083 /*
00084  * complete parameter create function. Note that setting COLLECTION_MODE_COPY
00085  * without specifying a copy function for either keys or values will result in
00086  * keys or values respectively being inserted by value, with no copying 
00087  * performed. Similarly, setting COLLECTION_MODE_DEEP without specifying a 
00088  * destructor function for keys or values will result in no destructor call
00089  * for keys or values respectively. This allows using the copy/deep mechanisms
00090  * for keys only, values only or both.
00091  */
00092 CPROPS_DLL
00093 cp_rbtree *
00094     cp_rbtree_create_by_option(int mode, cp_compare_fn cmp, 
00095                                cp_copy_fn key_copy, cp_destructor_fn key_dtr,
00096                                cp_copy_fn val_copy, cp_destructor_fn val_dtr);
00097 
00098 /*
00099  * create function for multiple value trees, allows specifying mapping 
00100  * comparison function to delete individual mappings. The mode parameter
00101  * is logically or'ed with COLLECTION_MODE_MULTIPLE_VALUES.
00102  */
00103 CPROPS_DLL
00104 cp_rbtree *
00105     cp_rbtree_create_multiple(int mode, cp_compare_fn cmp, 
00106                                cp_copy_fn key_copy, cp_destructor_fn key_dtr,
00107                                cp_copy_fn val_copy, cp_destructor_fn val_dtr,
00108                                cp_mapping_cmp_fn map_cmp);
00109 
00110 /* 
00111  * recursively destroy the tree structure 
00112  */
00113 CPROPS_DLL
00114 void cp_rbtree_destroy(cp_rbtree *tree);
00115 /*
00116  * recursively destroy the tree structure with the given destructor functions
00117  */
00118 CPROPS_DLL
00119 void cp_rbtree_destroy_custom(cp_rbtree *tree, 
00120                               cp_destructor_fn key_dtr,
00121                               cp_destructor_fn val_dtr);
00122 
00123 /* insertion function */
00124 CPROPS_DLL
00125 void *cp_rbtree_insert(cp_rbtree *tree, void *key, void *value);
00126 
00127 /* retrieve the value mapped to the given key */
00128 CPROPS_DLL
00129 void *cp_rbtree_get(cp_rbtree *tree, void *key);
00130 
00131 /* find the value of the closest key by operator */
00132 CPROPS_DLL
00133 void *cp_rbtree_find(cp_rbtree *tree, void *key, cp_op op);
00134 
00135 /* return non-zero if a mapping for 'key' could be found */
00136 CPROPS_DLL
00137 int cp_rbtree_contains(cp_rbtree *tree, void *key);
00138 
00139 /* delete a mapping */
00140 CPROPS_DLL
00141 void *cp_rbtree_delete(cp_rbtree *tree, void *key);
00142 
00143 /* 
00144  * perform a pre-order iteration over the tree, calling 'callback' on each 
00145  * node
00146  */
00147 CPROPS_DLL
00148 int cp_rbtree_callback_preorder(cp_rbtree *tree, 
00149                                 cp_callback_fn callback, 
00150                                 void *prm);
00151 /* 
00152  * perform an in-order iteration over the tree, calling 'callback' on each 
00153  * node
00154  */
00155 CPROPS_DLL
00156 int cp_rbtree_callback(cp_rbtree *tree, cp_callback_fn callback, void *prm);
00157 /* 
00158  * perform a post-order iteration over the tree, calling 'callback' on each 
00159  * node
00160  */
00161 
00162 CPROPS_DLL
00163 int cp_rbtree_callback_postorder(cp_rbtree *tree, 
00164                                  cp_callback_fn callback, 
00165                                  void *prm);
00166 
00167 /* return the number of mappings in the tree */
00168 CPROPS_DLL
00169 int cp_rbtree_count(cp_rbtree *tree);
00170 
00171 /* 
00172  * lock tree for reading or writing as specified by type parameter. 
00173  */
00174 CPROPS_DLL
00175 int cp_rbtree_lock(cp_rbtree *tree, int type);
00176 /* read lock */
00177 #define cp_rbtree_rdlock(tree) (cp_rbtree_lock((tree), COLLECTION_LOCK_READ))
00178 /* write lock */
00179 #define cp_rbtree_wrlock(tree) (cp_rbtree_lock((tree), COLLECTION_LOCK_WRITE))
00180 /* unlock */
00181 CPROPS_DLL
00182 int cp_rbtree_unlock(cp_rbtree *tree);
00183 
00184 
00185 /* return the table mode indicator */
00186 CPROPS_DLL
00187 int cp_rbtree_get_mode(cp_rbtree *tree);
00188 /* set mode bits on the tree mode indicator */
00189 CPROPS_DLL
00190 int cp_rbtree_set_mode(cp_rbtree *tree, int mode);
00191 /* unset mode bits on the tree mode indicator. if unsetting 
00192  * COLLECTION_MODE_NOSYNC and the tree was not previously synchronized, the 
00193  * internal synchronization structure is initalized.
00194  */
00195 CPROPS_DLL
00196 int cp_rbtree_unset_mode(cp_rbtree *tree, int mode);
00197 
00198 
00200 CPROPS_DLL
00201 void cp_rbtree_dump(cp_rbtree *tree);
00202 
00203 /* set tree to use given mempool or allocate a new one if pool is NULL */
00204 CPROPS_DLL
00205 int cp_rbtree_use_mempool(cp_rbtree *tree, cp_mempool *pool);
00206 
00207 /* set tree to use a shared memory pool */
00208 CPROPS_DLL
00209 int cp_rbtree_share_mempool(cp_rbtree *tree, struct _cp_shared_mempool *pool);
00210 
00211 __END_DECLS
00212 
00215 #endif
00216 

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