multimap implementation More...

#include "cgul_common.h"
#include "cgul_cache.h"
#include "cgul_exception.h"
#include "cgul_multimap_node.h"
#include "cgul_rbtree.h"

Include dependency graph for cgul_multimap.h:

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

Typedefs
typedef typedefCGUL_BEGIN_C struct cgul_multimap *	cgul_multimap_t

typedef int(*	cgul_multimap__compare_t) (const void key1, const void key2)

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

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

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

typedef int(*	cgul_multimap__traverse_t) (cgul_exception_t cex, cgul_multimap_t mm, cgul_multimap_node_t n, void data)

Functions
CGUL_EXPORT cgul_multimap_t	cgul_multimap__new (cgul_exception_t *cex, cgul_multimap__compare_t compare)

CGUL_EXPORT void	cgul_multimap__delete (cgul_multimap_t mm)

CGUL_EXPORT void	cgul_multimap__free_keys (cgul_multimap_t mm)

CGUL_EXPORT void	cgul_multimap__free_values (cgul_multimap_t mm)

CGUL_EXPORT int	cgul_multimap__is_empty (cgul_exception_t *cex, cgul_multimap_t mm)

CGUL_EXPORT unsigned long int	cgul_multimap__insert (cgul_exception_t cex, cgul_multimap_t mm, void key, void value, cgul_multimap_node_t node)

CGUL_EXPORT unsigned long int	cgul_multimap__insert_with_hint (cgul_exception_t cex, cgul_multimap_t mm, void key, void value, cgul_multimap_node_t hint, cgul_multimap_node_t node)

CGUL_EXPORT unsigned long int	cgul_multimap__find (cgul_exception_t cex, cgul_multimap_t mm, void key, int older_is_greater, cgul_multimap_node_t *node)

CGUL_EXPORT unsigned long int	cgul_multimap__find_floor (cgul_exception_t cex, cgul_multimap_t mm, void search_key, int older_is_greater, cgul_multimap_node_t *node)

CGUL_EXPORT unsigned long int	cgul_multimap__find_ceiling (cgul_exception_t cex, cgul_multimap_t mm, void search_key, int older_is_greater, cgul_multimap_node_t *node)

CGUL_EXPORT int	cgul_multimap__remove (cgul_exception_t cex, cgul_multimap_t mm, void key, cgul_cache_t keys_cache, cgul_cache_t values_cache)

CGUL_EXPORT unsigned long int	cgul_multimap__remove_node (cgul_exception_t cex, cgul_multimap_t mm, cgul_multimap_node_t node, void key_out, void *value_out)

CGUL_EXPORT int	cgul_multimap__remove_range (cgul_exception_t *cex, cgul_multimap_t mm, cgul_multimap_node_t first, cgul_multimap_node_t last, int older_is_greater, cgul_cache_t keys_cache, cgul_cache_t values_cache)

CGUL_EXPORT int	cgul_multimap__remove_front (cgul_exception_t cex, cgul_multimap_t mm, int older_is_greater, void key_out, void *value_out)

CGUL_EXPORT int	cgul_multimap__remove_back (cgul_exception_t cex, cgul_multimap_t mm, int older_is_greater, void key_out, void *value_out)

CGUL_EXPORT cgul_multimap_node_t	cgul_multimap__get_front (cgul_exception_t *cex, cgul_multimap_t mm, int older_is_greater)

CGUL_EXPORT cgul_multimap_node_t	cgul_multimap__get_back (cgul_exception_t *cex, cgul_multimap_t mm, int older_is_greater)

CGUL_EXPORT cgul_multimap_node_t	cgul_multimap__get_oldest (cgul_exception_t *cex, cgul_multimap_t mm)

CGUL_EXPORT void	cgul_multimap__set_oldest (cgul_exception_t *cex, cgul_multimap_t mm, cgul_multimap_node_t n)

CGUL_EXPORT cgul_multimap_node_t	cgul_multimap__get_youngest (cgul_exception_t *cex, cgul_multimap_t mm)

CGUL_EXPORT void	cgul_multimap__set_youngest (cgul_exception_t *cex, cgul_multimap_t mm, cgul_multimap_node_t n)

CGUL_EXPORT void	cgul_multimap__clear (cgul_exception_t *cex, cgul_multimap_t mm, cgul_cache_t keys_cache, cgul_cache_t values_cache)

CGUL_EXPORT unsigned long int	cgul_multimap__get_size (cgul_exception_t *cex, cgul_multimap_t mm)

CGUL_EXPORT cgul_rbtree_t	cgul_multimap__get_tree (cgul_exception_t *cex, cgul_multimap_t mm)

CGUL_EXPORT void	cgul_multimap__swap (cgul_exception_t *cex, cgul_multimap_t mm1, cgul_multimap_t mm2)

CGUL_EXPORT void	cgul_multimap__foldl_keys (cgul_exception_t cex, cgul_multimap_t mm, cgul_multimap__fold_key_t f, void data)

CGUL_EXPORT void	cgul_multimap__foldr_keys (cgul_exception_t cex, cgul_multimap_t mm, cgul_multimap__fold_key_t f, void data)

CGUL_EXPORT void	cgul_multimap__foldl_values (cgul_exception_t cex, cgul_multimap_t mm, int older_is_greater, cgul_multimap__fold_value_t f, void data)

CGUL_EXPORT void	cgul_multimap__foldr_values (cgul_exception_t cex, cgul_multimap_t mm, int older_is_greater, cgul_multimap__fold_value_t f, void data)

CGUL_EXPORT void	cgul_multimap__foldl_pairs (cgul_exception_t cex, cgul_multimap_t mm, int older_is_greater, cgul_multimap__fold_pair_t f, void data)

CGUL_EXPORT void	cgul_multimap__foldr_pairs (cgul_exception_t cex, cgul_multimap_t mm, int older_is_greater, cgul_multimap__fold_pair_t f, void data)

CGUL_EXPORT void	cgul_multimap__traverse (cgul_exception_t cex, cgul_multimap_t mm, int older_is_greater, cgul_multimap__traverse_t f, void data)

CGUL_EXPORT void	cgul_multimap__traverse_range (cgul_exception_t cex, cgul_multimap_t mm, cgul_multimap_node_t first, cgul_multimap_node_t last, int older_is_greater, cgul_multimap__traverse_t f, void data)

Detailed Description

Multimap implementation.

Author: Paul Serice

Typedef Documentation

§ cgul_multimap_t

typedef typedefCGUL_BEGIN_C struct cgul_multimap* cgul_multimap_t

Opaque pointer to a cgul_multimap instance.

§ cgul_multimap__compare_t

typedef int(* cgul_multimap__compare_t) (const void *key1, const void *key2)

This typedef is the interface the client must define in order for cgul_multimap to sort your keys as they are inserted. When you define your comparison function, you should compare key1 to key2 and return less than zero, zero, or greater than zero if key1 is less than, equal to, or greater than key2.

Parameters

[in]	key1	first key
[in]	key2	second key

Returns: result of comparison

§ cgul_multimap__fold_key_t

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

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

    cgul_multimap__foldl_keys()
    cgul_multimap__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_multimap__fold_value_t

typedef int(* cgul_multimap__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_multimap__foldl_values()
    cgul_multimap__foldr_values()

Parameters

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

Returns: whether to continue

§ cgul_multimap__fold_pair_t

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

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

    cgul_multimap__foldl_pairs()
    cgul_multimap__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_multimap__traverse_t

typedef int(* cgul_multimap__traverse_t) (cgul_exception_t *cex, cgul_multimap_t mm, cgul_multimap_node_t n, void *data)

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

    cgul_multimap__traverse()
    cgul_multimap__traverse_range()

Parameters

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

Returns: whether to continue

Function Documentation

§ cgul_multimap__new()

CGUL_EXPORT cgul_multimap_t cgul_multimap__new	(	cgul_exception_t *	cex,
		cgul_multimap__compare_t	compare
	)

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 freeing the object by calling cgul_multimap__delete(). Also, the client is responsible for freeing the key/value pairs only after their nodes have been permanently removed from the cgul_multimap. The cgul_multimap__traverse() method can be used to remove each node safely before calling cgul_multimap__delete().

Parameters

[in,out]	cex	c-style exception
[in]	compare	comparison function

Returns: new cgul_multimap instance

See also: cgul_multimap__compare_t

Referenced by cgul_multimap_cxx::cgul_multimap_cxx().

§ cgul_multimap__delete()

CGUL_EXPORT void cgul_multimap__delete ( cgul_multimap_t mm )

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 cgul_multimap__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 multimap. 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 mm after calling this method.

Parameters

[in] mm cgul_multimap instance

See also: cgul_multimap__free_keys(); cgul_multimap__free_values()

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

§ cgul_multimap__free_keys()

CGUL_EXPORT void cgul_multimap__free_keys ( cgul_multimap_t mm )

This method calls free() on all the keys in the multimap mm. 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_multimap__delete() because it otherwise invalidates the multimap. Because this function is basically an extension of cgul_multimap__delete(), it does not accept a cgul_exception object as an input parameter.

Parameters

[in] mm cgul_multimap instance

Referenced by cgul_multimap_cxx::free_keys().

§ cgul_multimap__free_values()

CGUL_EXPORT void cgul_multimap__free_values ( cgul_multimap_t mm )

This method calls free() on all the values in the multimap mm. 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_multimap__delete() because it otherwise invalidates the multimap. Because this function is basically an extension of cgul_multimap__delete(), it does not accept a cgul_exception object as an input parameter.

Parameters

[in] mm cgul_multimap instance

Referenced by cgul_multimap_cxx::free_values().

§ cgul_multimap__is_empty()

CGUL_EXPORT int cgul_multimap__is_empty	(	cgul_exception_t *	cex,
		cgul_multimap_t	mm
	)

Whether the multimap mm is empty.

Parameters

[in]	cex	c-style exception
[in]	mm	`cgul_multimap` instance

Returns: whether the multimap mm is empty

Referenced by cgul_multimap_cxx::is_empty().

§ cgul_multimap__insert()

CGUL_EXPORT unsigned long int cgul_multimap__insert	(	cgul_exception_t *	cex,
		cgul_multimap_t	mm,
		void *	key,
		void *	value,
		cgul_multimap_node_t *	node
	)

Insert the (key, value) pair into the multimap mm. 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, 0 is returned, *node is set to NULL (if node is not NULL), and an exception is thrown.

It is important to understand that the cgul_multimap class (like all containers in the cgul library) does 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:

    count = cgul_multimap__insert(cex, mm, key, value, NULL);
    if (*cex) {
        goto out;
    }
    if (count > 1) {
        free(key);
    }

Parameters

[in,out]	cex	c-style exception
[in]	mm	`cgul_multimap` instance
[in]	key	key
[in]	value	value
[out]	node	newly inserted node

Returns: count of values now associated with key

Referenced by cgul_multimap_cxx::insert().

§ cgul_multimap__insert_with_hint()

CGUL_EXPORT unsigned long int cgul_multimap__insert_with_hint	(	cgul_exception_t *	cex,
		cgul_multimap_t	mm,
		void *	key,
		void *	value,
		cgul_multimap_node_t	hint,
		cgul_multimap_node_t *	node
	)

This method works the same as cgul_multimap__insert() except if hint is not NULL it calls the comparison function (passed into cgul_multimap__new()) 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 cgul_multimap__insert(), and the insertion occurs in logarithmic time.

Parameters

[in,out]	cex	c-style exception
[in]	mm	`cgul_multimap` instance
[in]	key	key
[in]	value	value
[in]	hint	hint
[out]	node	newly inserted node

Returns: count of values now associated with key

Referenced by cgul_multimap_cxx::insert_with_hint().

§ cgul_multimap__find()

CGUL_EXPORT unsigned long int cgul_multimap__find	(	cgul_exception_t *	cex,
		cgul_multimap_t	mm,
		void *	key,
		int	older_is_greater,
		cgul_multimap_node_t *	node
	)

This method finds the smallest node associated with key in the multimap mm 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 = cgul_multimap__find(cex, mm, key, 0, &node);
    for (i = 0 ; i < count ; ++i) {
        ...
        node = cgul_multimap_node__get_next(cex, node, 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]	cex	c-style exception
[in]	mm	`cgul_multimap` instance
[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

Referenced by cgul_multimap_cxx::find().

§ cgul_multimap__find_floor()

CGUL_EXPORT unsigned long int cgul_multimap__find_floor	(	cgul_exception_t *	cex,
		cgul_multimap_t	mm,
		void *	search_key,
		int	older_is_greater,
		cgul_multimap_node_t *	node
	)

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]	cex	c-style exception
[in]	mm	`cgul_multimap` instance
[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

Referenced by cgul_multimap_cxx::find_floor().

§ cgul_multimap__find_ceiling()

CGUL_EXPORT unsigned long int cgul_multimap__find_ceiling	(	cgul_exception_t *	cex,
		cgul_multimap_t	mm,
		void *	search_key,
		int	older_is_greater,
		cgul_multimap_node_t *	node
	)

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]	cex	c-style exception
[in]	mm	`cgul_multimap` instance
[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

Referenced by cgul_multimap_cxx::find_ceiling().

§ cgul_multimap__remove()

CGUL_EXPORT int cgul_multimap__remove	(	cgul_exception_t *	cex,
		cgul_multimap_t	mm,
		void *	key,
		cgul_cache_t	keys_cache,
		cgul_cache_t	values_cache
	)

This method removes key and all the values associated with key from the multimap mm 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 cgul_multimap__remove_node() instead.

Parameters

[in]	cex	c-style exception
[in]	mm	`cgul_multimap` instance
[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__get_freer()

Referenced by cgul_multimap_cxx::remove().

§ cgul_multimap__remove_node()

CGUL_EXPORT unsigned long int cgul_multimap__remove_node	(	cgul_exception_t *	cex,
		cgul_multimap_t	mm,
		cgul_multimap_node_t	node,
		void **	key_out,
		void **	value_out
	)

Remove node from the multimap mm. 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:

    cgul_multimap__remove_node(cex, mm, 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 cgul_multimap_node__get_next() afterward. The solution is simple. Just call cgul_multimap_node__get_next() before calling this method:

    count = cgul_multimap__find(cex, mm, key, 1, &curr);
    if (curr) {
        for (i = 0 ; i < count ; ++i, curr = next) {
            next = cgul_multimap_node__get_next(cex, curr, 1);
            cgul_multimap__remove_node(cex,
                                       mm,
                                       curr,
                                       &key_out,
                                       &value_out);
            if (key_out) {
                free(key_out);
            }
            free(value_out);
        }
    }

Alternatively, you can use cgul_multimap__remove(), cgul_multimap__remove_range(), cgul_multimap__traverse(), or cgul_multimap__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 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_t key = NULL;
        cgul_string_t value = NULL;
        cgul_exception_t local = NULL;
        cgul_multimap__remove_node(&local,
                                   mm,
                                   node,
                                   (void**)&key,
                                   (void**)&value);
        if (key) {
            cgul_string__delete(key);
        }
        cgul_string__delete(value);
        return 1;
    }

    cgul_multimap_node_t first = NULL;
    cgul_multimap_node_t last = NULL;
    cgul_multimap__find(cex, mm, key, 1, &first);
    cgul_multimap__find(cex, mm, key, 0, &last);
    if (first && last) {
        cgul_multimap__traverse_range(cex,
                                      mm,
                                      first,
                                      last,
                                      1,
                                      &remove_node_cb,
                                      NULL);
    }

Parameters

[in]	cex	c-style exception
[in]	mm	`cgul_multimap` instance
[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

Referenced by cgul_multimap_cxx::remove_node().

§ cgul_multimap__remove_range()

CGUL_EXPORT int cgul_multimap__remove_range	(	cgul_exception_t *	cex,
		cgul_multimap_t	mm,
		cgul_multimap_node_t	first,
		cgul_multimap_node_t	last,
		int	older_is_greater,
		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.

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]	cex	c-style exception
[in]	mm	`cgul_multimap` instance
[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__get_freer()

Referenced by cgul_multimap_cxx::remove_range().

§ cgul_multimap__remove_front()

CGUL_EXPORT int cgul_multimap__remove_front	(	cgul_exception_t *	cex,
		cgul_multimap_t	mm,
		int	older_is_greater,
		void **	key_out,
		void **	value_out
	)

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:

    cgul_multimap__remove_front(cex, mm, 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 cgul_multimap__get_front() for more details.

Parameters

[in]	cex	c-style exception
[in]	mm	`cgul_multimap` instance
[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

Referenced by cgul_multimap_cxx::remove_front().

§ cgul_multimap__remove_back()

CGUL_EXPORT int cgul_multimap__remove_back	(	cgul_exception_t *	cex,
		cgul_multimap_t	mm,
		int	older_is_greater,
		void **	key_out,
		void **	value_out
	)

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:

    cgul_multimap__remove_back(cex, mm, 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 cgul_multimap__get_back() for more details.

Parameters

[in]	cex	c-style exception
[in]	mm	`cgul_multimap` instance
[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

Referenced by cgul_multimap_cxx::remove_back().

§ cgul_multimap__get_front()

CGUL_EXPORT cgul_multimap_node_t cgul_multimap__get_front	(	cgul_exception_t *	cex,
		cgul_multimap_t	mm,
		int	older_is_greater
	)

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]	cex	c-style exception
[in]	mm	`cgul_multimap` instance
[in]	older_is_greater	whether older nodes are greater than newer nodes

Returns: front node

See also: cgul_multimap_node__get_next(); cgul_multimap_node__get_prev()

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

§ cgul_multimap__get_back()

CGUL_EXPORT cgul_multimap_node_t cgul_multimap__get_back	(	cgul_exception_t *	cex,
		cgul_multimap_t	mm,
		int	older_is_greater
	)

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]	cex	c-style exception
[in]	mm	`cgul_multimap` instance
[in]	older_is_greater	whether older nodes are greater than newer nodes

Returns: back node

See also: cgul_multimap_node__get_next(); cgul_multimap_node__get_prev()

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

§ cgul_multimap__get_oldest()

CGUL_EXPORT cgul_multimap_node_t cgul_multimap__get_oldest	(	cgul_exception_t *	cex,
		cgul_multimap_t	mm
	)

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_t n = cgul_multimap__get_oldest(cex, mm);
    for ( ; n ; n = cgul_multimap_node__get_younger(cex, n)) {
        ...
    }

Parameters

[in]	cex	c-style exception
[in]	mm	`cgul_multimap` instance

Returns: oldest node

See also: cgul_multimap_node__get_younger()

Referenced by cgul_multimap_cxx::get_oldest().

§ cgul_multimap__set_oldest()

CGUL_EXPORT void cgul_multimap__set_oldest	(	cgul_exception_t *	cex,
		cgul_multimap_t	mm,
		cgul_multimap_node_t	n
	)

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 cgul_multimap__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]	cex	c-style exception
[in]	mm	`cgul_multimap` instance
[in]	n	node

See also: cgul_multimap__set_youngest()

Referenced by cgul_multimap_cxx::set_oldest().

§ cgul_multimap__get_youngest()

CGUL_EXPORT cgul_multimap_node_t cgul_multimap__get_youngest	(	cgul_exception_t *	cex,
		cgul_multimap_t	mm
	)

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_t n = cgul_multimap__get_youngest(cex, mm);
    for ( ; n ; n = cgul_multimap_node__get_older(cex, n)) {
        ...
    }

Parameters

[in]	cex	c-style exception
[in]	mm	`cgul_multimap` instance

Returns: youngest node

See also: cgul_multimap_node__get_older()

Referenced by cgul_multimap_cxx::get_youngest().

§ cgul_multimap__set_youngest()

CGUL_EXPORT void cgul_multimap__set_youngest	(	cgul_exception_t *	cex,
		cgul_multimap_t	mm,
		cgul_multimap_node_t	n
	)

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

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

Parameters

[in]	cex	c-style exception
[in]	mm	`cgul_multimap` instance
[in]	n	node

See also: cgul_multimap__set_oldest()

Referenced by cgul_multimap_cxx::set_youngest().

§ cgul_multimap__clear()

CGUL_EXPORT void cgul_multimap__clear	(	cgul_exception_t *	cex,
		cgul_multimap_t	mm,
		cgul_cache_t	keys_cache,
		cgul_cache_t	values_cache
	)

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 (cgul_multimap__remove_front(cex, mm, 0, &key, &value)) {
        if (key) {
            free(key);
        }
        free(value);
    }

Parameters

[in]	cex	c-style exception
[in]	mm	`cgul_multimap` instance
[in]	keys_cache	keys cache
[in]	values_cache	values cache

See also: cgul_multimap__remove_range; cgul_cache__get_freer()

Referenced by cgul_multimap_cxx::clear().

§ cgul_multimap__get_size()

CGUL_EXPORT unsigned long int cgul_multimap__get_size	(	cgul_exception_t *	cex,
		cgul_multimap_t	mm
	)

Return the total number of values stored in mm.

Parameters

[in]	cex	c-style exception
[in]	mm	`cgul_multimap` instance

Returns: size of the multimap

Referenced by cgul_multimap_cxx::get_size().

§ cgul_multimap__get_tree()

CGUL_EXPORT cgul_rbtree_t cgul_multimap__get_tree	(	cgul_exception_t *	cex,
		cgul_multimap_t	mm
	)

Get the underlying tree of keys. This is needed by cgul_multimap_cxx::foldl_keys() and cgul_multimap_cxx::foldr_keys() in order to efficiently find the keys.

Referenced by cgul_multimap_cxx::foldl_keys(), and cgul_multimap_cxx::foldr_keys().

§ cgul_multimap__swap()

CGUL_EXPORT void cgul_multimap__swap	(	cgul_exception_t *	cex,
		cgul_multimap_t	mm1,
		cgul_multimap_t	mm2
	)

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

Parameters

[in]	cex	c-style exception
[in]	mm1	first `cgul_multimap` instance
[in]	mm2	second `cgul_multimap` instance

Referenced by cgul_multimap_cxx::swap().

§ cgul_multimap__foldl_keys()

CGUL_EXPORT void cgul_multimap__foldl_keys	(	cgul_exception_t *	cex,
		cgul_multimap_t	mm,
		cgul_multimap__fold_key_t	f,
		void *	data
	)

This method performs a left fold of the multimap mm 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 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]	mm	`cgul_multimap` instance
[in]	f	combining function
[in]	data	client data passed to `f`

§ cgul_multimap__foldr_keys()

CGUL_EXPORT void cgul_multimap__foldr_keys	(	cgul_exception_t *	cex,
		cgul_multimap_t	mm,
		cgul_multimap__fold_key_t	f,
		void *	data
	)

This method performs a right fold of the multimap mm 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 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]	mm	`cgul_multimap` instance
[in]	f	combining function
[in]	data	client data passed to `f`

§ cgul_multimap__foldl_values()

CGUL_EXPORT void cgul_multimap__foldl_values	(	cgul_exception_t *	cex,
		cgul_multimap_t	mm,
		int	older_is_greater,
		cgul_multimap__fold_value_t	f,
		void *	data
	)

This method performs a left fold of the multimap mm 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 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]	mm	`cgul_multimap` instance
[in]	older_is_greater	whether older nodes are greater than newer nodes
[in]	f	combining function
[in]	data	client data passed to `f`

§ cgul_multimap__foldr_values()

CGUL_EXPORT void cgul_multimap__foldr_values	(	cgul_exception_t *	cex,
		cgul_multimap_t	mm,
		int	older_is_greater,
		cgul_multimap__fold_value_t	f,
		void *	data
	)

This method performs a right fold of the multimap mm 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 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]	mm	`cgul_multimap` instance
[in]	older_is_greater	whether older nodes are greater than newer nodes
[in]	f	combining function
[in]	data	client data passed to `f`

§ cgul_multimap__foldl_pairs()

CGUL_EXPORT void cgul_multimap__foldl_pairs	(	cgul_exception_t *	cex,
		cgul_multimap_t	mm,
		int	older_is_greater,
		cgul_multimap__fold_pair_t	f,
		void *	data
	)

This method performs a left fold of the multimap mm 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 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.

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,out]	cex	c-style exception
[in]	mm	`cgul_multimap` instance
[in]	older_is_greater	whether older nodes are greater than newer nodes
[in]	f	combining function
[in]	data	client data passed to `f`

§ cgul_multimap__foldr_pairs()

CGUL_EXPORT void cgul_multimap__foldr_pairs	(	cgul_exception_t *	cex,
		cgul_multimap_t	mm,
		int	older_is_greater,
		cgul_multimap__fold_pair_t	f,
		void *	data
	)

This method performs a right fold of the multimap mm 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 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.

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,out]	cex	c-style exception
[in]	mm	`cgul_multimap` instance
[in]	older_is_greater	whether older nodes are greater than newer nodes
[in]	f	combining function
[in]	data	client data passed to `f`

§ cgul_multimap__traverse()

CGUL_EXPORT void cgul_multimap__traverse	(	cgul_exception_t *	cex,
		cgul_multimap_t	mm,
		int	older_is_greater,
		cgul_multimap__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 multimap mm. 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_multimap__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 cgul_multimap__traverse() or cgul_multimap__traverse_range() in order to iterate over the multimap elements. In fact, I would recommend that you use cgul_multimap_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_multimap_node 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,out]	cex	c-style exception
[in]	mm	`cgul_multimap` instance
[in]	older_is_greater	whether older nodes are greater than newer nodes
[in]	f	traversal callback function
[in]	data	passed to `f`

§ cgul_multimap__traverse_range()

CGUL_EXPORT void cgul_multimap__traverse_range	(	cgul_exception_t *	cex,
		cgul_multimap_t	mm,
		cgul_multimap_node_t	first,
		cgul_multimap_node_t	last,
		int	older_is_greater,
		cgul_multimap__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 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 standard c-style exception parameter. It can be used by f to throw an exception. The second parameter passed into f is the multimap mm. 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_multimap__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 cgul_multimap__traverse() or cgul_multimap__traverse_range() in order to iterate over the multimap elements. In fact, I would recommend that you use cgul_multimap_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_multimap_node 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,out]	cex	c-style exception
[in]	mm	`cgul_multimap` instance
[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]	f	traversal callback function
[in]	data	client data passed to `f`

See also: cgul_multimap__traverse

Typedefs

Functions

Detailed Description

Typedef Documentation

§ cgul_multimap_t

§ cgul_multimap__compare_t

§ cgul_multimap__fold_key_t

§ cgul_multimap__fold_value_t

§ cgul_multimap__fold_pair_t

§ cgul_multimap__traverse_t

Function Documentation

§ cgul_multimap__new()

§ cgul_multimap__delete()

§ cgul_multimap__free_keys()

§ cgul_multimap__free_values()

§ cgul_multimap__is_empty()

§ cgul_multimap__insert()

§ cgul_multimap__insert_with_hint()

§ cgul_multimap__find()

§ cgul_multimap__find_floor()

§ cgul_multimap__find_ceiling()

§ cgul_multimap__remove()

§ cgul_multimap__remove_node()

§ cgul_multimap__remove_range()

§ cgul_multimap__remove_front()

§ cgul_multimap__remove_back()

§ cgul_multimap__get_front()

§ cgul_multimap__get_back()

§ cgul_multimap__get_oldest()

§ cgul_multimap__set_oldest()

§ cgul_multimap__get_youngest()

§ cgul_multimap__set_youngest()

§ cgul_multimap__clear()

§ cgul_multimap__get_size()

§ cgul_multimap__get_tree()

§ cgul_multimap__swap()

§ cgul_multimap__foldl_keys()

§ cgul_multimap__foldr_keys()

§ cgul_multimap__foldl_values()

§ cgul_multimap__foldr_values()

§ cgul_multimap__foldl_pairs()

§ cgul_multimap__foldr_pairs()

§ cgul_multimap__traverse()

§ cgul_multimap__traverse_range()