Additional changes to integrate with highperf-lib, moved osal.c to highperf-lib
[keystone-rtos/netapi.git] / ti / runtime / netapi / test / trie.c
1 /*
3 Copyright (c) 2005, Simon Howard
4 All rights reserved.
6 Redistribution and use in source and binary forms, with or without 
7 modification, are permitted provided that the following conditions 
8 are met:
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.
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.
33  *ALSO:   TI modifications made to support binary data keys
34 *
35  *  Copyright (c) Texas Instruments Incorporated 2010-2011
36 */
38 /* Trie: fast mapping of strings to values */
40 #include <stdlib.h>
41 #include <string.h>
43 #include "trie.h"
45 typedef struct _TrieNode TrieNode;
47 struct _TrieNode {
48         void *data;
49         unsigned int use_count;
50         TrieNode *next[256];
51 };
53 struct _Trie {
54         TrieNode *root_node;
55 };
57 static void trie_free_node(TrieNode *node)
58 {
59         int i;
61         if (node == NULL)
62                 return;
63         
64         /* First, free all subnodes */
66         for (i=0; i<256; ++i) {
67                 trie_free_node(node->next[i]);
68         }
70         /* Free this node */
72         free(node);
73 }
75 Trie *trie_new(void)
76 {
77         Trie *new_trie;
79         new_trie = (Trie *) malloc(sizeof(Trie));
80         new_trie->root_node = NULL;
82         return new_trie;
83 }
85 void trie_free(Trie *trie)
86 {
87         /* Free the subnode, and all others by implication */
89         trie_free_node(trie->root_node);
91         /* Free the trie */
93         free(trie);
94 }
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;
104         /* Cannot insert NULL values */
106         if (value == NULL) {
107                 return;
108         }
110         /* Search down the trie until we reach the end of string,
111          * creating nodes as necessary */
113         rover = &trie->root_node;
114         p = (unsigned char *) key;
116         for (k=0;;) {
118                 node = *rover;
120                 if (node == NULL) {
121                         
122                         /* Node does not exist, so create it */
124                         node = (TrieNode *) malloc(sizeof(TrieNode));
125                         memset(node, 0, sizeof(TrieNode));
127                         /* Link in to the trie */
129                         *rover = node;
130                 }
132                 /* One more use of this node */
134                 ++node->use_count;
136                 /* Current character */
138                 c = *p;
140                 /* Reached the end of string?  If so, we're finished. */
142                 if (k>=keylen) {
144                         /* Set the data at the node we have reached */
146                         node->data = value;
148                         break;
149                 }
151                 /* Advance to the next node in the chain */
153                 rover = &node->next[c];
154                 ++p; 
155                 k+=1;
156         }
159 void trie_remove(Trie *trie, char *key, int keylen)
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. */
171         /* Search down the trie until the end of string is reached */
173         node = trie->root_node;
175         for (p=(unsigned char *) key, k=0; k<keylen; ++p, k+=1) {
177                 if (node == NULL) {
178                         /* Not found in the tree. Return. */
180                         return;
181                 }
183                 /* Jump to the next node */
185                 c = *p;
186                 node = node->next[c];
187         }
189         /* Remove the data at this node */
191         node->data = NULL;
193         /* Now traverse the tree again as before, decrementing the use
194          * count of each node.  Free back nodes as necessary. */
196         node = trie->root_node;
197         last_next_ptr = &trie->root_node;
198         p = key;
200         for (k=0;;k++) {
202                 /* Find the next node */
203                 
204                 c = *p;
205                 next = node->next[c];
207                 /* Free this node if necessary */
209                 --node->use_count;
211                 if (node->use_count <= 0) {
212                         free(node);
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. */
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 */
228                 if (k>=keylen) {
229                         break;
230                 } else {
231                         ++p;
232                 }
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. */
238                 if (last_next_ptr != NULL) {
239                         last_next_ptr = &node->next[c];
240                 }
241                 
242                 /* Jump to the next node */
244                 node = next;
245         }
248 void *trie_lookup(Trie *trie, char *key, int keylen)
250         TrieNode *node;
251         unsigned char *p;
252         unsigned char c;
253         int k=0;
255         /* Search down the trie until the end of string is found */
256         
257         node = trie->root_node;
258         p = (unsigned char *) key;
260         while (k<keylen ) {
261                 if (node == NULL) {
262                         /* Not found - reached end of branch */
264                         return NULL;
265                 }
267                 /* Advance to the next node in the chain, next character */
269                 c = *p;
270                 node = node->next[c];
271                 ++p;
272                 k+=1;
273         }
274         /* bug! */
275         
276         return (node ? node->data : NULL);
280 int trie_num_entries(Trie *trie)
282         /* To find the number of entries, simply look at the use count
283          * of the root node. */
285         if (trie->root_node == NULL) {
286                 return 0;
287         } else {
288                 return trie->root_node->use_count;
289         }
292 //#define TEST
293 #ifdef TEST
294 main()
296 Trie * p_trie;
297 char * p_res;
298 p_trie = trie_new();
299 if (!p_trie) {printf("trie alloc failed\n"); exit(1);}
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");
306 p_res= trie_lookup(p_trie,"key1");
307 printf("lookup %s = %s\n", "key1", p_res ?  p_res : "not found");
309 p_res= trie_lookup(p_trie,"key12");
310 printf("lookup %s = %s\n", "key2", p_res ?  p_res : "not found");
312 p_res= trie_lookup(p_trie,"key3");
313 printf("lookup %s = %s\n", "key3", p_res ?  p_res : "not found");
315 p_res= trie_lookup(p_trie,"key4");
316 printf("lookup %s = %s\n", "key4", p_res ?  p_res : "not found");
318 p_res= trie_lookup(p_trie,"key5");
319 printf("lookup %s = %s\n", "key5", p_res ?  p_res : "not found");
321 p_res= trie_lookup(p_trie,"k5");
322 printf("lookup %s = %s\n", "k5", p_res ?  p_res : "not found");
324 trie_free(p_trie);
327 #endif