Back to index

python-biopython  1.60
trie.c
Go to the documentation of this file.
00001 #include <stdio.h>    /* printf */
00002 #include <stdlib.h>   /* malloc */
00003 #include <string.h>   /* strcmp, strlen */
00004 
00005 #include "trie.h"
00006 
00007 static char* duplicate(const char* s) {
00008     /* Don't use strdup, as it's not ANSI C. */
00009     char* t = malloc((strlen(s)+1)*sizeof(char));
00010     if (!t) return NULL;
00011     strcpy(t, s);
00012     return t;
00013 }
00014 
00015 
00016 /* Transition holds information about the transitions leading from
00017  * one Trie to another.  The trie structure here is different from
00018  * typical ones, because the transitions between nodes can contain
00019  * strings of arbitrary length, not just single characters.  Suffix is
00020  * the string that is matched from one node to the next.
00021  */
00022 typedef struct {
00023     char *suffix;
00024     Trie* next;
00025 } Transition;
00026 
00027 
00028 /* Trie is a recursive data structure.  A Trie contains zero or more
00029  * Transitions that lead to more Tries.  The transitions are stored
00030  * in alphabetical order of the suffix member of the data structure.
00031  * Trie also contains a pointer called value where the user can store
00032  * arbitrary data.  If value is NULL, then no data is stored here.
00033  */
00034 struct Trie {
00035     Transition *transitions;
00036     unsigned char num_transitions;
00037     void *value;   /* specified by user, never freed or allocated by me! */
00038 };
00039 
00040 
00041 #define MAX_KEY_LENGTH 1000
00042 static char KEY[MAX_KEY_LENGTH];
00043 
00044 
00045 Trie* Trie_new(void) {
00046     Trie* trie;
00047 
00048     if(!(trie = malloc(sizeof(struct Trie))))
00049        return NULL;
00050     trie->transitions = NULL;
00051     trie->num_transitions = 0;
00052     trie->value = NULL;
00053     return trie;
00054 }
00055 
00056 int Trie_set(Trie* trie, const char *key, const void *value) {
00057     int i;
00058     Transition* transition=NULL;
00059     const char *suffix=NULL;
00060     int retval = 0;
00061     int first, last, mid;
00062 
00063     if(!key[0]) {
00064        trie->value = (void *)value;
00065        return 0;
00066     }
00067 
00068     /* Insert the key in alphabetical order.  Do a binary search to
00069        find the proper place. */
00070     first = 0;
00071     last = trie->num_transitions-1;
00072     i = -1;
00073     while(first <= last) {
00074        mid = (first+last)/2;
00075        transition = &trie->transitions[mid];
00076        suffix = transition->suffix;
00077        if(key[0] < suffix[0])
00078            last = mid-1;
00079        else if(key[0] > suffix[0])
00080            first = mid+1;
00081        else {
00082            i = mid;
00083            break;
00084        }
00085     }
00086 
00087     /* If no place was found for it, then the indexes will be in the
00088        order last,first.  Place it at index first. */
00089     if(i == -1)
00090        i = first;
00091 
00092     /* If nothing matches, then insert a new trie here. */
00093     if((i >= trie->num_transitions) || (key[0] != suffix[0])) {
00094        char *new_suffix=NULL;
00095        Trie* newtrie=NULL;
00096        Transition* new_transitions=NULL;
00097 
00098        /* Create some variables for the new transition.  I'm going to
00099           allocate these first so that if I can detect memory errors
00100           before I mess up the data structure of the transitions.
00101        */
00102        if(!(new_suffix = duplicate(key)))
00103            goto insert_memerror;
00104        if(!(newtrie = Trie_new()))
00105            goto insert_memerror;
00106 
00107        /* Create some space for the next transition.  Allocate some
00108           memory and shift the old transitions over to make room for
00109           this one.
00110        */
00111        if(!(new_transitions = malloc(sizeof(Transition) *
00112                                   (trie->num_transitions+1))))
00113            goto insert_memerror;
00114        memcpy(new_transitions, trie->transitions,
00115               sizeof(Transition)*i);
00116        memcpy(&new_transitions[i+1], &trie->transitions[i],
00117               sizeof(Transition)*(trie->num_transitions-i));
00118        free(trie->transitions);
00119        trie->transitions = new_transitions;
00120        new_transitions = NULL;
00121        trie->num_transitions += 1;
00122 
00123        /* Initialize the new transition. */
00124        transition = &trie->transitions[i];
00125        transition->suffix = new_suffix;
00126        transition->next = newtrie;
00127        transition->next->value = (void *)value;
00128 
00129        if(0) {
00130        insert_memerror:
00131            if(new_transitions) free(new_transitions);
00132            if(newtrie) free(newtrie);
00133            if(new_suffix) free(new_suffix);
00134            return 1;
00135        }
00136     } 
00137     /* There are three cases where the key and suffix share some
00138        letters. 
00139        1.  suffix is proper substring of key.
00140        2.  key is proper substring of suffix.
00141        3.  neither is proper substring of other.
00142 
00143        For cases 2 and 3, I need to first split up the transition
00144        based on the number of characters shared.  Then, I can insert
00145        the rest of the key into the next trie.
00146     */
00147     else {
00148        /* Count the number of characters shared between key
00149           and suffix. */
00150        int chars_shared = 0;
00151        while(key[chars_shared] && key[chars_shared] == suffix[chars_shared])
00152            chars_shared++;
00153 
00154        /* Case 2 or 3, split this sucker! */
00155        if(chars_shared < strlen(suffix)) {
00156            Trie* newtrie=NULL;
00157            char *new_suffix1=NULL, *new_suffix2=NULL;
00158 
00159            if(!(new_suffix1 = malloc(chars_shared+1)))
00160               goto split_memerror;
00161            strncpy(new_suffix1, key, chars_shared);
00162            new_suffix1[chars_shared] = 0;
00163            if(!(new_suffix2 = duplicate(suffix+chars_shared)))
00164               goto split_memerror;
00165            if(!(newtrie = Trie_new()))
00166               goto split_memerror;
00167            if(!(newtrie->transitions = malloc(sizeof(Transition))))
00168               goto split_memerror;
00169            newtrie->num_transitions = 1;
00170            newtrie->transitions[0].next = transition->next;
00171            newtrie->transitions[0].suffix = new_suffix2;
00172 
00173            free(transition->suffix);
00174            transition->suffix = new_suffix1;
00175            transition->next = newtrie;
00176 
00177            if(0) {
00178            split_memerror:
00179               if(newtrie && newtrie->transitions) free(newtrie->transitions);
00180               if(newtrie) free(newtrie);
00181               if(new_suffix2) free(new_suffix2);
00182               if(new_suffix1) free(new_suffix1);
00183               return 1;
00184            }
00185        }
00186        retval = Trie_set(transition->next, key+chars_shared, value);
00187     }
00188 
00189     return retval;
00190 }
00191 
00192 void Trie_del(Trie* trie) {
00193     int i;
00194     if(!trie)
00195        return;
00196     for(i=0; i<trie->num_transitions; i++) {
00197        Transition* transition = &trie->transitions[i];
00198        if(transition->suffix)
00199            free(transition->suffix);
00200        Trie_del(transition->next);
00201     }
00202     free(trie);
00203 }
00204 
00205 void *Trie_get(const Trie* trie, const char *key) {
00206     int first, last, mid;
00207 
00208     if(!key[0]) {
00209        return trie->value;
00210     }
00211 
00212     /* The transitions are stored in alphabetical order.  Do a binary
00213      * search to find the proper one.
00214      */
00215     first = 0;
00216     last = trie->num_transitions-1;
00217     while(first <= last) {
00218        Transition* transition;
00219        char *suffix;
00220        int c;
00221        mid = (first+last)/2;
00222        transition = &trie->transitions[mid];
00223        suffix = transition->suffix;
00224        /* If suffix is a substring of key, then get the value from
00225           the next trie.
00226        */
00227        c = strncmp(key, suffix, strlen(suffix));
00228        if(c < 0)
00229            last = mid-1;
00230        else if(c > 0)
00231            first = mid+1;
00232        else
00233            return Trie_get(transition->next, key+strlen(suffix));
00234     }
00235     return NULL;
00236 }
00237 
00238 
00239 /* Mutually recursive, so need to make a forward declaration. */
00240 static void
00241 _get_approximate_trie(const Trie* trie, const char *key, const int k,
00242                     void (*callback)(const char *key, 
00243                                    const void *value,
00244                                    const int mismatches,
00245                                    void *data),
00246                     void *data, 
00247                     const int mismatches,
00248                     char *current_key, const int max_key
00249                     );
00250 
00251 static void 
00252 _get_approximate_transition(const char *key, 
00253                          const int k,
00254                          const Transition* transition, 
00255                          const char *suffix,
00256                          void (*callback)(const char *key, 
00257                                         const void *value,
00258                                         const int mismatches,
00259                                         void *data),
00260                          void *data, 
00261                          const int mismatches,
00262                          char *current_key, const int max_key
00263                          )
00264 {
00265     int i;
00266     int prev_keylen = strlen(current_key);
00267 
00268     /* Short circuit optimization.  If there's too many characters to
00269        possibly be a match, then don't even try to match things. */
00270     if((int)(strlen(suffix) - strlen(key)) > k)
00271        return;
00272 
00273     /* Match as many characters as possible. */
00274     i = 0;
00275     while(suffix[i] && (key[i] == suffix[i])) {
00276        i++;
00277     }
00278     /* Check to make sure the key is not too long.  BUG: If it is,
00279        fails silently. */
00280     if((prev_keylen+i) >= max_key)
00281        return;
00282     strncat(current_key, suffix, i);
00283 
00284     /* If all the letters in the suffix matched, then move to the
00285        next trie. */
00286     if(!suffix[i]) {
00287        _get_approximate_trie(transition->next, &key[i], k, callback, data,
00288                            mismatches, current_key, max_key);
00289     }
00290     /* Otherwise, try out different kinds of mismatches. */
00291     else if(k) {
00292        int new_keylen = prev_keylen+i;
00293 
00294        /* Letter replacement, skip the next letter in both the key and
00295           suffix. */
00296        if((new_keylen+1 < max_key) && key[i] && suffix[i]) {
00297            current_key[new_keylen] = suffix[i];
00298            current_key[new_keylen+1] = 0;
00299            _get_approximate_transition(&key[i+1], k-1,
00300                                    transition, &suffix[i+1],
00301                                    callback, data,
00302                                    mismatches+1, current_key, max_key);
00303            current_key[new_keylen] = 0;
00304        }
00305 
00306        /* Insertion in key, skip the next letter in the key. */
00307        if(key[i]) {
00308            _get_approximate_transition(&key[i+1], k-1, 
00309                                    transition, &suffix[i],
00310                                    callback, data,
00311                                    mismatches+1, current_key, max_key);
00312        }
00313 
00314        /* Deletion from key, skip the next letter in the suffix. */
00315        if((new_keylen+1 < max_key) && suffix[i]) {
00316            current_key[new_keylen] = suffix[i];
00317            current_key[new_keylen+1] = 0;
00318            _get_approximate_transition(&key[i], k-1,
00319                                    transition, &suffix[i+1],
00320                                    callback, data,
00321                                    mismatches+1, current_key, max_key);
00322            current_key[new_keylen] = 0;
00323        }
00324     }
00325     current_key[prev_keylen] = 0;
00326 }
00327 
00328 static void
00329 _get_approximate_trie(const Trie* trie, const char *key, const int k,
00330                     void (*callback)(const char *key, 
00331                                    const void *value,
00332                                    const int mismatches,
00333                                    void *data),
00334                     void *data, 
00335                     const int mismatches,
00336                     char *current_key, const int max_key
00337                     )
00338 {
00339     int i;
00340 
00341     /* If there's no more key to match, then I'm done. */
00342     if(!key[0]) {
00343        if(trie->value)
00344            (*callback)(current_key, trie->value, mismatches, data);
00345     }
00346     /* If there are no more mismatches allowed, then fall back to the
00347        faster Trie_get. */
00348     else if(!k) {
00349        void *value = Trie_get(trie, key);
00350        if(value) {
00351            int l = strlen(current_key);
00352            /* Make sure I have enough space for the full key. */
00353            if(l + strlen(key) < max_key) {
00354               strcat(current_key, key);
00355               (*callback)(current_key, value, mismatches, data);
00356               current_key[l] = 0;
00357            }
00358            /* BUG: Ran out of space for the key.  This fails
00359               silently, but should signal an error. */
00360        }
00361     }
00362     /* If there are no more transitions, then all the characters left
00363        in the key are mismatches. */
00364     else if(!trie->num_transitions) {
00365        if(trie->value && (strlen(key) <= k)) {
00366            (*callback)(current_key, trie->value, 
00367                      mismatches+strlen(key), data);
00368        }
00369     }
00370     /* Otherwise, try to match each of the transitions. */
00371     else {
00372        for(i=0; i<trie->num_transitions; i++) {
00373            Transition* transition = &trie->transitions[i];
00374            const char *suffix = transition->suffix;
00375            _get_approximate_transition(key, k, transition, suffix,
00376                                    callback, data, 
00377                                    mismatches, current_key, max_key);
00378        }
00379     }
00380 
00381 }
00382 
00383 
00384 void 
00385 Trie_get_approximate(const Trie* trie, const char *key, const int k,
00386                    void (*callback)(const char *key, 
00387                                   const void *value,
00388                                   const int mismatches,
00389                                   void *data),
00390                    void *data
00391                    )
00392 {
00393     KEY[0] = 0;
00394     _get_approximate_trie(trie, key, k, callback, data, 0, KEY,MAX_KEY_LENGTH);
00395 }
00396 
00397 int Trie_len(const Trie* trie) 
00398 {
00399     int i;
00400     int length = 0;
00401     
00402     if(!trie)
00403        return 0;
00404     if(trie->value)
00405        length += 1;
00406     for(i=0; i<trie->num_transitions; i++) {
00407        length += Trie_len(trie->transitions[i].next);
00408     }
00409     return length;
00410 }
00411 
00412 int Trie_has_key(const Trie* trie, const char *key) 
00413 {
00414     return Trie_get(trie, key) != NULL;
00415 }
00416 
00417 int Trie_has_prefix(const Trie* trie, const char *prefix) 
00418 {
00419     int first, last, mid;
00420 
00421     if(!prefix[0]) {
00422        return 1;
00423     }
00424 
00425     /* The transitions are stored in alphabetical order.  Do a binary
00426      * search to find the proper one.
00427      */
00428     first = 0;
00429     last = trie->num_transitions-1;
00430     while(first <= last) {
00431        Transition* transition;
00432        char *suffix;
00433        int suffixlen, prefixlen, minlen;
00434        int c;
00435        mid = (first+last)/2;
00436        transition = &trie->transitions[mid];
00437        suffix = transition->suffix;
00438        suffixlen = strlen(suffix);
00439        prefixlen = strlen(prefix);
00440        minlen = (suffixlen < prefixlen) ? suffixlen : prefixlen;
00441        c = strncmp(prefix, suffix, minlen);
00442        if(c < 0)
00443            last = mid-1;
00444        else if(c > 0)
00445            first = mid+1;
00446        else
00447            return Trie_has_prefix(transition->next, prefix+minlen);
00448     }
00449     return 0;
00450 }
00451 
00452 static void 
00453 _iterate_helper(const Trie* trie, 
00454               void (*callback)(const char *key, 
00455                              const void *value,
00456                              void *data),
00457               void *data,
00458               char *current_key, const int max_key)
00459 {
00460     int i;
00461     if(trie->value)
00462        (*callback)(current_key, trie->value, data);
00463     for(i=0; i<trie->num_transitions; i++) {
00464        Transition* transition = &trie->transitions[i];
00465        const char *suffix = transition->suffix;
00466        int keylen = strlen(current_key);
00467 
00468        if(keylen + strlen(suffix) >= max_key) {
00469            /* BUG: This will fail silently.  It should raise some
00470               sort of error. */
00471            continue;
00472        }
00473        strcat(current_key, suffix);
00474        _iterate_helper(transition->next, callback, data, 
00475                      current_key, max_key);
00476        current_key[keylen] = 0;
00477     }
00478 }
00479 
00480 void 
00481 Trie_iterate(const Trie* trie, 
00482             void (*callback)(const char *key, 
00483                            const void *value,
00484                            void *data),
00485             void *data)
00486 {
00487     KEY[0] = 0;
00488     _iterate_helper(trie, callback, data, KEY, MAX_KEY_LENGTH);
00489 }
00490 
00491 static void
00492 _with_prefix_helper(const Trie* trie, const char *prefix,
00493                   void (*callback)(const char *key, 
00494                                  const void *value,
00495                                  void *data),
00496                   void *data,
00497                   char *current_key, const int max_key)
00498 {
00499     int first, last, mid;
00500 
00501     if(!prefix[0]) {
00502        _iterate_helper(trie, callback, data, current_key, max_key);
00503        return;
00504     }
00505 
00506     /* The transitions are stored in alphabetical order.  Do a binary
00507      * search to find the proper one.
00508      */
00509     first = 0;
00510     last = trie->num_transitions-1;
00511     while(first <= last) {
00512        Transition* transition;
00513        const char *suffix;
00514        int suffixlen, prefixlen, minlen;
00515        int c;
00516        mid = (first+last)/2;
00517        transition = &trie->transitions[mid];
00518        suffix = transition->suffix;
00519        suffixlen = strlen(suffix);
00520        prefixlen = strlen(prefix);
00521        minlen = (suffixlen < prefixlen) ? suffixlen : prefixlen;
00522        c = strncmp(prefix, suffix, minlen);
00523        if(c < 0)
00524            last = mid-1;
00525        else if(c > 0)
00526            first = mid+1;
00527        else {
00528            int keylen = strlen(current_key);
00529            if(keylen + minlen >= max_key) {
00530               /* BUG: This will fail silently.  It should raise some
00531                  sort of error. */
00532               break;
00533            }
00534            strncat(current_key, suffix, minlen);
00535            _with_prefix_helper(transition->next, prefix+minlen,
00536                             callback, data, current_key, max_key);
00537            current_key[keylen] = 0;
00538            break;
00539        }
00540     }
00541 }
00542 
00543 void 
00544 Trie_with_prefix(const Trie* trie, const char *prefix,
00545                void (*callback)(const char *key, 
00546                               const void *value,
00547                               void *data),
00548                void *data
00549                )
00550 {
00551     KEY[0] = 0;
00552     _with_prefix_helper(trie, prefix, callback, data, KEY, MAX_KEY_LENGTH);
00553 }
00554 
00555 
00556 
00557 /* Need to declare _serialize_transition here so it can be called from
00558    _serialize_trie. */
00559 static int _serialize_transition(const Transition* transition, 
00560                        int (*write)(const void *towrite, const int length,
00561                                    void *data),
00562                        int (*write_value)(const void *value, void *data),
00563                        void *data);
00564 
00565 /* This library also provides code for flattening tries so that they
00566  * can be saved and read back in later.  The format of a serialized
00567  * trie is:
00568  * TYPE        NBYTES    DESCRIPTION
00569  * byte        1         Whether or not there is a value
00570  * variable    variable  If there is a value, let the client store it.
00571  * byte        1         Number of transitions for this Trie.
00572  * transition  variable
00573  *   int       4         Number of characters in the suffix.
00574  *   suffix    variable  the suffix for this transition
00575  *   byte      1         Whether or not there is a trie
00576  *   trie      variable  Recursively points to another trie.
00577  * 
00578  * The number of bytes and the endian may vary from platform to
00579  * platform.
00580  */
00581 
00582 static
00583 int _serialize_trie(const Trie* trie, 
00584                   int (*write)(const void *towrite, const int length,
00585                              void *data),
00586                   int (*write_value)(const void *value, void *data),
00587                   void *data)
00588 {
00589     int i;
00590     unsigned char has_value;
00591 
00592     has_value = (trie->value != NULL);
00593     if(!(*write)(&has_value, sizeof(has_value), data))
00594        return 0;
00595     if(has_value) {
00596        if(!(*write_value)(trie->value, data))
00597            return 0;
00598     }
00599 
00600     if(!(*write)(&trie->num_transitions, sizeof(trie->num_transitions), data))
00601        return 0;
00602     for(i=0; i<trie->num_transitions; i++) {
00603        if(!_serialize_transition(&trie->transitions[i], 
00604                               write, write_value, data))
00605            return 0;
00606     }
00607 
00608     return 1;
00609 }
00610 
00611 static
00612 int _serialize_transition(const Transition* transition, 
00613                        int (*write)(const void *towrite, const int length,
00614                                    void *data),
00615                        int (*write_value)(const void *value, void *data),
00616                        void *data)
00617 {
00618     int suffixlen;
00619     unsigned char has_trie;
00620 
00621     suffixlen = strlen(transition->suffix);
00622     if(!(*write)(&suffixlen, sizeof(suffixlen), data))
00623        return 0;
00624     if(!(*write)(transition->suffix, suffixlen, data))
00625        return 0;
00626 
00627     has_trie = (transition->next != NULL);
00628     if(!(*write)(&has_trie, sizeof(has_trie), data))
00629        return 0;
00630     if(has_trie) {
00631        if(!_serialize_trie(transition->next, write, write_value, data))
00632            return 0;
00633     }
00634     return 1;
00635 }
00636 
00637 int Trie_serialize(const Trie* trie, 
00638                  int (*write)(const void *towrite, const int length, 
00639                             void *data),
00640                  int (*write_value)(const void *value, void *data),
00641                  void *data)
00642 {
00643     int success = _serialize_trie(trie, write, write_value, data);
00644     (*write)(NULL, 0, data);
00645     return success;
00646 }
00647 
00648 static
00649 int _deserialize_transition(Transition* transition,
00650                          int (*read)(void *wasread, const int length, 
00651                                    void *data),
00652                          void *(*read_value)(void *data),
00653                          void *data);
00654 
00655 static
00656 int _deserialize_trie(Trie* trie, 
00657                     int (*read)(void *wasread, const int length, void *data),
00658                     void *(*read_value)(void *data),
00659                     void *data)
00660 {
00661     int i;
00662     unsigned char has_value;
00663 
00664     if(!(*read)(&has_value, sizeof(has_value), data))
00665        goto _deserialize_trie_error;
00666     if(has_value != 0 && has_value != 1)
00667        goto _deserialize_trie_error;
00668     if(has_value) {
00669        if(!(trie->value = (*read_value)(data)))
00670            goto _deserialize_trie_error;
00671     }
00672     if(!(*read)(&trie->num_transitions, sizeof(trie->num_transitions), data))
00673        goto _deserialize_trie_error;
00674     if(!(trie->transitions = 
00675         malloc(trie->num_transitions*sizeof(Transition))))
00676        goto _deserialize_trie_error;
00677     for(i=0; i<trie->num_transitions; i++) {
00678        if(!_deserialize_transition(&trie->transitions[i], 
00679                                 read, read_value, data))
00680            goto _deserialize_trie_error;
00681     }
00682     return 1;
00683    
00684  _deserialize_trie_error:
00685     trie->num_transitions = 0;
00686     if(trie->transitions) {
00687        free(trie->transitions);
00688        trie->transitions = NULL;
00689     }
00690     trie->value = NULL;
00691     return 0;
00692 }
00693 
00694 static
00695 int _deserialize_transition(Transition* transition,
00696                          int (*read)(void *wasread, const int length, 
00697                                    void *data),
00698                          void *(*read_value)(void *data),
00699                          void *data)
00700 {
00701     int suffixlen;
00702     unsigned char has_trie;
00703     
00704     if(!(*read)(&suffixlen, sizeof(suffixlen), data))
00705        goto _deserialize_transition_error;
00706     if(suffixlen < 0 || suffixlen >= MAX_KEY_LENGTH)
00707        goto _deserialize_transition_error;
00708     if(!(*read)(KEY, suffixlen, data))
00709        goto _deserialize_transition_error;
00710     KEY[suffixlen] = 0;
00711     if(!(transition->suffix = duplicate(KEY)))
00712        goto _deserialize_transition_error;
00713     if(!(*read)(&has_trie, sizeof(has_trie), data))
00714        goto _deserialize_transition_error;
00715     if(has_trie != 0 && has_trie != 1)
00716        goto _deserialize_transition_error;
00717     if(has_trie) {
00718        transition->next = Trie_new();
00719        if(!_deserialize_trie(transition->next, read, read_value, data))
00720            goto _deserialize_transition_error;
00721     }
00722     return 1;
00723 
00724  _deserialize_transition_error:
00725     if(transition->suffix) {
00726        free(transition->suffix);
00727        transition->suffix = NULL;
00728     }
00729     if(transition->next) {
00730        Trie_del(transition->next);
00731        transition->next = NULL;
00732     }
00733     return 0;
00734 }
00735 
00736 Trie* Trie_deserialize(int (*read)(void *wasread, const int length, void *data),
00737                     void *(*read_value)(void *data),
00738                     void *data)
00739 {
00740     Trie* trie = Trie_new();
00741     if(!_deserialize_trie(trie, read, read_value, data)) {
00742        Trie_del(trie);
00743        return NULL;
00744     }
00745     return trie;
00746 }