ti/runtime/netapi/test/trie.c

   1 /*
   2
   3 Copyright (c) 2005, Simon Howard
   4 All rights reserved.
   5
   6 Redistribution and use in source and binary forms, with or without
   7 modification, are permitted provided that the following conditions
   8 are met:
   9
  10  * Redistributions of source code must retain the above copyright
  11    notice, this list of conditions and the following disclaimer.
  12  * Redistributions in binary form must reproduce the above copyright
  13    notice, this list of conditions and the following disclaimer in
  14    the documentation and/or other materials provided with the
  15    distribution.
  16  * Neither the name of the C Algorithms project nor the names of its
  17    contributors may be used to endorse or promote products derived
  18    from this software without specific prior written permission.
  19
  20 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  21 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  22 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
  23 FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
  24 COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
  25 INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
  26 BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
  27 LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
  28 CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  29 LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
  30 ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
  31 POSSIBILITY OF SUCH DAMAGE.
  32
  33  *ALSO:   TI modifications made to support binary data keys
  34 *
  35  *  Copyright (c) Texas Instruments Incorporated 2010-2011
  36 */
  37
  38 /* Trie: fast mapping of strings to values */
  39
  40 #include <stdlib.h>
  41 #include <string.h>
  42
  43 #include "trie.h"
  44
  45 typedef struct _TrieNode TrieNode;
  46
  47 struct _TrieNode {
  48         void *data;
  49         unsigned int use_count;
  50         TrieNode *next[256];
  51 };
  52
  53 struct _Trie {
  54         TrieNode *root_node;
  55 };
  56
  57 static void trie_free_node(TrieNode *node)
  58 {
  59         int i;
  60
  61         if (node == NULL)
  62                 return;
  63
  64         /* First, free all subnodes */
  65
  66         for (i=0; i<256; ++i) {
  67                 trie_free_node(node->next[i]);
  68         }
  69
  70         /* Free this node */
  71
  72         free(node);
  73 }
  74
  75 Trie *trie_new(void)
  76 {
  77         Trie *new_trie;
  78
  79         new_trie = (Trie *) malloc(sizeof(Trie));
  80         new_trie->root_node = NULL;
  81
  82         return new_trie;
  83 }
  84
  85 void trie_free(Trie *trie)
  86 {
  87         /* Free the subnode, and all others by implication */
  88
  89         trie_free_node(trie->root_node);
  90
  91         /* Free the trie */
  92
  93         free(trie);
  94 }
  95
  96 void trie_insert(Trie *trie, char *key, int keylen, void *value)
  97 {
  98         TrieNode **rover;
  99         TrieNode *node;
 100         unsigned char *p;
 101         unsigned char c;
 102         int k;
 103
 104         /* Cannot insert NULL values */
 105
 106         if (value == NULL) {
 107                 return;
 108         }
 109
 110         /* Search down the trie until we reach the end of string,
 111          * creating nodes as necessary */
 112
 113         rover = &trie->root_node;
 114         p = (unsigned char *) key;
 115
 116         for (k=0;;) {
 117
 118                 node = *rover;
 119
 120                 if (node == NULL) {
 121
 122                         /* Node does not exist, so create it */
 123
 124                         node = (TrieNode *) malloc(sizeof(TrieNode));
 125                         memset(node, 0, sizeof(TrieNode));
 126
 127                         /* Link in to the trie */
 128
 129                         *rover = node;
 130                 }
 131
 132                 /* One more use of this node */
 133
 134                 ++node->use_count;
 135
 136                 /* Current character */
 137
 138                 c = *p;
 139
 140                 /* Reached the end of string?  If so, we're finished. */
 141
 142                 if (k>=keylen) {
 143
 144                         /* Set the data at the node we have reached */
 145
 146                         node->data = value;
 147
 148                         break;
 149                 }
 150
 151                 /* Advance to the next node in the chain */
 152
 153                 rover = &node->next[c];
 154                 ++p;
 155                 k+=1;
 156         }
 157 }
 158
 159 void trie_remove(Trie *trie, char *key, int keylen)
 160 {
 161         TrieNode *node;
 162         TrieNode *next;
 163         TrieNode **last_next_ptr;
 164         unsigned char *p;
 165         unsigned char c;
 166         int k=0;
 167
 168         /* First, search down to the ending node so that the data can
 169          * be removed. */
 170
 171         /* Search down the trie until the end of string is reached */
 172
 173         node = trie->root_node;
 174
 175         for (p=(unsigned char *) key, k=0; k<keylen; ++p, k+=1) {
 176
 177                 if (node == NULL) {
 178                         /* Not found in the tree. Return. */
 179
 180                         return;
 181                 }
 182
 183                 /* Jump to the next node */
 184
 185                 c = *p;
 186                 node = node->next[c];
 187         }
 188
 189         /* Remove the data at this node */
 190
 191         node->data = NULL;
 192
 193         /* Now traverse the tree again as before, decrementing the use
 194          * count of each node.  Free back nodes as necessary. */
 195
 196         node = trie->root_node;
 197         last_next_ptr = &trie->root_node;
 198         p = key;
 199
 200         for (k=0;;k++) {
 201
 202                 /* Find the next node */
 203
 204                 c = *p;
 205                 next = node->next[c];
 206
 207                 /* Free this node if necessary */
 208
 209                 --node->use_count;
 210
 211                 if (node->use_count <= 0) {
 212                         free(node);
 213
 214                         /* Set the "next" pointer on the previous node to NULL,
 215                          * to unlink the free'd node from the tree.  This only
 216                          * needs to be done once in a remove.  After the first
 217                          * unlink, all further nodes are also going to be
 218                          * free'd. */
 219
 220                         if (last_next_ptr != NULL) {
 221                                 *last_next_ptr = NULL;
 222                                 last_next_ptr = NULL;
 223                         }
 224                 }
 225
 226                 /* Go to the next character or finish */
 227
 228                 if (k>=keylen) {
 229                         break;
 230                 } else {
 231                         ++p;
 232                 }
 233
 234                 /* If necessary, save the location of the "next" pointer
 235                  * so that it may be set to NULL on the next iteration if
 236                  * the next node visited is freed. */
 237
 238                 if (last_next_ptr != NULL) {
 239                         last_next_ptr = &node->next[c];
 240                 }
 241
 242                 /* Jump to the next node */
 243
 244                 node = next;
 245         }
 246 }
 247
 248 void *trie_lookup(Trie *trie, char *key, int keylen)
 249 {
 250         TrieNode *node;
 251         unsigned char *p;
 252         unsigned char c;
 253         int k=0;
 254
 255         /* Search down the trie until the end of string is found */
 256
 257         node = trie->root_node;
 258         p = (unsigned char *) key;
 259
 260         while (k<keylen ) {
 261                 if (node == NULL) {
 262                         /* Not found - reached end of branch */
 263
 264                         return NULL;
 265                 }
 266
 267                 /* Advance to the next node in the chain, next character */
 268
 269                 c = *p;
 270                 node = node->next[c];
 271                 ++p;
 272                 k+=1;
 273         }
 274         /* bug! */
 275
 276         return (node ? node->data : NULL);
 277
 278 }
 279
 280 int trie_num_entries(Trie *trie)
 281 {
 282         /* To find the number of entries, simply look at the use count
 283          * of the root node. */
 284
 285         if (trie->root_node == NULL) {
 286                 return 0;
 287         } else {
 288                 return trie->root_node->use_count;
 289         }
 290 }
 291
 292 //#define TEST
 293 #ifdef TEST
 294 main()
 295 {
 296 Trie * p_trie;
 297 char * p_res;
 298 p_trie = trie_new();
 299 if (!p_trie) {printf("trie alloc failed\n"); exit(1);}
 300
 301 trie_insert(p_trie,"key1","this is key 1");
 302 trie_insert(p_trie,"key12","this is key 2");
 303 trie_insert(p_trie,"key3","this is key 3");
 304 trie_insert(p_trie,"key4","this is key 4");
 305
 306 p_res= trie_lookup(p_trie,"key1");
 307 printf("lookup %s = %s\n", "key1", p_res ?  p_res : "not found");
 308
 309 p_res= trie_lookup(p_trie,"key12");
 310 printf("lookup %s = %s\n", "key2", p_res ?  p_res : "not found");
 311
 312 p_res= trie_lookup(p_trie,"key3");
 313 printf("lookup %s = %s\n", "key3", p_res ?  p_res : "not found");
 314
 315 p_res= trie_lookup(p_trie,"key4");
 316 printf("lookup %s = %s\n", "key4", p_res ?  p_res : "not found");
 317
 318 p_res= trie_lookup(p_trie,"key5");
 319 printf("lookup %s = %s\n", "key5", p_res ?  p_res : "not found");
 320
 321 p_res= trie_lookup(p_trie,"k5");
 322 printf("lookup %s = %s\n", "k5", p_res ?  p_res : "not found");
 323
 324 trie_free(p_trie);
 325
 326 }
 327 #endif