rtrie.c

00001 #include <stdlib.h>
00002 #include <errno.h>
00003 #include "collection.h"
00004 #include "rtrie.h"
00005 #include "bstr.h"
00006 
00007 /*
00008  * allocate a new node
00009  */
00010 cp_rtrie_node *cp_rtrie_node_new(void *leaf, cp_mempool *pool) 
00011 { 
00012     cp_rtrie_node *node;
00013     if (pool) 
00014         node = (cp_rtrie_node *) cp_mempool_calloc(pool);
00015     else
00016         node = (cp_rtrie_node *) calloc(1, sizeof(cp_rtrie_node)); 
00017 
00018     if (node) 
00019         node->leaf = leaf; 
00020 
00021     return node; 
00022 } 
00023 
00024 /*
00025  * recursively delete the subtree at node
00026  */
00027 void *cp_rtrie_node_delete(cp_rtrie *grp, cp_rtrie_node *node) 
00028 { 
00029     void *leaf = NULL; 
00030 
00031     if (node) 
00032     { 
00033         if (node->node_zero)
00034             cp_rtrie_node_delete(grp, node->node_zero);
00035         if (node->zero)
00036             cp_bstr_destroy(node->zero);
00037         if (node->node_one)
00038             cp_rtrie_node_delete(grp, node->node_one);
00039         if (node->one)
00040             cp_bstr_destroy(node->one);
00041 
00042         leaf = node->leaf; 
00043         if (grp->mempool)
00044             cp_mempool_free(grp->mempool, node);
00045         else
00046             free(node); 
00047     } 
00048 
00049     if (leaf && grp->delete_leaf && grp->mode & COLLECTION_MODE_DEEP)
00050         (*grp->delete_leaf)(leaf);
00051 
00052     return leaf; 
00053 } 
00054 
00055 /*
00056  * delete just one node (no recursion) 
00057  */
00058 void *cp_rtrie_node_drop(cp_rtrie *grp, cp_rtrie_node *node) 
00059 { 
00060     void *leaf = NULL; 
00061 
00062     if (node) 
00063     { 
00064         if (node->zero)
00065             cp_bstr_destroy(node->zero);
00066         if (node->one)
00067             cp_bstr_destroy(node->one);
00068 
00069         leaf = node->leaf; 
00070         if (grp->mempool)
00071             cp_mempool_free(grp->mempool, node);
00072         else
00073             free(node); 
00074     } 
00075 
00076     if (leaf && grp->delete_leaf && grp->mode & COLLECTION_MODE_DEEP)
00077         (*grp->delete_leaf)(leaf);
00078 
00079     return leaf; 
00080 } 
00081 
00082 void cp_rtrie_node_unmap(cp_rtrie *grp, cp_rtrie_node **node) 
00083 { 
00084     cp_rtrie_node_delete(grp, *node); 
00085     *node = NULL; 
00086 } 
00087 
00088 int cp_rtrie_lock_internal(cp_rtrie *grp, int type)
00089 {
00090     int rc = 0;
00091     switch(type)
00092     {
00093         case COLLECTION_LOCK_READ:
00094             rc = cp_lock_rdlock(grp->lock);
00095             break;
00096 
00097         case COLLECTION_LOCK_WRITE:
00098             rc = cp_lock_wrlock(grp->lock);
00099             break;
00100 
00101         case COLLECTION_LOCK_NONE:
00102         default:
00103             break; 
00104     }
00105 
00106     return rc;
00107 }
00108 
00109 int cp_rtrie_unlock_internal(cp_rtrie *grp)
00110 {
00111     return cp_lock_unlock(grp->lock);
00112 }
00113 
00114 int cp_rtrie_txlock(cp_rtrie *grp, int type)
00115 {
00116     if (grp->mode & COLLECTION_MODE_NOSYNC) return 0;
00117     if (grp->mode & COLLECTION_MODE_IN_TRANSACTION && 
00118         grp->txtype == COLLECTION_LOCK_WRITE)
00119     {
00120         cp_thread self = cp_thread_self();
00121         if (cp_thread_equal(self, grp->txowner)) return 0;
00122     }
00123     return cp_rtrie_lock_internal(grp, type);
00124 }
00125 
00126 int cp_rtrie_txunlock(cp_rtrie *grp)
00127 {
00128     if (grp->mode & COLLECTION_MODE_NOSYNC) return 0;
00129     if (grp->mode & COLLECTION_MODE_IN_TRANSACTION && 
00130         grp->txtype == COLLECTION_LOCK_WRITE)
00131     {
00132         cp_thread self = cp_thread_self();
00133         if (cp_thread_equal(self, grp->txowner)) return 0;
00134     }
00135     return cp_rtrie_unlock_internal(grp);
00136 }
00137 
00138 /* lock and set the transaction indicators */
00139 int cp_rtrie_lock(cp_rtrie *grp, int type)
00140 {
00141     int rc;
00142     if ((grp->mode & COLLECTION_MODE_NOSYNC)) return EINVAL;
00143     if ((rc = cp_rtrie_lock_internal(grp, type))) return rc;
00144     grp->txtype = type;
00145     grp->txowner = cp_thread_self();
00146     grp->mode |= COLLECTION_MODE_IN_TRANSACTION;
00147     return 0;
00148 }
00149 
00150 /* unset the transaction indicators and unlock */
00151 int cp_rtrie_unlock(cp_rtrie *grp)
00152 {
00153     cp_thread self = cp_thread_self();
00154     if (grp->txowner == self)
00155     {
00156         grp->txtype = 0;
00157         grp->txowner = 0;
00158         grp->mode ^= COLLECTION_MODE_IN_TRANSACTION;
00159     }
00160     else if (grp->txtype == COLLECTION_LOCK_WRITE)
00161         return -1;
00162     return cp_rtrie_unlock_internal(grp);
00163 }
00164 
00165 /* get the current collection mode */
00166 int cp_rtrie_get_mode(cp_rtrie *grp)
00167 {
00168     return grp->mode;
00169 }
00170 
00171 /* set mode bits on the rtrie mode indicator */
00172 int cp_rtrie_set_mode(cp_rtrie *grp, int mode)
00173 {
00174     int nosync;
00175 
00176     /* can't set NOSYNC in the middle of a transaction */
00177     if ((grp->mode & COLLECTION_MODE_IN_TRANSACTION) && 
00178         (mode & COLLECTION_MODE_NOSYNC)) return EINVAL;
00179     
00180     nosync = grp->mode & COLLECTION_MODE_NOSYNC;
00181     if (!nosync)
00182         if (cp_rtrie_txlock(grp, COLLECTION_LOCK_WRITE))
00183             return -1;
00184 
00185     grp->mode |= mode;
00186 
00187     if (!nosync)
00188         cp_rtrie_txunlock(grp);
00189 
00190     return 0;
00191 }
00192 
00193 /* unset mode bits on the grp mode indicator. if unsetting 
00194  * COLLECTION_MODE_NOSYNC and the grp was not previously synchronized, the 
00195  * internal synchronization structure is initalized.
00196  */
00197 int cp_rtrie_unset_mode(cp_rtrie *grp, int mode)
00198 {
00199     int nosync = grp->mode & COLLECTION_MODE_NOSYNC;
00200 
00201     if (!nosync)
00202         if (cp_rtrie_txlock(grp, COLLECTION_LOCK_WRITE))
00203             return -1;
00204     
00205     /* handle the special case of unsetting COLLECTION_MODE_NOSYNC */
00206     if ((mode & COLLECTION_MODE_NOSYNC) && grp->lock == NULL)
00207     {
00208         /* grp can't be locked in this case, no need to unlock on failure */
00209         if ((grp->lock = malloc(sizeof(cp_lock))) == NULL)
00210             return -1; 
00211         if (cp_lock_init(grp->lock, NULL))
00212             return -1;
00213     }
00214     
00215     /* unset specified bits */
00216     grp->mode &= grp->mode ^ mode;
00217     if (!nosync)
00218         cp_rtrie_txunlock(grp);
00219 
00220     return 0;
00221 }
00222 
00223 
00224 cp_rtrie *cp_rtrie_create_rtrie(int mode,
00225                              cp_copy_fn copy_leaf,
00226                              cp_destructor_fn delete_leaf) 
00227 { 
00228     cp_rtrie *grp = calloc(1, sizeof(cp_rtrie)); 
00229 
00230     if (grp == NULL) return NULL; 
00231     grp->root = cp_rtrie_node_new(NULL, NULL); //~~ what if mempool set later?
00232     if (grp->root == NULL) 
00233     { 
00234         free(grp); 
00235         return NULL; 
00236     } 
00237 
00238     if (!(mode & COLLECTION_MODE_NOSYNC))
00239     {
00240         if ((grp->lock = malloc(sizeof(cp_lock))) == NULL)
00241         {
00242             cp_rtrie_node_delete(grp, grp->root);
00243             free(grp);
00244             return NULL;
00245         }
00246 
00247         if (cp_lock_init(grp->lock, NULL)) 
00248         {
00249             free(grp->lock);
00250             cp_rtrie_node_delete(grp, grp->root);
00251             free(grp); 
00252             return NULL; 
00253         } 
00254     }
00255 
00256     grp->mode = mode;
00257     grp->copy_leaf = copy_leaf;
00258     grp->delete_leaf = delete_leaf;
00259 
00260     return grp; 
00261 } 
00262 
00263 cp_rtrie *cp_rtrie_create(int mode)
00264 {
00265     return cp_rtrie_create_rtrie(mode, NULL, NULL);
00266 }
00267 
00268 /*
00269  * recursively deletes rtrie structure
00270  */
00271 int cp_rtrie_destroy(cp_rtrie *grp) 
00272 { 
00273     int rc = 0; 
00274 
00275     /* no locking is done here. It is the application's responsibility to
00276      * ensure that the rtrie isn't being destroyed while it's still in use
00277      * by other threads.
00278      */
00279     if (grp)
00280     { 
00281         cp_rtrie_node_delete(grp, grp->root); 
00282         if (grp->lock) 
00283         {
00284             rc = cp_lock_destroy(grp->lock); 
00285             free(grp->lock);
00286         }
00287         free(grp); 
00288     } 
00289     else rc = -1; 
00290 
00291     return rc; 
00292 } 
00293 
00294 void *RNODE_STORE(cp_rtrie_node *node, cp_bstr *key, cp_rtrie_node *sub)
00295 {
00296     if ((key->bits[0] & 0x80) == 0)
00297     {
00298         node->zero = key;
00299         node->node_zero = sub;
00300     }
00301     else
00302     {
00303         node->one = key;
00304         node->node_one = sub;
00305     }
00306 
00307     return sub; // mtab_put(node->others, *k, sub, k);
00308 }
00309 
00310 void *RNODE_STORE_CPY(cp_rtrie_node *node, cp_bstr *key, cp_rtrie_node *sub)
00311 {
00312     cp_bstr *k = cp_bstr_dup(key);
00313     if (k == NULL) return NULL;
00314 
00315     if ((k->bits[0] & 0x80) == 0)
00316     {
00317         node->zero = k;
00318         node->node_zero = sub;
00319     }
00320     else
00321     {
00322         node->one = k;
00323         node->node_one = sub;
00324     }
00325 
00326     return sub; // mtab_put(node->others, *k, sub, k);
00327 }
00328 
00329 cp_rtrie_node **RNODE_MATCH(cp_rtrie_node *node, cp_bstr *key, int *pos)
00330 {
00331     *pos = -1;
00332     if (node->zero)
00333     {
00334         cp_bstr_cmp(node->zero, key, pos);
00335 //      if (*pos != -1) 
00336         if (*pos > 0)
00337             return &node->node_zero;
00338     }
00339 
00340     if (node->one)
00341     {
00342         cp_bstr_cmp(node->one, key, pos);
00343 //      if (*pos != -1) 
00344         if (*pos > 0)
00345             return &node->node_one;
00346     }
00347 
00348     return NULL;
00349 }
00350     
00351 /*
00352  * since cp_rtrie compresses single child nodes, the following cases are handled
00353  * here. 'abc' etc denote existing path, X marks the spot:
00354  *
00355  * (1) simple case: abc-X         - first mapping for abc
00356  *
00357  * (2) mid-branch:  ab-X-c        - abc already mapped, but ab isn't 
00358  *
00359  * (3) new branch:  ab-X-cd       - the key abcd is already mapped
00360  *                      \          
00361  *                       ef         the key abef is to be added
00362  *
00363  * (4) extending:   abc-de-X      - abc mapped, abcde isn't
00364  * 
00365  * (5) replace:     abc-X         - abc already mapped, just replace leaf  
00366  */
00367 int cp_rtrie_node_store(cp_rtrie *grp, 
00368                        cp_rtrie_node *node, 
00369                        cp_bstr *key, 
00370                        void *leaf) 
00371 { 
00372 //  mtab_node *map_node;
00373 //  char *next;
00374     int pos;
00375     cp_rtrie_node *sub, *old;
00376     cp_bstr *curr;
00377 
00378 //  map_node = RNODE_MATCH(node, key); 
00379 
00380     cp_rtrie_node **match = RNODE_MATCH(node, key, &pos);
00381     if (match == NULL) /* case (1) - not mapped - just add it */
00382     { 
00383         sub = cp_rtrie_node_new(leaf, grp->mempool); 
00384         if (RNODE_STORE_CPY(node, key, sub) == NULL) return -1; 
00385     } 
00386     else 
00387     {
00388         curr = (*match == node->node_zero) ? node->zero : node->one;
00389         if (pos == key->length)
00390         {
00391             if (pos < curr->length) /* case (2) - key ab, curr abc */
00392             {
00393                 cp_bstr *right = cp_bstr_dup(curr);
00394                 if (right == NULL) return -1;
00395                 //~~ cp_bstr_dup_shift would save potential memory wastage here
00396                 cp_bstr_shift_left(right, pos); /* key ab, right c */
00397                 sub = cp_rtrie_node_new(leaf, grp->mempool);
00398                 if (sub == NULL) return -1;
00399                 if (RNODE_STORE(sub, right, *match) == NULL) return -1;
00400                 sub->leaf = leaf;
00401                 *match = sub; /* set old pointer to new node */
00402                 curr->length = pos; /* adjust old bit sequence length */
00403             }
00404             else if (pos == curr->length) /* case (5) - replace: key abc, curr abc */
00405             {
00406                 if ((*match)->leaf && grp->delete_leaf && 
00407                     ((grp->mode & COLLECTION_MODE_DEEP) != 0))
00408                     (*grp->delete_leaf)((*match)->leaf);
00409                 (*match)->leaf = leaf;
00410             }
00411         }
00412         else /* pos < key->length */
00413         {
00414             if (pos == curr->length) /* case (4) - extend */
00415             {
00416                 int res;
00417                 cp_bstr *right = cp_bstr_dup(key);
00418                 if (right == NULL) return -1;
00419                 cp_bstr_shift_left(right, pos);
00420                 res = cp_rtrie_node_store(grp, *match, right, leaf);
00421                 cp_bstr_destroy(right);
00422                 return res;
00423             }
00424             else /* pos can't be greater than curr length, so it must be shorter - case (3) */
00425             {
00426                 cp_bstr *snew, *sold;
00427 
00428                 snew = cp_bstr_dup(key);
00429                 if (snew == NULL) return -1;
00430                 sold = cp_bstr_dup(curr);
00431                 if (sold == NULL) return -1;
00432                 sub = cp_rtrie_node_new(leaf, grp->mempool);
00433                 if (sub == NULL) return -1;
00434                 old = cp_rtrie_node_new(NULL, grp->mempool);
00435                 if (old == NULL) return -1;
00436 
00437                 cp_bstr_shift_left(snew, pos);
00438                 cp_bstr_shift_left(sold, pos);
00439                 RNODE_STORE(old, sold, *match);
00440                 RNODE_STORE(old, snew, sub);
00441                 curr->length = pos;
00442                 *match = old;
00443             }
00444         }
00445     }
00446 
00447     return 0;
00448 } 
00449 
00450 /*
00451  * wrapper for the recursive insertion - implements collection mode setting
00452  */
00453 int cp_rtrie_add(cp_rtrie *grp, cp_bstr *key, void *leaf) 
00454 { 
00455     int rc = 0; 
00456     if ((rc = cp_rtrie_txlock(grp, COLLECTION_LOCK_WRITE))) return rc; 
00457 
00458     if ((grp->mode & COLLECTION_MODE_COPY) && grp->copy_leaf && (leaf != NULL))
00459     {
00460         leaf = (*grp->copy_leaf)(leaf);
00461         if (leaf == NULL) goto DONE;
00462     }
00463 
00464     if (key == NULL) /* map NULL key to root node */
00465     {
00466         if (grp->root->leaf && 
00467                 grp->delete_leaf && grp->mode & COLLECTION_MODE_DEEP)
00468             (*grp->delete_leaf)(grp->root->leaf);
00469         grp->root->leaf = leaf; 
00470     }
00471     else 
00472     {
00473         if ((rc = cp_rtrie_node_store(grp, grp->root, key, leaf)))
00474             goto DONE;
00475     } 
00476 
00477     grp->path_count++; 
00478 
00479 DONE:
00480     cp_rtrie_txunlock(grp);
00481     return rc; 
00482 } 
00483 
00484 #if 0
00485 /* helper functions for cp_rtrie_remove */
00486 
00487 static char *mergestr(char *s1, char *s2)
00488 {
00489     char *s;
00490     int len = strlen(s1) + strlen(s2);
00491 
00492     s = malloc((len + 1) * sizeof(char));
00493     if (s == NULL) return NULL;
00494     
00495 #ifdef CP_HAS_STRLCPY
00496     strlcpy(s, s1, len + 1);
00497 #else
00498     strcpy(s, s1);
00499 #endif /* CP_HAS_STRLCPY */
00500 #ifdef CP_HAS_STRLCAT
00501     strlcat(s, s2, len + 1);
00502 #else
00503     strcat(s, s2);
00504 #endif /* CP_HAS_STRLCAT */
00505 
00506     return s;
00507 }
00508 
00509 static mtab_node *get_single_entry(mtab *t)
00510 {
00511     int i;
00512 
00513     for (i = 0; i < t->size; i++)
00514         if (t->table[i]) return t->table[i];
00515 
00516     return NULL;
00517 }
00518 
00519 #endif
00520 
00521 /*
00522  * removing mappings, the following cases are possible:
00523  * 
00524  * (1) simple case:       abc-X       removing mapping abc
00525  *
00526  * (2) branch:            abc-de-X    removing mapping abcde -
00527  *                           \        mapping abcfg remains, but
00528  *                            fg      junction node abc no longer needed
00529  *
00530  * (3) mid-branch:        abc-X-de    removing mapping abc - mapping abcde
00531  *                                    remains
00532  */
00533 int cp_rtrie_remove(cp_rtrie *grp, cp_bstr *key, void **leaf)
00534 {
00535     int rc = 0;
00536     cp_rtrie_node *link = grp->root; 
00537     cp_rtrie_node *prev = NULL;
00538     int pos;
00539     cp_rtrie_node **match;
00540     cp_bstr *k, **kmatch;
00541 
00542     if (link == NULL) return 0; /* tree is empty */
00543 
00544     if ((rc = cp_rtrie_txlock(grp, COLLECTION_LOCK_READ))) return rc;
00545  
00546     if (key == NULL) /* as a special case, NULL keys are stored on the root */
00547     {
00548         if (link->leaf)
00549         {
00550             if (leaf != NULL) *leaf = link->leaf;
00551             grp->path_count--;
00552             if (grp->delete_leaf && grp->mode & COLLECTION_MODE_DEEP)
00553                 (*grp->delete_leaf)(link->leaf);
00554             link->leaf = NULL;
00555         }
00556         goto DONE;
00557     }
00558 
00559     k = cp_bstr_dup(key);
00560     while (1)
00561     {
00562         pos = -1;
00563         match = RNODE_MATCH(link, k, &pos);
00564         if (match == NULL) break;
00565         kmatch = ((*match) == link->node_zero) ? &link->zero : &link->one;
00566 
00567         if (pos == k->length)
00568         {
00569             if (leaf != NULL) *leaf = (*match)->leaf;
00570 
00571             if ((*match)->leaf != NULL)
00572             {
00573                 grp->path_count--;
00574                 rc = 1;
00575                 if (grp->delete_leaf && grp->mode & COLLECTION_MODE_DEEP)
00576                     (*grp->delete_leaf)((*match)->leaf);
00577                 (*match)->leaf = NULL;
00578             }
00579 
00580             if ((*match)->zero != NULL && (*match)->one == NULL)
00581             {
00582                 cp_bstr_cat(*kmatch, (*match)->zero);
00583                 link = *match;
00584                 *match = (*match)->node_zero;
00585                 cp_rtrie_node_drop(grp, link);
00586             }
00587             else if ((*match)->zero == NULL && (*match)->one != NULL)
00588             {
00589                 cp_bstr_cat(*kmatch, (*match)->one);
00590                 link = *match;
00591                 *match = (*match)->node_one;
00592                 cp_rtrie_node_drop(grp, link);
00593             }
00594             else if ((*match)->zero == NULL && (*match)->one == NULL)
00595             {
00596                 cp_rtrie_node_drop(grp, *match);
00597                 *match = NULL;
00598                 cp_bstr_destroy(*kmatch);
00599                 *kmatch = NULL;
00600 
00601                 /* handle the dangle - case (2) */
00602                 if (prev != NULL && link->leaf == NULL)
00603                 {
00604                     if (prev->node_zero == link)
00605                     {
00606                         match = &prev->node_zero;
00607                         kmatch = &prev->zero;
00608                     }
00609                     else
00610                     {
00611                         match = &prev->node_one;
00612                         kmatch = &prev->one;
00613                     }
00614                     if (link->zero == NULL)
00615                     {
00616                         *match = link->node_one;
00617                         cp_bstr_cat(*kmatch, link->one);
00618                     }
00619                     else
00620                     {
00621                         *match = link->node_zero;
00622                         cp_bstr_cat(*kmatch, link->zero);
00623                     }
00624                     cp_rtrie_node_drop(grp, link);
00625                 }
00626             }
00627 
00628             goto DONE;
00629         }
00630         else if (pos == (*kmatch)->length) // pos > 0)
00631             cp_bstr_shift_left(k, pos);
00632         else /* not found */
00633             break; 
00634 
00635         prev = link;
00636         link = *match;
00637     }
00638 
00639 DONE: 
00640     cp_bstr_destroy(k);
00641     cp_rtrie_txunlock(grp);
00642     return rc;
00643     
00644 }
00645 
00646 void *cp_rtrie_exact_match(cp_rtrie *grp, cp_bstr *key)
00647 {
00648     void *res = NULL;
00649     cp_bstr *k, *kmatch;
00650     cp_rtrie_node *curr, **match;
00651     int pos;
00652 
00653     k = NULL;
00654     if (cp_rtrie_txlock(grp, COLLECTION_LOCK_READ)) return NULL;
00655 
00656     if (key == NULL) 
00657     {
00658         res = grp->root->leaf;
00659         goto DONE;
00660     }
00661 
00662     k = cp_bstr_dup(key);
00663     curr = grp->root;
00664     while (1)
00665     {
00666         pos = -1;
00667         match = RNODE_MATCH(curr, k, &pos);
00668         if (match == NULL) break;
00669         kmatch = ((*match) == curr->node_zero) ? curr->zero : curr->one;
00670         if (pos == k->length)
00671         {
00672             if (pos == kmatch->length)
00673                 res = (*match)->leaf;
00674             break;
00675         }
00676         if (pos == kmatch->length)
00677             cp_bstr_shift_left(k, pos);
00678         else
00679             break;
00680 
00681         curr = *match;
00682     }
00683 
00684 DONE:
00685     if (k != NULL)
00686         cp_bstr_destroy(k);
00687     cp_rtrie_txunlock(grp);
00688     return res;
00689 }
00690 
00691 cp_vector *cp_rtrie_fetch_matches(cp_rtrie *grp, cp_bstr *key)
00692 {
00693     int rc;
00694     cp_vector *res = NULL;
00695     cp_rtrie_node *curr = grp->root;
00696     cp_bstr *k = NULL;
00697     int pos;
00698     cp_rtrie_node **match;
00699     cp_bstr *kmatch;
00700 
00701     if ((rc = cp_rtrie_txlock(grp, COLLECTION_LOCK_READ))) return NULL; 
00702     
00703     if (key == NULL) 
00704     {
00705         res = cp_vector_create(1);
00706         if (res == NULL)
00707             goto DONE;
00708 
00709         errno = 0;
00710         if (cp_vector_add_element(res, curr->leaf) == NULL)
00711         {
00712             if (errno != 0)
00713             {
00714                 cp_vector_destroy(res);
00715                 res = NULL;
00716             }
00717         }
00718         goto DONE;
00719     }
00720 
00721     k = cp_bstr_dup(key);
00722     curr = grp->root;
00723     while (1)
00724     {
00725         pos = -1;
00726         match = RNODE_MATCH(curr, k, &pos);
00727         if (match == NULL) break;
00728         kmatch = ((*match) == curr->node_zero) ? curr->zero : curr->one;
00729 
00730         if (res == NULL)
00731         {
00732             res = cp_vector_create(1);
00733             if (res == NULL) //~~ set errno
00734                 goto DONE;
00735         }
00736         errno = 0;
00737         if (cp_vector_add_element(res, curr->leaf) == NULL && errno != 0)
00738         {
00739             cp_vector_destroy(res);
00740             res = NULL;
00741             goto DONE;
00742         }
00743 
00744         if (pos == k->length)
00745         {
00746             if (pos == kmatch->length)
00747             {
00748                 errno = 0;
00749                 if (cp_vector_add_element(res, (*match)->leaf) == NULL && errno != 0)
00750                 {
00751                     cp_vector_destroy(res);
00752                     res = NULL;
00753                 }
00754             }
00755             break;
00756         }
00757         if (pos == kmatch->length)
00758             cp_bstr_shift_left(k, pos);
00759         else
00760             break;
00761 
00762         curr = *match;
00763     }
00764 
00765 DONE:
00766     if (k != NULL)
00767         cp_bstr_destroy(k);
00768     cp_rtrie_txunlock(grp);
00769     return res; 
00770 }
00771 
00772 
00773 static void extract_subrtrie(cp_rtrie_node *link, cp_vector *v)
00774 {
00775     if (link->leaf)
00776         cp_vector_add_element(v, link->leaf);
00777 
00778     if (link->node_zero)
00779         extract_subrtrie(link->node_zero, v);
00780 
00781     if (link->node_one)
00782         extract_subrtrie(link->node_one, v);
00783 }
00784 
00785 /* return a vector containing all enrtries in subtree under path given by key */
00786 cp_vector *cp_rtrie_submatch(cp_rtrie *grp, cp_bstr *key)
00787 {
00788     cp_vector *res = NULL;
00789     cp_bstr *k, *kmatch;
00790     cp_rtrie_node *curr, **match;
00791     int pos;
00792 
00793     k = NULL;
00794 
00795     if (cp_rtrie_txlock(grp, COLLECTION_LOCK_READ)) return NULL;
00796 
00797     if (key == NULL) 
00798     {
00799         res = cp_vector_create(1);
00800         if (res != NULL)
00801             extract_subrtrie(grp->root, res);
00802         goto DONE;
00803     }
00804 
00805     k = cp_bstr_dup(key);
00806     curr = grp->root;
00807     while (1)
00808     {
00809         pos = -1;
00810         match = RNODE_MATCH(curr, k, &pos);
00811         if (match == NULL) break;
00812         kmatch = ((*match) == curr->node_zero) ? curr->zero : curr->one;
00813         if (pos == k->length)
00814         {
00815             if (pos == kmatch->length)
00816             {
00817                 res = cp_vector_create(1);
00818                 if (res != NULL)
00819                     extract_subrtrie(*match, res);
00820             }
00821             break;
00822         }
00823         if (pos == kmatch->length)
00824             cp_bstr_shift_left(k, pos);
00825         else
00826             break;
00827 
00828         curr = *match;
00829     }
00830 
00831 DONE:
00832     if (k != NULL)
00833         cp_bstr_destroy(k);
00834     cp_rtrie_txunlock(grp);
00835     return res;
00836 } 
00837 
00838 /* return longest prefix match for given key */
00839 int cp_rtrie_prefix_match(cp_rtrie *grp, cp_bstr *key, void **leaf)
00840 { 
00841     int count = 0;
00842     cp_bstr *k, *kmatch;
00843     cp_rtrie_node *curr, **match;
00844     int pos;
00845     void *last = grp->root->leaf; 
00846 
00847     k = NULL;
00848     if (cp_rtrie_txlock(grp, COLLECTION_LOCK_READ)) return -1;
00849 
00850     if (key == NULL) 
00851     {
00852         if (leaf != NULL)
00853             *leaf = grp->root->leaf;
00854         goto DONE;
00855     }
00856 
00857     k = cp_bstr_dup(key);
00858     curr = grp->root;
00859     while (1)
00860     {
00861         pos = -1;
00862         match = RNODE_MATCH(curr, k, &pos);
00863         if (match == NULL) break;
00864         kmatch = ((*match) == curr->node_zero) ? curr->zero : curr->one;
00865         if (pos == k->length)
00866         {
00867             if (pos == kmatch->length)
00868             {
00869                 if ((*match)->leaf != NULL)
00870                 {
00871                     last = (*match)->leaf;
00872                     count++;
00873                 }
00874             }
00875             break;
00876         }
00877         if (pos == kmatch->length)
00878         {
00879             cp_bstr_shift_left(k, pos);
00880             if ((*match)->leaf != NULL)
00881             {
00882                 last = (*match)->leaf;
00883                 count++;
00884             }
00885         }
00886         else
00887             break;
00888 
00889         curr = *match;
00890     }
00891 
00892 DONE:
00893     if (k != NULL)
00894         cp_bstr_destroy(k);
00895     if (leaf != NULL)
00896         *leaf = last;
00897     cp_rtrie_txunlock(grp);
00898     return count;
00899 }
00900 
00901 int cp_rtrie_count(cp_rtrie *grp)
00902 {
00903     return grp->path_count;
00904 }
00905 
00906 void cp_rtrie_set_root(cp_rtrie *grp, void *leaf) 
00907 { 
00908     grp->root->leaf = leaf; 
00909 } 
00910 
00911 /* dump rtrie to stdout - for debugging */
00912 void cp_rtrie_dump_node(cp_rtrie_node *node, int level, cp_bstr *prefix)
00913 {
00914     char *bstr;
00915     cp_bstr *p;
00916     int tab;
00917 
00918     if (node->node_zero != NULL)
00919     {
00920         p = cp_bstr_dup(prefix);
00921         cp_bstr_cat(p, node->zero);
00922         cp_rtrie_dump_node(node->node_zero, level + 1, p);
00923         cp_bstr_destroy(p);
00924     }
00925 
00926     bstr = cp_bstr_to_string(prefix);
00927     for (tab = 0; tab < level; tab++)
00928         printf("\t");
00929     printf("%s => [%s]\n", bstr, node->leaf ? (char *) node->leaf : "NULL");
00930     free(bstr);
00931 
00932     if (node->node_one != NULL)
00933     {
00934         p = cp_bstr_dup(prefix);
00935         cp_bstr_cat(p, node->one);
00936         cp_rtrie_dump_node(node->node_one, level + 1, p);
00937         cp_bstr_destroy(p);
00938     }
00939 }
00940         
00941 void cp_rtrie_dump(cp_rtrie *grp)
00942 {
00943     cp_bstr prefix;
00944 
00945     prefix.bits = "";
00946     prefix.length = 0;
00947     
00948     cp_rtrie_dump_node(grp->root, 0, &prefix);
00949 }
00950 
00951 /* set rtrie to use given mempool or allocate a new one if pool is NULL */
00952 int cp_rtrie_use_mempool(cp_rtrie *rtrie, cp_mempool *pool)
00953 {
00954     int rc = 0;
00955     
00956     if ((rc = cp_rtrie_txlock(rtrie, COLLECTION_LOCK_WRITE))) return rc;
00957     
00958     if (pool)
00959     {
00960         if (pool->item_size < sizeof(cp_rtrie_node))
00961         {
00962             rc = EINVAL;
00963             goto DONE;
00964         }
00965         if (rtrie->mempool) 
00966         {
00967             if (rtrie->path_count) 
00968             {
00969                 rc = ENOTEMPTY;
00970                 goto DONE;
00971             }
00972             cp_mempool_destroy(rtrie->mempool);
00973         }
00974         cp_mempool_inc_refcount(pool);
00975         rtrie->mempool = pool;
00976     }
00977     else
00978     {
00979         rtrie->mempool = 
00980             cp_mempool_create_by_option(COLLECTION_MODE_NOSYNC, 
00981                                         sizeof(cp_rtrie_node), 0);
00982         if (rtrie->mempool == NULL) 
00983         {
00984             rc = ENOMEM;
00985             goto DONE;
00986         }
00987     }
00988 
00989 DONE:
00990     cp_rtrie_txunlock(rtrie);
00991     return rc;
00992 }
00993 
00994 
00995 /* set rtrie to use a shared memory pool */
00996 int cp_rtrie_share_mempool(cp_rtrie *rtrie, cp_shared_mempool *pool)
00997 {
00998     int rc;
00999 
01000     if ((rc = cp_rtrie_txlock(rtrie, COLLECTION_LOCK_WRITE))) return rc;
01001 
01002     if (rtrie->mempool)
01003     {
01004         if (rtrie->path_count)
01005         {
01006             rc = ENOTEMPTY;
01007             goto DONE;
01008         }
01009 
01010         cp_mempool_destroy(rtrie->mempool);
01011     }
01012 
01013     rtrie->mempool = cp_shared_mempool_register(pool, sizeof(cp_rtrie_node));
01014     if (rtrie->mempool == NULL) 
01015     {
01016         rc = ENOMEM;
01017         goto DONE;
01018     }
01019     
01020 DONE:
01021     cp_rtrie_txunlock(rtrie);
01022     return rc;
01023 }
01024 

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