Debian Codegraph @

datrie/trie.c

raw
1 /* -*- Mode: C; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
2 /*
3 * libdatrie - Double-Array Trie Library
4 * Copyright (C) 2006 Theppitak Karoonboonyanan <[email protected]>
5 *
6 * This library is free software; you can redistribute it and/or
7 * modify it under the terms of the GNU Lesser General Public
8 * License as published by the Free Software Foundation; either
9 * version 2.1 of the License, or (at your option) any later version.
10 *
11 * This library is distributed in the hope that it will be useful,
12 * but WITHOUT ANY WARRANTY; without even the implied warranty of
13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
14 * Lesser General Public License for more details.
15 *
16 * You should have received a copy of the GNU Lesser General Public
17 * License along with this library; if not, write to the Free Software
18 * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
19 */
20
21 /*
22 * trie.c - Trie data type and functions
23 * Created: 2006-08-11
24 * Author: Theppitak Karoonboonyanan <[email protected]>
25 */
26
27 #include <stdlib.h>
28 #include <string.h>
29
30 #include "trie.h"
31 #include "trie-private.h"
32 #include "fileutils.h"
33 #include "alpha-map.h"
34 #include "alpha-map-private.h"
35 #include "darray.h"
36 #include "tail.h"
37 #include "trie-string.h"
38
39 /**
40 * @brief Trie structure
41 */
42 struct _Trie {
43 AlphaMap *alpha_map;
44 DArray *da;
45 Tail *tail;
46
47 Bool is_dirty;
48 };
49
50 /**
51 * @brief TrieState structure
52 */
53 struct _TrieState {
54 const Trie *trie; /**< the corresponding trie */
55 TrieIndex index; /**< index in double-array/tail structures */
56 short suffix_idx; /**< suffix character offset, if in suffix */
57 short is_suffix; /**< whether it is currently in suffix part */
58 };
59
60 /**
61 * @brief TrieIterator structure
62 */
63 struct _TrieIterator {
64 const TrieState *root; /**< the state to start iteration from */
65 TrieState *state; /**< the current state */
66 TrieString *key; /**< buffer for calculating the entry key */
67 };
68
69
70 /*------------------------*
71 * INTERNAL FUNCTIONS *
72 *------------------------*/
73
74 #define trie_da_is_separate(da,s) (da_get_base ((da), (s)) < 0)
75 #define trie_da_get_tail_index(da,s) (-da_get_base ((da), (s)))
76 #define trie_da_set_tail_index(da,s,v) (da_set_base ((da), (s), -(v)))
77
78 static TrieState * trie_state_new (const Trie *trie,
79 TrieIndex index,
80 short suffix_idx,
81 short is_suffix);
82
83 static Bool trie_store_conditionally (Trie *trie,
84 const AlphaChar *key,
85 TrieData data,
86 Bool is_overwrite);
87
88 static Bool trie_branch_in_branch (Trie *trie,
89 TrieIndex sep_node,
90 const TrieChar *suffix,
91 TrieData data);
92
93 static Bool trie_branch_in_tail (Trie *trie,
94 TrieIndex sep_node,
95 const TrieChar *suffix,
96 TrieData data);
97
98 /*-----------------------*
99 * GENERAL FUNCTIONS *
100 *-----------------------*/
101
102 /**
103 * @brief Create a new trie
104 *
105 * @param alpha_map : the alphabet set for the trie
106 *
107 * @return a pointer to the newly created trie, NULL on failure
108 *
109 * Create a new empty trie object based on the given @a alpha_map alphabet
110 * set. The trie contents can then be added and deleted with trie_store() and
111 * trie_delete() respectively.
112 *
113 * The created object must be freed with trie_free().
114 */
115 Trie *
116 trie_new (const AlphaMap *alpha_map)
117 {
118 Trie *trie;
119
120 trie = (Trie *) malloc (sizeof (Trie));
121 if (UNLIKELY (!trie))
122 return NULL;
123
124 trie->alpha_map = alpha_map_clone (alpha_map);
125 if (UNLIKELY (!trie->alpha_map))
126 goto exit_trie_created;
127
128 trie->da = da_new ();
129 if (UNLIKELY (!trie->da))
130 goto exit_alpha_map_created;
131
132 trie->tail = tail_new ();
133 if (UNLIKELY (!trie->tail))
134 goto exit_da_created;
135
136 trie->is_dirty = TRUE;
137 return trie;
138
139 exit_da_created:
140 da_free (trie->da);
141 exit_alpha_map_created:
142 alpha_map_free (trie->alpha_map);
143 exit_trie_created:
144 free (trie);
145 return NULL;
146 }
147
148 /**
149 * @brief Create a new trie by loading from a file
150 *
151 * @param path : the path to the file
152 *
153 * @return a pointer to the created trie, NULL on failure
154 *
155 * Create a new trie and initialize its contents by loading from the file at
156 * given @a path.
157 *
158 * The created object must be freed with trie_free().
159 */
160 Trie *
161 trie_new_from_file (const char *path)
162 {
163 Trie *trie;
164 FILE *trie_file;
165
166 trie_file = fopen (path, "rb");
167 if (!trie_file)
168 return NULL;
169
170 trie = trie_fread (trie_file);
171 fclose (trie_file);
172 return trie;
173 }
174
175 /**
176 * @brief Create a new trie by reading from an open file
177 *
178 * @param file : the handle of the open file
179 *
180 * @return a pointer to the created trie, NULL on failure
181 *
182 * Create a new trie and initialize its contents by reading from the open
183 * @a file. After reading, the file pointer is left at the end of the trie data.
184 * This can be useful for reading embedded trie index as part of a file data.
185 *
186 * The created object must be freed with trie_free().
187 *
188 * Available since: 0.2.4
189 */
190 Trie *
191 trie_fread (FILE *file)
192 {
193 Trie *trie;
194
195 trie = (Trie *) malloc (sizeof (Trie));
196 if (UNLIKELY (!trie))
197 return NULL;
198
199 if (NULL == (trie->alpha_map = alpha_map_fread_bin (file)))
200 goto exit_trie_created;
201 if (NULL == (trie->da = da_fread (file)))
202 goto exit_alpha_map_created;
203 if (NULL == (trie->tail = tail_fread (file)))
204 goto exit_da_created;
205
206 trie->is_dirty = FALSE;
207 return trie;
208
209 exit_da_created:
210 da_free (trie->da);
211 exit_alpha_map_created:
212 alpha_map_free (trie->alpha_map);
213 exit_trie_created:
214 free (trie);
215 return NULL;
216 }
217
218 /**
219 * @brief Free a trie object
220 *
221 * @param trie : the trie object to free
222 *
223 * Destruct the @a trie and free its allocated memory.
224 */
225 void
226 trie_free (Trie *trie)
227 {
228 alpha_map_free (trie->alpha_map);
229 da_free (trie->da);
230 tail_free (trie->tail);
231 free (trie);
232 }
233
234 /**
235 * @brief Save a trie to file
236 *
237 * @param trie : the trie
238 *
239 * @param path : the path to the file
240 *
241 * @return 0 on success, non-zero on failure
242 *
243 * Create a new file at the given @a path and write @a trie data to it.
244 * If @a path already exists, its contents will be replaced.
245 */
246 int
247 trie_save (Trie *trie, const char *path)
248 {
249 FILE *file;
250 int res = 0;
251
252 file = fopen (path, "wb+");
253 if (!file)
254 return -1;
255
256 res = trie_fwrite (trie, file);
257 fclose (file);
258 return res;
259 }
260
261
262 /**
263 * @brief Get trie serialized size
264 *
265 * @param trie : the trie
266 *
267 * @return size of the trie in bytes
268 *
269 * Returns size that would be occupied by a trie if it was
270 * serialized into a binary blob or file.
271 *
272 * Available since: 0.2.13
273 */
274 size_t
275 trie_get_serialized_size (Trie *trie)
276 {
277 return alpha_map_get_serialized_size (trie->alpha_map)
278 + da_get_serialized_size (trie->da)
279 + tail_get_serialized_size (trie->tail);
280 }
281
282
283 /**
284 * @brief Serializes trie data into a memory buffer (including mapping)
285 *
286 * @param trie : the trie
287 *
288 * @param ptr : a pointer to current position inside of a preallocated buffer.
289 *
290 * Write @a trie data to a current position in a buffer pointed by @a ptr.
291 * This can be useful for embedding trie index as part of a file data.
292 *
293 * The size that the trie will occupy can be calculated using
294 * trie_get_serialized_size()
295 *
296 * Available since: 0.2.13
297 */
298 void
299 trie_serialize (Trie *trie, uint8 *ptr)
300 {
301 uint8 *ptr1 = ptr;
302 alpha_map_serialize_bin (trie->alpha_map, &ptr1);
303 da_serialize (trie->da, &ptr1);
304 tail_serialize (trie->tail, &ptr1);
305 trie->is_dirty = FALSE;
306 }
307
308
309 /**
310 * @brief Write trie data to an open file
311 *
312 * @param trie : the trie
313 *
314 * @param file : the open file
315 *
316 * @return 0 on success, non-zero on failure
317 *
318 * Write @a trie data to @a file which is opened for writing.
319 * After writing, the file pointer is left at the end of the trie data.
320 * This can be useful for embedding trie index as part of a file data.
321 *
322 * Available since: 0.2.4
323 */
324 int
325 trie_fwrite (Trie *trie, FILE *file)
326 {
327 if (alpha_map_fwrite_bin (trie->alpha_map, file) != 0)
328 return -1;
329
330 if (da_fwrite (trie->da, file) != 0)
331 return -1;
332
333 if (tail_fwrite (trie->tail, file) != 0)
334 return -1;
335
336 trie->is_dirty = FALSE;
337
338 return 0;
339 }
340
341 /**
342 * @brief Check pending changes
343 *
344 * @param trie : the trie object
345 *
346 * @return TRUE if there are pending changes, FALSE otherwise
347 *
348 * Check if the @a trie is dirty with some pending changes and needs saving
349 * to keep the file synchronized.
350 */
351 Bool
352 trie_is_dirty (const Trie *trie)
353 {
354 return trie->is_dirty;
355 }
356
357
358 /*------------------------------*
359 * GENERAL QUERY OPERATIONS *
360 *------------------------------*/
361
362 /**
363 * @brief Retrieve an entry from trie
364 *
365 * @param trie : the trie
366 * @param key : the key for the entry to retrieve
367 * @param o_data : the storage for storing the entry data on return
368 *
369 * @return boolean value indicating the existence of the entry.
370 *
371 * Retrieve an entry for the given @a key from @a trie. On return,
372 * if @a key is found and @a o_data is not NULL, @a *o_data is set
373 * to the data associated to @a key.
374 */
375 Bool
376 trie_retrieve (const Trie *trie, const AlphaChar *key, TrieData *o_data)
377 {
378 TrieIndex s;
379 short suffix_idx;
380 const AlphaChar *p;
381
382 /* walk through branches */
383 s = da_get_root (trie->da);
384 for (p = key; !trie_da_is_separate (trie->da, s); p++) {
385 TrieIndex tc = alpha_map_char_to_trie (trie->alpha_map, *p);
386 if (TRIE_INDEX_MAX == tc)
387 return FALSE;
388 if (!da_walk (trie->da, &s, (TrieChar) tc))
389 return FALSE;
390 if (0 == *p)
391 break;
392 }
393
394 /* walk through tail */
395 s = trie_da_get_tail_index (trie->da, s);
396 suffix_idx = 0;
397 for ( ; ; p++) {
398 TrieIndex tc = alpha_map_char_to_trie (trie->alpha_map, *p);
399 if (TRIE_INDEX_MAX == tc)
400 return FALSE;
401 if (!tail_walk_char (trie->tail, s, &suffix_idx, (TrieChar) tc))
402 return FALSE;
403 if (0 == *p)
404 break;
405 }
406
407 /* found, set the val and return */
408 if (o_data)
409 *o_data = tail_get_data (trie->tail, s);
410 return TRUE;
411 }
412
413 /**
414 * @brief Store a value for an entry to trie
415 *
416 * @param trie : the trie
417 * @param key : the key for the entry to store
418 * @param data : the data associated to the entry
419 *
420 * @return boolean value indicating the success of the operation
421 *
422 * Store a @a data for the given @a key in @a trie. If @a key does not
423 * exist in @a trie, it will be appended. If it does, its current data will
424 * be overwritten.
425 */
426 Bool
427 trie_store (Trie *trie, const AlphaChar *key, TrieData data)
428 {
429 return trie_store_conditionally (trie, key, data, TRUE);
430 }
431
432 /**
433 * @brief Store a value for an entry to trie only if the key is not present
434 *
435 * @param trie : the trie
436 * @param key : the key for the entry to store
437 * @param data : the data associated to the entry
438 *
439 * @return boolean value indicating the success of the operation
440 *
441 * Store a @a data for the given @a key in @a trie. If @a key does not
442 * exist in @a trie, it will be inserted. If it does, the function will
443 * return failure and the existing value will not be touched.
444 *
445 * This can be useful for multi-thread applications, as race condition
446 * can be avoided.
447 *
448 * Available since: 0.2.4
449 */
450 Bool
451 trie_store_if_absent (Trie *trie, const AlphaChar *key, TrieData data)
452 {
453 return trie_store_conditionally (trie, key, data, FALSE);
454 }
455
456 static Bool
457 trie_store_conditionally (Trie *trie,
458 const AlphaChar *key,
459 TrieData data,
460 Bool is_overwrite)
461 {
462 TrieIndex s, t;
463 short suffix_idx;
464 const AlphaChar *p, *sep;
465
466 /* walk through branches */
467 s = da_get_root (trie->da);
468 for (p = key; !trie_da_is_separate (trie->da, s); p++) {
469 TrieIndex tc = alpha_map_char_to_trie (trie->alpha_map, *p);
470 if (TRIE_INDEX_MAX == tc)
471 return FALSE;
472 if (!da_walk (trie->da, &s, (TrieChar) tc)) {
473 TrieChar *key_str;
474 Bool res;
475
476 key_str = alpha_map_char_to_trie_str (trie->alpha_map, p);
477 if (!key_str)
478 return FALSE;
479 res = trie_branch_in_branch (trie, s, key_str, data);
480 free (key_str);
481
482 return res;
483 }
484 if (0 == *p)
485 break;
486 }
487
488 /* walk through tail */
489 sep = p;
490 t = trie_da_get_tail_index (trie->da, s);
491 suffix_idx = 0;
492 for ( ; ; p++) {
493 TrieIndex tc = alpha_map_char_to_trie (trie->alpha_map, *p);
494 if (TRIE_INDEX_MAX == tc)
495 return FALSE;
496 if (!tail_walk_char (trie->tail, t, &suffix_idx, (TrieChar) tc)) {
497 TrieChar *tail_str;
498 Bool res;
499
500 tail_str = alpha_map_char_to_trie_str (trie->alpha_map, sep);
501 if (!tail_str)
502 return FALSE;
503 res = trie_branch_in_tail (trie, s, tail_str, data);
504 free (tail_str);
505
506 return res;
507 }
508 if (0 == *p)
509 break;
510 }
511
512 /* duplicated key, overwrite val if flagged */
513 if (!is_overwrite) {
514 return FALSE;
515 }
516 tail_set_data (trie->tail, t, data);
517 trie->is_dirty = TRUE;
518 return TRUE;
519 }
520
521 static Bool
522 trie_branch_in_branch (Trie *trie,
523 TrieIndex sep_node,
524 const TrieChar *suffix,
525 TrieData data)
526 {
527 TrieIndex new_da, new_tail;
528
529 new_da = da_insert_branch (trie->da, sep_node, *suffix);
530 if (TRIE_INDEX_ERROR == new_da)
531 return FALSE;
532
533 if (TRIE_CHAR_TERM != *suffix)
534 ++suffix;
535
536 new_tail = tail_add_suffix (trie->tail, suffix);
537 tail_set_data (trie->tail, new_tail, data);
538 trie_da_set_tail_index (trie->da, new_da, new_tail);
539
540 trie->is_dirty = TRUE;
541 return TRUE;
542 }
543
544 static Bool
545 trie_branch_in_tail (Trie *trie,
546 TrieIndex sep_node,
547 const TrieChar *suffix,
548 TrieData data)
549 {
550 TrieIndex old_tail, old_da, s;
551 const TrieChar *old_suffix, *p;
552
553 /* adjust separate point in old path */
554 old_tail = trie_da_get_tail_index (trie->da, sep_node);
555 old_suffix = tail_get_suffix (trie->tail, old_tail);
556 if (!old_suffix)
557 return FALSE;
558
559 for (p = old_suffix, s = sep_node; *p == *suffix; p++, suffix++) {
560 TrieIndex t = da_insert_branch (trie->da, s, *p);
561 if (TRIE_INDEX_ERROR == t)
562 goto fail;
563 s = t;
564 }
565
566 old_da = da_insert_branch (trie->da, s, *p);
567 if (TRIE_INDEX_ERROR == old_da)
568 goto fail;
569
570 if (TRIE_CHAR_TERM != *p)
571 ++p;
572 tail_set_suffix (trie->tail, old_tail, p);
573 trie_da_set_tail_index (trie->da, old_da, old_tail);
574
575 /* insert the new branch at the new separate point */
576 return trie_branch_in_branch (trie, s, suffix, data);
577
578 fail:
579 /* failed, undo previous insertions and return error */
580 da_prune_upto (trie->da, sep_node, s);
581 trie_da_set_tail_index (trie->da, sep_node, old_tail);
582 return FALSE;
583 }
584
585 /**
586 * @brief Delete an entry from trie
587 *
588 * @param trie : the trie
589 * @param key : the key for the entry to delete
590 *
591 * @return boolean value indicating whether the key exists and is removed
592 *
593 * Delete an entry for the given @a key from @a trie.
594 */
595 Bool
596 trie_delete (Trie *trie, const AlphaChar *key)
597 {
598 TrieIndex s, t;
599 short suffix_idx;
600 const AlphaChar *p;
601
602 /* walk through branches */
603 s = da_get_root (trie->da);
604 for (p = key; !trie_da_is_separate (trie->da, s); p++) {
605 TrieIndex tc = alpha_map_char_to_trie (trie->alpha_map, *p);
606 if (TRIE_INDEX_MAX == tc)
607 return FALSE;
608 if (!da_walk (trie->da, &s, (TrieChar) tc))
609 return FALSE;
610 if (0 == *p)
611 break;
612 }
613
614 /* walk through tail */
615 t = trie_da_get_tail_index (trie->da, s);
616 suffix_idx = 0;
617 for ( ; ; p++) {
618 TrieIndex tc = alpha_map_char_to_trie (trie->alpha_map, *p);
619 if (TRIE_INDEX_MAX == tc)
620 return FALSE;
621 if (!tail_walk_char (trie->tail, t, &suffix_idx, (TrieChar) tc))
622 return FALSE;
623 if (0 == *p)
624 break;
625 }
626
627 tail_delete (trie->tail, t);
628 da_set_base (trie->da, s, TRIE_INDEX_ERROR);
629 da_prune (trie->da, s);
630
631 trie->is_dirty = TRUE;
632 return TRUE;
633 }
634
635 /**
636 * @brief Enumerate entries in trie
637 *
638 * @param trie : the trie
639 * @param enum_func : the callback function to be called on each key
640 * @param user_data : user-supplied data to send as an argument to @a enum_func
641 *
642 * @return boolean value indicating whether all the keys are visited
643 *
644 * Enumerate all entries in trie. For each entry, the user-supplied
645 * @a enum_func callback function is called, with the entry key and data.
646 * Returning FALSE from such callback will stop enumeration and return FALSE.
647 */
648 Bool
649 trie_enumerate (const Trie *trie, TrieEnumFunc enum_func, void *user_data)
650 {
651 TrieState *root;
652 TrieIterator *iter;
653 Bool cont = TRUE;
654
655 root = trie_root (trie);
656 if (UNLIKELY (!root))
657 return FALSE;
658
659 iter = trie_iterator_new (root);
660 if (UNLIKELY (!iter))
661 goto exit_root_created;
662
663 while (cont && trie_iterator_next (iter)) {
664 AlphaChar *key = trie_iterator_get_key (iter);
665 TrieData data = trie_iterator_get_data (iter);
666 cont = (*enum_func) (key, data, user_data);
667 free (key);
668 }
669
670 trie_iterator_free (iter);
671 trie_state_free (root);
672
673 return cont;
674
675 exit_root_created:
676 trie_state_free (root);
677 return FALSE;
678 }
679
680
681 /*-------------------------------*
682 * STEPWISE QUERY OPERATIONS *
683 *-------------------------------*/
684
685 /**
686 * @brief Get root state of a trie
687 *
688 * @param trie : the trie
689 *
690 * @return the root state of the trie
691 *
692 * Get root state of @a trie, for stepwise walking.
693 *
694 * The returned state is allocated and must be freed with trie_state_free()
695 */
696 TrieState *
697 trie_root (const Trie *trie)
698 {
699 return trie_state_new (trie, da_get_root (trie->da), 0, FALSE);
700 }
701
702 /*----------------*
703 * TRIE STATE *
704 *----------------*/
705
706 static TrieState *
707 trie_state_new (const Trie *trie,
708 TrieIndex index,
709 short suffix_idx,
710 short is_suffix)
711 {
712 TrieState *s;
713
714 s = (TrieState *) malloc (sizeof (TrieState));
715 if (UNLIKELY (!s))
716 return NULL;
717
718 s->trie = trie;
719 s->index = index;
720 s->suffix_idx = suffix_idx;
721 s->is_suffix = is_suffix;
722
723 return s;
724 }
725
726 /**
727 * @brief Copy trie state to another
728 *
729 * @param dst : the destination state
730 * @param src : the source state
731 *
732 * Copy trie state data from @a src to @a dst. All existing data in @a dst
733 * is overwritten.
734 */
735 void
736 trie_state_copy (TrieState *dst, const TrieState *src)
737 {
738 /* May be deep copy if necessary, not the case for now */
739 *dst = *src;
740 }
741
742 /**
743 * @brief Clone a trie state
744 *
745 * @param s : the state to clone
746 *
747 * @return an duplicated instance of @a s
748 *
749 * Make a copy of trie state.
750 *
751 * The returned state is allocated and must be freed with trie_state_free()
752 */
753 TrieState *
754 trie_state_clone (const TrieState *s)
755 {
756 return trie_state_new (s->trie, s->index, s->suffix_idx, s->is_suffix);
757 }
758
759 /**
760 * @brief Free a trie state
761 *
762 * @param s : the state to free
763 *
764 * Free the trie state.
765 */
766 void
767 trie_state_free (TrieState *s)
768 {
769 free (s);
770 }
771
772 /**
773 * @brief Rewind a trie state
774 *
775 * @param s : the state to rewind
776 *
777 * Put the state at root.
778 */
779 void
780 trie_state_rewind (TrieState *s)
781 {
782 s->index = da_get_root (s->trie->da);
783 s->is_suffix = FALSE;
784 }
785
786 /**
787 * @brief Walk the trie from the state
788 *
789 * @param s : current state
790 * @param c : key character for walking
791 *
792 * @return boolean value indicating the success of the walk
793 *
794 * Walk the trie stepwise, using a given character @a c.
795 * On return, the state @a s is updated to the new state if successfully walked.
796 */
797 Bool
798 trie_state_walk (TrieState *s, AlphaChar c)
799 {
800 TrieIndex tc = alpha_map_char_to_trie (s->trie->alpha_map, c);
801 if (UNLIKELY (TRIE_INDEX_MAX == tc))
802 return FALSE;
803
804 if (!s->is_suffix) {
805 Bool ret;
806
807 ret = da_walk (s->trie->da, &s->index, (TrieChar) tc);
808
809 if (ret && trie_da_is_separate (s->trie->da, s->index)) {
810 s->index = trie_da_get_tail_index (s->trie->da, s->index);
811 s->suffix_idx = 0;
812 s->is_suffix = TRUE;
813 }
814
815 return ret;
816 } else {
817 return tail_walk_char (s->trie->tail, s->index, &s->suffix_idx,
818 (TrieChar) tc);
819 }
820 }
821
822 /**
823 * @brief Test walkability of character from state
824 *
825 * @param s : the state to check
826 * @param c : the input character
827 *
828 * @return boolean indicating walkability
829 *
830 * Test if there is a transition from state @a s with input character @a c.
831 */
832 Bool
833 trie_state_is_walkable (const TrieState *s, AlphaChar c)
834 {
835 TrieIndex tc = alpha_map_char_to_trie (s->trie->alpha_map, c);
836 if (UNLIKELY (TRIE_INDEX_MAX == tc))
837 return FALSE;
838
839 if (!s->is_suffix)
840 return da_is_walkable (s->trie->da, s->index, (TrieChar) tc);
841 else
842 return tail_is_walkable_char (s->trie->tail, s->index, s->suffix_idx,
843 (TrieChar) tc);
844 }
845
846 /**
847 * @brief Get all walkable characters from state
848 *
849 * @param s : the state to get
850 * @param chars : the storage for the result
851 * @param chars_nelm : the size of @a chars[] in number of elements
852 *
853 * @return total walkable characters
854 *
855 * Get the list of all walkable characters from state @a s. At most
856 * @a chars_nelm walkable characters are stored in @a chars[] on return.
857 *
858 * The function returns the actual number of walkable characters from @a s.
859 * Note that this may not equal the number of characters stored in @a chars[]
860 * if @a chars_nelm is less than the actual number.
861 *
862 * Available since: 0.2.6
863 */
864 int
865 trie_state_walkable_chars (const TrieState *s,
866 AlphaChar chars[],
867 int chars_nelm)
868 {
869 int syms_num = 0;
870
871 if (!s->is_suffix) {
872 Symbols *syms = da_output_symbols (s->trie->da, s->index);
873 int i;
874
875 syms_num = symbols_num (syms);
876 for (i = 0; i < syms_num && i < chars_nelm; i++) {
877 TrieChar tc = symbols_get (syms, i);
878 chars[i] = alpha_map_trie_to_char (s->trie->alpha_map, tc);
879 }
880
881 symbols_free (syms);
882 } else {
883 const TrieChar *suffix = tail_get_suffix (s->trie->tail, s->index);
884 chars[0] = alpha_map_trie_to_char (s->trie->alpha_map,
885 suffix[s->suffix_idx]);
886 syms_num = 1;
887 }
888
889 return syms_num;
890 }
891
892 /**
893 * @brief Check for single path
894 *
895 * @param s : the state to check
896 *
897 * @return boolean value indicating whether it is in a single path
898 *
899 * Check if the given state is in a single path, that is, there is no other
900 * branch from it to leaf.
901 */
902 Bool
903 trie_state_is_single (const TrieState *s)
904 {
905 return s->is_suffix;
906 }
907
908 /**
909 * @brief Get data from terminal state
910 *
911 * @param s : a terminal state
912 *
913 * @return the data associated with the terminal state @a s,
914 * or TRIE_DATA_ERROR if @a s is not a terminal state
915 *
916 * Get value from a terminal state of trie. Getting value from a non-terminal
917 * state will result in TRIE_DATA_ERROR.
918 */
919 TrieData
920 trie_state_get_data (const TrieState *s)
921 {
922 if (!s) {
923 return TRIE_DATA_ERROR;
924 }
925
926 if (!s->is_suffix) {
927 TrieIndex index = s->index;
928
929 /* walk a terminal char to get the data from tail */
930 if (da_walk (s->trie->da, &index, TRIE_CHAR_TERM)) {
931 if (trie_da_is_separate (s->trie->da, index)) {
932 index = trie_da_get_tail_index (s->trie->da, index);
933 return tail_get_data (s->trie->tail, index);
934 }
935 }
936 } else {
937 if (tail_is_walkable_char (s->trie->tail, s->index, s->suffix_idx,
938 TRIE_CHAR_TERM))
939 {
940 return tail_get_data (s->trie->tail, s->index);
941 }
942 }
943
944 return TRIE_DATA_ERROR;
945 }
946
947
948 /*---------------------*
949 * ENTRY ITERATION *
950 *---------------------*/
951
952 /**
953 * @brief Create a new trie iterator
954 *
955 * @param s : the TrieState to start iteration from
956 *
957 * @return a pointer to the newly created TrieIterator, or NULL on failure
958 *
959 * Create a new trie iterator for iterating entries of a sub-trie rooted at
960 * state @a s.
961 *
962 * Use it with the result of trie_root() to iterate the whole trie.
963 *
964 * The created object must be freed with trie_iterator_free().
965 *
966 * Available since: 0.2.6
967 */
968 TrieIterator *
969 trie_iterator_new (TrieState *s)
970 {
971 TrieIterator *iter;
972
973 iter = (TrieIterator *) malloc (sizeof (TrieIterator));
974 if (UNLIKELY (!iter))
975 return NULL;
976
977 iter->root = s;
978 iter->state = NULL;
979 iter->key = NULL;
980
981 return iter;
982 }
983
984 /**
985 * @brief Free a trie iterator
986 *
987 * @param iter : the trie iterator to free
988 *
989 * Destruct the iterator @a iter and free its allocated memory.
990 *
991 * Available since: 0.2.6
992 */
993 void
994 trie_iterator_free (TrieIterator *iter)
995 {
996 if (iter->state) {
997 trie_state_free (iter->state);
998 }
999 if (iter->key) {
1000 trie_string_free (iter->key);
1001 }
1002 free (iter);
1003 }
1004
1005 /**
1006 * @brief Move trie iterator to the next entry
1007 *
1008 * @param iter : an iterator
1009 *
1010 * @return boolean value indicating the availability of the entry
1011 *
1012 * Move trie iterator to the next entry.
1013 * On return, the iterator @a iter is updated to reference to the new entry
1014 * if successfully moved.
1015 *
1016 * Available since: 0.2.6
1017 */
1018 Bool
1019 trie_iterator_next (TrieIterator *iter)
1020 {
1021 TrieState *s = iter->state;
1022 TrieIndex sep;
1023
1024 /* first iteration */
1025 if (!s) {
1026 s = iter->state = trie_state_clone (iter->root);
1027
1028 /* for tail state, we are already at the only entry */
1029 if (s->is_suffix)
1030 return TRUE;
1031
1032 iter->key = trie_string_new (20);
1033 sep = da_first_separate (s->trie->da, s->index, iter->key);
1034 if (TRIE_INDEX_ERROR == sep)
1035 return FALSE;
1036
1037 s->index = sep;
1038 return TRUE;
1039 }
1040
1041 /* no next entry for tail state */
1042 if (s->is_suffix)
1043 return FALSE;
1044
1045 /* iter->state is a separate node */
1046 sep = da_next_separate (s->trie->da, iter->root->index, s->index,
1047 iter->key);
1048 if (TRIE_INDEX_ERROR == sep)
1049 return FALSE;
1050
1051 s->index = sep;
1052 return TRUE;
1053 }
1054
1055 /**
1056 * @brief Get key for a trie iterator
1057 *
1058 * @param iter : an iterator
1059 *
1060 * @return the allocated key string; NULL on failure
1061 *
1062 * Get key for the current entry referenced by the trie iterator @a iter.
1063 *
1064 * The return string must be freed with free().
1065 *
1066 * Available since: 0.2.6
1067 */
1068 AlphaChar *
1069 trie_iterator_get_key (const TrieIterator *iter)
1070 {
1071 const TrieState *s;
1072 const TrieChar *tail_str;
1073 AlphaChar *alpha_key, *alpha_p;
1074
1075 s = iter->state;
1076 if (!s)
1077 return NULL;
1078
1079 /* if s is in tail, root == s */
1080 if (s->is_suffix) {
1081 tail_str = tail_get_suffix (s->trie->tail, s->index);
1082 if (!tail_str)
1083 return NULL;
1084
1085 tail_str += s->suffix_idx;
1086
1087 alpha_key = (AlphaChar *) malloc (sizeof (AlphaChar)
1088 * (trie_char_strlen (tail_str) + 1));
1089 if (UNLIKELY (!alpha_key))
1090 return NULL;
1091 alpha_p = alpha_key;
1092 } else {
1093 TrieIndex tail_idx;
1094 int i, key_len;
1095 const TrieChar *key_p;
1096
1097 tail_idx = trie_da_get_tail_index (s->trie->da, s->index);
1098 tail_str = tail_get_suffix (s->trie->tail, tail_idx);
1099 if (!tail_str)
1100 return NULL;
1101
1102 key_len = trie_string_length (iter->key);
1103 key_p = trie_string_get_val (iter->key);
1104 alpha_key = (AlphaChar *) malloc (
1105 sizeof (AlphaChar)
1106 * (key_len + trie_char_strlen (tail_str) + 1)
1107 );
1108 if (UNLIKELY (!alpha_key))
1109 return NULL;
1110 alpha_p = alpha_key;
1111 for (i = key_len; i > 0; i--) {
1112 *alpha_p++ = alpha_map_trie_to_char (s->trie->alpha_map, *key_p++);
1113 }
1114 }
1115
1116 while (TRIE_CHAR_TERM != *tail_str) {
1117 *alpha_p++ = alpha_map_trie_to_char (s->trie->alpha_map, *tail_str++);
1118 }
1119 *alpha_p = 0;
1120
1121 return alpha_key;
1122 }
1123
1124 /**
1125 * @brief Get data for the entry referenced by an iterator
1126 *
1127 * @param iter : an iterator
1128 *
1129 * @return the data associated with the entry referenced by iterator @a iter,
1130 * or TRIE_DATA_ERROR if @a iter does not reference to a unique entry
1131 *
1132 * Get value for the entry referenced by an iterator. Getting value from an
1133 * un-iterated (or broken for any reason) iterator will result in
1134 * TRIE_DATA_ERROR.
1135 *
1136 * Available since: 0.2.6
1137 */
1138 TrieData
1139 trie_iterator_get_data (const TrieIterator *iter)
1140 {
1141 const TrieState *s = iter->state;
1142 TrieIndex tail_index;
1143
1144 if (!s)
1145 return TRIE_DATA_ERROR;
1146
1147 if (!s->is_suffix) {
1148 if (!trie_da_is_separate (s->trie->da, s->index))
1149 return TRIE_DATA_ERROR;
1150
1151 tail_index = trie_da_get_tail_index (s->trie->da, s->index);
1152 } else {
1153 tail_index = s->index;
1154 }
1155
1156 return tail_get_data (s->trie->tail, tail_index);
1157 }
1158
1159 /*
1160 vi:ts=4:ai:expandtab
1161 */