avl.c

00001 #include <stdio.h>
00002 #include <stdlib.h>
00003 #include <errno.h>
00004 #include <string.h>
00005 
00006 #include "collection.h"
00007 #include "avl.h"
00008 
00009 cp_avlnode *cp_avlnode_create(void *key, void *value, cp_mempool *mempool)
00010 {
00011     cp_avlnode *node;
00012     if (mempool)
00013         node = (cp_avlnode *) cp_mempool_calloc(mempool);
00014     else
00015         node = (cp_avlnode *) calloc(1, sizeof(cp_avlnode));
00016     if (node == NULL) return NULL;
00017 
00018     node->key = key;
00019     node->value = value;
00020 
00021     return node;
00022 }
00023     
00024 void cp_avltree_destroy_node(cp_avltree *tree, cp_avlnode *node)
00025 {
00026     if (node)
00027     {
00028         if ((tree->mode & COLLECTION_MODE_DEEP))
00029         {
00030             if (tree->key_dtr) (*tree->key_dtr)(node->key);
00031             if ((tree->mode & COLLECTION_MODE_MULTIPLE_VALUES) && node->value)
00032                 cp_vector_destroy_custom(node->value, tree->value_dtr);
00033             else if (tree->value_dtr) 
00034                 (*tree->value_dtr)(node->value);
00035         }
00036         else if ((tree->mode & COLLECTION_MODE_MULTIPLE_VALUES) && node->value)
00037             cp_vector_destroy(node->value);
00038         if (tree->mempool)
00039             cp_mempool_free(tree->mempool, node);
00040         else 
00041             free(node);
00042     }
00043 }
00044 
00045 void cp_avltree_destroy_node_deep(cp_avltree *tree, cp_avlnode *node)
00046 {
00047     if (node)
00048     {
00049         cp_avlnode *parent = node;
00050         cp_avlnode *child;
00051 
00052         while (1)
00053         {
00054             if (node->right)
00055             {
00056                 child = node->right;
00057                 node->right = node->left;
00058                 node->left = parent;
00059                 parent = node;
00060                 node = child;
00061             }
00062             else
00063             {
00064                 if (node->left)
00065                     cp_avltree_destroy_node(tree, node->left);
00066 
00067                 cp_avltree_destroy_node(tree, node);
00068                 if (node != parent)
00069                 {
00070                     node = parent;
00071                     parent = node->left;
00072                     node->left = NULL;
00073                 }
00074                 else
00075                     break;
00076             }
00077         }
00078     }
00079 }
00080 
00081 /* default create function - default mode is COLLECTION_MODE_NOSYNC */
00082 cp_avltree *cp_avltree_create(cp_compare_fn cmp)
00083 {
00084     cp_avltree *tree = calloc(1, sizeof(cp_avltree));
00085     if (tree == NULL) return NULL;
00086 
00087     tree->mode = COLLECTION_MODE_NOSYNC;
00088     tree->cmp = cmp;
00089 
00090     return tree;
00091 }
00092 
00093 /*
00094  * complete parameter create function
00095  */
00096 cp_avltree *
00097     cp_avltree_create_by_option(int mode, cp_compare_fn cmp, 
00098                                 cp_copy_fn key_copy, cp_destructor_fn key_dtr,
00099                                 cp_copy_fn val_copy, cp_destructor_fn val_dtr)
00100 {
00101     cp_avltree *tree = cp_avltree_create(cmp);
00102     if (tree == NULL) return NULL;
00103     
00104     tree->mode = mode;
00105     tree->key_copy = key_copy;
00106     tree->key_dtr = key_dtr;
00107     tree->value_copy = val_copy;
00108     tree->value_dtr = val_dtr;
00109 
00110     if (!(mode & COLLECTION_MODE_NOSYNC))
00111     {
00112         tree->lock = malloc(sizeof(cp_lock));
00113         if (tree->lock == NULL) 
00114         {
00115             cp_avltree_destroy(tree);
00116             return NULL;
00117         }
00118         if (cp_lock_init(tree->lock, NULL) != 0)
00119         {
00120             cp_avltree_destroy(tree);
00121             return NULL;
00122         }
00123     }
00124 
00125     return tree;
00126 }
00127 
00128 void cp_avltree_destroy(cp_avltree *tree)
00129 {
00130     if (tree)
00131     {
00132         cp_avltree_destroy_node_deep(tree, tree->root);
00133         if (tree->lock)
00134         {
00135             cp_lock_destroy(tree->lock);
00136             free(tree->lock);
00137         }
00138         free(tree);
00139     }
00140 }
00141 
00142 void cp_avltree_destroy_custom(cp_avltree *tree, 
00143                                cp_destructor_fn key_dtr,
00144                                cp_destructor_fn val_dtr)
00145 {
00146     tree->mode |= COLLECTION_MODE_DEEP;
00147     tree->key_dtr = key_dtr;
00148     tree->value_dtr = val_dtr;
00149     cp_avltree_destroy(tree);
00150 }
00151 
00152 
00153 static int cp_avltree_lock_internal(cp_avltree *tree, int type)
00154 {
00155     int rc;
00156 
00157     switch (type)
00158     {
00159         case COLLECTION_LOCK_READ:
00160             rc = cp_lock_rdlock(tree->lock);
00161             break;
00162 
00163         case COLLECTION_LOCK_WRITE:
00164             rc = cp_lock_wrlock(tree->lock);
00165             break;
00166 
00167         case COLLECTION_LOCK_NONE:
00168             rc = 0;
00169             break;
00170 
00171         default:
00172             rc = EINVAL;
00173             break;
00174     }
00175 
00176     /* api functions may rely on errno to report locking failure */
00177     if (rc) errno = rc;
00178 
00179     return rc;
00180 }
00181 
00182 static int cp_avltree_unlock_internal(cp_avltree *tree)
00183 {
00184     return cp_lock_unlock(tree->lock);
00185 }
00186 
00187 int cp_avltree_txlock(cp_avltree *tree, int type)
00188 {
00189     /* clear errno to allow client code to distinguish between a NULL return
00190      * value indicating the tree doesn't contain the requested value and NULL
00191      * on locking failure in tree operations
00192      */
00193     errno = 0;
00194     if (tree->mode & COLLECTION_MODE_NOSYNC) return 0;
00195     if (tree->mode & COLLECTION_MODE_IN_TRANSACTION && 
00196         tree->txtype == COLLECTION_LOCK_WRITE)
00197     {
00198         cp_thread self = cp_thread_self();
00199         if (cp_thread_equal(self, tree->transaction_owner)) return 0;
00200     }
00201     return cp_avltree_lock_internal(tree, type);
00202 }
00203 
00204 int cp_avltree_txunlock(cp_avltree *tree)
00205 {
00206     if (tree->mode & COLLECTION_MODE_NOSYNC) return 0;
00207     if (tree->mode & COLLECTION_MODE_IN_TRANSACTION && 
00208         tree->txtype == COLLECTION_LOCK_WRITE)
00209     {
00210         cp_thread self = cp_thread_self();
00211         if (cp_thread_equal(self, tree->transaction_owner)) return 0;
00212     }
00213     return cp_avltree_unlock_internal(tree);
00214 }
00215 
00216 /* lock and set the transaction indicators */
00217 int cp_avltree_lock(cp_avltree *tree, int type)
00218 {
00219     int rc;
00220     if ((tree->mode & COLLECTION_MODE_NOSYNC)) return EINVAL;
00221     if ((rc = cp_avltree_lock_internal(tree, type))) return rc;
00222     tree->txtype = type;
00223     tree->transaction_owner = cp_thread_self();
00224     tree->mode |= COLLECTION_MODE_IN_TRANSACTION;
00225     return 0;
00226 }
00227 
00228 /* unset the transaction indicators and unlock */
00229 int cp_avltree_unlock(cp_avltree *tree)
00230 {
00231     cp_thread self = cp_thread_self();
00232     if (tree->transaction_owner == self)
00233     {
00234         tree->transaction_owner = 0;
00235         tree->txtype = 0;
00236         tree->mode ^= COLLECTION_MODE_IN_TRANSACTION;
00237     }
00238     else if (tree->txtype == COLLECTION_LOCK_WRITE)
00239         return CP_UNLOCK_FAILED;
00240     return cp_avltree_unlock_internal(tree);
00241 }
00242 
00243 /* set mode bits on the tree mode indicator */
00244 int cp_avltree_set_mode(cp_avltree *tree, int mode)
00245 {
00246     int rc;
00247     int nosync; 
00248 
00249     /* COLLECTION_MODE_MULTIPLE_VALUES must be set at creation time */
00250     if ((mode & COLLECTION_MODE_MULTIPLE_VALUES)) return EINVAL;
00251     /* can't set NOSYNC in the middle of a transaction */
00252     if ((tree->mode & COLLECTION_MODE_IN_TRANSACTION) && 
00253         (mode & COLLECTION_MODE_NOSYNC)) return EINVAL;
00254     
00255     if ((rc = cp_avltree_txlock(tree, COLLECTION_LOCK_WRITE))) return rc;
00256     
00257     nosync = tree->mode & COLLECTION_MODE_NOSYNC;
00258 
00259     tree->mode |= mode;
00260 
00261     if (!nosync)
00262          rc = cp_avltree_txunlock(tree);
00263 
00264     return rc;
00265 }
00266 
00267 /* unset mode bits on the tree mode indicator. if unsetting 
00268  * COLLECTION_MODE_NOSYNC and the tree was not previously synchronized, the 
00269  * internal synchronization structure is initalized.
00270  */
00271 int cp_avltree_unset_mode(cp_avltree *tree, int mode)
00272 {
00273     int rc;
00274     int nosync;
00275 
00276     /* COLLECTION_MODE_MULTIPLE_VALUES can't be unset */
00277     if ((mode & COLLECTION_MODE_MULTIPLE_VALUES)) return EINVAL;
00278 
00279     nosync = tree->mode & COLLECTION_MODE_NOSYNC;
00280     if ((rc = cp_avltree_txlock(tree, COLLECTION_LOCK_WRITE))) return rc;
00281     
00282     /* handle the special case of unsetting COLLECTION_MODE_NOSYNC */
00283     if ((mode & COLLECTION_MODE_NOSYNC) && tree->lock == NULL)
00284     {
00285         /* tree can't be locked in this case, no need to unlock on failure */
00286         if ((tree->lock = malloc(sizeof(cp_lock))) == NULL)
00287             return -1; 
00288         if (cp_lock_init(tree->lock, NULL))
00289             return -1;
00290     }
00291     
00292     /* unset specified bits */
00293     tree->mode &= tree->mode ^ mode;
00294     if (!nosync)
00295         cp_avltree_txunlock(tree);
00296 
00297     return 0;
00298 }
00299 
00300 int cp_avltree_get_mode(cp_avltree *tree)
00301 {
00302     return tree->mode;
00303 }
00304 
00305 /* set tree to use given mempool or allocate a new one if pool is NULL */
00306 int cp_avltree_use_mempool(cp_avltree *tree, cp_mempool *pool)
00307 {
00308     int rc = 0;
00309     
00310     if ((rc = cp_avltree_txlock(tree, COLLECTION_LOCK_WRITE))) return rc;
00311     
00312     if (pool)
00313     {
00314         if (pool->item_size < sizeof(cp_avlnode))
00315         {
00316             rc = EINVAL;
00317             goto DONE;
00318         }
00319         if (tree->mempool) 
00320         {
00321             if (tree->items) 
00322             {
00323                 rc = ENOTEMPTY;
00324                 goto DONE;
00325             }
00326             cp_mempool_destroy(tree->mempool);
00327         }
00328         cp_mempool_inc_refcount(pool);
00329         tree->mempool = pool;
00330     }
00331     else
00332     {
00333         tree->mempool = 
00334             cp_mempool_create_by_option(COLLECTION_MODE_NOSYNC, 
00335                                         sizeof(cp_avlnode), 0);
00336         if (tree->mempool == NULL) 
00337         {
00338             rc = ENOMEM;
00339             goto DONE;
00340         }
00341     }
00342 
00343 DONE:
00344     cp_avltree_txunlock(tree);
00345     return rc;
00346 }
00347 
00348 
00349 /* set tree to use a shared memory pool */
00350 int cp_avltree_share_mempool(cp_avltree *tree, cp_shared_mempool *pool)
00351 {
00352     int rc;
00353 
00354     if ((rc = cp_avltree_txlock(tree, COLLECTION_LOCK_WRITE))) return rc;
00355 
00356     if (tree->mempool)
00357     {
00358         if (tree->items)
00359         {
00360             rc = ENOTEMPTY;
00361             goto DONE;
00362         }
00363 
00364         cp_mempool_destroy(tree->mempool);
00365     }
00366 
00367     tree->mempool = cp_shared_mempool_register(pool, sizeof(cp_avlnode));
00368     if (tree->mempool == NULL) 
00369     {
00370         rc = ENOMEM;
00371         goto DONE;
00372     }
00373     
00374 DONE:
00375     cp_avltree_txunlock(tree);
00376     return rc;
00377 }
00378 
00379 
00380 #define MIN(x, y) ((x) < (y) ? (x) : (y))
00381 #define MAX(x, y) ((x) > (y) ? (x) : (y))                                     
00382 
00383 /*         left rotate
00384  *
00385  *    (P)                (Q)
00386  *   /   \              /   \
00387  *  1    (Q)    ==>   (P)    3
00388  *      /   \        /   \
00389  *     2     3      1     2
00390  *
00391  */
00392 static void left_rotate(cp_avlnode **node)
00393 {
00394     cp_avlnode *p = *node;
00395     cp_avlnode *q = p->right;
00396 
00397     p->right = q->left;
00398     q->left = p;
00399     *node = q;
00400 
00401     p->balance -= 1 + MAX(0, q->balance);
00402     q->balance -= 1 - MIN(0, p->balance);
00403 }
00404 
00405 /*           right rotate
00406  *  
00407  *       (P)                (Q)
00408  *      /   \              /   \
00409  *    (Q)    3    ==>     1    (P)  
00410  *   /   \                    /   \
00411  *  1     2                  2     3
00412  *
00413  */
00414 static void right_rotate(cp_avlnode **node)
00415 {
00416     cp_avlnode *p = *node;
00417     cp_avlnode *q = p->left;
00418     p->left = q->right;
00419     q->right = p;
00420     *node = q;
00421 
00422     p->balance += 1 - MIN(0, q->balance);
00423     q->balance += 1 + MAX(0, p->balance);
00424 }
00425 
00426 
00427 /*            left-right rotate
00428  * 
00429  *          (P)                (R)
00430  *         /   \              /   \
00431  *      (Q)     4   ==>     (Q)    (P)  
00432  *      / \                /  \    /  \
00433  *     1  (R)             1    2  3    4
00434  *        / \
00435  *       2   3
00436  *
00437  *  note that left-right rotate could be implemented as a call to 
00438  *  left_rotate(Q) followed by a call to right_rotate(P).
00439  */
00440 static void left_right_rotate(cp_avlnode **node)
00441 {
00442     cp_avlnode *p = *node;
00443     cp_avlnode *q = (*node)->left;
00444     cp_avlnode *r = q->right;
00445 
00446     q->right = r->left;
00447     p->left = r->right;
00448     r->right = p;
00449     r->left = q;
00450 
00451     *node = r;
00452 
00453     q->balance -= 1 + MAX(0, r->balance);
00454     p->balance += 1 - MIN(MIN(0, r->balance) - 1, r->balance + q->balance);
00455     r->balance += MAX(0, p->balance) + MIN(0, q->balance);
00456 }
00457 
00458 /*              right-left rotate
00459  * 
00460  *          (P)                   (R)
00461  *         /   \                 /   \
00462  *        1     (Q)     ==>    (P)    (Q)  
00463  *             /  \           /  \    /  \
00464  *           (R)   4         1    2  3    4
00465  *           / \
00466  *          2   3
00467  *
00468  *  note that right-left rotate could be implemented as a call to 
00469  *  right_rotate(Q) followed by a call to left_rotate(P).
00470  */
00471 static void right_left_rotate(cp_avlnode **node)
00472 {
00473     cp_avlnode *p = *node;
00474     cp_avlnode *q = (*node)->right;
00475     cp_avlnode *r = q->left;
00476 
00477     q->left = r->right;
00478     p->right = r->left;
00479     r->left = p;
00480     r->right = q;
00481 
00482     *node = r;
00483 
00484     q->balance += 1 - MIN(0, r->balance);
00485     p->balance -= 1 + MAX(MAX(0, r->balance) + 1, r->balance + q->balance);
00486     r->balance += MAX(0, q->balance) + MIN(0, p->balance);
00487 }
00488 
00489 /*
00490  *  check balances and rotate as required. 
00491  */
00492 static void rebalance(cp_avlnode **node)
00493 {
00494     if ((*node)->balance == -2)
00495     {
00496         if ((*node)->left->balance == 1)
00497             left_right_rotate(node);
00498         else
00499             right_rotate(node);
00500     }
00501     else if ((*node)->balance == 2)
00502     {
00503         if ((*node)->right->balance == -1)
00504             right_left_rotate(node);
00505         else
00506             left_rotate(node);
00507     }
00508 }
00509 
00510 /* implement COLLECTION_MODE_COPY if set */
00511 static cp_avlnode *create_avlnode(cp_avltree *tree, void *key, void *value)
00512 {
00513     cp_avlnode *node = NULL;
00514 
00515     if (tree->mode & COLLECTION_MODE_COPY)
00516     {
00517         void *k = tree->key_copy ? (*tree->key_copy)(key) : key;
00518         if (k)
00519         {
00520             void *v = tree->value_copy ? (*tree->value_copy)(value) : value;
00521             if (v)
00522                 node = cp_avlnode_create(k, v, tree->mempool);
00523         }
00524     }
00525     else
00526         node = cp_avlnode_create(key, value, tree->mempool);
00527 
00528     if (node && (tree->mode & COLLECTION_MODE_MULTIPLE_VALUES))
00529     {
00530         cp_vector *m = cp_vector_create(1);
00531         if (m == NULL) 
00532         {
00533             cp_avltree_destroy_node(tree, node);
00534             return NULL;
00535         }
00536 
00537         cp_vector_add_element(m, node->value);
00538         node->value = m;
00539     }
00540 
00541     return node;
00542 }
00543 
00544 /* update_avlnode - implement COLLECTION_MODE_COPY, COLLECTION_MODE_DEEP and
00545  * COLLECTION_MODE_MULTIPLE_VALUES when inserting a value for an existing key
00546  */
00547 static void *
00548     update_avlnode(cp_avltree *tree, cp_avlnode *node, void *key, void *value)
00549 {
00550     void *new_key = key;
00551     void *new_value = value;
00552 
00553     if (tree->mode & COLLECTION_MODE_COPY)
00554     {
00555         if (tree->key_copy) 
00556         {
00557             new_key = (*tree->key_copy)(key);
00558             if (new_key == NULL) return NULL;
00559         }
00560         if (tree->value_copy)
00561         {
00562             new_value = (*tree->value_copy)(value);
00563             if (new_value == NULL) return NULL;
00564         }
00565     }
00566 
00567     if (tree->mode & COLLECTION_MODE_DEEP)
00568     {
00569         if (tree->key_dtr)
00570             (*tree->key_dtr)(node->key);
00571         if (tree->value_dtr && !(tree->mode & COLLECTION_MODE_MULTIPLE_VALUES))
00572             (*tree->value_dtr)(node->value);
00573     }
00574         
00575     node->key = new_key;
00576     if ((tree->mode & COLLECTION_MODE_MULTIPLE_VALUES))
00577     {
00578         cp_vector_add_element(node->value, new_value);
00579         return node->value;
00580     }
00581     else
00582         node->value = new_value;
00583 
00584     return new_value;
00585 }
00586 
00587 static void *avl_insert(cp_avltree *tree,         /* the tree */
00588                         cp_avlnode **node,        /* current node */
00589                         cp_avlnode *parent,       /* parent node */
00590                         void *key, void *value)   /* new entry */
00591 {
00592     void *res = NULL;
00593     int before = (*node)->balance;
00594     int cmp = tree->cmp((*node)->key, key);
00595 
00596     if (cmp == 0)
00597         return update_avlnode(tree, *node, key, value);
00598 
00599     if (cmp > 0)
00600     {   /* go left */
00601         if ((*node)->left)
00602             res = avl_insert(tree, &(*node)->left, *node, key, value);
00603         else
00604         {
00605             (*node)->left = create_avlnode(tree, key, value);
00606             if ((*node)->left == NULL) return NULL;
00607             res = (*node)->left->value;
00608             (*node)->balance--;
00609             tree->items++;
00610         }
00611     }
00612     else            /* go right */
00613     {
00614         if ((*node)->right)
00615             res = avl_insert(tree, &(*node)->right, *node, key, value);
00616         else
00617         {
00618             (*node)->right = create_avlnode(tree, key, value);
00619             if ((*node)->right == NULL) return NULL;
00620             res = (*node)->right->value;
00621             (*node)->balance++;
00622             tree->items++;
00623         }
00624     }
00625     
00626     if (parent && (*node)->balance && before == 0)
00627         parent->balance += (parent->left == *node ? (-1) : (+1));
00628 
00629     rebalance(node);
00630 
00631     return res;
00632 }
00633 
00634 /* cp_avltree_insert recurses through the tree, finds where the new node fits
00635  * in, puts it there, and balances the tree on the way out of the recursion.
00636  *
00637  * if the insertion is successful, the actual inserted value is returned - this
00638  * may be different than the 'value' parameter if COLLECTION_MODE_COPY is set.
00639  * On failure cp_avltree_insert returns NULL. insertion may fail if memory for
00640  * the new node could not be allocated, or if the operation is synchronized 
00641  * (ie, COLLECTION_MODE_NOSYNC is not set) and locking failed.
00642  *
00643  * the current implementation is recursive. An iterative implementation would
00644  * still require a stack to maintain balance after an insertion, but could save 
00645  * a few comparisons in determining whether rebalancing is required. The number
00646  * of saved comparisons would be on the order of log(N/2) on average. For a 
00647  * tree on the order of million keys, this would mean saving about 10 integer 
00648  * comparisons. This may be optimized in a future version.
00649  *
00650  * Note that cp_avltree replaces the mapping for existing keys by default. To 
00651  * create multiple mappings for the same key, COLLECTION_MODE_MULTIPLE_VALUES
00652  * must be set.
00653  */
00654 void *cp_avltree_insert(cp_avltree *tree, void *key, void *value)
00655 {
00656     void *res = NULL;
00657 
00658     /* lock unless COLLECTION_MODE_NOSYNC is set or this thread owns the tx */
00659     if (cp_avltree_txlock(tree, COLLECTION_LOCK_WRITE)) return NULL;
00660     
00661     /* perform insert */
00662     if (tree->root)
00663     {
00664         res = avl_insert(tree, &tree->root, NULL, key, value);
00665     }
00666     else
00667     {
00668         tree->root = create_avlnode(tree, key, value);
00669         if (tree->root)
00670         {
00671             tree->items++;
00672             res = tree->root->value;
00673         }
00674     }
00675 
00676     /* unlock unless COLLECTION_MODE_NOSYNC set or this thread owns the tx */
00677     cp_avltree_txunlock(tree);
00678     
00679     return res;
00680 }
00681 
00682 /*
00683  * cp_avltree_get is an iterative search function, returning the value for the
00684  * given key if found or NULL otherwise. cp_avltree_get may also return NULL if
00685  * the operation is synchronized (ie COLLECTION_MODE_NOSYNC is not set) and
00686  * locking failed. In this case, errno should be set.
00687  * 
00688  * Note that if COLLECTION_MODE_MULTIPLE_VALUES is set, the return value is a
00689  * vector containing the values for the given key. This vector may contain a 
00690  * single value.
00691  */
00692 void *cp_avltree_get(cp_avltree *tree, void *key)
00693 {
00694     void *res = NULL;
00695     cp_avlnode *curr;
00696     
00697     /* lock unless COLLECTION_MODE_NOSYNC is set or this thread owns the tx */
00698     if (cp_avltree_txlock(tree, COLLECTION_LOCK_READ)) return NULL;
00699     
00700     curr = tree->root;
00701 
00702     while (curr)
00703     {
00704         int c = tree->cmp(curr->key, key);
00705         if (c == 0) break;
00706         curr = (c > 0) ? curr->left : curr ->right;
00707     }
00708 
00709     if (curr) res = curr->value;
00710 
00711     /* unlock unless COLLECTION_MODE_NOSYNC set or this thread owns the tx */
00712     cp_avltree_txunlock(tree);
00713 
00714     return res;
00715 }
00716 
00717 static void *
00718     avltree_find_internal(cp_avltree *tree, 
00719                           cp_avlnode *curr, 
00720                           void *key, 
00721                           cp_op op)
00722 {
00723     void *res = NULL;
00724 
00725     if (curr)
00726     {
00727         int cmp = tree->cmp(key, curr->key);
00728         if (cmp == 0)
00729         {
00730             if (op == CP_OP_NE)
00731             {
00732                 if (curr->right) return curr->right->value;
00733                 if (curr->left) return curr->left->value;
00734             }
00735 
00736             if (op == CP_OP_GT)
00737             {
00738                 if (curr->right)
00739                 {
00740                     curr = curr->right;
00741                     while (curr->left) curr = curr->left;
00742                 }
00743                 else
00744                     return NULL;
00745             }
00746 
00747             if (op == CP_OP_LT)
00748             {
00749                 if (curr->left)
00750                 {
00751                     curr = curr->left;
00752                     while (curr->right) curr = curr->right;
00753                 }
00754                 else
00755                     return NULL;
00756             }
00757 
00758             return curr->value;
00759         }
00760         else
00761         {
00762             if (op == CP_OP_NE) return curr->value;
00763             if (cmp > 0) 
00764                 res = avltree_find_internal(tree, curr->right, key, op);
00765             else
00766                 res = avltree_find_internal(tree, curr->left, key, op);
00767 
00768             if (res == NULL)
00769             {
00770                 if ((cmp > 0 && (op == CP_OP_LT || op == CP_OP_LE)) ||
00771                     (cmp < 0 && (op == CP_OP_GE || op == CP_OP_GT)))
00772                         res = curr->value;
00773             }
00774         }
00775     }
00776 
00777     return res;
00778 }
00779 
00780 void *cp_avltree_find(cp_avltree *tree, void *key, cp_op op)
00781 {
00782     void *res = NULL;
00783     if (op == CP_OP_EQ) return cp_avltree_get(tree, key);
00784 
00785     /* lock unless COLLECTION_MODE_NOSYNC is set or this thread owns the tx */
00786     if (cp_avltree_txlock(tree, COLLECTION_LOCK_READ)) return NULL;
00787 
00788     res = avltree_find_internal(tree, tree->root, key, op);
00789 
00790     /* unlock unless COLLECTION_MODE_NOSYNC set or this thread owns the tx */
00791     cp_avltree_txunlock(tree);
00792 
00793     return res;
00794 }
00795 
00796 int cp_avltree_contains(cp_avltree *tree, void *key)
00797 {
00798     return (cp_avltree_get(tree, key) != NULL);
00799 }
00800 
00801 /* helper function for step_delete_right, step_delete_left */
00802 static void swap_node_content(cp_avlnode *a, cp_avlnode *b)
00803 {
00804     void *tmpkey, *tmpval;
00805 
00806     tmpkey = a->key;
00807     a->key = b->key;
00808     b->key = tmpkey;
00809     
00810     tmpval = a->value;
00811     a->value = b->value;
00812     b->value = tmpval;
00813 }
00814 
00815 /*
00816  * target can't be deleted directly because it has no NULL branches, so find 
00817  * surrogate that doesn't and delete that instead
00818  */
00819 static cp_avlnode * 
00820     step_delete_right(cp_avlnode *target, 
00821                       cp_avlnode **surrogate, 
00822                       cp_avlnode **prev, 
00823                       int *balance)
00824 {
00825     cp_avlnode *rm;
00826     cp_avlnode **pprev;
00827     if ((*surrogate)->right == NULL)
00828     {
00829         /* keep old key and value on the node being unlinked so they can be
00830          * deallocated if COLLECTION_MODE_DEEP is set
00831          */
00832         rm = *surrogate;
00833         swap_node_content(target, rm);
00834         *surrogate = (*surrogate)->left;
00835         *balance = 1;
00836     }
00837     else
00838     {
00839         pprev = prev;
00840         prev = surrogate;
00841         rm = step_delete_right(target, &(*surrogate)->right, prev, balance);
00842         prev = pprev;
00843     }
00844         
00845     if (*balance)
00846     {
00847         if ((*prev) == target)
00848             (*prev)->balance++;
00849         else
00850             (*prev)->balance--;
00851 
00852         rebalance(prev);
00853 
00854         if ((*prev)->balance == 1 || (*prev)->balance == -1)
00855             *balance = 0;
00856     }
00857 
00858     return rm;
00859 }
00860 
00861 static cp_avlnode * 
00862     step_delete_left(cp_avlnode *target, 
00863                      cp_avlnode **surrogate, 
00864                      cp_avlnode **prev, 
00865                      int *balance)
00866 {
00867     cp_avlnode *rm;
00868     cp_avlnode **pprev;
00869     if ((*surrogate)->left == NULL)
00870     {
00871         /* keep old key and value on the node being unlinked so they can be
00872          * deallocated if COLLECTION_MODE_DEEP is set
00873          */
00874         rm = *surrogate;
00875         swap_node_content(target, rm);
00876         *surrogate = (*surrogate)->right;
00877         *balance = 1;
00878     }
00879     else
00880     {
00881         pprev = prev;
00882         prev = surrogate;
00883         rm = step_delete_left(target, &(*surrogate)->left, prev, balance);
00884         prev = pprev;
00885     }
00886         
00887     if (*balance)
00888     {
00889         if ((*prev) == target)
00890             (*prev)->balance--;
00891         else
00892             (*prev)->balance++;
00893 
00894         rebalance(prev);
00895 
00896         if ((*prev)->balance == 1 || (*prev)->balance == -1)
00897             *balance = 0;
00898     }
00899 
00900     return rm;
00901 }
00902 
00903 static void *avl_delete(cp_avltree *tree, 
00904                         cp_avlnode **node, 
00905                         void *key, int *balance)
00906 {
00907     void *res = NULL;
00908     int cmp;
00909     int direction = 0;
00910 
00911     if (*node == NULL) return NULL;
00912 
00913     cmp = tree->cmp((*node)->key, key);
00914     if (cmp > 0)
00915     {
00916         direction = 1;
00917         res = avl_delete(tree, &(*node)->left, key, balance);
00918     }
00919     else if (cmp < 0)
00920     {
00921         direction = -1;
00922         res = avl_delete(tree, &(*node)->right, key, balance);
00923     }
00924     else /* cmp == 0 - found delete candidate, remove it */
00925     {
00926         cp_avlnode *old;
00927         res = (*node)->value; /* store the value to return */
00928 
00929         tree->items--;
00930         if ((*node)->left == NULL) 
00931         {
00932             old = *node;
00933             *node = (*node)->right;
00934             *balance = 1;
00935         }
00936         else if ((*node)->right == NULL)
00937         {
00938             old = *node;
00939             *node = (*node)->left;
00940             *balance = 1;
00941         }
00942         else
00943         {
00944             cp_avlnode **d;
00945             /* 
00946              * although not strictly necessary, test may save some 
00947              * rebalancing operations.  
00948              */
00949             if ((*node)->balance > 0)
00950             {
00951                 d = &(*node)->right;
00952                 old = step_delete_left(*node, d, node, balance);
00953             }
00954             else 
00955             {
00956                 d = &(*node)->left;
00957                 old = step_delete_right(*node, d, node, balance);
00958             }
00959             
00960             if ((*node)->balance == 1 || (*node)->balance == -1) *balance = 0;
00961         }
00962         cp_avltree_destroy_node(tree, old);
00963         return res;
00964     }
00965 
00966     if (*balance)
00967         (*node)->balance += direction;
00968 
00969     rebalance(node);
00970 
00971     if ((*node)->balance)
00972         *balance = 0;
00973 
00974     return res;
00975 }
00976 
00977 
00978 /* cp_avltree_delete is a recursive mapping removal function, returning the 
00979  * value mapped to the key removed or NULL if no mapping for the given key is
00980  * found. cp_avltree_delete may also return NULL if the operation is 
00981  * synchronized (ie COLLECTION_MODE_NOSYNC is not set) and locking failed. In 
00982  * this case, errno should be set. Note that the return value may point to 
00983  * unallocated memory if COLLECTION_MODE_DEEP is set. 
00984  */
00985 void *cp_avltree_delete(cp_avltree *tree, void *key)
00986 {
00987     int b = 0;
00988     void *res = NULL;
00989 
00990     if (cp_avltree_txlock(tree, COLLECTION_LOCK_WRITE)) return NULL;
00991 
00992     res = avl_delete(tree, &tree->root, key, &b);
00993 
00994     cp_avltree_txunlock(tree);
00995 
00996     return res;
00997 }
00998 
00999 static int 
01000     avl_scan_pre_order(cp_avlnode *node, cp_callback_fn callback, void *prm)
01001 {
01002     int rc;
01003     
01004     if (node) 
01005     {
01006         if ((rc = (*callback)(node, prm))) return rc;
01007         if ((rc = avl_scan_pre_order(node->left, callback, prm))) return rc;
01008         if ((rc = avl_scan_pre_order(node->right, callback, prm))) return rc;
01009     }
01010 
01011     return 0;
01012 }
01013 
01014 int cp_avltree_callback_preorder(cp_avltree *tree, 
01015                                  cp_callback_fn callback, 
01016                                  void *prm)
01017 {
01018     int rc;
01019 
01020     if ((rc = cp_avltree_txlock(tree, COLLECTION_LOCK_READ))) return rc;
01021     rc = avl_scan_pre_order(tree->root, callback, prm);
01022     cp_avltree_txunlock(tree);
01023 
01024     return rc;
01025 }
01026 
01027 static int 
01028     avl_scan_in_order(cp_avlnode *node, cp_callback_fn callback, void *prm)
01029 {
01030     int rc;
01031     
01032     if (node) 
01033     {
01034         if ((rc = avl_scan_in_order(node->left, callback, prm))) return rc;
01035         if ((rc = (*callback)(node, prm))) return rc;
01036         if ((rc = avl_scan_in_order(node->right, callback, prm))) return rc;
01037     }
01038 
01039     return 0;
01040 }
01041 
01042 int cp_avltree_callback(cp_avltree *tree, cp_callback_fn callback, void *prm)
01043 {
01044     int rc;
01045 
01046     if ((rc = cp_avltree_txlock(tree, COLLECTION_LOCK_READ))) return rc;
01047     rc = avl_scan_in_order(tree->root, callback, prm);
01048     cp_avltree_txunlock(tree);
01049 
01050     return rc;
01051 }
01052 
01053 static int 
01054     avl_scan_post_order(cp_avlnode *node, cp_callback_fn callback, void *prm)
01055 {
01056     int rc;
01057     
01058     if (node) 
01059     {
01060         if ((rc = avl_scan_post_order(node->left, callback, prm))) return rc;
01061         if ((rc = avl_scan_post_order(node->right, callback, prm))) return rc;
01062         if ((rc = (*callback)(node, prm))) return rc;
01063     }
01064 
01065     return 0;
01066 }
01067 
01068 int cp_avltree_callback_postorder(cp_avltree *tree, 
01069                                   cp_callback_fn callback, 
01070                                   void *prm)
01071 {
01072     int rc;
01073 
01074     if ((rc = cp_avltree_txlock(tree, COLLECTION_LOCK_READ))) return rc;
01075     rc = avl_scan_post_order(tree->root, callback, prm);
01076     cp_avltree_txunlock(tree);
01077 
01078     return rc;
01079 }
01080 
01081 int cp_avltree_count(cp_avltree *tree)
01082 {
01083     return tree->items;
01084 }
01085 
01086 
01087 void cp_avlnode_print(cp_avlnode *node, int level)
01088 {
01089     int i;
01090     if (node->right) cp_avlnode_print(node->right, level + 1);
01091     for (i = 0; i < level; i++) printf("  . ");
01092     printf("(%d) [%s => %s]\n", node->balance, (char *) node->key, (char *) node->value);
01093     if (node->left) cp_avlnode_print(node->left, level + 1);
01094 }
01095 
01096 void cp_avlnode_multi_print(cp_avlnode *node, int level)
01097 {
01098     int i;
01099     cp_vector *v = node->value;
01100     if (node->right) cp_avlnode_multi_print(node->right, level + 1);
01101     
01102     for (i = 0; i < level; i++) printf("  . ");
01103     printf("(%d) [%s => ", node->balance, (char *) node->key);
01104 
01105     for (i = 0; i < cp_vector_size(v); i++)
01106         printf("%s; ", (char *) cp_vector_element_at(v, i));
01107 
01108     printf("]\n");
01109 
01110     if (node->left) cp_avlnode_multi_print(node->left, level + 1);
01111 }
01112 
01113 void cp_avltree_dump(cp_avltree *tree)
01114 {
01115     if (tree->root) 
01116     {
01117         if ((tree->mode & COLLECTION_MODE_MULTIPLE_VALUES))
01118             cp_avlnode_multi_print(tree->root, 0);
01119         else
01120             cp_avlnode_print(tree->root, 0);
01121     }
01122 }
01123 

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