1.1 --- a/CMakeLists.txt	Wed Oct 03 01:07:04 2012 -0500
     1.2 +++ b/CMakeLists.txt	Thu Oct 04 23:07:48 2012 -0500
     1.3 @@ -111,3 +111,10 @@
     1.4    ${ctrie_SRCS}
     1.5    ${list_SRCS}
     1.6    )
     1.7 +
     1.8 +set (trie_sedgewick_SRCS src/trie_sedgewick.h src/trie_sedgewick.c)
     1.9 +add_executable (trie_sedgewick_test
    1.10 +  src/trie_sedgewick_test.c
    1.11 +  ${trie_sedgewick_SRCS}
    1.12 +  )
    1.13 +

     2.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     2.2 +++ b/src/trie_sedgewick.c	Thu Oct 04 23:07:48 2012 -0500
     2.3 @@ -0,0 +1,114 @@
     2.4 +#include <stdlib.h>
     2.5 +#include <string.h>
     2.6 +#include <stdio.h>
     2.7 +
     2.8 +#include "trie_sedgewick.h"
     2.9 +
    2.10 +// Our alphabet size.  One byte's worth.
    2.11 +#define RADIX 256
    2.12 +
    2.13 +struct trie_node
    2.14 +   {
    2.15 +   void * data;
    2.16 +   struct trie_node * next[RADIX];
    2.17 +   };
    2.18 +
    2.19 +struct trie
    2.20 +   {
    2.21 +   struct trie_node * root;
    2.22 +   };
    2.23 +
    2.24 +
    2.25 +struct trie_node * trie_node_new();
    2.26 +void * trie_node_get(struct trie_node * node, char * key, int d);
    2.27 +struct trie_node * trie_node_put(struct trie_node * node, char * key, void * data, int d);
    2.28 +
    2.29 +////////////////////////////////////////////////////////////////////////////////
    2.30 +struct trie_node *
    2.31 +trie_node_new()
    2.32 +   {
    2.33 +   struct trie_node * node = malloc(sizeof(struct trie_node));
    2.34 +   if (NULL == node)
    2.35 +      return NULL;
    2.36 +
    2.37 +   for (int i = 0; i < RADIX; ++i)
    2.38 +      node->next[i] = NULL;
    2.39 +   node->data = NULL;
    2.40 +
    2.41 +   return node;
    2.42 +   }
    2.43 +
    2.44 +////////////////////////////////////////////////////////////////////////////////
    2.45 +struct trie *
    2.46 +trie_new()
    2.47 +   {
    2.48 +   struct trie * trie = malloc(sizeof(struct trie));
    2.49 +   if (NULL == trie)
    2.50 +      return NULL;
    2.51 +
    2.52 +   trie->root = NULL;
    2.53 +   return trie;
    2.54 +   }
    2.55 +
    2.56 +////////////////////////////////////////////////////////////////////////////////
    2.57 +void
    2.58 +trie_delete(struct trie * trie)
    2.59 +   {
    2.60 +   if (NULL == trie)
    2.61 +      return;
    2.62 +   // TODO free nodes
    2.63 +   free(trie);
    2.64 +   }
    2.65 +
    2.66 +////////////////////////////////////////////////////////////////////////////////
    2.67 +char *
    2.68 +trie_put(struct trie * trie, char * key, void * data)
    2.69 +   {
    2.70 +   if ( (NULL == trie) || (NULL == key) )
    2.71 +      return NULL;
    2.72 +   trie->root = trie_node_put(trie->root, key, data, 0);
    2.73 +   return key;
    2.74 +   }
    2.75 +
    2.76 +////////////////////////////////////////////////////////////////////////////////
    2.77 +struct trie_node *
    2.78 +trie_node_put(struct trie_node * node, char * key, void * data, int d)
    2.79 +   {
    2.80 +   if (NULL == node)
    2.81 +      node = trie_node_new();
    2.82 +   if (NULL == node)
    2.83 +      return NULL;
    2.84 +
    2.85 +   if (d == strlen(key))
    2.86 +      {
    2.87 +      node->data = data;
    2.88 +      return node;
    2.89 +      }
    2.90 +   int c = key[d];
    2.91 +   node->next[c] = trie_node_put(node->next[c], key, data, d+1);
    2.92 +   return node;
    2.93 +   }
    2.94 +
    2.95 +////////////////////////////////////////////////////////////////////////////////
    2.96 +void *
    2.97 +trie_get(struct trie * trie, char * key)
    2.98 +   {
    2.99 +   if ( (NULL == trie) || (NULL == key) )
   2.100 +      return NULL;
   2.101 +
   2.102 +   struct trie_node * node = trie_node_get(trie->root, key, 0);
   2.103 +   if (NULL == node)
   2.104 +      return NULL;
   2.105 +   return node->data;
   2.106 +   }
   2.107 +
   2.108 +////////////////////////////////////////////////////////////////////////////////
   2.109 +void *
   2.110 +trie_node_get(struct trie_node * node, char * key, int d)
   2.111 +   {
   2.112 +   if (NULL == node)
   2.113 +      return NULL;
   2.114 +   if (d == strlen(key))
   2.115 +      return node;
   2.116 +   return trie_node_get(node->next[(int) key[d]], key, d+1);
   2.117 +   }

     3.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     3.2 +++ b/src/trie_sedgewick.h	Thu Oct 04 23:07:48 2012 -0500
     3.3 @@ -0,0 +1,14 @@
     3.4 +#ifndef TRIE_SEDGEWICK_H_
     3.5 +#define TRIE_SEDGEWICK_H_
     3.6 +
     3.7 +// Simple trie.  After Sedgewick, Algorithms, Ch 5.
     3.8 +
     3.9 +struct trie;
    3.10 +
    3.11 +struct trie * trie_new();
    3.12 +void trie_delete(struct trie * trie);
    3.13 +
    3.14 +char * trie_put(struct trie * trie, char * key, void * data);
    3.15 +void * trie_get(struct trie * trie, char * key);
    3.16 +
    3.17 +#endif

     4.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     4.2 +++ b/src/trie_sedgewick_test.c	Thu Oct 04 23:07:48 2012 -0500
     4.3 @@ -0,0 +1,47 @@
     4.4 +#include <stdio.h>
     4.5 +#include <stdlib.h>
     4.6 +
     4.7 +#include "trie_sedgewick.h"
     4.8 +
     4.9 +int main(int argc, char ** argv)
    4.10 +   {
    4.11 +   struct trie * trie = trie_new();
    4.12 +   if (NULL == trie)
    4.13 +      {
    4.14 +      fprintf(stderr, "trie_new failed\n");
    4.15 +      exit(EXIT_FAILURE);
    4.16 +      }
    4.17 +
    4.18 +   char * words[] = 
    4.19 +	 {
    4.20 +	 "she", "sells", "sea", "shells", "by", "the", "sea", "shore", NULL,
    4.21 +	 };
    4.22 +
    4.23 +   printf("Loading trie\n");
    4.24 +   char ** w = words;
    4.25 +   while (*w)
    4.26 +      {
    4.27 +      if (NULL == trie_put(trie, *w, *w))
    4.28 +	 {
    4.29 +	 fprintf(stderr, "trie_put failed on %s\n", *w);
    4.30 +	 exit(EXIT_FAILURE);
    4.31 +	 }
    4.32 +      w++;
    4.33 +      }
    4.34 +
    4.35 +   printf("Reading trie\n");
    4.36 +   w = words;
    4.37 +   while (*w)
    4.38 +      {
    4.39 +      char * value;
    4.40 +      if (NULL == (value = trie_get(trie, *w)))
    4.41 +	 {
    4.42 +	 fprintf(stderr, "trie_get failed on %s\n", *w);
    4.43 +	 exit(EXIT_FAILURE);
    4.44 +	 }
    4.45 +      printf("%s\n", value);
    4.46 +      w++;
    4.47 +      }
    4.48 +
    4.49 +   exit(EXIT_SUCCESS);
    4.50 +   }