1.1 --- a/CMakeLists.txt	Tue Oct 02 10:13:07 2012 -0500
     1.2 +++ b/CMakeLists.txt	Tue Oct 02 20:00:38 2012 -0500
     1.3 @@ -104,3 +104,10 @@
     1.4    ${trie_SRCS}
     1.5    ${list_SRCS}
     1.6    )
     1.7 +
     1.8 +set (ctrie_SRCS src/ctrie.h src/ctrie.c)
     1.9 +add_executable (ctrie_test
    1.10 +  src/ctrie_test.c
    1.11 +  ${ctrie_SRCS}
    1.12 +  ${list_SRCS}
    1.13 +  )

     2.1 --- a/src/ctrie.c	Tue Oct 02 10:13:07 2012 -0500
     2.2 +++ b/src/ctrie.c	Tue Oct 02 20:00:38 2012 -0500
     2.3 @@ -27,19 +27,22 @@
     2.4  static struct list * subkey_list = NULL;
     2.5  static size_t subkey_list_limit = 0;
     2.6  
     2.7 -struct ctrie_node * ctrie_search_children(struct ctrie_node * node, char k);
     2.8 +char *              ctrie_insert_node(struct ctrie * ctrie, struct ctrie_node * node, char * key, void * data);
     2.9 +struct ctrie_node * ctrie_longest_matching_child(struct ctrie_node * node, char * key);
    2.10 +struct ctrie_node * ctrie_node_new(char * key, void * data);
    2.11 +int                 ctrie_str_common(char * s1, char * s2);
    2.12 +
    2.13 +void ctrie_print_node(struct ctrie_node * node);
    2.14 +void ctrie_print_key (struct ctrie_node * node);
    2.15 +void ctrie_node_dump (struct ctrie_node * node, int depth, void (*op)(struct ctrie_node *));
    2.16 +
    2.17  void ctrie_visit_node(struct ctrie * ctrie, struct ctrie_node * node, void (*op)(char * k, void * d), char * key);
    2.18 -void ctrie_print_node(struct ctrie_node * node);
    2.19 -void ctrie_print_node(struct ctrie_node * node);
    2.20 -void ctrie_node_dump_preorder(struct ctrie * ctrie, struct ctrie_node * node, int depth);
    2.21 -void ctrie_node_dump_raw(struct ctrie_node * node, int depth);
    2.22 +
    2.23 +struct ctrie_node * ctrie_find_node      (struct ctrie_node * node, char * key);
    2.24 +struct ctrie_node * ctrie_search_children(struct ctrie_node * node, char * k);
    2.25 +
    2.26 +
    2.27  void ctrie_subtree_list_push(char * k, void * d);
    2.28 -struct ctrie_node * ctrie_find_node(struct ctrie * ctrie, char * key);
    2.29 -
    2.30 -struct ctrie_node * ctrie_search_children_longest_match(struct ctrie_node * node, char * k);
    2.31 -
    2.32 -#undef MAX
    2.33 -#define MAX (a, b) ((a) > (b) ? (a) : (b))
    2.34  
    2.35  ////////////////////////////////////////////////////////////////////////////////
    2.36  struct ctrie *
    2.37 @@ -54,10 +57,11 @@
    2.38        return NULL;
    2.39  
    2.40     ctrie->root->parent = ctrie->root->child = ctrie->root->next_sibling = NULL;
    2.41 -   ctrie->root->key = NULL;
    2.42 +   ctrie->root->key = "";
    2.43     ctrie->root->data = NULL;
    2.44     ctrie->size = ctrie->count = 0;
    2.45  
    2.46 +   printf("The root node is %p\n", ctrie->root);
    2.47     return ctrie;
    2.48     }
    2.49  
    2.50 @@ -72,6 +76,43 @@
    2.51     }
    2.52  
    2.53  ////////////////////////////////////////////////////////////////////////////////
    2.54 +struct ctrie_node *
    2.55 +ctrie_node_new(char * key, void * data)
    2.56 +   {
    2.57 +   if (NULL == key)
    2.58 +      return NULL;
    2.59 +
    2.60 +   struct ctrie_node * new = malloc(sizeof(struct ctrie_node));
    2.61 +   if (NULL == new)
    2.62 +      return NULL;
    2.63 +
    2.64 +   new->key = malloc(strlen(key));
    2.65 +   if (NULL == new->key)
    2.66 +      {
    2.67 +      free(new);
    2.68 +      return NULL;
    2.69 +      }
    2.70 +   strcpy(new->key, key);
    2.71 +
    2.72 +   new->data = data;
    2.73 +   new->parent = new->child = new->prev_sibling = new->next_sibling = NULL;
    2.74 +
    2.75 +   return new;
    2.76 +   }
    2.77 +
    2.78 +////////////////////////////////////////////////////////////////////////////////
    2.79 +void *
    2.80 +ctrie_node_free(struct ctrie_node * node)
    2.81 +   {
    2.82 +   if (NULL == node)
    2.83 +      return NULL;
    2.84 +   void * data = node->data;
    2.85 +   free(node->key);
    2.86 +   free(node);
    2.87 +   return data;
    2.88 +   }
    2.89 +
    2.90 +////////////////////////////////////////////////////////////////////////////////
    2.91  size_t
    2.92  ctrie_size(struct ctrie * ctrie)
    2.93     {
    2.94 @@ -96,131 +137,342 @@
    2.95     if ( (NULL == ctrie) || (NULL == key) )
    2.96        return NULL;
    2.97  
    2.98 -   struct ctrie_node * curr = ctrie->root;
    2.99 -   struct ctrie_node * result;
   2.100 +   printf("root node is ");
   2.101 +   ctrie_print_node(ctrie->root);
   2.102 +   return ctrie_insert_node(ctrie, ctrie->root, key, data);
   2.103 +   }
   2.104  
   2.105 -   size_t len = strlen(key);
   2.106 -   for (int i = 0; i <= len; ++i)
   2.107 +////////////////////////////////////////////////////////////////////////////////
   2.108 +char *
   2.109 +ctrie_insert_node(struct ctrie * ctrie, struct ctrie_node * node, char * key, void * data)
   2.110 +   {
   2.111 +   if ( (NULL == node) || (NULL == key) )
   2.112 +      return NULL;
   2.113 +
   2.114 +   struct ctrie_node * p = ctrie_longest_matching_child(node, key);
   2.115 +
   2.116 +   /*
   2.117 +   printf("Longest match is ");
   2.118 +   if (NULL != p)
   2.119 +      ctrie_print_node(p);
   2.120 +   else
   2.121 +      printf("(nil)\n");
   2.122 +   */
   2.123 +
   2.124 +   if (NULL == p)
   2.125        {
   2.126 -      result = ctrie_search_children_longest_match(curr, key+i);
   2.127 -      if (NULL == result)
   2.128 +      // No matching child found.  Create new(key, data) as child of node
   2.129 +      struct ctrie_node * new = ctrie_node_new(key, data);
   2.130 +      if (NULL == new)
   2.131 +	 return NULL;
   2.132 +      new->parent = node;
   2.133 +
   2.134 +      if (NULL == node->child)
   2.135 +	 node->child = new;
   2.136 +      else 
   2.137  	 {
   2.138 -	 // current char is not in the ctrie yet, allocate a new node and attach it to the children
   2.139 -	 struct ctrie_node * new = malloc(sizeof(struct ctrie_node));
   2.140 -	 if (NULL == new)
   2.141 -	    return NULL;
   2.142 -	 new->key = tolower(key[i]);
   2.143 -	 new->child = new->next_sibling = new->prev_sibling = NULL;
   2.144 -	 new->data = NULL;
   2.145 +	 struct ctrie_node * s = node->child;
   2.146 +	 while (NULL != s->next_sibling)
   2.147 +	    s = s->next_sibling;
   2.148 +	 s->next_sibling = new;
   2.149 +	 new->prev_sibling = s;
   2.150 +	 }
   2.151 +      
   2.152 +      ctrie->size++;
   2.153 +      ctrie->count++;
   2.154  
   2.155 -	 if (NULL == curr->child)
   2.156 -	    curr->child = new;
   2.157 -	 else
   2.158 -	    {
   2.159 -	    struct ctrie_node * p = curr->child;
   2.160 -	    while (p->next_sibling)
   2.161 -	       p = p->next_sibling;
   2.162 -	    new->prev_sibling = p;
   2.163 -	    p->next_sibling = new;
   2.164 -	    }
   2.165 +      /*
   2.166 +      printf("Added ");
   2.167 +      ctrie_print_node(new);
   2.168 +      */
   2.169  
   2.170 -	 new->parent = curr;
   2.171 -	 curr = new;
   2.172 -	 ctrie->size++;
   2.173 +      return key;
   2.174 +      }
   2.175 +   else if (ctrie_str_common(p->key, key) == strlen(p->key))
   2.176 +      {
   2.177 +      // Found a node whose key matches for it's entire length
   2.178 +      if (0 == strcmp(p->key, key))
   2.179 +	 {
   2.180 +	 // Key already exists.  Error
   2.181 +	 return NULL;
   2.182  	 }
   2.183        else
   2.184 -	 curr = result;
   2.185 +	 {
   2.186 +	 // The node found has a key that is a prefix of the key we are inserting.
   2.187 +	 // Recurse with the remainder of the key
   2.188 +	 //	 printf("Recursing because node's entire key %s is a prefix of %s\n", p->key, key);
   2.189 +	 return ctrie_insert_node(ctrie, p, key+strlen(p->key), data);
   2.190 +	 }
   2.191 +      }
   2.192 +   else
   2.193 +      {
   2.194 +      // Found a node that matches for only part of it's length.
   2.195 +      // Split the node and then recurse.
   2.196 +
   2.197 +      /*
   2.198 +      printf("splitting this node: ");
   2.199 +      ctrie_print_node(p);
   2.200 +      */
   2.201 +
   2.202 +      // Get the new shorter key for p.
   2.203 +      int matchlen = ctrie_str_common(p->key, key);
   2.204 +      char * prefix = malloc(matchlen+1);
   2.205 +      if (NULL == prefix)
   2.206 +	 return NULL;
   2.207 +
   2.208 +      strncpy(prefix, key, matchlen);
   2.209 +      prefix[matchlen] = '\0';
   2.210 +
   2.211 +      // Create a new node to hold the remainder of the old key and take over the existing children.
   2.212 +      struct ctrie_node * new = ctrie_node_new((p->key)+matchlen, p->data);
   2.213 +      if (NULL == new)
   2.214 +	 {
   2.215 +	 free(prefix);
   2.216 +	 return NULL;
   2.217 +	 }
   2.218 +      new->parent = p;
   2.219 +      new->child = p->child;
   2.220 +      new->data = p->data;
   2.221 +
   2.222 +      // Update p to point to it's new child and have it's new (shorter) key
   2.223 +      free(p->key);
   2.224 +      p->key = prefix;
   2.225 +      p->child = new;
   2.226 +      p->data = NULL;
   2.227 +
   2.228 +      ctrie->size++;
   2.229 +
   2.230 +      /*
   2.231 +      printf("Node was split into these\n");
   2.232 +      ctrie_print_node(p);
   2.233 +      ctrie_print_node(new);
   2.234 +      */
   2.235 +
   2.236 +      // Now add the user requested new key as a child of p
   2.237 +      //      printf("Recursing with key %s as a prefix of %s\n", p->key, key);
   2.238 +      return ctrie_insert_node(ctrie, p, key + matchlen, data);
   2.239        }
   2.240  
   2.241 -   // At this point, curr is either pointing to a new \0 node with a NULL data pointer,
   2.242 -   // or an existing \0 node with a valid data pointer (in which case we were asked to "insert" 
   2.243 -   // a key that was already present in the ctrie.
   2.244 -   // For now I am simply ignoring collisions.  We will update the data.
   2.245 -
   2.246 -   curr->data = data;
   2.247 -
   2.248 -   ctrie->count++;
   2.249 -
   2.250 -   return key;
   2.251 +   // should not get here
   2.252 +   return NULL;
   2.253     }
   2.254  
   2.255  ////////////////////////////////////////////////////////////////////////////////
   2.256  struct ctrie_node *
   2.257 -ctrie_search_children_longest_match(struct ctrie_node * node, char * k)
   2.258 +ctrie_longest_matching_child(struct ctrie_node * node, char * key)
   2.259     {
   2.260 +   struct ctrie_node * longest = NULL;
   2.261 +   int len = 0;
   2.262 +   int l;
   2.263 +
   2.264 +   printf("Searching for match in children of %p\n", node);
   2.265 +
   2.266     struct ctrie_node * p = node->child;
   2.267 -   if (NULL == p)
   2.268 -      return NULL;
   2.269 -
   2.270 -   size_t klen = strlen(k);
   2.271 -   struct ctrie_node * longest = NULL;
   2.272 -   size_t length = 0;
   2.273     while (NULL != p)
   2.274        {
   2.275 -      size_t len = strlen(p->key);
   2.276 -      while (len > 0)
   2.277 +      l = ctrie_str_common(p->key, key);
   2.278 +      printf("common length is %d\n", l);
   2.279 +      if (l > len)
   2.280  	 {
   2.281 -	 if ( (0 == strncmp(p->key, k, MAX(len, klen))) &&
   2.282 -	      (length < MAX(len, klen)) )
   2.283 -	    {
   2.284 -	    longest = p;
   2.285 -	    length = MAX(len, klen);
   2.286 -	    break;
   2.287 -	    }
   2.288 -	 len--;
   2.289 +	 len = l;
   2.290 +	 longest = p;
   2.291  	 }
   2.292        p = p->next_sibling;
   2.293        }
   2.294 -
   2.295 -   return p;
   2.296 +   return longest;
   2.297     }
   2.298  
   2.299  ////////////////////////////////////////////////////////////////////////////////
   2.300 -struct ctrie_node *
   2.301 -ctrie_search_children(struct ctrie_node * node, char k)
   2.302 +// Returns the number of characters of s1 (starting at the beginning)
   2.303 +// that match the corresponding characters in s2.
   2.304 +//
   2.305 +// eg: ctrie_str_common("asdf", "asdf") returns 4
   2.306 +//     ctrie_str_common("asdf", "asdfer") returns 4
   2.307 +//     ctrie_str_common("asdf", "asgg") returns 2
   2.308 +//     ctrie_str_common("asdf", "gggg") returns 0
   2.309 +
   2.310 +int
   2.311 +ctrie_str_common(char * s1, char * s2)
   2.312     {
   2.313 -   struct ctrie_node * p = node->child;
   2.314 -   if (NULL == p)
   2.315 -      return NULL;
   2.316 +   int i = 0;
   2.317 +   while ( (*s1 != '\0') && (*s2 != '\0') &&
   2.318 +	   (*(s1+i) == *(s2+i)) )
   2.319 +      i++;
   2.320  
   2.321 -   while ( (NULL != p) && (p->key != tolower(k)) )
   2.322 -      p = p->next_sibling;
   2.323 -   return p;
   2.324 +   return i;
   2.325     }
   2.326  
   2.327  ////////////////////////////////////////////////////////////////////////////////
   2.328 -struct ctrie_node *
   2.329 -ctrie_find_node(struct ctrie * ctrie, char * key)
   2.330 +void
   2.331 +ctrie_print_node(struct ctrie_node * node)
   2.332     {
   2.333 -   if ( (NULL == ctrie) || (NULL == key) )
   2.334 -      return NULL;
   2.335 +   if (NULL == node)
   2.336 +      printf("(nil node)\n");
   2.337 +   else
   2.338 +      printf("%s \t%p\t parent:%p \tchild:%p \tprev:%p \tnext:%p \tdata:%p\n", node->key, node, node->parent, node->child, node->prev_sibling, node->next_sibling, node->data);
   2.339  
   2.340 -   struct ctrie_node * node = ctrie->root;
   2.341 -   size_t len = strlen(key);
   2.342 -   for (int i = 0; i <= len; i++)
   2.343 +   }
   2.344 +
   2.345 +////////////////////////////////////////////////////////////////////////////////
   2.346 +void
   2.347 +ctrie_print_key(struct ctrie_node * node)
   2.348 +   {
   2.349 +   if (NULL == node)
   2.350 +      printf("(nil node)\n");
   2.351 +   else if (NULL == node->key)
   2.352 +      printf("(nil key)\n");
   2.353 +   else
   2.354 +      printf("%s\n", node->key);
   2.355 +   }
   2.356 +
   2.357 +////////////////////////////////////////////////////////////////////////////////
   2.358 +void ctrie_dump(struct ctrie * ctrie)
   2.359 +   { 
   2.360 +   if (NULL == ctrie)
   2.361 +      return;
   2.362 +  
   2.363 +   int depth = 0;
   2.364 +   ctrie_node_dump(ctrie->root, depth, ctrie_print_key);
   2.365 +   }
   2.366 +
   2.367 +////////////////////////////////////////////////////////////////////////////////
   2.368 +void ctrie_dump_raw(struct ctrie * ctrie)
   2.369 +   { 
   2.370 +   if (NULL == ctrie)
   2.371 +      return;
   2.372 +  
   2.373 +   int depth = 0;
   2.374 +   ctrie_node_dump(ctrie->root, depth, ctrie_print_node);
   2.375 +   }
   2.376 +
   2.377 +////////////////////////////////////////////////////////////////////////////////
   2.378 +void
   2.379 +ctrie_node_dump(struct ctrie_node * node, int depth, void (*op)(struct ctrie_node *))
   2.380 +   {
   2.381 +   for (int i=0; i < depth; i++)
   2.382 +      printf(" ");
   2.383 +   op(node);
   2.384 +   if (node->child)
   2.385        {
   2.386 -      node = ctrie_search_children(node, key[i]);
   2.387 -      if (NULL == node)
   2.388 -	 return NULL;
   2.389 -      if ('\0' == key[i])
   2.390 -	 return node;
   2.391 +      int len = 0;
   2.392 +      if (NULL != node->key)
   2.393 +	 len = strlen(node->key);
   2.394 +      ctrie_node_dump(node->child, depth+len, op); 
   2.395 +      }
   2.396 +   if (NULL != node->next_sibling)
   2.397 +      ctrie_node_dump(node->next_sibling, depth, op);
   2.398 +   }
   2.399 +
   2.400 +////////////////////////////////////////////////////////////////////////////////
   2.401 +void
   2.402 +ctrie_walk_keys(struct ctrie * ctrie, void (*op)(char * k, void * d))
   2.403 +   {
   2.404 +   if (NULL == ctrie)
   2.405 +      return;
   2.406 +   ctrie_visit_node(ctrie, ctrie->root, op, "");
   2.407 +   }
   2.408 +
   2.409 +////////////////////////////////////////////////////////////////////////////////
   2.410 +void
   2.411 +ctrie_visit_node(struct ctrie * ctrie, struct ctrie_node * node, void (*op)(char * k, void * d), char * prefix)
   2.412 +   {
   2.413 +   if (NULL != node->data)
   2.414 +      {
   2.415 +      char * k = malloc(strlen(prefix) + strlen(node->key));
   2.416 +      if (NULL == k)
   2.417 +	 return;
   2.418 +      k[0] = '\0';
   2.419 +      strcat(k, prefix);
   2.420 +      strcat(k, node->key);
   2.421 +      op(k, node->data);
   2.422 +      free(k);
   2.423        }
   2.424  
   2.425 -   // Should never get here
   2.426 -   return NULL;
   2.427 +   if(NULL != node->child)
   2.428 +      {
   2.429 +      char * k = malloc(strlen(prefix) + strlen(node->key));
   2.430 +      if (NULL == k)
   2.431 +	 return;
   2.432 +      k[0] = '\0';
   2.433 +      strcat(k, prefix);
   2.434 +      strcat(k, node->key);
   2.435 +      struct ctrie_node * p = node->child;
   2.436 +      while (NULL != p)
   2.437 +	 {
   2.438 +	 ctrie_visit_node(ctrie, p, op, k);
   2.439 +	 p = p->next_sibling;
   2.440 +	 }
   2.441 +      free(k);
   2.442 +      }
   2.443     }
   2.444  
   2.445  ////////////////////////////////////////////////////////////////////////////////
   2.446  void *
   2.447  ctrie_find(struct ctrie * ctrie, char * key)
   2.448     {
   2.449 -   struct ctrie_node * node = ctrie_find_node(ctrie, key);
   2.450 +   struct ctrie_node * node = ctrie_find_node(ctrie->root, key);
   2.451     if (NULL == node)
   2.452        return NULL;
   2.453     return node->data;
   2.454     }
   2.455  
   2.456  ////////////////////////////////////////////////////////////////////////////////
   2.457 +struct ctrie_node *
   2.458 +ctrie_find_node(struct ctrie_node * node, char * key)
   2.459 +   {
   2.460 +   if ( (NULL == node) || (NULL == key) )
   2.461 +      return NULL;
   2.462 +
   2.463 +   size_t len = strlen(key);
   2.464 +   for (int i = 0; i <= len; i += strlen(node->key))
   2.465 +      {
   2.466 +      node = ctrie_search_children(node, key+i);
   2.467 +      if (NULL == node)
   2.468 +	 return NULL;
   2.469 +      if (NULL != node->data)
   2.470 +	 return node;
   2.471 +      }
   2.472 +
   2.473 +   // Should never get here
   2.474 +   return NULL;
   2.475 +
   2.476 +   struct ctrie_node * p = ctrie_longest_matching_child(node, key);
   2.477 +   }
   2.478 +
   2.479 +////////////////////////////////////////////////////////////////////////////////
   2.480 +struct ctrie_node *
   2.481 +ctrie_search_children(struct ctrie_node * node, char * k)
   2.482 +   {
   2.483 +   struct ctrie_node * p = node->child;
   2.484 +   if (NULL == p)
   2.485 +      return NULL;
   2.486 +
   2.487 +   size_t len = strlen(node->key);
   2.488 +   while ( (NULL != p) && (0 != strncmp(node->key, k, len)) )
   2.489 +      p = p->next_sibling;
   2.490 +   return p;
   2.491 +   }
   2.492 +
   2.493 +
   2.494 +
   2.495 +
   2.496 +
   2.497 +
   2.498 +
   2.499 +
   2.500 +
   2.501 +
   2.502 +
   2.503 +
   2.504 +
   2.505 +
   2.506 +
   2.507 +
   2.508 +
   2.509 +
   2.510 +
   2.511 +
   2.512 +////////////////////////////////////////////////////////////////////////////////
   2.513  void *
   2.514  ctrie_remove(struct ctrie * ctrie, char * key)
   2.515     {
   2.516 @@ -261,98 +513,6 @@
   2.517  
   2.518  ////////////////////////////////////////////////////////////////////////////////
   2.519  void
   2.520 -ctrie_walk_keys(struct ctrie * ctrie, void (*op)(char * k, void * d))
   2.521 -   {
   2.522 -   if (NULL == ctrie)
   2.523 -      return;
   2.524 -   ctrie_visit_node(ctrie, ctrie->root, op, "");
   2.525 -   }
   2.526 -
   2.527 -////////////////////////////////////////////////////////////////////////////////
   2.528 -void
   2.529 -ctrie_visit_node(struct ctrie * ctrie, struct ctrie_node * node, void (*op)(char * k, void * d), char * key)
   2.530 -   {
   2.531 -   if ( (node->key == '\0') && (node != ctrie->root) )
   2.532 -      op(key, node->data);
   2.533 -   else
   2.534 -      {
   2.535 -      size_t len = strlen(key);
   2.536 -      char * k = malloc(len+2);
   2.537 -      if (NULL == k)
   2.538 -	 return;
   2.539 -      strcpy(k, key);
   2.540 -      k[len] = node->key;
   2.541 -      k[len+1] = '\0';
   2.542 -      struct ctrie_node * p = node->child;
   2.543 -      while (NULL != p)
   2.544 -	 {
   2.545 -	 ctrie_visit_node(ctrie, p, op, k);
   2.546 -	 p = p->next_sibling;
   2.547 -	 }
   2.548 -      free(k);
   2.549 -      }
   2.550 -   }
   2.551 -
   2.552 -////////////////////////////////////////////////////////////////////////////////
   2.553 -void ctrie_dump_raw(struct ctrie * ctrie)
   2.554 -   { 
   2.555 -   if (NULL == ctrie)
   2.556 -      return;
   2.557 -  
   2.558 -   int depth = -1;
   2.559 -   ctrie_node_dump_raw(ctrie->root, depth);
   2.560 -   }
   2.561 -
   2.562 -////////////////////////////////////////////////////////////////////////////////
   2.563 -void
   2.564 -ctrie_node_dump_raw(struct ctrie_node * node, int depth)
   2.565 -   {
   2.566 -   for (int i=0; i < depth; i++)
   2.567 -      printf(" ");
   2.568 -   ctrie_print_node(node);
   2.569 -   if (node->child)
   2.570 -      ctrie_node_dump_raw(node->child, depth+1); 
   2.571 -   if (NULL != node->next_sibling)
   2.572 -      ctrie_node_dump_raw(node->next_sibling, depth+1);
   2.573 -   }
   2.574 -
   2.575 -////////////////////////////////////////////////////////////////////////////////
   2.576 -void ctrie_dump(struct ctrie * ctrie)
   2.577 -   { 
   2.578 -   if (NULL == ctrie)
   2.579 -      return;
   2.580 -  
   2.581 -   int depth = -1;
   2.582 -   ctrie_node_dump_preorder(ctrie, ctrie->root, depth);
   2.583 -   }
   2.584 -
   2.585 -////////////////////////////////////////////////////////////////////////////////
   2.586 -void
   2.587 -ctrie_node_dump_preorder(struct ctrie * ctrie, struct ctrie_node * node, int depth)
   2.588 -   {
   2.589 -   printf("%c", node->key);
   2.590 -   if ( (node != ctrie->root) && ('\0' == node->key) )
   2.591 -      printf("\n");
   2.592 -   if (node->child)
   2.593 -      ctrie_node_dump_preorder(ctrie, node->child, depth+1);
   2.594 -   if (NULL != node->next_sibling)
   2.595 -      {
   2.596 -      for (int i=0; i < depth; i++)
   2.597 -	 printf(" ");
   2.598 -      ctrie_node_dump_preorder(ctrie, node->next_sibling, depth);
   2.599 -      }
   2.600 -   }
   2.601 -
   2.602 -////////////////////////////////////////////////////////////////////////////////
   2.603 -void
   2.604 -ctrie_print_node(struct ctrie_node * node)
   2.605 -   {
   2.606 -   printf("%p\tchild %p\tnext_sibling %p\tkey %c\tdata %p\n", (void *) node, (void *) node->child, 
   2.607 -	  (void *) node->next_sibling, node->key, node->data);
   2.608 -   }
   2.609 -
   2.610 -////////////////////////////////////////////////////////////////////////////////
   2.611 -void
   2.612  ctrie_subtree_list_push(char * k, void * d)
   2.613     {
   2.614     if (NULL == subkey_list)

     3.1 --- a/src/ctrie_test.c	Tue Oct 02 10:13:07 2012 -0500
     3.2 +++ b/src/ctrie_test.c	Tue Oct 02 20:00:38 2012 -0500
     3.3 @@ -28,11 +28,14 @@
     3.4  		      "anybody", "any person",
     3.5  		      "Apple", "A computer manufacturer.",
     3.6  		      "ABLE", "having necessary power, skill, resources, or qualifications",
     3.7 +		      /*
     3.8 +		      */
     3.9  		      NULL, NULL
    3.10     };
    3.11     int i = 0;
    3.12     while (words[i])
    3.13        {
    3.14 +      printf("Adding %s\n", words[i]);
    3.15        ctrie_insert(ctrie, words[i], words[i+1]);
    3.16        i += 2;
    3.17        }
    3.18 @@ -42,6 +45,8 @@
    3.19     ctrie_walk_keys(ctrie, print_val);
    3.20     printf("ctrie is storing %zd words in %zd keys\n", ctrie_count(ctrie), ctrie_size(ctrie));
    3.21  
    3.22 +   exit(EXIT_SUCCESS);
    3.23 +
    3.24     ////////////////////////////////////////////
    3.25     printf("===================================================\n");
    3.26     char word[100];;