datrie/darray.h File Reference

---

Detailed Description

Double-array trie structure.

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 _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_open (const char *path, const char *name, TrieIOMode mode)
	Open double-array from file.
int	da_close (DArray *d)
	Close double-array data.
int	da_save (DArray *d)
	Save 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 (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.
Bool	da_enumerate (DArray *d, DAEnumFunc enum_func, void *user_data)
	Enumerate entries stored in double-array structure.

---

Define Documentation

#define da_is_walkable	(	d,
		s,
		c		)	(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

int da_close

(

DArray *

d

)

Close double-array data.

Parameters:

d

: the double-array data

Returns:

0 on success, non-zero on failure

Close the given double-array data. If d was openned for writing, all pending changes will be saved to file.

Bool da_enumerate	(	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.

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_open	(	const char *	path,
		const char *	name,
		TrieIOMode	mode
	)

Open double-array from file.

Parameters:

	path	: the path that stores the double-array files
	name	: the name of the double-array (not actual file name)
	mode	: openning mode, read or write

Returns:

a pointer to the openned double-array, NULL on failure

Open a double-array structure of given name. Note that name here does not mean the actual file name. Rather, the file name will be inferred by the name.

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.

int da_save

(

DArray *

d

)

Save double-array data.

Parameters:

d

: the double-array data

Returns:

0 on success, non-zero on failure

If double-array data was openned for writing, save all pending changes to file.

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

---