Ternary search trie 1.4

Russ Allbery rra at stanford.edu
Sun Jul 6 00:23:52 UTC 2008


Julien ÉLIE <julien at trigofacile.com> writes:

> The only thing I see in tst 1.4 is that there is this addition:
>
> if(key[key_index] == 0) {
>  if(tst->free_list == NULL) {
>    if(tst_grow_node_free_list(tst) != 1)
>      return TST_ERROR;
>  }
>  new_node = tst->free_list;
>  tst->free_list = tst->free_list->middle;
>  memcpy((void*)new_node, (void*)current_node, sizeof(struct node));
>  current_node->value = 0;
>  if(new_node->value < 64) {
>    current_node->left = new_node;
>    current_node->right = '\0';
>  } else {
>    current_node->left = '\0';
>    current_node->right = new_node;
>  }
>  current_node->middle = data;
>  return TST_OK;
> }

It looks like this code may be not adding another node for each character
in the string and instead is adding only a single new node, just enough to
disambiguate from the current contents, and making it terminal.

-- 
Russ Allbery (rra at stanford.edu)             <http://www.eyrie.org/~eagle/>

    Please send questions to the list rather than mailing me directly.
     <http://www.eyrie.org/~eagle/faqs/questions.html> explains why.


More information about the inn-workers mailing list