1 /* vifm
2 * Copyright (C) 2015 xaizek.
3 *
4 * This program is free software; you can redistribute it and/or modify
5 * it under the terms of the GNU General Public License as published by
6 * the Free Software Foundation; either version 2 of the License, or
7 * (at your option) any later version.
8 *
9 * This program is distributed in the hope that it will be useful,
10 * but WITHOUT ANY WARRANTY; without even the implied warranty of
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 * GNU General Public License for more details.
13 *
14 * You should have received a copy of the GNU General Public License
15 * along with this program; if not, write to the Free Software
16 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA
17 */
18
19 #include "trie.h"
20
21 #include <stdlib.h> /* calloc() free() */
22
23 /* Trie node. */
24 struct trie_t
25 {
26 trie_t *left; /* Nodes with values less than value. */
27 trie_t *right; /* Nodes with values greater than value. */
28 trie_t *children; /* Child nodes. */
29 void *data; /* Data associated with the key. */
30 char value; /* Value of the node. */
31 char exists; /* Whether this node exists or it's an intermediate node. */
32 };
33
34 static trie_t *clone_nodes(trie_t *trie, int *error);
35 static void get_or_create(trie_t *trie, const char str[], void *data,
36 int *result);
37
38 trie_t *
trie_create(void)39 trie_create(void)
40 {
41 return calloc(1U, sizeof(struct trie_t));
42 }
43
44 trie_t *
trie_clone(trie_t * trie)45 trie_clone(trie_t *trie)
46 {
47 int error = 0;
48
49 trie = clone_nodes(trie, &error);
50 if(error)
51 {
52 trie_free(trie);
53 return NULL;
54 }
55
56 return trie;
57 }
58
59 /* Clones node and all its relatives. Sets *error to non-zero on error.
60 * Returns new node. */
61 static trie_t *
clone_nodes(trie_t * trie,int * error)62 clone_nodes(trie_t *trie, int *error)
63 {
64 trie_t *new_trie;
65
66 if(trie == NULL)
67 {
68 return NULL;
69 }
70
71 new_trie = malloc(sizeof(*new_trie));
72 if(new_trie == NULL)
73 {
74 *error = 1;
75 return NULL;
76 }
77
78 *new_trie = *trie;
79 new_trie->left = clone_nodes(trie->left, error);
80 new_trie->right = clone_nodes(trie->right, error);
81 new_trie->children = clone_nodes(trie->children, error);
82
83 return new_trie;
84 }
85
86 void
trie_free(trie_t * trie)87 trie_free(trie_t *trie)
88 {
89 if(trie != NULL)
90 {
91 trie_free(trie->left);
92 trie_free(trie->right);
93 trie_free(trie->children);
94 free(trie);
95 }
96 }
97
98 void
trie_free_with_data(trie_t * trie,trie_free_func free_func)99 trie_free_with_data(trie_t *trie, trie_free_func free_func)
100 {
101 if(trie != NULL)
102 {
103 trie_free_with_data(trie->left, free_func);
104 trie_free_with_data(trie->right, free_func);
105 trie_free_with_data(trie->children, free_func);
106 free_func(trie->data);
107 free(trie);
108 }
109 }
110
111 int
trie_put(trie_t * trie,const char str[])112 trie_put(trie_t *trie, const char str[])
113 {
114 return trie_set(trie, str, NULL);
115 }
116
117 int
trie_set(trie_t * trie,const char str[],const void * data)118 trie_set(trie_t *trie, const char str[], const void *data)
119 {
120 int result;
121
122 if(trie == NULL)
123 {
124 return -1;
125 }
126
127 get_or_create(trie, str, (void *)data, &result);
128 return result;
129 }
130
131 /* Gets node which might involve its creation. Sets *return to negative value
132 * on error, to zero on successful insertion and to positive number if element
133 * was already in the trie. */
134 static void
get_or_create(trie_t * trie,const char str[],void * data,int * result)135 get_or_create(trie_t *trie, const char str[], void *data, int *result)
136 {
137 trie_t **link = ≜
138 while(1)
139 {
140 /* Create inexistent node. */
141 if(trie == NULL)
142 {
143 trie = trie_create();
144 if(trie == NULL)
145 {
146 *result = -1;
147 break;
148 }
149 trie->value = *str;
150 *link = trie;
151 }
152
153 if(trie->value == *str)
154 {
155 if(*str == '\0')
156 {
157 /* Found full match. */
158 *result = (trie->exists != 0);
159 trie->exists = 1;
160 trie->data = data;
161 break;
162 }
163
164 link = &trie->children;
165 ++str;
166 }
167 else
168 {
169 link = (*str < trie->value) ? &trie->left : &trie->right;
170 }
171 trie = *link;
172 }
173 }
174
175 int
trie_get(trie_t * trie,const char str[],void ** data)176 trie_get(trie_t *trie, const char str[], void **data)
177 {
178 while(1)
179 {
180 if(trie == NULL)
181 {
182 return 1;
183 }
184
185 if(trie->value == *str)
186 {
187 if(*str == '\0')
188 {
189 /* Found full match. */
190 if(!trie->exists)
191 {
192 return 1;
193 }
194 *data = trie->data;
195 return 0;
196 }
197
198 trie = trie->children;
199 ++str;
200 continue;
201 }
202
203 trie = (*str < trie->value) ? trie->left : trie->right;
204 }
205 }
206
207 /* vim: set tabstop=2 softtabstop=2 shiftwidth=2 noexpandtab cinoptions-=(0 : */
208 /* vim: set cinoptions+=t0 filetype=c : */
209