splay.h

Go to the documentation of this file.
00001 #ifndef _CP_SPLAY_H
00002 #define _CP_SPLAY_H
00003 
00020 #include "common.h"
00021 #include "collection.h"
00022 #include "vector.h"
00023 #include "mempool.h"
00024 
00025 __BEGIN_DECLS
00026 
00027 CPROPS_DLL struct _cp_splaytree;
00028 
00029 typedef CPROPS_DLL struct _cp_splaynode
00030 {
00031     void *key;
00032     void *value;
00033     
00034     struct _cp_splaynode *left;
00035     struct _cp_splaynode *right;
00036 } cp_splaynode;
00037 
00038 /* (internal) allocate a new node */
00039 CPROPS_DLL
00040 cp_splaynode *cp_splaynode_create(void *key, void *value, cp_mempool *pool);
00041 /* (internal) deallocate a node */
00042 CPROPS_DLL
00043 void cp_splaytree_destroy_node(struct _cp_splaytree *tree, cp_splaynode *node);
00044 /* (internal) deallocate a node and its subnodes */
00045 CPROPS_DLL
00046 void cp_splaytree_destroy_node_deep(struct _cp_splaytree *owner, cp_splaynode *node);
00047 
00048 
00049 /* tree wrapper object */
00050 typedef CPROPS_DLL struct _cp_splaytree
00051 {
00052     cp_splaynode *root;          /* root node */
00053     
00054     int items;                   /* item count */
00055 
00056     int mode;                    /* mode flags */
00057     cp_compare_fn cmp;           /* key comparison function */
00058     cp_copy_fn key_copy;         /* key copy function */
00059     cp_destructor_fn key_dtr;    /* key destructor */
00060     cp_copy_fn value_copy;       /* value copy function */
00061     cp_destructor_fn value_dtr;  /* value destructor */
00062     cp_lock *lock;
00063     cp_thread txowner;           /* set if a transaction is in progress */
00064     int txtype;                  /* lock type */
00065 
00066     cp_mempool *mempool;         /* memory pool */
00067 } cp_splaytree;
00068 
00069 /* 
00070  * default create function - equivalent to create_by_option with mode 
00071  * COLLECTION_MODE_NOSYNC
00072  */
00073 CPROPS_DLL
00074 cp_splaytree *cp_splaytree_create(cp_compare_fn cmp);
00075 
00076 /*
00077  * complete parameter create function. Note that setting COLLECTION_MODE_COPY
00078  * without specifying a copy function for either keys or values will result in
00079  * keys or values respectively being inserted by value, with no copying 
00080  * performed. Similarly, setting COLLECTION_MODE_DEEP without specifying a 
00081  * destructor function for keys or values will result in no destructor call
00082  * for keys or values respectively. This allows using the copy/deep mechanisms
00083  * for keys only, values only or both.
00084  */
00085 CPROPS_DLL
00086 cp_splaytree *
00087     cp_splaytree_create_by_option(int mode, cp_compare_fn cmp, 
00088                                 cp_copy_fn key_copy, cp_destructor_fn key_dtr,
00089                                 cp_copy_fn val_copy, cp_destructor_fn val_dtr);
00090 
00091 /* 
00092  * recursively destroy the tree structure 
00093  */
00094 CPROPS_DLL
00095 void cp_splaytree_destroy(cp_splaytree *tree);
00096 
00097 /*
00098  * recursively destroy the tree structure with the given destructor functions
00099  */
00100 CPROPS_DLL
00101 void cp_splaytree_destroy_custom(cp_splaytree *tree, 
00102                                cp_destructor_fn key_dtr,
00103                                cp_destructor_fn val_dtr);
00104 
00105 /* insertion function */
00106 CPROPS_DLL
00107 void *cp_splaytree_insert(cp_splaytree *tree, void *key, void *value);
00108 
00109 /* retrieve the value mapped to the given key */
00110 CPROPS_DLL
00111 void *cp_splaytree_get(cp_splaytree *tree, void *key);
00112 
00113 /* find the value of the closest key by operator */
00114 CPROPS_DLL
00115 void *cp_splaytree_find(cp_splaytree *tree, void *key, cp_op op);
00116 
00117 /* return non-zero if a mapping for 'key' could be found */
00118 CPROPS_DLL
00119 int cp_splaytree_contains(cp_splaytree *tree, void *key);
00120 
00121 /* delete a mapping */
00122 CPROPS_DLL
00123 void *cp_splaytree_delete(cp_splaytree *tree, void *key);
00124 
00125 /* 
00126  * perform a pre-order iteration over the tree, calling 'callback' on each 
00127  * node
00128  */
00129 CPROPS_DLL
00130 int cp_splaytree_callback_preorder(cp_splaytree *tree, 
00131                                  cp_callback_fn callback, 
00132                                  void *prm);
00133 /* 
00134  * perform an in-order iteration over the tree, calling 'callback' on each 
00135  * node
00136  */
00137 CPROPS_DLL
00138 int cp_splaytree_callback(cp_splaytree *tree, cp_callback_fn callback, void *prm);
00139 /* 
00140  * perform a post-order iteration over the tree, calling 'callback' on each 
00141  * node
00142  */
00143 CPROPS_DLL
00144 int cp_splaytree_callback_postorder(cp_splaytree *tree, 
00145                                   cp_callback_fn callback, 
00146                                   void *prm);
00147 
00148 /* return the number of mappings in the tree */
00149 CPROPS_DLL
00150 int cp_splaytree_count(cp_splaytree *tree);
00151 
00152 /* 
00153  * lock tree for reading or writing as specified by type parameter. 
00154  */
00155 CPROPS_DLL
00156 int cp_splaytree_lock(cp_splaytree *tree, int type);
00157 /* read lock */
00158 #define cp_splaytree_rdlock(tree) \
00159     (cp_splaytree_lock((tree), COLLECTION_LOCK_READ))
00160 /* write lock */
00161 #define cp_splaytree_wrlock(tree) \
00162     (cp_splaytree_lock((tree), COLLECTION_LOCK_WRITE))
00163 /* unlock */
00164 CPROPS_DLL
00165 int cp_splaytree_unlock(cp_splaytree *tree);
00166 
00167 
00168 /* return the table mode indicator */
00169 CPROPS_DLL
00170 int cp_splaytree_get_mode(cp_splaytree *tree);
00171 /* set mode bits on the tree mode indicator */
00172 CPROPS_DLL
00173 int cp_splaytree_set_mode(cp_splaytree *tree, int mode);
00174 /* unset mode bits on the tree mode indicator. if unsetting 
00175  * COLLECTION_MODE_NOSYNC and the tree was not previously synchronized, the 
00176  * internal synchronization structure is initalized.
00177  */
00178 CPROPS_DLL
00179 int cp_splaytree_unset_mode(cp_splaytree *tree, int mode);
00180 
00181 /* print tree to stdout */
00182 CPROPS_DLL
00183 void cp_splaytree_dump(cp_splaytree *tree);
00184 
00185 /* set tree to use given mempool or allocate a new one if pool is NULL */
00186 CPROPS_DLL
00187 int cp_splaytree_use_mempool(cp_splaytree *tree, cp_mempool *pool);
00188 
00189 /* set tree to use a shared memory pool */
00190 CPROPS_DLL
00191 int cp_splaytree_share_mempool(cp_splaytree *tree, cp_shared_mempool *pool);
00192 
00193 
00194 __END_DECLS
00195 
00198 #endif
00199 

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