datrie/trie.h File Reference

---

Detailed Description

Trie data type and functions.

Defines
#define	trie_state_is_terminal(s)   trie_state_is_walkable((s),TRIE_CHAR_TERM)
	Check for terminal state.
Typedefs
typedef _Trie	Trie
	Trie data type.
typedef Bool(*)	TrieEnumFunc (const TrieChar *key, TrieData key_data, void *user_data)
	Trie enumeration function.
typedef _TrieState	TrieState
	Trie walking state.
Functions
Trie *	trie_open (const char *path, const char *name, TrieIOMode mode)
	Open a trie.
int	trie_close (Trie *trie)
	Close a trie.
int	trie_save (Trie *trie)
	Save a trie.
Bool	trie_retrieve (Trie *trie, const TrieChar *key, TrieData *o_data)
	Retrieve an entry from trie.
Bool	trie_store (Trie *trie, const TrieChar *key, TrieData data)
	Store a value for an entry to trie.
Bool	trie_delete (Trie *trie, const TrieChar *key)
	Delete an entry from trie.
Bool	trie_enumerate (Trie *trie, TrieEnumFunc enum_func, void *user_data)
	Enumerate entries in trie.
TrieState *	trie_root (Trie *trie)
	Get root state of a trie.
TrieState *	trie_state_clone (const TrieState *s)
	Clone a trie state.
void	trie_state_free (TrieState *s)
	Free a trie state.
void	trie_state_rewind (TrieState *s)
	Rewind a trie state.
Bool	trie_state_walk (TrieState *s, TrieChar c)
	Walk the trie from the state.
Bool	trie_state_is_walkable (const TrieState *s, TrieChar c)
	Test walkability of character from state.
Bool	trie_state_is_leaf (const TrieState *s)
	Check for leaf state.
TrieData	trie_state_get_data (const TrieState *s)
	Get data from leaf state.

---

Define Documentation

#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 leaf state is a trie state that terminates a key, and stores a value associated with the key.

---

Typedef Documentation

typedef Bool(*) TrieEnumFunc(const TrieChar *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

int trie_close

(

Trie *

trie

)

Close a trie.

Parameters:

trie,:

the trie

Returns:

0 on success, non-zero on failure

Close the given trie. If trie was openned for writing, all pending changes will be saved to file.

Bool trie_delete	(	Trie *	trie,
		const TrieChar *	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	(	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.

Trie* trie_open	(	const char *	path,
		const char *	name,
		TrieIOMode	mode
	)

Open a trie.

Parameters:

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

Returns:

a pointer to the openned trie, NULL on failure

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

Bool trie_retrieve	(	Trie *	trie,
		const TrieChar *	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_val is not NULL, *o_val is set to the data associated to key.

TrieState* trie_root

(

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

)

Save a trie.

Parameters:

trie,:

the trie

Returns:

0 on success, non-zero on failure

If trie was openned for writing, save all pending data to file.

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_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

: the 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 the value from leaf state will result in TRIE_DATA_ERROR.

Bool trie_state_is_leaf

(

const TrieState *

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.

Bool trie_state_is_walkable	(	const TrieState *	s,
		TrieChar	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,
		TrieChar	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 TrieChar *	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 data for the given key in trie. If key does not exist in trie, it will be appended.

---