+++ /dev/null
-#include <stdio.h> /* printf */
-#include <stdlib.h> /* malloc */
-#include <string.h> /* strcmp, strlen */
-
-#include "trie.h"
-
-/* The following is necessary to make sure that trie.pyd won't link
- * to msvcrt.dll in addition to msvcr71.dll on Windows.
- * See Bug #1767 on Bugzilla.
- */
-#ifdef __MINGW32__
-# define strdup _strdup
-#endif
-
-struct _Transition; /* Forward declaration, needed in _Trie. */
-
-
-/* _Trie is a recursive data structure. A _Trie contains zero or more
- * _Transitions that lead to more _Tries. The transitions are stored
- * in alphabetical order of the suffix member of the data structure.
- * _Trie also contains a pointer called value where the user can store
- * arbitrary data. If value is NULL, then no data is stored here.
- */
-struct _Trie {
- struct _Transition *transitions;
- unsigned char num_transitions;
- void *value; /* specified by user, never freed or allocated by me! */
-};
-
-/* _Transition holds information about the transitions leading from
- * one _Trie to another. The trie structure here is different from
- * typical ones, because the transitions between nodes can contain
- * strings of arbitrary length, not just single characters. Suffix is
- * the string that is matched from one node to the next.
- */
-typedef struct _Transition {
- unsigned char *suffix;
- Trie next;
-} *Transition;
-
-
-#define MAX_KEY_LENGTH 1000
-static unsigned char KEY[MAX_KEY_LENGTH];
-
-
-Trie Trie_new(void) {
- Trie trie;
-
- if(!(trie = (Trie)malloc(sizeof(struct _Trie))))
- return NULL;
- trie->transitions = NULL;
- trie->num_transitions = 0;
- trie->value = NULL;
- return trie;
-}
-
-int Trie_set(Trie trie, const unsigned char *key, const void *value) {
- int i;
- Transition transition=NULL;
- unsigned char *suffix=NULL;
- int retval = 0;
- int first, last, mid;
-
- if(!key[0]) {
- trie->value = (void *)value;
- return 0;
- }
-
- /* Insert the key in alphabetical order. Do a binary search to
- find the proper place. */
- first = 0;
- last = trie->num_transitions-1;
- i = -1;
- while(first <= last) {
- mid = (first+last)/2;
- transition = &trie->transitions[mid];
- suffix = transition->suffix;
- if(key[0] < suffix[0])
- last = mid-1;
- else if(key[0] > suffix[0])
- first = mid+1;
- else {
- i = mid;
- break;
- }
- }
-
- /* If no place was found for it, then the indexes will be in the
- order last,first. Place it at index first. */
- if(i == -1)
- i = first;
-
- /* If nothing matches, then insert a new trie here. */
- if((i >= trie->num_transitions) || (key[0] != suffix[0])) {
- unsigned char *new_suffix=NULL;
- Trie newtrie=NULL;
- Transition new_transitions=NULL;
-
- /* Create some variables for the new transition. I'm going to
- allocate these first so that if I can detect memory errors
- before I mess up the data structure of the transitions.
- */
- if(!(new_suffix = (unsigned char *)strdup(key)))
- goto insert_memerror;
- if(!(newtrie = Trie_new()))
- goto insert_memerror;
-
- /* Create some space for the next transition. Allocate some
- memory and shift the old transitions over to make room for
- this one.
- */
- if(!(new_transitions = malloc(sizeof(struct _Transition) *
- (trie->num_transitions+1))))
- goto insert_memerror;
- memcpy(new_transitions, trie->transitions,
- sizeof(struct _Transition)*i);
- memcpy(&new_transitions[i+1], &trie->transitions[i],
- sizeof(struct _Transition)*(trie->num_transitions-i));
- free(trie->transitions);
- trie->transitions = new_transitions;
- new_transitions = NULL;
- trie->num_transitions += 1;
-
- /* Initialize the new transition. */
- transition = &trie->transitions[i];
- transition->suffix = new_suffix;
- transition->next = newtrie;
- transition->next->value = (void *)value;
-
- if(0) {
- insert_memerror:
- if(new_transitions) free(new_transitions);
- if(newtrie) free(newtrie);
- if(new_suffix) free(new_suffix);
- return 1;
- }
- }
- /* There are three cases where the key and suffix share some
- letters.
- 1. suffix is proper substring of key.
- 2. key is proper substring of suffix.
- 3. neither is proper substring of other.
-
- For cases 2 and 3, I need to first split up the transition
- based on the number of characters shared. Then, I can insert
- the rest of the key into the next trie.
- */
- else {
- /* Count the number of characters shared between key
- and suffix. */
- int chars_shared = 0;
- while(key[chars_shared] && key[chars_shared] == suffix[chars_shared])
- chars_shared++;
-
- /* Case 2 or 3, split this sucker! */
- if(chars_shared < strlen(suffix)) {
- Trie newtrie=NULL;
- unsigned char *new_suffix1=NULL, *new_suffix2=NULL;
-
- if(!(new_suffix1 = (unsigned char *)malloc(chars_shared+1)))
- goto split_memerror;
- strncpy(new_suffix1, key, chars_shared);
- new_suffix1[chars_shared] = 0;
- if(!(new_suffix2 = (unsigned char *)strdup(suffix+chars_shared)))
- goto split_memerror;
- if(!(newtrie = Trie_new()))
- goto split_memerror;
- if(!(newtrie->transitions =
- (Transition)malloc(sizeof(struct _Transition))))
- goto split_memerror;
- newtrie->num_transitions = 1;
- newtrie->transitions[0].next = transition->next;
- newtrie->transitions[0].suffix = new_suffix2;
-
- free(transition->suffix);
- transition->suffix = new_suffix1;
- transition->next = newtrie;
-
- if(0) {
- split_memerror:
- if(newtrie && newtrie->transitions) free(newtrie->transitions);
- if(newtrie) free(newtrie);
- if(new_suffix2) free(new_suffix2);
- if(new_suffix1) free(new_suffix1);
- return 1;
- }
- }
- retval = Trie_set(transition->next, key+chars_shared, value);
- }
-
- return retval;
-}
-
-void Trie_del(Trie trie) {
- int i;
- if(!trie)
- return;
- for(i=0; i<trie->num_transitions; i++) {
- Transition transition = &trie->transitions[i];
- if(transition->suffix)
- free(transition->suffix);
- Trie_del(transition->next);
- }
- free(trie);
-}
-
-void *Trie_get(const Trie trie, const unsigned char *key) {
- int first, last, mid;
-
- if(!key[0]) {
- return trie->value;
- }
-
- /* The transitions are stored in alphabetical order. Do a binary
- * search to find the proper one.
- */
- first = 0;
- last = trie->num_transitions-1;
- while(first <= last) {
- Transition transition;
- unsigned char *suffix;
- int c;
- mid = (first+last)/2;
- transition = &trie->transitions[mid];
- suffix = transition->suffix;
- /* If suffix is a substring of key, then get the value from
- the next trie.
- */
- c = strncmp(key, suffix, strlen(suffix));
- if(c < 0)
- last = mid-1;
- else if(c > 0)
- first = mid+1;
- else
- return Trie_get(transition->next, key+strlen(suffix));
- }
- return NULL;
-}
-
-
-/* Mutually recursive, so need to make a forward declaration. */
-void
-_get_approximate_trie(const Trie trie, const unsigned char *key, const int k,
- void (*callback)(const unsigned char *key,
- const void *value,
- const int mismatches,
- void *data),
- void *data,
- const int mismatches,
- unsigned char *current_key, const int max_key
- );
-
-void
-_get_approximate_transition(const unsigned char *key,
- const int k,
- const Transition transition,
- const unsigned char *suffix,
- void (*callback)(const unsigned char *key,
- const void *value,
- const int mismatches,
- void *data),
- void *data,
- const int mismatches,
- unsigned char *current_key, const int max_key
- )
-{
- int i;
- int prev_keylen = strlen(current_key);
-
- /* Short circuit optimization. If there's too many characters to
- possibly be a match, then don't even try to match things. */
- if((int)(strlen(suffix) - strlen(key)) > k)
- return;
-
- /* Match as many characters as possible. */
- i = 0;
- while(suffix[i] && (key[i] == suffix[i])) {
- i++;
- }
- /* Check to make sure the key is not too long. BUG: If it is,
- fails silently. */
- if((prev_keylen+i) >= max_key)
- return;
- strncat(current_key, suffix, i);
-
- /* If all the letters in the suffix matched, then move to the
- next trie. */
- if(!suffix[i]) {
- _get_approximate_trie(transition->next, &key[i], k, callback, data,
- mismatches, current_key, max_key);
- }
- /* Otherwise, try out different kinds of mismatches. */
- else if(k) {
- int new_keylen = prev_keylen+i;
-
- /* Letter replacement, skip the next letter in both the key and
- suffix. */
- if((new_keylen+1 < max_key) && key[i] && suffix[i]) {
- current_key[new_keylen] = suffix[i];
- current_key[new_keylen+1] = 0;
- _get_approximate_transition(&key[i+1], k-1,
- transition, &suffix[i+1],
- callback, data,
- mismatches+1, current_key, max_key);
- current_key[new_keylen] = 0;
- }
-
- /* Insertion in key, skip the next letter in the key. */
- if(key[i]) {
- _get_approximate_transition(&key[i+1], k-1,
- transition, &suffix[i],
- callback, data,
- mismatches+1, current_key, max_key);
- }
-
- /* Deletion from key, skip the next letter in the suffix. */
- if((new_keylen+1 < max_key) && suffix[i]) {
- current_key[new_keylen] = suffix[i];
- current_key[new_keylen+1] = 0;
- _get_approximate_transition(&key[i], k-1,
- transition, &suffix[i+1],
- callback, data,
- mismatches+1, current_key, max_key);
- current_key[new_keylen] = 0;
- }
- }
- current_key[prev_keylen] = 0;
-}
-
-void
-_get_approximate_trie(const Trie trie, const unsigned char *key, const int k,
- void (*callback)(const unsigned char *key,
- const void *value,
- const int mismatches,
- void *data),
- void *data,
- const int mismatches,
- unsigned char *current_key, const int max_key
- )
-{
- int i;
-
- /* If there's no more key to match, then I'm done. */
- if(!key[0]) {
- if(trie->value)
- (*callback)(current_key, trie->value, mismatches, data);
- }
- /* If there are no more mismatches allowed, then fall back to the
- faster Trie_get. */
- else if(!k) {
- void *value = Trie_get(trie, key);
- if(value) {
- int l = strlen(current_key);
- /* Make sure I have enough space for the full key. */
- if(l + strlen(key) < max_key) {
- strcat(current_key, key);
- (*callback)(current_key, value, mismatches, data);
- current_key[l] = 0;
- }
- /* BUG: Ran out of space for the key. This fails
- silently, but should signal an error. */
- }
- }
- /* If there are no more transitions, then all the characters left
- in the key are mismatches. */
- else if(!trie->num_transitions) {
- if(trie->value && (strlen(key) <= k)) {
- (*callback)(current_key, trie->value,
- mismatches+strlen(key), data);
- }
- }
- /* Otherwise, try to match each of the transitions. */
- else {
- for(i=0; i<trie->num_transitions; i++) {
- Transition transition = &trie->transitions[i];
- unsigned char *suffix = transition->suffix;
- _get_approximate_transition(key, k, transition, suffix,
- callback, data,
- mismatches, current_key, max_key);
- }
- }
-
-}
-
-
-void
-Trie_get_approximate(const Trie trie, const unsigned char *key, const int k,
- void (*callback)(const unsigned char *key,
- const void *value,
- const int mismatches,
- void *data),
- void *data
- )
-{
- KEY[0] = 0;
- _get_approximate_trie(trie, key, k, callback, data, 0, KEY,MAX_KEY_LENGTH);
-}
-
-int Trie_len(const Trie trie)
-{
- int i;
- int length = 0;
-
- if(!trie)
- return 0;
- if(trie->value)
- length += 1;
- for(i=0; i<trie->num_transitions; i++) {
- length += Trie_len(trie->transitions[i].next);
- }
- return length;
-}
-
-int Trie_has_key(const Trie trie, const unsigned char *key)
-{
- return Trie_get(trie, key) != NULL;
-}
-
-int Trie_has_prefix(const Trie trie, const unsigned char *prefix)
-{
- int first, last, mid;
-
- if(!prefix[0]) {
- return 1;
- }
-
- /* The transitions are stored in alphabetical order. Do a binary
- * search to find the proper one.
- */
- first = 0;
- last = trie->num_transitions-1;
- while(first <= last) {
- Transition transition;
- unsigned char *suffix;
- int suffixlen, prefixlen, minlen;
- int c;
- mid = (first+last)/2;
- transition = &trie->transitions[mid];
- suffix = transition->suffix;
- suffixlen = strlen(suffix);
- prefixlen = strlen(prefix);
- minlen = (suffixlen < prefixlen) ? suffixlen : prefixlen;
- c = strncmp(prefix, suffix, minlen);
- if(c < 0)
- last = mid-1;
- else if(c > 0)
- first = mid+1;
- else
- return Trie_has_prefix(transition->next, prefix+minlen);
- }
- return 0;
-}
-
-static void
-_iterate_helper(const Trie trie,
- void (*callback)(const unsigned char *key,
- const void *value,
- void *data),
- void *data,
- unsigned char *current_key, const int max_key)
-{
- int i;
- if(trie->value)
- (*callback)(current_key, trie->value, data);
- for(i=0; i<trie->num_transitions; i++) {
- Transition transition = &trie->transitions[i];
- unsigned char *suffix = transition->suffix;
- int keylen = strlen(current_key);
-
- if(keylen + strlen(suffix) >= max_key) {
- /* BUG: This will fail silently. It should raise some
- sort of error. */
- continue;
- }
- strcat(current_key, suffix);
- _iterate_helper(transition->next, callback, data,
- current_key, max_key);
- current_key[keylen] = 0;
- }
-}
-
-void
-Trie_iterate(const Trie trie,
- void (*callback)(const unsigned char *key,
- const void *value,
- void *data),
- void *data)
-{
- KEY[0] = 0;
- _iterate_helper(trie, callback, data, KEY, MAX_KEY_LENGTH);
-}
-
-static void
-_with_prefix_helper(const Trie trie, const unsigned char *prefix,
- void (*callback)(const unsigned char *key,
- const void *value,
- void *data),
- void *data,
- unsigned char *current_key, const int max_key)
-{
- int first, last, mid;
-
- if(!prefix[0]) {
- _iterate_helper(trie, callback, data, current_key, max_key);
- return;
- }
-
- /* The transitions are stored in alphabetical order. Do a binary
- * search to find the proper one.
- */
- first = 0;
- last = trie->num_transitions-1;
- while(first <= last) {
- Transition transition;
- unsigned char *suffix;
- int suffixlen, prefixlen, minlen;
- int c;
- mid = (first+last)/2;
- transition = &trie->transitions[mid];
- suffix = transition->suffix;
- suffixlen = strlen(suffix);
- prefixlen = strlen(prefix);
- minlen = (suffixlen < prefixlen) ? suffixlen : prefixlen;
- c = strncmp(prefix, suffix, minlen);
- if(c < 0)
- last = mid-1;
- else if(c > 0)
- first = mid+1;
- else {
- int keylen = strlen(current_key);
- if(keylen + minlen >= max_key) {
- /* BUG: This will fail silently. It should raise some
- sort of error. */
- break;
- }
- strncat(current_key, suffix, minlen);
- _with_prefix_helper(transition->next, prefix+minlen,
- callback, data, current_key, max_key);
- current_key[keylen] = 0;
- break;
- }
- }
-}
-
-void
-Trie_with_prefix(const Trie trie, const unsigned char *prefix,
- void (*callback)(const unsigned char *key,
- const void *value,
- void *data),
- void *data
- )
-{
- KEY[0] = 0;
- _with_prefix_helper(trie, prefix, callback, data, KEY, MAX_KEY_LENGTH);
-}
-
-
-
-/* Need to declare _serialize_transition here so it can be called from
- _serialize_trie. */
-int _serialize_transition(const Transition transition,
- int (*write)(const void *towrite, const int length,
- void *data),
- int (*write_value)(const void *value, void *data),
- void *data);
-
-/* This library also provides code for flattening tries so that they
- * can be saved and read back in later. The format of a serialized
- * trie is:
- * TYPE NBYTES DESCRIPTION
- * byte 1 Whether or not there is a value
- * variable variable If there is a value, let the client store it.
- * byte 1 Number of transitions for this Trie.
- * transition variable
- * int 4 Number of characters in the suffix.
- * suffix variable the suffix for this transition
- * byte 1 Whether or not there is a trie
- * trie variable Recursively points to another trie.
- *
- * The number of bytes and the endian may vary from platform to
- * platform.
- */
-
-int _serialize_trie(const Trie trie,
- int (*write)(const void *towrite, const int length,
- void *data),
- int (*write_value)(const void *value, void *data),
- void *data)
-{
- int i;
- unsigned char has_value;
-
- has_value = (trie->value != NULL);
- if(!(*write)(&has_value, sizeof(has_value), data))
- return 0;
- if(has_value) {
- if(!(*write_value)(trie->value, data))
- return 0;
- }
-
- if(!(*write)(&trie->num_transitions, sizeof(trie->num_transitions), data))
- return 0;
- for(i=0; i<trie->num_transitions; i++) {
- if(!_serialize_transition(&trie->transitions[i],
- write, write_value, data))
- return 0;
- }
-
- return 1;
-}
-
-int _serialize_transition(const Transition transition,
- int (*write)(const void *towrite, const int length,
- void *data),
- int (*write_value)(const void *value, void *data),
- void *data)
-{
- int suffixlen;
- unsigned char has_trie;
-
- suffixlen = strlen(transition->suffix);
- if(!(*write)(&suffixlen, sizeof(suffixlen), data))
- return 0;
- if(!(*write)(transition->suffix, suffixlen, data))
- return 0;
-
- has_trie = (transition->next != NULL);
- if(!(*write)(&has_trie, sizeof(has_trie), data))
- return 0;
- if(has_trie) {
- if(!_serialize_trie(transition->next, write, write_value, data))
- return 0;
- }
- return 1;
-}
-
-int Trie_serialize(const Trie trie,
- int (*write)(const void *towrite, const int length,
- void *data),
- int (*write_value)(const void *value, void *data),
- void *data)
-{
- int success = _serialize_trie(trie, write, write_value, data);
- (*write)(NULL, 0, data);
- return success;
-}
-
-int _deserialize_transition(Transition transition,
- int (*read)(void *wasread, const int length,
- void *data),
- void *(*read_value)(void *data),
- void *data);
-
-int _deserialize_trie(Trie trie,
- int (*read)(void *wasread, const int length, void *data),
- void *(*read_value)(void *data),
- void *data)
-{
- int i;
- unsigned char has_value;
-
- if(!(*read)(&has_value, sizeof(has_value), data))
- goto _deserialize_trie_error;
- if(has_value != 0 && has_value != 1)
- goto _deserialize_trie_error;
- if(has_value) {
- if(!(trie->value = (*read_value)(data)))
- goto _deserialize_trie_error;
- }
- if(!(*read)(&trie->num_transitions, sizeof(trie->num_transitions), data))
- goto _deserialize_trie_error;
- if(!(trie->transitions =
- malloc(trie->num_transitions*sizeof(struct _Transition))))
- goto _deserialize_trie_error;
- for(i=0; i<trie->num_transitions; i++) {
- if(!_deserialize_transition(&trie->transitions[i],
- read, read_value, data))
- goto _deserialize_trie_error;
- }
- return 1;
-
- _deserialize_trie_error:
- trie->num_transitions = 0;
- if(trie->transitions) {
- free(trie->transitions);
- trie->transitions = NULL;
- }
- trie->value = NULL;
- return 0;
-}
-
-int _deserialize_transition(Transition transition,
- int (*read)(void *wasread, const int length,
- void *data),
- void *(*read_value)(void *data),
- void *data)
-{
- int suffixlen;
- unsigned char has_trie;
-
- if(!(*read)(&suffixlen, sizeof(suffixlen), data))
- goto _deserialize_transition_error;
- if(suffixlen < 0 || suffixlen >= MAX_KEY_LENGTH)
- goto _deserialize_transition_error;
- if(!(*read)(KEY, suffixlen, data))
- goto _deserialize_transition_error;
- KEY[suffixlen] = 0;
- if(!(transition->suffix = (unsigned char *)strdup(KEY)))
- goto _deserialize_transition_error;
- if(!(*read)(&has_trie, sizeof(has_trie), data))
- goto _deserialize_transition_error;
- if(has_trie != 0 && has_trie != 1)
- goto _deserialize_transition_error;
- if(has_trie) {
- transition->next = Trie_new();
- if(!_deserialize_trie(transition->next, read, read_value, data))
- goto _deserialize_transition_error;
- }
- return 1;
-
- _deserialize_transition_error:
- if(transition->suffix) {
- free(transition->suffix);
- transition->suffix = NULL;
- }
- if(transition->next) {
- Trie_del(transition->next);
- transition->next = NULL;
- }
- return 0;
-}
-
-Trie Trie_deserialize(int (*read)(void *wasread, const int length, void *data),
- void *(*read_value)(void *data),
- void *data)
-{
- Trie trie = Trie_new();
- if(!_deserialize_trie(trie, read, read_value, data)) {
- Trie_del(trie);
- return NULL;
- }
- return trie;
-}
-
-void test(void) {
- Trie trie;
-
- printf("Hello world!\n");
-
- trie = Trie_new();
- printf("New trie %p\n", trie);
- Trie_set(trie, "hello world", "s1");
- Trie_set(trie, "bye", "s2");
- Trie_set(trie, "hell sucks", "s3");
- Trie_set(trie, "hebee", "s4");
-
- printf("%s\n", (char *)Trie_get(trie, "hello world"));
- printf("%s\n", (char *)Trie_get(trie, "bye"));
- printf("%s\n", (char *)Trie_get(trie, "hell sucks"));
- printf("%s\n", (char *)Trie_get(trie, "hebee"));
-
- Trie_set(trie, "blah", "s5");
- printf("%s\n", (char *)Trie_get(trie, "blah"));
-
- printf("%p\n", Trie_get(trie, "foobar"));
- printf("%d\n", Trie_len(trie));
-
- Trie_set(trie, "blah", "snew");
- printf("%s\n", (char *)Trie_get(trie, "blah"));
-
- Trie_del(trie);
-}
-
-#if 0
-int main() {
- test();
-}
-#endif
git://source.jalview.org / jabaws.git / blobdiff