libthai  0.1.14
Macros | Typedefs | Functions
darray.h File Reference

Double-array trie structure. More...

Macros

#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

DArrayda_new ()
 Create a new double-array object.
DArrayda_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.

Detailed Description

Double-array trie structure.


Macro Definition Documentation

#define da_is_walkable (   d,
  s,
 
)    (da_get_check ((d), da_get_base ((d), (s)) + (c)) == (s))

Test walkability in double-array structure.

Parameters:
d: the double-array structure
s: current state
c: the input character
Returns:
boolean indicating walkability

Test if there is a transition from state s with input character c.


Typedef Documentation

typedef Bool(* DAEnumFunc)(const TrieChar *key, TrieIndex sep_node, void *user_data)

Double-array entry enumeration function.

Parameters:
key: the key of the entry, up to sep_node
sep_node: the separate node of the entry
user_data: user-supplied data
Returns:
TRUE to continue enumeration, FALSE to stop

Function Documentation

Bool da_enumerate ( const DArray d,
DAEnumFunc  enum_func,
void *  user_data 
)

Enumerate entries stored in double-array structure.

Parameters:
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
Returns:
boolean value indicating whether all the keys are visited

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.

Parameters:
d: the double-array data

Free the given double-array data.

TrieIndex da_get_base ( const DArray d,
TrieIndex  s 
)

Get BASE cell.

Parameters:
d: the double-array data
s: the double-array state to get data
Returns:
the BASE cell value for the given state

Get BASE cell value for the given state.

TrieIndex da_get_check ( const DArray d,
TrieIndex  s 
)

Get CHECK cell.

Parameters:
d: the double-array data
s: the double-array state to get data
Returns:
the CHECK cell value for the given state

Get CHECK cell value for the given state.

TrieIndex da_get_root ( const DArray d)

Get root state.

Parameters:
d: the double-array data
Returns:
root state of the index set, or TRIE_INDEX_ERROR on failure

Get root state for stepwise walking.

TrieIndex da_insert_branch ( DArray d,
TrieIndex  s,
TrieChar  c 
)

Insert a branch from trie node.

Parameters:
d: the double-array structure
s: the state to add branch to
c: the character for the branch label
Returns:
the index of the new node

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.

void da_prune ( DArray d,
TrieIndex  s 
)

Prune the single branch.

Parameters:
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.

void da_prune_upto ( DArray d,
TrieIndex  p,
TrieIndex  s 
)

Prune the single branch up to given parent.

Parameters:
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.

Parameters:
file: the file to read
Returns:
a pointer to the openned double-array, NULL on failure

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.

void da_set_base ( DArray d,
TrieIndex  s,
TrieIndex  val 
)

Set BASE cell.

Parameters:
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.

void da_set_check ( DArray d,
TrieIndex  s,
TrieIndex  val 
)

Set CHECK cell.

Parameters:
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.

Bool da_walk ( const DArray d,
TrieIndex s,
TrieChar  c 
)

Walk in double-array structure.

Parameters:
d: the double-array structure
s: current state
c: the input character
Returns:
boolean indicating success

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.

Parameters:
d: the double-array data
file: the file to write to
Returns:
0 on success, non-zero on failure

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.


Generated for libthai by doxygen 1.8.1.1