Mercurial > data_structures

view src/trie.c @ 12:d359966ed8de

find changesets by author, revision, files, or words in the commit message
Added trie
author Eris Caffee <discordia@eldalin.com>
date Mon, 01 Oct 2012 15:50:30 -0500
parents
children 7886d2da8cc4
line source
1 #include <ctype.h>
2 #include <stdlib.h>
3 #include <stdbool.h>
4 #include <string.h>
5
6
7 #include <stdio.h>
8
9
10 struct trie_node
11 {
12 char key;
13 struct trie_node * child;
14 struct trie_node * sibling;
15 void * data;
16 };
17
18 struct trie
19 {
20 struct trie_node * root;
21 };
22
23 struct trie_node * trie_search_children(struct trie_node * node, char k);
24 void trie_visit_node(struct trie * trie, struct trie_node * node, void (*op)(char * k, void * d), char * key);
25 void trie_print_node(struct trie_node * node);
26 void trie_print_node(struct trie_node * node);
27 void trie_node_dump_preorder(struct trie * trie, struct trie_node * node, int depth);
28 void trie_node_dump_raw(struct trie_node * node, int depth);
29
30 ////////////////////////////////////////////////////////////////////////////////
31 struct trie *
32 trie_new()
33 {
34 struct trie * trie = malloc(sizeof(struct trie));
35 if (NULL == trie)
36 return NULL;
37
38 trie->root = malloc(sizeof(struct trie_node));
39 if (NULL == trie->root)
40 return NULL;
41
42 trie->root->child = trie->root->sibling = NULL;
43 trie->root->key = '\0';
44 trie->root->data = NULL;
45
46 return trie;
47 }
48
49 ////////////////////////////////////////////////////////////////////////////////
50 void
51 trie_delete(struct trie * trie)
52 {
53 if (NULL == trie)
54 return;
55
56 free(trie);
57 }
58
59 ////////////////////////////////////////////////////////////////////////////////
60 char *
61 trie_insert(struct trie * trie, char * key, void * data)
62 {
63 if ( (NULL == trie) || (NULL == key) )
64 return NULL;
65
66 struct trie_node * curr = trie->root;
67 struct trie_node * result;
68
69 size_t len = strlen(key);
70 for (int i = 0; i <= len; ++i)
71 {
72 result = trie_search_children(curr, key[i]);
73 if (NULL == result)
74 {
75 // current char is not in the trie yet, allocate a new node and attach it to the children
76 struct trie_node * new = malloc(sizeof(struct trie_node));
77 if (NULL == new)
78 return NULL;
79 new->key = tolower(key[i]);
80 new->child = new->sibling = NULL;
81 new->data = NULL;
82
83 if (NULL == curr->child)
84 curr->child = new;
85 else
86 {
87 struct trie_node * p = curr->child;
88 while (p->sibling)
89 p = p->sibling;
90 p->sibling = new;
91 }
92
93 curr = new;
94 }
95 else
96 curr = result;
97 }
98
99 // At this point, curr is either pointing to a new \0 node with a NULL data pointer,
100 // or an existing \0 node with a valid data pointer (in which case we were asked to "insert"
101 // a key that was already present in the trie.
102 // For now I am simply ignoring collisions. We will update the data.
103
104 curr->data = data;
105 return key;
106 }
107
108 ////////////////////////////////////////////////////////////////////////////////
109 struct trie_node *
110 trie_search_children(struct trie_node * node, char k)
111 {
112 struct trie_node * p = node->child;
113 if (NULL == p)
114 return NULL;
115
116 while ( (NULL != p) && (p->key != tolower(k)) )
117 p = p->sibling;
118 return p;
119 }
120
121 ////////////////////////////////////////////////////////////////////////////////
122 void *
123 trie_find(struct trie * trie, char * key)
124 {
125 if ( (NULL == trie) || (NULL == key) )
126 return NULL;
127
128 struct trie_node * node = trie->root;
129 size_t len = strlen(key);
130 for (int i = 0; i <= len; i++)
131 {
132 node = trie_search_children(node, key[i]);
133 if (NULL == node)
134 return NULL;
135 if ('\0' == key[i])
136 return node->data;
137 }
138
139 // Should never get here
140 return NULL;
141 }
142
143 ////////////////////////////////////////////////////////////////////////////////
144 void *
145 trie_remove(struct trie * trie, char * key)
146 {
147 return NULL;
148 }
149
150 ////////////////////////////////////////////////////////////////////////////////
151 void
152 trie_walk_keys(struct trie * trie, void (*op)(char * k, void * d))
153 {
154 if (NULL == trie)
155 return;
156 trie_visit_node(trie, trie->root, op, "");
157 }
158
159 ////////////////////////////////////////////////////////////////////////////////
160 void
161 trie_visit_node(struct trie * trie, struct trie_node * node, void (*op)(char * k, void * d), char * key)
162 {
163 if ( (node->key == '\0') && (node != trie->root) )
164 op(key, node->data);
165 else
166 {
167 size_t len = strlen(key);
168 char * k = malloc(len+2);
169 if (NULL == k)
170 return;
171 strcpy(k, key);
172 k[len] = node->key;
173 k[len+1] = '\0';
174 struct trie_node * p = node->child;
175 while (NULL != p)
176 {
177 trie_visit_node(trie, p, op, k);
178 p = p->sibling;
179 }
180 }
181 }
182
183 ////////////////////////////////////////////////////////////////////////////////
184 void trie_dump_raw(struct trie * trie)
185 {
186 if (NULL == trie)
187 return;
188
189 int depth = -1;
190 trie_node_dump_raw(trie->root, depth);
191 }
192
193 ////////////////////////////////////////////////////////////////////////////////
194 void
195 trie_node_dump_raw(struct trie_node * node, int depth)
196 {
197 for (int i=0; i < depth; i++)
198 printf(" ");
199 trie_print_node(node);
200 if (node->child)
201 trie_node_dump_raw(node->child, depth+1);
202 if (NULL != node->sibling)
203 trie_node_dump_raw(node->sibling, depth+1);
204 }
205
206 ////////////////////////////////////////////////////////////////////////////////
207 void trie_dump(struct trie * trie)
208 {
209 if (NULL == trie)
210 return;
211
212 int depth = -1;
213 trie_node_dump_preorder(trie, trie->root, depth);
214 }
215
216 ////////////////////////////////////////////////////////////////////////////////
217 void
218 trie_node_dump_preorder(struct trie * trie, struct trie_node * node, int depth)
219 {
220 printf("%c", node->key);
221 if ( (node != trie->root) && ('\0' == node->key) )
222 printf("\n");
223 if (node->child)
224 trie_node_dump_preorder(trie, node->child, depth+1);
225 if (NULL != node->sibling)
226 {
227 for (int i=0; i < depth; i++)
228 printf(" ");
229 trie_node_dump_preorder(trie, node->sibling, depth);
230 }
231 }
232
233 ////////////////////////////////////////////////////////////////////////////////
234 void
235 trie_print_node(struct trie_node * node)
236 {
237 printf("%p\tchild %p\tsibling %p\tkey %c\tdata %p\n", node, node->child, node->sibling, node->key, node->data);
238 }