C++ bindings for cgul_multimap More...

#include <cgul_multimap_cxx.h>

Collaboration diagram for cgul_multimap_cxx:

Public Types
typedef cgul_multimap__compare_t	compare_t

typedef int(*	fold_key_t) (const void key, void data)

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

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

typedef int(*	traverse_t) (cgul_multimap_cxx mm, cgul_multimap_node_cxx n, void *data)

Public Member Functions
	cgul_multimap_cxx (compare_t compare)

	cgul_multimap_cxx (cgul_multimap_t rhs)

virtual	~cgul_multimap_cxx ()

virtual void	free_keys ()

virtual void	free_values ()

virtual int	is_empty () const

virtual unsigned long int	insert (void key, void value, cgul_multimap_node_cxx **node=NULL)

virtual unsigned long int	insert_with_hint (void key, void value, cgul_multimap_node_cxx hint, cgul_multimap_node_cxx *node=NULL)

virtual unsigned long int	find (void key, int older_is_greater, cgul_multimap_node_cxx *node)

virtual unsigned long int	find_floor (void search_key, int older_is_greater, cgul_multimap_node_cxx *node)

virtual unsigned long int	find_ceiling (void search_key, int older_is_greater, cgul_multimap_node_cxx *node)

virtual int	remove (void key, cgul_cache_cxx keys_cache=NULL, cgul_cache_cxx *values_cache=NULL)

virtual unsigned long int	remove_node (cgul_multimap_node_cxx node, void key_out=NULL, void *value_out=NULL)

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

virtual int	remove_front (int older_is_greater, void key_out, void value_out)

virtual int	remove_back (int older_is_greater, void key_out, void value_out)

virtual cgul_multimap_node_cxx *	get_front (int older_is_greater) const

virtual cgul_multimap_node_cxx *	get_back (int older_is_greater) const

virtual cgul_multimap_node_cxx *	get_oldest () const

virtual void	set_oldest (cgul_multimap_node_cxx *n)

virtual cgul_multimap_node_cxx *	get_youngest () const

virtual void	set_youngest (cgul_multimap_node_cxx *n)

virtual void	clear (cgul_cache_cxx keys_cache=NULL, cgul_cache_cxx values_cache=NULL)

virtual unsigned long int	get_size () const

virtual void	swap (cgul_multimap_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 (int older_is_greater, fold_value_t f, void *data)

virtual void	foldr_values (int older_is_greater, fold_value_t f, void *data)

virtual void	foldl_pairs (int older_is_greater, fold_pair_t f, void *data)

virtual void	foldr_pairs (int older_is_greater, fold_pair_t f, void *data)

virtual void	traverse (int older_is_greater, traverse_t f, void *data)

virtual void	traverse_range (cgul_multimap_node_cxx first, cgul_multimap_node_cxx last, int older_is_greater, traverse_t f, void *data)

virtual cgul_multimap_t	get_obj () const

virtual cgul_multimap_t	take_obj ()

virtual void	set_obj (cgul_multimap_t rhs)

Detailed Description

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

See also: cgul_multimap_t

Member Typedef Documentation

§ compare_t

typedef cgul_multimap__compare_t cgul_multimap_cxx::compare_t

This typedef is the interface the client must define in order for cgul_multimap_cxx to sort your keys as they are inserted.

Arguably, this typedef should be an abstract base class, a pure virtual method, or something that is the functional equivalent of Java's "interface" keyword, but it doesn't really buy anything except added complexity.

§ fold_key_t

typedef int(* cgul_multimap_cxx::fold_key_t) (const void *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_multimap_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_multimap_cxx::fold_pair_t) (const void *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_multimap_cxx::traverse_t) (cgul_multimap_cxx *mm, cgul_multimap_node_cxx *n, void *data)

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

    traverse()
    traverse_range()

Parameters

[in]	mm	multimap
[in]	n	node
[in]	data	client data

Returns: whether to continue

Constructor & Destructor Documentation

§ cgul_multimap_cxx() [1/2]

cgul_multimap_cxx::cgul_multimap_cxx ( compare_t compare )

inline

Create a new cgul_multimap object. compare is the comparison function that allows the container to maintain its sorted order. If memory cannot be allocated, NULL is returned, and an exception is thrown.

The client is responsible for deleting the object. Also, the client is responsible for freeing the key/value pairs only after their nodes have been permanently removed from the cgul_multimap. The traverse() method can be used to remove each node safely before deleting the object.

Parameters

[in] compare comparison function

See also: compare_t

References cgul_multimap__new().

§ cgul_multimap_cxx() [2/2]

cgul_multimap_cxx::cgul_multimap_cxx ( cgul_multimap_t rhs )

inline

Create a new cgul_multimap_cxx object by wrapping an existing cgul_multimap object.

Parameters

[in] rhs right-hand side

§ ~cgul_multimap_cxx()

virtual cgul_multimap_cxx::~cgul_multimap_cxx ( )

inlinevirtual

This method frees all internally allocated memory. This does not include the key/value pairs stored in the multimap. 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 multimap. 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_multimap__delete().

Member Function Documentation

§ free_keys()

virtual void cgul_multimap_cxx::free_keys ( )

inlinevirtual

This method calls free() on all the keys in the multimap. 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 multimap.

References cgul_multimap__free_keys().

§ free_values()

virtual void cgul_multimap_cxx::free_values ( )

inlinevirtual

This method calls free() on all the values in the multimap. 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 multimap.

References cgul_multimap__free_values().

§ is_empty()

virtual int cgul_multimap_cxx::is_empty ( ) const

inlinevirtual

Whether the multimap is empty.

Returns: whether the multimap mm is empty

References cgul_multimap__is_empty().

§ insert()

virtual unsigned long int cgul_multimap_cxx::insert	(	void *	key,
		void *	value,
		cgul_multimap_node_cxx **	node = `NULL`
	)

inlinevirtual

Insert the (key, value) pair into the multimap. If node is not NULL, it will hold the newly inserted node upon completion. The return value is the count of how many values in the multimap are now associated with key. If an error occurs, an exception is thrown.

It is important to understand that this class (like all containers in the cgul library) do not take ownership of key or value. It also does not attempt to make a copy of the thing pointed to by key or value. This gives the user complete control over the lifetime of these objects 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.

Most containers in the cgul library, map one key to one value. This class is different. It maps one key to many values. Thus, this class really only needs one instance of the key even though the insert method is called many times, and in fact, this class only keeps the first instance of key that is inserted. Thus, it is important to check the value returned by this method to determine when to free your keys.

For example, if you use malloc() to dynamically allocate a new key every time this method is called, the key should probably be freed for all but the first insert:

    if (mm->insert(key, value, &node) > 1) {
        free(key);
    }

Parameters

[in]	key	key
[in]	value	value
[out]	node	newly inserted node

Returns: count of values now associated with key

References cgul_multimap__insert().

§ insert_with_hint()

virtual unsigned long int cgul_multimap_cxx::insert_with_hint	(	void *	key,
		void *	value,
		cgul_multimap_node_cxx *	hint,
		cgul_multimap_node_cxx **	node = `NULL`
	)

inlinevirtual

This method works the same as insert() except if hint is not NULL it calls the comparison function (passed into the constructor) to determine if key is equal to the key for hint. If so, the insertion can occur in constant time instead of logarithmic time because hint already holds a back reference to the underlying node for key.

If hint is NULL or key does not equal the key for hint, this method simply forwards the request to insert(), and the insertion occurs in logarithmic time.

Parameters

[in]	key	key
[in]	value	value
[in]	hint	hint
[out]	node	newly inserted node

Returns: count of values now associated with key

References cgul_multimap__insert_with_hint().

§ find()

virtual unsigned long int cgul_multimap_cxx::find	(	void *	key,
		int	older_is_greater,
		cgul_multimap_node_cxx **	node
	)

inlinevirtual

This method finds the smallest node associated with key in the multimap and returns it in node. The return value of this method is the total number of values associated with key. If key cannot be found, node will be set to NULL, and 0 will be returned.

The caller can use the return value to iterate over all the values associated with key. For example, the following shows how to iterate over all the values associated with key in the order in which they were inserted:

    count = mm->find(key, 0, &node);
    for (i = 0 ; i < count ; ++i) {
        ...
        node = node->get_next(0);
    }

The primary sort criterion is the user's compare function, of course, but the older_is_greater boolean is used as a secondary sort criterion. When a key maps to many values, the older_is_greater boolean determines how to sort the older nodes relative to the newer nodes.

Parameters

[in]	key	key
[in]	older_is_greater	whether older nodes are greater than newer nodes
[out]	node	smallest node associated with `key`

Returns: count of values associated with key

References cgul_multimap__find().

§ find_floor()

virtual unsigned long int cgul_multimap_cxx::find_floor	(	void *	search_key,
		int	older_is_greater,
		cgul_multimap_node_cxx **	node
	)

inlinevirtual

Find the node having the largest key less than or equal to the search key search_key and return it in *node. If such a key does not exist, NULL is returned instead. This method returns the number of values that directly map to the floor.

The iterator returned in *node is for the floor key's smallest value as determined by older_is_greater such that forward iteration includes all the values for the floor node.

Parameters

[in]	search_key	search key
[in]	older_is_greater	whether older nodes are greater than newer nodes
[out]	node	floor or `NULL`

Returns: count of values associated with the floor

References cgul_multimap__find_floor().

§ find_ceiling()

virtual unsigned long int cgul_multimap_cxx::find_ceiling	(	void *	search_key,
		int	older_is_greater,
		cgul_multimap_node_cxx **	node
	)

inlinevirtual

Find the node having the smallest key greater than or equal to the search key search_key and return it in *node. If such a key does not exist, NULL is returned instead. This method returns the number of values that directly map to the ceiling.

The iterator returned in *node is for the ceiling key's largest value as determined by older_is_greater such that reverse iteration includes all the values for the ceiling node.

Parameters

[in]	search_key	search key
[in]	older_is_greater	whether older nodes are greater than newer nodes
[out]	node	ceiling or `NULL`

Returns: count of values associated with the ceiling

References cgul_multimap__find_ceiling().

§ remove()

virtual int cgul_multimap_cxx::remove	(	void *	key,
		cgul_cache_cxx *	keys_cache = `NULL`,
		cgul_cache_cxx *	values_cache = `NULL`
	)

inlinevirtual

This method removes key and all the values associated with key from the multimap and returns 1 on success. On failure, this method returns 0 which indicates that key could not be found in the multimap.

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.

If you need to remove just one value associated with key instead of all the values associated with key, use remove_node() instead.

Parameters

[in]	key	key
[in]	keys_cache	keys cache
[in]	values_cache	values cache

Returns: whether the nodes associated with key were removed

See also: cgul_cache_cxx::get_freer()

References cgul_multimap__remove().

§ remove_node()

virtual unsigned long int cgul_multimap_cxx::remove_node	(	cgul_multimap_node_cxx *	node,
		void **	key_out = `NULL`,
		void **	value_out = `NULL`
	)

inlinevirtual

Remove node from the multimap. 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, but the value for the key that is returned will be NULL if the multimap is still using the key. This method returns the number of values still associated with the same key.

Because the key in node might map to more than one value, the caller should never invalidate the key until after this method returns a count of zero or, equivalently, a value for key that is not NULL:

    mm->remove_node(node, &key, &value);
    if (key) {
        free(key);
    }
    free(value);

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

    count = mm->find(key, 1, &curr);
    if (curr) {
        for (i = 0 ; i < count ; ++i, curr = next) {
            next = curr->get_next(1);
            mm->remove_node(curr, &key_out, &value_out);
            if (key_out) {
                free(key_out);
            }
            free(value_out);
        }
    }

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

If you use one of the traversal methods, it is safe to call this method naively. For example, if your multimap stores cgul_string_cxx* objects for both its keys and values, another way to remove all the values associated with a key as follows:

    static int
    remove_node_cb(cgul_multimap_t mm,
                   cgul_multimap_node_t node,
                   void* data)
    {
        cgul_string_cxx* key = NULL;
        cgul_string_cxx* value = NULL;
        mm->remove_node(node, (void**)&key, (void**)&value);
        if (key) {
            delete key;
        }
        delete value;
        return 1;
    }

    cgul_multimap_node_cxx* first = NULL;
    cgul_multimap_node_cxx* last = NULL;
    mm->find(key, 1, &first);
    mm->find(key, 0, &last);
    if (first && last) {
        mm->traverse_range(first, last, 1, &remove_node_cb, NULL);
    }

Parameters

[in]	node	node
[out]	key_out	pointer for the key stored in the node
[out]	value_out	pointer for the value stored in the node

Returns: count of values now associated with key

References cgul_multimap__remove_node().

§ remove_range()

virtual int cgul_multimap_cxx::remove_range	(	cgul_multimap_node_cxx *	first,
		cgul_multimap_node_cxx *	last,
		int	older_is_greater,
		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.

The primary sort criterion is the user's compare function, of course, but the older_is_greater boolean is used as a secondary sort criterion. When a key maps to many values, the older_is_greater boolean determines how to sort the older nodes relative to the newer nodes.

Parameters

[in]	first	first node in range
[in]	last	last node in range
[in]	older_is_greater	whether older nodes are greater than newer nodes
[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_multimap__remove_range().

§ remove_front()

virtual int cgul_multimap_cxx::remove_front	(	int	older_is_greater,
		void **	key_out,
		void **	value_out
	)

inlinevirtual

This method removes the front node. 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. Note however that because keys map to multiple values, the key for this node may still be in use by another node. If this is the case, NULL is returned in key_out. An example of how to use this method follows:

    mm->remove_front(0, &key_out, &value_out);
    if (key_out) {
        free(key_out);
    }
    free(value_out);

The primary sort criterion is the user's compare function, of course, but the older_is_greater boolean is used as a secondary sort criterion. When a key maps to many values, the older_is_greater boolean determines how to sort the older nodes relative to the newer nodes. See get_front() for more details.

Parameters

[in]	older_is_greater	whether older nodes are greater than newer nodes
[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_multimap__remove_front().

§ remove_back()

virtual int cgul_multimap_cxx::remove_back	(	int	older_is_greater,
		void **	key_out,
		void **	value_out
	)

inlinevirtual

This method removes the back node. 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. Note however that because keys map to multiple values, the key for this node may still be in use by another node. If this is the case, NULL is returned in key_out. An example of how to use this method follows:

    mm->remove_back(1, &key_out, &value_out);
    if (key_out) {
        free(key_out);
    }
    free(value_out);

The primary sort criterion is the user's compare function, of course, but the older_is_greater boolean is used as a secondary sort criterion. When a key maps to many values, the older_is_greater boolean determines how to sort the older nodes relative to the newer nodes. See get_back() for more details.

Parameters

[in]	older_is_greater	whether older nodes are greater than newer nodes
[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_multimap__remove_back().

§ get_front()

virtual cgul_multimap_node_cxx* cgul_multimap_cxx::get_front ( int older_is_greater ) const

inlinevirtual

Return the front node according to sort order. This operation is O(1). If the multimap is empty, NULL is returned. This class does not have to search the multimap in order to find the front node because it indirectly keeps a pointer to the front node up to date.

The primary sort criterion is the user's compare function, of course, but the older_is_greater boolean is used as a secondary sort criterion. When a key maps to many values, the older_is_greater boolean determines how to sort the older nodes relative to the newer nodes.

The way the older_is_greater boolean works in this implementation is that each key maps to a linked list of values. The compare function only determines the relative order of the keys. To order the values, this implementation always pushes newer values onto the front of the list. Thus, the newest value is always at the front of the list, and the oldest value is always at the back of the list. If older_is_greater is true, the sort order is from front to back. If older_is_greater is false, the sort order is from back to front.

For example, if you use this class to implement a priority queue and want to get the node with the lowest priority that has been waiting the longest, you would call this method with older_is_greater set to 0.

Parameters

[in] older_is_greater whether older nodes are greater than newer nodes

Returns: front node

See also: get_next(); get_prev()

References cgul_multimap__get_front().

§ get_back()

virtual cgul_multimap_node_cxx* cgul_multimap_cxx::get_back ( int older_is_greater ) const

inlinevirtual

Return the back node according to sort order. This operation is O(1). If the multimap is empty, NULL is returned. This class does not have to search the multimap in order to find the back node because it indirectly keeps a pointer to the back node up to date.

The primary sort criterion is the user's compare function, of course, but the older_is_greater boolean is used as a secondary sort criterion. When a key maps to many values, the older_is_greater boolean determines how to sort the older nodes relative to the newer nodes.

The way the older_is_greater boolean works in this implementation is that each key maps to a linked list of values. The compare function only determines the relative order of the keys. To order the values, this implementation always pushes newer values onto the front of the list. Thus, the newest value is always at the front of the list, and the oldest value is always at the back of the list. If older_is_greater is true, the sort order is from front to back. If older_is_greater is false, the sort order is from back to front.

For example, if you use this class to implement a priority queue and want to get the node with the highest priority that has been waiting the longest, you would call this method with older_is_greater set to 1.

Parameters

[in] older_is_greater whether older nodes are greater than newer nodes

Returns: back node

See also: get_next(); get_prev()

References cgul_multimap__get_back().

§ get_oldest()

virtual cgul_multimap_node_cxx* cgul_multimap_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 multimap is empty, NULL is returned. This class does not have to search the multimap 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 multimap in chronological order:

    cgul_multimap_node_cxx* n = mm->get_oldest();
    for ( ; n ; n = n->get_younger()) {
        ...
    }

Returns: oldest node

See also: get_younger()

References cgul_multimap__get_oldest().

§ set_oldest()

virtual void cgul_multimap_cxx::set_oldest ( cgul_multimap_node_cxx * n )

inlinevirtual

Set the oldest node in the multimap 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 multimap, and you want to force n to be the next node to expire.

Parameters

[in] n node

See also: set_youngest()

References cgul_multimap__set_oldest().

§ get_youngest()

virtual cgul_multimap_node_cxx* cgul_multimap_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 multimap is empty, NULL is returned. This class does not have to search the multimap 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 multimap in reverse chronological order:

    cgul_multimap_node_cxx* n = mm->get_youngest();
    for ( ; n ; n = n->get_older()) {
        ...
    }

Returns: youngest node

See also: get_older()

References cgul_multimap__get_youngest().

§ set_youngest()

virtual void cgul_multimap_cxx::set_youngest ( cgul_multimap_node_cxx * n )

inlinevirtual

Set the youngest node in the multimap 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 multimap.

Parameters

[in] n node

See also: cgul_multimap__set_oldest()

References cgul_multimap__set_youngest().

§ clear()

virtual void cgul_multimap_cxx::clear	(	cgul_cache_cxx *	keys_cache = `NULL`,
		cgul_cache_cxx *	values_cache = `NULL`
	)

inlinevirtual

This method clears the multimap 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.

Another easy way to clear your multimap is to just keep removing nodes from the front of the multimap freeing the key/value pairs as you go:

    void* key = NULL;
    void* value = NULL;
    while (mm->remove_front(0, &key, &value)) {
        if (key) {
            free(key);
        }
        free(value);
    }

Parameters

[in]	keys_cache	keys cache
[in]	values_cache	values cache

See also: remove_range(); cgul_cache_cxx::get_freer()

References cgul_multimap__clear().

§ get_size()

virtual unsigned long int cgul_multimap_cxx::get_size ( ) const

inlinevirtual

Return the total number of values stored in the multimap.

Returns: size of the multimap

References cgul_multimap__get_size().

§ swap()

virtual void cgul_multimap_cxx::swap ( cgul_multimap_cxx & rhs )

inlinevirtual

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

Parameters

[in] rhs right-hand side

References cgul_multimap__swap().

§ foldl_keys()

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

inlinevirtual

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

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_multimap__get_tree(), cgul_rbtree__get_front(), cgul_rbtree_node__get_key(), and cgul_rbtree_node__get_next().

§ foldr_keys()

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

inlinevirtual

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

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_multimap__get_tree(), cgul_rbtree__get_back(), cgul_rbtree_node__get_key(), and cgul_rbtree_node__get_prev().

§ foldl_values()

virtual void cgul_multimap_cxx::foldl_values	(	int	older_is_greater,
		fold_value_t	f,
		void *	data
	)

inlinevirtual

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

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]	older_is_greater	whether older nodes are greater
[in]	f	combining function
[in]	data	client data passed to `f`

References cgul_multimap__get_front(), cgul_multimap_node__get_next(), and cgul_multimap_node__get_value().

§ foldr_values()

virtual void cgul_multimap_cxx::foldr_values	(	int	older_is_greater,
		fold_value_t	f,
		void *	data
	)

inlinevirtual

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

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]	older_is_greater	whether older nodes are greater
[in]	f	combining function
[in]	data	client data passed to `f`

References cgul_multimap__get_back(), cgul_multimap_node__get_prev(), and cgul_multimap_node__get_value().

§ foldl_pairs()

virtual void cgul_multimap_cxx::foldl_pairs	(	int	older_is_greater,
		fold_pair_t	f,
		void *	data
	)

inlinevirtual

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

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]	older_is_greater	whether older nodes are greater
[in]	f	combining function
[in]	data	client data passed to `f`

References cgul_multimap__get_front(), cgul_multimap_node__get_key(), cgul_multimap_node__get_next(), and cgul_multimap_node__get_value().

§ foldr_pairs()

virtual void cgul_multimap_cxx::foldr_pairs	(	int	older_is_greater,
		fold_pair_t	f,
		void *	data
	)

inlinevirtual

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

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]	older_is_greater	whether older nodes are greater
[in]	f	combining function
[in]	data	client data passed to `f`

References cgul_multimap__get_back(), cgul_multimap_node__get_key(), cgul_multimap_node__get_prev(), and cgul_multimap_node__get_value().

§ traverse()

virtual void cgul_multimap_cxx::traverse	(	int	older_is_greater,
		traverse_t	f,
		void *	data
	)

inlinevirtual

Traverse all nodes passing each node to the function f.

The first parameter passed into f is the multimap 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.

The primary sort criterion is the user's compare function, of course, but the older_is_greater boolean is used as a secondary sort criterion. When a key maps to many values, the older_is_greater boolean determines how to sort the older nodes relative to the newer nodes.

NOTE: It is not strictly necessary that you use traverse() or traverse_range() in order to iterate over the multimap elements. In fact, I would recommend that you use cgul_multimap_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_multimap_node_cxx class provides all the public methods you need to safely remove nodes while you are iterating over the multimap, but you do have to be careful.

Parameters

[in]	older_is_greater	whether older nodes are greater
[in]	f	traversal callback function
[in]	data	client data passed to `f`

See also: traverse_range()

References traverse_range().

§ traverse_range()

virtual void cgul_multimap_cxx::traverse_range	(	cgul_multimap_node_cxx *	first,
		cgul_multimap_node_cxx *	last,
		int	older_is_greater,
		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 multimap. 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 multimap 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 multimap. If last is NULL, iteration stops at the end of the multimap.

The primary sort criterion is the user's compare function, of course, but the older_is_greater boolean is used as a secondary sort criterion. When a key maps to many values, the older_is_greater boolean determines how to sort the older nodes relative to the newer nodes.

NOTE: It is not strictly necessary that you use traverse() or traverse_range() in order to iterate over the multimap elements. In fact, I would recommend that you use cgul_multimap_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_multimap_node_cxx class provides all the public methods you need to safely remove nodes while you are iterating over the multimap, but you do have to be careful.

Parameters

[in]	first	first node in range
[in]	last	last node in range
[in]	older_is_greater	whether older nodes are greater
[in]	f	traversal callback function
[in]	data	client data passed to `f`

See also: traverse()

References cgul_multimap__get_back(), cgul_multimap__get_front(), and cgul_multimap_node__get_next().

Referenced by traverse().

§ get_obj()

virtual cgul_multimap_t cgul_multimap_cxx::get_obj ( ) const

inlinevirtual

Get the underlying cgul_multimap object.

Returns: underlying object

§ take_obj()

virtual cgul_multimap_t cgul_multimap_cxx::take_obj ( )

inlinevirtual

Take the underlying cgul_multimap 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_multimap__delete().

Returns: underlying object

§ set_obj()

virtual void cgul_multimap_cxx::set_obj ( cgul_multimap_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_multimap__delete().

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

cgul_multimap_cxx.h

Public Types

Public Member Functions

Detailed Description

Member Typedef Documentation

§ compare_t

§ fold_key_t

§ fold_value_t

§ fold_pair_t

§ traverse_t

Constructor & Destructor Documentation

§ cgul_multimap_cxx() [1/2]

§ cgul_multimap_cxx() [2/2]

§ ~cgul_multimap_cxx()

Member Function Documentation

§ free_keys()

§ free_values()

§ is_empty()

§ insert()

§ insert_with_hint()

§ find()

§ find_floor()

§ find_ceiling()

§ remove()

§ remove_node()

§ remove_range()

§ remove_front()

§ remove_back()

§ get_front()

§ get_back()

§ get_oldest()

§ set_oldest()

§ get_youngest()

§ set_youngest()

§ 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()