C++ bindings for cgul_trie More...

#include <cgul_trie_cxx.h>

Collaboration diagram for cgul_trie_cxx:

Public Types
typedef int(*	fold_key_t) (const char key, void data)

typedef int(*	fold_value_t) (void value, void data)

typedef int(*	fold_pair_t) (const char key, void value, void *data)

typedef int(*	traverse_t) (cgul_trie_cxx trie, cgul_trie_node_cxx node, void *data)

Public Member Functions
	cgul_trie_cxx (int with_indexing=0)

	cgul_trie_cxx (cgul_trie_t rhs)

virtual	~cgul_trie_cxx ()

virtual void	free_keys ()

virtual void	free_values ()

virtual unsigned long int	get_cache_size () const

virtual void	set_cache_size (unsigned long int size)

virtual unsigned long int	get_cache_reserve () const

virtual void	set_cache_reserve (unsigned long int reserve)

virtual int	is_empty () const

virtual void	balance (int maintain_relative_ages)

virtual int	insert (const char key, cgul_trie_node_cxx *n)

virtual unsigned long int	insert_from_arrays (const char keys, void values, unsigned long int kv_size, int maintain_relative_ages)

virtual cgul_trie_node_cxx *	find (const char *key)

virtual cgul_trie_node_cxx *	find_at (unsigned long int index)

virtual int	find_rank (const char key, unsigned long int rank)

virtual cgul_trie_node_cxx *	find_floor (const char *search_key)

virtual cgul_trie_node_cxx *	find_ceiling (const char *search_key)

virtual int	find_closed_range_by_prefix (const char prefix, cgul_trie_node_cxx begin_node, cgul_trie_node_cxx *end_node)

virtual int	find_half_opened_range_by_prefix (const char prefix, cgul_trie_node_cxx begin_node, cgul_trie_node_cxx *end_node)

virtual int	find_keys_by_prefix (const char prefix, const char *keys, unsigned long int keys_size)

virtual int	find_values_by_prefix (const char prefix, void *values, unsigned long int values_size)

virtual int	find_nodes_by_prefix (const char prefix, cgul_trie_node_cxx *nodes, unsigned long int nodes_size)

virtual const char *	find_longest_prefix_of (const char *complete_string)

virtual cgul_trie_node_cxx *	get_front () const

virtual cgul_trie_node_cxx *	get_back () const

virtual cgul_trie_node_cxx *	get_oldest () const

virtual void	set_oldest (cgul_trie_node_cxx *n)

virtual cgul_trie_node_cxx *	get_youngest () const

virtual void	set_youngest (cgul_trie_node_cxx *n)

virtual int	remove (const char key_in, char key_out, void *value_out)

virtual void	remove_node (cgul_trie_node_cxx n, char key_out, void *value_out)

virtual int	remove_at (unsigned long int index, char key_out, void value_out)

virtual int	remove_front (char key_out, void value_out)

virtual int	remove_back (char key_out, void value_out)

virtual int	remove_range (cgul_trie_node_cxx first, cgul_trie_node_cxx last, cgul_cache_cxx keys_cache=NULL, cgul_cache_cxx values_cache=NULL)

virtual void	clear (cgul_cache_cxx keys_cache, cgul_cache_cxx values_cache)

virtual unsigned long int	get_size () const

virtual void	swap (cgul_trie_cxx &rhs)

virtual void	foldl_keys (fold_key_t f, void *data)

virtual void	foldr_keys (fold_key_t f, void *data)

virtual void	foldl_values (fold_value_t f, void *data)

virtual void	foldr_values (fold_value_t f, void *data)

virtual void	foldl_pairs (fold_pair_t f, void *data)

virtual void	foldr_pairs (fold_pair_t f, void *data)

virtual void	traverse (traverse_t f, void *data)

virtual void	traverse_range (cgul_trie_node_cxx first, cgul_trie_node_cxx last, traverse_t f, void *data)

virtual cgul_trie_t	get_obj () const

virtual cgul_trie_t	take_obj ()

virtual void	set_obj (cgul_trie_t rhs)

Detailed Description

This class provides the C++ bindings for C cgul_trie objects. The main purpose of this class is to convert the C-style function calls and exception handling in cgul_trie into C++-style function calls and exception handling.

See also: cgul_trie_t

Member Typedef Documentation

§ fold_key_t

typedef int(* cgul_trie_cxx::fold_key_t) (const char *key, void *data)

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

    foldl_keys()
    foldr_keys()

Parameters

[in]	key	key
[in]	data	client data

Returns: whether to continue

§ fold_value_t

typedef int(* cgul_trie_cxx::fold_value_t) (void *value, void *data)

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

    foldl_values()
    foldr_values()

Parameters

[in]	value	value
[in]	data	client data

Returns: whether to continue

§ fold_pair_t

typedef int(* cgul_trie_cxx::fold_pair_t) (const char *key, void *value, void *data)

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

    foldl_pairs()
    foldr_pairs()

Parameters

[in]	key	key
[in]	value	value
[in]	data	client data

Returns: whether to continue

§ traverse_t

typedef int(* cgul_trie_cxx::traverse_t) (cgul_trie_cxx *trie, cgul_trie_node_cxx *node, void *data)

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

    traverse()
    traverse_range()

Parameters

[in]	trie	trie
[in]	node	node
[in]	data	client data

Returns: whether to continue

Constructor & Destructor Documentation

§ cgul_trie_cxx() [1/2]

cgul_trie_cxx::cgul_trie_cxx ( int with_indexing = 0 )

inline

Create a new cgul_trie_cxx object. The caller is responsible for freeing the object by arranging for delete to be called. If memory cannot be allocated, an exception is thrown.

Be default with_indexing is false which means the ability to index into the trie as though it were an array will not be enabled. If with_indexing is set to true, each node will be larger containing three extra unsigned long values and will run about 15% slower.

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_cxx. The traverse() method can be used to remove each node safely before calling delete on the object created.

Parameters

[in] with_indexing whether to enable indexing

References cgul_trie__new(), and cgul_trie__new_with_indexing().

Referenced by set_obj().

§ cgul_trie_cxx() [2/2]

cgul_trie_cxx::cgul_trie_cxx ( cgul_trie_t rhs )

inline

Create a new cgul_trie_cxx object by wrapping an existing cgul_trie object.

Parameters

[in] rhs right-hand side

§ ~cgul_trie_cxx()

virtual cgul_trie_cxx::~cgul_trie_cxx ( )

inlinevirtual

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 clear() before calling this method in order to properly put the keys and values back on their respective cgul_cache_cxx objects (if cgul_cache_cxx objects are being used) before you delete the trie. If cgul_cache_cxx objects are not being used, the client needs to arrange some other mechanism to free the keys or values.

See also: free_keys(); free_values()

References cgul_trie__delete().

Member Function Documentation

§ free_keys()

virtual void cgul_trie_cxx::free_keys ( )

inlinevirtual

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 delete because it otherwise invalidates the trie.

References cgul_trie__free_keys().

§ free_values()

virtual void cgul_trie_cxx::free_values ( )

inlinevirtual

This method calls free() on all the values in the 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 delete because it otherwise invalidates the trie.

References cgul_trie__free_values().

§ get_cache_size()

virtual unsigned long int cgul_trie_cxx::get_cache_size ( ) const

inlinevirtual

Get the size of the cache of nodes.

Returns: size of the cache of nodes

References cgul_trie__get_cache_size().

§ set_cache_size()

virtual void cgul_trie_cxx::set_cache_size ( unsigned long int size )

inlinevirtual

Set the size of the cache of nodes.

For efficiency, the cgul_trie_cxx object 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] size of the cache of nodes

References cgul_trie__set_cache_size().

§ get_cache_reserve()

virtual unsigned long int cgul_trie_cxx::get_cache_reserve ( ) const

inlinevirtual

Get the reserve limit of the cache of nodes.

Returns: reserve limit of the cache of nodes

References cgul_trie__get_cache_reserve().

§ set_cache_reserve()

virtual void cgul_trie_cxx::set_cache_reserve ( unsigned long int reserve )

inlinevirtual

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 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 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_cxx 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] reserve of the cache of nodes

See also: cgul_cache_cxx::set_reserve()

References cgul_trie__set_cache_reserve().

§ is_empty()

virtual int cgul_trie_cxx::is_empty ( ) const

inlinevirtual

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

Returns: whether the trie is empty

References cgul_trie__is_empty().

§ balance()

virtual void cgul_trie_cxx::balance ( int maintain_relative_ages )

inlinevirtual

Balance the 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 insert_from_arrays().)

Parameters

[in] maintain_relative_ages whether to maintain relative node ages

See also: insert_from_arrays()

References cgul_trie__balance().

§ insert()

virtual int cgul_trie_cxx::insert	(	const char *	key,
		cgul_trie_node_cxx **	n
	)

inlinevirtual

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_cxx::get_value() or cgul_trie_node_cxx::set_value() to get or set the value indexed by "key".

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

    cgul_string_cxx word;
    cgul_trie_node_cxx* n = NULL;

    if (trie->insert(word.get_value(), &n)) {
        word.take_value();
        . . .
    } 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]	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: balance(); insert_from_arrays()

References cgul_trie__insert().

§ insert_from_arrays()

virtual unsigned long int cgul_trie_cxx::insert_from_arrays	(	const char **	keys,
		void **	values,
		unsigned long int	kv_size,
		int	maintain_relative_ages
	)

inlinevirtual

Insert into the 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]	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()

References cgul_trie__insert_from_arrays().

§ find()

virtual cgul_trie_node_cxx* cgul_trie_cxx::find ( const char * key )

inlinevirtual

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] key key

Returns: node associated with the key or NULL

References cgul_trie__find().

§ find_at()

virtual cgul_trie_node_cxx* cgul_trie_cxx::find_at ( unsigned long int index )

inlinevirtual

Find the node indexed by position. This lets you use a cgul_trie_cxx instances like you would an array. Even in the best-case scenario where indexing into cgul_trie_cxx 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 the trie was not created with indexing enabled.

Parameters

[in] index index into sorted keys of node to return

Returns: node associated with index

See also: find_rank()

References cgul_trie__find_at().

§ find_rank()

virtual int cgul_trie_cxx::find_rank	(	const char *	key,
		unsigned long int *	rank
	)

inlinevirtual

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 find_at() in order to lookup key by index.

This method throws an exception if trie was not created with indexing enabled.

Parameters

[in]	key	key
[out]	rank	rank of key

Returns: whether the key exists in the trie

See also: find_at()

References cgul_trie__find_rank().

§ find_floor()

virtual cgul_trie_node_cxx* cgul_trie_cxx::find_floor ( const char * search_key )

inlinevirtual

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] search_key search key

Returns: floor node or NULL

References cgul_trie__find_floor().

§ find_ceiling()

virtual cgul_trie_node_cxx* cgul_trie_cxx::find_ceiling ( const char * search_key )

inlinevirtual

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] search_key search key

Returns: ceiling node or NULL

References cgul_trie__find_ceiling().

§ find_closed_range_by_prefix()

virtual int cgul_trie_cxx::find_closed_range_by_prefix	(	const char *	prefix,
		cgul_trie_node_cxx **	begin_node,
		cgul_trie_node_cxx **	end_node
	)

inlinevirtual

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 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]	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: find_half_opened_range_by_prefix()

References cgul_trie__find_closed_range_by_prefix().

§ find_half_opened_range_by_prefix()

virtual int cgul_trie_cxx::find_half_opened_range_by_prefix	(	const char *	prefix,
		cgul_trie_node_cxx **	begin_node,
		cgul_trie_node_cxx **	end_node
	)

inlinevirtual

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 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]	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: find_closed_range_by_prefix()

References cgul_trie__find_half_opened_range_by_prefix().

§ find_keys_by_prefix()

virtual int cgul_trie_cxx::find_keys_by_prefix	(	const char *	prefix,
		const char ***	keys,
		unsigned long int *	keys_size
	)

inlinevirtual

All keys in the 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_trie_cxx& trie,
                          const char* prefix)
     {
         unsigned long int i = 0;
         const char** keys = NULL;
         unsigned long int keys_size = 0;

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

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

Parameters

[in]	prefix	prefix
[out]	keys	keys found by prefix
[out]	keys_size	number of keys found

Returns: whether any keys were found

See also: find_nodes_by_prefix(); find_closed_range_by_prefix(); find_half_opened_range_by_prefix()

References cgul_trie__find_keys_by_prefix().

§ find_values_by_prefix()

virtual int cgul_trie_cxx::find_values_by_prefix	(	const char *	prefix,
		void ***	values,
		unsigned long int *	values_size
	)

inlinevirtual

All values in the 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_cxx::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_trie_cxx& trie,
                            const char* prefix)
     {
         unsigned long int i = 0;
         void** values = NULL;
         unsigned long int values_size = 0;

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

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

Parameters

[in]	prefix	prefix
[out]	values	values found by prefix
[out]	values_size	number of values found

Returns: whether any values were found

See also: find_nodes_by_prefix(); find_closed_range_by_prefix(); find_half_opened_range_by_prefix()

References cgul_trie__find_values_by_prefix().

§ find_nodes_by_prefix()

virtual int cgul_trie_cxx::find_nodes_by_prefix	(	const char *	prefix,
		cgul_trie_node_cxx ***	nodes,
		unsigned long int *	nodes_size
	)

inlinevirtual

All nodes in the 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_cxx::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_trie_cxx& trie,
                           const char* prefix)
     {
         unsigned long int i = 0;
         const char* key = NULL;
         void* value = NULL;
         cgul_trie_node_cxx** nodes = NULL;
         unsigned long int nodes_size = 0;

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

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

Parameters

[in]	prefix	prefix
[out]	nodes	nodes found by prefix
[out]	nodes_size	number of nodes found

Returns: whether any nodes were found

See also: find_closed_range_by_prefix(); find_half_opened_range_by_prefix()

References cgul_trie__find_nodes_by_prefix().

§ find_longest_prefix_of()

virtual const char* cgul_trie_cxx::find_longest_prefix_of ( const char * complete_string )

inlinevirtual

Return the key in the 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] complete_string complete string

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

References cgul_trie__find_longest_prefix_of().

§ get_front()

virtual cgul_trie_node_cxx* cgul_trie_cxx::get_front ( ) const

inlinevirtual

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_cxx* n = trie->get_front();
    for ( ; n ; n = n->get_next()) {
        ...
    }

Returns: front node

References cgul_trie__get_front().

§ get_back()

virtual cgul_trie_node_cxx* cgul_trie_cxx::get_back ( ) const

inlinevirtual

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_cxx* n = trie->get_back();
    for ( ; n ; n = n->get_prev()) {
        ...
    }

Returns: back node

References cgul_trie__get_back().

§ get_oldest()

virtual cgul_trie_node_cxx* cgul_trie_cxx::get_oldest ( ) const

inlinevirtual

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_cxx* n = trie->get_oldest();
    for ( ; n ; n = n->get_younger()) {
        ...
    }

Returns: oldest node

See also: cgul_trie_node_cxx::get_younger()

References cgul_trie__get_oldest().

§ set_oldest()

virtual void cgul_trie_cxx::set_oldest ( cgul_trie_node_cxx * n )

inlinevirtual

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 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] n node

See also: set_youngest()

References cgul_trie__set_oldest().

§ get_youngest()

virtual cgul_trie_node_cxx* cgul_trie_cxx::get_youngest ( ) const

inlinevirtual

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_cxx* n = trie->get_youngest();
    for ( ; n ; n = n->get_older()) {
        ...
    }

Returns: youngest node

See also: cgul_trie_node_cxx::get_older()

References cgul_trie__get_youngest().

§ set_youngest()

virtual void cgul_trie_cxx::set_youngest ( cgul_trie_node_cxx * n )

inlinevirtual

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

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

Parameters

[in] n node

See also: set_oldest()

References cgul_trie__set_youngest().

§ remove()

virtual int cgul_trie_cxx::remove	(	const char *	key_in,
		char **	key_out,
		void **	value_out
	)

inlinevirtual

Remove the node in the 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 remove_node() for details.

Parameters

[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

References cgul_trie__remove().

§ remove_node()

virtual void cgul_trie_cxx::remove_node	(	cgul_trie_node_cxx *	n,
		char **	key_out,
		void **	value_out
	)

inlinevirtual

Remove node from the 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_cxx::get_next() afterward. The solution is simple. Just call cgul_trie_node_cxx::get_next() before calling this method:

    for (curr = trie->find(key) ; curr ; curr = next) {
        next = curr->get_next();
        trie->remove_node(curr, &key_out, &value_out);
        free(key_out);
        free(value_out);
    }

Alternatively, you can use remove_range(), traverse(), or traverse_range().

Parameters

[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

References cgul_trie__remove_node().

§ remove_at()

virtual int cgul_trie_cxx::remove_at	(	unsigned long int	index,
		char **	key_out,
		void **	value_out
	)

inlinevirtual

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 the trie was not created with indexing enabled.

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

Parameters

[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

References cgul_trie__remove_at().

§ remove_front()

virtual int cgul_trie_cxx::remove_front	(	char **	key_out,
		void **	value_out
	)

inlinevirtual

Remove the first key/value pair as determined by sort order from the 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

[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

References cgul_trie__remove_front().

§ remove_back()

virtual int cgul_trie_cxx::remove_back	(	char **	key_out,
		void **	value_out
	)

inlinevirtual

Remove the last key/value pair as determined by sort order from the 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

[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

References cgul_trie__remove_back().

§ remove_range()

virtual int cgul_trie_cxx::remove_range	(	cgul_trie_node_cxx *	first,
		cgul_trie_node_cxx *	last,
		cgul_cache_cxx *	keys_cache = `NULL`,
		cgul_cache_cxx *	values_cache = `NULL`
	)

inlinevirtual

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]	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_cxx::get_freer()

References cgul_trie__remove_range().

§ clear()

virtual void cgul_trie_cxx::clear	(	cgul_cache_cxx *	keys_cache,
		cgul_cache_cxx *	values_cache
	)

inlinevirtual

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]	keys_cache	keys cache
[in]	values_cache	values cache

See also: remove_range; cgul_cache_cxx::get_freer()

References cgul_trie__clear(), and cgul_cache_cxx::get_obj().

§ get_size()

virtual unsigned long int cgul_trie_cxx::get_size ( ) const

inlinevirtual

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

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

References cgul_trie__get_size().

§ swap()

virtual void cgul_trie_cxx::swap ( cgul_trie_cxx & rhs )

inlinevirtual

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

Parameters

[in] rhs right-hand side

References cgul_trie__swap().

§ foldl_keys()

virtual void cgul_trie_cxx::foldl_keys	(	fold_key_t	f,
		void *	data
	)

inlinevirtual

This method performs a left fold of the 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 current key. The second 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]	f	combining function
[in]	data	client data passed to `f`

References cgul_trie__get_front(), cgul_trie_node__get_key(), and cgul_trie_node__get_next().

§ foldr_keys()

virtual void cgul_trie_cxx::foldr_keys	(	fold_key_t	f,
		void *	data
	)

inlinevirtual

This method performs a right fold of the 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 current key. The second 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]	f	combining function
[in]	data	client data passed to `f`

References cgul_trie__get_back(), cgul_trie_node__get_key(), and cgul_trie_node__get_prev().

§ foldl_values()

virtual void cgul_trie_cxx::foldl_values	(	fold_value_t	f,
		void *	data
	)

inlinevirtual

This method performs a left fold of the 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 current value. The second 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]	f	combining function
[in]	data	client data passed to `f`

References cgul_trie__get_front(), cgul_trie_node__get_next(), and cgul_trie_node__get_value().

§ foldr_values()

virtual void cgul_trie_cxx::foldr_values	(	fold_value_t	f,
		void *	data
	)

inlinevirtual

This method performs a right fold of the 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 current value. The second 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]	f	combining function
[in]	data	client data passed to `f`

References cgul_trie__get_back(), cgul_trie_node__get_prev(), and cgul_trie_node__get_value().

§ foldl_pairs()

virtual void cgul_trie_cxx::foldl_pairs	(	fold_pair_t	f,
		void *	data
	)

inlinevirtual

This method performs a left fold of the 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 current key. 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]	f	combining function
[in]	data	client data passed to `f`

References cgul_trie__get_front(), cgul_trie_node__get_key(), cgul_trie_node__get_next(), and cgul_trie_node__get_value().

§ foldr_pairs()

virtual void cgul_trie_cxx::foldr_pairs	(	fold_pair_t	f,
		void *	data
	)

inlinevirtual

This method performs a right fold of the 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 current key. 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]	f	combining function
[in]	data	client data passed to `f`

References cgul_trie__get_back(), cgul_trie_node__get_key(), cgul_trie_node__get_prev(), and cgul_trie_node__get_value().

§ traverse()

virtual void cgul_trie_cxx::traverse	(	traverse_t	f,
		void *	data
	)

inlinevirtual

Traverse all nodes passing each node to the function f.

The first parameter passed into f is the trie this. The second paramenter passed into f is the node for this iteration. The third 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 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 traverse() or traverse_range() in order to iterate over the trie elements. In fact, I would recommend that you use cgul_trie_node_cxx::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_cxx 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]	f	traversal callback function
[in]	data	client data passed to `f`

See also: traverse_range()

References traverse_range().

§ traverse_range()

virtual void cgul_trie_cxx::traverse_range	(	cgul_trie_node_cxx *	first,
		cgul_trie_node_cxx *	last,
		traverse_t	f,
		void *	data
	)

inlinevirtual

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 trie this. The second paramenter passed into f is the node for this iteration. The third 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 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 traverse() or traverse_range() in order to iterate over the trie elements. In fact, I would recommend that you use cgul_trie_node_cxx::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_cxx 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]	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: traverse()

References cgul_trie__get_back(), cgul_trie__get_front(), and cgul_trie_node__get_next().

Referenced by traverse().

§ get_obj()

virtual cgul_trie_t cgul_trie_cxx::get_obj ( ) const

inlinevirtual

Get the underlying cgul_trie object.

Returns: underlying object

§ take_obj()

virtual cgul_trie_t cgul_trie_cxx::take_obj ( )

inlinevirtual

Take the underlying cgul_trie object. This means the underlying object will not be deleted when the wrapper goes out of scope. Also, because you have taken the underlying object, no other methods should be called on this wrapper's instance. Lastly, after taking the underlying object, it is the caller's responsibility to delete the underlying object by calling cgul_trie__delete().

Returns: underlying object

§ set_obj()

virtual void cgul_trie_cxx::set_obj ( cgul_trie_t rhs )

inlinevirtual

Set the new underlying object to rhs. This causes the old underlying object to be deleted which invalidates any outstanding pointers to or iterators for the old underlying object.

This instance takes ownership of rhs which means rhs will be automatically deleted when the C++ wrapper is deleted. To prevent automatic deletion of rhs, call take_obj() when the C++ wrapper is no longer needed.

Parameters

[in] rhs right-hand side

References cgul_trie__delete(), and cgul_trie_cxx().

The documentation for this class was generated from the following file:

cgul_trie_cxx.h

Public Types

Public Member Functions

Detailed Description

Member Typedef Documentation

§ fold_key_t

§ fold_value_t

§ fold_pair_t

§ traverse_t

Constructor & Destructor Documentation

§ cgul_trie_cxx() [1/2]

§ cgul_trie_cxx() [2/2]

§ ~cgul_trie_cxx()

Member Function Documentation

§ free_keys()

§ free_values()

§ get_cache_size()

§ set_cache_size()

§ get_cache_reserve()

§ set_cache_reserve()

§ is_empty()

§ balance()

§ insert()

§ insert_from_arrays()

§ find()

§ find_at()

§ find_rank()

§ find_floor()

§ find_ceiling()

§ find_closed_range_by_prefix()

§ find_half_opened_range_by_prefix()

§ find_keys_by_prefix()

§ find_values_by_prefix()

§ find_nodes_by_prefix()

§ find_longest_prefix_of()

§ get_front()

§ get_back()

§ get_oldest()

§ set_oldest()

§ get_youngest()

§ set_youngest()

§ remove()

§ remove_node()

§ remove_at()

§ remove_front()

§ remove_back()

§ remove_range()

§ clear()

§ get_size()

§ swap()

§ foldl_keys()

§ foldr_keys()

§ foldl_values()

§ foldr_values()

§ foldl_pairs()

§ foldr_pairs()

§ traverse()

§ traverse_range()

§ get_obj()

§ take_obj()

§ set_obj()