The Handle Ordered Map Interface. More...

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

Include dependency graph for handle_ordered_map.h:

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

Initialization Interface
Initialize the container with memory, callbacks, and permissions.
#define	ccc_hom_init(mem_ptr, om_elem_field, key_elem_field, key_cmp, alloc_fn, aux, capacity)
	Initializes the map at runtime or compile time.

ccc_result	ccc_hom_copy (ccc_handle_ordered_map dst, ccc_handle_ordered_map const src, ccc_alloc_fn *fn)
	Copy the map at source to destination.

Membership Interface
Test membership or obtain references to stored user types directly.
#define	ccc_hom_as(handle_ordered_map_ptr, type_name, handle_i...) ccc_impl_hom_as(handle_ordered_map_ptr, type_name, handle_i)
	Returns a reference to the user type in the table at the handle.

void *	ccc_hom_at (ccc_handle_ordered_map const *h, ccc_handle_i i)
	Returns a reference to the user data at the provided handle.

ccc_tribool	ccc_hom_contains (ccc_handle_ordered_map hom, void const key)
	Searches the map for the presence of key.

ccc_handle_i	ccc_hom_get_key_val (ccc_handle_ordered_map hom, void const key)
	Returns a reference into the map at handle key.

Handle Interface
Obtain and operate on container handles for efficient queries when non-trivial control flow is needed.
#define	ccc_hom_swap_handle_r(handle_ordered_map_ptr, out_handle_ptr)
	Invariantly inserts the key value wrapping key_val_handle.

#define	ccc_hom_try_insert_r(handle_ordered_map_ptr, key_val_handle_ptr)
	Attempts to insert the key value wrapping key_val_handle.

#define	ccc_hom_try_insert_w(handle_ordered_map_ptr, key, lazy_value...)
	lazily insert lazy_value into the map at key if key is absent.

#define	ccc_hom_insert_or_assign_w(handle_ordered_map_ptr, key, lazy_value...)
	Inserts a new key value pair or overwrites the existing handle.

#define	ccc_hom_remove_r(handle_ordered_map_ptr, out_handle_ptr)
	Removes the key value in the map storing the old value, if present, in the struct containing out_handle provided by the user.

#define	ccc_hom_handle_r(handle_ordered_map_ptr, key_ptr)
	Obtains a handle for the provided key in the map for future use.

#define	ccc_hom_and_modify_w(handle_ordered_map_handle_ptr, type_name, closure_over_T...)
	Modify an Occupied handle with a closure over user type T.

#define	ccc_hom_or_insert_w(handle_ordered_map_handle_ptr, lazy_key_value...) ccc_impl_hom_or_insert_w(handle_ordered_map_handle_ptr, lazy_key_value)
	Lazily insert the desired key value into the handle if it is Vacant.

#define	ccc_hom_insert_handle_w(handle_ordered_map_handle_ptr, lazy_key_value...) ccc_impl_hom_insert_handle_w(handle_ordered_map_handle_ptr, lazy_key_value)
	Write the contents of the compound literal lazy_key_value to a node.

#define	ccc_hom_remove_handle_r(handle_ordered_map_handle_ptr)
	Remove the handle from the map if Occupied.

ccc_handle	ccc_hom_swap_handle (ccc_handle_ordered_map hom, ccc_homap_elem out_handle)
	Invariantly inserts the key value wrapping key_val_handle.

ccc_handle	ccc_hom_try_insert (ccc_handle_ordered_map hom, ccc_homap_elem key_val_handle)
	Attempts to insert the key value wrapping key_val_handle.

ccc_handle	ccc_hom_insert_or_assign (ccc_handle_ordered_map hom, ccc_homap_elem key_val_handle)
	Invariantly inserts or overwrites a user struct into the map.

ccc_handle	ccc_hom_remove (ccc_handle_ordered_map hom, ccc_homap_elem out_handle)
	Removes the key value in the map storing the old value, if present, in the struct containing out_handle provided by the user.

ccc_homap_handle	ccc_hom_handle (ccc_handle_ordered_map hom, void const key)
	Obtains a handle for the provided key in the map for future use.

ccc_homap_handle *	ccc_hom_and_modify (ccc_homap_handle h, ccc_update_fn fn)
	Modifies the provided handle if it is Occupied.

ccc_homap_handle *	ccc_hom_and_modify_aux (ccc_homap_handle h, ccc_update_fn fn, void *aux)
	Modifies the provided handle if it is Occupied.

ccc_handle_i	ccc_hom_or_insert (ccc_homap_handle const h, ccc_homap_elem elem)
	Inserts the struct with handle elem if the handle is Vacant.

ccc_handle_i	ccc_hom_insert_handle (ccc_homap_handle const h, ccc_homap_elem elem)
	Inserts the provided handle invariantly.

ccc_handle	ccc_hom_remove_handle (ccc_homap_handle *h)
	Remove the handle from the map if Occupied.

ccc_handle_i	ccc_hom_unwrap (ccc_homap_handle const *h)
	Unwraps the provided handle to obtain a view into the map element.

ccc_tribool	ccc_hom_occupied (ccc_homap_handle const *h)
	Returns the Vacant or Occupied status of the handle.

ccc_tribool	ccc_hom_insert_error (ccc_homap_handle const *h)
	Provides the status of the handle should an insertion follow.

ccc_handle_status	ccc_hom_handle_status (ccc_homap_handle const *h)
	Obtain the handle status from a container handle.

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

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

ccc_range	ccc_hom_equal_range (ccc_handle_ordered_map hom, 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_hom_equal_rrange (ccc_handle_ordered_map hom, void const rbegin_key, void const *rend_key)
	Return an iterable rrange of values from [rbegin_key, end_key). Amortized O(lg N).

void *	ccc_hom_begin (ccc_handle_ordered_map const *hom)
	Return the start of an inorder traversal of the map. Amortized O(lg N).

void *	ccc_hom_rbegin (ccc_handle_ordered_map const *hom)
	Return the start of a reverse inorder traversal of the map. Amortized O(lg N).

void *	ccc_hom_next (ccc_handle_ordered_map const hom, ccc_homap_elem const iter_handle)
	Return the next element in an inorder traversal of the map. O(1).

void *	ccc_hom_rnext (ccc_handle_ordered_map const hom, ccc_homap_elem const iter_handle)
	Return the rnext element in a reverse inorder traversal of the map. O(1).

void *	ccc_hom_end (ccc_handle_ordered_map const *hom)
	Return the end of an inorder traversal of the map. O(1).

void *	ccc_hom_rend (ccc_handle_ordered_map const *hom)
	Return the rend of a reverse inorder traversal of the map. O(1).

Container Types
Types available in the container interface.
typedef struct ccc_homap_	ccc_handle_ordered_map
	A self-optimizing data structure offering amortized O(lg N) search, insert, and erase.

typedef struct ccc_homap_elem_	ccc_homap_elem
	The intrusive element for the user defined type being stored in the map.

typedef union ccc_homap_handle_	ccc_homap_handle
	A container specific handle used to implement the Handle Interface.

Deallocation Interface
Deallocate the container.
ccc_result	ccc_hom_clear (ccc_handle_ordered_map hom, ccc_destructor_fn fn)
	Frees all slots in the map for use without affecting capacity.

ccc_result	ccc_hom_clear_and_free (ccc_handle_ordered_map hom, ccc_destructor_fn fn)
	Frees all slots in the map and frees the underlying buffer.

State Interface
Obtain the container state.
ccc_ucount	ccc_hom_size (ccc_handle_ordered_map const *hom)
	Returns the size of the map representing active slots.

ccc_ucount	ccc_hom_capacity (ccc_handle_ordered_map const *hom)
	Returns the capacity of the map representing total possible slots.

void *	ccc_hom_data (ccc_handle_ordered_map const *hom)
	Return a reference to the base of backing array. O(1).

ccc_tribool	ccc_hom_is_empty (ccc_handle_ordered_map const *hom)
	Returns the size status of the map.

ccc_tribool	ccc_hom_validate (ccc_handle_ordered_map const *hom)
	Validation of invariants for the map.

Detailed Description

The Handle Ordered Map Interface.

A handle ordered map is a contiguously stored map offering storage and retrieval by key. Because the data structure is self-optimizing it is not a suitable map in a realtime environment where strict runtime bounds are needed. Also, searching the map is not a const thread-safe operation as indicated by the function signatures. The map is optimized upon every new search. However, in many cases the self-optimizing structure of the map can be beneficial when considering non-uniform access patterns. In the best case, repeated searches of the same value yield an O(1) access and many other frequently searched values will remain close to the root of the map.

The handle variant of the ordered map promises contiguous storage and random access if needed. Handles remain valid until an element is removed even if other elements are inserted, other elements are removed, or resizing occurs. All elements in the map track their relationships via indices in the buffer. Therefore, this data structure can be relocated, copied, serialized, or written to disk and all internal data structure references will remain valid. Insertion may invoke an O(N) operation if resizing occurs. Finally, if allocation is prohibited upon initialization and the user intends to store a fixed size N nodes in the map N + 1 capacity is needed for the sentinel node in the buffer.

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

#define HANDLE_ORDERED_MAP_USING_NAMESPACE_CCC

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

Macro Definition Documentation

◆ ccc_hom_and_modify_w

#define ccc_hom_and_modify_w	(	handle_ordered_map_handle_ptr,
		type_name,
		closure_over_T...
	)

Value:

    &(ccc_homap_handle)                                                        \
    {                                                                          \
        ccc_impl_hom_and_modify_w(handle_ordered_map_handle_ptr, type_name,    \
                                  closure_over_T)                              \
    }

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

Parameters

[in]	handle_ordered_map_handle_ptr	a pointer to the obtained handle.
[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 handle if it was occupied or a vacant handle if it was vacant.

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

#define HANDLE_ORDERED_MAP_USING_NAMESPACE_CCC
// Increment the key k if found otherwise do nothing.
hom_handle *e = hom_and_modify_w(handle_r(&hom, &k), word, T->cnt++;);
 
// Increment the key k if found otherwise insert a default value.
handle_i w = hom_or_insert_w(hom_and_modify_w(handle_r(&hom, &k), word,
                                              { T->cnt++; }),
                             (word){.key = k, .cnt = 1});

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

◆ ccc_hom_as

#define ccc_hom_as	(	handle_ordered_map_ptr,
		type_name,
		handle_i...
	)	ccc_impl_hom_as(handle_ordered_map_ptr, type_name, handle_i)

Returns a reference to the user type in the table at the handle.

Parameters

[in]	handle_ordered_map_ptr	a pointer to the map.
[in]	type_name	name of the user type stored in each slot of the map.
[in]	handle_i	the index handle obtained from previous map operations.

Returns: a reference to the handle at handle in the map as the type the user has stored in the map.

◆ ccc_hom_equal_range_r

#define ccc_hom_equal_range_r	(	handle_ordered_map_ptr,
		begin_and_end_key_ptrs...
	)

Value:

    &(ccc_range)                                                               \
    {                                                                          \
        ccc_hom_equal_range(handle_ordered_map_ptr, begin_and_end_key_ptrs)    \
            .impl_                                                             \
    }

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

Parameters

[in]	handle_ordered_map_ptr	a pointer to the map.
[in]	begin_and_end_key_ptrs	pointers to the begin and end of the range.

Returns: a compound literal reference to the produced range associated with the enclosing scope. This reference is always be valid.

◆ ccc_hom_equal_rrange_r

#define ccc_hom_equal_rrange_r	(	handle_ordered_map_ptr,
		rbegin_and_rend_key_ptrs...
	)

Value:

    &(ccc_rrange)                                                              \
    {                                                                          \
        ccc_hom_equal_rrange(handle_ordered_map_ptr, rbegin_and_rend_key_ptrs) \
            .impl_                                                             \
    }

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

Parameters

[in]	handle_ordered_map_ptr	a pointer to the map.
[in]	rbegin_and_rend_key_ptrs	pointers to the rbegin and rend of the range.

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

◆ ccc_hom_handle_r

#define ccc_hom_handle_r	(	handle_ordered_map_ptr,
		key_ptr
	)

Value:

    &(ccc_homap_handle)                                                        \
    {                                                                          \
        ccc_hom_handle((handle_ordered_map_ptr), (key_ptr)).impl_              \
    }

Obtains a handle for the provided key in the map for future use.

Parameters

[in]	handle_ordered_map_ptr	the map to be searched.
[in]	key_ptr	the key used to search the map matching the stored key type.

Returns: a compound literal reference to a specialized handle for use with other functions in the Handle Interface.

Warning: the contents of a handle should not be examined or modified. Use the provided functions, only.

a handle is a search result that provides either an Occupied or Vacant handle in the map. An occupied handle signifies that the search was successful. A Vacant handle means the search was not successful but a handle is gained to where in the map such an element should be inserted.

a handle is rarely useful on its own. It should be passed in a functional style to subsequent calls in the Handle Interface.

◆ ccc_hom_init

#define ccc_hom_init	(	mem_ptr,
		om_elem_field,
		key_elem_field,
		key_cmp,
		alloc_fn,
		aux,
		capacity
	)

Value:

ccc_impl_hom_init(mem_ptr, om_elem_field, key_elem_field, key_cmp, \

alloc_fn, aux, capacity)

Initializes the map at runtime or compile time.

Parameters

[in]	mem_ptr	a pointer to the contiguous user types or ((T *)NULL).
[in]	om_elem_field	the name of the intrusive map elem field.
[in]	key_elem_field	the name of the field in user type used as key.
[in]	key_cmp	the key comparison function (see types.h).
[in]	alloc_fn	the allocation function or NULL if allocation is banned.
[in]	aux	a pointer to any auxiliary data for comparison or destruction.
[in]	capacity	the capacity at mem_ptr or 0 if ((T *)NULL).

Returns: the struct initialized ordered map for direct assignment (i.e. ccc_handle_ordered_map m = ccc_hom_init(...);).

◆ ccc_hom_insert_handle_w

#define ccc_hom_insert_handle_w	(	handle_ordered_map_handle_ptr,
		lazy_key_value...
	)	ccc_impl_hom_insert_handle_w(handle_ordered_map_handle_ptr, lazy_key_value)

Write the contents of the compound literal lazy_key_value to a node.

Parameters

[in]	handle_ordered_map_handle_ptr	a pointer to the obtained handle.
[in]	lazy_key_value	the compound literal to write to a new slot.

Returns: a reference to the newly inserted or overwritten user type. NULL is returned if allocation failed or is not allowed when required.

◆ ccc_hom_insert_or_assign_w

#define ccc_hom_insert_or_assign_w	(	handle_ordered_map_ptr,
		key,
		lazy_value...
	)

Value:

    &(ccc_handle)                                                              \
    {                                                                          \
        ccc_impl_hom_insert_or_assign_w(handle_ordered_map_ptr, key,           \
                                        lazy_value)                            \
    }

Inserts a new key value pair or overwrites the existing handle.

Parameters

[in]	handle_ordered_map_ptr	the pointer to the handle hash map.
[in]	key	the key to be searched in the map.
[in]	lazy_value	the compound literal to insert or use for overwrite.

Returns: a compound literal reference to the handle of the existing or newly inserted value. Occupied indicates the key existed, Vacant indicates the key was absent. Unwrapping in any case provides the current value unless an error occurs that prevents insertion. An insertion error will flag such a case.

Note that for brevity and convenience the user need not write the key to the lazy value compound literal as well. This function ensures the key in the compound literal matches the searched key.

◆ ccc_hom_or_insert_w

#define ccc_hom_or_insert_w	(	handle_ordered_map_handle_ptr,
		lazy_key_value...
	)	ccc_impl_hom_or_insert_w(handle_ordered_map_handle_ptr, lazy_key_value)

Lazily insert the desired key value into the handle if it is Vacant.

Parameters

[in]	handle_ordered_map_handle_ptr	a pointer to the obtained handle.
[in]	lazy_key_value	the compound literal to construct in place if the handle is Vacant.

Returns: a reference to the unwrapped user type in the handle, either the unmodified reference if the handle was Occupied or the newly inserted element if the handle was Vacant. NULL is returned if resizing is required but fails or is not allowed.

Note that if the compound literal uses any function calls to generate values or other data, such functions will not be called if the handle is Occupied.

◆ ccc_hom_remove_handle_r

#define ccc_hom_remove_handle_r ( handle_ordered_map_handle_ptr )

Value:

    &(ccc_handle)                                                              \
    {                                                                          \
        ccc_hom_remove_handle((handle_ordered_map_handle_ptr)).impl_           \
    }

Remove the handle from the map if Occupied.

Parameters

[in] handle_ordered_map_handle_ptr a pointer to the map handle.

Returns: a compound literal reference containing no valid reference but information about the old handle. If Occupied a handle in the map existed and was removed. If Vacant, no prior handle existed to be removed.

◆ ccc_hom_remove_r

#define ccc_hom_remove_r	(	handle_ordered_map_ptr,
		out_handle_ptr
	)

Value:

    &(ccc_handle)                                                              \
    {                                                                          \
        ccc_hom_remove((handle_ordered_map_ptr), (out_handle_ptr)).impl_       \
    }

Removes the key value in the map storing the old value, if present, in the struct containing out_handle provided by the user.

Parameters

[in]	handle_ordered_map_ptr	the pointer to the ordered map.
[out]	out_handle_ptr	the handle to the user type wrapping map elem.

Returns: a compound literal reference to a handle. If Occupied the struct containing out_handle holds the old value. If Vacant the key value pair was not stored in the map. If bad input is provided an input error is set.

Note that this function may write to the struct containing the second parameter and wraps it in a handle to provide information about the old value.

◆ ccc_hom_swap_handle_r

#define ccc_hom_swap_handle_r	(	handle_ordered_map_ptr,
		out_handle_ptr
	)

Value:

    &(ccc_handle)                                                              \
    {                                                                          \
        ccc_hom_swap_handle((handle_ordered_map_ptr), (out_handle_ptr)).impl_  \
    }

Invariantly inserts the key value wrapping key_val_handle.

Parameters

[in]	handle_ordered_map_ptr	the pointer to the ordered map.
[out]	out_handle_ptr	the handle to the user type wrapping map elem.

Returns: a compound literal reference to a handle. If Vacant, no prior element with key existed and the type wrapping out_handle remains unchanged. If Occupied the old value is written to the type wrapping out_handle and may be unwrapped to view. If more space is needed but allocation fails or has been forbidden, an insert error is set.

Note that this function may write to the struct containing out_handle and wraps it in a handle to provide information about the old value.

◆ ccc_hom_try_insert_r

#define ccc_hom_try_insert_r	(	handle_ordered_map_ptr,
		key_val_handle_ptr
	)

Value:

    &(ccc_handle)                                                              \
    {                                                                          \
        ccc_hom_try_insert((handle_ordered_map_ptr), (key_val_handle_ptr))     \
            .impl_                                                             \
    }

Attempts to insert the key value wrapping key_val_handle.

Parameters

[in]	handle_ordered_map_ptr	the pointer to the map.
[in]	key_val_handle_ptr	the handle to the user type wrapping map elem.

Returns: a compound literal reference to a handle. If Occupied, the handle contains a reference to the key value user type in the map and may be unwrapped. If Vacant the handle contains a reference to the newly inserted handle in the map. If more space is needed but allocation fails an insert error is set.

◆ ccc_hom_try_insert_w

#define ccc_hom_try_insert_w	(	handle_ordered_map_ptr,
		key,
		lazy_value...
	)

Value:

    &(ccc_handle)                                                              \
    {                                                                          \
        ccc_impl_hom_try_insert_w(handle_ordered_map_ptr, key, lazy_value)     \
    }

lazily insert lazy_value into the map at key if key is absent.

Parameters

[in]	handle_ordered_map_ptr	a pointer to the map.
[in]	key	the direct key r-value.
[in]	lazy_value	the compound literal specifying the value.

Returns: a compound literal reference to the handle of the existing or newly inserted value. Occupied indicates the key existed, Vacant indicates the key was absent. Unwrapping in any case provides the current value unless an error occurs that prevents insertion. An insertion error will flag such a case.

Note that for brevity and convenience the user need not write the key to the lazy value compound literal as well. This function ensures the key in the compound literal matches the searched key.

Typedef Documentation

◆ ccc_handle_ordered_map

typedef struct ccc_homap_ ccc_handle_ordered_map

A self-optimizing data structure offering amortized O(lg N) search, insert, and erase.

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

A handle ordered map can be initialized on the stack, heap, or data segment at runtime or compile time.

◆ ccc_homap_elem

typedef struct ccc_homap_elem_ ccc_homap_elem

The intrusive element for the user defined type being stored in the map.

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_homap_handle

typedef union ccc_homap_handle_ ccc_homap_handle

A container specific handle used to implement the Handle Interface.

The Handle Interface offers efficient search and subsequent insertion, deletion, or value update based on the needs of the user.

Function Documentation

◆ ccc_hom_and_modify()

ccc_homap_handle * ccc_hom_and_modify	(	ccc_homap_handle *	h,
		ccc_update_fn *	fn
	)

Modifies the provided handle if it is Occupied.

Parameters

[in]	h	the handle obtained from a handle function or macro.
[in]	fn	an update function in which the auxiliary argument is unused.

Returns: the updated handle if it was Occupied or the unmodified vacant handle.

This function is intended to make the function chaining in the Handle Interface more succinct if the handle will be modified in place based on its own value without the need of the auxiliary argument a ccc_update_fn can provide.

◆ ccc_hom_and_modify_aux()

ccc_homap_handle * ccc_hom_and_modify_aux	(	ccc_homap_handle *	h,
		ccc_update_fn *	fn,
		void *	aux
	)

Modifies the provided handle if it is Occupied.

Parameters

[in]	h	the handle obtained from a handle function or macro.
[in]	fn	an update function that requires auxiliary data.
[in]	aux	auxiliary data required for the update.

Returns: the updated handle if it was Occupied or the unmodified vacant handle.

This function makes full use of a ccc_update_fn capability, meaning a complete ccc_update object will be passed to the update function callback.

◆ ccc_hom_at()

void * ccc_hom_at	(	ccc_handle_ordered_map const *	h,
		ccc_handle_i	i
	)

Returns a reference to the user data at the provided handle.

Parameters

[in]	h	a pointer to the map.
[in]	i	the stable handle obtained by the user.

Returns: a pointer to the user type stored at the specified handle or NULL if an out of range handle or handle representing no data is provided.

Warning: this function can only check if the handle value is in range. If a handle represents a slot that has been taken by a new element because the old one has been removed that new element data will be returned.; do not try to access data in the table manually with a handle. Always use this provided interface function when a reference to data is needed.

◆ ccc_hom_begin()

void * ccc_hom_begin ( ccc_handle_ordered_map const * hom )

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

Parameters

[in] hom a pointer to the map.

Returns: the oldest minimum element of the map.

◆ ccc_hom_capacity()

ccc_ucount ccc_hom_capacity ( ccc_handle_ordered_map const * hom )

Returns the capacity of the map representing total possible slots.

Parameters

[in] hom the map.

Returns: the capacity or an argument error is set if hom is NULL.

◆ ccc_hom_clear()

ccc_result ccc_hom_clear	(	ccc_handle_ordered_map *	hom,
		ccc_destructor_fn *	fn
	)

Frees all slots in the map for use without affecting capacity.

Parameters

[in]	hom	the map to be cleared.
[in]	fn	the destructor for each element. NULL can be passed if no maintenance is required on the elements in the map before their slots are forfeit.

If NULL is passed as the destructor function time is O(1), else O(size).

◆ ccc_hom_clear_and_free()

ccc_result ccc_hom_clear_and_free	(	ccc_handle_ordered_map *	hom,
		ccc_destructor_fn *	fn
	)

Frees all slots in the map and frees the underlying buffer.

Parameters

[in]	hom	the map to be cleared.
[in]	fn	the destructor for each element. NULL can be passed if no maintenance is required on the elements in the map before their slots are forfeit.

Returns: the result of free operation. If no alloc function is provided it is an error to attempt to free the buffer and a memory error is returned. Otherwise, an OK result is returned.

If NULL is passed as the destructor function time is O(1), else O(size).

◆ ccc_hom_contains()

ccc_tribool ccc_hom_contains	(	ccc_handle_ordered_map *	hom,
		void const *	key
	)

Searches the map for the presence of key.

Parameters

[in]	hom	the map to be searched.
[in]	key	pointer to the key matching the key type of the user struct.

Returns: true if the struct containing key is stored, false if not. Error if hom or key is NULL.

◆ ccc_hom_copy()

ccc_result ccc_hom_copy	(	ccc_handle_ordered_map *	dst,
		ccc_handle_ordered_map const *	src,
		ccc_alloc_fn *	fn
	)

Copy the map at source to destination.

Parameters

[in]	dst	the initialized destination for the copy of the src map.
[in]	src	the initialized source of the map.
[in]	fn	the allocation function to resize dst or NULL.

Returns: the result of the copy operation. If the destination capacity is less than the source capacity and no allocation function is provided an input error is returned. If resizing is required and resizing of dst fails a memory error is returned.

Note: dst must have capacity greater than or equal to src. If dst capacity is less than src, an allocation function must be provided with the fn argument.

Note that there are two ways to copy data from source to destination: provide sufficient memory and pass NULL as fn, or allow the copy function to take care of allocation for the copy.

Manual memory management with no allocation function provided.

#define HANDLE_ORDERED_MAP_USING_NAMESPACE_CCC
struct val
{
    homap_elem e;
    int key;
    int val;
};
static handle_ordered_map src
    = hom_init((static struct val[11]){}, e, key, key_cmp, NULL, NULL, 11);
insert_rand_vals(&src);
static handle_ordered_map dst
    = hom_init((static struct val[13]){}, e, key, key_cmp, NULL, NULL, 13);
ccc_result res = hom_copy(&dst, &src, NULL);

The above requires dst capacity be greater than or equal to src capacity. Here is memory management handed over to the copy function.

#define HANDLE_ORDERED_MAP_USING_NAMESPACE_CCC
struct val
{
    homap_elem e;
    int key;
    int val;
};
static handle_ordered_map src
    = hom_init((struct val *)NULL, e, key, key_cmp, std_alloc, NULL, 0);
insert_rand_vals(&src);
static handle_ordered_map dst
    = hom_init((struct val *)NULL, e, key, key_cmp, std_alloc, NULL, 0);
ccc_result res = hom_copy(&dst, &src, std_alloc);

The above allows dst to have a capacity less than that of the src as long as copy has been provided an allocation function to resize dst. Note that this would still work if copying to a destination that the user wants as a fixed size map.

#define HANDLE_ORDERED_MAP_USING_NAMESPACE_CCC
struct val
{
    homap_elem e;
    int key;
    int val;
};
static handle_ordered_map src
    = hom_init((struct val *)NULL, e, key, key_cmp, std_alloc, NULL);
insert_rand_vals(&src);
static handle_ordered_map dst
    = hom_init((struct val *)NULL, e, key, key_cmp, NULL, NULL, 0);
ccc_result res = hom_copy(&dst, &src, std_alloc);

The above sets up dst with fixed size while src is a dynamic map. Because an allocation function is provided, the dst is resized once for the copy and retains its fixed size after the copy is complete. This would require the user to manually free the underlying buffer at dst eventually if this method is used. Usually it is better to allocate the memory explicitly before the copy if copying between maps without allocation permission.

These options allow users to stay consistent across containers with their memory management strategies.

◆ ccc_hom_data()

void * ccc_hom_data ( ccc_handle_ordered_map const * hom )

Return a reference to the base of backing array. O(1).

Parameters

[in] hom a pointer to the map.

Returns: a reference to the base of the backing array.

Note: the reference is to the base of the backing array at index 0 with no consideration for the organization of map. However, all nodes of the map are guaranteed to be stored contiguously starting at index 1. Index 0 is reserved for the sentinel node.

Warning: it is the users responsibility to ensure that access to any data is within the capacity of the backing buffer.

◆ ccc_hom_end()

void * ccc_hom_end ( ccc_handle_ordered_map const * hom )

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

Parameters

[in] hom a pointer to the map.

Returns: the newest maximum element of the map.

◆ ccc_hom_equal_range()

ccc_range ccc_hom_equal_range	(	ccc_handle_ordered_map *	hom,
		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]	hom	a pointer to the map.
[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(&hom, &i->elem))
{}

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

◆ ccc_hom_equal_rrange()

ccc_rrange ccc_hom_equal_rrange	(	ccc_handle_ordered_map *	hom,
		void const *	rbegin_key,
		void const *	rend_key
	)

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

Parameters

[in]	hom	a pointer to the map.
[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(&hom, &i->elem))
{}

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

◆ ccc_hom_get_key_val()

ccc_handle_i ccc_hom_get_key_val	(	ccc_handle_ordered_map *	hom,
		void const *	key
	)

Returns a reference into the map at handle key.

Parameters

[in]	hom	the ordered map to search.
[in]	key	the key to search matching stored key type.

Returns: a view of the map handle if it is present, else NULL.

◆ ccc_hom_handle()

ccc_homap_handle ccc_hom_handle	(	ccc_handle_ordered_map *	hom,
		void const *	key
	)

Obtains a handle for the provided key in the map for future use.

Parameters

[in]	hom	the map to be searched.
[in]	key	the key used to search the map matching the stored key type.

Returns: a specialized handle for use with other functions in the Handle Interface.

Warning: the contents of a handle should not be examined or modified. Use the provided functions, only.

a handle is a search result that provides either an Occupied or Vacant handle in the map. An occupied handle signifies that the search was successful. A Vacant handle means the search was not successful but a handle is gained to where in the map such an element should be inserted.

a handle is rarely useful on its own. It should be passed in a functional style to subsequent calls in the Handle Interface.

◆ ccc_hom_handle_status()

ccc_handle_status ccc_hom_handle_status ( ccc_homap_handle const * h )

Obtain the handle status from a container handle.

Parameters

[in] h a pointer to the handle.

Returns: the status stored in the handle after the required action on the container completes. If h is NULL a handle 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_handle_status_msg() in ccc/types.h for more information on detailed handle statuses.

◆ ccc_hom_insert_error()

ccc_tribool ccc_hom_insert_error ( ccc_homap_handle const * h )

Provides the status of the handle should an insertion follow.

Parameters

[in] h the handle from a query to the table via function or macro.

Returns: true if a handle obtained from an insertion attempt failed to insert due to an allocation failure when allocation success was expected. Error if h is NULL.

◆ ccc_hom_insert_handle()

ccc_handle_i ccc_hom_insert_handle	(	ccc_homap_handle const *	h,
		ccc_homap_elem *	elem
	)

Inserts the provided handle invariantly.

Parameters

[in]	h	the handle returned from a call obtaining a handle.
[in]	elem	a handle to the struct the user intends to insert.

Returns: a pointer to the inserted element or NULL upon allocation failure.

This method can be used when the old value in the map does not need to be preserved. See the regular insert method if the old value is of interest.

◆ ccc_hom_insert_or_assign()

ccc_handle ccc_hom_insert_or_assign	(	ccc_handle_ordered_map *	hom,
		ccc_homap_elem *	key_val_handle
	)

Invariantly inserts or overwrites a user struct into the map.

Parameters

[in]	hom	a pointer to the handle hash map.
[in]	key_val_handle	the handle to the wrapping user struct key value.

Returns: a handle. If Occupied a handle was overwritten by the new key value. If Vacant no prior map handle existed.

Note that this function can be used when the old user type is not needed but the information regarding its presence is helpful.

◆ ccc_hom_is_empty()

ccc_tribool ccc_hom_is_empty ( ccc_handle_ordered_map const * hom )

Returns the size status of the map.

Parameters

[in] hom the map.

Returns: true if empty else false. Error if hom is NULL.

◆ ccc_hom_next()

void * ccc_hom_next	(	ccc_handle_ordered_map const *	hom,
		ccc_homap_elem const *	iter_handle
	)

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

Parameters

[in]	hom	a pointer to the map.
[in]	iter_handle	a pointer to the intrusive map element of the current iterator.

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

◆ ccc_hom_occupied()

ccc_tribool ccc_hom_occupied ( ccc_homap_handle const * h )

Returns the Vacant or Occupied status of the handle.

Parameters

[in] h the handle from a query to the map via function or macro.

Returns: true if the handle is occupied, false if not. Error if h is NULL.

◆ ccc_hom_or_insert()

ccc_handle_i ccc_hom_or_insert	(	ccc_homap_handle const *	h,
		ccc_homap_elem *	elem
	)

Inserts the struct with handle elem if the handle is Vacant.

Parameters

[in]	h	the handle obtained via function or macro call.
[in]	elem	the handle to the struct to be inserted to a Vacant handle.

Returns: a pointer to handle in the map invariantly. NULL on error.

Because this functions takes a handle and inserts if it is Vacant, the only reason NULL shall be returned is when an insertion error occurs, usually due to a user struct allocation failure.

If no allocation is permitted, this function assumes the user struct wrapping elem has been allocated with the appropriate lifetime and scope by the user.

◆ ccc_hom_rbegin()

void * ccc_hom_rbegin ( ccc_handle_ordered_map const * hom )

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

Parameters

[in] hom a pointer to the map.

Returns: the oldest maximum element of the map.

◆ ccc_hom_remove()

ccc_handle ccc_hom_remove	(	ccc_handle_ordered_map *	hom,
		ccc_homap_elem *	out_handle
	)

Removes the key value in the map storing the old value, if present, in the struct containing out_handle provided by the user.

Parameters

[in]	hom	the pointer to the ordered map.
[out]	out_handle	the handle to the user type wrapping map elem.

Returns: the removed handle. If Occupied the struct containing out_handle holds the old value. If Vacant the key value pair was not stored in the map. If bad input is provided an input error is set.

Note that this function may write to the struct containing the second parameter and wraps it in a handle to provide information about the old value.

◆ ccc_hom_remove_handle()

ccc_handle ccc_hom_remove_handle ( ccc_homap_handle * h )

Remove the handle from the map if Occupied.

Parameters

[in] h a pointer to the map handle.

Returns: a handle containing no valid reference but information about removed element. If Occupied a handle in the map existed and was removed. If Vacant, no prior handle existed to be removed.

◆ ccc_hom_rend()

void * ccc_hom_rend ( ccc_handle_ordered_map const * hom )

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

Parameters

[in] hom a pointer to the map.

Returns: the newest minimum element of the map.

◆ ccc_hom_rnext()

void * ccc_hom_rnext	(	ccc_handle_ordered_map const *	hom,
		ccc_homap_elem const *	iter_handle
	)

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

Parameters

[in]	hom	a pointer to the map.
[in]	iter_handle	a pointer to the intrusive map element of the current iterator.

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

◆ ccc_hom_size()

ccc_ucount ccc_hom_size ( ccc_handle_ordered_map const * hom )

Returns the size of the map representing active slots.

Parameters

[in] hom the map.

Returns: the size of the map or an argument error is set if hom is NULL.

◆ ccc_hom_swap_handle()

ccc_handle ccc_hom_swap_handle	(	ccc_handle_ordered_map *	hom,
		ccc_homap_elem *	out_handle
	)

Invariantly inserts the key value wrapping key_val_handle.

Parameters

[in]	hom	the pointer to the ordered map.
[out]	out_handle	the handle to the user type wrapping map elem.

Returns: a handle. If Vacant, no prior element with key existed and the type wrapping out_handle remains unchanged. If Occupied the old value is written to the type wrapping out_handle and may be unwrapped to view. If more space is needed but allocation fails or has been forbidden, an insert error is set.

Note that this function may write to the struct containing out_handle and wraps it in a handle to provide information about the old value.

◆ ccc_hom_try_insert()

ccc_handle ccc_hom_try_insert	(	ccc_handle_ordered_map *	hom,
		ccc_homap_elem *	key_val_handle
	)

Attempts to insert the key value wrapping key_val_handle.

Parameters

[in]	hom	the pointer to the map.
[in]	key_val_handle	the handle to the user type wrapping map elem.

Returns: a handle. If Occupied, the handle contains a reference to the key value user type in the map and may be unwrapped. If Vacant the handle contains a reference to the newly inserted handle in the map. If more space is needed but allocation fails, an insert error is set.

◆ ccc_hom_unwrap()

ccc_handle_i ccc_hom_unwrap ( ccc_homap_handle const * h )

Unwraps the provided handle to obtain a view into the map element.

Parameters

[in] h the handle from a query to the map via function or macro.

Returns: a view into the table handle if one is present, or NULL.

◆ ccc_hom_validate()

ccc_tribool ccc_hom_validate ( ccc_handle_ordered_map const * hom )

Validation of invariants for the map.

Parameters

[in] hom the map to validate.

Returns: true if all invariants hold, false if corruption occurs. Error if home is NULL.

Initialization Interface

Membership Interface

Handle Interface

Iterator Interface

Container Types

Deallocation Interface

State Interface

Detailed Description

Macro Definition Documentation

◆ ccc_hom_and_modify_w

◆ ccc_hom_as

◆ ccc_hom_equal_range_r

◆ ccc_hom_equal_rrange_r

◆ ccc_hom_handle_r

◆ ccc_hom_init

◆ ccc_hom_insert_handle_w

◆ ccc_hom_insert_or_assign_w

◆ ccc_hom_or_insert_w

◆ ccc_hom_remove_handle_r

◆ ccc_hom_remove_r

◆ ccc_hom_swap_handle_r

◆ ccc_hom_try_insert_r

◆ ccc_hom_try_insert_w

Typedef Documentation

◆ ccc_handle_ordered_map

◆ ccc_homap_elem

◆ ccc_homap_handle

Function Documentation

◆ ccc_hom_and_modify()

◆ ccc_hom_and_modify_aux()

◆ ccc_hom_at()

◆ ccc_hom_begin()

◆ ccc_hom_capacity()

◆ ccc_hom_clear()

◆ ccc_hom_clear_and_free()

◆ ccc_hom_contains()

◆ ccc_hom_copy()

◆ ccc_hom_data()

◆ ccc_hom_end()

◆ ccc_hom_equal_range()

◆ ccc_hom_equal_rrange()

◆ ccc_hom_get_key_val()

◆ ccc_hom_handle()

◆ ccc_hom_handle_status()

◆ ccc_hom_insert_error()

◆ ccc_hom_insert_handle()

◆ ccc_hom_insert_or_assign()

◆ ccc_hom_is_empty()

◆ ccc_hom_next()

◆ ccc_hom_occupied()

◆ ccc_hom_or_insert()

◆ ccc_hom_rbegin()

◆ ccc_hom_remove()

◆ ccc_hom_remove_handle()

◆ ccc_hom_rend()

◆ ccc_hom_rnext()

◆ ccc_hom_size()

◆ ccc_hom_swap_handle()

◆ ccc_hom_try_insert()

◆ ccc_hom_unwrap()

◆ ccc_hom_validate()