Double-array trie structure. More...
Defines | |
#define | da_is_walkable(d, s, c) (da_get_check ((d), da_get_base ((d), (s)) + (c)) == (s)) |
Test walkability in double-array structure. | |
Typedefs | |
typedef struct _DArray | DArray |
Double-array structure type. | |
typedef Bool(* | DAEnumFunc )(const TrieChar *key, TrieIndex sep_node, void *user_data) |
Double-array entry enumeration function. | |
Functions | |
DArray * | da_new () |
Create a new double-array object. | |
DArray * | da_read (FILE *file) |
Read double-array data from file. | |
void | da_free (DArray *d) |
Free double-array data. | |
int | da_write (const DArray *d, FILE *file) |
Write double-array data. | |
TrieIndex | da_get_root (const DArray *d) |
Get root state. | |
TrieIndex | da_get_base (const DArray *d, TrieIndex s) |
Get BASE cell. | |
TrieIndex | da_get_check (const DArray *d, TrieIndex s) |
Get CHECK cell. | |
void | da_set_base (DArray *d, TrieIndex s, TrieIndex val) |
Set BASE cell. | |
void | da_set_check (DArray *d, TrieIndex s, TrieIndex val) |
Set CHECK cell. | |
Bool | da_walk (const DArray *d, TrieIndex *s, TrieChar c) |
Walk in double-array structure. | |
TrieIndex | da_insert_branch (DArray *d, TrieIndex s, TrieChar c) |
Insert a branch from trie node. | |
void | da_prune (DArray *d, TrieIndex s) |
Prune the single branch. | |
void | da_prune_upto (DArray *d, TrieIndex p, TrieIndex s) |
Prune the single branch up to given parent. | |
Bool | da_enumerate (const DArray *d, DAEnumFunc enum_func, void *user_data) |
Enumerate entries stored in double-array structure. |
Double-array trie structure.
#define da_is_walkable | ( | d, | |||
s, | |||||
c | ) | (da_get_check ((d), da_get_base ((d), (s)) + (c)) == (s)) |
Test walkability in double-array structure.
d | : the double-array structure | |
s | : current state | |
c | : the input character |
Test if there is a transition from state s with input character c.
typedef Bool(* DAEnumFunc)(const TrieChar *key, TrieIndex sep_node, void *user_data) |
Double-array entry enumeration function.
key | : the key of the entry, up to sep_node | |
sep_node | : the separate node of the entry | |
user_data | : user-supplied data |
Bool da_enumerate | ( | const DArray * | d, | |
DAEnumFunc | enum_func, | |||
void * | user_data | |||
) |
Enumerate entries stored in double-array structure.
d | : the double-array structure | |
enum_func | : the callback function to be called on each separate node | |
user_data | : user-supplied data to send as an argument to enum_func |
Enumerate all keys stored in double-array structure. For each entry, the user-supplied enum_func callback function is called, with the entry key, the separate node, and user-supplied data. Returning FALSE from such callback will stop enumeration and return FALSE.
void da_free | ( | DArray * | d | ) |
Free double-array data.
d | : the double-array data |
Free the given double-array data.
Get BASE cell.
d | : the double-array data | |
s | : the double-array state to get data |
Get BASE cell value for the given state.
Get CHECK cell.
d | : the double-array data | |
s | : the double-array state to get data |
Get CHECK cell value for the given state.
Get root state.
d | : the double-array data |
Get root state for stepwise walking.
Insert a branch from trie node.
d | : the double-array structure | |
s | : the state to add branch to | |
c | : the character for the branch label |
Insert a new arc labelled with character c from the trie node represented by index s in double-array structure d. Note that it assumes that no such arc exists before inserting.
DArray* da_new | ( | ) |
Create a new double-array object.
Create a new empty doubla-array object.
Prune the single branch.
d | : the double-array structure | |
s | : the dangling state to prune off |
Prune off a non-separate path up from the final state s. If s still has some children states, it does nothing. Otherwise, it deletes the node and all its parents which become non-separate.
Prune the single branch up to given parent.
d | : the double-array structure | |
p | : the parent up to which to be pruned | |
s | : the dangling state to prune off |
Prune off a non-separate path up from the final state s to the given parent p. The prunning stop when either the parent p is met, or a first non-separate node is found.
DArray* da_read | ( | FILE * | file | ) |
Read double-array data from file.
file | : the file to read |
Read double-array data from the opened file, starting from the current file pointer until the end of double array data block. On return, the file pointer is left at the position after the read block.
Set BASE cell.
d | : the double-array data | |
s | : the double-array state to get data | |
val | : the value to set |
Set BASE cell for the given state to the given value.
Set CHECK cell.
d | : the double-array data | |
s | : the double-array state to get data | |
val | : the value to set |
Set CHECK cell for the given state to the given value.
Walk in double-array structure.
d | : the double-array structure | |
s | : current state | |
c | : the input character |
Walk the double-array trie from state *s, using input character c. If there exists an edge from *s with arc labeled c, this function returns TRUE and *s is updated to the new state. Otherwise, it returns FALSE and *s is left unchanged.
int da_write | ( | const DArray * | d, | |
FILE * | file | |||
) |
Write double-array data.
d | : the double-array data | |
file | : the file to write to |
Write double-array data to the given file, starting from the current file pointer. On return, the file pointer is left after the double-array data block.