prefix tree More...

#include "cgul_common.h"
#include "cgul_exception.h"
#include "cgul_trie_node.h"

Include dependency graph for cgul_trie.h:

This graph shows which files directly or indirectly include this file:

Typedefs
typedef typedefCGUL_BEGIN_C struct cgul_trie *	cgul_trie_t

typedef int(*	cgul_trie__fold_key_t) (cgul_exception_t cex, const char key, void *data)

typedef int(*	cgul_trie__fold_value_t) (cgul_exception_t cex, void value, void *data)

typedef int(*	cgul_trie__fold_pair_t) (cgul_exception_t cex, const char key, void value, void data)

typedef int(*	cgul_trie__traverse_t) (cgul_exception_t cex, cgul_trie_t trie, cgul_trie_node_t n, void data)

Functions
CGUL_EXPORT cgul_trie_t	cgul_trie__new (cgul_exception_t *cex)

CGUL_EXPORT cgul_trie_t	cgul_trie__new_with_indexing (cgul_exception_t *cex)

CGUL_EXPORT void	cgul_trie__delete (cgul_trie_t trie)

CGUL_EXPORT void	cgul_trie__free_keys (cgul_trie_t trie)

CGUL_EXPORT void	cgul_trie__free_values (cgul_trie_t trie)

CGUL_EXPORT unsigned long int	cgul_trie__get_cache_size (cgul_exception_t *cex, cgul_trie_t trie)

CGUL_EXPORT void	cgul_trie__set_cache_size (cgul_exception_t *cex, cgul_trie_t trie, unsigned long int size)

CGUL_EXPORT unsigned long int	cgul_trie__get_cache_reserve (cgul_exception_t *cex, cgul_trie_t trie)

CGUL_EXPORT void	cgul_trie__set_cache_reserve (cgul_exception_t *cex, cgul_trie_t trie, unsigned long int reserve)

CGUL_EXPORT int	cgul_trie__is_empty (cgul_exception_t *cex, cgul_trie_t trie)

CGUL_EXPORT void	cgul_trie__balance (cgul_exception_t *cex, cgul_trie_t trie, int maintain_relative_ages)

CGUL_EXPORT int	cgul_trie__insert (cgul_exception_t cex, cgul_trie_t trie, const char key, cgul_trie_node_t *n)

CGUL_EXPORT int	cgul_trie__insert_from_arrays (cgul_exception_t cex, cgul_trie_t trie, const char keys, void *values, unsigned long int kv_size, int maintain_relative_ages)

CGUL_EXPORT cgul_trie_node_t	cgul_trie__find (cgul_exception_t cex, cgul_trie_t trie, const char key)

CGUL_EXPORT cgul_trie_node_t	cgul_trie__find_at (cgul_exception_t *cex, cgul_trie_t trie, unsigned long int index)

CGUL_EXPORT int	cgul_trie__find_rank (cgul_exception_t cex, cgul_trie_t trie, const char key, unsigned long int *rank)

CGUL_EXPORT cgul_trie_node_t	cgul_trie__find_floor (cgul_exception_t cex, cgul_trie_t trie, const char search_key)

CGUL_EXPORT cgul_trie_node_t	cgul_trie__find_ceiling (cgul_exception_t cex, cgul_trie_t trie, const char search_key)

CGUL_EXPORT int	cgul_trie__find_closed_range_by_prefix (cgul_exception_t cex, cgul_trie_t trie, const char prefix, cgul_trie_node_t begin_node, cgul_trie_node_t end_node)

CGUL_EXPORT int	cgul_trie__find_half_opened_range_by_prefix (cgul_exception_t cex, cgul_trie_t trie, const char prefix, cgul_trie_node_t begin_node, cgul_trie_node_t end_node)

CGUL_EXPORT int	cgul_trie__find_keys_by_prefix (cgul_exception_t cex, cgul_trie_t trie, const char prefix, const char **keys, unsigned long int keys_size)

CGUL_EXPORT int	cgul_trie__find_values_by_prefix (cgul_exception_t cex, cgul_trie_t trie, const char prefix, void **values, unsigned long int values_size)

CGUL_EXPORT int	cgul_trie__find_nodes_by_prefix (cgul_exception_t cex, cgul_trie_t trie, const char prefix, cgul_trie_node_t *nodes, unsigned long int nodes_size)

CGUL_EXPORT const char *	cgul_trie__find_longest_prefix_of (cgul_exception_t cex, cgul_trie_t trie, const char complete_string)

CGUL_EXPORT cgul_trie_node_t	cgul_trie__get_front (cgul_exception_t *cex, cgul_trie_t trie)

CGUL_EXPORT cgul_trie_node_t	cgul_trie__get_back (cgul_exception_t *cex, cgul_trie_t trie)

CGUL_EXPORT cgul_trie_node_t	cgul_trie__get_oldest (cgul_exception_t *cex, cgul_trie_t trie)

CGUL_EXPORT void	cgul_trie__set_oldest (cgul_exception_t *cex, cgul_trie_t trie, cgul_trie_node_t n)

CGUL_EXPORT cgul_trie_node_t	cgul_trie__get_youngest (cgul_exception_t *cex, cgul_trie_t trie)

CGUL_EXPORT void	cgul_trie__set_youngest (cgul_exception_t *cex, cgul_trie_t trie, cgul_trie_node_t n)

CGUL_EXPORT int	cgul_trie__remove (cgul_exception_t cex, cgul_trie_t trie, const char key_in, char key_out, void value_out)

CGUL_EXPORT void	cgul_trie__remove_node (cgul_exception_t cex, cgul_trie_t trie, cgul_trie_node_t n, char key_out, void *value_out)

CGUL_EXPORT int	cgul_trie__remove_at (cgul_exception_t cex, cgul_trie_t trie, unsigned long int index, char key_out, void *value_out)

CGUL_EXPORT int	cgul_trie__remove_front (cgul_exception_t cex, cgul_trie_t trie, char key_out, void *value_out)

CGUL_EXPORT int	cgul_trie__remove_back (cgul_exception_t cex, cgul_trie_t trie, char key_out, void *value_out)

CGUL_EXPORT int	cgul_trie__remove_range (cgul_exception_t *cex, cgul_trie_t trie, cgul_trie_node_t first, cgul_trie_node_t last, cgul_cache_t keys_cache, cgul_cache_t values_cache)

CGUL_EXPORT void	cgul_trie__clear (cgul_exception_t *cex, cgul_trie_t trie, cgul_cache_t keys_cache, cgul_cache_t values_cache)

CGUL_EXPORT unsigned long int	cgul_trie__get_size (cgul_exception_t *cex, cgul_trie_t trie)

CGUL_EXPORT void	cgul_trie__swap (cgul_exception_t *cex, cgul_trie_t trie1, cgul_trie_t trie2)

CGUL_EXPORT void	cgul_trie__foldl_keys (cgul_exception_t cex, cgul_trie_t trie, cgul_trie__fold_key_t f, void data)

CGUL_EXPORT void	cgul_trie__foldr_keys (cgul_exception_t cex, cgul_trie_t trie, cgul_trie__fold_key_t f, void data)

CGUL_EXPORT void	cgul_trie__foldl_values (cgul_exception_t cex, cgul_trie_t trie, cgul_trie__fold_value_t f, void data)

CGUL_EXPORT void	cgul_trie__foldr_values (cgul_exception_t cex, cgul_trie_t trie, cgul_trie__fold_value_t f, void data)

CGUL_EXPORT void	cgul_trie__foldl_pairs (cgul_exception_t cex, cgul_trie_t trie, cgul_trie__fold_pair_t f, void data)

CGUL_EXPORT void	cgul_trie__foldr_pairs (cgul_exception_t cex, cgul_trie_t trie, cgul_trie__fold_pair_t f, void data)

CGUL_EXPORT void	cgul_trie__traverse (cgul_exception_t cex, cgul_trie_t trie, cgul_trie__traverse_t f, void data)

CGUL_EXPORT void	cgul_trie__traverse_range (cgul_exception_t cex, cgul_trie_t trie, cgul_trie_node_t first, cgul_trie_node_t last, cgul_trie__traverse_t f, void data)

Detailed Description

Prefix tree implemented as a Ternary Search Trie (TST).

Author: Paul Serice

Typedef Documentation

§ cgul_trie_t

typedef typedefCGUL_BEGIN_C struct cgul_trie* cgul_trie_t

Opaque pointer to a cgul_trie instance.

§ cgul_trie__fold_key_t

typedef int(* cgul_trie__fold_key_t) (cgul_exception_t *cex, const char *key, void *data)

This typedef is the interface for the combining function used by the following methods:

    cgul_trie__foldl_keys()
    cgul_trie__foldr_keys()

The client must not alter key.

Parameters

[in,out]	cex	c-style exception
[in]	key	key
[in]	data	client data

Returns: whether to continue

§ cgul_trie__fold_value_t

typedef int(* cgul_trie__fold_value_t) (cgul_exception_t *cex, void *value, void *data)

This typedef is the interface for the combining function used by the following methods:

    cgul_trie__foldl_values()
    cgul_trie__foldr_values()

Parameters

[in,out]	cex	c-style exception
[in]	value	value
[in]	data	client data

Returns: whether to continue

§ cgul_trie__fold_pair_t

typedef int(* cgul_trie__fold_pair_t) (cgul_exception_t *cex, const char *key, void *value, void *data)

This typedef is the interface for the combining function used by the following methods:

    cgul_trie__foldl_pairs()
    cgul_trie__foldr_pairs()

The client must not alter key.

Parameters

[in,out]	cex	c-style exception
[in]	key	key
[in]	value	value
[in]	data	client data

Returns: whether to continue

§ cgul_trie__traverse_t

typedef int(* cgul_trie__traverse_t) (cgul_exception_t *cex, cgul_trie_t trie, cgul_trie_node_t n, void *data)

This typedef is the interface for the callback function used by the following methods:

    cgul_trie__traverse()
    cgul_trie__traverse_range()

Parameters

[in,out]	cex	c-style exception
[in]	trie	`cgul_trie` instance
[in]	n	node
[in]	data	client data

Returns: whether to continue

Function Documentation

§ cgul_trie__new()

CGUL_EXPORT cgul_trie_t cgul_trie__new ( cgul_exception_t * cex )

Create a new cgul_trie object. The caller is responsible for freeing the object by calling cgul_trie__delete(). If memory cannot be allocated, NULL is returned, and an exception is thrown.

The cgul_trie object that is returned does not allow you to index into it as though it were an array. This saves you three unsigned long values for each node in the trie. It also saves you about 15% for inserts and deletes. If in doubt, use this constructor.

This class does not take ownership of the inserted key/value pairs. Instead, the client is responsible for freeing the key/value pairs only after their nodes have been permanently removed from the cgul_trie. The cgul_trie__traverse() method can be used to remove each node safely before calling cgul_trie__delete().

Parameters

[in,out] cex c-style exception

Returns: new cgul_trie instance

Referenced by cgul_trie_cxx::cgul_trie_cxx().

§ cgul_trie__new_with_indexing()

CGUL_EXPORT cgul_trie_t cgul_trie__new_with_indexing ( cgul_exception_t * cex )

Create a new cgul_trie object. The caller is responsible for freeing the object by calling cgul_trie__delete(). If memory cannot be allocated, NULL is returned, and an exception is thrown.

The cgul_trie object that is returned allows you to index into it as though it were an array. This costs you three unsigned long values for each node in the trie. It also costs you about 15% for inserts and deletes. You should only use this constructor if you know you want to be able to call cgul_trie__find_at() or cgul_trie__remove_at().

This class does not take ownership of the inserted key/value pairs. Instead, the client is responsible for freeing the key/value pairs only after their nodes have been permanently removed from the cgul_trie. The cgul_trie__traverse() method can be used to remove each node safely before calling cgul_trie__delete().

Parameters

[in,out] cex c-style exception

Returns: new cgul_trie instance

Referenced by cgul_trie_cxx::cgul_trie_cxx().

§ cgul_trie__delete()

CGUL_EXPORT void cgul_trie__delete ( cgul_trie_t trie )

This method frees all internally allocated memory. This does not include the key/value pairs stored in the trie. The client is responsible for freeing the key/value pairs when the client thinks it is convenient and safe to do so; however, the client must understand that freeing a key before removing its node invalidates the data structure.

As a convenience, you may want to call cgul_trie__clear() before calling this method in order to properly put the keys and values back on their respective cgul_cache objects (if cgul_cache objects are being used) before you delete the trie. If cgul_cache objects are not being used, the client needs to arrange some other mechanism to free the keys or values.

Do not try to access trie after calling this method.

Parameters

[in] trie trie instance

See also: cgul_trie__free_keys(); cgul_trie__free_values()

Referenced by cgul_trie_cxx::set_obj(), and cgul_trie_cxx::~cgul_trie_cxx().

§ cgul_trie__free_keys()

CGUL_EXPORT void cgul_trie__free_keys ( cgul_trie_t trie )

This method calls free() on all the keys in the trie trie. Because this is such a common operation, it is an exception to the rule that cgul containers never free keys. This method should only ever be called immediately before calling cgul_trie__delete() because it otherwise invalidates the trie. Because this function is basically an extension of cgul_trie__delete(), it does not accept a cgul_exception object as an input parameter.

Parameters

[in] trie cgul_trie instance

Referenced by cgul_trie_cxx::free_keys().

§ cgul_trie__free_values()

CGUL_EXPORT void cgul_trie__free_values ( cgul_trie_t trie )

This method calls free() on all the values in the trie trie. Because this is such a common operation, it is an exception to the rule that cgul containers never free values. This method should only ever be called immediately before calling cgul_trie__delete() because it otherwise invalidates the trie. Because this function is basically an extension of cgul_trie__delete(), it does not accept a cgul_exception object as an input parameter.

Parameters

[in] trie cgul_trie instance

Referenced by cgul_trie_cxx::free_values().

§ cgul_trie__get_cache_size()

CGUL_EXPORT unsigned long int cgul_trie__get_cache_size	(	cgul_exception_t *	cex,
		cgul_trie_t	trie
	)

Get the size of the cache of nodes.

Parameters

[in]	cex	c-style exception
[in]	trie	`cgul_trie` instance

Returns: size of the cache of nodes

Referenced by cgul_trie_cxx::get_cache_size().

§ cgul_trie__set_cache_size()

CGUL_EXPORT void cgul_trie__set_cache_size	(	cgul_exception_t *	cex,
		cgul_trie_t	trie,
		unsigned long int	size
	)

Set the size of the cache of nodes.

For efficiency, the cgul_trie can keep a cache of nodes that can be reused. In many situations, this can greatly reduce the number of calls to malloc() which can greatly improve performance and reduce memory fragmentation.

You can release all the cached nodes and disable caching of nodes by setting the cache reserve to 0 and the cache size to 0 (in that order). This is the default.

If an error occurs (while enlarging the cache), an exception is thrown.

Parameters

[in,out]	cex	c-style exception
[in]	trie	`cgul_trie` instance
[in]	size	of the cache of nodes

Referenced by cgul_trie_cxx::set_cache_size().

§ cgul_trie__get_cache_reserve()

CGUL_EXPORT unsigned long int cgul_trie__get_cache_reserve	(	cgul_exception_t *	cex,
		cgul_trie_t	trie
	)

Get the reserve limit of the cache of nodes.

Parameters

[in]	cex	c-style exception
[in]	trie	`cgul_trie` instance

Returns: reserve limit of the cache of nodes

Referenced by cgul_trie_cxx::get_cache_reserve().

§ cgul_trie__set_cache_reserve()

CGUL_EXPORT void cgul_trie__set_cache_reserve	(	cgul_exception_t *	cex,
		cgul_trie_t	trie,
		unsigned long int	reserve
	)

Set the reserve limit of the cache of nodes and guarantee that at least that many nodes are allocated and waiting in reserve.

When you use this method to increase the reserve, you are guaranteed that at least reserve count of nodes will be allocated and reserved for future use.

This is useful because cgul_trie__insert() can throw an exception if it cannot allocate a node to hold the key/value pair. Thus, by allocating and reserving a node now, we know that cgul_trie__insert() will be able to run without error later when the node is "unreserved". Normally, this is not an issue because you can almost always just insert at the moment when it is requested, but if the cgul_trie is busy at that moment (perhaps it is iterating over its nodes), you'll have to queue insert (and remove) requests for later execution.

To "unreserve" a node so that it can be used, you simply call this method again with a value for reserve that is less than the current reserve limit.

If an error occurs while allocating the reserved nodes, an exception is thrown.

WARNING: If you reserve nodes without "unreserving" them, you will introduce a memory leak that is difficult to track down because this class is careful to free all of the cached nodes (including the reserved nodes) when it is deleted, but the reserved nodes will just sit around in memory until that time. Thus, after reserving nodes by calling this method, you must remember to timely set the reserve level back to zero in order to make those nodes available.

Parameters

[in,out]	cex	c-style exception
[in]	trie	`cgul_trie` instance
[in]	reserve	of the cache of nodes

See also: cgul_cache__set_reserve()

Referenced by cgul_trie_cxx::set_cache_reserve().

§ cgul_trie__is_empty()

CGUL_EXPORT int cgul_trie__is_empty	(	cgul_exception_t *	cex,
		cgul_trie_t	trie
	)

Return 1 if the trie trie is empty; otherwise, return 0.

Parameters

[in]	cex	c-style exception
[in]	trie	`cgul_trie` instance

Returns: whether the trie is empty

Referenced by cgul_trie_cxx::is_empty().

§ cgul_trie__balance()

CGUL_EXPORT void cgul_trie__balance	(	cgul_exception_t *	cex,
		cgul_trie_t	trie,
		int	maintain_relative_ages
	)

Balance the trie trie. If an error occurs, an exception is thrown.

Because the key/value pairs are reinserted randomly into the trie, the resulting older/younger linked list (which tracks insertion order) will generally not match the original insertion order. However, if maintain_relative_ages is true, this method will take the extra, relatively expensive step of adjusting the older/younger list to match the original order.

Ternary Search Tries have worst-case search behavior of O(n). This problem occurs when the keys are inserted in sort order. This method can be used to reinsert all the keys at random which will likely come very close to minimizing the depth of the trie which will result in search behavior of O(log n). This is an expensive operation which should be called rarely over the lifetime of the trie.

One plausible scenario where this method could be called is if all the keys are read at once from a sorted list. After inserting all the keys, this method could be called to balance the trie. (Another solution to this problem would be to insert all the keys through cgul_trie__insert_from_arrays().)

Parameters

[in,out]	cex	c-style exception
[in]	trie	`cgul_trie` instance
[in]	maintain_relative_ages	whether to maintain relative node ages

See also: cgul_trie__insert_from_arrays()

Referenced by cgul_trie_cxx::balance().

§ cgul_trie__insert()

CGUL_EXPORT int cgul_trie__insert	(	cgul_exception_t *	cex,
		cgul_trie_t	trie,
		const char *	key,
		cgul_trie_node_t *	n
	)

Insert key into the trie trie. If key already exists, another node with the same key is not created. The new or pre-existing node is returned in n if n is not NULL.

If a matching node is not found, 1 is returned because a new node can and will be inserted. If a matching node is found, 0 is returned because the insertion failed because the key already exists.

If an error occurs, 0 is returned, *n is set to NULL (if n is not NULL), and an exception is thrown.

It is important to understand that the cgul_trie class (like all containers in the cgul library) does not take ownership of key. It also does not attempt to make a copy of the thing pointed to by key. This gives the user complete control over the lifetime of the key and gives a real performance boost in many cases; however, this means that key must not be invalidated while it is still being used by this class.

This method operates as it does so that you only have to search the trie once when doing an insert. Logically, you would usually like to do a find to see if the trie holds your key. If it does, you use the value associated with that key in some way. If it does not, you then want to insert a new key/value pair into the trie. The problem with divorcing the find from the insert is that it then requires you to search the trie twice. Once to see if the key exists and once to do the insertion.

To prevent having to search the trie twice, you can just call this method to handle both inserting and updating nodes. It will search the trie once, and it will always return a pointer to the correct node. You can then use cgul_trie_node__get_value() or cgul_trie_node__set_value() to get or set the value indexed by "key".

TIP: You might find it convenient to use cgul_string to build up a string that you use as a key. You can then use cgul_string__get_value() [yes, get_value()] and pass the string to cgul_trie__insert(). If the insert succeeds, you can inform the cgul_string object that it is no longer the owner of the underlying C-style string by calling cgul_string__take_value() [yes, take_value()]. An example is as follows:

    int insert_rv = 0;
    cgul_trie_node_t n = NULL;

    char* w = cgul_string__get_value(word);
    insert_rv = cgul_trie__insert(trie, w, &n);
    if (*cex) {
        goto out;
    }
    if (insert_rv) {
        cgul_string__take_value(word);
        . . .
    } else {
        . . .
    }

NOTE: Inserting a key/value pair does not cause this class to take ownership of key or value. The client must make sure the values pointed to by key and value are not invalidated during the life of the newly created node. If the client needs to delete the key or the value or both, the client needs to manually arrange for this.

Parameters

[in,out]	cex	c-style exception
[in]	trie	`cgul_trie` instance
[in]	key	key
[out]	n	node that already existed or was newly created

Returns: 1 if a new node was inserted; 0 if a node with the same key already exists

See also: cgul_trie__balance(); cgul_trie__insert_from_arrays()

Referenced by cgul_trie_cxx::insert().

§ cgul_trie__insert_from_arrays()

CGUL_EXPORT int cgul_trie__insert_from_arrays	(	cgul_exception_t *	cex,
		cgul_trie_t	trie,
		const char **	keys,
		void **	values,
		unsigned long int	kv_size,
		int	maintain_relative_ages
	)

Insert into the trie trie the key/value pairs formed by interleaving keys from the keys array with values from the values array. If values is NULL, all values will be set to NULL. The number of new nodes insert is returned. If an error occurs, an exception is thrown.

This method copies the keys and values arrays and then performs the same shuffle on each copy before inserting the shuffled key/value pairs. It shuffles the key/value pairs because inserting sorted keys into a Ternary Search Trie leads to worst-case search behavior of O(N). By shuffling the keys first, the trie will very likely be balanced leading to O(log N) search behavior.

Because the key/value pairs are inserted randomly into the trie, the resulting older/younger linked list (which tracks insertion order) will generally not match the order of the key/value pairs from the keys and values arrays. However, if maintain_relative_ages is true, this method will take the extra, relatively expensive step of adjusting the older/younger list to match the original order of the key/value pairs.

Parameters

[in,out]	cex	c-style exception
[in]	trie	`cgul_trie` instance
[in]	keys	keys
[in]	values	values
[in]	kv_size	number of key/value pairs (i.e., size of the arrays)
[in]	maintain_relative_ages	whether to maintain relative node ages

Returns: number of new nodes inserted

See also: balance()

Referenced by cgul_trie_cxx::insert_from_arrays().

§ cgul_trie__find()

CGUL_EXPORT cgul_trie_node_t cgul_trie__find	(	cgul_exception_t *	cex,
		cgul_trie_t	trie,
		const char *	key
	)

Find the node indexed by key. If the key does not exist, NULL is returned; otherwise, the node associated with the key is returned.

Parameters

[in]	cex	c-style exception
[in]	trie	`cgul_trie` instance
[in]	key	key

Returns: node associated with the key or NULL

Referenced by cgul_trie_cxx::find().

§ cgul_trie__find_at()

CGUL_EXPORT cgul_trie_node_t cgul_trie__find_at	(	cgul_exception_t *	cex,
		cgul_trie_t	trie,
		unsigned long int	index
	)

Find the node indexed by position. This lets you use a cgul_trie instances like you would an array. Even in the best-case scenario where indexing into cgul_trie is a logarithmic function, it will still be slower than indexing into an array, but you get all the advantages of a trie including relatively fast insertion and deletion. So, if you ever feel the need to shift the elements of an array, this method might be for you.

If index is out of range, NULL is returned; otherwise, the node returned is the same node that would be returned if you had an array trie that held all the nodes in the trie in sorted order, and you asked for trie[index].

This method throws an exception if trie was not created with cguil_trie__new_with_indexing().

Parameters

[in,out]	cex	c-style exception
[in]	trie	`cgul_trie` instance
[in]	index	index into sorted keys of node to return

Returns: node associated with index

See also: cgul_trie__find_rank()

Referenced by cgul_trie_cxx::find_at().

§ cgul_trie__find_rank()

CGUL_EXPORT int cgul_trie__find_rank	(	cgul_exception_t *	cex,
		cgul_trie_t	trie,
		const char *	key,
		unsigned long int *	rank
	)

Return whether the rank of the key key could be determined. If the rank could be determined it is returned in *rank (if rank is not NULL).

The rank is the number of keys less than key. It can be used as the index parameter to cgul_trie__find_at() in order to lookup key by index.

This method throws an exception if trie was not created with cguil_trie__new_with_indexing().

Parameters

[in,out]	cex	c-style exception
[in]	trie	`cgul_trie` instance
[in]	key	key
[out]	rank	rank of key

Returns: whether the key exists in the trie

See also: cgul_trie__find_at()

Referenced by cgul_trie_cxx::find_rank().

§ cgul_trie__find_floor()

CGUL_EXPORT cgul_trie_node_t cgul_trie__find_floor	(	cgul_exception_t *	cex,
		cgul_trie_t	trie,
		const char *	search_key
	)

Find the node having the largest key less than or equal to the search key search_key and return it. If such a key does not exist, NULL is returned.

Parameters

[in]	cex	c-style exception
[in]	trie	`cgul_trie` instance
[in]	search_key	search key

Returns: floor node or NULL

Referenced by cgul_trie_cxx::find_floor().

§ cgul_trie__find_ceiling()

CGUL_EXPORT cgul_trie_node_t cgul_trie__find_ceiling	(	cgul_exception_t *	cex,
		cgul_trie_t	trie,
		const char *	search_key
	)

Find the node having the smallest key greater than or equal to the search key search_key and return it. If such a key does not exist, NULL is returned.

Parameters

[in]	cex	c-style exception
[in]	trie	`cgul_trie` instance
[in]	search_key	search key

Returns: ceiling node or NULL

Referenced by cgul_trie_cxx::find_ceiling().

§ cgul_trie__find_closed_range_by_prefix()

CGUL_EXPORT int cgul_trie__find_closed_range_by_prefix	(	cgul_exception_t *	cex,
		cgul_trie_t	trie,
		const char *	prefix,
		cgul_trie_node_t *	begin_node,
		cgul_trie_node_t *	end_node
	)

When dealing with prefixes that generate a large number of matches, it may be more responsive from the user's perspective to iterate over the results. To that end, this method returns the closed range [begin_node, end_node] for the nodes in the trie trie associated with keys that start with the prefix prefix. If any nodes exist in the range, this method returns 1; otherwise, this methods returns 0. If an error occurs, an exception is thrown.

Parameters

[in,out]	cex	c-style exception
[in]	trie	`cgul_trie` instance
[in]	prefix	prefix
[out]	begin_node	beginning node (inclusive) or `NULL`
[out]	end_node	ending node (inclusive) or `NULL`

Returns: whether any nodes were found

See also: cgul_trie__find_half_opened_range_by_prefix()

Referenced by cgul_trie_cxx::find_closed_range_by_prefix().

§ cgul_trie__find_half_opened_range_by_prefix()

CGUL_EXPORT int cgul_trie__find_half_opened_range_by_prefix	(	cgul_exception_t *	cex,
		cgul_trie_t	trie,
		const char *	prefix,
		cgul_trie_node_t *	begin_node,
		cgul_trie_node_t *	end_node
	)

When dealing with prefixes that generate a large number of matches, it may be more responsive from the user's perspective to iterate over the results. To that end, this method returns the half-opened range [begin_node, end_node] for the nodes in the trie trie associated with keys that start with the prefix prefix. If any nodes exist in the range, this method returns 1; otherwise, this methods returns 0. If an error occurs, an exception is thrown.

Parameters

[in,out]	cex	c-style exception
[in]	trie	`cgul_trie` instance
[in]	prefix	prefix
[out]	begin_node	beginning node (inclusive) or `NULL`
[out]	end_node	ending node (exclusive) or `NULL`

Returns: whether any nodes were found

See also: cgul_trie__find_closed_range_by_prefix()

Referenced by cgul_trie_cxx::find_half_opened_range_by_prefix().

§ cgul_trie__find_keys_by_prefix()

CGUL_EXPORT int cgul_trie__find_keys_by_prefix	(	cgul_exception_t *	cex,
		cgul_trie_t	trie,
		const char *	prefix,
		const char ***	keys,
		unsigned long int *	keys_size
	)

All keys in the trie trie that start with the prefix prefix are returned in the arrays keys (if not NULL) and the number of keys is returned in keys_size (if not NULL). If any keys are found, this method returns 1; otherwise, this methods returns 0. If an error occurs, an exception is thrown.

The client is responsible for calling free() on the keys array but must not modify or delete any of the individual keys.

The following example code shows how to print all the keys in the trie that match a particular prefix and how to clean up afterward:

     void
     print_keys_by_prefix(cgul_exception_t* cex,
                          cgul_trie_t trie,
                          const char* prefix)
     {
         unsigned long int i = 0;
         const char** keys = NULL;
         unsigned long int keys_size = 0;

         assert(cex);
         if (*cex) {
             goto out;
         }

         // Iterate over all the keys that match the prefix.
         if (cgul_trie__find_keys_by_prefix(
                 cex, trie, prefix, &keys, &keys_size))
         {
             for (i = 0 ; i < keys_size ; ++i) {
                 printf("%s -> %s\n", prefix, keys[i]);
             }
         }

      out:

         // Clean up.
         if (keys) {
             free(keys);
         }

Parameters

[in,out]	cex	c-style exception
[in]	trie	`cgul_trie` instance
[in]	prefix	prefix
[out]	keys	keys found by prefix
[out]	keys_size	number of keys found

Returns: whether any keys were found

See also: cgul_trie__find_nodes_by_prefix(); cgul_trie__find_closed_range_by_prefix(); cgul_trie__find_half_opened_range_by_prefix()

Referenced by cgul_trie_cxx::find_keys_by_prefix().

§ cgul_trie__find_values_by_prefix()

CGUL_EXPORT int cgul_trie__find_values_by_prefix	(	cgul_exception_t *	cex,
		cgul_trie_t	trie,
		const char *	prefix,
		void ***	values,
		unsigned long int *	values_size
	)

All values in the trie trie associated with keys that start with the prefix prefix are returned in the arrays values (if not NULL) and the number of values is returned in values_size (if not NULL). If any values are found, this method returns 1; otherwise, this methods returns 0. If an error occurs, an exception is thrown.

The client is responsible for calling free() on the values array. The client is free to modify but not delete any of the individual values unless the value is also used as a key for the trie. If a value needs to be delete the client should do so only after using cgul_trie_node__set_value() to clear the value.

The following example code shows how to print all the values in the trie associated with keys that match a particular prefix and how to clean up afterward:

     void
     print_values_by_prefix(cgul_exception_t* cex,
                            cgul_trie_t trie,
                            const char* prefix)
     {
         unsigned long int i = 0;
         void** values = NULL;
         unsigned long int values_size = 0;

         assert(cex);
         if (*cex) {
             goto out;
         }

         // Iterate over all the values that match the prefix.
         if (cgul_trie__find_values_by_prefix(
                 cex, trie, prefix, &values, &values_size))
         {
             for (i = 0 ; i < values_size ; ++i) {
                 printf("%s -> %p\n", prefix, values[i]);
             }
         }

      out:

         // Clean up.
         if (values) {
             free(values);
         }

Parameters

[in,out]	cex	c-style exception
[in]	trie	`cgul_trie` instance
[in]	prefix	prefix
[out]	values	values found by prefix
[out]	values_size	number of values found

Returns: whether any values were found

See also: cgul_trie__find_nodes_by_prefix(); cgul_trie__find_closed_range_by_prefix(); cgul_trie__find_half_opened_range_by_prefix()

Referenced by cgul_trie_cxx::find_values_by_prefix().

§ cgul_trie__find_nodes_by_prefix()

CGUL_EXPORT int cgul_trie__find_nodes_by_prefix	(	cgul_exception_t *	cex,
		cgul_trie_t	trie,
		const char *	prefix,
		cgul_trie_node_t **	nodes,
		unsigned long int *	nodes_size
	)

All nodes in the trie trie associated with keys that start with the prefix prefix are returned in the arrays nodes (if not NULL) and the number of nodes is returned in nodes_size (if not NULL). If any nodes are found, this method returns 1; otherwise, this methods returns 0. If an error occurs, an exception is thrown.

The client is responsible for calling free() on the nodes array. The client must not delete any of the nodes nor delete or modify any of the keys stored in the nodes, but the client is free to modify but not delete any of the individual values stored in the nodes unless the value is also used as a key for the trie. If a value needs to be delete the client should do so only after using cgul_trie_node__set_value() to clear the value.

The following example code shows how to print all the key/value pairs in the trie where the keys match a particular prefix and how to clean up afterward:

     void
     print_nodes_by_prefix(cgul_exception_t* cex,
                           cgul_trie_t trie,
                           const char* prefix)
     {
         unsigned long int i = 0;
         const char* key = NULL;
         void* value = NULL;
         cgul_trie_node_t* nodes = NULL;
         unsigned long int nodes_size = 0;

         assert(cex);
         if (*cex) {
             goto out;
         }

         // Iterate over all the nodes that match the prefix.
         if (cgul_trie__find_nodes_by_prefix(
                 cex, trie, prefix, &nodes, &nodes_size))
         {
             for (i = 0 ; i < nodes_size ; ++i) {
                 key = cgul_trie_node__get_key(cex, nodes[i]);
                 value = cgul_trie_node__get_value(cex, nodes[i]);
                 printf("%s -> (%s, %p)\n", prefix, key, value);
             }
         }

      out:

         // Clean up.
         if (nodes) {
             free(nodes);
         }

Parameters

[in,out]	cex	c-style exception
[in]	trie	`cgul_trie` instance
[in]	prefix	prefix
[out]	nodes	nodes found by prefix
[out]	nodes_size	number of nodes found

Returns: whether any nodes were found

See also: cgul_trie__find_closed_range_by_prefix(); cgul_trie__find_half_opened_range_by_prefix()

Referenced by cgul_trie_cxx::find_nodes_by_prefix().

§ cgul_trie__find_longest_prefix_of()

CGUL_EXPORT const char* cgul_trie__find_longest_prefix_of	(	cgul_exception_t *	cex,
		cgul_trie_t	trie,
		const char *	complete_string
	)

Return the key in the trie trie that is the longest prefix of complete_string. To match, the entire key must be a prefix of complete_string. If no keys are a prefix, NULL is returned.

For example, assume "abcx" and "abcxyz123" are the only keys in the trie and this method is called with complete_string equal to "abcxyz", the longest key that is a prefix of the complete string is "abcx". The result is not "abcxyz123" because the entire key must be a prefix of complete_string.

One practical example for the use of this function is if the trie holds IP routing information for subnetworks. To route a packet to a particular IP address, you will likely want to use the route that is the longest prefix of the IP address. (See Wikipedia's "Longest Prefix Match" entry.)

Parameters

[in]	cex	c-style exception
[in]	trie	`cgul_trie` instance
[in]	complete_string	complete string

Returns: key that is the longest prefix of the complete string

Referenced by cgul_trie_cxx::find_longest_prefix_of().

§ cgul_trie__get_front()

CGUL_EXPORT cgul_trie_node_t cgul_trie__get_front	(	cgul_exception_t *	cex,
		cgul_trie_t	trie
	)

Return the node holding the first key according to sort order. This operation is not O(1) because it has to descend the trie looking for the front node. If the trie is empty, NULL is returned.

The following example shows how to iterate over the entire trie in sort order:

    cgul_trie_node_t n = cgul_trie__get_front(cex, t);
    for ( ; n ; n = cgul_trie_node__get_next(cex, n)) {
        ...
    }

Parameters

[in]	cex	c-style exception
[in]	trie	`cgul_trie` instance

Returns: front node

Referenced by cgul_trie_cxx::foldl_keys(), cgul_trie_cxx::foldl_pairs(), cgul_trie_cxx::foldl_values(), cgul_trie_cxx::get_front(), and cgul_trie_cxx::traverse_range().

§ cgul_trie__get_back()

CGUL_EXPORT cgul_trie_node_t cgul_trie__get_back	(	cgul_exception_t *	cex,
		cgul_trie_t	trie
	)

Return the node holding the last key according to sort order. This operation is not O(1) because it has to descend the trie looking for the back node. If the trie is empty, NULL is returned.

The following example shows how to iterate over the entire trie in reverse sort order:

    cgul_trie_node_t n = cgul_trie__get_back(cex, t);
    for ( ; n ; n = cgul_trie_node__get_prev(cex, n)) {
        ...
    }

Parameters

[in]	cex	c-style exception
[in]	trie	`cgul_trie` instance

Returns: back node

Referenced by cgul_trie_cxx::foldr_keys(), cgul_trie_cxx::foldr_pairs(), cgul_trie_cxx::foldr_values(), cgul_trie_cxx::get_back(), and cgul_trie_cxx::traverse_range().

§ cgul_trie__get_oldest()

CGUL_EXPORT cgul_trie_node_t cgul_trie__get_oldest	(	cgul_exception_t *	cex,
		cgul_trie_t	trie
	)

Return the oldest node according to chronological order (i.e., the order in which the nodes are inserted). This operation is O(1). If the trie is empty, NULL is returned. This class does not have to search the trie in order to find the oldest node because it efficiently keeps a direct pointer to the oldest node up to date.

The following example shows how to iterate over the entire trie in chronological order:

    cgul_trie_node_t n = cgul_trie__get_oldest(cex, t);
    for ( ; n ; n = cgul_trie_node__get_younger(cex, n)) {
        ...
    }

Parameters

[in]	cex	c-style exception
[in]	trie	`cgul_trie` instance

Returns: oldest node

See also: cgul_trie_node__get_younger()

Referenced by cgul_trie_cxx::get_oldest().

§ cgul_trie__set_oldest()

CGUL_EXPORT void cgul_trie__set_oldest	(	cgul_exception_t *	cex,
		cgul_trie_t	trie,
		cgul_trie_node_t	n
	)

Set the oldest node in the trie to be n. Calling this method has the potential to confuse iterators and should be handled with roughly the same level of caution as calling cgul_trie__remove_node().

This method could be used, for example, if your code expires the oldest node in the trie, and you want to force n to be the next node to expire.

Parameters

[in]	cex	c-style exception
[in]	trie	`cgul_trie` instance
[in]	n	node

See also: cgul_trie__set_youngest()

Referenced by cgul_trie_cxx::set_oldest().

§ cgul_trie__get_youngest()

CGUL_EXPORT cgul_trie_node_t cgul_trie__get_youngest	(	cgul_exception_t *	cex,
		cgul_trie_t	trie
	)

Return the youngest node according to chronological order (i.e., the order in which the nodes are inserted). This operation is O(1). If the trie is empty, NULL is returned. This class does not have to search the trie in order to find the youngest node because it efficiently keeps a direct pointer to the youngest node up to date.

The following example shows how to iterate over the entire trie in reverse chronological order:

    cgul_trie_node_t n = cgul_trie__get_youngest(cex, t);
    for ( ; n ; n = cgul_trie_node__get_older(cex, n)) {
        ...
    }

Parameters

[in]	cex	c-style exception
[in]	trie	`cgul_trie` instance

Returns: youngest node

See also: cgul_trie_node__get_older()

Referenced by cgul_trie_cxx::get_youngest().

§ cgul_trie__set_youngest()

CGUL_EXPORT void cgul_trie__set_youngest	(	cgul_exception_t *	cex,
		cgul_trie_t	trie,
		cgul_trie_node_t	n
	)

Set the youngest node in the trie to be n. Calling this method has the potential to confuse iterators and should be handled with roughly the same level of caution as calling cgul_trie__remove_node().

This method could be used, for example, if your code expires the least-recently used (LRU) node. By calling cgul_trie__set_youngest() each time a node is used, the least-recently used node will be the oldest node in the trie.

Parameters

[in]	cex	c-style exception
[in]	trie	`cgul_trie` instance
[in]	n	node

See also: cgul_trie__set_oldest()

Referenced by cgul_trie_cxx::set_youngest().

§ cgul_trie__remove()

CGUL_EXPORT int cgul_trie__remove	(	cgul_exception_t *	cex,
		cgul_trie_t	trie,
		const char *	key_in,
		char **	key_out,
		void **	value_out
	)

Remove the node in trie associated with key_in. The key and value pointers stored in the node that is to be removed will be returned in key_out and value_out if you pass in pointers that are not NULL. This method returns 1 if the node was removed; it returns 0 otherwise.

It is almost always a mistake to naively call this method while iterating over the trie. See cgul_trie__remove_node() for details.

Parameters

[in]	cex	c-style exception
[in]	trie	`cgul_trie` instance
[in]	key_in	key associated with the node to be removed
[out]	key_out	pointer for the key stored in the node
[out]	value_out	pointer for the value stored in the node

Returns: whether the node was removed

Referenced by cgul_trie_cxx::remove().

§ cgul_trie__remove_node()

CGUL_EXPORT void cgul_trie__remove_node	(	cgul_exception_t *	cex,
		cgul_trie_t	trie,
		cgul_trie_node_t	n,
		char **	key_out,
		void **	value_out
	)

Remove node from the trie trie. The key and value pointers stored in the node that is to be removed will be returned in key_out and value_out if you pass in pointers that are not NULL.

It is almost always a mistake to naively call this method while iterating over the trie. The problem is that calling this method invalidates the node making it impossible to call cgul_trie_node__get_next() afterward. The solution is simple. Just call cgul_trie_node__get_next() before calling this method:

    curr = cgul_trie__find(&local, trie, key);
    for ( ; curr ; curr = next) {
        next = cgul_trie_node__get_next(&local, curr);
        cgul_trie__remove_node(&local,
                               trie,
                               curr,
                               &key_out,
                               &value_out);
        free(key_out);
        free(value_out);
    }

Alternatively, you can use cgul_trie__remove_range(), cgul_trie__traverse(), or cgul_trie__traverse_range().

Parameters

[in]	cex	c-style exception
[in]	trie	`cgul_trie` instance
[in]	n	node to be removed
[out]	key_out	pointer for the key stored in the node
[out]	value_out	pointer for the value stored in the node

Referenced by cgul_trie_cxx::remove_node().

§ cgul_trie__remove_at()

CGUL_EXPORT int cgul_trie__remove_at	(	cgul_exception_t *	cex,
		cgul_trie_t	trie,
		unsigned long int	index,
		char **	key_out,
		void **	value_out
	)

This method lets you remove a node based on its sorted order index. If the index is out of bounds, 0 is returned; otherwise 1 is returned. If you are interested in getting your hands on the key and value pointers stored in the node that is to be removed, they will be returned in key_out and value_out if you pass in pointers that are not NULL. index is zero-based.

This method throws an exception if trie was not created with cguil_trie__new_with_indexing().

It is almost always a mistake to naively call this method while iterating over the trie. See cgul_trie__remove_node() for details.

Parameters

[in,out]	cex	c-style exception
[in]	trie	`cgul_trie` instance
[in]	index	index of the sorted key associated with the node to be removed
[out]	key_out	pointer for the key stored in the node
[out]	value_out	pointer for the value stored in the node

Returns: whether the node was removed

Referenced by cgul_trie_cxx::remove_at().

§ cgul_trie__remove_front()

CGUL_EXPORT int cgul_trie__remove_front	(	cgul_exception_t *	cex,
		cgul_trie_t	trie,
		char **	key_out,
		void **	value_out
	)

Remove the first key/value pair as determined by sort order from the trie trie. The key and value pointers stored in the node that is to be removed will be returned in key_out and value_out if you pass in pointers that are not NULL.

Parameters

[in]	cex	c-style exception
[in]	trie	`cgul_trie` instance
[out]	key_out	pointer for the key stored in the node
[out]	value_out	pointer for the value stored in the node

Returns: whether the node was removed

Referenced by cgul_trie_cxx::remove_front().

§ cgul_trie__remove_back()

CGUL_EXPORT int cgul_trie__remove_back	(	cgul_exception_t *	cex,
		cgul_trie_t	trie,
		char **	key_out,
		void **	value_out
	)

Remove the last key/value pair as determined by sort order from the trie trie. The key and value pointers stored in the node that is to be removed will be returned in key_out and value_out if you pass in pointers that are not NULL.

Parameters

[in]	cex	c-style exception
[in]	trie	`cgul_trie` instance
[out]	key_out	pointer for the key stored in the node
[out]	value_out	pointer for the value stored in the node

Returns: whether the node was removed

Referenced by cgul_trie_cxx::remove_back().

§ cgul_trie__remove_range()

CGUL_EXPORT int cgul_trie__remove_range	(	cgul_exception_t *	cex,
		cgul_trie_t	trie,
		cgul_trie_node_t	first,
		cgul_trie_node_t	last,
		cgul_cache_t	keys_cache,
		cgul_cache_t	values_cache
	)

This method removes nodes in the range first (inclusive) to last (inclusive). Strictly as a convenience, this method is an exception to the rule that cgul containers never free keys or values. If you pass in keys_cache or values_cache instances that are not NULL, the keys or values will be put back on their respective caches.

Parameters

[in]	cex	c-style exception
[in]	trie	`cgul_trie` instance
[in]	first	first node in range
[in]	last	last node in range
[in]	keys_cache	keys cache
[in]	values_cache	values cache

Returns: whether any nodes were removed.

See also: cgul_cache__get_freer()

Referenced by cgul_trie_cxx::remove_range().

§ cgul_trie__clear()

CGUL_EXPORT void cgul_trie__clear	(	cgul_exception_t *	cex,
		cgul_trie_t	trie,
		cgul_cache_t	keys_cache,
		cgul_cache_t	values_cache
	)

This method clears the trie by removing each node individually. Strictly as a convenience, this method is an exception to the rule that cgul containers never free keys or values. If you pass in keys_cache or values_cache instances that are not NULL, the keys or values will be put back on their respective caches.

Parameters

[in]	cex	c-style exception
[in]	trie	`cgul_trie` instance
[in]	keys_cache	keys cache
[in]	values_cache	values cache

See also: cgul_trie__remove_range; cgul_cache__get_freer()

Referenced by cgul_trie_cxx::clear().

§ cgul_trie__get_size()

CGUL_EXPORT unsigned long int cgul_trie__get_size	(	cgul_exception_t *	cex,
		cgul_trie_t	trie
	)

Return the number of key/value pairs stored in the trie trie.

Parameters

[in]	cex	c-style exception
[in]	trie	`trie` instance

Returns: number of key/value pairs stored in the trie

Referenced by cgul_trie_cxx::get_size().

§ cgul_trie__swap()

CGUL_EXPORT void cgul_trie__swap	(	cgul_exception_t *	cex,
		cgul_trie_t	trie1,
		cgul_trie_t	trie2
	)

Swap the underlying data for trie1 and trie2. For large tries, this should be much faster than trying to do the same thing using removes and inserts.

Parameters

[in]	cex	c-style exception
[in]	trie1	first `cgul_trie` instance
[in]	trie2	second `cgul_trie` instance

Referenced by cgul_trie_cxx::swap().

§ cgul_trie__foldl_keys()

CGUL_EXPORT void cgul_trie__foldl_keys	(	cgul_exception_t *	cex,
		cgul_trie_t	trie,
		cgul_trie__fold_key_t	f,
		void *	data
	)

This method performs a left fold of the trie trie with the combining function f. f is called once for each key in the trie starting at the front of the trie and iterating forward to the end of the trie.

The first parameter passed into f is the standard c-style exception parameter. It can be used by f to throw an exception. The second parameter passed into f is the current key. The third parameter passed into f is the client data which is where the result of the fold should be accumulated.

f must return true after each iteration in order for iteration to continue.

Parameters

[in,out]	cex	c-style exception
[in]	trie	`cgul_trie` instance
[in]	f	combining function
[in]	data	client data passed to `f`

§ cgul_trie__foldr_keys()

CGUL_EXPORT void cgul_trie__foldr_keys	(	cgul_exception_t *	cex,
		cgul_trie_t	trie,
		cgul_trie__fold_key_t	f,
		void *	data
	)

This method performs a right fold of the trie trie with the combining function f. f is called once for each key in the trie starting at the back of the trie and iterating backward to the front of the trie.

The first parameter passed into f is the standard c-style exception parameter. It can be used by f to throw an exception. The second parameter passed into f is the current key. The third parameter passed into f is the client data which is where the result of the fold should be accumulated.

f must return true after each iteration in order for iteration to continue.

Parameters

[in,out]	cex	c-style exception
[in]	trie	`cgul_trie` instance
[in]	f	combining function
[in]	data	client data passed to `f`

§ cgul_trie__foldl_values()

CGUL_EXPORT void cgul_trie__foldl_values	(	cgul_exception_t *	cex,
		cgul_trie_t	trie,
		cgul_trie__fold_value_t	f,
		void *	data
	)

This method performs a left fold of the trie trie with the combining function f. f is called once for each value in the trie starting at the front of the trie and iterating forward to the end of the trie.

The first parameter passed into f is the standard c-style exception parameter. It can be used by f to throw an exception. The second parameter passed into f is the current value. The third parameter passed into f is the client data which is where the result of the fold should be accumulated.

f must return true after each iteration in order for iteration to continue.

Parameters

[in,out]	cex	c-style exception
[in]	trie	`cgul_trie` instance
[in]	f	combining function
[in]	data	client data passed to `f`

§ cgul_trie__foldr_values()

CGUL_EXPORT void cgul_trie__foldr_values	(	cgul_exception_t *	cex,
		cgul_trie_t	trie,
		cgul_trie__fold_value_t	f,
		void *	data
	)

This method performs a right fold of the trie trie with the combining function f. f is called once for each value in the trie starting at the back of the trie and iterating backward to the front of the trie.

The first parameter passed into f is the standard c-style exception parameter. It can be used by f to throw an exception. The second parameter passed into f is the current value. The third parameter passed into f is the client data which is where the result of the fold should be accumulated.

f must return true after each iteration in order for iteration to continue.

Parameters

[in,out]	cex	c-style exception
[in]	trie	`cgul_trie` instance
[in]	f	combining function
[in]	data	client data passed to `f`

§ cgul_trie__foldl_pairs()

CGUL_EXPORT void cgul_trie__foldl_pairs	(	cgul_exception_t *	cex,
		cgul_trie_t	trie,
		cgul_trie__fold_pair_t	f,
		void *	data
	)

This method performs a left fold of the trie trie with the combining function f. f is called once for each key/value pair in the trie starting at the front of the trie and iterating forward to the end of the trie.

The first parameter passed into f is the standard c-style exception parameter. It can be used by f to throw an exception. The second parameter passed into f is the current key. The third parameter passed into f is the current value. The fourth parameter passed into f is the client data which is where the result of the fold should be accumulated.

f must return true after each iteration in order for iteration to continue.

Parameters

[in,out]	cex	c-style exception
[in]	trie	`cgul_trie` instance
[in]	f	combining function
[in]	data	client data passed to `f`

§ cgul_trie__foldr_pairs()

CGUL_EXPORT void cgul_trie__foldr_pairs	(	cgul_exception_t *	cex,
		cgul_trie_t	trie,
		cgul_trie__fold_pair_t	f,
		void *	data
	)

This method performs a right fold of the trie trie with the combining function f. f is called once for each key/value pair in the trie starting at the back of the trie and iterating backward to the front of the trie.

The first parameter passed into f is the standard c-style exception parameter. It can be used by f to throw an exception. The second parameter passed into f is the current key. The third parameter passed into f is the current value. The fourth parameter passed into f is the client data which is where the result of the fold should be accumulated.

f must return true after each iteration in order for iteration to continue.

Parameters

[in,out]	cex	c-style exception
[in]	trie	`cgul_trie` instance
[in]	f	combining function
[in]	data	client data passed to `f`

§ cgul_trie__traverse()

CGUL_EXPORT void cgul_trie__traverse	(	cgul_exception_t *	cex,
		cgul_trie_t	trie,
		cgul_trie__traverse_t	f,
		void *	data
	)

Traverse all nodes passing each node to the function f.

The first parameter passed into f is the standard c-style exception parameter. It can be used by f to throw an exception. The second parameter passed into f is the trie trie. The third paramenter passed into f is the node for this iteration. The fourth parameter passed into f is the client data data.

f is provided with a safe context in which it can remove the node that is passed into f by calling cgul_trie__remove_node().

f must return true after each iteration in order for the traversal to continue.

NOTE: It is not strictly necessary that you use cgul_trie__traverse() or cgul_trie__traverse_range() in order to iterate over the trie elements. In fact, I would recommend that you use cgul_trie_node__get_next() for most of your iteration needs. If you need to remove nodes though, you should probably use this method. If you look at this method's source however, you will see that the cgul_trie_node class provides all the public methods you need to safely remove nodes while you are iterating over the trie, but you do have to be careful.

Parameters

[in,out]	cex	c-style exception
[in]	trie	`cgul_trie` instance
[in]	f	traversal callback function
[in]	data	passed to `f`

§ cgul_trie__traverse_range()

CGUL_EXPORT void cgul_trie__traverse_range	(	cgul_exception_t *	cex,
		cgul_trie_t	trie,
		cgul_trie_node_t	first,
		cgul_trie_node_t	last,
		cgul_trie__traverse_t	f,
		void *	data
	)

Traverse all nodes starting with first (inclusive) and ending with last (inclusive) passing each node to the function f. If you know the first node, but are not sure of the last node, just use NULL as the last node. This will cause this method to iterate until it reaches the end of the trie. You can than have f return 0 when it determines that the last node has been reached.

The first parameter passed into f is the standard c-style exception parameter. It can be used by f to throw an exception. The second parameter passed into f is the trie trie. The third paramenter passed into f is the node for this iteration. The fourth parameter passed into f is the client data data.

f is provided with a safe context in which it can remove the node that is passed into f by calling cgul_trie__remove_node().

f must return true after each iteration in order for the traversal to continue.

If first is NULL, iteration starts at the beginning of the trie. If last is NULL, iteration stops at the end of the trie.

NOTE: It is not strictly necessary that you use cgul_trie__traverse() or cgul_trie__traverse_range() in order to iterate over the trie elements. In fact, I would recommend that you use cgul_trie_node__get_next() for most of your iteration needs. If you need to remove nodes though, you should probably use this method. If you look at this method's source however, you will see that the cgul_trie_node class provides all the public methods you need to safely remove nodes while you are iterating over the trie, but you do have to be careful.

Parameters

[in,out]	cex	c-style exception
[in]	trie	`cgul_trie` instance
[in]	first	first node in range
[in]	last	last node in range
[in]	f	traversal callback function
[in]	data	client data passed to `f`

See also: cgul_trie__traverse

Typedefs

Functions

Detailed Description

Typedef Documentation

§ cgul_trie_t

§ cgul_trie__fold_key_t

§ cgul_trie__fold_value_t

§ cgul_trie__fold_pair_t

§ cgul_trie__traverse_t

Function Documentation

§ cgul_trie__new()

§ cgul_trie__new_with_indexing()

§ cgul_trie__delete()

§ cgul_trie__free_keys()

§ cgul_trie__free_values()

§ cgul_trie__get_cache_size()

§ cgul_trie__set_cache_size()

§ cgul_trie__get_cache_reserve()

§ cgul_trie__set_cache_reserve()

§ cgul_trie__is_empty()

§ cgul_trie__balance()

§ cgul_trie__insert()

§ cgul_trie__insert_from_arrays()

§ cgul_trie__find()

§ cgul_trie__find_at()

§ cgul_trie__find_rank()

§ cgul_trie__find_floor()

§ cgul_trie__find_ceiling()

§ cgul_trie__find_closed_range_by_prefix()

§ cgul_trie__find_half_opened_range_by_prefix()

§ cgul_trie__find_keys_by_prefix()

§ cgul_trie__find_values_by_prefix()

§ cgul_trie__find_nodes_by_prefix()

§ cgul_trie__find_longest_prefix_of()

§ cgul_trie__get_front()

§ cgul_trie__get_back()

§ cgul_trie__get_oldest()

§ cgul_trie__set_oldest()

§ cgul_trie__get_youngest()

§ cgul_trie__set_youngest()

§ cgul_trie__remove()

§ cgul_trie__remove_node()

§ cgul_trie__remove_at()

§ cgul_trie__remove_front()

§ cgul_trie__remove_back()

§ cgul_trie__remove_range()

§ cgul_trie__clear()

§ cgul_trie__get_size()

§ cgul_trie__swap()

§ cgul_trie__foldl_keys()

§ cgul_trie__foldr_keys()

§ cgul_trie__foldl_values()

§ cgul_trie__foldr_values()

§ cgul_trie__foldl_pairs()

§ cgul_trie__foldr_pairs()

§ cgul_trie__traverse()

§ cgul_trie__traverse_range()