avl.h

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

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