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