multimap.c

00001 #include <stdio.h>
00002 #include <stdlib.h>
00003 #include <string.h>
00004 #include <errno.h>
00005 
00006 #include "collection.h"
00007 #include "vector.h"
00008 #include "multimap.h"
00009 
00010 cp_index_map_node *
00011     cp_index_map_node_create(void *entry, cp_mempool *pool)
00012 {
00013     cp_index_map_node *node;
00014     
00015     if (pool) 
00016         node = (cp_index_map_node *) cp_mempool_calloc(pool);
00017     else
00018         node = (cp_index_map_node *) calloc(1, sizeof(cp_index_map_node));
00019 
00020     if (node == NULL) return NULL;
00021 
00022     node->entry = entry;
00023 
00024     return node;
00025 }
00026     
00027 /* implement COLLECTION_MODE_MULTIPLE_VALUES if set */
00028 static cp_index_map_node *
00029     create_index_map_node(cp_index_map *tree, void *entry)
00030 {
00031     if ((tree->mode & COLLECTION_MODE_MULTIPLE_VALUES))
00032     {
00033         cp_vector *m = cp_vector_create(1);
00034         if (m == NULL) return NULL;
00035         cp_vector_add_element(m, entry);
00036         return cp_index_map_node_create(m, tree->owner->mempool);
00037     }
00038     else 
00039         return cp_index_map_node_create(entry, tree->owner->mempool);
00040 
00041     return NULL;
00042 }
00043 
00044 void cp_index_map_destroy_node(cp_index_map *tree, cp_index_map_node *node)
00045 {
00046     if (node)
00047     {
00048         if (node->entry)
00049         {
00050             if ((tree->mode & COLLECTION_MODE_DEEP))
00051             {
00052                 if ((tree->mode & COLLECTION_MODE_MULTIPLE_VALUES))
00053                     cp_vector_destroy_custom(node->entry, tree->owner->dtr);
00054                 else if (tree->owner->dtr) 
00055                     (*tree->owner->dtr)(node->entry);
00056             }
00057             else if ((tree->mode & COLLECTION_MODE_MULTIPLE_VALUES))
00058                 cp_vector_destroy(node->entry);
00059         }
00060 
00061         if (tree->owner->mempool)
00062             cp_mempool_free(tree->owner->mempool, node);
00063         else
00064             free(node);
00065     }
00066 }
00067 
00068 void cp_index_map_drop_node(cp_index_map *tree, cp_index_map_node *node)
00069 {
00070     if (node)
00071     {
00072         if (tree->mode & COLLECTION_MODE_MULTIPLE_VALUES && node->entry)
00073             cp_vector_destroy(node->entry);
00074 
00075         if (tree->owner->mempool)
00076             cp_mempool_free(tree->owner->mempool, node);
00077         else
00078             free(node);
00079     }
00080 }
00081 
00082 void cp_index_map_drop_node_deep(cp_index_map *tree, cp_index_map_node *node)
00083 {
00084     if (node)
00085     {
00086         if (node->left) 
00087             cp_index_map_drop_node_deep(tree, node->left);
00088         if (node->right)
00089             cp_index_map_drop_node_deep(tree, node->right);
00090         cp_index_map_drop_node(tree, node);
00091     }
00092 }
00093 
00094 void cp_index_map_destroy_ref(cp_index_map *tree)
00095 {
00096     cp_index_map_drop_node_deep(tree, tree->root);
00097     free(tree);
00098 }
00099 
00100 void cp_index_map_destroy_node_deep(cp_index_map *owner, 
00101                                     cp_index_map_node *node)
00102 {
00103     while (node)
00104     {
00105         if (node->right)
00106         {
00107             node = node->right;
00108             node->up->right = NULL;
00109         }
00110         else if (node->left)
00111         {
00112             node = node->left;
00113             node->up->left = NULL;
00114         }
00115         else
00116         {
00117             cp_index_map_node *tmp = node;
00118             node = node->up;
00119             cp_index_map_destroy_node(owner, tmp);
00120         }
00121     }
00122 }
00123 
00124 void cp_index_map_destroy(cp_index_map *tree)
00125 {
00126     if (tree)
00127     {
00128         cp_index_map_destroy_node_deep(tree, tree->root);
00129         free(tree);
00130     }
00131 }
00132 
00133 void *cp_index_map_insert(cp_index_map *tree, void *entry);
00134 
00135 cp_multimap *
00136     cp_multimap_create_by_option(int mode, cp_key_fn key, 
00137                                  cp_compare_fn cmp, cp_copy_fn copy, 
00138                                  cp_destructor_fn dtr)
00139 {
00140     int default_map_mode;
00141     cp_multimap *map = (cp_multimap *) calloc(1, sizeof(cp_multimap));
00142     if (map == NULL) goto CREATE_ERROR;
00143 
00144     if (!(mode & COLLECTION_MODE_NOSYNC))
00145     {
00146         map->lock = (cp_lock *) malloc(sizeof(cp_lock));
00147         if (map->lock == NULL) goto CREATE_ERROR;
00148 
00149         if (cp_lock_init(map->lock, NULL) != 0) goto CREATE_ERROR;
00150     }
00151 
00152     map->mode = mode;
00153 
00154     map->copy = copy;
00155     map->dtr = dtr;
00156 
00157     map->default_index.type = 
00158         (mode & COLLECTION_MODE_MULTIPLE_VALUES) ? CP_MULTIPLE : CP_UNIQUE;
00159     map->default_index.key = key;
00160     map->default_index.cmp = cmp;
00161 
00162     default_map_mode = 
00163         (mode & COLLECTION_MODE_MULTIPLE_VALUES) ? (mode & ~(COLLECTION_MODE_COPY | COLLECTION_MODE_DEEP)) : mode;
00164 
00165     map->default_map = 
00166         cp_index_map_create(map, default_map_mode , &map->default_index);
00167     if (map->default_map == NULL) goto CREATE_ERROR;
00168 
00169     map->index = 
00170         cp_hashlist_create_by_option(COLLECTION_MODE_NOSYNC | 
00171                                      COLLECTION_MODE_DEEP, 
00172                                      3, 
00173                                      cp_hash_addr, cp_hash_compare_addr, 
00174                                      (cp_copy_fn) cp_index_copy, free, 
00175                                      NULL, 
00176                                      (cp_destructor_fn) 
00177                                         cp_index_map_destroy_ref);
00178     if (map->index == NULL) goto CREATE_ERROR;
00179 
00180     if (mode & COLLECTION_MODE_MULTIPLE_VALUES)
00181     {
00182         cp_index *primary_index = (cp_index *) calloc(1, sizeof(cp_index));
00183         if (primary_index == NULL) goto CREATE_ERROR;
00184         primary_index->type = CP_UNIQUE;
00185         primary_index->key = NULL;
00186         primary_index->cmp = cp_hash_compare_addr;
00187         map->primary = 
00188             cp_index_map_create(map, 
00189                                 mode & ~(COLLECTION_MODE_MULTIPLE_VALUES), 
00190                                 primary_index);
00191         if (map->primary == NULL) 
00192         {
00193             free(primary_index);
00194             goto CREATE_ERROR;
00195         }
00196 
00197         cp_hashlist_append(map->index, &map->default_index, map->default_map);
00198     }
00199     else
00200         map->primary = map->default_map;
00201 
00202     return map;
00203 
00204 CREATE_ERROR:
00205     if (map)
00206     {
00207         if ((map->mode & COLLECTION_MODE_MULTIPLE_VALUES) &&
00208             map->primary != NULL)
00209             cp_index_map_destroy(map->primary);
00210         if (map->default_map) cp_index_map_destroy(map->default_map);
00211         if (map->index) cp_hashlist_destroy(map->index);
00212         if (map->lock) cp_lock_destroy(map->lock);
00213         free(map);
00214     }
00215     return NULL;
00216 }
00217 
00218 cp_multimap *cp_multimap_create(cp_key_fn key_fn, cp_compare_fn cmp)
00219 {
00220     return cp_multimap_create_by_option(0, key_fn, cmp, NULL, NULL);
00221 }
00222 
00223 void cp_multimap_destroy(cp_multimap *map)
00224 {
00225     if (map)
00226     {
00227         cp_hashlist_remove_by_option(map->index, &map->default_index, COLLECTION_MODE_NOSYNC);
00228         if ((map->mode & COLLECTION_MODE_MULTIPLE_VALUES))
00229         {
00230             free(map->primary->index);
00231 //          cp_hashlist_remove_by_option(map->index, &map->default_index, COLLECTION_MODE_NOSYNC);
00232             cp_hashlist_destroy(map->index);
00233             if (map->default_map) cp_index_map_destroy_ref(map->default_map);
00234         }
00235         else
00236         {
00237             if (map->index) cp_hashlist_destroy(map->index);
00238         }
00239         if (map->primary) cp_index_map_destroy(map->primary);
00240         if (map->lock) cp_lock_destroy(map->lock);
00241         free(map);
00242     }
00243 }
00244 
00245 void cp_multimap_destroy_custom(cp_multimap *map, cp_destructor_fn dtr)
00246 {
00247     if (map)
00248     {
00249         map->dtr = dtr;
00250         cp_multimap_destroy(map);
00251     }
00252 }
00253 
00254 cp_index_map *
00255     cp_index_map_create(cp_multimap *owner, int mode, cp_index *index)
00256 {
00257     cp_index_map *tree;
00258 
00259     if (index == NULL) return NULL;
00260 
00261     tree = calloc(1, sizeof(cp_index_map));
00262     if (tree == NULL) return NULL;
00263 
00264     tree->index = index;
00265     tree->mode = mode;
00266 
00267     tree->owner = owner;
00268 
00269     return tree;
00270 }
00271 
00272 void cp_index_map_destroy_custom(cp_index_map *tree, cp_destructor_fn dtr)
00273 {
00274     tree->mode |= COLLECTION_MODE_DEEP;
00275     tree->owner->dtr = dtr;
00276     cp_index_map_destroy(tree);
00277 }
00278 
00279 static int cp_multimap_lock_internal(cp_multimap *map, int type)
00280 {
00281     int rc;
00282 
00283     switch (type)
00284     {
00285         case COLLECTION_LOCK_READ:
00286             rc = cp_lock_rdlock(map->lock);
00287             break;
00288 
00289         case COLLECTION_LOCK_WRITE:
00290             rc = cp_lock_wrlock(map->lock);
00291             break;
00292 
00293         case COLLECTION_LOCK_NONE:
00294             rc = 0;
00295             break;
00296 
00297         default:
00298             rc = EINVAL;
00299             break;
00300     }
00301 
00302     /* api functions may rely on errno to report locking failure */
00303     if (rc) errno = rc;
00304 
00305     return rc;
00306 }
00307 
00308 static int cp_multimap_unlock_internal(cp_multimap *map)
00309 {
00310     return cp_lock_unlock(map->lock);
00311 }
00312 
00313 int cp_multimap_txlock(cp_multimap *map, int type)
00314 {
00315     /* clear errno to allow client code to distinguish between a NULL return
00316      * value indicating the map doesn't contain the requested value and NULL
00317      * on locking failure in map operations
00318      */
00319     if (map->mode & COLLECTION_MODE_NOSYNC) return 0;
00320     if ((map->mode & COLLECTION_MODE_IN_TRANSACTION) && 
00321         map->txtype == COLLECTION_LOCK_WRITE)
00322     {
00323         cp_thread self = cp_thread_self();
00324         if (cp_thread_equal(self, map->txowner)) return 0;
00325     }
00326     errno = 0;
00327     return cp_multimap_lock_internal(map, type);
00328 }
00329 
00330 int cp_multimap_txunlock(cp_multimap *map)
00331 {
00332     if (map->mode & COLLECTION_MODE_NOSYNC) return 0;
00333     if ((map->mode & COLLECTION_MODE_IN_TRANSACTION) && 
00334         map->txtype == COLLECTION_LOCK_WRITE)
00335     {
00336         cp_thread self = cp_thread_self();
00337         if (cp_thread_equal(self, map->txowner)) return 0;
00338     }
00339     return cp_multimap_unlock_internal(map);
00340 }
00341 
00342 /* lock and set the transaction indicators */
00343 int cp_multimap_lock(cp_multimap *map, int type)
00344 {
00345     int rc;
00346     if ((map->mode & COLLECTION_MODE_NOSYNC)) return EINVAL;
00347     if ((rc = cp_multimap_lock_internal(map, type))) return rc;
00348     map->txtype = type;
00349     map->txowner = cp_thread_self();
00350     map->mode |= COLLECTION_MODE_IN_TRANSACTION;
00351     return 0;
00352 }
00353 
00354 /* unset the transaction indicators and unlock */
00355 int cp_multimap_unlock(cp_multimap *map)
00356 {
00357     cp_thread self = cp_thread_self();
00358     if (map->txowner == self)
00359     {
00360         map->txowner = 0;
00361         map->txtype = 0;
00362         map->mode ^= COLLECTION_MODE_IN_TRANSACTION;
00363     }
00364     else if (map->txtype == COLLECTION_LOCK_WRITE)
00365         return -1;
00366     return cp_multimap_unlock_internal(map);
00367 }
00368 
00369 /* set mode bits on the map mode indicator */
00370 int cp_multimap_set_mode(cp_multimap *map, int mode)
00371 {
00372     int rc;
00373     int nosync; 
00374 
00375     /* can't set NOSYNC in the middle of a transaction */
00376     if ((map->mode & COLLECTION_MODE_IN_TRANSACTION) && 
00377         (mode & COLLECTION_MODE_NOSYNC)) return EINVAL;
00378     /* COLLECTION_MODE_MULTIPLE_VALUES must be set at creation time */    
00379     if ((mode & COLLECTION_MODE_MULTIPLE_VALUES)) return EINVAL;
00380 
00381     if ((rc = cp_multimap_txlock(map, COLLECTION_LOCK_WRITE))) return rc;
00382     
00383     nosync = map->mode & COLLECTION_MODE_NOSYNC;
00384 
00385     map->mode |= mode;
00386 
00387     if (!nosync)
00388         cp_multimap_txunlock(map);
00389 
00390     return 0;
00391 }
00392 
00393 /* unset mode bits on the map mode indicator. if unsetting 
00394  * COLLECTION_MODE_NOSYNC and the map was not previously synchronized, the 
00395  * internal synchronization structure is initialized.
00396  */
00397 int cp_multimap_unset_mode(cp_multimap *map, int mode)
00398 {
00399     int rc;
00400     int nosync;
00401 
00402     /* COLLECTION_MODE_MULTIPLE_VALUES can't be unset */
00403     if ((mode & COLLECTION_MODE_MULTIPLE_VALUES)) return EINVAL;
00404 
00405     if ((rc = cp_multimap_txlock(map, COLLECTION_LOCK_WRITE))) return rc;
00406     
00407     nosync = map->mode & COLLECTION_MODE_NOSYNC;
00408 
00409     /* handle the special case of unsetting COLLECTION_MODE_NOSYNC */
00410     if ((mode & COLLECTION_MODE_NOSYNC) && map->lock == NULL)
00411     {
00412         /* map can't be locked in this case, no need to unlock on failure */
00413         if ((map->lock = malloc(sizeof(cp_lock))) == NULL)
00414             return -1;
00415         if (cp_lock_init(map->lock, NULL))
00416             return -1;
00417     }
00418     
00419     /* unset specified bits */
00420     map->mode &= map->mode ^ mode;
00421     if (!nosync)
00422         cp_multimap_txunlock(map);
00423 
00424     return 0;
00425 }
00426 
00427 int cp_multimap_get_mode(cp_multimap *map)
00428 {
00429     return map->mode;
00430 }
00431 
00432 
00433 static cp_index_map_node *sibling(cp_index_map_node *node)
00434 {
00435     return (node->up != NULL ) && (node == node->up->left) ? 
00436         node->up->right : node->up->left;
00437 }
00438 
00439 static int is_right_child(cp_index_map_node *node)
00440 {
00441     return (node->up->right == node);
00442 }
00443 
00444 static int is_left_child(cp_index_map_node *node)
00445 {
00446     return (node->up->left == node);
00447 }
00448 
00449 /*         left rotate
00450  *
00451  *    (P)                (Q)
00452  *   /   \              /   \
00453  *  1    (Q)    ==>   (P)    3
00454  *      /   \        /   \
00455  *     2     3      1     2
00456  *
00457  */
00458 static void left_rotate(cp_index_map *tree, cp_index_map_node *p)
00459 {
00460     cp_index_map_node *q = p->right;
00461     cp_index_map_node **sup;
00462     
00463     if (p->up)
00464         sup = is_left_child(p) ? &(p->up->left) : &(p->up->right);
00465     else
00466         sup = &tree->root;
00467 
00468     p->right = q->left;
00469     if (p->right) p->right->up = p;
00470     q->left = p;
00471     q->up = p->up;
00472     p->up = q;
00473     *sup = q;
00474 }
00475 
00476 /*           right rotate
00477  *  
00478  *       (P)                (Q)
00479  *      /   \              /   \
00480  *    (Q)    3    ==>     1    (P)  
00481  *   /   \                    /   \
00482  *  1     2                  2     3
00483  *
00484  */
00485 static void right_rotate(cp_index_map *tree, cp_index_map_node *p)
00486 {
00487     cp_index_map_node *q = p->left;
00488     cp_index_map_node **sup;
00489     
00490     if (p->up)
00491         sup = is_left_child(p) ? &(p->up->left) : &(p->up->right);
00492     else
00493         sup = &tree->root;
00494 
00495     p->left = q->right;
00496     if (p->left) p->left->up = p;
00497     q->right = p;
00498     q->up = p->up;
00499     p->up = q;
00500     *sup = q;
00501 }
00502 
00503 
00504 /*
00505  * newly entered node is RED; check balance recursively as required 
00506  */
00507 static void rebalance(cp_index_map *tree, cp_index_map_node *node)
00508 {
00509     cp_index_map_node *up = node->up;
00510     if (up == NULL || up->color == MM_BLACK) return;
00511     if (sibling(up) && sibling(up)->color == MM_RED)
00512     {
00513         up->color = MM_BLACK;
00514         sibling(up)->color = MM_BLACK;
00515         if (up->up->up)
00516         {
00517             up->up->color = MM_RED;
00518             rebalance(tree, up->up);
00519         }
00520     }
00521     else
00522     {
00523         if (is_left_child(node) && is_right_child(up))
00524         {
00525             right_rotate(tree, up);
00526             node = node->right;
00527         }
00528         else if (is_right_child(node) && is_left_child(up))
00529         {
00530             left_rotate(tree, up);
00531             node = node->left;
00532         }
00533 
00534         node->up->color = MM_BLACK;
00535         node->up->up->color = MM_RED;
00536 
00537         if (is_left_child(node)) 
00538             right_rotate(tree, node->up->up);
00539         else 
00540             left_rotate(tree, node->up->up);
00541     }
00542 }
00543 
00544 void cp_index_map_drop(cp_index_map *tree, void *entry);
00545 
00546 static void 
00547     multimap_swap_secondaries(cp_multimap *map, void *before, void *after)
00548 {
00549     if (map->index)
00550     {
00551         cp_hashlist_iterator itr;
00552         if (cp_hashlist_iterator_init(&itr, map->index, 
00553                                       COLLECTION_LOCK_NONE) == 0)
00554         {
00555             cp_index_map *curr;
00556             while ((curr = (cp_index_map *) 
00557                             cp_hashlist_iterator_next_value(&itr)))
00558                 cp_index_map_drop(curr, before);
00559             cp_hashlist_iterator_release(&itr);
00560         }
00561     }
00562 }
00563 
00564 /* update_index_map_node - implement COLLECTION_MODE_DEEP and 
00565  * COLLECTION_MODE_MULTIPLE_VALUES when inserting a * value for an existing key
00566  */
00567 static void *
00568     update_index_map_node(cp_index_map *tree, 
00569                           cp_index_map_node *node, 
00570                           void *entry)
00571 {
00572     void *before = node->entry;
00573     void *new_entry = entry;
00574         
00575     if (!(tree->mode & COLLECTION_MODE_MULTIPLE_VALUES))
00576         node->entry = new_entry;
00577     else
00578     {
00579         cp_vector_add_element(node->entry, new_entry);
00580         new_entry = node->entry;
00581     }
00582 
00583     /* if this is the primary index, we'll have to iterate through all other
00584      * indices to swap pointers to the new value
00585      */
00586     if (tree->owner->primary == tree && new_entry != before)
00587         multimap_swap_secondaries(tree->owner, before, new_entry);
00588 
00589     if (tree->mode & COLLECTION_MODE_DEEP)
00590     {
00591         if (tree->owner->dtr && !(tree->mode & COLLECTION_MODE_MULTIPLE_VALUES))
00592             (*tree->owner->dtr)(before);
00593     }
00594 
00595     return new_entry;
00596 }
00597 
00598 int cp_index_compare_internal(cp_index *index, void *a, void *b)
00599 {
00600     void *e = NULL;
00601 
00602     if (index->type == CP_UNIQUE)
00603         e = a;
00604     else
00605     {
00606         cp_vector *v = a;
00607         if (v && cp_vector_size(v))
00608             e = cp_vector_element_at(v, 0);
00609 #ifdef DEBUG
00610         else
00611         {
00612             DEBUGMSG("empty multiple value node %p", a);
00613         }
00614 #endif
00615     }
00616 
00617     return index->key ? 
00618         (*index->cmp)((*index->key)(e), (*index->key)(b)) : 
00619         (*index->cmp)(e, b);
00620 }
00621 
00622 
00623 /*
00624  * cp_index_map_insert iterates through the tree, finds where the new node fits
00625  * in, puts it there, then calls rebalance. 
00626  *
00627  * If a mapping for the given key already exists it is replaced unless 
00628  * COLLECTION_MODE_MULTIPLE_VALUES is set, is which case a new mapping is 
00629  * added. By default COLLECTION_MODE_MULTIPLE_VALUES is not set.
00630  */
00631 void *cp_index_map_insert(cp_index_map *tree, void *entry)
00632 {
00633     void *res = NULL;
00634 
00635     if (tree->root == NULL)
00636     {
00637         tree->root = create_index_map_node(tree, entry);
00638         if (tree->root == NULL) 
00639         {
00640             errno = CP_MEMORY_ALLOCATION_FAILURE;
00641             goto DONE;
00642         }
00643         res = tree->root->entry;
00644         tree->root->color = MM_BLACK;
00645     }
00646     else
00647     {
00648         int cmp;
00649         cp_index_map_node **curr = &tree->root;
00650         cp_index_map_node *prev = NULL;
00651 
00652         while (*curr)
00653         {
00654             prev = *curr;
00655             cmp = cp_index_compare_internal(tree->index, (*curr)->entry, entry);
00656             if (cmp > 0)
00657                 curr = &(*curr)->left;
00658             else if (cmp < 0) 
00659                 curr = &(*curr)->right;
00660             else /* replace */
00661             {
00662                 res = update_index_map_node(tree, *curr, entry);
00663                 break;
00664             }
00665         }
00666 
00667         if (*curr == NULL) /* not replacing, create new node */
00668         {
00669             *curr = create_index_map_node(tree, entry);
00670             if (*curr == NULL) goto DONE;
00671             res = (*curr)->entry;
00672             (*curr)->up = prev;
00673             rebalance(tree, *curr);
00674         }
00675     }
00676 
00677 DONE:
00678     return res;
00679 }
00680 
00681 void *cp_index_map_get(cp_index_map *tree, void *entry);
00682 
00683 int cp_multimap_match_unique(cp_multimap *map, 
00684                              void *entry, 
00685                              cp_index **index, 
00686                              void **existing)
00687 {                            
00688     void *res = NULL;
00689     int count = 0;
00690     cp_index_map *idx;
00691     cp_hashlist_iterator itr;
00692 
00693     /* try default index first */
00694     if (map->default_map->index->type == CP_UNIQUE)
00695         if ((res = cp_multimap_get(map, entry))) 
00696     {
00697         if (index) *index = map->default_map->index;
00698         if (existing) *existing = res;
00699         count = 1;
00700     }
00701 
00702     cp_hashlist_iterator_init(&itr, map->index, COLLECTION_LOCK_NONE);
00703     while ((idx = (cp_index_map *) cp_hashlist_iterator_next_value(&itr)))
00704     {
00705         if (idx->index->type == CP_UNIQUE)
00706             if ((res = cp_index_map_get(idx, entry)))
00707             {
00708                 if (count == 0)
00709                 {
00710                     if (index) *index = idx->index;
00711                     if (existing) *existing = res;
00712                 }
00713                 count++;
00714             }
00715     }
00716     cp_hashlist_iterator_release(&itr);
00717 
00718     return count;
00719 }
00720 
00721 void *cp_index_map_delete(cp_index_map *tree, void *entry);
00722 
00723 void *cp_multimap_insert(cp_multimap *map, void *entry, int *err)
00724 {
00725     void *res = NULL;
00726     void *dupl = NULL;
00727     cp_hashlist_iterator *itr = NULL;
00728     cp_hashlist_entry *idx;
00729 
00730     if (cp_multimap_txlock(map, COLLECTION_LOCK_WRITE)) 
00731     {
00732         if (err != NULL) *err = CP_LOCK_FAILED;
00733         return NULL;
00734     }
00735 
00736     if (cp_multimap_match_unique(map, entry, NULL, &res))
00737     {
00738         if (err != NULL) *err = CP_UNIQUE_INDEX_VIOLATION;
00739         goto DONE;
00740     }
00741 
00742     if ((map->mode & COLLECTION_MODE_COPY))
00743     {
00744         dupl = map->copy ? (*map->copy)(entry) : entry;
00745         if (dupl)
00746             entry = dupl;
00747         else
00748             goto INSERT_ERROR;
00749     }
00750 
00751     /* add entry on primary index */
00752     if ((res = cp_index_map_insert(map->primary, entry)) == NULL)
00753     {
00754         if (err != NULL) *err = CP_MEMORY_ALLOCATION_FAILURE;
00755         goto DONE;
00756     }
00757 
00758     /* add entry on secondary indices */
00759     itr = cp_hashlist_create_iterator(map->index, COLLECTION_MODE_NOSYNC);
00760     if (itr == NULL) 
00761     {
00762         if (err != NULL) *err = errno;
00763         map->items++;
00764         goto DONE;
00765     }
00766 
00767     while ((idx = cp_hashlist_iterator_next(itr)))
00768         if (cp_index_map_insert(idx->value, res) == NULL)
00769         {
00770             if (err != NULL) *err = CP_MEMORY_ALLOCATION_FAILURE;
00771             goto INSERT_ERROR;
00772         }
00773 
00774     map->items++;
00775     goto DONE;
00776 
00777 
00778 INSERT_ERROR:
00779     if (itr)
00780     {
00781         cp_hashlist_entry *idx;
00782         while ((idx = cp_hashlist_iterator_prev(itr)))
00783             cp_index_map_drop(idx->value, entry);
00784     }
00785     cp_index_map_delete(map->primary, entry);
00786     if ((dupl != NULL) && (dupl != entry) && map->dtr)
00787         (*map->dtr)(dupl);
00788 
00789 DONE:
00790     if (itr) cp_hashlist_iterator_destroy(itr);
00791     cp_multimap_txunlock(map);
00792     return res;
00793 }
00794 
00795 /* cp_index_map_reindex() repositions an entry being edited in a way that 
00796  * modifies its value in respect to the index maintained by this index map. 
00797  * This function is called by cp_multimap_reindex. 
00798  */
00799 int cp_index_map_reindex(cp_index_map *tree, void *before, void *after)
00800 {
00801     int cmp;
00802     cp_index_map_node **curr;
00803     cp_index_map_node *prev;
00804 
00805     if (tree->root == NULL) 
00806     {
00807 #ifdef DEBUG
00808         DEBUGMSG("can\'t reindex entry at %p", before);
00809 #endif
00810         return -1;
00811     }
00812 
00813     /* remove old entry */
00814     cp_index_map_drop(tree, before);
00815     if (tree->root == NULL)
00816     {
00817         tree->root = create_index_map_node(tree, after);
00818         if (tree->root == NULL) 
00819         {
00820 #ifdef DEBUG
00821             cp_error(CP_MEMORY_ALLOCATION_FAILURE, 
00822                      "can\'t reindex entry at %p", before);
00823 #endif
00824             return -1;
00825         }
00826         tree->root->color = MM_BLACK;
00827         return 0;
00828     }
00829 
00830     /* perform insertion */
00831     curr = &tree->root;
00832     prev = NULL;
00833     while (*curr)
00834     {
00835         prev = *curr;
00836         cmp = cp_index_compare_internal(tree->index, (*curr)->entry, after);
00837         if (cmp > 0)
00838             curr = &(*curr)->left;
00839         else if (cmp < 0) 
00840             curr = &(*curr)->right;
00841         else /* replace */
00842         {
00843             if ((tree->mode & COLLECTION_MODE_MULTIPLE_VALUES) == 0)
00844                 (*curr)->entry = after;
00845             else
00846                 cp_vector_add_element((*curr)->entry, after);
00847             break;
00848         }
00849     }
00850 
00851     if (*curr == NULL) /* not replacing, create new node */
00852     {
00853         *curr = create_index_map_node(tree, after);
00854         if (*curr == NULL) 
00855         {
00856 #ifdef DEBUG
00857             int err = errno;
00858             cp_perror(CP_MEMORY_ALLOCATION_FAILURE, err, 
00859                       "can\'t create new node reindexing %p", before);
00860 #endif
00861             return -1;
00862         }
00863         (*curr)->up = prev;
00864         rebalance(tree, *curr);
00865     }
00866 
00867     return 0;
00868 }
00869 
00870 /* determine which indices need to be refreshed, then swap ``after'' and 
00871  * ``before''
00872  */
00873 int cp_multimap_reindex(cp_multimap *map, void *before, void *after)
00874 {
00875     void *existing;
00876     void *dupl = NULL;
00877     cp_index *index;
00878     int violation_count;
00879 
00880     if (cp_multimap_txlock(map, COLLECTION_LOCK_WRITE)) return CP_LOCK_FAILED;
00881 
00882     violation_count = cp_multimap_match_unique(map, after, &index, &existing);
00883     if (violation_count > 2 || 
00884         (violation_count == 2 && existing != before))
00885     {
00886 #if 0
00887         printf("unique index violation. ciao.\n");
00888         *(char *) 0 = 0;
00889 #endif
00890         return CP_UNIQUE_INDEX_VIOLATION;
00891     }
00892 
00893     if ((map->mode & COLLECTION_MODE_COPY))
00894     {
00895         dupl = map->copy ? (*map->copy)(after) : after;
00896         if (dupl)
00897             after = dupl;
00898         else
00899             goto REINDEX_ERROR;
00900     }
00901 
00902     if (map->index)
00903     {
00904         cp_hashlist_iterator itr;
00905         if (cp_hashlist_iterator_init(&itr, map->index, 
00906                                       COLLECTION_LOCK_NONE) == 0)
00907         {
00908             cp_index_map *curr;
00909             while ((curr = (cp_index_map *) 
00910                             cp_hashlist_iterator_next_value(&itr)))
00911             {
00912                     cp_index_map_reindex(curr, before, after);
00913             }
00914             cp_hashlist_iterator_release(&itr);
00915         }
00916     }
00917 
00918 //  if ((map->mode & COLLECTION_MODE_MULTIPLE_VALUES))
00919 //      cp_index_map_reindex(map->default_map, before, after);
00920 
00921 //  if ((map->mode & COLLECTION_MODE_MULTIPLE_VALUES))
00922     cp_index_map_reindex(map->primary, before, after);
00923 
00924     goto REINDEX_DONE;
00925 
00926 REINDEX_ERROR:
00927     if (dupl && after != dupl && map->dtr) 
00928         (*map->dtr)(dupl);
00929 
00930 REINDEX_DONE:
00931     cp_multimap_txunlock(map);
00932 
00933     return 0;
00934 }
00935 
00936 /* cp_index_map_get - return the value mapped to the given key or NULL if none
00937  * is found. If COLLECTION_MODE_MULTIPLE_VALUES is set the returned value is a
00938  * cp_vector object or NULL if no mapping is found. 
00939  */
00940 void *cp_index_map_get(cp_index_map *tree, void *entry)
00941 {
00942     cp_index_map_node *curr;
00943     void *res = NULL;
00944 
00945     curr = tree->root;
00946     while (curr)
00947     {
00948         int c = cp_index_compare_internal(tree->index, curr->entry, entry);
00949         if (c == 0) return curr->entry;
00950         curr = (c > 0) ? curr->left : curr->right;
00951     }
00952 
00953     if (curr) res = curr->entry;
00954 
00955     return res;
00956 }
00957     
00958 void *cp_multimap_get(cp_multimap *map, void *entry)
00959 {
00960     void *res = NULL;
00961 
00962     if (cp_multimap_txlock(map, COLLECTION_LOCK_READ)) return NULL;
00963     res = cp_index_map_get(map->default_map, entry); 
00964     cp_multimap_txunlock(map);
00965 
00966     return res;
00967 }
00968 
00969 void *cp_index_map_find(cp_index_map *tree, void *entry, cp_op op)
00970 {
00971     int cmp;
00972     cp_index_map_node **curr;
00973     cp_index_map_node *prev;
00974     cp_index_map_node *res = NULL;
00975 
00976     if (tree->root == NULL) return NULL;
00977 
00978     curr = &tree->root;
00979     while (*curr)
00980     {
00981         prev = *curr;
00982         cmp = cp_index_compare_internal(tree->index, (*curr)->entry, entry);
00983 
00984         if (cmp == 0) break;
00985         if (op == CP_OP_NE)
00986         {
00987             res = *curr;
00988             goto FIND_DONE;
00989         }
00990 
00991         if (cmp > 0)
00992             curr = &(*curr)->left;
00993         else 
00994             curr = &(*curr)->right;
00995     }
00996 
00997     if (*curr)
00998     {
00999         if (op == CP_OP_EQ || op == CP_OP_LE || op == CP_OP_GE)
01000         {
01001             res = *curr;
01002             goto FIND_DONE;
01003         }
01004 
01005         if (op == CP_OP_GT)
01006         {
01007             if ((*curr)->right)
01008             {
01009                 curr = &(*curr)->right;
01010                 while ((*curr)->left) curr = &(*curr)->left;
01011                 res = *curr;
01012             }
01013             else
01014             {
01015                 while ((*curr)->up)
01016                 {
01017                     prev = *curr;
01018                     curr = &(*curr)->up;
01019                     if ((*curr)->left == prev)
01020                     {
01021                         res = *curr;
01022                         break;
01023                     }
01024                 }
01025             }
01026         }
01027         else
01028         {
01029             if ((*curr)->left)
01030             {
01031                 curr = &(*curr)->left;
01032                 while ((*curr)->right) curr = &(*curr)->right;
01033                 res = *curr;
01034             }
01035             else
01036             {
01037                 while ((*curr)->up)
01038                 {
01039                     prev = *curr;
01040                     curr = &(*curr)->up;
01041                     if ((*curr)->right == prev)
01042                     {
01043                         res = *curr;
01044                         break;
01045                     }
01046                 }
01047             }
01048         }
01049 
01050         goto FIND_DONE;
01051     }
01052 
01053     /* *curr is NULL */
01054     if (op == CP_OP_EQ) goto FIND_DONE;
01055 
01056     if (op == CP_OP_LT || op == CP_OP_LE)
01057     {
01058         if (curr == &prev->right) 
01059         {
01060             res = prev;
01061             goto FIND_DONE;
01062         }
01063 
01064         while (prev)
01065         {
01066             if (prev->up && prev->up->right == prev)
01067             {
01068                 res = prev->up;
01069                 break;
01070             }
01071             prev = prev->up;
01072         }
01073     } 
01074     else /* op == CP_OP_GE || op == CP_OP_GT */
01075     {
01076         if (curr == &prev->left)
01077         {
01078             res = prev;
01079             goto FIND_DONE;
01080         }
01081 
01082         while (prev)
01083         {
01084             if (prev->up && prev->up->left == prev)
01085             {
01086                 res = prev->up;
01087                 break;
01088             }
01089             prev = prev->up;
01090         }
01091     }
01092 
01093 FIND_DONE:
01094     return res ? res->entry : NULL;
01095 }
01096 
01097 void *cp_multimap_find(cp_multimap *map, void *entry, cp_op op)
01098 {
01099     void *res = NULL;
01100 
01101     if (cp_multimap_txlock(map, COLLECTION_LOCK_READ)) return NULL;
01102     res = cp_index_map_find(map->default_map, entry, op); 
01103     cp_multimap_txunlock(map);
01104 
01105     return res;
01106 }
01107 
01108 void *cp_multimap_find_by_index(cp_multimap *map, 
01109                                 cp_index *index, 
01110                                 void *entry, 
01111                                 cp_op op)
01112 {
01113     void *res = NULL;
01114 
01115     cp_index_map *tree = cp_hashlist_get(map->index, index);
01116     if (tree == NULL)
01117     {
01118 #ifdef DEBUG
01119         cp_error(CP_INVALID_VALUE, 
01120             "request for search by unknown index %p", index);
01121 #endif
01122         return NULL;
01123     }
01124 
01125     if (cp_multimap_txlock(map, COLLECTION_LOCK_READ)) return NULL;
01126     res = cp_index_map_find(tree, entry, op); 
01127     cp_multimap_txunlock(map);
01128 
01129     return res;
01130 }
01131 
01132 
01133 void *cp_multimap_get_by_index(cp_multimap *map, cp_index *index, void *entry)
01134 {
01135     void *res = NULL;
01136     cp_index_map *tree;
01137     if (index == NULL) return cp_multimap_get(map, entry);
01138     
01139     if (cp_multimap_txlock(map, COLLECTION_LOCK_READ)) return NULL;
01140 
01141 #ifdef DEBUG
01142     if (map->index == NULL)
01143     {
01144         DEBUGMSG("no secondary indices set on multimap");
01145         return NULL;
01146     }
01147 #endif /* DEBUG */
01148 
01149     tree = cp_hashlist_get(map->index, index);
01150     if (tree)
01151         res = cp_index_map_get(tree, entry);
01152 #ifdef DEBUG
01153     else
01154         cp_error(CP_INVALID_VALUE, 
01155             "request for lookup by unknown index %p", index);
01156 #endif
01157     cp_multimap_txunlock(map);
01158 
01159     return res;
01160 }
01161 
01162 int cp_index_map_contains(cp_index_map *tree, void *entry)
01163 {
01164     return (cp_index_map_get(tree, entry) != NULL);
01165 }
01166 
01167 /* return non-zero if entry could be found on any index */
01168 CPROPS_DLL
01169 int cp_multimap_contains(cp_multimap *map, void *entry)
01170 {
01171     int res = 0;
01172     cp_index_map *idx;
01173     cp_hashlist_iterator itr;
01174 
01175     /* try default index first */
01176     if (cp_multimap_get(map, entry) != NULL) return 1;
01177 
01178     cp_hashlist_iterator_init(&itr, map->index, COLLECTION_LOCK_NONE);
01179     while ((idx = (cp_index_map *) cp_hashlist_iterator_next_value(&itr)))
01180     {
01181         if (cp_index_map_get(idx, entry) != NULL)
01182         {
01183             res = 1;
01184             break;
01185         }
01186     }
01187     cp_hashlist_iterator_release(&itr);
01188 
01189     return res;
01190 }
01191 
01192 
01193 /* helper function for deletion */
01194 static void swap_node_content(cp_index_map_node *a, cp_index_map_node *b)
01195 {
01196     void *tmp;
01197 
01198     tmp = a->entry;
01199     a->entry = b->entry;
01200     b->entry = tmp;
01201 }
01202 
01203 /*
01204  * helper function for cp_index_map_delete to remove nodes with either a left 
01205  * NULL branch or a right NULL branch
01206  */
01207 static void index_map_unlink(cp_index_map *tree, cp_index_map_node *node)
01208 {
01209     if (node->left)
01210     {
01211         node->left->up = node->up;
01212         if (node->up)
01213         {
01214             if (is_left_child(node))
01215                 node->up->left = node->left;
01216             else
01217                 node->up->right = node->left;
01218         }
01219         else
01220             tree->root = node->left;
01221     }
01222     else
01223     {
01224         if (node->right) node->right->up = node->up;
01225         if (node->up)
01226         {
01227             if (is_left_child(node))
01228                 node->up->left = node->right;
01229             else
01230                 node->up->right = node->right;
01231         }
01232         else
01233             tree->root = node->right;
01234     }
01235 }
01236 
01237 /* delete_rebalance - perform rebalancing after a deletion */
01238 static void delete_rebalance(cp_index_map *tree, cp_index_map_node *n)
01239 {
01240     if (n->up)
01241     {
01242         cp_index_map_node *sibl = sibling(n);
01243 
01244         if (sibl->color == MM_RED)
01245         {
01246             n->up->color = MM_RED;
01247             sibl->color = MM_BLACK;
01248             if (is_left_child(n))
01249                 left_rotate(tree, n->up);
01250             else
01251                 right_rotate(tree, n->up);
01252             sibl = sibling(n);
01253         }
01254 
01255         if (n->up->color == MM_BLACK &&
01256             sibl->color == MM_BLACK &&
01257             (sibl->left == NULL || sibl->left->color == MM_BLACK) &&
01258             (sibl->right == NULL || sibl->right->color == MM_BLACK))
01259         {
01260             sibl->color = MM_RED;
01261             delete_rebalance(tree, n->up);
01262         }
01263         else
01264         {
01265             if (n->up->color == MM_RED &&
01266                 sibl->color == MM_BLACK &&
01267                 (sibl->left == NULL || sibl->left->color == MM_BLACK) &&
01268                 (sibl->right == NULL || sibl->right->color == MM_BLACK))
01269             {
01270                 sibl->color = MM_RED;
01271                 n->up->color = MM_BLACK;
01272             }
01273             else
01274             {
01275                 if (is_left_child(n) && 
01276                     sibl->color == MM_BLACK &&
01277                     sibl->left && sibl->left->color == MM_RED && 
01278                     (sibl->right == NULL || sibl->right->color == MM_BLACK))
01279                 {
01280                     sibl->color = MM_RED;
01281                     sibl->left->color = MM_BLACK;
01282                     right_rotate(tree, sibl);
01283                     
01284                     sibl = sibling(n);
01285                 }
01286                 else if (is_right_child(n) &&
01287                     sibl->color == MM_BLACK &&
01288                     sibl->right && sibl->right->color == MM_RED &&
01289                     (sibl->left == NULL || sibl->left->color == MM_BLACK))
01290                 {
01291                     sibl->color = MM_RED;
01292                     sibl->right->color = MM_BLACK;
01293                     left_rotate(tree, sibl);
01294 
01295                     sibl = sibling(n);
01296                 }
01297 
01298                 sibl->color = n->up->color;
01299                 n->up->color = MM_BLACK;
01300                 if (is_left_child(n))
01301                 {
01302                     sibl->right->color = MM_BLACK;
01303                     left_rotate(tree, n->up);
01304                 }
01305                 else
01306                 {
01307                     sibl->left->color = MM_BLACK;
01308                     right_rotate(tree, n->up);
01309                 }
01310             }
01311         }
01312     }
01313 }
01314 
01315 /* cp_index_map_delete - deletes the value mapped to the given key from the 
01316  * tree and returns the value removed. 
01317  */
01318 void *cp_index_map_delete(cp_index_map *tree, void *entry)
01319 {
01320     void *res = NULL;
01321     cp_index_map_node *node; 
01322     int cmp;
01323 
01324     node = tree->root;
01325     while (node)
01326     {
01327         cmp = cp_index_compare_internal(tree->index, node->entry, entry);
01328         if (cmp > 0)
01329             node = node->left;
01330         else if (cmp < 0)
01331             node = node->right;
01332         else /* found */
01333             break;
01334     }
01335 
01336     if (node) /* may be null if not found */
01337     {
01338         cp_index_map_node *child; 
01339         res = node->entry;
01340 
01341         if (node->right && node->left)
01342         {
01343             cp_index_map_node *surrogate = node;
01344             node = node->right;
01345             while (node->left) node = node->left;
01346             swap_node_content(node, surrogate);
01347         }
01348         child = node->right ? node->right : node->left;
01349 
01350         /* if the node was red - no rebalancing required */
01351         if (node->color == MM_BLACK)
01352         {
01353             if (child)
01354             {
01355                 /* single red child - paint it black */
01356                 if (child->color == MM_RED)
01357                     child->color = MM_BLACK; /* and the balance is restored */
01358                 else
01359                     delete_rebalance(tree, child);
01360             }
01361             else 
01362                 delete_rebalance(tree, node);
01363         }
01364 
01365         index_map_unlink(tree, node);
01366         cp_index_map_destroy_node(tree, node);
01367     }
01368 
01369     return res;
01370 }
01371 
01372 /* drop a single entry. Locate the entry, if it's a multiple mapping iterate
01373  * over multiple values and remove the specified entry only. If operating on
01374  * the default index, implement mode settings, ie destroy node if required.
01375  */
01376 void cp_index_map_drop(cp_index_map *tree, void *entry)
01377 {
01378     cp_index_map_node *node; 
01379     int cmp;
01380 
01381     node = tree->root;
01382     while (node)
01383     {
01384         cmp = cp_index_compare_internal(tree->index, node->entry, entry);
01385         if (cmp > 0)
01386             node = node->left;
01387         else if (cmp < 0)
01388             node = node->right;
01389         else /* found */
01390             break;
01391     }
01392 
01393     if (node) /* may be null if not found */
01394     {
01395         cp_index_map_node *child; 
01396 
01397         /* find the single entry to be removed */
01398         if (tree->index->type == CP_MULTIPLE)
01399         {
01400             int i;
01401             cp_vector *v = node->entry;
01402             int size = cp_vector_size(v);
01403 
01404             for (i = 0; i < size; i++)
01405                 if (cp_vector_element_at(v, i) == entry)
01406                 {
01407                     cp_vector_remove_element_at(v, i);
01408                     break;
01409                 }
01410 
01411 #ifdef DEBUG
01412             if (i == size) 
01413             {
01414                 DEBUGMSG("can\'t find item to remove: entry %p", entry);
01415                 *(char *) 0 = 1;
01416             }
01417 #endif
01418 
01419             /* still more multiple values in this vector, safe to return */
01420             if (cp_vector_size(v)) return;
01421         }
01422 
01423         if (node->right && node->left)
01424         {
01425             cp_index_map_node *surrogate = node;
01426             node = node->right;
01427             while (node->left) node = node->left;
01428             swap_node_content(node, surrogate);
01429         }
01430         child = node->right ? node->right : node->left;
01431 
01432         /* if the node was red - no rebalancing required */
01433         if (node->color == MM_BLACK)
01434         {
01435             if (child)
01436             {
01437                 /* single red child - paint it black */
01438                 if (child->color == MM_RED)
01439                     child->color = MM_BLACK; /* and the balance is restored */
01440                 else
01441                     delete_rebalance(tree, child);
01442             }
01443             else 
01444                 delete_rebalance(tree, node);
01445         }
01446 
01447         index_map_unlink(tree, node);
01448 //      cp_index_map_drop_node(tree, node);        
01449         cp_index_map_destroy_node(tree, node);        
01450     }
01451 }
01452 
01453 /* drop the given entry from all indices */
01454 void cp_multimap_drop(cp_multimap *map, 
01455                       cp_index *index, 
01456                       void *entry)
01457 {
01458     cp_hashlist_iterator *itr = NULL;
01459 
01460     if (map->index) 
01461         itr = cp_hashlist_create_iterator(map->index, COLLECTION_LOCK_NONE);
01462 
01463     if (itr)
01464     {
01465         cp_hashlist_entry *idx;
01466 
01467         while ((idx = cp_hashlist_iterator_next(itr)))
01468             if (idx->key != index && idx->key != &map->primary) 
01469                 cp_index_map_drop(idx->value, entry);
01470 
01471         cp_hashlist_iterator_destroy(itr);
01472     }
01473 
01474     if ((map->mode & COLLECTION_MODE_MULTIPLE_VALUES))
01475         cp_index_map_drop(map->default_map, entry);
01476 
01477     if (index)
01478         cp_index_map_drop(map->primary, entry);
01479 }
01480 
01481 /* delete the entry (or entries) matching the given value by the tree primary
01482  * key. 
01483  */
01484 void *cp_multimap_remove(cp_multimap *map, void *entry)
01485 {
01486     void *res = NULL;
01487     int count = 0;
01488 
01489     if (cp_multimap_txlock(map, COLLECTION_LOCK_WRITE)) return NULL;
01490 
01491     if (map->mode & COLLECTION_MODE_MULTIPLE_VALUES)
01492     {
01493         int i;
01494         cp_vector *v = cp_index_map_get(map->default_map, entry);
01495         if (v)
01496         {
01497             res = v;
01498             count = cp_vector_size(v);
01499             for (i = 0; i < count; i++)
01500             {
01501                 void *element = cp_vector_element_at(v, i);
01502                 cp_multimap_drop(map, NULL, element);
01503                 cp_index_map_delete(map->primary, element);
01504             }
01505         }
01506     }
01507     else
01508     {
01509         void *e = cp_index_map_get(map->primary, entry);
01510         if (e)
01511         {
01512             res = e;
01513             cp_multimap_drop(map, NULL, e);
01514             cp_index_map_delete(map->primary, e);
01515             count = 1;
01516         }
01517     }
01518 
01519     if (count)
01520         map->items -= count;
01521 
01522     cp_multimap_txunlock(map);
01523 
01524     return res;
01525 }
01526 
01527 /* the point in deleting entries by index is when you have multiple values for
01528  * a given entry respective to the given index, and you want to delete them all
01529  * in one go.
01530  */
01531 void *cp_multimap_remove_by_index(cp_multimap *map, 
01532                                   cp_index *index, 
01533                                   void *entry)
01534 {
01535     void *res = NULL;
01536     cp_index_map *lookup;
01537     int count = 0;
01538 
01539     if (index == NULL) 
01540         return cp_multimap_remove(map, entry);
01541 
01542     if (cp_multimap_txlock(map, COLLECTION_LOCK_WRITE)) return NULL;
01543     
01544     if (index != map->primary->index)
01545         lookup = cp_hashlist_get(map->index, index);
01546     else
01547         lookup = map->primary;
01548 
01549 #ifdef DEBUG
01550     if (lookup == NULL)
01551     {
01552         cp_error(CP_INVALID_VALUE, 
01553                  "request for removal by unknown index %p", index);
01554         goto DELETE_DONE;
01555     }
01556 #endif
01557 
01558     if (lookup->mode & COLLECTION_MODE_MULTIPLE_VALUES)
01559     {
01560         int i;
01561         cp_vector *v = cp_index_map_get(lookup, entry);
01562         if (v)
01563         {
01564             res = v;
01565             count = cp_vector_size(v);
01566             for (i = 0; i < count; i++)
01567                 cp_multimap_drop(map, index, cp_vector_element_at(v, i));
01568         }
01569     }
01570     else
01571     {
01572         void *e = cp_index_map_get(lookup, entry);
01573         if (e)
01574         {
01575             cp_index *drop_index = (lookup == map->primary) ? NULL : drop_index;
01576             res = e;
01577             cp_multimap_drop(map, drop_index, e);
01578             count = 1;
01579         }
01580     }
01581 
01582     if (count)
01583     {
01584         cp_index_map_delete(lookup, entry);
01585         map->items -= count;
01586     }
01587     
01588 #ifdef DEBUG
01589 DELETE_DONE:
01590 #endif
01591     cp_multimap_txunlock(map);
01592 
01593     return res;
01594 }
01595 
01596 static int 
01597     index_map_scan_pre_order(cp_index_map_node *node, 
01598                              cp_callback_fn callback, 
01599                              void *prm)
01600 {
01601     int rc;
01602     
01603     if (node) 
01604     {
01605         if ((rc = (*callback)(node, prm))) return rc;
01606         if ((rc = index_map_scan_pre_order(node->left, callback, prm))) return rc;
01607         if ((rc = index_map_scan_pre_order(node->right, callback, prm))) return rc;
01608     }
01609 
01610     return 0;
01611 }
01612 
01613 int cp_multimap_callback_preorder(cp_multimap *map, 
01614                                   cp_callback_fn callback, 
01615                                   void *prm)
01616 {
01617     int rc;
01618 
01619     if ((rc = cp_multimap_txlock(map, COLLECTION_LOCK_READ))) return rc;
01620     rc = index_map_scan_pre_order(map->default_map->root, callback, prm);
01621     cp_multimap_txunlock(map);
01622 
01623     return rc;
01624 }
01625 
01626 static int 
01627     index_map_scan_in_order(cp_index_map_node *node, 
01628                             cp_callback_fn callback, 
01629                             void *prm)
01630 {
01631     int rc;
01632     
01633     if (node) 
01634     {
01635         if ((rc = index_map_scan_in_order(node->left, callback, prm))) return rc;
01636         if ((rc = (*callback)(node, prm))) return rc;
01637         if ((rc = index_map_scan_in_order(node->right, callback, prm))) return rc;
01638     }
01639 
01640     return 0;
01641 }
01642 
01643 int cp_multimap_callback(cp_multimap *map, cp_callback_fn callback, void *prm)
01644 {
01645     int rc;
01646 
01647     if ((rc = cp_multimap_txlock(map, COLLECTION_LOCK_READ))) return rc;
01648     rc = index_map_scan_in_order(map->default_map->root, callback, prm);
01649     cp_multimap_txunlock(map);
01650 
01651     return rc;
01652 }
01653 
01654 int cp_multimap_callback_by_index(cp_multimap *map, 
01655                                   cp_index *index, 
01656                                   cp_callback_fn callback, 
01657                                   void *prm)
01658 {
01659     int rc;
01660     cp_index_map *imap;
01661 
01662     if (index == NULL) return cp_multimap_callback(map, callback, prm);
01663 
01664     if ((rc = cp_multimap_txlock(map, COLLECTION_LOCK_READ))) return rc;
01665 
01666     imap = cp_hashlist_get(map->index, index);
01667     if (imap == NULL) 
01668         rc = -1;
01669     else
01670         rc = index_map_scan_in_order(imap->root, callback, prm);
01671     cp_multimap_txunlock(map);
01672 
01673     return rc;
01674 }
01675 
01676 
01677 
01678 static int 
01679     index_map_scan_post_order(cp_index_map_node *node, cp_callback_fn callback, void *prm)
01680 {
01681     int rc;
01682     
01683     if (node) 
01684     {
01685         if ((rc = index_map_scan_post_order(node->left, callback, prm))) return rc;
01686         if ((rc = index_map_scan_post_order(node->right, callback, prm))) return rc;
01687         if ((rc = (*callback)(node, prm))) return rc;
01688     }
01689 
01690     return 0;
01691 }
01692 
01693 int cp_multimap_callback_postorder(cp_multimap *map, 
01694                                  cp_callback_fn callback, 
01695                                  void *prm)
01696 {
01697     int rc;
01698 
01699     if ((rc = cp_multimap_txlock(map, COLLECTION_LOCK_READ))) return rc;
01700     rc = index_map_scan_post_order(map->default_map->root, callback, prm);
01701     cp_multimap_txunlock(map);
01702 
01703     return rc;
01704 }
01705 
01706 int cp_multimap_count(cp_multimap *tree)
01707 {
01708     return tree->items;
01709 }
01710 
01711 
01712 void cp_index_map_node_print(cp_index_map_node *node, int level)
01713 {
01714     int i;
01715     if (node->right) cp_index_map_node_print(node->right, level + 1);
01716     for (i = 0; i < level; i++) printf("  . ");
01717     printf("(%d) [%s]\n", node->color, (char *) node->entry);
01718     if (node->left) cp_index_map_node_print(node->left, level + 1);
01719 }
01720 
01721 void cp_index_map_node_multi_print(cp_index_map_node *node, int level)
01722 {
01723     int i;
01724     cp_vector *v = node->entry;
01725     if (node->right) cp_index_map_node_multi_print(node->right, level + 1);
01726     
01727     for (i = 0; i < level; i++) printf("  . ");
01728     printf("(%d) [ ", node->color);
01729 
01730     for (i = 0; i < cp_vector_size(v); i++)
01731         printf("%s; ", (char *) cp_vector_element_at(v, i));
01732 
01733     printf("]\n");
01734 
01735     if (node->left) cp_index_map_node_multi_print(node->left, level + 1);
01736 }
01737 
01738 void cp_multimap_dump(cp_multimap *map)
01739 {
01740     if (map->default_map->root) 
01741     {
01742         if ((map->mode & COLLECTION_MODE_MULTIPLE_VALUES))
01743             cp_index_map_node_multi_print(map->default_map->root, 0);
01744         else
01745             cp_index_map_node_print(map->default_map->root, 0);
01746     }
01747 }
01748 
01749 /* set map to use given mempool or allocate a new one if pool is NULL */
01750 int cp_multimap_use_mempool(cp_multimap *map, cp_mempool *pool)
01751 {
01752     int rc = 0;
01753     
01754     if ((rc = cp_multimap_txlock(map, COLLECTION_LOCK_WRITE))) return rc;
01755     
01756     if (pool)
01757     {
01758         if (pool->item_size < sizeof(cp_index_map_node))
01759         {
01760             rc = EINVAL;
01761             goto DONE;
01762         }
01763         if (map->mempool) 
01764         {
01765             if (map->items) 
01766             {
01767                 rc = ENOTEMPTY;
01768                 goto DONE;
01769             }
01770             cp_mempool_destroy(map->mempool);
01771         }
01772         cp_mempool_inc_refcount(pool);
01773         map->mempool = pool;
01774     }
01775     else
01776     {
01777         map->mempool = 
01778             cp_mempool_create_by_option(COLLECTION_MODE_NOSYNC, 
01779                                         sizeof(cp_index_map_node), 0);
01780         if (map->mempool == NULL) 
01781         {
01782             rc = ENOMEM;
01783             goto DONE;
01784         }
01785     }
01786 
01787 DONE:
01788     cp_multimap_txunlock(map);
01789     return rc;
01790 }
01791 
01792 
01793 /* set map to use a shared memory pool */
01794 int cp_multimap_share_mempool(cp_multimap *map, cp_shared_mempool *pool)
01795 {
01796     int rc;
01797 
01798     if ((rc = cp_multimap_txlock(map, COLLECTION_LOCK_WRITE))) return rc;
01799 
01800     if (map->mempool)
01801     {
01802         if (map->items)
01803         {
01804             rc = ENOTEMPTY;
01805             goto DONE;
01806         }
01807 
01808         cp_mempool_destroy(map->mempool);
01809     }
01810 
01811     map->mempool = cp_shared_mempool_register(pool, sizeof(cp_index_map_node));
01812     if (map->mempool == NULL) 
01813     {
01814         rc = ENOMEM;
01815         goto DONE;
01816     }
01817     
01818 DONE:
01819     cp_multimap_txunlock(map);
01820     return rc;
01821 }
01822 
01823 /* add an index */
01824 cp_index *cp_multimap_create_index(cp_multimap *map, 
01825                                    cp_index_type type,
01826                                    cp_key_fn key, 
01827                                    cp_compare_fn cmp,
01828                                    int *err)
01829 {
01830     int mode;
01831     cp_index *res = NULL;
01832     cp_index *desc;
01833     cp_index_map *index;
01834     int rc;
01835 
01836     if ((rc = cp_multimap_txlock(map, COLLECTION_LOCK_WRITE))) 
01837     {
01838         if (err != NULL) *err = rc;
01839         return NULL;
01840     }
01841 
01842     if (map->index == NULL)
01843     {
01844         map->index = 
01845             cp_hashlist_create_by_option(COLLECTION_MODE_NOSYNC |
01846                                          COLLECTION_MODE_DEEP, 3,
01847                                          cp_hash_addr, cp_hash_compare_addr, 
01848                                          NULL, NULL, 
01849                                          NULL, (cp_destructor_fn) free);
01850         if (map->index == NULL)
01851         {
01852             if (err != NULL) *err = CP_MEMORY_ALLOCATION_FAILURE;
01853             return NULL;
01854         }
01855     }
01856     else /* verify that no such index has been registered */
01857     {
01858         int exists = 0;
01859         cp_hashlist_entry *entry;
01860         cp_hashlist_iterator *itr = 
01861             cp_hashlist_create_iterator(map->index, COLLECTION_LOCK_NONE);
01862 
01863         while ((entry = cp_hashlist_iterator_next(itr)))
01864         {
01865             cp_index *curr = (cp_index *) entry->key;
01866             if (curr->key == key && curr->cmp == cmp)
01867             {
01868                 res = curr;
01869                 exists = 1;
01870                 break;
01871             }
01872         }
01873 
01874         cp_hashlist_iterator_destroy(itr);
01875 
01876         if (exists)
01877         {
01878             if (err != NULL) *err = CP_ITEM_EXISTS;
01879             goto DONE;
01880         }
01881     }
01882 
01883     desc = calloc(1, sizeof(cp_index));
01884     if (desc == NULL) 
01885     {
01886         if (err != NULL) *err = CP_MEMORY_ALLOCATION_FAILURE;
01887         goto DONE;
01888     }
01889     desc->type = type;
01890     desc->key = key;
01891     desc->cmp = cmp;
01892 
01893     mode = map->mode & ~(COLLECTION_MODE_COPY | COLLECTION_MODE_DEEP);
01894     if (type == CP_UNIQUE)
01895         mode &= ~COLLECTION_MODE_MULTIPLE_VALUES;
01896     else
01897         mode |= COLLECTION_MODE_MULTIPLE_VALUES;
01898 
01899     index = cp_index_map_create(map, mode, desc);
01900     if (index == NULL) goto DONE;
01901 
01902     if (cp_hashlist_insert(map->index, desc, index)) res = desc;
01903 
01904 DONE:
01905     cp_multimap_txunlock(map);
01906     return res;
01907 }
01908 

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