Mercurial > data_structures

view src/trie_sedgewick.c @ 16:5d8158ad2d61

find changesets by author, revision, files, or words in the commit message
sedgewick trie
author Eris Caffee <discordia@eldalin.com>
date Thu, 04 Oct 2012 23:07:48 -0500
parents
children
line source
1 #include <stdlib.h>
2 #include <string.h>
3 #include <stdio.h>
4
5 #include "trie_sedgewick.h"
6
7 // Our alphabet size. One byte's worth.
8 #define RADIX 256
9
10 struct trie_node
11 {
12 void * data;
13 struct trie_node * next[RADIX];
14 };
15
16 struct trie
17 {
18 struct trie_node * root;
19 };
20
21
22 struct trie_node * trie_node_new();
23 void * trie_node_get(struct trie_node * node, char * key, int d);
24 struct trie_node * trie_node_put(struct trie_node * node, char * key, void * data, int d);
25
26 ////////////////////////////////////////////////////////////////////////////////
27 struct trie_node *
28 trie_node_new()
29 {
30 struct trie_node * node = malloc(sizeof(struct trie_node));
31 if (NULL == node)
32 return NULL;
33
34 for (int i = 0; i < RADIX; ++i)
35 node->next[i] = NULL;
36 node->data = NULL;
37
38 return node;
39 }
40
41 ////////////////////////////////////////////////////////////////////////////////
42 struct trie *
43 trie_new()
44 {
45 struct trie * trie = malloc(sizeof(struct trie));
46 if (NULL == trie)
47 return NULL;
48
49 trie->root = NULL;
50 return trie;
51 }
52
53 ////////////////////////////////////////////////////////////////////////////////
54 void
55 trie_delete(struct trie * trie)
56 {
57 if (NULL == trie)
58 return;
59 // TODO free nodes
60 free(trie);
61 }
62
63 ////////////////////////////////////////////////////////////////////////////////
64 char *
65 trie_put(struct trie * trie, char * key, void * data)
66 {
67 if ( (NULL == trie) || (NULL == key) )
68 return NULL;
69 trie->root = trie_node_put(trie->root, key, data, 0);
70 return key;
71 }
72
73 ////////////////////////////////////////////////////////////////////////////////
74 struct trie_node *
75 trie_node_put(struct trie_node * node, char * key, void * data, int d)
76 {
77 if (NULL == node)
78 node = trie_node_new();
79 if (NULL == node)
80 return NULL;
81
82 if (d == strlen(key))
83 {
84 node->data = data;
85 return node;
86 }
87 int c = key[d];
88 node->next[c] = trie_node_put(node->next[c], key, data, d+1);
89 return node;
90 }
91
92 ////////////////////////////////////////////////////////////////////////////////
93 void *
94 trie_get(struct trie * trie, char * key)
95 {
96 if ( (NULL == trie) || (NULL == key) )
97 return NULL;
98
99 struct trie_node * node = trie_node_get(trie->root, key, 0);
100 if (NULL == node)
101 return NULL;
102 return node->data;
103 }
104
105 ////////////////////////////////////////////////////////////////////////////////
106 void *
107 trie_node_get(struct trie_node * node, char * key, int d)
108 {
109 if (NULL == node)
110 return NULL;
111 if (d == strlen(key))
112 return node;
113 return trie_node_get(node->next[(int) key[d]], key, d+1);
114 }