This a simple implementation of trie
data structure in C99. This implementation allows to store sequences of
int
-s, however one can easy trigger a type of symb
in struct trie
.
The library includes a simple test-case in the trie.c. In order to make
it work, run make test
.
Currently an implemetation provides interfaces to store char
based strings in the
trie, attaching to each word some information of ssize_t
type. For
example, consider the following case:
#include <stdio.h>
#include <string.h>
#include <unistd.h>
#include <stdlib.h>
#include "trie.h"
/* some values, we want to attach to every
word in the trie data base. */
enum type_of_word {
type_a, type_b
};
int main (int argc, char *argv[])
{
int ret = EXIT_SUCCESS;
ssize_t res;
/* Initialize new trie. */
truct trie * dict = trie_new ();
if (argc <= 1)
{
(void) fprintf (stderr, "usage: %s word to find\n", argv[0]);
ret = EXIT_FAILURE;
goto out;
}
/* Add two words of two different types. */
trie_add_word (dict, "hello", strlen ("hello"), (ssize_t)type_a);
trie_add_word (dict, "hell", strlen ("hell"), (ssize_t)type_b);
printf ("Printing the trie.\n");
trie_print (dict);
/* Search the argument in the trie and detect a type of it. */
res = trie_search (dict, argv[1], strlen (argv[1]));
printf ("searching '%s' in the database -- %s\n",
argv[1], res != TRIE_NOT_LAST
? (enum type_of_word)res == type_a ? "yes, type A" : "yes, type B"
: "no");
out:
trie_free (dict);
return ret;
}
As the type of information you attach is a transparent size_t
we need
to dedicate one symbol, whic would denote that a certain symbol is not
last. Macro TRIE_NOT_LAST
serves this purpose.
Tha implementation is valgrinded, and is compiled at strictes gcc warning level.
Send your suggestions or patches.