rb.c

00001 #include <stdio.h>
00002 #include <stdlib.h>
00003 #include <errno.h>
00004 
00005 #include "collection.h"
00006 #include "vector.h"
00007 #include "rb.h"
00008 
00009 cp_rbnode *cp_rbnode_create(void *key, void *value, cp_mempool *pool)
00010 {
00011     cp_rbnode *node;
00012     
00013     if (pool) 
00014         node = (cp_rbnode *) cp_mempool_calloc(pool);
00015     else
00016         node = (cp_rbnode *) calloc(1, sizeof(cp_rbnode));
00017 
00018     if (node == NULL) return NULL;
00019 
00020     node->key = key;
00021     node->value = value;
00022 
00023     return node;
00024 }
00025     
00026 /* implement COLLECTION_MODE_COPY if set */
00027 static cp_rbnode *create_rbnode(cp_rbtree *tree, void *key, void *value)
00028 {
00029     if (tree->mode & COLLECTION_MODE_COPY)
00030     {
00031         void *k, *v;
00032         k = tree->key_copy ? (*tree->key_copy)(key) : key;
00033         if (k)
00034         {
00035             v = tree->value_copy ? (*tree->value_copy)(value) : value;
00036             if (v)
00037             {
00038                 if ((tree->mode & COLLECTION_MODE_MULTIPLE_VALUES))
00039                 {
00040                     cp_vector *m = cp_vector_create(1);
00041                     if (m == NULL) return NULL;
00042                     cp_vector_add_element(m, v);
00043                     v = m;
00044                 }
00045                 return cp_rbnode_create(k, v, tree->mempool);
00046             }
00047         }
00048     }
00049     else if ((tree->mode & COLLECTION_MODE_MULTIPLE_VALUES))
00050     {
00051         cp_vector *m = cp_vector_create(1);
00052         if (m == NULL) return NULL;
00053         cp_vector_add_element(m, value);
00054         return cp_rbnode_create(key, m, tree->mempool);
00055     }
00056     else 
00057         return cp_rbnode_create(key, value, tree->mempool);
00058 
00059     return NULL;
00060 }
00061 
00062 void cp_rbtree_destroy_node_deep(cp_rbtree *owner, cp_rbnode *node)
00063 {
00064     while (node)
00065     {
00066         if (node->right)
00067         {
00068             node = node->right;
00069             node->up->right = NULL;
00070         }
00071         else if (node->left)
00072         {
00073             node = node->left;
00074             node->up->left = NULL;
00075         }
00076         else
00077         {
00078             cp_rbnode *tmp = node;
00079             node = node->up;
00080             cp_rbtree_destroy_node(owner, tmp);
00081         }
00082     }
00083 }
00084 
00085 void cp_rbtree_destroy_node(cp_rbtree *tree, cp_rbnode *node)
00086 {
00087     if (node)
00088     {
00089         if ((tree->mode & COLLECTION_MODE_DEEP))
00090         {
00091             if (tree->key_dtr) (*tree->key_dtr)(node->key);
00092             if ((tree->mode & COLLECTION_MODE_MULTIPLE_VALUES) && node->value)
00093                 cp_vector_destroy_custom(node->value, tree->value_dtr);
00094             else if (tree->value_dtr) 
00095                 (*tree->value_dtr)(node->value);
00096         }
00097         else if ((tree->mode & COLLECTION_MODE_MULTIPLE_VALUES) && node->value)
00098             cp_vector_destroy(node->value);
00099 
00100         if (tree->mempool)
00101             cp_mempool_free(tree->mempool, node);
00102         else
00103             free(node);
00104     }
00105 }
00106 
00107 
00108 cp_rbtree *cp_rbtree_create(cp_compare_fn cmp)
00109 {
00110     cp_rbtree *tree = calloc(1, sizeof(cp_rbtree));
00111     if (tree == NULL) return NULL;
00112 
00113     tree->mode = COLLECTION_MODE_NOSYNC;
00114     tree->cmp = cmp;
00115 
00116     return tree;
00117 }
00118 
00119 /*
00120  * complete parameter create function
00121  */
00122 cp_rbtree *
00123     cp_rbtree_create_by_option(int mode, cp_compare_fn cmp, 
00124                                cp_copy_fn key_copy, cp_destructor_fn key_dtr,
00125                                cp_copy_fn val_copy, cp_destructor_fn val_dtr)
00126 {
00127     cp_rbtree *tree = cp_rbtree_create(cmp);
00128     if (tree == NULL) return NULL;
00129     
00130     tree->mode = mode;
00131     tree->key_copy = key_copy;
00132     tree->key_dtr = key_dtr;
00133     tree->value_copy = val_copy;
00134     tree->value_dtr = val_dtr;
00135 
00136     if (!(mode & COLLECTION_MODE_NOSYNC))
00137     {
00138         tree->lock = malloc(sizeof(cp_lock));
00139         if (tree->lock == NULL) 
00140         {
00141             cp_rbtree_destroy(tree);
00142             return NULL;
00143         }
00144         if (cp_lock_init(tree->lock, NULL) != 0)
00145         {
00146             cp_rbtree_destroy(tree);
00147             return NULL;
00148         }
00149     }
00150 
00151     return tree;
00152 }
00153 
00154 cp_rbtree *
00155     cp_rbtree_create_multiple(int mode, cp_compare_fn cmp, 
00156                                cp_copy_fn key_copy, cp_destructor_fn key_dtr,
00157                                cp_copy_fn val_copy, cp_destructor_fn val_dtr,
00158                                cp_mapping_cmp_fn map_cmp)
00159 {
00160     cp_rbtree *res = 
00161         cp_rbtree_create_by_option(mode | COLLECTION_MODE_MULTIPLE_VALUES, 
00162                                    cmp, 
00163                                    key_copy, 
00164                                    key_dtr, 
00165                                    val_copy, 
00166                                    val_dtr);
00167 
00168     if (res)
00169         res->map_cmp = map_cmp;
00170 
00171     return res;
00172 }
00173 
00174 void cp_rbtree_destroy(cp_rbtree *tree)
00175 {
00176     if (tree)
00177     {
00178         cp_rbtree_destroy_node_deep(tree, tree->root);
00179         if (tree->lock)
00180         {
00181             cp_lock_destroy(tree->lock);
00182             free(tree->lock);
00183         }
00184         free(tree);
00185     }
00186 }
00187 
00188 void cp_rbtree_destroy_custom(cp_rbtree *tree, 
00189                               cp_destructor_fn key_dtr,
00190                               cp_destructor_fn val_dtr)
00191 {
00192     tree->mode |= COLLECTION_MODE_DEEP;
00193     tree->key_dtr = key_dtr;
00194     tree->value_dtr = val_dtr;
00195     cp_rbtree_destroy(tree);
00196 }
00197 
00198 static int cp_rbtree_lock_internal(cp_rbtree *tree, int type)
00199 {
00200     int rc;
00201 
00202     switch (type)
00203     {
00204         case COLLECTION_LOCK_READ:
00205             rc = cp_lock_rdlock(tree->lock);
00206             break;
00207 
00208         case COLLECTION_LOCK_WRITE:
00209             rc = cp_lock_wrlock(tree->lock);
00210             break;
00211 
00212         case COLLECTION_LOCK_NONE:
00213             rc = 0;
00214             break;
00215 
00216         default:
00217             rc = EINVAL;
00218             break;
00219     }
00220 
00221     /* api functions may rely on errno to report locking failure */
00222     if (rc) errno = rc;
00223 
00224     return rc;
00225 }
00226 
00227 static int cp_rbtree_unlock_internal(cp_rbtree *tree)
00228 {
00229     return cp_lock_unlock(tree->lock);
00230 }
00231 
00232 int cp_rbtree_txlock(cp_rbtree *tree, int type)
00233 {
00234     /* clear errno to allow client code to distinguish between a NULL return
00235      * value indicating the tree doesn't contain the requested value and NULL
00236      * on locking failure in tree operations
00237      */
00238     if (tree->mode & COLLECTION_MODE_NOSYNC) return 0;
00239     if ((tree->mode & COLLECTION_MODE_IN_TRANSACTION) && 
00240         tree->txtype == COLLECTION_LOCK_WRITE)
00241     {
00242         cp_thread self = cp_thread_self();
00243         if (cp_thread_equal(self, tree->txowner)) return 0;
00244     }
00245     errno = 0;
00246     return cp_rbtree_lock_internal(tree, type);
00247 }
00248 
00249 int cp_rbtree_txunlock(cp_rbtree *tree)
00250 {
00251     if (tree->mode & COLLECTION_MODE_NOSYNC) return 0;
00252     if ((tree->mode & COLLECTION_MODE_IN_TRANSACTION) && 
00253         tree->txtype == COLLECTION_LOCK_WRITE)
00254     {
00255         cp_thread self = cp_thread_self();
00256         if (cp_thread_equal(self, tree->txowner)) return 0;
00257     }
00258     return cp_rbtree_unlock_internal(tree);
00259 }
00260 
00261 /* lock and set the transaction indicators */
00262 int cp_rbtree_lock(cp_rbtree *tree, int type)
00263 {
00264     int rc;
00265     if ((tree->mode & COLLECTION_MODE_NOSYNC)) return EINVAL;
00266     if ((rc = cp_rbtree_lock_internal(tree, type))) return rc;
00267     tree->txtype = type;
00268     tree->txowner = cp_thread_self();
00269     tree->mode |= COLLECTION_MODE_IN_TRANSACTION;
00270     return 0;
00271 }
00272 
00273 /* unset the transaction indicators and unlock */
00274 int cp_rbtree_unlock(cp_rbtree *tree)
00275 {
00276     cp_thread self = cp_thread_self();
00277     if (tree->txowner == self)
00278     {
00279         tree->txowner = 0;
00280         tree->txtype = 0;
00281         tree->mode ^= COLLECTION_MODE_IN_TRANSACTION;
00282     }
00283     else if (tree->txtype == COLLECTION_LOCK_WRITE)
00284         return -1;
00285     return cp_rbtree_unlock_internal(tree);
00286 }
00287 
00288 /* set mode bits on the tree mode indicator */
00289 int cp_rbtree_set_mode(cp_rbtree *tree, int mode)
00290 {
00291     int rc;
00292     int nosync; 
00293 
00294     /* can't set NOSYNC in the middle of a transaction */
00295     if ((tree->mode & COLLECTION_MODE_IN_TRANSACTION) && 
00296         (mode & COLLECTION_MODE_NOSYNC)) return EINVAL;
00297     /* COLLECTION_MODE_MULTIPLE_VALUES must be set at creation time */  
00298     if ((mode & COLLECTION_MODE_MULTIPLE_VALUES)) return EINVAL;
00299 
00300     if ((rc = cp_rbtree_txlock(tree, COLLECTION_LOCK_WRITE))) return rc;
00301     
00302     nosync = tree->mode & COLLECTION_MODE_NOSYNC;
00303 
00304     tree->mode |= mode;
00305 
00306     if (!nosync)
00307         cp_rbtree_txunlock(tree);
00308 
00309     return 0;
00310 }
00311 
00312 /* unset mode bits on the tree mode indicator. if unsetting 
00313  * COLLECTION_MODE_NOSYNC and the tree was not previously synchronized, the 
00314  * internal synchronization structure is initialized.
00315  */
00316 int cp_rbtree_unset_mode(cp_rbtree *tree, int mode)
00317 {
00318     int rc;
00319     int nosync;
00320 
00321     /* COLLECTION_MODE_MULTIPLE_VALUES can't be unset */
00322     if ((mode & COLLECTION_MODE_MULTIPLE_VALUES)) return EINVAL;
00323 
00324     if ((rc = cp_rbtree_txlock(tree, COLLECTION_LOCK_WRITE))) return rc;
00325     
00326     nosync = tree->mode & COLLECTION_MODE_NOSYNC;
00327 
00328     /* handle the special case of unsetting COLLECTION_MODE_NOSYNC */
00329     if ((mode & COLLECTION_MODE_NOSYNC) && tree->lock == NULL)
00330     {
00331         /* tree can't be locked in this case, no need to unlock on failure */
00332         if ((tree->lock = malloc(sizeof(cp_lock))) == NULL)
00333             return -1;
00334         if (cp_lock_init(tree->lock, NULL))
00335             return -1;
00336     }
00337     
00338     /* unset specified bits */
00339     tree->mode &= tree->mode ^ mode;
00340     if (!nosync)
00341         cp_rbtree_txunlock(tree);
00342 
00343     return 0;
00344 }
00345 
00346 int cp_rbtree_get_mode(cp_rbtree *tree)
00347 {
00348     return tree->mode;
00349 }
00350 
00351 
00352 static cp_rbnode *sibling(cp_rbnode *node)
00353 {
00354     return node == node->up->left ? node->up->right : node->up->left;
00355 }
00356 
00357 static int is_right_child(cp_rbnode *node)
00358 {
00359     return (node->up->right == node);
00360 }
00361 
00362 static int is_left_child(cp_rbnode *node)
00363 {
00364     return (node->up->left == node);
00365 }
00366 
00367 /*         left rotate
00368  *
00369  *    (P)                (Q)
00370  *   /   \              /   \
00371  *  1    (Q)    ==>   (P)    3
00372  *      /   \        /   \
00373  *     2     3      1     2
00374  *
00375  */
00376 static void left_rotate(cp_rbtree *tree, cp_rbnode *p)
00377 {
00378     cp_rbnode *q = p->right;
00379     cp_rbnode **sup;
00380     
00381     if (p->up)
00382         sup = is_left_child(p) ? &(p->up->left) : &(p->up->right);
00383     else
00384         sup = &tree->root;
00385 
00386     p->right = q->left;
00387     if (p->right) p->right->up = p;
00388     q->left = p;
00389     q->up = p->up;
00390     p->up = q;
00391     *sup = q;
00392 }
00393 
00394 /*           right rotate
00395  *  
00396  *       (P)                (Q)
00397  *      /   \              /   \
00398  *    (Q)    3    ==>     1    (P)  
00399  *   /   \                    /   \
00400  *  1     2                  2     3
00401  *
00402  */
00403 static void right_rotate(cp_rbtree *tree, cp_rbnode *p)
00404 {
00405     cp_rbnode *q = p->left;
00406     cp_rbnode **sup;
00407     
00408     if (p->up)
00409         sup = is_left_child(p) ? &(p->up->left) : &(p->up->right);
00410     else
00411         sup = &tree->root;
00412 
00413     p->left = q->right;
00414     if (p->left) p->left->up = p;
00415     q->right = p;
00416     q->up = p->up;
00417     p->up = q;
00418     *sup = q;
00419 }
00420 
00421 
00422 /*
00423  * newly entered node is RED; check balance recursively as required 
00424  */
00425 static void rebalance(cp_rbtree *tree, cp_rbnode *node)
00426 {
00427     cp_rbnode *up = node->up;
00428     if (up == NULL || up->color == RB_BLACK) return;
00429     if (sibling(up) && sibling(up)->color == RB_RED)
00430     {
00431         up->color = RB_BLACK;
00432         sibling(up)->color = RB_BLACK;
00433         if (up->up->up)
00434         {
00435             up->up->color = RB_RED;
00436             rebalance(tree, up->up);
00437         }
00438     }
00439     else
00440     {
00441         if (is_left_child(node) && is_right_child(up))
00442         {
00443             right_rotate(tree, up);
00444             node = node->right;
00445         }
00446         else if (is_right_child(node) && is_left_child(up))
00447         {
00448             left_rotate(tree, up);
00449             node = node->left;
00450         }
00451 
00452         node->up->color = RB_BLACK;
00453         node->up->up->color = RB_RED;
00454 
00455         if (is_left_child(node)) // && is_left_child(node->up)
00456             right_rotate(tree, node->up->up);
00457         else 
00458             left_rotate(tree, node->up->up);
00459     }
00460 }
00461 
00462 /* update_rbnode - implement COLLECTION_MODE_COPY, COLLECTION_MODE_DEEP and
00463  * COLLECTION_MODE_MULTIPLE_VALUES when inserting a value for an existing key
00464  */
00465 static void *
00466     update_rbnode(cp_rbtree *tree, cp_rbnode *node, void *key, void *value)
00467 {
00468     void *new_key = key;
00469     void *new_value = value;
00470 
00471     if (tree->mode & COLLECTION_MODE_COPY)
00472     {
00473         if (tree->key_copy) 
00474         {
00475             new_key = (*tree->key_copy)(key);
00476             if (new_key == NULL) return NULL;
00477         }
00478         if (tree->value_copy)
00479         {
00480             new_value = (*tree->value_copy)(value);
00481             if (new_value == NULL) return NULL;
00482         }
00483     }
00484 
00485     if (tree->mode & COLLECTION_MODE_DEEP)
00486     {
00487         if (tree->key_dtr)
00488             (*tree->key_dtr)(node->key);
00489         if (tree->value_dtr && !(tree->mode & COLLECTION_MODE_MULTIPLE_VALUES))
00490             (*tree->value_dtr)(node->value);
00491     }
00492         
00493     node->key = new_key;
00494     if (!(tree->mode & COLLECTION_MODE_MULTIPLE_VALUES))
00495         node->value = new_value;
00496     else
00497     {
00498         cp_vector_add_element(node->value, new_value);
00499         return node->value;
00500     }
00501 
00502     return new_value;
00503 }
00504 
00505 /*
00506  * cp_rbtree_insert iterates through the tree, finds where the new node fits
00507  * in, puts it there, then calls rebalance. 
00508  *
00509  * If a mapping for the given key already exists it is replaced unless 
00510  * COLLECTION_MODE_MULTIPLE_VALUES is set, is which case a new mapping is 
00511  * added. By default COLLECTION_MODE_MULTIPLE_VALUES is not set.
00512  */
00513 void *cp_rbtree_insert(cp_rbtree *tree, void *key, void *value)
00514 {
00515     void *res = NULL;
00516     
00517     if (cp_rbtree_txlock(tree, COLLECTION_LOCK_WRITE)) return NULL;
00518 
00519     if (tree->root == NULL)
00520     {
00521         tree->root = create_rbnode(tree, key, value);
00522         if (tree->root == NULL) goto DONE;
00523         res = value;
00524         tree->root->color = RB_BLACK;
00525         tree->items++;
00526     }
00527     else
00528     {
00529         int cmp;
00530         cp_rbnode **curr = &tree->root;
00531         cp_rbnode *prev = NULL;
00532 
00533         while (*curr)
00534         {
00535             prev = *curr;
00536             cmp = (*tree->cmp)((*curr)->key, key);
00537             if (cmp < 0)
00538                 curr = &(*curr)->right;
00539             else if (cmp > 0) 
00540                 curr = &(*curr)->left;
00541             else /* replace */
00542             {
00543                 res = update_rbnode(tree, *curr, key, value);
00544                 break;
00545             }
00546         }
00547 
00548         if (*curr == NULL) /* not replacing, create new node */
00549         {
00550             *curr = create_rbnode(tree, key, value);
00551             if (*curr == NULL) goto DONE;
00552             res = (*curr)->value;
00553             tree->items++;
00554             (*curr)->up = prev;
00555             rebalance(tree, *curr);
00556         }
00557     }
00558 
00559 DONE:
00560     cp_rbtree_txunlock(tree);
00561     return res;
00562 }
00563 
00564 /* cp_rbtree_get - return the value mapped to the given key or NULL if none is
00565  * found. If COLLECTION_MODE_MULTIPLE_VALUES is set the returned value is a
00566  * cp_vector object or NULL if no mapping is found. 
00567  */
00568 void *cp_rbtree_get(cp_rbtree *tree, void *key)
00569 {
00570     cp_rbnode *curr;
00571     void *value = NULL;
00572     
00573     if (cp_rbtree_txlock(tree, COLLECTION_LOCK_READ)) return NULL;
00574 
00575     curr = tree->root;
00576     while (curr)
00577     {
00578         int c = tree->cmp(curr->key, key);
00579         if (c == 0) return curr->value;
00580         curr = (c > 0) ? curr->left : curr ->right;
00581     }
00582 
00583     if (curr) value = curr->value;
00584 
00585     cp_rbtree_txunlock(tree);
00586     return value;;
00587 }
00588     
00589 CPROPS_DLL
00590 void *cp_rbtree_find(cp_rbtree *tree, void *key, cp_op op)
00591 {
00592     int cmp;
00593     cp_rbnode **curr;
00594     cp_rbnode *prev = NULL;
00595     cp_rbnode *res = NULL;
00596 
00597     if (tree->root == NULL) return NULL;
00598 
00599     if (cp_rbtree_txlock(tree, COLLECTION_LOCK_READ)) return NULL;
00600 
00601     curr = &tree->root;
00602     while (*curr)
00603     {
00604         prev = *curr;
00605         cmp = (*tree->cmp)((*curr)->key, key);
00606 
00607         if (cmp == 0) break;
00608         if (op == CP_OP_NE)
00609         {
00610             res = *curr;
00611             goto FIND_DONE;
00612         }
00613 
00614         if (cmp < 0)
00615             curr = &(*curr)->right;
00616         else 
00617             curr = &(*curr)->left;
00618     }
00619 
00620     if (*curr)
00621     {
00622         if (op == CP_OP_EQ || op == CP_OP_LE || op == CP_OP_GE)
00623         {
00624             res = *curr;
00625             goto FIND_DONE;
00626         }
00627 
00628         if (op == CP_OP_GT)
00629         {
00630             if ((*curr)->right)
00631             {
00632                 curr = &(*curr)->right;
00633                 while ((*curr)->left) curr = &(*curr)->left;
00634                 res = *curr;
00635             }
00636             else
00637             {
00638                 while ((*curr)->up)
00639                 {
00640                     prev = *curr;
00641                     curr = &(*curr)->up;
00642                     if ((*curr)->left == prev)
00643                     {
00644                         res = *curr;
00645                         break;
00646                     }
00647                 }
00648             }
00649         }
00650         else
00651         {
00652             if ((*curr)->left)
00653             {
00654                 curr = &(*curr)->left;
00655                 while ((*curr)->right) curr = &(*curr)->right;
00656                 res = *curr;
00657             }
00658             else
00659             {
00660                 while ((*curr)->up)
00661                 {
00662                     prev = *curr;
00663                     curr = &(*curr)->up;
00664                     if ((*curr)->right == prev)
00665                     {
00666                         res = *curr;
00667                         break;
00668                     }
00669                 }
00670             }
00671         }
00672 
00673         goto FIND_DONE;
00674     }
00675 
00676     /* *curr is NULL */
00677     if (op == CP_OP_EQ) goto FIND_DONE;
00678 
00679     if (op == CP_OP_LT || op == CP_OP_LE)
00680     {
00681         if (curr == &prev->right) 
00682         {
00683             res = prev;
00684             goto FIND_DONE;
00685         }
00686 
00687         while (prev)
00688         {
00689             if (prev->up && prev->up->right == prev)
00690             {
00691                 res = prev->up;
00692                 break;
00693             }
00694             prev = prev->up;
00695         }
00696     } 
00697     else /* op == CP_OP_GE || op == CP_OP_GT */
00698     {
00699         if (curr == &prev->left)
00700         {
00701             res = prev;
00702             goto FIND_DONE;
00703         }
00704 
00705         while (prev)
00706         {
00707             if (prev->up && prev->up->left == prev)
00708             {
00709                 res = prev->up;
00710                 break;
00711             }
00712             prev = prev->up;
00713         }
00714     }
00715 
00716 FIND_DONE:
00717     cp_rbtree_txunlock(tree);
00718     return res ? res->value : NULL;
00719 }
00720 
00721 int cp_rbtree_contains(cp_rbtree *tree, void *key)
00722 {
00723     return (cp_rbtree_get(tree, key) != NULL);
00724 }
00725 
00726 /* helper function for deletion */
00727 static void swap_node_content(cp_rbnode *a, cp_rbnode *b)
00728 {
00729     void *tmpkey, *tmpval;
00730 
00731     tmpkey = a->key;
00732     a->key = b->key;
00733     b->key = tmpkey;
00734     
00735     tmpval = a->value;
00736     a->value = b->value;
00737     b->value = tmpval;
00738 }
00739 
00740 /*
00741  * helper function for cp_rbtree_delete to remove nodes with either a left 
00742  * NULL branch or a right NULL branch
00743  */
00744 static void rb_unlink(cp_rbtree *tree, cp_rbnode *node)
00745 {
00746     if (node->left)
00747     {
00748         node->left->up = node->up;
00749         if (node->up)
00750         {
00751             if (is_left_child(node))
00752                 node->up->left = node->left;
00753             else
00754                 node->up->right = node->left;
00755         }
00756         else
00757             tree->root = node->left;
00758     }
00759     else
00760     {
00761         if (node->right) node->right->up = node->up;
00762         if (node->up)
00763         {
00764             if (is_left_child(node))
00765                 node->up->left = node->right;
00766             else
00767                 node->up->right = node->right;
00768         }
00769         else
00770             tree->root = node->right;
00771     }
00772 }
00773 
00774 /* delete_rebalance - perform rebalancing after a deletion */
00775 static void delete_rebalance(cp_rbtree *tree, cp_rbnode *n)
00776 {
00777     if (n->up)
00778     {
00779         cp_rbnode *sibl = sibling(n);
00780 
00781         if (sibl->color == RB_RED)
00782         {
00783             n->up->color = RB_RED;
00784             sibl->color = RB_BLACK;
00785             if (is_left_child(n))
00786                 left_rotate(tree, n->up);
00787             else
00788                 right_rotate(tree, n->up);
00789             sibl = sibling(n);
00790         }
00791 
00792         if (n->up->color == RB_BLACK &&
00793             sibl->color == RB_BLACK &&
00794             (sibl->left == NULL || sibl->left->color == RB_BLACK) &&
00795             (sibl->right == NULL || sibl->right->color == RB_BLACK))
00796         {
00797             sibl->color = RB_RED;
00798             delete_rebalance(tree, n->up);
00799         }
00800         else
00801         {
00802             if (n->up->color == RB_RED &&
00803                 sibl->color == RB_BLACK &&
00804                 (sibl->left == NULL || sibl->left->color == RB_BLACK) &&
00805                 (sibl->right == NULL || sibl->right->color == RB_BLACK))
00806             {
00807                 sibl->color = RB_RED;
00808                 n->up->color = RB_BLACK;
00809             }
00810             else
00811             {
00812                 if (is_left_child(n) && 
00813                     sibl->color == RB_BLACK &&
00814                     sibl->left && sibl->left->color == RB_RED && 
00815                     (sibl->right == NULL || sibl->right->color == RB_BLACK))
00816                 {
00817                     sibl->color = RB_RED;
00818                     sibl->left->color = RB_BLACK;
00819                     right_rotate(tree, sibl);
00820                     
00821                     sibl = sibling(n);
00822                 }
00823                 else if (is_right_child(n) &&
00824                     sibl->color == RB_BLACK &&
00825                     sibl->right && sibl->right->color == RB_RED &&
00826                     (sibl->left == NULL || sibl->left->color == RB_BLACK))
00827                 {
00828                     sibl->color = RB_RED;
00829                     sibl->right->color = RB_BLACK;
00830                     left_rotate(tree, sibl);
00831 
00832                     sibl = sibling(n);
00833                 }
00834 
00835                 sibl->color = n->up->color;
00836                 n->up->color = RB_BLACK;
00837                 if (is_left_child(n))
00838                 {
00839                     sibl->right->color = RB_BLACK;
00840                     left_rotate(tree, n->up);
00841                 }
00842                 else
00843                 {
00844                     sibl->left->color = RB_BLACK;
00845                     right_rotate(tree, n->up);
00846                 }
00847             }
00848         }
00849     }
00850 }
00851 
00852 /* cp_rbtree_delete_mapping_impl - delete a mapping from a red black tree */
00853 void *cp_rbtree_delete_mapping_impl(cp_rbtree *tree, cp_mapping *mapping)
00854 {
00855     cp_vector *res = NULL;
00856     cp_rbnode *node; 
00857     int cmp;
00858 
00859     node = tree->root;
00860     while (node)
00861     {
00862         cmp = (*tree->cmp)(node->key, cp_mapping_key(mapping));
00863         if (cmp < 0)
00864             node = node->right;
00865         else if (cmp > 0)
00866             node = node->left;
00867         else /* found */
00868             break;
00869     }
00870 
00871     if (node) /* may be null if not found */
00872     {
00873         int index;
00874         cp_rbnode *child; 
00875         cp_mapping map;
00876 
00877         res = node->value;
00878         map.key = cp_mapping_key(mapping);
00879         for (index = 0; index < cp_vector_size(res); index++)
00880         {
00881             map.value = cp_vector_element_at(res, index);
00882             if (tree->map_cmp(mapping, &map) == 0) break;
00883         }
00884 
00885         if (index == cp_vector_size(res)) return NULL;
00886         
00887         cp_vector_remove_element_at(res, index);
00888 
00889         tree->items--;
00890 
00891         if (cp_vector_size(res) > 0) return map.value;
00892         
00893         if (node->right && node->left)
00894         {
00895             cp_rbnode *surrogate = node;
00896             node = node->right;
00897             while (node->left) node = node->left;
00898             swap_node_content(node, surrogate);
00899         }
00900         child = node->right ? node->right : node->left;
00901 
00902         /* if the node was red - no rebalancing required */
00903         if (node->color == RB_BLACK)
00904         {
00905             if (child)
00906             {
00907                 /* single red child - paint it black */
00908                 if (child->color == RB_RED)
00909                     child->color = RB_BLACK; /* and the balance is restored */
00910                 else
00911                     delete_rebalance(tree, child);
00912             }
00913             else 
00914                 delete_rebalance(tree, node);
00915         }
00916 
00917         rb_unlink(tree, node);
00918         cp_rbtree_destroy_node(tree, node);
00919     }
00920 
00921     return res;
00922 }
00923 
00924 /* cp_rbtree_delete_impl - delete one node from a red black tree */
00925 void *cp_rbtree_delete_impl(cp_rbtree *tree, void *key)
00926 {
00927     void *res = NULL;
00928     cp_rbnode *node; 
00929     int cmp;
00930 
00931     node = tree->root;
00932     while (node)
00933     {
00934         cmp = (*tree->cmp)(node->key, key);
00935         if (cmp < 0)
00936             node = node->right;
00937         else if (cmp > 0)
00938             node = node->left;
00939         else /* found */
00940             break;
00941     }
00942 
00943     if (node) /* may be null if not found */
00944     {
00945         cp_rbnode *child; 
00946         res = node->value;
00947         if (!(tree->mode & COLLECTION_MODE_MULTIPLE_VALUES))
00948             tree->items--;
00949         else
00950             tree->items -= cp_vector_size((cp_vector *) res);
00951 
00952         if (node->right && node->left)
00953         {
00954             cp_rbnode *surrogate = node;
00955             node = node->right;
00956             while (node->left) node = node->left;
00957             swap_node_content(node, surrogate);
00958         }
00959         child = node->right ? node->right : node->left;
00960 
00961         /* if the node was red - no rebalancing required */
00962         if (node->color == RB_BLACK)
00963         {
00964             if (child)
00965             {
00966                 /* single red child - paint it black */
00967                 if (child->color == RB_RED)
00968                     child->color = RB_BLACK; /* and the balance is restored */
00969                 else
00970                     delete_rebalance(tree, child);
00971             }
00972             else 
00973                 delete_rebalance(tree, node);
00974         }
00975 
00976         rb_unlink(tree, node);
00977         cp_rbtree_destroy_node(tree, node);
00978     }
00979 
00980     return res;
00981 }
00982 
00983 /* cp_rbtree_delete - deletes the value mapped to the given key from the tree
00984  * and returns the value removed. 
00985  */
00986 void *cp_rbtree_delete(cp_rbtree *tree, void *key)
00987 {
00988     void *res = NULL;
00989 
00990     if (cp_rbtree_txlock(tree, COLLECTION_LOCK_WRITE)) return NULL;
00991 
00992     res = cp_rbtree_delete_impl(tree, key);
00993 
00994     cp_rbtree_txunlock(tree);
00995     return res;
00996 }
00997 
00998 /* if using COLLECTION_MODE_MULTIPLE_VALUES, use cp_rbtree_delete_mapping to
00999  * remove a specific mapping. cp_rbtree_delete will delete all mappings for
01000  * the given key.
01001  */
01002 void *cp_rbtree_delete_mapping(cp_rbtree *tree, cp_mapping *mapping)
01003 {
01004     void *res = NULL;
01005 
01006     if (cp_rbtree_txlock(tree, COLLECTION_LOCK_WRITE)) return NULL;
01007     
01008     res = cp_rbtree_delete_mapping_impl(tree, mapping);
01009 
01010     cp_rbtree_txunlock(tree);
01011     return res;
01012 }
01013 
01014 static int 
01015     rb_scan_pre_order(cp_rbnode *node, cp_callback_fn callback, void *prm)
01016 {
01017     int rc;
01018     
01019     if (node) 
01020     {
01021         if ((rc = (*callback)(node, prm))) return rc;
01022         if ((rc = rb_scan_pre_order(node->left, callback, prm))) return rc;
01023         if ((rc = rb_scan_pre_order(node->right, callback, prm))) return rc;
01024     }
01025 
01026     return 0;
01027 }
01028 
01029 int cp_rbtree_callback_preorder(cp_rbtree *tree, 
01030                                 cp_callback_fn callback, 
01031                                 void *prm)
01032 {
01033     int rc;
01034 
01035     if ((rc = cp_rbtree_txlock(tree, COLLECTION_LOCK_READ))) return rc;
01036     rc = rb_scan_pre_order(tree->root, callback, prm);
01037     cp_rbtree_txunlock(tree);
01038 
01039     return rc;
01040 }
01041 
01042 static int 
01043     rb_scan_in_order(cp_rbnode *node, cp_callback_fn callback, void *prm)
01044 {
01045     int rc;
01046     
01047     if (node) 
01048     {
01049         if ((rc = rb_scan_in_order(node->left, callback, prm))) return rc;
01050         if ((rc = (*callback)(node, prm))) return rc;
01051         if ((rc = rb_scan_in_order(node->right, callback, prm))) return rc;
01052     }
01053 
01054     return 0;
01055 }
01056 
01057 int cp_rbtree_callback(cp_rbtree *tree, cp_callback_fn callback, void *prm)
01058 {
01059     int rc;
01060 
01061     if ((rc = cp_rbtree_txlock(tree, COLLECTION_LOCK_READ))) return rc;
01062     rc = rb_scan_in_order(tree->root, callback, prm);
01063     cp_rbtree_txunlock(tree);
01064 
01065     return rc;
01066 }
01067 
01068 static int 
01069     rb_scan_post_order(cp_rbnode *node, cp_callback_fn callback, void *prm)
01070 {
01071     int rc;
01072     
01073     if (node) 
01074     {
01075         if ((rc = rb_scan_post_order(node->left, callback, prm))) return rc;
01076         if ((rc = rb_scan_post_order(node->right, callback, prm))) return rc;
01077         if ((rc = (*callback)(node, prm))) return rc;
01078     }
01079 
01080     return 0;
01081 }
01082 
01083 int cp_rbtree_callback_postorder(cp_rbtree *tree, 
01084                                  cp_callback_fn callback, 
01085                                  void *prm)
01086 {
01087     int rc;
01088 
01089     if ((rc = cp_rbtree_txlock(tree, COLLECTION_LOCK_READ))) return rc;
01090     rc = rb_scan_post_order(tree->root, callback, prm);
01091     cp_rbtree_txunlock(tree);
01092 
01093     return rc;
01094 }
01095 
01096 int cp_rbtree_count(cp_rbtree *tree)
01097 {
01098     return tree->items;
01099 }
01100 
01101 
01102 void cp_rbnode_print(cp_rbnode *node, int level)
01103 {
01104     int i;
01105     if (node->right) cp_rbnode_print(node->right, level + 1);
01106     for (i = 0; i < level; i++) printf("  . ");
01107     printf("(%d) [%s => %s]\n", node->color, (char *) node->key, (char *) node->value);
01108     if (node->left) cp_rbnode_print(node->left, level + 1);
01109 }
01110 
01111 void cp_rbnode_multi_print(cp_rbnode *node, int level)
01112 {
01113     int i;
01114     cp_vector *v = node->value;
01115     if (node->right) cp_rbnode_multi_print(node->right, level + 1);
01116     
01117     for (i = 0; i < level; i++) printf("  . ");
01118     printf("(%d) [%s => ", node->color, (char *) node->key);
01119 
01120     for (i = 0; i < cp_vector_size(v); i++)
01121         printf("%s; ", (char *) cp_vector_element_at(v, i));
01122 
01123     printf("]\n");
01124 
01125     if (node->left) cp_rbnode_multi_print(node->left, level + 1);
01126 }
01127 
01128 void cp_rbtree_dump(cp_rbtree *tree)
01129 {
01130     if (tree->root) 
01131     {
01132         if ((tree->mode & COLLECTION_MODE_MULTIPLE_VALUES))
01133             cp_rbnode_multi_print(tree->root, 0);
01134         else
01135             cp_rbnode_print(tree->root, 0);
01136     }
01137 }
01138 
01139 /* set tree to use given mempool or allocate a new one if pool is NULL */
01140 int cp_rbtree_use_mempool(cp_rbtree *tree, cp_mempool *pool)
01141 {
01142     int rc = 0;
01143     
01144     if ((rc = cp_rbtree_txlock(tree, COLLECTION_LOCK_WRITE))) return rc;
01145     
01146     if (pool)
01147     {
01148         if (pool->item_size < sizeof(cp_rbnode))
01149         {
01150             rc = EINVAL;
01151             goto DONE;
01152         }
01153         if (tree->mempool) 
01154         {
01155             if (tree->items) 
01156             {
01157                 rc = ENOTEMPTY;
01158                 goto DONE;
01159             }
01160             cp_mempool_destroy(tree->mempool);
01161         }
01162         cp_mempool_inc_refcount(pool);
01163         tree->mempool = pool;
01164     }
01165     else
01166     {
01167         tree->mempool = 
01168             cp_mempool_create_by_option(COLLECTION_MODE_NOSYNC, 
01169                                         sizeof(cp_rbnode), 0);
01170         if (tree->mempool == NULL) 
01171         {
01172             rc = ENOMEM;
01173             goto DONE;
01174         }
01175     }
01176 
01177 DONE:
01178     cp_rbtree_txunlock(tree);
01179     return rc;
01180 }
01181 
01182 
01183 /* set tree to use a shared memory pool */
01184 int cp_rbtree_share_mempool(cp_rbtree *tree, cp_shared_mempool *pool)
01185 {
01186     int rc;
01187 
01188     if ((rc = cp_rbtree_txlock(tree, COLLECTION_LOCK_WRITE))) return rc;
01189 
01190     if (tree->mempool)
01191     {
01192         if (tree->items)
01193         {
01194             rc = ENOTEMPTY;
01195             goto DONE;
01196         }
01197 
01198         cp_mempool_destroy(tree->mempool);
01199     }
01200 
01201     tree->mempool = cp_shared_mempool_register(pool, sizeof(cp_rbnode));
01202     if (tree->mempool == NULL) 
01203     {
01204         rc = ENOMEM;
01205         goto DONE;
01206     }
01207     
01208 DONE:
01209     cp_rbtree_txunlock(tree);
01210     return rc;
01211 }
01212 

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