The Ordered Multimap Interface. More...

#include "impl/impl_ordered_multimap.h"
#include "types.h"

Include dependency graph for ordered_multimap.h:

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

Initialization Interface
Initialize the container with memory, callbacks, and permissions.
#define	ccc_omm_init(omm_name, user_struct_name, ommap_elem_field, key_field, alloc_fn, key_cmp_fn, aux)
	Initialize a ordered multimap of the user specified type.

Entry Interface
Obtain and operate on container entries for efficient queries when non-trivial control flow is needed.
#define	ccc_omm_try_insert_w(ordered_multimap_ptr, key, lazy_value...)
	Inserts a new key-value into the multimap only if none exists. Amortized O(lg N).

#define	ccc_omm_insert_or_assign_w(ordered_multimap_ptr, key, lazy_value...)
	Invariantly inserts the key value pair into the multimap either as the first entry or overwriting the oldest existing entry at key. Amortized O(lg N).

#define	ccc_omm_entry_r(ordered_multimap_ptr, key_ptr)
	Return a compound literal reference to the entry generated from a search. No manual management of a compound literal reference is necessary. Amortized O(lg N).

#define	ccc_omm_and_modify_w(ordered_multimap_entry_ptr, type_name, closure_over_T...)
	Modify an Occupied entry with a closure over user type T.

#define	ccc_omm_or_insert_w(ordered_multimap_entry_ptr, lazy_key_value...) ccc_impl_omm_or_insert_w(ordered_multimap_entry_ptr, lazy_key_value)
	Insert an initial key value into the multimap if none is present, otherwise return the oldest user type stored at the specified key. O(1).

#define	ccc_omm_insert_entry_w(ordered_multimap_entry_ptr, lazy_key_value...) ccc_impl_omm_insert_entry_w(ordered_multimap_entry_ptr, lazy_key_value)
	Invariantly writes the specified compound literal directly to the existing or newly allocated entry. O(1).

ccc_entry	ccc_omm_insert (ccc_ordered_multimap mm, ccc_ommap_elem key_val_handle)
	Returns an entry pointing to the newly inserted element and a status indicating if the map has already been Occupied at the given key. Amortized O(lg N).

ccc_entry	ccc_omm_try_insert (ccc_ordered_multimap mm, ccc_ommap_elem key_val_handle)
	Inserts a new key-value into the multimap only if none exists. Amortized O(lg N).

ccc_entry	ccc_omm_insert_or_assign (ccc_ordered_multimap mm, ccc_ommap_elem key_val_handle)
	Invariantly inserts the key value pair into the multimap either as the first entry or overwriting the oldest existing entry at key. Amortized O(lg N).

ccc_entry	ccc_omm_remove (ccc_ordered_multimap mm, ccc_ommap_elem out_handle)
	Removes the entry specified at key of the type containing out_handle preserving the old value if possible. Amortized O(lg N).

ccc_ommap_entry	ccc_omm_entry (ccc_ordered_multimap mm, void const key)
	Return a container specific entry for the given search for key. Amortized O(lg N).

ccc_ommap_entry *	ccc_omm_and_modify (ccc_ommap_entry e, ccc_update_fn fn)
	Return a reference to the provided entry modified with fn if Occupied.

ccc_ommap_entry *	ccc_omm_and_modify_aux (ccc_ommap_entry e, ccc_update_fn fn, void *aux)
	Return a reference to the provided entry modified with fn and auxiliary data aux if Occupied.

void *	ccc_omm_or_insert (ccc_ommap_entry const e, ccc_ommap_elem key_val_handle)
	Insert an initial key value into the multimap if none is present, otherwise return the oldest user type stored at the specified key. O(1).

void *	ccc_omm_insert_entry (ccc_ommap_entry const e, ccc_ommap_elem key_val_handle)
	Invariantly writes the specified key value directly to the existing or newly allocated entry. O(1).

ccc_entry	ccc_omm_remove_entry (ccc_ommap_entry *e)
	Removes the entry if it is Occupied. O(1).

bool	ccc_omm_occupied (ccc_ommap_entry const *e)
	Indicates if an entry is Occupied or Vacant.

void *	ccc_omm_unwrap (ccc_ommap_entry const *e)
	Unwraps the provided entry. An Occupied entry will point to the user type stored in the map, a Vacant entry will be NULL.

bool	ccc_omm_insert_error (ccc_ommap_entry const *e)
	Indicates if an insertion error occurs.

bool	ccc_omm_input_error (ccc_ommap_entry const *e)
	Indicates if a function used to generate the provided entry encountered bad arguments that prevented the operation of the function.

ccc_entry_status	ccc_omm_entry_status (ccc_ommap_entry const *e)
	Obtain the entry status from a container entry.

Iterator Interface
Obtain and manage iterators over the container.
#define	ccc_omm_equal_range_r(ordered_multimap_ptr, begin_and_end_key_ptrs...)
	Returns a compound literal reference to the desired range. Amortized O(lg N).

#define	ccc_omm_equal_rrange_r(ordered_multimap_ptr, rbegin_and_rend_key_ptrs...)
	Returns a compound literal reference to the desired rrange. Amortized O(lg N).

ccc_range	ccc_omm_equal_range (ccc_ordered_multimap mm, void const begin_key, void const *end_key)
	Return an iterable range of values from [begin_key, end_key). Amortized O(lg N).

ccc_rrange	ccc_omm_equal_rrange (ccc_ordered_multimap mm, void const rbegin_key, void const *rend_key)
	Return an iterable rrange of values from [begin_key, end_key). Amortized O(lg N).

void *	ccc_omm_begin (ccc_ordered_multimap const *mm)
	Return the start of an inorder traversal of the multimap. Amortized O(lg N).

void *	ccc_omm_rbegin (ccc_ordered_multimap const *mm)
	Return the start of a reverse inorder traversal of the multimap. Amortized O(lg N).

void *	ccc_omm_next (ccc_ordered_multimap const mm, ccc_ommap_elem const iter_handle)
	Return the next element in an inorder traversal of the multimap. O(1).

void *	ccc_omm_rnext (ccc_ordered_multimap const mm, ccc_ommap_elem const iter_handle)
	Return the rnext element in a reverse inorder traversal of the multimap. O(1).

void *	ccc_omm_end (ccc_ordered_multimap const *mm)
	Return the end of an inorder traversal of the multimap. O(1).

void *	ccc_omm_rend (ccc_ordered_multimap const *mm)
	Return the rend of a reverse inorder traversal of the multimap. O(1).

Container Types
Types available in the container interface.
typedef union ccc_ordered_multimap_	ccc_ordered_multimap
	A container for membership testing by key field, allowing duplicate keys.

typedef union ccc_ommap_elem_	ccc_ommap_elem
	The intrusive element for the user defined type stored in the multimap.

typedef union ccc_ommap_entry_	ccc_ommap_entry
	The container specific type to support the Entry Interface.

Membership Interface
Test membership or obtain references to stored user types directly.
bool	ccc_omm_contains (ccc_ordered_multimap mm, void const key)
	Returns the membership of key in the multimap. Amortized O(lg N).

void *	ccc_omm_get_key_val (ccc_ordered_multimap mm, void const key)
	Returns a reference to the user type stored at key. Amortized O(lg N).

Push and Pop Interface
An interface to enhance the priority queue capabilities of a multimap.
ccc_result	ccc_omm_pop_max (ccc_ordered_multimap *mm)
	Pops the oldest maximum key value user type from the map. Elements are stored in ascending order, smallest as defined by the comparison function is min and largest is max. Amortized O(lg N).

ccc_result	ccc_omm_pop_min (ccc_ordered_multimap *mm)
	Pops the oldest minimum element from the map. Elements are stored in ascending order, smallest as defined by the comparison function is min and largest is max. Amortized O(lg N).

void *	ccc_omm_max (ccc_ordered_multimap *mm)
	Returns a reference to the oldest maximum key value user type from the map. Elements are stored in ascending order, smallest as defined by the comparison function is min and largest is max. Amortized O(lg N).

void *	ccc_omm_min (ccc_ordered_multimap *mm)
	Returns a reference to the oldest minimum key value user type from the map. Elements are stored in ascending order, smallest as defined by the comparison function is min and largest is max. Amortized O(lg N).

void *	ccc_omm_extract (ccc_ordered_multimap mm, ccc_ommap_elem key_val_handle)
	Extracts a user type known to be stored in the map with key_val_handle as an element currently in use by the map. O(1).

bool	ccc_omm_update (ccc_ordered_multimap mm, ccc_ommap_elem key_val_handle, ccc_update_fn fn, void aux)
	Updates an element key that is currently tracked directly as a member of the map. Amortized O(lg N).

bool	ccc_omm_increase (ccc_ordered_multimap mm, ccc_ommap_elem key_val_handle, ccc_update_fn fn, void aux)
	Increases an element key that is currently tracked directly as a member of the map. Amortized O(lg N).

bool	ccc_omm_decrease (ccc_ordered_multimap mm, ccc_ommap_elem key_val_handle, ccc_update_fn fn, void aux)
	Decreases an element key that is currently tracked directly as a member of the map. Amortized O(lg N).

Deallocation Interface
Deallocate the container.
ccc_result	ccc_omm_clear (ccc_ordered_multimap mm, ccc_destructor_fn destructor)
	Pops every element from the map calling destructor if destructor is non-NULL. O(N).

State Interface
Obtain the container state.
bool	ccc_omm_is_empty (ccc_ordered_multimap const *mm)
	Returns true if the multimap is empty. O(1).

size_t	ccc_omm_size (ccc_ordered_multimap const *mm)
	Returns true if the multimap is empty. O(1).

bool	ccc_omm_validate (ccc_ordered_multimap const *mm)
	Returns true if the multimap is empty.

Detailed Description

The Ordered Multimap Interface.

A multimap offers storage and retrieval by key. However, duplicate keys are allowed to be stored in the map.

This multimap orders duplicate keys by a round robin scheme. This means the oldest key-value inserted into the multimap will be the one found on any queries or removed first when popped from the multimap. Therefore, this multimap is equivalent to a double ended priority queue with round robin fairness among duplicate key elements. There are helper functions to make this use case simpler. The multimap is a self-optimizing data structure and therefore does not offer read-only searching. The runtime for all search, insert, and remove operations is amortized O(lg N) and may not meet the requirements of realtime systems.

This container offers pointer stability. Also, if the container is not permitted to allocate all insertion code assumes that the user has allocated memory appropriately for the element to be inserted; it will not allocate or free in this case. If allocation is permitted upon initialization the container will manage the memory as expected on insert or erase operations as defined by the interface; memory is allocated for insertions and freed for removals.

To shorten names in the interface, define the following preprocessor directive at the top of your file.

#define ORDERED_MULTIMAP_USING_NAMESPACE_CCC

All types and functions can then be written without the ccc_ prefix.

Macro Definition Documentation

◆ ccc_omm_and_modify_w

#define ccc_omm_and_modify_w	(	ordered_multimap_entry_ptr,
		type_name,
		closure_over_T...
	)

Value:

    &(ccc_ommap_entry)                                                         \
    {                                                                          \
        ccc_impl_omm_and_modify_w(ordered_multimap_entry_ptr, type_name,       \
                                  closure_over_T)                              \
    }

Modify an Occupied entry with a closure over user type T.

Parameters

[in]	ordered_multimap_entry_ptr	the address of the multimap entry.
[in]	type_name	the name of the user type stored in the container.
[in]	closure_over_T	the code to be run on the reference to user type T, if Occupied. This may be a semicolon separated list of statements to execute on T or a section of code wrapped in braces {code here} which may be preferred for formatting.

Returns: a compound literal reference to the modified entry if it was occupied or a vacant entry if it was vacant.

Note: T is a reference to the user type stored in the entry guaranteed to be non-NULL if the closure executes.

#define ORDERED_MULTIMAP_USING_NAMESPACE_CCC
// Increment the key k if found otherwise do nothing.
omm_entry *e = omm_and_modify_w(entry_r(&omm, &k), word, T->cnt++;);
 
// Increment the key k if found otherwise insert a default value.
word *w = omm_or_insert_w(omm_and_modify_w(entry_r(&omm, &k), word,
                                           { T->cnt++; }),
                          (word){.key = k, .cnt = 1});

Note that any code written is only evaluated if the entry is Occupied and the container can deliver the user type T. This means any function calls are lazily evaluated in the closure scope.

◆ ccc_omm_entry_r

#define ccc_omm_entry_r	(	ordered_multimap_ptr,
		key_ptr
	)

Value:

    &(ccc_ommap_entry)                                                         \
    {                                                                          \
        ccc_omm_entry((ordered_multimap_ptr), (key_ptr)).impl_                 \
    }

Return a compound literal reference to the entry generated from a search. No manual management of a compound literal reference is necessary. Amortized O(lg N).

Parameters

[in]	ordered_multimap_ptr	a pointer to the multimap.
[in]	key_ptr	a ponter to the key to be searched.

Returns: a compound literal reference to a container specific entry associated with the enclosing scope. This reference is always non-NULL.

Note this is useful for nested calls where an entry pointer is requested by further operations in the Entry Interface, avoiding uneccessary intermediate values and references (e.g. struct val *v = or_insert(entry_r(...), ...));

◆ ccc_omm_equal_range_r

#define ccc_omm_equal_range_r	(	ordered_multimap_ptr,
		begin_and_end_key_ptrs...
	)

Value:

    &(ccc_range)                                                               \
    {                                                                          \
        ccc_omm_equal_range(ordered_multimap_ptr, begin_and_end_key_ptrs)      \
            .impl_                                                             \
    }

Returns a compound literal reference to the desired range. Amortized O(lg N).

Parameters

[in]	ordered_multimap_ptr	a pointer to the multimap.
[in]	begin_and_end_key_ptrs	two pointers, one to the beginning of the range and one to the end of the range.

Returns: a compound literal reference to the produced range associated with the enclosing scope. This reference is always non-NULL.

◆ ccc_omm_equal_rrange_r

#define ccc_omm_equal_rrange_r	(	ordered_multimap_ptr,
		rbegin_and_rend_key_ptrs...
	)

Value:

    &(ccc_rrange)                                                              \
    {                                                                          \
        ccc_omm_equal_rrange(ordered_multimap_ptr, rbegin_and_rend_key_ptrs)   \
            .impl_                                                             \
    }

Returns a compound literal reference to the desired rrange. Amortized O(lg N).

Parameters

[in]	ordered_multimap_ptr	a pointer to the multimap.
[in]	rbegin_and_rend_key_ptrs	two pointers, one to the beginning of the rrange and one to the end of the rrange.

Returns: a compound literal reference to the produced rrange associated with the enclosing scope. This reference is always non-NULL.

◆ ccc_omm_init

#define ccc_omm_init	(	omm_name,
		user_struct_name,
		ommap_elem_field,
		key_field,
		alloc_fn,
		key_cmp_fn,
		aux
	)

Value:

ccc_impl_omm_init(omm_name, user_struct_name, ommap_elem_field, key_field, \

alloc_fn, key_cmp_fn, aux)

Initialize a ordered multimap of the user specified type.

Parameters

[in]	omm_name	the name of the ordered multimap being initialized.
[in]	user_struct_name	the struct the user intends to store.
[in]	ommap_elem_field	the name of the field with the intrusive element.
[in]	key_field	the name of the field used as the multimap key.
[in]	alloc_fn	the ccc_alloc_fn (types.h) used to allocate nodes or NULL.
[in]	key_cmp_fn	the ccc_key_cmp_fn (types.h) used to compare the key to the current stored element under considertion during a map operation.
[in]	aux	any aux data needed for compare, print, or destruction.

Returns: the initialized ordered multimap. Use this initializer on the right hand side of the variable at compile or run time (e.g. ccc_ordered_multimap m = ccc_omm_init(...);)

◆ ccc_omm_insert_entry_w

#define ccc_omm_insert_entry_w	(	ordered_multimap_entry_ptr,
		lazy_key_value...
	)	ccc_impl_omm_insert_entry_w(ordered_multimap_entry_ptr, lazy_key_value)

Invariantly writes the specified compound literal directly to the existing or newly allocated entry. O(1).

Parameters

[in]	ordered_multimap_entry_ptr	the address of the multimap entry.
[in]	lazy_key_value	the compound literal that is constructed directly at the existing or newly allocated memory in the container.

Returns: a pointer to the user type written to the existing map entry or newly inserted. If NULL is returned, an allocator error has occured or allocation was disallowed on initialization to prevent inserting a new element

Warning: the key in the lazy_key_value compound literal must match the key used for the initial entry generation.

Note that it only makes sense to use this method when the container is permitted to allocate memory.

◆ ccc_omm_insert_or_assign_w

#define ccc_omm_insert_or_assign_w	(	ordered_multimap_ptr,
		key,
		lazy_value...
	)

Value:

    &(ccc_entry)                                                               \
    {                                                                          \
        ccc_impl_omm_insert_or_assign_w(ordered_multimap_ptr, key, lazy_value) \
    }

Invariantly inserts the key value pair into the multimap either as the first entry or overwriting the oldest existing entry at key. Amortized O(lg N).

Parameters

[in]	ordered_multimap_ptr	a pointer to the multimap
[in]	key	the direct key r-value to be searched.
[in]	lazy_value	the compound literal for the type to be directly written to the existing or newly allocated map entry.

Returns: a compound literal reference to the entry in the map. The status is Occupied if this entry shows the oldest existing entry at key with the newly written value, or Vacant if no prior entry existed and this is the first insertion at key.

Note that only the value, and any other supplementary fields, need to be specified in the struct compound literal as this method ensures the struct key and searched key match.

◆ ccc_omm_or_insert_w

#define ccc_omm_or_insert_w	(	ordered_multimap_entry_ptr,
		lazy_key_value...
	)	ccc_impl_omm_or_insert_w(ordered_multimap_entry_ptr, lazy_key_value)

Insert an initial key value into the multimap if none is present, otherwise return the oldest user type stored at the specified key. O(1).

Parameters

[in]	ordered_multimap_entry_ptr	the address of the multimap entry.
[in]	lazy_key_value	the compound literal of the user struct stored in the map.

Returns: a pointer to the user type stored in the map either existing or newly inserted. If NULL is returned, an allocator error has occured or allocation was disallowed on initialization to prevent inserting a new element.

Warning: the key in the lazy_key_value compound literal must match the key used for the initial entry generation.

Note that it only makes sense to use this method when the container is permitted to allocate memory.

◆ ccc_omm_try_insert_w

#define ccc_omm_try_insert_w	(	ordered_multimap_ptr,
		key,
		lazy_value...
	)

Value:

    &(ccc_entry)                                                               \
    {                                                                          \
        ccc_impl_omm_try_insert_w(ordered_multimap_ptr, key, lazy_value)       \
    }

Inserts a new key-value into the multimap only if none exists. Amortized O(lg N).

Parameters

[in]	ordered_multimap_ptr	a pointer to the multimap
[in]	key	the direct key r-value to be searched.
[in]	lazy_value	the compound literal for the type to be directly written to a new allocation if an entry does not already exist at key.

Returns: a compound literal reference to the entry in the map. The status is Occupied if this entry shows the oldest existing entry at key, or Vacant if no prior entry existed and this is the first insertion at key.

Note that only the value, and any other supplementary fields, need be specified in the struct compound literal as this method ensures the struct key and searched key match.

Typedef Documentation

◆ ccc_ommap_elem

typedef union ccc_ommap_elem_ ccc_ommap_elem

The intrusive element for the user defined type stored in the multimap.

The ordered multimap element can occupy a single field anywhere in the user struct. Note that if allocation is not permitted, insertions functions accepting this type as an argument assume it to exist in pre-allocated memory that will exist with the appropriate lifetime and scope for the user's needs; the container does not allocate or free in this case.

◆ ccc_ommap_entry

typedef union ccc_ommap_entry_ ccc_ommap_entry

The container specific type to support the Entry Interface.

An Entry Interface offers efficient conditional searching, saving multiple searches. Entries are views of Vacant or Occupied multimap elements allowing further operations to be performed once they are obtained without a second search, insert, or remove query.

◆ ccc_ordered_multimap

typedef union ccc_ordered_multimap_ ccc_ordered_multimap

A container for membership testing by key field, allowing duplicate keys.

Warning: it is undefined behavior to use an uninitialized container.

A ordered multimap may be stored on the stack, heap, or data segment. It can be initialized at compile time or runtime.

Function Documentation

◆ ccc_omm_and_modify()

ccc_ommap_entry * ccc_omm_and_modify	(	ccc_ommap_entry *	e,
		ccc_update_fn *	fn
	)

Return a reference to the provided entry modified with fn if Occupied.

Parameters

[in]	e	a pointer to the container specific entry.
[in]	fn	the update function to modify the type in the entry.

Returns: a reference to the same entry provided. The update function will be called on the entry with NULL as the auxiliary argument if the entry is Occupied, otherwise the function is not called. If either arguments to the function are NULL, NULL is returned.

◆ ccc_omm_and_modify_aux()

ccc_ommap_entry * ccc_omm_and_modify_aux	(	ccc_ommap_entry *	e,
		ccc_update_fn *	fn,
		void *	aux
	)

Return a reference to the provided entry modified with fn and auxiliary data aux if Occupied.

Parameters

[in]	e	a pointer to the container specific entry.
[in]	fn	the update function to modify the type in the entry.
[in]	aux	a pointer to auxiliary data needed for the modification.

Returns: a reference to the same entry provided. The update function will be called on the entry with aux as the auxiliary argument if the entry is Occupied, otherwise the function is not called. If any arguments to the function are NULL, NULL is returned.

◆ ccc_omm_begin()

void * ccc_omm_begin ( ccc_ordered_multimap const * mm )

Return the start of an inorder traversal of the multimap. Amortized O(lg N).

Parameters

[in] mm a pointer to the multimap.

Returns: the oldest minimum element of the map.

Note that duplicate keys will be traversed starting at the oldest element in round robin order and ending at the newest before progressing to the next key of stored in the multimap.

◆ ccc_omm_clear()

ccc_result ccc_omm_clear	(	ccc_ordered_multimap *	mm,
		ccc_destructor_fn *	destructor
	)

Pops every element from the map calling destructor if destructor is non-NULL. O(N).

Parameters

[in]	mm	a pointer to the multimap.
[in]	destructor	a destructor function if required. NULL if unneeded.

Returns: an input error if mm points to NULL otherwise ok.

Note that if the multimap has been given permission to allocate, the destructor will be called on each element before it uses the provided allocator to free the element. Therefore, the destructor should not free the element or a double free will occur.

If the container has not been given allocation permission, then the destructor may free elements or not depending on how and when the user wishes to free elements of the map according to their own memory management schemes.

◆ ccc_omm_contains()

bool ccc_omm_contains	(	ccc_ordered_multimap *	mm,
		void const *	key
	)

Returns the membership of key in the multimap. Amortized O(lg N).

Parameters

[in]	mm	a pointer to the multimap.
[in]	key	a pointer to the key to be searched.

Returns: true if the multimap contains at least one entry at key, else false.

◆ ccc_omm_decrease()

bool ccc_omm_decrease	(	ccc_ordered_multimap *	mm,
		ccc_ommap_elem *	key_val_handle,
		ccc_update_fn *	fn,
		void *	aux
	)

Decreases an element key that is currently tracked directly as a member of the map. Amortized O(lg N).

Parameters

[in]	mm	the pointer to the multimap.
[in]	key_val_handle	a pointer to the intrusive element embedded in a user type that the user knows is currently in the map.
[in]	fn	the function used to decrease an element key in the map.
[in]	aux	any auxiliary data needed for the key decrease. Usually a new value but NULL is possible if aux is not needed.

Returns: true if the key decrease was successful, false if bad arguments are provided, it is possible to prove the key_val_handle is not tracked by the map, or the map is empty.

◆ ccc_omm_end()

void * ccc_omm_end ( ccc_ordered_multimap const * mm )

Return the end of an inorder traversal of the multimap. O(1).

Parameters

[in] mm a pointer to the multimap.

Returns: the newest maximum element of the map.

Note that duplicate keys will be traversed starting at the oldest element in round robin order and ending at the newest before progressing to the next key of stored in the multimap.

◆ ccc_omm_entry()

ccc_ommap_entry ccc_omm_entry	(	ccc_ordered_multimap *	mm,
		void const *	key
	)

Return a container specific entry for the given search for key. Amortized O(lg N).

Parameters

[in]	mm	a pointer to the multimap.
[in]	key	a pointer to the key to be searched.

Returns: a container specific entry for status, unwrapping, or further Entry Interface operations. Occupied indicates at least one user type with key exists and can be unwrapped to view. Vacant indicates no user type at key exists.

◆ ccc_omm_entry_status()

ccc_entry_status ccc_omm_entry_status ( ccc_ommap_entry const * e )

Obtain the entry status from a container entry.

Parameters

[in] e a pointer to the entry.

Returns: the status stored in the entry after the required action on the container completes. If e is NULL an entry input error is returned so ensure e is non-NULL to avoid an inaccurate status returned.

Note that this function can be useful for debugging or if more detailed messages are needed for logging purposes. See ccc_entry_status_msg() in ccc/types.h for more information on detailed entry statuses.

◆ ccc_omm_equal_range()

ccc_range ccc_omm_equal_range	(	ccc_ordered_multimap *	mm,
		void const *	begin_key,
		void const *	end_key
	)

Return an iterable range of values from [begin_key, end_key). Amortized O(lg N).

Parameters

[in]	mm	a pointer to the multimap.
[in]	begin_key	a pointer to the key intended as the start of the range.
[in]	end_key	a pointer to the key intended as the end of the range.

Returns: a range containing the first element NOT LESS than the begin_key and the first element GREATER than end_key.

Note that due to the variety of values that can be returned in the range, using the provided range iteration functions from types.h is recommended for example:

for (struct val *i = range_begin(&range); i != end_range(&range); i = next(&omm, &i->elem)) {}

This avoids any possible errors in handling an end range element that is in the map versus the end map sentinel.

◆ ccc_omm_equal_rrange()

ccc_rrange ccc_omm_equal_rrange	(	ccc_ordered_multimap *	mm,
		void const *	rbegin_key,
		void const *	rend_key
	)

Return an iterable rrange of values from [begin_key, end_key). Amortized O(lg N).

Parameters

[in]	mm	a pointer to the multimap.
[in]	rbegin_key	a pointer to the key intended as the start of the rrange.
[in]	rend_key	a pointer to the key intended as the end of the rrange.

Returns: a rrange containing the first element NOT GREATER than the begin_key and the first element LESS than rend_key.

Note that due to the variety of values that can be returned in the rrange, using the provided rrange iteration functions from types.h is recommended for example:

for (struct val *i = rrange_begin(&rrange); i != rend_rrange(&rrange); i = rnext(&omm, &i->elem)) {}

This avoids any possible errors in handling an rend rrange element that is in the map versus the end map sentinel.

◆ ccc_omm_extract()

void * ccc_omm_extract	(	ccc_ordered_multimap *	mm,
		ccc_ommap_elem *	key_val_handle
	)

Extracts a user type known to be stored in the map with key_val_handle as an element currently in use by the map. O(1).

Parameters

[in]	mm	the pointer to the multimap.
[in]	key_val_handle	a pointer to the intrusive element embedded in a user type that the user knows is currently in the map.

Returns: a reference to the extracted element. NULL is returned if it is possible to prove the key_val_handle is not tracked by the map or the map is empty.

Note that the element that is extracted is not freed, even if allocation permission is given to the container. It is the user's responsibility to free the element that has been extracted.

◆ ccc_omm_get_key_val()

void * ccc_omm_get_key_val	(	ccc_ordered_multimap *	mm,
		void const *	key
	)

Returns a reference to the user type stored at key. Amortized O(lg N).

Parameters

[in]	mm	a pointer to the multimap.
[in]	key	a pointer to the key to be searched.

Returns: a reference to the oldest existing user type at key, NULL if absent.

◆ ccc_omm_increase()

bool ccc_omm_increase	(	ccc_ordered_multimap *	mm,
		ccc_ommap_elem *	key_val_handle,
		ccc_update_fn *	fn,
		void *	aux
	)

Increases an element key that is currently tracked directly as a member of the map. Amortized O(lg N).

Parameters

[in]	mm	the pointer to the multimap.
[in]	key_val_handle	a pointer to the intrusive element embedded in a user type that the user knows is currently in the map.
[in]	fn	the function used to increase an element key in the map.
[in]	aux	any auxiliary data needed for the key increase. Usually a new value but NULL is possible if aux is not needed.

Returns: true if the key increase was successful, false if bad arguments are provided, it is possible to prove the key_val_handle is not tracked by the map, or the map is empty.

◆ ccc_omm_input_error()

bool ccc_omm_input_error ( ccc_ommap_entry const * e )

Indicates if a function used to generate the provided entry encountered bad arguments that prevented the operation of the function.

Parameters

[in] e a pointer to the multimap entry.

Returns: true if bad function arguments were provided, otherwise false.

Note bad arguments usually mean NULL pointers were passed to functions expecting non-NULL arguments.

◆ ccc_omm_insert()

ccc_entry ccc_omm_insert	(	ccc_ordered_multimap *	mm,
		ccc_ommap_elem *	key_val_handle
	)

Returns an entry pointing to the newly inserted element and a status indicating if the map has already been Occupied at the given key. Amortized O(lg N).

Parameters

[in]	mm	a pointer to the multimap.
[in]	key_val_handle	a handle to the new key value to be inserted.

Returns: an entry that can be unwrapped to view the inserted element. The status will be Occupied if this element is a duplicate added to a duplicate list or Vacant if this key is the first of its value inserted into the multimap. If the element cannot be added due to an allocator error, an insert error is set.

Note that if allocation has been prohibited the address of the key_val_handle is used directly. This means the container assumes the memory provided for the user type containing key_val_handle has been allocated with appropriate lifetime by the user, for the user's intended use case.

◆ ccc_omm_insert_entry()

void * ccc_omm_insert_entry	(	ccc_ommap_entry const *	e,
		ccc_ommap_elem *	key_val_handle
	)

Invariantly writes the specified key value directly to the existing or newly allocated entry. O(1).

Parameters

[in]	e	a pointer to the multimap entry.
[in]	key_val_handle	a pointer to the intrusive element in the user type.

Returns: a pointer to the user type written to the existing map entry or newly inserted. NULL is returned if allocation is permitted but the allocator encounters an error.

Note that if allocation has been prohibited the address of the key_val_handle is used directly. This means the container assumes the memory provided for the user type containing key_val_handle has been allocated with appropriate lifetime by the user, for the user's intended use case.

◆ ccc_omm_insert_error()

bool ccc_omm_insert_error ( ccc_ommap_entry const * e )

Indicates if an insertion error occurs.

Parameters

[in] e a pointer to the multimap entry.

Returns: true if an insertion error occured preventing completing of an Entry Interface series of operations.

Note that this will most commonly occur if the container is permitted to allocate but the allocation has failed.

◆ ccc_omm_insert_or_assign()

ccc_entry ccc_omm_insert_or_assign	(	ccc_ordered_multimap *	mm,
		ccc_ommap_elem *	key_val_handle
	)

Invariantly inserts the key value pair into the multimap either as the first entry or overwriting the oldest existing entry at key. Amortized O(lg N).

Parameters

[in]	mm	a pointer to the multimap
[in]	key_val_handle	a pointer to the intrusive element in the user type.

Returns: an entry of the user type in the map. The status is Occupied if this entry shows the oldest existing entry at key with the newly written value, or Vacant if no prior entry existed and this is the first insertion at key.

Note that if allocation has been prohibited the address of the key_val_handle is used directly. This means the container assumes the memory provided for the user type containing key_val_handle has been allocated with appropriate lifetime by the user, for the user's intended use case.

◆ ccc_omm_is_empty()

bool ccc_omm_is_empty ( ccc_ordered_multimap const * mm )

Returns true if the multimap is empty. O(1).

Parameters

[in] mm a pointer to the multimap.

Returns: true if empty, false if mm is NULL or mm is empty.

◆ ccc_omm_max()

void * ccc_omm_max ( ccc_ordered_multimap * mm )

Returns a reference to the oldest maximum key value user type from the map. Elements are stored in ascending order, smallest as defined by the comparison function is min and largest is max. Amortized O(lg N).

Parameters

[in] mm the pointer to the multimap.

Returns: the oldest maximum key value user type in the map.

Note that because the map is self optimizing, a search for the maximum element followed by a pop of the maximum element results in one amortized O(lg N) search followed by one O(1) pop. If there are duplicate max keys stored in the map, all subsequent max search and pop operations are O(1) until duplicates are exhausted and if no intervening search, insert, or erase operations occur for non-max keys.

◆ ccc_omm_min()

void * ccc_omm_min ( ccc_ordered_multimap * mm )

Returns a reference to the oldest minimum key value user type from the map. Elements are stored in ascending order, smallest as defined by the comparison function is min and largest is max. Amortized O(lg N).

Parameters

[in] mm the pointer to the multimap.

Returns: the oldest minimum key value user type in the map.

Note that because the map is self optimizing, a search for the minimum element followed by a pop of the minimum element results in one amortized O(lg N) search followed by one O(1) pop. If there are duplicate min keys stored in the map, all subsequent min search and pop operations are O(1) until duplicates are exhausted and if no intervening search, insert, or erase operations occur for non-min keys.

◆ ccc_omm_next()

void * ccc_omm_next	(	ccc_ordered_multimap const *	mm,
		ccc_ommap_elem const *	iter_handle
	)

Return the next element in an inorder traversal of the multimap. O(1).

Parameters

[in]	mm	a pointer to the multimap.
[in]	iter_handle	a pointer to the intrusive multimap element of the current iterator.

Returns: the next user type stored in the map in an inorder traversal.

Note that duplicate keys will be traversed starting at the oldest element in round robin order and ending at the newest before progressing to the next key of stored in the multimap.

◆ ccc_omm_occupied()

bool ccc_omm_occupied ( ccc_ommap_entry const * e )

Indicates if an entry is Occupied or Vacant.

Parameters

[in] e a pointer to the multimap entry.

Returns: true if the entry is Occupied, false if it is Vacant.

◆ ccc_omm_or_insert()

void * ccc_omm_or_insert	(	ccc_ommap_entry const *	e,
		ccc_ommap_elem *	key_val_handle
	)

Insert an initial key value into the multimap if none is present, otherwise return the oldest user type stored at the specified key. O(1).

Parameters

[in]	e	a pointer to the multimap entry.
[in]	key_val_handle	a pointer to the intrusive element in the user type.

Returns: a pointer to the user type stored in the map either existing or newly inserted. If NULL is returned, an allocator error has occured when allocation was allowed for the container.

Note that if allocation has been prohibited the address of the key_val_handle is used directly. This means the container assumes the memory provided for the user type containing key_val_handle has been allocated with appropriate lifetime by the user, for the user's intended use case.

◆ ccc_omm_pop_max()

ccc_result ccc_omm_pop_max ( ccc_ordered_multimap * mm )

Pops the oldest maximum key value user type from the map. Elements are stored in ascending order, smallest as defined by the comparison function is min and largest is max. Amortized O(lg N).

Parameters

[in] mm the pointer to the multimap.

Returns: the status of the pop operation. If NULL pointer is provided or the map is empty a bad input result is returned otherwise ok.

Note that continual pop max operations emptying a full queue with few to no intervening search or insert operations is a good use case for this container due to its self optimization.

◆ ccc_omm_pop_min()

ccc_result ccc_omm_pop_min ( ccc_ordered_multimap * mm )

Pops the oldest minimum element from the map. Elements are stored in ascending order, smallest as defined by the comparison function is min and largest is max. Amortized O(lg N).

Parameters

[in] mm the pointer to the multimap.

Returns: the status of the pop operation. If NULL pointer is provided or the map is empty a bad input result is returned otherwise ok.

Note that continual pop min operations emptying a full queue with few to no intervening search or insert operations is a good use case for this container due to its self optimization.

◆ ccc_omm_rbegin()

void * ccc_omm_rbegin ( ccc_ordered_multimap const * mm )

Return the start of a reverse inorder traversal of the multimap. Amortized O(lg N).

Parameters

[in] mm a pointer to the multimap.

Returns: the oldest maximum element of the map.

Note that duplicate keys will be traversed starting at the oldest element in round robin order and ending at the newest before progressing to the next key of stored in the multimap.

◆ ccc_omm_remove()

ccc_entry ccc_omm_remove	(	ccc_ordered_multimap *	mm,
		ccc_ommap_elem *	out_handle
	)

Removes the entry specified at key of the type containing out_handle preserving the old value if possible. Amortized O(lg N).

Parameters

[in]	mm	a pointer to the multimap.
[in]	out_handle	the pointer to the intrusive element in the user type.

Returns: an entry indicating if one of the elements stored at key has been removed. The status is Occupied if at least one element at key existed and was removed, or Vacant if no element existed at key. If the container has been given permission to allocate, the oldest user type stored at key will be written to the struct containing out_handle; the original data has been freed. If allocation has been denied the container will return the user struct directly and the user must unwrap and free their type themselves.

◆ ccc_omm_remove_entry()

ccc_entry ccc_omm_remove_entry ( ccc_ommap_entry * e )

Removes the entry if it is Occupied. O(1).

Parameters

[in] e a pointer to the multimap entry.

Returns: an entry indicating the status of the removal. If the entry was Vacant, a Vacant entry with NULL is returned. If the entry is Occupied and allocation is permitted, the stored user type is freed, the entry points to NULL, and the status indicates the entry was Occupied but contains NULL. If allocation is prohibited the entry is removed from the map and returned to be unwrapped and freed by the user.

◆ ccc_omm_rend()

void * ccc_omm_rend ( ccc_ordered_multimap const * mm )

Return the rend of a reverse inorder traversal of the multimap. O(1).

Parameters

[in] mm a pointer to the multimap.

Returns: the newest minimum element of the map.

Note that duplicate keys will be traversed starting at the oldest element in round robin order and ending at the newest before progressing to the next key of stored in the multimap.

◆ ccc_omm_rnext()

void * ccc_omm_rnext	(	ccc_ordered_multimap const *	mm,
		ccc_ommap_elem const *	iter_handle
	)

Return the rnext element in a reverse inorder traversal of the multimap. O(1).

Parameters

[in]	mm	a pointer to the multimap.
[in]	iter_handle	a pointer to the intrusive multimap element of the current iterator.

Returns: the rnext user type stored in the map in a reverse inorder traversal.

Note that duplicate keys will be traversed starting at the oldest element in round robin order and ending at the newest before progressing to the rnext key of stored in the multimap.

◆ ccc_omm_size()

size_t ccc_omm_size ( ccc_ordered_multimap const * mm )

Returns true if the multimap is empty. O(1).

Parameters

[in] mm a pointer to the multimap.

Returns: the size of the container or 0 if empty or mm is NULL.

◆ ccc_omm_try_insert()

ccc_entry ccc_omm_try_insert	(	ccc_ordered_multimap *	mm,
		ccc_ommap_elem *	key_val_handle
	)

Inserts a new key-value into the multimap only if none exists. Amortized O(lg N).

Parameters

[in]	mm	a pointer to the multimap
[in]	key_val_handle	a pointer to the intrusive element in the user type.

Returns: an entry of the user type in the map. The status is Occupied if this entry shows the oldest existing entry at key, or Vacant if no prior entry existed and this is the first insertion at key.

Note that if allocation has been prohibited the address of the key_val_handle is used directly. This means the container assumes the memory provided for the user type containing key_val_handle has been allocated with appropriate lifetime by the user, for the user's intended use case.

◆ ccc_omm_unwrap()

void * ccc_omm_unwrap ( ccc_ommap_entry const * e )

Unwraps the provided entry. An Occupied entry will point to the user type stored in the map, a Vacant entry will be NULL.

Parameters

[in] e a pointer to the multimap entry.

Returns: a pointer to the user type if Occupied, otherwise NULL.

◆ ccc_omm_update()

bool ccc_omm_update	(	ccc_ordered_multimap *	mm,
		ccc_ommap_elem *	key_val_handle,
		ccc_update_fn *	fn,
		void *	aux
	)

Updates an element key that is currently tracked directly as a member of the map. Amortized O(lg N).

Parameters

[in]	mm	the pointer to the multimap.
[in]	key_val_handle	a pointer to the intrusive element embedded in a user type that the user knows is currently in the map.
[in]	fn	the function used to update an element key in the map.
[in]	aux	any auxiliary data needed for the update. Usually a new value but NULL is possible if aux is not needed.

Returns: true if the key update was successful, false if bad arguments are provided, it is possible to prove the key_val_handle is not tracked by the map, or the map is empty.

◆ ccc_omm_validate()

bool ccc_omm_validate ( ccc_ordered_multimap const * mm )

Returns true if the multimap is empty.

Parameters

[in] mm a pointer to the multimap.

Returns: true if invariants of the data structure are preserved, else false.

Initialization Interface

Entry Interface

Iterator Interface

Container Types

Membership Interface

Push and Pop Interface

Deallocation Interface

State Interface

Detailed Description

Macro Definition Documentation

◆ ccc_omm_and_modify_w

◆ ccc_omm_entry_r

◆ ccc_omm_equal_range_r

◆ ccc_omm_equal_rrange_r

◆ ccc_omm_init

◆ ccc_omm_insert_entry_w

◆ ccc_omm_insert_or_assign_w

◆ ccc_omm_or_insert_w

◆ ccc_omm_try_insert_w

Typedef Documentation

◆ ccc_ommap_elem

◆ ccc_ommap_entry

◆ ccc_ordered_multimap

Function Documentation

◆ ccc_omm_and_modify()

◆ ccc_omm_and_modify_aux()

◆ ccc_omm_begin()

◆ ccc_omm_clear()

◆ ccc_omm_contains()

◆ ccc_omm_decrease()

◆ ccc_omm_end()

◆ ccc_omm_entry()

◆ ccc_omm_entry_status()

◆ ccc_omm_equal_range()

◆ ccc_omm_equal_rrange()

◆ ccc_omm_extract()

◆ ccc_omm_get_key_val()

◆ ccc_omm_increase()

◆ ccc_omm_input_error()

◆ ccc_omm_insert()

◆ ccc_omm_insert_entry()

◆ ccc_omm_insert_error()

◆ ccc_omm_insert_or_assign()

◆ ccc_omm_is_empty()

◆ ccc_omm_max()

◆ ccc_omm_min()

◆ ccc_omm_next()

◆ ccc_omm_occupied()

◆ ccc_omm_or_insert()

◆ ccc_omm_pop_max()

◆ ccc_omm_pop_min()

◆ ccc_omm_rbegin()

◆ ccc_omm_remove()

◆ ccc_omm_remove_entry()

◆ ccc_omm_rend()

◆ ccc_omm_rnext()

◆ ccc_omm_size()

◆ ccc_omm_try_insert()

◆ ccc_omm_unwrap()

◆ ccc_omm_update()

◆ ccc_omm_validate()