Debian Codegraph @

datrie/trie.h

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.h - Trie data type and functions
23 * Created: 2006-08-11
24 * Author: Theppitak Karoonboonyanan <[email protected]>
25 */
26
27 #ifndef __TRIE_H
28 #define __TRIE_H
29
30 #include <datrie/triedefs.h>
31 #include <datrie/alpha-map.h>
32
33 #ifdef __cplusplus
34 extern "C" {
35 #endif
36
37 /**
38 * @file trie.h
39 * @brief Trie data type and functions
40 *
41 * Trie is a kind of digital search tree, an efficient indexing method with
42 * O(1) time complexity for searching. Comparably as efficient as hashing,
43 * trie also provides flexibility on incremental matching and key spelling
44 * manipulation. This makes it ideal for lexical analyzers, as well as
45 * spelling dictionaries.
46 *
47 * This library is an implementation of double-array structure for representing
48 * trie, as proposed by Junichi Aoe. The details of the implementation can be
49 * found at http://linux.thai.net/~thep/datrie/datrie.html
50 *
51 * A Trie is associated with an AlphaMap, a map between actual alphabet
52 * characters and the raw characters used to walk through trie.
53 * You can define the alphabet set by adding ranges of character codes
54 * to it before associating it to a trie. And the keys to be added to the trie
55 * must comprise only characters in such ranges. Note that the size of the
56 * alphabet set is limited to 256 (TRIE_CHAR_MAX + 1), and the AlphaMap
57 * will map the alphabet characters to raw codes in the range 0..255
58 * (0..TRIE_CHAR_MAX). The alphabet character ranges need not be continuous,
59 * but the mapped raw codes will be continuous, for the sake of compactness
60 * of the trie.
61 *
62 * A new Trie can be created in memory using trie_new(), saved to file using
63 * trie_save(), and loaded later with trie_new_from_file().
64 * It can even be embeded in another file using trie_fwrite() and read back
65 * using trie_fread().
66 * After use, Trie objects must be freed using trie_free().
67 *
68 * Operations on trie include:
69 *
70 * - Add/delete entries with trie_store() and trie_delete()
71 * - Retrieve entries with trie_retrieve()
72 * - Walk through trie stepwise with TrieState and its functions
73 * (trie_root(), trie_state_walk(), trie_state_rewind(),
74 * trie_state_clone(), trie_state_copy(),
75 * trie_state_is_walkable(), trie_state_walkable_chars(),
76 * trie_state_is_single(), trie_state_get_data().
77 * And do not forget to free TrieState objects with trie_state_free()
78 * after use.)
79 * - Enumerate all keys using trie_enumerate()
80 * - Iterate entries using TrieIterator and its functions
81 * (trie_iterator_new(), trie_iterator_next(), trie_iterator_get_key(),
82 * trie_iterator_get_data().
83 * And do not forget to free TrieIterator objects with trie_iterator_free()
84 * after use.)
85 */
86
87 /**
88 * @brief Trie data type
89 */
90 typedef struct _Trie Trie;
91
92 /**
93 * @brief Trie enumeration function
94 *
95 * @param key : the key of the entry
96 * @param key_data : the data of the entry
97 * @param user_data : the user-supplied data on enumerate call
98 *
99 * @return TRUE to continue enumeration, FALSE to stop
100 */
101 typedef Bool (*TrieEnumFunc) (const AlphaChar *key,
102 TrieData key_data,
103 void *user_data);
104
105 /**
106 * @brief Trie walking state
107 */
108 typedef struct _TrieState TrieState;
109
110
111 /**
112 * @brief Trie iteration state
113 */
114 typedef struct _TrieIterator TrieIterator;
115
116 /*-----------------------*
117 * GENERAL FUNCTIONS *
118 *-----------------------*/
119
120 Trie * trie_new (const AlphaMap *alpha_map);
121
122 Trie * trie_new_from_file (const char *path);
123
124 Trie * trie_fread (FILE *file);
125
126 void trie_free (Trie *trie);
127
128 size_t trie_get_serialized_size (Trie *trie);
129
130 void trie_serialize (Trie *trie, uint8 *ptr);
131
132 int trie_save (Trie *trie, const char *path);
133
134 int trie_fwrite (Trie *trie, FILE *file);
135
136 Bool trie_is_dirty (const Trie *trie);
137
138
139 /*------------------------------*
140 * GENERAL QUERY OPERATIONS *
141 *------------------------------*/
142
143 Bool trie_retrieve (const Trie *trie,
144 const AlphaChar *key,
145 TrieData *o_data);
146
147 Bool trie_store (Trie *trie, const AlphaChar *key, TrieData data);
148
149 Bool trie_store_if_absent (Trie *trie, const AlphaChar *key, TrieData data);
150
151 Bool trie_delete (Trie *trie, const AlphaChar *key);
152
153 Bool trie_enumerate (const Trie *trie,
154 TrieEnumFunc enum_func,
155 void *user_data);
156
157
158 /*-------------------------------*
159 * STEPWISE QUERY OPERATIONS *
160 *-------------------------------*/
161
162 TrieState * trie_root (const Trie *trie);
163
164
165 /*----------------*
166 * TRIE STATE *
167 *----------------*/
168
169 TrieState * trie_state_clone (const TrieState *s);
170
171 void trie_state_copy (TrieState *dst, const TrieState *src);
172
173 void trie_state_free (TrieState *s);
174
175 void trie_state_rewind (TrieState *s);
176
177 Bool trie_state_walk (TrieState *s, AlphaChar c);
178
179 Bool trie_state_is_walkable (const TrieState *s, AlphaChar c);
180
181 int trie_state_walkable_chars (const TrieState *s,
182 AlphaChar chars[],
183 int chars_nelm);
184
185 /**
186 * @brief Check for terminal state
187 *
188 * @param s : the state to check
189 *
190 * @return boolean value indicating whether it is a terminal state
191 *
192 * Check if the given state is a terminal state. A terminal state is a trie
193 * state that terminates a key, and stores a value associated with it.
194 */
195 #define trie_state_is_terminal(s) trie_state_is_walkable((s),0)
196
197 Bool trie_state_is_single (const TrieState *s);
198
199 /**
200 * @brief Check for leaf state
201 *
202 * @param s : the state to check
203 *
204 * @return boolean value indicating whether it is a leaf state
205 *
206 * Check if the given state is a leaf state. A leaf state is a terminal state
207 * that has no other branch.
208 */
209 #define trie_state_is_leaf(s) \
210 (trie_state_is_single(s) && trie_state_is_terminal(s))
211
212 TrieData trie_state_get_data (const TrieState *s);
213
214
215 /*----------------------*
216 * ENTRY ITERATION *
217 *----------------------*/
218
219 TrieIterator * trie_iterator_new (TrieState *s);
220
221 void trie_iterator_free (TrieIterator *iter);
222
223 Bool trie_iterator_next (TrieIterator *iter);
224
225 AlphaChar * trie_iterator_get_key (const TrieIterator *iter);
226
227 TrieData trie_iterator_get_data (const TrieIterator *iter);
228
229
230 #ifdef __cplusplus
231 }
232 #endif
233
234 #endif /* __TRIE_H */
235
236 /*
237 vi:ts=4:ai:expandtab
238 */