The Handle Hash Map Interface. More...

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

Include dependency graph for handle_hash_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_hhm_init(memory_ptr, hhash_elem_field, key_field, hash_fn, key_eq_fn, alloc_fn, aux_data, capacity)
	Initialize a map with a buffer of types at compile time or runtime.

ccc_result	ccc_hhm_copy (ccc_handle_hash_map dst, ccc_handle_hash_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_hhm_as(handle_hash_map_ptr, type_name, handle_i...) ccc_impl_hhm_as(handle_hash_map_ptr, type_name, handle_i)
	Returns a reference to the user type in the table at the handle.

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

ccc_tribool	ccc_hhm_contains (ccc_handle_hash_map h, void const key)
	Searches the table for the presence of key.

ccc_handle_i	ccc_hhm_get_key_val (ccc_handle_hash_map h, void const key)
	Returns a handle to the element stored at key if present.

Handle Interface
Obtain and operate on container entries for efficient queries when non-trivial control flow is needed. A handle is a stable index to data in the table. For the handle hash map a valid handle will always be non-zero. This allows for the user to rely on truthy/falsey logic if needed: this is similar to valid pointers vs the NULL pointer.
#define	ccc_hhm_swap_handle_r(handle_hash_map_ptr, out_handle_ptr)
	Invariantly inserts the key value wrapping out_handle_ptr.

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

#define	ccc_hhm_try_insert_r(handle_hash_map_ptr, key_val_handle_ptr)
	Attempts to insert the key value wrapping key_val_handle_ptr.

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

#define	ccc_hhm_insert_or_assign_r(handle_hash_map_ptr, key_val_handle_ptr)
	Invariantly inserts or overwrites a user struct into the table.

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

#define	ccc_hhm_handle_r(handle_hash_map_ptr, key_ptr)
	Obtains a handle for the provided key in the table for future use.

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

#define	ccc_hhm_or_insert_w(handle_hash_map_handle_ptr, lazy_key_value...) ccc_impl_hhm_or_insert_w(handle_hash_map_handle_ptr, lazy_key_value)
	lazily insert the desired key value into the handle if it is Vacant.

#define	ccc_hhm_insert_handle_w(handle_hash_map_handle_ptr, lazy_key_value...) ccc_impl_hhm_insert_handle_w(handle_hash_map_handle_ptr, lazy_key_value)
	write the contents of the compound literal lazy_key_value to a slot.

#define	ccc_hhm_remove_handle_r(handle_hash_map_handle_ptr)
	Remove the handle from the table if Occupied.

ccc_handle	ccc_hhm_swap_handle (ccc_handle_hash_map h, ccc_hhmap_elem out_handle)
	Invariantly inserts the key value wrapping out_handle.

ccc_handle	ccc_hhm_remove (ccc_handle_hash_map h, ccc_hhmap_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_handle	ccc_hhm_try_insert (ccc_handle_hash_map h, ccc_hhmap_elem key_val_handle)
	Attempts to insert the key value wrapping key_val_handle.

ccc_handle	ccc_hhm_insert_or_assign (ccc_handle_hash_map h, ccc_hhmap_elem key_val_handle)
	Invariantly inserts or overwrites a user struct into the table.

ccc_hhmap_handle	ccc_hhm_handle (ccc_handle_hash_map h, void const key)
	Obtains a handle for the provided key in the table for future use.

ccc_hhmap_handle *	ccc_hhm_and_modify (ccc_hhmap_handle e, ccc_update_fn fn)
	Modifies the provided handle if it is Occupied.

ccc_hhmap_handle *	ccc_hhm_and_modify_aux (ccc_hhmap_handle e, ccc_update_fn fn, void *aux)
	Modifies the provided handle if it is Occupied.

ccc_handle_i	ccc_hhm_or_insert (ccc_hhmap_handle const e, ccc_hhmap_elem elem)
	Inserts the struct with handle elem if the handle is Vacant.

ccc_handle_i	ccc_hhm_insert_handle (ccc_hhmap_handle const e, ccc_hhmap_elem elem)
	Inserts the provided handle invariantly.

ccc_handle	ccc_hhm_remove_handle (ccc_hhmap_handle const *e)
	Remove the handle from the table if Occupied.

ccc_handle_i	ccc_hhm_unwrap (ccc_hhmap_handle const *e)
	Unwraps the provided handle to obtain a handle index.

ccc_tribool	ccc_hhm_occupied (ccc_hhmap_handle const *e)
	Returns the Vacant or Occupied status of the handle.

ccc_tribool	ccc_hhm_insert_error (ccc_hhmap_handle const *e)
	Provides the status of the handle should an insertion follow.

ccc_handle_status	ccc_hhm_handle_status (ccc_hhmap_handle const *e)
	Obtain the handle status from a container handle.

Container Types
Types available in the container interface.
typedef struct ccc_hhmap_	ccc_handle_hash_map
	A container for storing key-value structures defined by the user in a contiguous buffer.

typedef struct ccc_hhmap_elem_	ccc_hhmap_elem
	An intrusive element for a user provided type.

typedef union ccc_hhmap_handle_	ccc_hhmap_handle
	A container specific handle used to implement the Handle Interface.

Deallocation Interface
Destroy the container.
ccc_result	ccc_hhm_clear (ccc_handle_hash_map h, ccc_destructor_fn fn)
	Frees all slots in the table for use without affecting capacity.

ccc_result	ccc_hhm_clear_and_free (ccc_handle_hash_map h, ccc_destructor_fn fn)
	Frees all slots in the table and frees the underlying buffer.

Iterator Interface
Obtain and manage iterators over the container.
ccc_hhmap_handle	ccc_hhm_begin (ccc_handle_hash_map const *h)
	Obtains a handle to the first element in the table.

ccc_result	ccc_hhm_next (ccc_hhmap_handle *iter)
	Advances the iterator to the next occupied table handle.

ccc_tribool	ccc_hhm_end (ccc_hhmap_handle const *iter)
	Check if the current handle iterator has reached the end.

State Interface
Obtain the container state.
ccc_tribool	ccc_hhm_is_empty (ccc_handle_hash_map const *h)
	Returns the size status of the table.

ccc_ucount	ccc_hhm_size (ccc_handle_hash_map const *h)
	Returns the size of the table representing active slots.

ccc_ucount	ccc_hhm_next_prime (size_t n)
	Helper to find a prime number if needed.

ccc_ucount	ccc_hhm_capacity (ccc_handle_hash_map const *h)
	Return the full capacity of the backing storage.

void *	ccc_hhm_data (ccc_handle_hash_map const *h)
	Return a reference to the base of backing array. O(1).

ccc_tribool	ccc_hhm_validate (ccc_handle_hash_map const *h)
	Validation of invariants for the hash table.

Detailed Description

The Handle Hash Map Interface.

A Handle Hash Map stores elements by hash value and allows the user to retrieve them by key in amortized O(1) while offering handle stability. A handle is an index into a slot of the table where the user data is originally placed upon insertion. It is guaranteed to remain in the same slot until deletion, even if the table is resized by subsequent insertions or deletions of other elements occur. This comes at a slight space and implementation complexity cost when compared to the standard flat hash map offered in the collection, especially during resizing operations. However, it is more beneficial for large structs and fixed table sizes to use this version. The benefits are that when the handles exposed in the interface are saved by the user they offer the similar guarantees as pointer stability except with the benefits of tightly grouped data in one array accessed via index.

For containers in this collection the user may have a variety of memory sources backing the containers. This container aims to be an equivalent stand in for std::unordered_map, absl::node_hash_map, or manually managing pointers in a flat hash map under the constraints of the C Container Collection. Instead of forcing the user to manage separate allocations for nodes that need to remain in the same location, this container will ensure any inserted element remains at the same index in the table allowing complex container compositions and any underlying source of memory specified at compile time or runtime. This container therefore exposes an interface that mainly returns stable handle indices and these should be what the user stores and accesses when needed. Only expose the underlying pointer to data with the provided access function when needed and store the handle for all other purposes.

A handle hash map requires the user to provide a struct with known key and handle hash element fields as well as a hash function and key comparator function. The hash function should be well tailored to the key being stored in the table to prevent collisions. Currently, the handle hash map does not offer any default hash functions or hash strengthening algorithms so strong hash functions should be obtained by the user for the data set.

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

#define HANDLE_HASH_MAP_USING_NAMESPACE_CCC

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

Macro Definition Documentation

◆ ccc_hhm_and_modify_w

#define ccc_hhm_and_modify_w	(	handle_hash_map_handle_ptr,
		type_name,
		closure_over_T...
	)

Value:

    &(ccc_hhmap_handle)                                                        \
    {                                                                          \
        ccc_impl_hhm_and_modify_w(handle_hash_map_handle_ptr, type_name,       \
                                  closure_over_T)                              \
    }

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

Parameters

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

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

#define HANDLE_HASH_MAP_USING_NAMESPACE_CCC
// Increment the key k if found otherwise do nothing.
hhmap_handle *e = hhm_and_modify_w(handle_r(&hhm, &k), word, T->cnt++;);
 
// Increment the key k if found otherwise insert a default value.
handle_i w = hhm_or_insert_w(hhm_and_modify_w(handle_r(&hhm, &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_hhm_as

#define ccc_hhm_as	(	handle_hash_map_ptr,
		type_name,
		handle_i...
	)	ccc_impl_hhm_as(handle_hash_map_ptr, type_name, handle_i)

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

Parameters

[in]	handle_hash_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_hhm_handle_r

#define ccc_hhm_handle_r	(	handle_hash_map_ptr,
		key_ptr
	)

Value:

    &(ccc_hhmap_handle)                                                        \
    {                                                                          \
        ccc_hhm_handle((handle_hash_map_ptr), (key_ptr)).impl_                 \
    }

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

Parameters

[in]	handle_hash_map_ptr	the hash table to be searched.
[in]	key_ptr	the key used to search the table matching the stored key type.

Returns: a compound literal handle to a specialized hash 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 table. An occupied handle signifies that the search was successful. A Vacant handle means the search was not successful but we now have a handle to where in the table such an element should be inserted.

A handle is most often passed in a functional style to subsequent calls in the Handle Interface.

◆ ccc_hhm_init

#define ccc_hhm_init	(	memory_ptr,
		hhash_elem_field,
		key_field,
		hash_fn,
		key_eq_fn,
		alloc_fn,
		aux_data,
		capacity
	)

Value:

ccc_impl_hhm_init(memory_ptr, hhash_elem_field, key_field, hash_fn, \

key_eq_fn, alloc_fn, aux_data, capacity)

Initialize a map with a buffer of types at compile time or runtime.

Parameters

[in]	memory_ptr	the pointer to the backing buffer array of user types. May be NULL if the user provides a allocation function. The buffer will be interpreted in units of type size that the user intends to store. buffer is provided and an allocation function is given.
[in]	hhash_elem_field	the name of the hhmap_elem field.
[in]	key_field	the field of the struct used for key storage. resizing is allowed.
[in]	hash_fn	the ccc_hash_fn function the user desires for the table.
[in]	key_eq_fn	the ccc_key_eq_fn the user intends to use.
[in]	alloc_fn	the allocation function for resizing or NULL if no
[in]	aux_data	auxiliary data that is needed for hashing or comparison.
[in]	capacity	the starting capacity of the provided buffer or 0 if no

Returns: the handle hash map directly initialized on the right hand side of the equality operator (i.e. ccc_handle_hash_map fh = ccc_hhm_init(...);)

◆ ccc_hhm_insert_handle_w

#define ccc_hhm_insert_handle_w	(	handle_hash_map_handle_ptr,
		lazy_key_value...
	)	ccc_impl_hhm_insert_handle_w(handle_hash_map_handle_ptr, lazy_key_value)

write the contents of the compound literal lazy_key_value to a slot.

Parameters

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

Returns: a non-zero handle to the newly inserted or overwritten user type. 0 is returned if resizing is required but fails or is not allowed.

◆ ccc_hhm_insert_or_assign_r

#define ccc_hhm_insert_or_assign_r	(	handle_hash_map_ptr,
		key_val_handle_ptr
	)

Value:

    &(ccc_handle)                                                              \
    {                                                                          \
        ccc_hhm_insert_or_assign((handle_hash_map_ptr), (key_val_handle))      \
            .impl_                                                             \
    }

Invariantly inserts or overwrites a user struct into the table.

Parameters

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

Returns: a compound literal handle to the current table element. If Occupied a handle was overwritten by the new key value. If Vacant no prior table 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_hhm_insert_or_assign_w

#define ccc_hhm_insert_or_assign_w	(	handle_hash_map_ptr,
		key,
		lazy_value...
	)

Value:

    &(ccc_handle)                                                              \
    {                                                                          \
        ccc_impl_hhm_insert_or_assign_w(handle_hash_map_ptr, key, lazy_value)  \
    }

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

Parameters

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

Returns: a compound literal handle 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_hhm_or_insert_w

#define ccc_hhm_or_insert_w	(	handle_hash_map_handle_ptr,
		lazy_key_value...
	)	ccc_impl_hhm_or_insert_w(handle_hash_map_handle_ptr, lazy_key_value)

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

Parameters

[in]	handle_hash_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 non-zero handle index to the unwrapped user type in the handle, either the unmodified handle if the handle was Occupied or the newly inserted element if the handle was Vacant. 0 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_hhm_remove_handle_r

#define ccc_hhm_remove_handle_r ( handle_hash_map_handle_ptr )

Value:

    &(ccc_handle)                                                              \
    {                                                                          \
        ccc_hhm_remove_handle((handle_hash_map_handle_ptr)).impl_              \
    }

Remove the handle from the table if Occupied.

Parameters

[in] handle_hash_map_handle_ptr a pointer to the table handle.

Returns: a handle containing 0. If Occupied a handle in the table existed and was removed. If Vacant, no prior handle existed to be removed.

If the old table element is needed see the remove method.

◆ ccc_hhm_remove_r

#define ccc_hhm_remove_r	(	handle_hash_map_ptr,
		out_handle_ptr
	)

Value:

    &(ccc_handle)                                                              \
    {                                                                          \
        ccc_hhm_remove((handle_hash_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_ptr provided by the user.

Parameters

[in]	handle_hash_map_ptr	the pointer to the handle hash map.
[out]	out_handle_ptr	the handle to the user type wrapping hhash elem.

Returns: a compound literal handle handle with a status indicating if the element searched existed and has been removed from the table. Unwrapping will result in NULL. If an old element existed it is copied to the struct wrapping out_handle_ptr.

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_hhm_swap_handle_r

#define ccc_hhm_swap_handle_r	(	handle_hash_map_ptr,
		out_handle_ptr
	)

Value:

    &(ccc_handle)                                                              \
    {                                                                          \
        ccc_hhm_swap_handle((handle_hash_map_ptr), (out_handle_ptr)).impl_     \
    }

Invariantly inserts the key value wrapping out_handle_ptr.

Parameters

[in]	handle_hash_map_ptr	the pointer to the handle hash map.
[out]	out_handle_ptr	the handle to the user type wrapping hhash elem.

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

Note: this function may write to the struct containing the second parameter.

◆ ccc_hhm_try_insert_r

#define ccc_hhm_try_insert_r	(	handle_hash_map_ptr,
		key_val_handle_ptr
	)

Value:

    &(ccc_handle)                                                              \
    {                                                                          \
        ccc_hhm_try_insert((handle_hash_map_ptr), (key_val_handle_ptr)).impl_  \
    }

Attempts to insert the key value wrapping key_val_handle_ptr.

Parameters

[in]	handle_hash_map_ptr	the pointer to the handle hash map.
[in]	key_val_handle_ptr	the handle to the user type wrapping hhash elem.

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

◆ ccc_hhm_try_insert_w

#define ccc_hhm_try_insert_w	(	handle_hash_map_ptr,
		key,
		lazy_value...
	)

Value:

    &(ccc_handle)                                                              \
    {                                                                          \
        ccc_impl_hhm_try_insert_w(handle_hash_map_ptr, key, lazy_value)        \
    }

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

Parameters

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

Returns: a compound literal handle 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.

Warning: ensure the key type matches the type stored in table as the key. For example, if the key is of type int and a size_t is passed as the variable to the key argument, adjacent bytes of the struct will be overwritten.

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_hash_map

typedef struct ccc_hhmap_ ccc_handle_hash_map

A container for storing key-value structures defined by the user in a contiguous buffer.

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

◆ ccc_hhmap_elem

typedef struct ccc_hhmap_elem_ ccc_hhmap_elem

An intrusive element for a user provided type.

Because the hash map is flat, data is always copied from the provided type into the table.

◆ ccc_hhmap_handle

typedef union ccc_hhmap_handle_ ccc_hhmap_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_hhm_and_modify()

ccc_hhmap_handle * ccc_hhm_and_modify	(	ccc_hhmap_handle *	e,
		ccc_update_fn *	fn
	)

Modifies the provided handle if it is Occupied.

Parameters

[in]	e	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_hhm_and_modify_aux()

ccc_hhmap_handle * ccc_hhm_and_modify_aux	(	ccc_hhmap_handle *	e,
		ccc_update_fn *	fn,
		void *	aux
	)

Modifies the provided handle if it is Occupied.

Parameters

[in]	e	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_hhm_at()

void * ccc_hhm_at	(	ccc_handle_hash_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_hhm_begin()

ccc_hhmap_handle ccc_hhm_begin ( ccc_handle_hash_map const * h )

Obtains a handle to the first element in the table.

Parameters

[in] h the table to iterate through.

Returns: a container specific handle that interface functions will accept.

Warning: erasing or inserting during iteration may result in repeating or unexpected iteration orders.

Iteration starts from index 0 by capacity of the table so iteration order is not obvious to the user, nor should any specific order be relied on.

◆ ccc_hhm_capacity()

ccc_ucount ccc_hhm_capacity ( ccc_handle_hash_map const * h )

Return the full capacity of the backing storage.

Parameters

[in] h the hash table.

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

◆ ccc_hhm_clear()

ccc_result ccc_hhm_clear	(	ccc_handle_hash_map *	h,
		ccc_destructor_fn *	fn
	)

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

Parameters

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

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

◆ ccc_hhm_clear_and_free()

ccc_result ccc_hhm_clear_and_free	(	ccc_handle_hash_map *	h,
		ccc_destructor_fn *	fn
	)

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

Parameters

[in]	h	the table to be cleared.
[in]	fn	the destructor for each element. NULL can be passed if no maintenance is required on the elements in the table 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.

◆ ccc_hhm_contains()

ccc_tribool ccc_hhm_contains	(	ccc_handle_hash_map *	h,
		void const *	key
	)

Searches the table for the presence of key.

Parameters

[in]	h	the handle hash table 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 h or key is NULL.

◆ ccc_hhm_copy()

ccc_result ccc_hhm_copy	(	ccc_handle_hash_map *	dst,
		ccc_handle_hash_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 optional allocation function if resizing is needed.

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.

Warning: the stable handles to user data in src will not remain the same as those in dst if dst has a capacity greater than src. However, after the initial copy to dst the handles in dst are now stable at their current positions.

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_hash_MAP_USING_NAMESPACE_CCC
struct val
{
    hhmap_elem e;
    int key;
    int val;
};
static handle_hash_map src
    = hhm_init((static struct val[11]){}, e, key, hhmap_int_to_u64,
               hhmap_id_eq, NULL, NULL, 11);
insert_rand_vals(&src);
static handle_hash_map dst
    = hhm_init((static struct val[13]){}, e, key, hhmap_int_to_u64,
               hhmap_id_eq, NULL, NULL, 13);
ccc_result res = hhm_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_hash_MAP_USING_NAMESPACE_CCC
struct val
{
    hhmap_elem e;
    int key;
    int val;
};
static handle_hash_map src
    = hhm_init((struct val*)NULL, e, key, hhmap_int_to_u64, hhmap_id_eq,
               NULL, 0);
insert_rand_vals(&src);
static handle_hash_map dst
    = hhm_init((struct val*)NULL, e, key, hhmap_int_to_u64, hhmap_id_eq,
               NULL, NULL, 0);
ccc_result res = hhm_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_hash_MAP_USING_NAMESPACE_CCC
struct val
{
    hhmap_elem e;
    int key;
    int val;
};
static handle_hash_map src
    = hhm_init((struct val*)NULL, e, key, hhmap_int_to_u64, hhmap_id_eq,
               NULL, NULL, 0);
insert_rand_vals(&src);
static handle_hash_map dst
    = hhm_init((struct val*)NULL, e, key, hhmap_int_to_u64, hhmap_id_eq,
               NULL, NULL, 0);
ccc_result res = hhm_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_hhm_data()

void * ccc_hhm_data ( ccc_handle_hash_map const * h )

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

Parameters

[in] h 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.

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

◆ ccc_hhm_end()

ccc_tribool ccc_hhm_end ( ccc_hhmap_handle const * iter )

Check if the current handle iterator has reached the end.

Parameters

[in] iter a pointer to the current handle iterator.

Returns: true if the handle iterator has reached the end of the table and iteration should stop, false if the iterator is valid and iteration should continue. Error if iter is NULL.

Warning: if iter has reached the end unwrapping it will result in 0 or invalid handles and NULL references.

◆ ccc_hhm_get_key_val()

ccc_handle_i ccc_hhm_get_key_val	(	ccc_handle_hash_map *	h,
		void const *	key
	)

Returns a handle to the element stored at key if present.

Parameters

[in]	h	the handle hash map to search.
[in]	key	the key to search matching stored key type.

Returns: a non-zero handle if present, otherwise 0 (falsey).

◆ ccc_hhm_handle()

ccc_hhmap_handle ccc_hhm_handle	(	ccc_handle_hash_map *	h,
		void const *	key
	)

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

Parameters

[in]	h	the hash table to be searched.
[in]	key	the key used to search the table matching the stored key type.

Returns: a specialized hash 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 element in the table. An occupied handle signifies that the search was successful. A Vacant handle means the search was not successful but we now have a handle to where in the table 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_hhm_handle_status()

ccc_handle_status ccc_hhm_handle_status ( ccc_hhmap_handle const * e )

Obtain the handle status from a container handle.

Parameters

[in] e a pointer to the handle.

Returns: the status stored in the handle after the required action on the container completes. If e 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_hhm_insert_error()

ccc_tribool ccc_hhm_insert_error ( ccc_hhmap_handle const * e )

Provides the status of the handle should an insertion follow.

Parameters

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

Returns: true if the next insertion of a new element will cause an error. Error if e is NULL.

Table resizing occurs upon calls to handle functions/macros or when trying to insert a new element directly. This is to provide stable entries from the time they are obtained to the time they are used in functions they are passed to (i.e. the idiomatic or_insert(handle(...)...)).

However, if a Vacant handle is returned and then a subsequent insertion function is used, it will not work if resizing has failed and the return of those functions will indicate such a failure. One can also confirm an insertion error will occur from a handle with this function. For example, leaving this function in an assert for debug builds can be a helpful sanity check.

◆ ccc_hhm_insert_handle()

ccc_handle_i ccc_hhm_insert_handle	(	ccc_hhmap_handle const *	e,
		ccc_hhmap_elem *	elem
	)

Inserts the provided handle invariantly.

Parameters

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

Returns: a non-zero handle index to the inserted element or 0 upon a memory error in which the load factor would be exceeded when no allocation policy is defined or resizing failed to find more memory.

This method can be used when the old value in the table does not need to be preserved. See the regular insert method if the old value is of interest. If an error occurs during the insertion process due to memory limitations or a search error 0 is returned. Otherwise insertion should not fail.

◆ ccc_hhm_insert_or_assign()

ccc_handle ccc_hhm_insert_or_assign	(	ccc_handle_hash_map *	h,
		ccc_hhmap_elem *	key_val_handle
	)

Invariantly inserts or overwrites a user struct into the table.

Parameters

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

Returns: a handle to the current table element. If Occupied a handle was overwritten by the new key value. If Vacant no prior table 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_hhm_is_empty()

ccc_tribool ccc_hhm_is_empty ( ccc_handle_hash_map const * h )

Returns the size status of the table.

Parameters

[in] h the hash table.

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

◆ ccc_hhm_next()

ccc_result ccc_hhm_next ( ccc_hhmap_handle * iter )

Advances the iterator to the next occupied table handle.

Parameters

[out] iter the previous handle that acts as an iterator.

Returns: ok if the handle is successfully updated to represent the next element or an error if iter is NULL.

Warning: erasing or inserting during iteration may result in repeating or unexpected iteration orders, but the index remains valid for the table.

◆ ccc_hhm_next_prime()

ccc_ucount ccc_hhm_next_prime ( size_t n )

Helper to find a prime number if needed.

Parameters

[in] n the input that may or may not be prime.

Returns: the next larger prime number.

It is possible to use this hash table without an allocator by providing the buffer to be used for the underlying storage and preventing allocation. If such a backing store is used it would be best to ensure it is a prime number size to mitigate hash collisions.

◆ ccc_hhm_occupied()

ccc_tribool ccc_hhm_occupied ( ccc_hhmap_handle const * e )

Returns the Vacant or Occupied status of the handle.

Parameters

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

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

◆ ccc_hhm_or_insert()

ccc_handle_i ccc_hhm_or_insert	(	ccc_hhmap_handle const *	e,
		ccc_hhmap_elem *	elem
	)

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

Parameters

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

Returns: a non-zero handle index to handle in the table invariantly. 0 (falsey) on error.

Because this functions takes a handle and inserts if it is Vacant, the only reason 0 shall be returned is when an insertion error will occur, usually due to a resizing memory error. This can happen if the table is not allowed to resize because no allocation function is provided.

◆ ccc_hhm_remove()

ccc_handle ccc_hhm_remove	(	ccc_handle_hash_map *	h,
		ccc_hhmap_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]	h	the pointer to the handle hash map.
[out]	out_handle	the handle to the user type wrapping hhash elem.

Returns: a handle with a status indicating if the element searched existed and has been removed from the table. Unwrapping will result in NULL. If an old element existed it is copied to the struct wrapping out_handle.

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

ccc_handle ccc_hhm_remove_handle ( ccc_hhmap_handle const * e )

Remove the handle from the table if Occupied.

Parameters

[in] e a pointer to the table handle.

Returns: a handle containing 0. If Occupied a handle in the table existed and was removed. If Vacant, no prior handle existed to be removed.

If the old table element is needed see the remove method.

◆ ccc_hhm_size()

ccc_ucount ccc_hhm_size ( ccc_handle_hash_map const * h )

Returns the size of the table representing active slots.

Parameters

[in] h the hash table.

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

◆ ccc_hhm_swap_handle()

ccc_handle ccc_hhm_swap_handle	(	ccc_handle_hash_map *	h,
		ccc_hhmap_elem *	out_handle
	)

Invariantly inserts the key value wrapping out_handle.

Parameters

[in]	h	the pointer to the handle hash map.
[out]	out_handle	the handle to the user type wrapping hhash 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. If more space is needed but allocation fails or has been forbidden, an insert error is set. Unwrap to view the current table element.

Note: this function may write to the struct containing the second parameter.

◆ ccc_hhm_try_insert()

ccc_handle ccc_hhm_try_insert	(	ccc_handle_hash_map *	h,
		ccc_hhmap_elem *	key_val_handle
	)

Attempts to insert the key value wrapping key_val_handle.

Parameters

[in]	h	the pointer to the handle hash map.
[in]	key_val_handle	the handle to the user type wrapping hhash elem.

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

◆ ccc_hhm_unwrap()

ccc_handle_i ccc_hhm_unwrap ( ccc_hhmap_handle const * e )

Unwraps the provided handle to obtain a handle index.

Parameters

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

Returns: a non-zero handle index if the table element is Occupied, otherwise 0 (falsey).

◆ ccc_hhm_validate()

ccc_tribool ccc_hhm_validate ( ccc_handle_hash_map const * h )

Validation of invariants for the hash table.

Parameters

[in] h the table to validate.

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

Initialization Interface

Membership Interface

Handle Interface

Container Types

Deallocation Interface

Iterator Interface

State Interface

Detailed Description

Macro Definition Documentation

◆ ccc_hhm_and_modify_w

◆ ccc_hhm_as

◆ ccc_hhm_handle_r

◆ ccc_hhm_init

◆ ccc_hhm_insert_handle_w

◆ ccc_hhm_insert_or_assign_r

◆ ccc_hhm_insert_or_assign_w

◆ ccc_hhm_or_insert_w

◆ ccc_hhm_remove_handle_r

◆ ccc_hhm_remove_r

◆ ccc_hhm_swap_handle_r

◆ ccc_hhm_try_insert_r

◆ ccc_hhm_try_insert_w

Typedef Documentation

◆ ccc_handle_hash_map

◆ ccc_hhmap_elem

◆ ccc_hhmap_handle

Function Documentation

◆ ccc_hhm_and_modify()

◆ ccc_hhm_and_modify_aux()

◆ ccc_hhm_at()

◆ ccc_hhm_begin()

◆ ccc_hhm_capacity()

◆ ccc_hhm_clear()

◆ ccc_hhm_clear_and_free()

◆ ccc_hhm_contains()

◆ ccc_hhm_copy()

◆ ccc_hhm_data()

◆ ccc_hhm_end()

◆ ccc_hhm_get_key_val()

◆ ccc_hhm_handle()

◆ ccc_hhm_handle_status()

◆ ccc_hhm_insert_error()

◆ ccc_hhm_insert_handle()

◆ ccc_hhm_insert_or_assign()

◆ ccc_hhm_is_empty()

◆ ccc_hhm_next()

◆ ccc_hhm_next_prime()

◆ ccc_hhm_occupied()

◆ ccc_hhm_or_insert()

◆ ccc_hhm_remove()

◆ ccc_hhm_remove_handle()

◆ ccc_hhm_size()

◆ ccc_hhm_swap_handle()

◆ ccc_hhm_try_insert()

◆ ccc_hhm_unwrap()

◆ ccc_hhm_validate()