wtrie.c

00001 #include <stdlib.h>
00002 #include "collection.h"
00003 #include "wtrie.h"
00004 #include "wtab.h"
00005 
00006 /*
00007  * allocate a new node
00008  */
00009 cp_wtrie_node *cp_wtrie_node_new(void *leaf, cp_mempool *pool) 
00010 { 
00011     cp_wtrie_node *node;
00012     if (pool) 
00013         node = (cp_wtrie_node *) cp_mempool_calloc(pool);
00014     else
00015         node = (cp_wtrie_node *) calloc(1, sizeof(cp_wtrie_node)); 
00016     if (node) 
00017     { 
00018         node->others = wtab_new(0); 
00019         node->leaf = leaf; 
00020     } 
00021 
00022     return node; 
00023 } 
00024 
00025 /*
00026  * recursively delete the subtree at node
00027  */
00028 void *cp_wtrie_node_delete(cp_wtrie *grp, cp_wtrie_node *node) 
00029 { 
00030     void *leaf = NULL; 
00031 
00032     if (node) 
00033     { 
00034         wtab_delete_custom(node->others, grp, (wtab_dtr)cp_wtrie_delete_mapping);
00035         leaf = node->leaf; 
00036         if (grp->mempool)
00037             cp_mempool_free(grp->mempool, node);
00038         else
00039             free(node); 
00040     } 
00041 
00042     if (leaf && grp->delete_leaf && grp->mode & COLLECTION_MODE_DEEP)
00043         (*grp->delete_leaf)(leaf);
00044 
00045     return leaf; 
00046 } 
00047 
00048 /* 
00049  * uses the wtab_dtr 'owner' parameter (grp here) to recursively delete 
00050  * sub-nodes
00051  */
00052 void cp_wtrie_delete_mapping(cp_wtrie *grp, wtab_node *map_node)
00053 {
00054     if (map_node)
00055     {
00056         if (map_node->attr) free(map_node->attr);
00057         if (map_node->value) cp_wtrie_node_delete(grp, map_node->value);
00058     }
00059 }
00060 
00061 void cp_wtrie_node_unmap(cp_wtrie *grp, cp_wtrie_node **node) 
00062 { 
00063     cp_wtrie_node_delete(grp, *node); 
00064     *node = NULL; 
00065 } 
00066 
00067 int cp_wtrie_lock_internal(cp_wtrie *grp, int type)
00068 {
00069     int rc = 0;
00070     switch(type)
00071     {
00072         case COLLECTION_LOCK_READ:
00073             rc = cp_lock_rdlock(grp->lock);
00074             break;
00075 
00076         case COLLECTION_LOCK_WRITE:
00077             rc = cp_lock_wrlock(grp->lock);
00078             break;
00079 
00080         case COLLECTION_LOCK_NONE:
00081         default:
00082             break; 
00083     }
00084 
00085     return rc;
00086 }
00087 
00088 int cp_wtrie_unlock_internal(cp_wtrie *grp)
00089 {
00090     return cp_lock_unlock(grp->lock);
00091 }
00092 
00093 int cp_wtrie_txlock(cp_wtrie *grp, int type)
00094 {
00095     if (grp->mode & COLLECTION_MODE_NOSYNC) return 0;
00096     if (grp->mode & COLLECTION_MODE_IN_TRANSACTION && 
00097         grp->txtype == COLLECTION_LOCK_WRITE)
00098     {
00099         cp_thread self = cp_thread_self();
00100         if (cp_thread_equal(self, grp->txowner)) return 0;
00101     }
00102     return cp_wtrie_lock_internal(grp, type);
00103 }
00104 
00105 int cp_wtrie_txunlock(cp_wtrie *grp)
00106 {
00107     if (grp->mode & COLLECTION_MODE_NOSYNC) return 0;
00108     if (grp->mode & COLLECTION_MODE_IN_TRANSACTION && 
00109         grp->txtype == COLLECTION_LOCK_WRITE)
00110     {
00111         cp_thread self = cp_thread_self();
00112         if (cp_thread_equal(self, grp->txowner)) return 0;
00113     }
00114     return cp_wtrie_unlock_internal(grp);
00115 }
00116 
00117 /* lock and set the transaction indicators */
00118 int cp_wtrie_lock(cp_wtrie *grp, int type)
00119 {
00120     int rc;
00121     if ((grp->mode & COLLECTION_MODE_NOSYNC)) return EINVAL;
00122     if ((rc = cp_wtrie_lock_internal(grp, type))) return rc;
00123     grp->txtype = type;
00124     grp->txowner = cp_thread_self();
00125     grp->mode |= COLLECTION_MODE_IN_TRANSACTION;
00126     return 0;
00127 }
00128 
00129 /* unset the transaction indicators and unlock */
00130 int cp_wtrie_unlock(cp_wtrie *grp)
00131 {
00132     cp_thread self = cp_thread_self();
00133     if (grp->txowner == self)
00134     {
00135         grp->txtype = 0;
00136         grp->txowner = 0;
00137         grp->mode ^= COLLECTION_MODE_IN_TRANSACTION;
00138     }
00139     else if (grp->txtype == COLLECTION_LOCK_WRITE)
00140         return -1;
00141     return cp_wtrie_unlock_internal(grp);
00142 }
00143 
00144 /* get the current collection mode */
00145 int cp_wtrie_get_mode(cp_wtrie *grp)
00146 {
00147     return grp->mode;
00148 }
00149 
00150 /* set mode bits on the wtrie mode indicator */
00151 int cp_wtrie_set_mode(cp_wtrie *grp, int mode)
00152 {
00153     int nosync;
00154 
00155     /* can't set NOSYNC in the middle of a transaction */
00156     if ((grp->mode & COLLECTION_MODE_IN_TRANSACTION) && 
00157         (mode & COLLECTION_MODE_NOSYNC)) return EINVAL;
00158     
00159     nosync = grp->mode & COLLECTION_MODE_NOSYNC;
00160     if (!nosync)
00161         if (cp_wtrie_txlock(grp, COLLECTION_LOCK_WRITE))
00162             return -1;
00163 
00164     grp->mode |= mode;
00165 
00166     if (!nosync)
00167         cp_wtrie_txunlock(grp);
00168 
00169     return 0;
00170 }
00171 
00172 /* unset mode bits on the grp mode indicator. if unsetting 
00173  * COLLECTION_MODE_NOSYNC and the grp was not previously synchronized, the 
00174  * internal synchronization structure is initalized.
00175  */
00176 int cp_wtrie_unset_mode(cp_wtrie *grp, int mode)
00177 {
00178     int nosync = grp->mode & COLLECTION_MODE_NOSYNC;
00179 
00180     if (!nosync)
00181         if (cp_wtrie_txlock(grp, COLLECTION_LOCK_WRITE))
00182             return -1;
00183     
00184     /* handle the special case of unsetting COLLECTION_MODE_NOSYNC */
00185     if ((mode & COLLECTION_MODE_NOSYNC) && grp->lock == NULL)
00186     {
00187         /* grp can't be locked in this case, no need to unlock on failure */
00188         if ((grp->lock = malloc(sizeof(cp_lock))) == NULL)
00189             return -1; 
00190         if (cp_lock_init(grp->lock, NULL))
00191             return -1;
00192     }
00193     
00194     /* unset specified bits */
00195     grp->mode &= grp->mode ^ mode;
00196     if (!nosync)
00197         cp_wtrie_txunlock(grp);
00198 
00199     return 0;
00200 }
00201 
00202 
00203 cp_wtrie *cp_wtrie_create_wtrie(int mode,
00204                              cp_copy_fn copy_leaf,
00205                              cp_destructor_fn delete_leaf) 
00206 { 
00207     cp_wtrie *grp = calloc(1, sizeof(cp_wtrie)); 
00208 
00209     if (grp == NULL) return NULL; 
00210     grp->root = cp_wtrie_node_new(NULL, NULL); //~~ what if mempool set later?
00211     if (grp->root == NULL) 
00212     { 
00213         free(grp); 
00214         return NULL; 
00215     } 
00216 
00217     if (!(mode & COLLECTION_MODE_NOSYNC))
00218     {
00219         if ((grp->lock = malloc(sizeof(cp_lock))) == NULL)
00220         {
00221             cp_wtrie_node_delete(grp, grp->root);
00222             free(grp);
00223             return NULL;
00224         }
00225 
00226         if (cp_lock_init(grp->lock, NULL)) 
00227         {
00228             free(grp->lock);
00229             cp_wtrie_node_delete(grp, grp->root);
00230             free(grp); 
00231             return NULL; 
00232         } 
00233     }
00234 
00235     grp->mode = mode;
00236     grp->copy_leaf = copy_leaf;
00237     grp->delete_leaf = delete_leaf;
00238 
00239     return grp; 
00240 } 
00241 
00242 cp_wtrie *cp_wtrie_create(int mode)
00243 {
00244     return cp_wtrie_create_wtrie(mode, NULL, NULL);
00245 }
00246 
00247 /*
00248  * recursively deletes wtrie structure
00249  */
00250 int cp_wtrie_destroy(cp_wtrie *grp) 
00251 { 
00252     int rc = 0; 
00253 
00254     /* no locking is done here. It is the application's responsibility to
00255      * ensure that the wtrie isn't being destroyed while it's still in use
00256      * by other threads.
00257      */
00258     if (grp)
00259     { 
00260         cp_wtrie_node_delete(grp, grp->root); 
00261         if (grp->lock) 
00262         {
00263             rc = cp_lock_destroy(grp->lock); 
00264             free(grp->lock);
00265         }
00266         free(grp); 
00267     } 
00268     else rc = -1; 
00269 
00270     return rc; 
00271 } 
00272 
00273 void *WNODE_STORE(cp_wtrie_node *node, wchar_t *key, cp_wtrie_node *sub)
00274 {
00275     wchar_t *k = wcsdup(key); 
00276     if (k == NULL) return NULL;
00277     return wtab_put(node->others, *k, sub, k);
00278 }
00279 
00280 /*
00281  * since cp_wtrie compresses single child nodes, the following cases are handled
00282  * here. 'abc' etc denote existing path, X marks the spot:
00283  *
00284  * (1) simple case: abc-X         - first mapping for abc
00285  *
00286  * (2) mid-branch:  ab-X-c        - abc already mapped, but ab isn't 
00287  *
00288  * (3) new branch:  ab-X-cd       - the key abcd is already mapped
00289  *                      \          
00290  *                       ef         the key abef is to be added
00291  *
00292  * (4) extending:   abc-de-X      - abc mapped, abcde isn't
00293  * 
00294  * (5) replace:     abc-X         - abc already mapped, just replace leaf  
00295  */
00296 int cp_wtrie_node_store(cp_wtrie *grp, 
00297                        cp_wtrie_node *node, 
00298                        wchar_t *key, 
00299                        void *leaf) 
00300 { 
00301 
00302     wchar_t *next;
00303     wtab_node *map_node;
00304     cp_wtrie_node *sub;
00305 
00306     map_node = WNODE_MATCH(node, key); 
00307 
00308     if (map_node == NULL) /* not mapped - just add it */
00309     { 
00310         sub = cp_wtrie_node_new(leaf, grp->mempool); 
00311         if (WNODE_STORE(node, key, sub) == NULL) return -1; 
00312     } 
00313     else
00314     {
00315         next = map_node->attr;
00316         while (*key && *key == *next) 
00317         {
00318             key++;
00319             next++;
00320         }
00321         
00322         if (*next) /* branch abc, key abx or ab */
00323         {
00324             cp_wtrie_node *old = map_node->value;
00325             if ((sub = cp_wtrie_node_new(NULL, grp->mempool)) == NULL) return -1;
00326             if (WNODE_STORE(sub, next, old) == NULL) return -1;
00327             *next = '\0'; //~~ truncate and realloc - prevent dangling key
00328             map_node->value = sub;
00329             if (*key) /* key abx */
00330             {
00331                 if ((WNODE_STORE(sub, key, 
00332                                 cp_wtrie_node_new(leaf, grp->mempool)) == NULL))
00333                     return -1;
00334             }
00335             else /* key ab */
00336                 sub->leaf = leaf;
00337         }
00338         else if (*key) /* branch abc, key abcde */
00339             return cp_wtrie_node_store(grp, map_node->value, key, leaf);
00340 
00341         else  /* branch abc, key abc */
00342         {
00343             cp_wtrie_node *node = ((cp_wtrie_node *) map_node->value);
00344             if (node->leaf && grp->delete_leaf && 
00345                 grp->mode & COLLECTION_MODE_DEEP)
00346                 (*grp->delete_leaf)(node->leaf);
00347             node->leaf = leaf;
00348         }
00349     }
00350     return 0;
00351 } 
00352 
00353 /*
00354  * wrapper for the recursive insertion - implements collection mode setting
00355  */
00356 int cp_wtrie_add(cp_wtrie *grp, wchar_t *key, void *leaf) 
00357 { 
00358     int rc = 0; 
00359     if ((rc = cp_wtrie_txlock(grp, COLLECTION_LOCK_WRITE))) return rc; 
00360 
00361     if ((grp->mode & COLLECTION_MODE_COPY) && grp->copy_leaf && (leaf != NULL))
00362     {
00363         leaf = (*grp->copy_leaf)(leaf);
00364         if (leaf == NULL) goto DONE;
00365     }
00366 
00367     if (key == NULL) /* map NULL key to root node */
00368     {
00369         if (grp->root->leaf && 
00370                 grp->delete_leaf && grp->mode & COLLECTION_MODE_DEEP)
00371             (*grp->delete_leaf)(grp->root->leaf);
00372         grp->root->leaf = leaf; 
00373     }
00374     else 
00375     {
00376         if ((rc = cp_wtrie_node_store(grp, grp->root, key, leaf)))
00377             goto DONE;
00378     } 
00379 
00380     grp->path_count++; 
00381 
00382 DONE:
00383     cp_wtrie_txunlock(grp);
00384     return rc; 
00385 } 
00386 
00387 /* helper functions for cp_wtrie_remove */
00388 
00389 static wchar_t *mergewcs(wchar_t *s1, wchar_t *s2)
00390 {
00391     wchar_t *s;
00392     int len = wcslen(s1) + wcslen(s2);
00393 
00394     s = (wchar_t *) malloc((len + 1) * sizeof(wchar_t));
00395     if (s == NULL) return NULL;
00396     
00397     wcscpy(s, s1); 
00398     wcscat(s, s2);
00399 
00400     return s;
00401 }
00402 
00403 static wtab_node *get_single_entry(wtab *t)
00404 {
00405     int i;
00406 
00407     for (i = 0; i < t->size; i++)
00408         if (t->table[i]) return t->table[i];
00409 
00410     return NULL;
00411 }
00412 
00413 /*
00414  * removing mappings, the following cases are possible:
00415  * 
00416  * (1) simple case:       abc-X       removing mapping abc
00417  *
00418  * (2) branch:            abc-de-X    removing mapping abcde -
00419  *                           \        mapping abcfg remains, but
00420  *                            fg      junction node abc no longer needed
00421  *
00422  * (3) mid-branch:        abc-X-de    removing mapping abc - mapping abcde
00423  *                                    remains
00424  */
00425 int cp_wtrie_remove(cp_wtrie *grp, wchar_t *key, void **leaf)
00426 {
00427     int rc = 0;
00428     cp_wtrie_node *link = grp->root; 
00429     cp_wtrie_node *prev = NULL;
00430     wchar_t ccurr, cprev = 0;
00431     wtab_node *map_node;
00432     wchar_t *branch;
00433 
00434     if (link == NULL) return 0; /* tree is empty */
00435 
00436     if ((rc = cp_wtrie_txlock(grp, COLLECTION_LOCK_READ))) return rc;
00437  
00438     if (key == NULL) /* as a special case, NULL keys are stored on the root */
00439     {
00440         if (link->leaf)
00441         {
00442             grp->path_count--;
00443             link->leaf = NULL;
00444         }
00445         goto DONE;
00446     }
00447 
00448     /* keep pointers one and two nodes up for merging in cases (2), (3) */
00449     ccurr = *key;
00450     while ((map_node = WNODE_MATCH(link, key)) != NULL) 
00451     {
00452         branch = map_node->attr;
00453  
00454         while (*key && *key == *branch)
00455         {
00456             key++;
00457             branch++;
00458         }
00459         if (*branch) break; /* mismatch */
00460         if (*key == '\0') /* found */
00461         {
00462             wchar_t *attr;
00463             cp_wtrie_node *node = map_node->value;
00464             if (leaf) *leaf = node->leaf;
00465             if (node->leaf)
00466             {
00467                 grp->path_count--;
00468                 rc = 1;
00469                 /* unlink leaf */
00470                 if (grp->delete_leaf && grp->mode & COLLECTION_MODE_DEEP)
00471                     (*grp->delete_leaf)(node->leaf);
00472                 node->leaf = NULL;
00473 
00474                 /* now remove node - case (1) */
00475                 if (wtab_count(node->others) == 0) 
00476                 {
00477                     wtab_remove(link->others, ccurr);
00478                     cp_wtrie_node_unmap(grp, &node);
00479                     
00480                     /* case (2) */
00481                     if (prev &&
00482                         wtab_count(link->others) == 1 && link->leaf == NULL)
00483                     {
00484                         wtab_node *sub2 = wtab_get(prev->others, cprev);
00485                         wtab_node *sub = get_single_entry(link->others);
00486                         attr = mergewcs(sub2->attr, sub->attr);
00487                         if (attr)
00488                         {
00489                             if (WNODE_STORE(prev, attr, sub->value))
00490                             {
00491                                 wtab_remove(link->others, sub->key);
00492                                 cp_wtrie_node_delete(grp, link);
00493                             }
00494                             free(attr);
00495                         }
00496                     }
00497                 }
00498                 else if (wtab_count(node->others) == 1) /* case (3) */
00499                 {
00500                     wtab_node *sub = get_single_entry(node->others);
00501                     attr = mergewcs(map_node->attr, sub->attr);
00502                     if (attr)
00503                     {
00504                         if (WNODE_STORE(link, attr, sub->value))
00505                         {
00506                             wtab_remove(node->others, sub->key);
00507                             cp_wtrie_node_delete(grp, node);
00508                         }
00509                         free(attr);
00510                     }
00511                 }
00512             }
00513             break;
00514         }
00515         
00516         prev = link;
00517         cprev = ccurr;
00518         ccurr = *key;
00519         link = map_node->value; 
00520     } 
00521 
00522 DONE: 
00523     cp_wtrie_txunlock(grp);
00524     return rc;
00525 }
00526 
00527 void *cp_wtrie_exact_match(cp_wtrie *grp, wchar_t *key)
00528 {
00529     void *last = NULL;
00530     cp_wtrie_node *link = grp->root; 
00531     wtab_node *map_node;
00532     wchar_t *branch = NULL;
00533 
00534     if (cp_wtrie_txlock(grp, COLLECTION_LOCK_READ)) return NULL; 
00535  
00536     while ((map_node = WNODE_MATCH(link, key)) != NULL) 
00537     {
00538         branch = map_node->attr;
00539  
00540         while (*key && *key == *branch)
00541         {
00542             key++;
00543             branch++;
00544         }
00545         if (*branch) break; /* mismatch */
00546 
00547         link = map_node->value; 
00548     } 
00549 
00550     if (link) last = link->leaf;
00551 
00552     cp_wtrie_txunlock(grp);
00553  
00554     if (*key == '\0' && branch && *branch == '\0') 
00555         return last;  /* prevent match on super-string keys */
00556     return NULL;
00557 }
00558 
00559 /* return a vector containing exact match and any prefix matches */
00560 cp_vector *cp_wtrie_fetch_matches(cp_wtrie *grp, wchar_t *key)
00561 {
00562     int rc;
00563     cp_vector *res = NULL;
00564     cp_wtrie_node *link = grp->root;
00565     wtab_node *map_node;
00566     wchar_t *branch;
00567 
00568     if ((rc = cp_wtrie_txlock(grp, COLLECTION_LOCK_READ))) return NULL; 
00569  
00570     while ((map_node = WNODE_MATCH(link, key)) != NULL) 
00571     {
00572         branch = map_node->attr;
00573 
00574         while (*key && *key == *branch)
00575         {
00576             key++;
00577             branch++;
00578         }
00579         if (*branch) break; /* mismatch */
00580     
00581         link = map_node->value; 
00582         if (link->leaf)
00583         { 
00584             if (res == NULL)
00585             {
00586                 res = cp_vector_create(1);
00587                 if (res == NULL) break;
00588             }
00589             cp_vector_add_element(res, link->leaf);
00590         } 
00591     }
00592 
00593     cp_wtrie_txunlock(grp);
00594     return res; 
00595 } 
00596 
00597 static void extract_subwtrie(cp_wtrie_node *link, cp_vector *v);
00598 
00599 static int extract_node(void *n, void *v)
00600 {
00601     wtab_node *node = n;
00602 
00603     extract_subwtrie(node->value, v);
00604 
00605     return 0;
00606 }
00607 
00608 static void extract_subwtrie(cp_wtrie_node *link, cp_vector *v)
00609 {
00610     if (link->leaf)
00611         cp_vector_add_element(v, link->leaf);
00612 
00613     if (link->others)
00614         wtab_callback(link->others, extract_node, v);
00615 }
00616 
00617 /* return a vector containing all enwtries in subtree under path given by key */
00618 cp_vector *cp_wtrie_submatch(cp_wtrie *grp, wchar_t *key)
00619 {
00620     int rc;
00621     cp_vector *res = NULL;
00622     cp_wtrie_node *link = grp->root;
00623     wtab_node *map_node;
00624     wchar_t *branch;
00625 
00626     if ((rc = cp_wtrie_txlock(grp, COLLECTION_LOCK_READ))) return NULL; 
00627  
00628     while ((map_node = WNODE_MATCH(link, key)) != NULL) 
00629     {
00630         branch = map_node->attr;
00631 
00632         while (*key && *key == *branch)
00633         {
00634             key++;
00635             branch++;
00636         }
00637 
00638         if (*branch && *key) break; /* mismatch */
00639     
00640         link = map_node->value; 
00641 
00642         if (*key == '\0')
00643         {
00644             res = cp_vector_create(1);
00645             extract_subwtrie(link, res);
00646             break;
00647         }
00648     }
00649 
00650     cp_wtrie_txunlock(grp);
00651     return res; 
00652 } 
00653 
00654 /* return longest prefix match for given key */
00655 int cp_wtrie_prefix_match(cp_wtrie *grp, wchar_t *key, void **leaf)
00656 { 
00657     int rc, match_count = 0; 
00658     void *last = grp->root->leaf; 
00659     cp_wtrie_node *link = grp->root; 
00660     wtab_node *map_node;
00661     wchar_t *branch;
00662 
00663     if ((rc = cp_wtrie_txlock(grp, COLLECTION_LOCK_READ))) return rc; 
00664  
00665     while ((map_node = WNODE_MATCH(link, key)) != NULL) 
00666     { 
00667         branch = map_node->attr;
00668  
00669         while (*key && *key == *branch)
00670         {
00671             key++;
00672             branch++;
00673         }
00674         if (*branch) break; /* mismatch */
00675 
00676         link = map_node->value; 
00677         if (link->leaf)
00678         { 
00679             last = link->leaf; 
00680             match_count++; 
00681         } 
00682     } 
00683 
00684     *leaf = last; 
00685  
00686     cp_wtrie_txunlock(grp);
00687  
00688     return match_count; 
00689 } 
00690 
00691 int cp_wtrie_count(cp_wtrie *grp)
00692 {
00693     return grp->path_count;
00694 }
00695 
00696 void cp_wtrie_set_root(cp_wtrie *grp, void *leaf) 
00697 { 
00698     grp->root->leaf = leaf; 
00699 } 
00700 
00701 /* dump wtrie to stdout - for debugging */
00702 
00703 static int node_count;
00704 static int depth_total;
00705 static int max_level;
00706 
00707 void cp_wtrie_dump_node(cp_wtrie_node *node, int level, char *prefix)
00708 {
00709     int i;
00710     wtab_node *map_node;
00711 
00712     node_count++;
00713     depth_total += level;
00714     if (level > max_level) max_level = level;
00715 
00716     for (i = 0; i < node->others->size; i++)
00717     {
00718         map_node = node->others->table[i];
00719         while (map_node)
00720         {
00721             cp_wtrie_dump_node(map_node->value, level + 1, map_node->attr);
00722             map_node = map_node->next;
00723         }
00724     }
00725 
00726     for (i = 0; i < level; i++) printf("\t");
00727 
00728     printf(" - %s => [%s]\n", prefix, node->leaf ? (char *) node->leaf : "");
00729 }
00730             
00731 void cp_wtrie_dump(cp_wtrie *grp)
00732 {
00733     node_count = 0;
00734     depth_total = 0;
00735     max_level = 0;
00736     
00737     cp_wtrie_dump_node(grp->root, 0, "");
00738 
00739 #ifdef DEBUG
00740     printf("\n %d nodes, %d deepest, avg. depth is %.2f\n\n", 
00741             node_count, max_level, (float) depth_total / node_count);
00742 #endif
00743 }
00744 
00745 /* set wtrie to use given mempool or allocate a new one if pool is NULL */
00746 int cp_wtrie_use_mempool(cp_wtrie *wtrie, cp_mempool *pool)
00747 {
00748     int rc = 0;
00749     
00750     if ((rc = cp_wtrie_txlock(wtrie, COLLECTION_LOCK_WRITE))) return rc;
00751     
00752     if (pool)
00753     {
00754         if (pool->item_size < sizeof(cp_wtrie_node))
00755         {
00756             rc = EINVAL;
00757             goto DONE;
00758         }
00759         if (wtrie->mempool) 
00760         {
00761             if (wtrie->path_count) 
00762             {
00763                 rc = ENOTEMPTY;
00764                 goto DONE;
00765             }
00766             cp_mempool_destroy(wtrie->mempool);
00767         }
00768         cp_mempool_inc_refcount(pool);
00769         wtrie->mempool = pool;
00770     }
00771     else
00772     {
00773         wtrie->mempool = 
00774             cp_mempool_create_by_option(COLLECTION_MODE_NOSYNC, 
00775                                         sizeof(cp_wtrie_node), 0);
00776         if (wtrie->mempool == NULL) 
00777         {
00778             rc = ENOMEM;
00779             goto DONE;
00780         }
00781     }
00782 
00783 DONE:
00784     cp_wtrie_txunlock(wtrie);
00785     return rc;
00786 }
00787 
00788 
00789 /* set wtrie to use a shared memory pool */
00790 int cp_wtrie_share_mempool(cp_wtrie *wtrie, cp_shared_mempool *pool)
00791 {
00792     int rc;
00793 
00794     if ((rc = cp_wtrie_txlock(wtrie, COLLECTION_LOCK_WRITE))) return rc;
00795 
00796     if (wtrie->mempool)
00797     {
00798         if (wtrie->path_count)
00799         {
00800             rc = ENOTEMPTY;
00801             goto DONE;
00802         }
00803 
00804         cp_mempool_destroy(wtrie->mempool);
00805     }
00806 
00807     wtrie->mempool = cp_shared_mempool_register(pool, sizeof(cp_wtrie_node));
00808     if (wtrie->mempool == NULL) 
00809     {
00810         rc = ENOMEM;
00811         goto DONE;
00812     }
00813     
00814 DONE:
00815     cp_wtrie_txunlock(wtrie);
00816     return rc;
00817 }
00818 
00819 

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