Line data Source code
1 : /* -*- Mode: C; tab-width: 8; indent-tabs-mode: t; c-basic-offset: 8 -*- */
2 : /*
3 : * lt-trie.c
4 : * Copyright (C) 2011-2012 Akira TAGOH
5 : *
6 : * Authors:
7 : * Akira TAGOH <akira@tagoh.org>
8 : *
9 : * You may distribute under the terms of either the GNU
10 : * Lesser General Public License or the Mozilla Public
11 : * License, as specified in the README file.
12 : */
13 : #ifdef HAVE_CONFIG_H
14 : #include "config.h"
15 : #endif
16 :
17 : #include <stdlib.h>
18 : #include <string.h>
19 : #include "lt-mem.h"
20 : #include "lt-messages.h"
21 : #include "lt-trie.h"
22 :
23 :
24 : typedef struct _lt_trie_node_t lt_trie_node_t;
25 : struct _lt_trie_node_t {
26 : lt_mem_t parent;
27 : lt_trie_node_t *node[255];
28 : lt_pointer_t data;
29 : char index_;
30 : };
31 : struct _lt_trie_t {
32 : lt_mem_t parent;
33 : lt_trie_node_t *root;
34 : };
35 :
36 : /*< private >*/
37 : static lt_trie_node_t *
38 41020 : lt_trie_node_new(char index_)
39 : {
40 41020 : lt_trie_node_t *retval = lt_mem_alloc_object(sizeof (lt_trie_node_t));
41 :
42 41020 : if (retval) {
43 41020 : retval->index_ = index_;
44 : }
45 :
46 41020 : return retval;
47 : }
48 :
49 : #if 0
50 : static lt_trie_node_t *
51 : lt_trie_node_ref(lt_trie_node_t *node)
52 : {
53 : lt_return_val_if_fail (node != NULL, NULL);
54 :
55 : return lt_mem_ref(&node->parent);
56 : }
57 : #endif
58 :
59 : static void
60 41020 : lt_trie_node_unref(lt_trie_node_t *node)
61 : {
62 41020 : if (node)
63 41020 : lt_mem_unref(&node->parent);
64 41020 : }
65 :
66 : static lt_bool_t
67 142084 : lt_trie_node_add(lt_trie_node_t *node,
68 : const char *key,
69 : lt_pointer_t data,
70 : lt_destroy_func_t func,
71 : lt_bool_t replace)
72 : {
73 : int index_;
74 :
75 142084 : lt_return_val_if_fail (node != NULL, FALSE);
76 142084 : lt_return_val_if_fail (key != NULL, FALSE);
77 :
78 142084 : index_ = *key - 1;
79 142084 : if (*key == 0) {
80 35204 : if (node->data && !replace) {
81 0 : return FALSE;
82 : } else {
83 35204 : if (node->data) {
84 0 : lt_mem_delete_ref(&node->parent, node->data);
85 : }
86 35204 : node->data = data;
87 35204 : if (func)
88 35204 : lt_mem_add_ref(&node->parent, data, func);
89 :
90 35204 : return TRUE;
91 : }
92 : }
93 106880 : if (!node->node[index_]) {
94 40992 : node->node[index_] = lt_trie_node_new(index_);
95 40992 : if (!node->node[index_])
96 0 : return FALSE;
97 40992 : lt_mem_add_ref(&node->parent, node->node[index_],
98 : (lt_destroy_func_t)lt_trie_node_unref);
99 40992 : lt_mem_add_weak_pointer(&node->node[index_]->parent,
100 40992 : (lt_pointer_t *)&node->node[index_]);
101 : }
102 :
103 106880 : return lt_trie_node_add(node->node[index_], key + 1, data, func, replace);
104 : }
105 :
106 : static lt_bool_t
107 0 : lt_trie_node_remove(lt_trie_node_t *node,
108 : lt_trie_node_t *parent,
109 : const char *key)
110 : {
111 : int i, index_;
112 0 : lt_bool_t found = FALSE;
113 :
114 0 : lt_return_val_if_fail (node != NULL, FALSE);
115 0 : lt_return_val_if_fail (key != NULL, FALSE);
116 :
117 0 : index_ = *key - 1;
118 0 : if (*key == 0) {
119 0 : if (!node->data)
120 0 : return FALSE;
121 0 : lt_mem_delete_ref(&node->parent, node->data);
122 0 : node->data = NULL;
123 0 : for (i = 0; i < 255; i++) {
124 0 : found |= node->node[i] != NULL;
125 : }
126 0 : if (!found)
127 0 : lt_mem_delete_ref(&parent->parent, node);
128 0 : return TRUE;
129 : }
130 0 : if (!node->node[index_])
131 0 : return FALSE;
132 :
133 0 : return lt_trie_node_remove(node->node[index_], node, key + 1);
134 : }
135 :
136 : static const lt_pointer_t
137 230 : lt_trie_node_lookup(lt_trie_node_t *node,
138 : const char *key)
139 : {
140 : int index_;
141 :
142 230 : lt_return_val_if_fail (node != NULL, NULL);
143 230 : lt_return_val_if_fail (key != NULL, NULL);
144 :
145 230 : index_ = *key - 1;
146 230 : if (*key == 0)
147 36 : return node->data;
148 194 : if (!node->node[index_])
149 32 : return NULL;
150 :
151 162 : return lt_trie_node_lookup(node->node[index_], key + 1);
152 : }
153 :
154 : /*< protected >*/
155 :
156 : /*< public >*/
157 : lt_trie_t *
158 28 : lt_trie_new(void)
159 : {
160 28 : return lt_mem_alloc_object(sizeof (lt_trie_t));
161 : }
162 :
163 : lt_trie_t *
164 0 : lt_trie_ref(lt_trie_t *trie)
165 : {
166 0 : lt_return_val_if_fail (trie != NULL, NULL);
167 :
168 0 : return lt_mem_ref(&trie->parent);
169 : }
170 :
171 : void
172 28 : lt_trie_unref(lt_trie_t *trie)
173 : {
174 28 : if (trie)
175 28 : lt_mem_unref(&trie->parent);
176 28 : }
177 :
178 : lt_bool_t
179 0 : lt_trie_add(lt_trie_t *trie,
180 : const char *key,
181 : lt_pointer_t data,
182 : lt_destroy_func_t func)
183 : {
184 0 : lt_return_val_if_fail (trie != NULL, FALSE);
185 0 : lt_return_val_if_fail (key != NULL, FALSE);
186 0 : lt_return_val_if_fail (data != NULL, FALSE);
187 :
188 0 : if (!trie->root) {
189 0 : if ((trie->root = lt_trie_node_new(0)) == NULL)
190 0 : return FALSE;
191 0 : lt_mem_add_ref(&trie->parent, trie->root,
192 : (lt_destroy_func_t)lt_trie_node_unref);
193 0 : lt_mem_add_weak_pointer(&trie->root->parent, (lt_pointer_t *)&trie->root);
194 : }
195 :
196 0 : return lt_trie_node_add(trie->root, key, data, func, FALSE);
197 : }
198 :
199 : lt_bool_t
200 35204 : lt_trie_replace(lt_trie_t *trie,
201 : const char *key,
202 : lt_pointer_t data,
203 : lt_destroy_func_t func)
204 : {
205 35204 : lt_return_val_if_fail (trie != NULL, FALSE);
206 35204 : lt_return_val_if_fail (key != NULL, FALSE);
207 35204 : lt_return_val_if_fail (data != NULL, FALSE);
208 :
209 35204 : if (!trie->root) {
210 28 : if ((trie->root = lt_trie_node_new(0)) == NULL)
211 0 : return FALSE;
212 28 : lt_mem_add_ref(&trie->parent, trie->root,
213 : (lt_destroy_func_t)lt_trie_node_unref);
214 : }
215 :
216 35204 : return lt_trie_node_add(trie->root, key, data, func, TRUE);
217 : }
218 :
219 : lt_bool_t
220 0 : lt_trie_remove(lt_trie_t *trie,
221 : const char *key)
222 : {
223 0 : lt_return_val_if_fail (trie != NULL, FALSE);
224 0 : lt_return_val_if_fail (key != NULL, FALSE);
225 0 : lt_return_val_if_fail (*key != 0, FALSE);
226 :
227 0 : if (!trie->root)
228 0 : return FALSE;
229 :
230 0 : return lt_trie_node_remove(trie->root, NULL, key);
231 : }
232 :
233 : lt_pointer_t
234 68 : lt_trie_lookup(lt_trie_t *trie,
235 : const char *key)
236 : {
237 68 : lt_return_val_if_fail (trie != NULL, NULL);
238 68 : lt_return_val_if_fail (key != NULL, NULL);
239 :
240 68 : if (!trie->root)
241 0 : return NULL;
242 :
243 68 : return lt_trie_node_lookup(trie->root, key);
244 : }
245 :
246 : lt_list_t *
247 0 : lt_trie_keys(lt_trie_t *trie)
248 : {
249 : lt_trie_iter_t iter;
250 0 : lt_list_t *retval = NULL;
251 : lt_pointer_t key;
252 :
253 0 : lt_return_val_if_fail (trie != NULL, NULL);
254 :
255 0 : if (trie->root)
256 0 : return NULL;
257 :
258 0 : lt_trie_iter_init(&iter, trie);
259 :
260 0 : while (lt_trie_iter_next(&iter, &key, NULL)) {
261 0 : retval = lt_list_append(retval, key, free);
262 : }
263 :
264 0 : lt_trie_iter_finish(&iter);
265 :
266 0 : return retval;
267 : }
268 :
269 : lt_trie_iter_t *
270 0 : lt_trie_iter_init(lt_trie_iter_t *iter,
271 : lt_trie_t *trie)
272 : {
273 : int i;
274 :
275 0 : lt_return_val_if_fail (iter != NULL, NULL);
276 0 : lt_return_val_if_fail (trie != NULL, NULL);
277 :
278 0 : iter->pos_str = lt_string_new(NULL);
279 0 : iter->stack = NULL;
280 0 : if (trie->root) {
281 0 : lt_trie_node_t *node = trie->root;
282 :
283 0 : for (i = 0; i < 255; i++) {
284 0 : if (node->node[i])
285 0 : iter->stack = lt_list_append(iter->stack, node->node[i], NULL);
286 : }
287 : /* add a terminator */
288 0 : iter->stack = lt_list_append(iter->stack, NULL, NULL);
289 : }
290 :
291 0 : return iter;
292 : }
293 :
294 : void
295 0 : lt_trie_iter_finish(lt_trie_iter_t *iter)
296 : {
297 0 : lt_return_if_fail (iter != NULL);
298 :
299 0 : if (iter->stack)
300 0 : lt_list_free(iter->stack);
301 0 : lt_string_unref(iter->pos_str);
302 : }
303 :
304 : lt_bool_t
305 0 : lt_trie_iter_next(lt_trie_iter_t *iter,
306 : lt_pointer_t *key,
307 : lt_pointer_t *value)
308 : {
309 : int i;
310 0 : lt_trie_node_t *node = NULL;
311 :
312 0 : lt_return_val_if_fail (iter != NULL, FALSE);
313 :
314 : while (1) {
315 0 : if (lt_list_length(iter->stack) == 0)
316 0 : break;
317 0 : iter->stack = lt_list_pop(iter->stack, (lt_pointer_t *)&node);
318 0 : if (node) {
319 0 : lt_string_append_c(iter->pos_str, node->index_);
320 : } else {
321 0 : lt_string_truncate(iter->pos_str, -1);
322 0 : continue;
323 : }
324 0 : for (i = 0; i < 255; i++) {
325 0 : if (node->node[i])
326 0 : iter->stack = lt_list_append(iter->stack, node->node[i], NULL);
327 : }
328 : /* add a terminator */
329 0 : iter->stack = lt_list_append(iter->stack, NULL, NULL);
330 0 : if (node->data) {
331 0 : if (key) {
332 0 : *key = strdup(lt_string_value(iter->pos_str));
333 : }
334 0 : if (value)
335 0 : *value = node->data;
336 :
337 0 : return TRUE;
338 : }
339 0 : }
340 :
341 0 : return FALSE;
342 : }
|
