libthai  0.1.20
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. More...
 

Typedefs

typedef struct _Symbols Symbols
 Symbol set structure type.
 
typedef struct _DArray DArray
 Double-array structure type.
 

Functions

DArrayda_new ()
 Create a new double-array object. More...
 
DArrayda_fread (FILE *file)
 Read double-array data from file. More...
 
void da_free (DArray *d)
 Free double-array data. More...
 
int da_fwrite (const DArray *d, FILE *file)
 Write double-array data. More...
 
TrieIndex da_get_root (const DArray *d)
 Get root state. More...
 
TrieIndex da_get_base (const DArray *d, TrieIndex s)
 Get BASE cell. More...
 
TrieIndex da_get_check (const DArray *d, TrieIndex s)
 Get CHECK cell. More...
 
void da_set_base (DArray *d, TrieIndex s, TrieIndex val)
 Set BASE cell. More...
 
void da_set_check (DArray *d, TrieIndex s, TrieIndex val)
 Set CHECK cell. More...
 
Bool da_walk (const DArray *d, TrieIndex *s, TrieChar c)
 Walk in double-array structure. More...
 
TrieIndex da_insert_branch (DArray *d, TrieIndex s, TrieChar c)
 Insert a branch from trie node. More...
 
void da_prune (DArray *d, TrieIndex s)
 Prune the single branch. More...
 
void da_prune_upto (DArray *d, TrieIndex p, TrieIndex s)
 Prune the single branch up to given parent. More...
 
TrieIndex da_first_separate (DArray *d, TrieIndex root, TrieString *keybuff)
 Find first separate node in a sub-trie. More...
 
TrieIndex da_next_separate (DArray *d, TrieIndex root, TrieIndex sep, TrieString *keybuff)
 Find next separate node in a sub-trie. More...
 

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.

Function Documentation

TrieIndex da_first_separate ( DArray d,
TrieIndex  root,
TrieString *  keybuff 
)

Find first separate node in a sub-trie.

Parameters
d: the double-array structure
root: the sub-trie root to search from
keybuff: the TrieString buffer for incrementally calcuating key
Returns
index to the first separate node; TRIE_INDEX_ERROR on any failure

Find the first separate node under a sub-trie rooted at root.

On return, keybuff is appended with the key characters which walk from root to the separate node. This is for incrementally calculating the transition key, which is more efficient than later totally reconstructing key from the given separate node.

Available since: 0.2.6

DArray* da_fread ( 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_free ( DArray d)

Free double-array data.

Parameters
d: the double-array data

Free the given double-array data.

int da_fwrite ( 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.

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.

TrieIndex da_next_separate ( DArray d,
TrieIndex  root,
TrieIndex  sep,
TrieString *  keybuff 
)

Find next separate node in a sub-trie.

Parameters
d: the double-array structure
root: the sub-trie root to search from
sep: the current separate node
keybuff: the TrieString buffer for incrementally calcuating key
Returns
index to the next separate node; TRIE_INDEX_ERROR if no more separate node is found

Find the next separate node under a sub-trie rooted at root starting from the current separate node sep.

On return, keybuff is incrementally updated from the key which walks to previous separate node to the one which walks to the new separate node. So, it is assumed to be initialized by at least one da_first_separate() call before. This incremental key calculation is more efficient than later totally reconstructing key from the given separate node.

Available since: 0.2.6

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.

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.


Generated for libthai by doxygen 1.8.6