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