Trie data type and functions. More...

Macros
#define	trie_state_is_terminal(s) trie_state_is_walkable((s),TRIE_CHAR_TERM)
	Check for terminal state. More...

#define	trie_state_is_leaf(s) (trie_state_is_single(s) && trie_state_is_terminal(s))
	Check for leaf state. More...

Typedefs
typedef struct _Trie	Trie
	Trie data type.

typedef Bool(*	TrieEnumFunc )(const AlphaChar key, TrieData key_data, void user_data)
	Trie enumeration function. More...

typedef struct _TrieState	TrieState
	Trie walking state.

Functions
Trie *	trie_new (const AlphaMap *alpha_map)
	Create a new trie. More...

Trie *	trie_new_from_file (const char *path)
	Create a new trie by loading from a file. More...

void	trie_free (Trie *trie)
	Free a trie object. More...

int	trie_save (Trie trie, const char path)
	Save a trie to file. More...

Bool	trie_is_dirty (const Trie *trie)
	Check pending changes. More...

Bool	trie_retrieve (const Trie trie, const AlphaChar key, TrieData *o_data)
	Retrieve an entry from trie. More...

Bool	trie_store (Trie trie, const AlphaChar key, TrieData data)
	Store a value for an entry to trie. More...

Bool	trie_delete (Trie trie, const AlphaChar key)
	Delete an entry from trie. More...

Bool	trie_enumerate (const Trie trie, TrieEnumFunc enum_func, void user_data)
	Enumerate entries in trie. More...

TrieState *	trie_root (const Trie *trie)
	Get root state of a trie. More...

TrieState *	trie_state_clone (const TrieState *s)
	Clone a trie state. More...

void	trie_state_copy (TrieState dst, const TrieState src)
	Copy trie state to another. More...

void	trie_state_free (TrieState *s)
	Free a trie state. More...

void	trie_state_rewind (TrieState *s)
	Rewind a trie state. More...

Bool	trie_state_walk (TrieState *s, AlphaChar c)
	Walk the trie from the state. More...

Bool	trie_state_is_walkable (const TrieState *s, AlphaChar c)
	Test walkability of character from state. More...

Bool	trie_state_is_single (const TrieState *s)
	Check for single path. More...

TrieData	trie_state_get_data (const TrieState *s)
	Get data from leaf state. More...

Detailed Description

Trie data type and functions.

Macro Definition Documentation

#define trie_state_is_leaf ( s ) (trie_state_is_single(s) && trie_state_is_terminal(s))

Check for leaf state.

Parameters

s	: the state to check

Returns: boolean value indicating whether it is a leaf state

Check if the given state is a leaf state. A leaf state is a terminal state that has no other branch.

#define trie_state_is_terminal ( s ) trie_state_is_walkable((s),TRIE_CHAR_TERM)

Check for terminal state.

Parameters

s	: the state to check

Returns: boolean value indicating whether it is a terminal state

Check if the given state is a terminal state. A terminal state is a trie state that terminates a key, and stores a value associated with it.

Typedef Documentation

typedef Bool(* TrieEnumFunc)(const AlphaChar *key, TrieData key_data, void *user_data)

Trie enumeration function.

Parameters

key	: the key of the entry
data	: the data of the entry

Returns: TRUE to continue enumeration, FALSE to stop

Function Documentation

Bool trie_delete	(	Trie *	trie,
		const AlphaChar *	key
	)

Delete an entry from trie.

Parameters

trie	: the trie
key	: the key for the entry to delete

Returns: boolean value indicating whether the key exists and is removed

Delete an entry for the given key from trie.

Bool trie_enumerate	(	const Trie *	trie,
		TrieEnumFunc	enum_func,
		void *	user_data
	)

Enumerate entries in trie.

Parameters

trie	: the trie
enum_func	: the callback function to be called on each key
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 entries in trie. For each entry, the user-supplied enum_func callback function is called, with the entry key and data. Returning FALSE from such callback will stop enumeration and return FALSE.

void trie_free ( Trie * trie )

Free a trie object.

Parameters

trie	: the trie object to free

Destruct the trie and free its allocated memory.

Bool trie_is_dirty ( const Trie * trie )

Check pending changes.

Parameters

trie	: the trie object

Returns: TRUE if there are pending changes, FALSE otherwise

Check if the trie is dirty with some pending changes and needs saving to synchronize with the file.

Trie* trie_new ( const AlphaMap * alpha_map )

Create a new trie.

Parameters

alpha_map : the alphabet set for the trie

Returns: a pointer to the newly created trie, NULL on failure

Create a new empty trie object based on the given alpha_map alphabet set. The trie contents can then be added and deleted with trie_store() and trie_delete() respectively.

The created object must be freed with trie_free().

Trie* trie_new_from_file ( const char * path )

Create a new trie by loading from a file.

Parameters

path	: the path to the file

Returns: a pointer to the created trie, NULL on failure

Create a new trie and initialize its contents by loading from the file at given path.

The created object must be freed with trie_free().

Bool trie_retrieve	(	const Trie *	trie,
		const AlphaChar *	key,
		TrieData *	o_data
	)

Retrieve an entry from trie.

Parameters

trie	: the trie
key	: the key for the entry to retrieve
o_data	: the storage for storing the entry data on return

Returns: boolean value indicating the existence of the entry.

Retrieve an entry for the given key from trie. On return, if key is found and o_data is not NULL, *o_data is set to the data associated to key.

TrieState* trie_root ( const Trie * trie )

Get root state of a trie.

Parameters

trie	: the trie

Returns: the root state of the trie

Get root state of trie, for stepwise walking.

The returned state is allocated and must be freed with trie_state_free()

int trie_save	(	Trie *	trie,
		const char *	path
	)

Save a trie to file.

Parameters

trie	: the trie
path	: the path to the file

Returns: 0 on success, non-zero on failure

Create a new file at the given path and write trie data to it. If path already exists, its contents will be replaced.

TrieState* trie_state_clone ( const TrieState * s )

Clone a trie state.

Parameters

s	: the state to clone

Returns: an duplicated instance of s

Make a copy of trie state.

The returned state is allocated and must be freed with trie_state_free()

void trie_state_copy	(	TrieState *	dst,
		const TrieState *	src
	)

Copy trie state to another.

Parameters

dst	: the destination state
src	: the source state

Copy trie state data from src to dst. All existing data in dst is overwritten.

void trie_state_free ( TrieState * s )

Free a trie state.

Parameters

s	: the state to free

Free the trie state.

TrieData trie_state_get_data ( const TrieState * s )

Get data from leaf state.

Parameters

s	: a leaf state

Returns: the data associated with the leaf state s, or TRIE_DATA_ERROR if s is not a leaf state

Get value from a leaf state of trie. Getting value from a non-leaf state will result in TRIE_DATA_ERROR.

Bool trie_state_is_single ( const TrieState * s )

Check for single path.

Parameters

s	: the state to check

Returns: boolean value indicating whether it is in a single path

Check if the given state is in a single path, that is, there is no other branch from it to leaf.

Bool trie_state_is_walkable	(	const TrieState *	s,
		AlphaChar	c
	)

Test walkability of character from state.

Parameters

s	: the state to check
c	: the input character

Returns: boolean indicating walkability

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

void trie_state_rewind ( TrieState * s )

Rewind a trie state.

Parameters

s	: the state to rewind

Put the state at root.

Bool trie_state_walk	(	TrieState *	s,
		AlphaChar	c
	)

Walk the trie from the state.

Parameters

s	: current state
c	: key character for walking

Returns: boolean value indicating the success of the walk

Walk the trie stepwise, using a given character c. On return, the state s is updated to the new state if successfully walked.

Bool trie_store	(	Trie *	trie,
		const AlphaChar *	key,
		TrieData	data
	)

Store a value for an entry to trie.

Parameters

trie	: the trie
key	: the key for the entry to retrieve
data	: the data associated to the entry

Returns: boolean value indicating the success of the process

Store a data for the given key in trie. If key does not exist in trie, it will be appended. If it does, its current data will be overwritten.

Macros

Typedefs

Functions

Detailed Description

Macro Definition Documentation

Typedef Documentation

Function Documentation