« back to all changes in this revision
Viewing changes to datrie/darray.h
- browse files at revision 7
- compare with another revision
- download diff
- download tarball
- view history from revision 7
- Committer: Bazaar Package Importer
- Author(s): Theppitak Karoonboonyanan
- Date: 2010-02-27 21:09:46 UTC
- mfrom: (1.2.2 upstream)
- Revision ID: james.westby@ubuntu.com-20100227210946-dayt6gm3m20meucz
* New upstream release.
* Bump Standards-Version to 3.8.4 (no changes needed)
* Bump Standards-Version to 3.8.4 (no changes needed)
- files modified:
- ChangeLog
added
removed
datrie/darray.h
1
1
/* -*- Mode: C; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
2
2
/*
3
* libdatrie - Double-Array Trie Library
4
* Copyright (C) 2006 Theppitak Karoonboonyanan <thep@linux.thai.net>
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
/*
3
22
* darray.h - Double-array trie structure
4
23
* Created: 2006-08-11
5
24
* Author: Theppitak Karoonboonyanan <thep@linux.thai.net>
34
53
void *user_data);
35
54
36
55
37
/**
38
* @brief Create a new double-array object
39
*
40
* Create a new empty doubla-array object.
41
*/
42
56
DArray * da_new ();
43
57
44
/**
45
* @brief Read double-array data from file
46
*
47
* @param file : the file to read
48
*
49
* @return a pointer to the openned double-array, NULL on failure
50
*
51
* Read double-array data from the opened file, starting from the current
52
* file pointer until the end of double array data block. On return, the
53
* file pointer is left at the position after the read block.
54
*/
55
58
DArray * da_read (FILE *file);
56
59
57
/**
58
* @brief Free double-array data
59
*
60
* @param d : the double-array data
61
*
62
* Free the given double-array data.
63
*/
64
60
void da_free (DArray *d);
65
61
66
/**
67
* @brief Write double-array data
68
*
69
* @param d : the double-array data
70
* @param file : the file to write to
71
*
72
* @return 0 on success, non-zero on failure
73
*
74
* Write double-array data to the given @a file, starting from the current
75
* file pointer. On return, the file pointer is left after the double-array
76
* data block.
77
*/
78
62
int da_write (const DArray *d, FILE *file);
79
63
80
64
81
/**
82
* @brief Get root state
83
*
84
* @param d : the double-array data
85
*
86
* @return root state of the @a index set, or TRIE_INDEX_ERROR on failure
87
*
88
* Get root state for stepwise walking.
89
*/
90
65
TrieIndex da_get_root (const DArray *d);
91
66
92
67
93
/**
94
* @brief Get BASE cell
95
*
96
* @param d : the double-array data
97
* @param s : the double-array state to get data
98
*
99
* @return the BASE cell value for the given state
100
*
101
* Get BASE cell value for the given state.
102
*/
103
68
TrieIndex da_get_base (const DArray *d, TrieIndex s);
104
69
105
/**
106
* @brief Get CHECK cell
107
*
108
* @param d : the double-array data
109
* @param s : the double-array state to get data
110
*
111
* @return the CHECK cell value for the given state
112
*
113
* Get CHECK cell value for the given state.
114
*/
115
70
TrieIndex da_get_check (const DArray *d, TrieIndex s);
116
71
117
72
118
/**
119
* @brief Set BASE cell
120
*
121
* @param d : the double-array data
122
* @param s : the double-array state to get data
123
* @param val : the value to set
124
*
125
* Set BASE cell for the given state to the given value.
126
*/
127
73
void da_set_base (DArray *d, TrieIndex s, TrieIndex val);
128
74
129
/**
130
* @brief Set CHECK cell
131
*
132
* @param d : the double-array data
133
* @param s : the double-array state to get data
134
* @param val : the value to set
135
*
136
* Set CHECK cell for the given state to the given value.
137
*/
138
75
void da_set_check (DArray *d, TrieIndex s, TrieIndex val);
139
76
140
/**
141
* @brief Walk in double-array structure
142
*
143
* @param d : the double-array structure
144
* @param s : current state
145
* @param c : the input character
146
*
147
* @return boolean indicating success
148
*
149
* Walk the double-array trie from state @a *s, using input character @a c.
150
* If there exists an edge from @a *s with arc labeled @a c, this function
151
* returns TRUE and @a *s is updated to the new state. Otherwise, it returns
152
* FALSE and @a *s is left unchanged.
153
*/
154
77
Bool da_walk (const DArray *d, TrieIndex *s, TrieChar c);
155
78
156
79
/**
170
93
#define da_is_walkable(d,s,c) \
171
94
(da_get_check ((d), da_get_base ((d), (s)) + (c)) == (s))
172
95
173
/**
174
* @brief Insert a branch from trie node
175
*
176
* @param d : the double-array structure
177
* @param s : the state to add branch to
178
* @param c : the character for the branch label
179
*
180
* @return the index of the new node
181
*
182
* Insert a new arc labelled with character @a c from the trie node
183
* represented by index @a s in double-array structure @a d.
184
* Note that it assumes that no such arc exists before inserting.
185
*/
186
96
TrieIndex da_insert_branch (DArray *d, TrieIndex s, TrieChar c);
187
97
188
/**
189
* @brief Prune the single branch
190
*
191
* @param d : the double-array structure
192
* @param s : the dangling state to prune off
193
*
194
* Prune off a non-separate path up from the final state @a s.
195
* If @a s still has some children states, it does nothing. Otherwise,
196
* it deletes the node and all its parents which become non-separate.
197
*/
198
98
void da_prune (DArray *d, TrieIndex s);
199
99
200
/**
201
* @brief Prune the single branch up to given parent
202
*
203
* @param d : the double-array structure
204
* @param p : the parent up to which to be pruned
205
* @param s : the dangling state to prune off
206
*
207
* Prune off a non-separate path up from the final state @a s to the
208
* given parent @a p. The prunning stop when either the parent @a p
209
* is met, or a first non-separate node is found.
210
*/
211
100
void da_prune_upto (DArray *d, TrieIndex p, TrieIndex s);
212
101
213
/**
214
* @brief Enumerate entries stored in double-array structure
215
*
216
* @param d : the double-array structure
217
* @param enum_func : the callback function to be called on each separate node
218
* @param user_data : user-supplied data to send as an argument to @a enum_func
219
*
220
* @return boolean value indicating whether all the keys are visited
221
*
222
* Enumerate all keys stored in double-array structure. For each entry, the
223
* user-supplied @a enum_func callback function is called, with the entry key,
224
* the separate node, and user-supplied data. Returning FALSE from such
225
* callback will stop enumeration and return FALSE.
226
*/
227
102
Bool da_enumerate (const DArray *d, DAEnumFunc enum_func, void *user_data);
228
103
229
104
#endif /* __DARRAY_H */
Loggerhead is a web-based interface for Breezy
Version: 2.0.1