The Flat Hash Map Interface. More...

#include "private/private_flat_hash_map.h"
#include "types.h"

Include dependency graph for flat_hash_map.h:

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

Detailed Description

The Flat Hash Map Interface.

A Flat Hash Map stores elements in a contiguous array and allows the user to query the map by key in amortized O(1) time. Elements in the table may be copied and moved, especially when rehashing occurs, so no pointer stability is available in this implementation.

A flat hash map requires the user to provide a pointer to the map, a type, a key field, a hash function, and a key three way comparator function. The hasher should be well tailored to the key being stored in the table to prevent collisions. Good variety in the upper bits of the hashed value will also result in faster performance. Currently, the flat 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.

The current implementation will seek to use the best platform specific Single Instruction Multiple Data (SIMD) or Single Register Multiple Data (SRMD) instructions available. However, if for any reason the user wishes to use the most portable Single Register Multiple Data fallback implementation, there are many options.

To use the map as a set, when only keys are needed, wrap a type in a struct or union. For example a set of int could be represented by creating a type struct My_int {int key;};. All interface functions can then be used normally.

If building this library separately to include its library file, add the flag to the build (and read INSTALL.md for more details).

cmake --preset=clang-ccc -DCCC_FLAT_HASH_MAP_PORTABLE=ON

If an install location other than the release folder is desired don't forget to add the install prefix.

cmake --preset=clang-ccc -DCCC_FLAT_HASH_MAP_PORTABLE=ON \

-DCMAKE_INSTALL_PREFIX=/my/path/

If this library is being built as part of your project via CMake's FetchContent mechanism, or any other method, then define the flag as part of your configuration.

cmake --preset=my-preset -DCCC_FLAT_HASH_MAP_PORTABLE=ON

Or, add the flag to your CMakePresets.json.

"cacheVariables": {
    "CCC_FLAT_HASH_MAP_PORTABLE": "ON"
}

Or, enable it in your CMakeLists.txt after including the C Container Collection via CMake's FetchContent mechanism (see INSTALL.md).

target_compile_definitions(ccc PRIVATE CCC_FLAT_HASH_MAP_PORTABLE)

See the INSTALL.md file for more ways to configure the map for hosted and freestanding environments.

To shorten names in the interface, define the following preprocessor directive at the top of your file. The CCC_ prefix may then be omitted for only this container.

#define FLAT_HASH_MAP_USING_NAMESPACE_CCC

#include "ccc/flat_hash_map.h"

flat_hash_map.h

The Flat Hash Map Interface.

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

Initialization Interface
Initialize the container with memory and callbacks. When a fixed size map is required, the user must declare the type name and size of the map they will use. Subsequent functions that request an allocator can then be passed the empty allocator argument, `&(CCC_Allocator){}`.
#define	CCC_flat_hash_map_storage_for( user_type_compound_literal_array, optional_storage_specifier...)
	Create the underlying fixed size storage for a user declared compound literal array of the type the user intends to store.

#define	CCC_flat_hash_map_default(type_name, key_field, hasher...) CCC_private_flat_hash_map_default(type_name, key_field, hasher)
	Initialize a default empty map at compile time or runtime.

#define	CCC_flat_hash_map_for( type_name, key_field, hasher, capacity, map_pointer)
	Initialize a map of types at compile time or runtime.

#define	CCC_flat_hash_map_from( key_field, hasher, allocator, optional_capacity, array_compound_literal...)
	Initialize a dynamic map at runtime from an initializer list.

#define	CCC_flat_hash_map_with_capacity( type_name, key_field, hasher, allocator, capacity)
	Initialize a dynamic map at runtime with at least the specified capacity.

#define	CCC_flat_hash_map_with_storage( key_field, hasher, compound_literal, optional_storage_specifier...)
	Initialize a fixed map at compile time or runtime from its previously declared type using a compound literal with no allocation permissions or context.

CCC_Result	CCC_flat_hash_map_copy (CCC_Flat_hash_map destination, CCC_Flat_hash_map const source, CCC_Allocator const *allocator)
	Copy the map at source to destination.

CCC_Result	CCC_flat_hash_map_reserve (CCC_Flat_hash_map map, size_t to_add, CCC_Allocator const allocator)
	Reserve space required to add a specified number of elements to the map. If the current capacity is sufficient, do nothing.

Entry Interface
Obtain and operate on container entries for efficient queries when non-trivial control flow is needed.
#define	CCC_flat_hash_map_entry_wrap( map_pointer, key_pointer, allocator_pointer...)
	Obtains an entry for the provided key in the table for future use.

#define	CCC_flat_hash_map_and_modify_with( map_entry_pointer, closure_parameter, closure_over_closure_parameter...)
	Modify an Occupied entry with a closure over user type T.

#define	CCC_flat_hash_map_or_insert_with( map_entry_pointer, type_compound_literal...)
	lazily insert the desired key value into the entry if it is Vacant.

#define	CCC_flat_hash_map_insert_entry_with( map_entry_pointer, type_compound_literal...)
	write the contents of the compound literal type_compound_literal to a slot.

#define	CCC_flat_hash_map_swap_entry_wrap( map_pointer, type_pointer, allocator_pointer)
	Invariantly inserts the key value wrapping out_handle.

#define	CCC_flat_hash_map_remove_entry_wrap(map_entry_pointer)
	Remove the entry from the table if Occupied.

#define	CCC_flat_hash_map_try_insert_wrap( map_pointer, type_pointer, allocator_pointer...)
	Attempts to insert the key value wrapping key_val_array_pointer.

#define	CCC_flat_hash_map_try_insert_with( map_pointer, key, allocator_pointer, type_compound_literal...)
	lazily insert type_compound_literal into the map at key if key is absent.

#define	CCC_flat_hash_map_insert_or_assign_wrap( map_pointer, type_pointer, allocator_pointer...)
	Invariantly inserts or overwrites a user struct into the table.

#define	CCC_flat_hash_map_insert_or_assign_with( map_pointer, key, allocator_pointer, type_compound_literal...)
	Inserts a new key value pair or overwrites the existing entry.

#define	CCC_flat_hash_map_remove_key_value_wrap( map_pointer, type_output_pointer)
	Removes the key value in the map storing the old value, if present, in the struct containing out_array_pointer provided by the user.

CCC_Flat_hash_map_entry	CCC_flat_hash_map_entry (CCC_Flat_hash_map map, void const key, CCC_Allocator const *allocator)
	Obtains an entry for the provided key in the table for future use.

CCC_Flat_hash_map_entry *	CCC_flat_hash_map_and_modify (CCC_Flat_hash_map_entry entry, CCC_Modifier const modifier)
	Modifies the provided entry if it is Occupied.

void *	CCC_flat_hash_map_or_insert (CCC_Flat_hash_map_entry const entry, void const type)
	Inserts the struct with handle elem if the entry is Vacant.

void *	CCC_flat_hash_map_insert_entry (CCC_Flat_hash_map_entry const entry, void const type)
	Inserts the provided entry invariantly.

CCC_Entry	CCC_flat_hash_map_swap_entry (CCC_Flat_hash_map map, void type_output, CCC_Allocator const *allocator)
	Invariantly inserts the key value wrapping out_handle.

CCC_Entry	CCC_flat_hash_map_remove_entry (CCC_Flat_hash_map_entry const *entry)
	Remove the entry from the table if Occupied.

CCC_Entry	CCC_flat_hash_map_try_insert (CCC_Flat_hash_map map, void const type, CCC_Allocator const *allocator)
	Attempts to insert the key value wrapping key_val_handle.

CCC_Entry	CCC_flat_hash_map_insert_or_assign (CCC_Flat_hash_map map, void const type, CCC_Allocator const *allocator)
	Invariantly inserts or overwrites a user struct into the table.

CCC_Entry	CCC_flat_hash_map_remove_key_value (CCC_Flat_hash_map map, void type_output)
	Removes the key value in the map storing the old value, if present, in the struct containing out_handle provided by the user.

void *	CCC_flat_hash_map_unwrap (CCC_Flat_hash_map_entry const *entry)
	Unwraps the provided entry to obtain a view into the table element.

CCC_Tribool	CCC_flat_hash_map_occupied (CCC_Flat_hash_map_entry const *entry)
	Returns the Vacant or Occupied status of the entry.

CCC_Tribool	CCC_flat_hash_map_insert_error (CCC_Flat_hash_map_entry const *entry)
	Provides the status of the entry should an insertion follow.

CCC_Entry_status	CCC_flat_hash_map_entry_status (CCC_Flat_hash_map_entry const *entry)
	Obtain the entry status from a container entry.

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

typedef struct CCC_Flat_hash_map_entry	CCC_Flat_hash_map_entry
	A container specific entry used to implement the Entry Interface.

Membership Interface
Test membership or obtain references to stored user types directly.
CCC_Tribool	CCC_flat_hash_map_contains (CCC_Flat_hash_map const map, void const key)
	Searches the table for the presence of key.

void *	CCC_flat_hash_map_get_key_value (CCC_Flat_hash_map const map, void const key)
	Returns a reference into the table at entry key.

Deallocation Interface
Destroy the container.
CCC_Result	CCC_flat_hash_map_clear (CCC_Flat_hash_map map, CCC_Destructor const destructor)
	Frees all slots in the table for use without affecting capacity.

CCC_Result	CCC_flat_hash_map_clear_and_free (CCC_Flat_hash_map map, CCC_Destructor const destructor, CCC_Allocator const *allocator)
	Frees all slots in the table and frees the underlying buffer.

Iterator Interface
Obtain and manage iterators over the container.
void *	CCC_flat_hash_map_begin (CCC_Flat_hash_map const *map)
	Obtains a pointer to the first element in the table.

void *	CCC_flat_hash_map_next (CCC_Flat_hash_map const map, void const type_iterator)
	Advances the iterator to the next occupied table slot.

void *	CCC_flat_hash_map_end (CCC_Flat_hash_map const *map)
	Check the current iterator against the end for loop termination.

State Interface
Obtain the container state.
CCC_Tribool	CCC_flat_hash_map_is_empty (CCC_Flat_hash_map const *map)
	Returns the size status of the table.

CCC_Count	CCC_flat_hash_map_count (CCC_Flat_hash_map const *map)
	Returns the count of table occupied slots.

CCC_Count	CCC_flat_hash_map_capacity (CCC_Flat_hash_map const *map)
	Return the full capacity of the backing storage.

CCC_Tribool	CCC_flat_hash_map_validate (CCC_Flat_hash_map const *map)
	Validation of invariants for the hash table.

Macro Definition Documentation

◆ CCC_flat_hash_map_and_modify_with

#define CCC_flat_hash_map_and_modify_with	(	map_entry_pointer,
		closure_parameter,
		closure_over_closure_parameter...
	)

Value:

    &(                                                                         \
         struct { CCC_Flat_hash_map_entry private; }                           \
    ){CCC_private_flat_hash_map_and_modify_with(                               \
          map_entry_pointer, closure_parameter, closure_over_closure_parameter \
      )}                                                                       \
         .private

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

Parameters

[in]	map_entry_pointer	a pointer to the obtained entry.
[in]	closure_parameter	the named pointer type, for example `My_type * e` or `My_type const * e` with which to interpret an occupied entry.
[in]	closure_over_closure_parameter	the code to be run on the reference to user type, if Occupied. This may be a semicolon separated list of statements to execute on the typed pointer 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.

#define FLAT_HASH_MAP_USING_NAMESPACE_CCC
// Increment the count if found otherwise do nothing.
Flat_hash_map_entry *entry =
    flat_hash_map_and_modify_with(
        entry_wrap(&map, &k),
        Word * e,
        e->cnt++;
    );
// Increment the count if found otherwise insert a default value.
Word *w =
    flat_hash_map_or_insert_with(
        flat_hash_map_and_modify_with(
            entry_wrap(&flat_hash_map, &k),
            Word * e,
            { e->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. This means any function calls are lazily evaluated in the closure scope.

◆ CCC_flat_hash_map_default

#define CCC_flat_hash_map_default	(	type_name,
		key_field,
		hasher...
	)	CCC_private_flat_hash_map_default(type_name, key_field, hasher)

Initialize a default empty map at compile time or runtime.

Parameters

[in]	type_name	the name of the user defined type stored in the map.
[in]	key_field	the field of the struct used for key storage.
[in]	hasher	a pointer to the CCC_Hasher that configures the hash function, key comparator function, and context for both hashing and comparison.

Returns: the flat hash map directly initialized on the right hand side of the equality operator.

◆ CCC_flat_hash_map_entry_wrap

#define CCC_flat_hash_map_entry_wrap	(	map_pointer,
		key_pointer,
		allocator_pointer...
	)

Value:

    &(struct { CCC_Flat_hash_map_entry private; }){                            \
        CCC_flat_hash_map_entry(map_pointer, key_pointer, allocator_pointer)}  \
         .private

Obtains an entry for the provided key in the table for future use.

Parameters

[in]	map_pointer	the hash table to be searched.
[in]	key_pointer	the key used to search the table matching the stored key type.
[in]	allocator_pointer	the CCC_Allocator needed in case of resizing.

Returns: a compound literal reference to a specialized hash entry for use with other functions in the Entry Interface.

Note: The Entry interface aims to eliminate the need for two queries in a table if the user wishes to insert after obtaining an Entry. Therefore, obtaining an entry may force a rehash resize, even if the user chooses to forgo insertion later.

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

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

An entry is most often passed in a functional style to subsequent calls in the Entry Interface.

◆ CCC_flat_hash_map_for

#define CCC_flat_hash_map_for	(	type_name,
		key_field,
		hasher,
		capacity,
		map_pointer
	)

Value:

    CCC_private_flat_hash_map_for(                                             \
        type_name, key_field, hasher, capacity, map_pointer                    \
    )

Initialize a map of types at compile time or runtime.

Parameters

[in]	type_name	the name of the user defined type stored in the map.
[in]	key_field	the field of the struct used for key storage.
[in]	hasher	a CCC_Hasher that configures the hash function, key comparator function, and context for both hashing and comparison.
[in]	capacity	the capacity of a fixed size map or 0.
[in]	map_pointer	a pointer to a fixed map allocation or NULL.

Returns: the flat hash map directly initialized on the right hand side of the equality operator.

Initialize a static fixed size hash map at compile time that has no allocation permission or context data needed.

#define FLAT_HASH_MAP_USING_NAMESPACE_CCC
struct Val
{
    int key;
    int val;
};
static Flat_hash_map static_map = flat_hash_map_for(
    struct Val,
    key,
    ((CCC_Hasher){.hash = hash_int, .compare = key_order}),
    64,
    &flat_hash_map_storage_for((struct Val[64]){})
);

See other, more specific, initializers for less boilerplate.

◆ CCC_flat_hash_map_from

#define CCC_flat_hash_map_from	(	key_field,
		hasher,
		allocator,
		optional_capacity,
		array_compound_literal...
	)

Value:

    CCC_private_flat_hash_map_from(                                            \
        key_field,                                                             \
        hasher,                                                                \
        allocator,                                                             \
        optional_capacity,                                                     \
        array_compound_literal                                                 \
    )

Initialize a dynamic map at runtime from an initializer list.

Parameters

[in]	key_field	the field of the struct used for key storage.
[in]	hasher	a CCC_Hasher that configures the hash function, key comparator function, and context for both hashing and comparison.
[in]	allocator	a CCC_Allocator for resizing.
[in]	optional_capacity	optionally specify the capacity of the map if different from the size of the compound literal array initializer. If the capacity is greater than the size of the compound literal array initializer, it is respected and the capacity is reserved. If the capacity is less than the size of the compound array initializer, the compound literal array initializer size is set as the capacity. Therefore, 0 is valid if one is not concerned with the size of the underlying reservation.
[in]	array_compound_literal	a list of key value pairs of the type intended to be stored in the map, using array compound literal initialization syntax (e.g `(struct My_type[]){{.k = 0, .v 0}, {.k = 1, .v = 1}}`).

Returns: the flat hash map directly initialized on the right hand side of the equality operator (i.e. CCC_Flat_hash_map map = CCC_flat_hash_map_from(...);)

Warning: An allocation function is required. This initializer is only available for dynamic maps.; When duplicate keys appear in the initializer list, the last occurrence replaces earlier ones by value (all fields are overwritten).; If initialization fails, the map will be returned empty. All subsequent queries, insertions, or removals will indicate the error: either memory related or lack of an allocation function provided.

Initialize a dynamic hash table at run time. This example requires no context data for initialization.

#define FLAT_HASH_MAP_USING_NAMESPACE_CCC
struct Val
{
    int key;
    int val;
};
int
main(void)
{
    Flat_hash_map map = flat_hash_map_from(
        key,
        ((CCC_Hasher){.hash = hash_int, .compare = key_order}),
        std_allocator,
        0,
        (struct Val[]) {
            {.key = 1, .val = 1},
            {.key = 2, .val = 2},
            {.key = 3, .val = 3},
        },
    );
    return 0;
}

Only dynamic maps may be initialized this way due the inability of the hash map to protect its invariants from user error at compile time.

◆ CCC_flat_hash_map_insert_entry_with

#define CCC_flat_hash_map_insert_entry_with	(	map_entry_pointer,
		type_compound_literal...
	)

Value:

    CCC_private_flat_hash_map_insert_entry_with(                               \
        map_entry_pointer, type_compound_literal                               \
    )

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

Parameters

[in]	map_entry_pointer	a pointer to the obtained entry.
[in]	type_compound_literal	the compound literal to write to a new slot.

Returns: a reference to the newly inserted or overwritten user type. NULL is returned if resizing is required but fails or is not allowed.

◆ CCC_flat_hash_map_insert_or_assign_with

#define CCC_flat_hash_map_insert_or_assign_with	(	map_pointer,
		key,
		allocator_pointer,
		type_compound_literal...
	)

Value:

    &(struct { CCC_Entry private; }){                                          \
        CCC_private_flat_hash_map_insert_or_assign_with(                       \
            map_pointer, key, allocator_pointer, type_compound_literal         \
        )}                                                                     \
         .private

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

Parameters

[in]	map_pointer	the pointer to the flat hash map.
[in]	key	the key to be searched in the table.
[in]	allocator_pointer	the CCC_Allocator needed in case resizing is required.
[in]	type_compound_literal	the compound literal specifying the value.

Returns: a compound literal reference to the entry 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_flat_hash_map_insert_or_assign_wrap

#define CCC_flat_hash_map_insert_or_assign_wrap	(	map_pointer,
		type_pointer,
		allocator_pointer...
	)

Value:

    &(struct { CCC_Entry private; }){                                          \
        CCC_flat_hash_map_insert_or_assign(                                    \
            map_pointer, type_pointer, allocator_pointer                       \
        )}                                                                     \
         .private

Invariantly inserts or overwrites a user struct into the table.

Parameters

[in]	map_pointer	a pointer to the flat hash map.
[in]	type_pointer	the complete key and value type to be inserted.
[in]	allocator_pointer	the CCC_Allocator needed in case resizing is required.

Returns: a compound literal reference to the entry. If Occupied an entry was overwritten by the new key value. If Vacant no prior table entry 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_flat_hash_map_or_insert_with

#define CCC_flat_hash_map_or_insert_with	(	map_entry_pointer,
		type_compound_literal...
	)

Value:

    CCC_private_flat_hash_map_or_insert_with(                                  \
        map_entry_pointer, type_compound_literal                               \
    )

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

Parameters

[in]	map_entry_pointer	a pointer to the obtained entry.
[in]	type_compound_literal	the compound literal to construct in place if the entry is Vacant.

Returns: a reference to the unwrapped user type in the entry, either the unmodified reference if the entry was Occupied or the newly inserted element if the entry 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 entry is Occupied.

◆ CCC_flat_hash_map_remove_entry_wrap

#define CCC_flat_hash_map_remove_entry_wrap ( map_entry_pointer )

Value:

    &(struct { CCC_Entry private; }){                                          \
        CCC_flat_hash_map_remove_entry(map_entry_pointer)}                     \
         .private

Remove the entry from the table if Occupied.

Parameters

[in] map_entry_pointer a pointer to the table entry.

Returns: a compound liter to an entry containing NULL. If Occupied an entry in the table existed and was removed. If Vacant, no prior entry existed to be removed.

◆ CCC_flat_hash_map_remove_key_value_wrap

#define CCC_flat_hash_map_remove_key_value_wrap	(	map_pointer,
		type_output_pointer
	)

Value:

    &(struct { CCC_Entry private; }){                                          \
        CCC_flat_hash_map_remove_key_value(map_pointer, type_output_pointer)}  \
         .private

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

Parameters

[in]	map_pointer	the pointer to the flat hash map.
[out]	type_output_pointer	the complete key and value type to be removed

Returns: a compound literal reference to the removed entry. If Occupied it may be unwrapped to obtain the old key value pair. If Vacant the key value pair was not stored in the map. If bad input is provided an input error is set. If a previously stored value is returned it is safe to keep and modify this reference because the data has been written to the provided space.

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

◆ CCC_flat_hash_map_storage_for

#define CCC_flat_hash_map_storage_for	(	user_type_compound_literal_array,
		optional_storage_specifier...
	)

Value:

    CCC_private_flat_hash_map_storage_for(                                     \
        user_type_compound_literal_array, optional_storage_specifier           \
    )

Create the underlying fixed size storage for a user declared compound literal array of the type the user intends to store.

Parameters

[in]	user_type_compound_literal_array	a compound literal array of the type around which the map will be built. Must be a power of 2 capacity array.
[in]	optional_storage_specifier	a storage specifier for the backing struct of array storage may be added on newer compilers such as static.

Warning: This should rarely be used. If a fixed size map is desired simply use the CCC_flat_hash_map_with_storage() initializer. For dynamic maps, there are also many other options.

This macro is required to support the edge case for the user allocating a fixed size map dynamically from an allocator at runtime. In this case, the user needs access to the underlying map storage object to know how many bytes to allocate. See the below example.

struct Val
{
    int key;
    int val;
};
 
int
main(void)
{
    void *const storage = malloc(
        sizeof(CCC_flat_hash_map_storage_for((struct Val[4096]){}))
    );
    defer free(storage);
    CCC_Flat_hash_map hash_map = CCC_flat_hash_map_for(
        struct Val,
        key,
        hash_key,
        order_vals,
        NULL,
        NULL,
        4096,
        storage
    );
    return 0;
}

Usually, using a dynamic map and the reserve interface would be sufficient. However, the reserve interface only guarantees that at least the needed bytes are allocated. When the user must know the exact size of the backing object due to strict memory requirements, this is helpful. Such a use case may be rare, but must be supported by this container.

◆ CCC_flat_hash_map_swap_entry_wrap

#define CCC_flat_hash_map_swap_entry_wrap	(	map_pointer,
		type_pointer,
		allocator_pointer
	)

Value:

    &(struct { CCC_Entry private; }){                                          \
        CCC_flat_hash_map_swap_entry(                                          \
            map_pointer, type_pointer, allocator_pointer                       \
        )}                                                                     \
         .private

Invariantly inserts the key value wrapping out_handle.

Parameters

[in]	map_pointer	the pointer to the flat hash map.
[out]	type_pointer	the complete key and value type to be inserted.
[in]	allocator_pointer	the CCC_Allocator needed in case resizing is required.

Returns: a compound literal reference to an entry. If Vacant, no prior element with key existed and entry may be unwrapped to view the new insertion in the table. If Occupied the old value is written to type_output 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 the second parameter and wraps it in an entry to provide information about the old value.

◆ CCC_flat_hash_map_try_insert_with

#define CCC_flat_hash_map_try_insert_with	(	map_pointer,
		key,
		allocator_pointer,
		type_compound_literal...
	)

Value:

    &(struct { CCC_Entry private; }){                                          \
        CCC_private_flat_hash_map_try_insert_with(                             \
            map_pointer, key, allocator_pointer, type_compound_literal         \
        )}                                                                     \
         .private

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

Parameters

[in]	map_pointer	a pointer to the flat hash map.
[in]	key	the direct key r-value.
[in]	type_compound_literal	the compound literal specifying the value.
[in]	allocator_pointer	the CCC_Allocator needed in case resizing is required.

Returns: a compound literal reference to the entry 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 your key. For example, if your key is of type int and you pass a size_t variable to the key argument, you will overwrite adjacent bytes of your struct.

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_flat_hash_map_try_insert_wrap

#define CCC_flat_hash_map_try_insert_wrap	(	map_pointer,
		type_pointer,
		allocator_pointer...
	)

Value:

    &(struct { CCC_Entry private; }){                                          \
        CCC_flat_hash_map_try_insert(                                          \
            map_pointer, type_pointer, allocator_pointer                       \
        )}                                                                     \
         .private

Attempts to insert the key value wrapping key_val_array_pointer.

Parameters

[in]	map_pointer	the pointer to the flat hash map.
[in]	type_pointer	the complete key and value type to be inserted.
[in]	allocator_pointer	the CCC_Allocator needed in case resizing is required.

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

Warning: because this function returns a reference to a user type in the table any subsequent insertions or deletions invalidate this reference.

◆ CCC_flat_hash_map_with_capacity

#define CCC_flat_hash_map_with_capacity	(	type_name,
		key_field,
		hasher,
		allocator,
		capacity
	)

Value:

    CCC_private_flat_hash_map_with_capacity(                                   \
        type_name, key_field, hasher, allocator, capacity                      \
    )

Initialize a dynamic map at runtime with at least the specified capacity.

Parameters

[in]	type_name	the name of the type being stored in the map.
[in]	key_field	the field of the struct used for key storage.
[in]	hasher	a CCC_Hasher that configures the hash function, key comparator function, and context for both hashing and comparison.
[in]	allocator	a required CCC_Allocator for resizing.
[in]	capacity	the desired capacity for the map. A capacity of 0 results in an argument error and is a no-op after the map is initialized empty.

Returns: the flat hash map directly initialized on the right hand side of the equality operator.

Warning: An allocation function is required. This initializer is only available for dynamic maps.; If initialization fails all subsequent queries, insertions, or removals will indicate the error: either memory related or lack of an allocation function provided.

Initialize a dynamic hash table at run time. This example requires no context data for initialization.

#define FLAT_HASH_MAP_USING_NAMESPACE_CCC
struct Val
{
    int key;
    int val;
};
int
main(void)
{
    Flat_hash_map map = flat_hash_map_with_capacity(
        struct Val,
        key,
        ((CCC_Hasher){.hash = hash_int, .compare = key_order}),
        std_allocator,
        4096
    );
    return 0;
}

Only dynamic maps may be initialized this way as it simply combines the steps of initialization and reservation.

◆ CCC_flat_hash_map_with_storage

#define CCC_flat_hash_map_with_storage	(	key_field,
		hasher,
		compound_literal,
		optional_storage_specifier...
	)

Value:

    CCC_private_flat_hash_map_with_storage(                                    \
        key_field, hasher, compound_literal, optional_storage_specifier        \
    )

Initialize a fixed map at compile time or runtime from its previously declared type using a compound literal with no allocation permissions or context.

Parameters

[in]	key_field	the field of the struct used for key storage.
[in]	hasher	a CCC_Hasher that configures the hash function, key comparator function, and context for both hashing and comparison.
[in]	compound_literal	the compound literal array of a type provided by the user around which the struct of arrays backing storage for the map is built.
[in]	optional_storage_specifier	lifetime specifier of the backing struct of array storage, such as static, for the fixed size map in the scope at which it is allocated or declared.

Returns: the flat hash map directly initialized on the right hand side of the equality operator.

Note: This initializer will warn the user if the compound literal provided is not a power of two capacity.

Initialize a static fixed size hash map at compile time that has no allocation permission or context data needed.

#define FLAT_HASH_MAP_USING_NAMESPACE_CCC
struct Val
{
    int key;
    int val;
};
static Flat_hash_map static_map = flat_hash_map_with_storage(
    key,
    ((CCC_Hasher){.hash = hash_int, .compare = key_order}),
    (struct Val[64]){}
);

This saves on boilerplate compared to the raw initializer.

Typedef Documentation

◆ CCC_Flat_hash_map

typedef struct CCC_Flat_hash_map CCC_Flat_hash_map

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

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

◆ CCC_Flat_hash_map_entry

typedef struct CCC_Flat_hash_map_entry CCC_Flat_hash_map_entry

A container specific entry used to implement the Entry Interface.

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

Function Documentation

◆ CCC_flat_hash_map_and_modify()

CCC_Flat_hash_map_entry * CCC_flat_hash_map_and_modify	(	CCC_Flat_hash_map_entry *	entry,
		CCC_Modifier const *	modifier
	)

Modifies the provided entry if it is Occupied.

Parameters

[in]	entry	the entry obtained from an entry function or macro.
[in]	modifier	the CCC_Modifier to act on this entry element if Occupied.

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

◆ CCC_flat_hash_map_begin()

void * CCC_flat_hash_map_begin ( CCC_Flat_hash_map const * map )

Obtains a pointer to the first element in the table.

Parameters

[in] map the table to iterate through.

Returns: a pointer that can be cast directly to the user type that is stored.

Warning: erasing or inserting during iteration may invalidate iterators if resizing occurs which would lead to undefined behavior. O(capacity).

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

CCC_Count CCC_flat_hash_map_capacity ( CCC_Flat_hash_map const * map )

Return the full capacity of the backing storage.

Parameters

[in] map the hash table.

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

◆ CCC_flat_hash_map_clear()

CCC_Result CCC_flat_hash_map_clear	(	CCC_Flat_hash_map *	map,
		CCC_Destructor const *	destructor
	)

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

Parameters

[in]	map	the table to be cleared.
[in]	destructor	the CCC_Destructor to call on each element if needed. If &(CCC_Destructor){} is passed runtime is O(1), else O(capacity).

◆ CCC_flat_hash_map_clear_and_free()

CCC_Result CCC_flat_hash_map_clear_and_free	(	CCC_Flat_hash_map *	map,
		CCC_Destructor const *	destructor,
		CCC_Allocator const *	allocator
	)

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

Parameters

[in]	map	the table to be cleared.
[in]	destructor	the CCC_Destructor to call on each element if needed.
[in]	allocator	the CCC_Allocator to free the underlying storage.

Returns: the result of free operation. If &(CCC_Allocator){} 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_flat_hash_map_contains()

CCC_Tribool CCC_flat_hash_map_contains	(	CCC_Flat_hash_map const *	map,
		void const *	key
	)

Searches the table for the presence of key.

Parameters

[in]	map	the flat 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 map or key is NULL.

◆ CCC_flat_hash_map_copy()

CCC_Result CCC_flat_hash_map_copy	(	CCC_Flat_hash_map *	destination,
		CCC_Flat_hash_map const *	source,
		CCC_Allocator const *	allocator
	)

Copy the map at source to destination.

Parameters

[in]	destination	the initialized destination for the copy of the source map.
[in]	source	the initialized source of the map.
[in]	allocator	the CCC_Allocator for resizing if 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 destination fails a memory error is returned.

Note: destination must have capacity greater than or equal to source. If destination capacity is less than source, an allocation function must be provided with the allocate argument.

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

Manual memory management with no allocation function provided.

#define FLAT_HASH_MAP_USING_NAMESPACE_CCC
struct Val
{
    int key;
    int val;
};
Flat_hash_map source = flat_hash_map_with_storage(
    key,
    ((CCC_Hasher){.hash = hash_int, .compare = key_order}),
    (struct Val[64]){}
);
insert_rand_vals(&source);
Flat_hash_map destination = flat_hash_map_with_storage(
    key,
    ((CCC_Hasher){.hash = hash_int, .compare = key_order}),
    (struct Val[64]){}
);
CCC_Result res = flat_hash_map_copy(&destination, &source, NULL);

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

#define FLAT_HASH_MAP_USING_NAMESPACE_CCC
struct Val
{
    int key;
    int val;
};
Flat_hash_map source = flat_hash_map_default(
    struct Val,
    key,
    (CCC_Hasher){.hash = hash_int, .compare = key_order}
);
insert_rand_vals(&source, &std_allocator);
Flat_hash_map destination = flat_hash_map_default(
    struct Val,
    key,
    (CCC_Hasher){.hash = hash_int, .compare = key_order}
);
CCC_Result res = flat_hash_map_copy(&destination, &source, &std_allocator);

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

◆ CCC_flat_hash_map_count()

CCC_Count CCC_flat_hash_map_count ( CCC_Flat_hash_map const * map )

Returns the count of table occupied slots.

Parameters

[in] map the hash table.

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

◆ CCC_flat_hash_map_end()

void * CCC_flat_hash_map_end ( CCC_Flat_hash_map const * map )

Check the current iterator against the end for loop termination.

Parameters

[in] map the table being iterated upon.

Returns: the end address of the hash table.

Warning: It is undefined behavior to access or modify the end address.

◆ CCC_flat_hash_map_entry()

CCC_Flat_hash_map_entry CCC_flat_hash_map_entry	(	CCC_Flat_hash_map *	map,
		void const *	key,
		CCC_Allocator const *	allocator
	)

Obtains an entry for the provided key in the table for future use.

Parameters

[in]	map	the hash table to be searched.
[in]	key	the key used to search the table matching the stored key type.
[in]	allocator	the CCC_Allocator needed in case resizing is required.

Returns: a specialized hash entry for use with other functions in the Entry Interface.

Note: The Entry interface aims to eliminate the need for two queries in a table if the user wishes to insert after obtaining an Entry. Therefore, obtaining an entry may force a rehash resize, even if the user chooses to forgo insertion later.

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

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

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

◆ CCC_flat_hash_map_entry_status()

CCC_Entry_status CCC_flat_hash_map_entry_status ( CCC_Flat_hash_map_entry const * entry )

Obtain the entry status from a container entry.

Parameters

[in] entry a pointer to the entry.

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

◆ CCC_flat_hash_map_get_key_value()

void * CCC_flat_hash_map_get_key_value	(	CCC_Flat_hash_map const *	map,
		void const *	key
	)

Returns a reference into the table at entry key.

Parameters

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

Returns: a view of the table entry if it is present, else NULL.

◆ CCC_flat_hash_map_insert_entry()

void * CCC_flat_hash_map_insert_entry	(	CCC_Flat_hash_map_entry const *	entry,
		void const *	type
	)

Inserts the provided entry invariantly.

Parameters

[in]	entry	the entry returned from a call obtaining an entry.
[in]	type	the complete key and value type to be inserted.

Returns: a pointer to the inserted element or NULL 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 NULL is returned. Otherwise insertion should not fail.

◆ CCC_flat_hash_map_insert_error()

CCC_Tribool CCC_flat_hash_map_insert_error ( CCC_Flat_hash_map_entry const * entry )

Provides the status of the entry should an insertion follow.

Parameters

[in] entry the entry 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 entry is null.

Table resizing occurs upon calls to entry 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(entry(...)...)).

However, if a Vacant entry 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 an entry with this function. For example, leaving this function in an assert for debug builds can be a helpful sanity check.

◆ CCC_flat_hash_map_insert_or_assign()

CCC_Entry CCC_flat_hash_map_insert_or_assign	(	CCC_Flat_hash_map *	map,
		void const *	type,
		CCC_Allocator const *	allocator
	)

Invariantly inserts or overwrites a user struct into the table.

Parameters

[in]	map	a pointer to the flat hash map.
[in]	type	the complete key and value type to be inserted.
[in]	allocator	the CCC_Allocator needed in case resizing is required.

Returns: an entry. If Occupied an entry was overwritten by the new key value. If Vacant no prior table entry 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_flat_hash_map_is_empty()

CCC_Tribool CCC_flat_hash_map_is_empty ( CCC_Flat_hash_map const * map )

Returns the size status of the table.

Parameters

[in] map the hash table.

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

◆ CCC_flat_hash_map_next()

void * CCC_flat_hash_map_next	(	CCC_Flat_hash_map const *	map,
		void const *	type_iterator
	)

Advances the iterator to the next occupied table slot.

Parameters

[in]	map	the table being iterated upon.
[in]	type_iterator	the previous iterator.

Returns: a pointer that can be cast directly to the user type that is stored.

Warning: erasing or inserting during iteration may invalidate iterators if resizing occurs which would lead to undefined behavior. O(capacity).

◆ CCC_flat_hash_map_occupied()

CCC_Tribool CCC_flat_hash_map_occupied ( CCC_Flat_hash_map_entry const * entry )

Returns the Vacant or Occupied status of the entry.

Parameters

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

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

◆ CCC_flat_hash_map_or_insert()

void * CCC_flat_hash_map_or_insert	(	CCC_Flat_hash_map_entry const *	entry,
		void const *	type
	)

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

Parameters

[in]	entry	the entry obtained via function or macro call.
[in]	type	the complete key and value type to be inserted.

Returns: a pointer to entry in the table invariantly. NULL on error.

Because this functions takes an entry and inserts if it is Vacant, the only reason NULL 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_flat_hash_map_remove_entry()

CCC_Entry CCC_flat_hash_map_remove_entry ( CCC_Flat_hash_map_entry const * entry )

Remove the entry from the table if Occupied.

Parameters

[in] entry a pointer to the table entry.

Returns: an entry containing NULL. If Occupied an entry in the table existed and was removed. If Vacant, no prior entry existed to be removed.

◆ CCC_flat_hash_map_remove_key_value()

CCC_Entry CCC_flat_hash_map_remove_key_value	(	CCC_Flat_hash_map *	map,
		void *	type_output
	)

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]	map	the pointer to the flat hash map.
[out]	type_output	the complete key and value type to be removed

Returns: the removed entry. If Occupied it may be unwrapped to obtain the old key value pair. If Vacant the key value pair was not stored in the map. If bad input is provided an input error is set. If a previously stored value is returned it is safe to keep and modify this reference because the data has been written to the provided space.

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

◆ CCC_flat_hash_map_reserve()

CCC_Result CCC_flat_hash_map_reserve	(	CCC_Flat_hash_map *	map,
		size_t	to_add,
		CCC_Allocator const *	allocator
	)

Reserve space required to add a specified number of elements to the map. If the current capacity is sufficient, do nothing.

Parameters

[in]	map	a pointer to the hash map.
[in]	to_add	the number of elements to add to the map.
[in]	allocator	the CCC_Allocator for resizing if needed.

Returns: the result of the reserving operation, OK if successful or an error code to indicate the specific failure.

If the map has already been initialized with allocation permission simply provide the same function that was passed upon initialization.

◆ CCC_flat_hash_map_swap_entry()

CCC_Entry CCC_flat_hash_map_swap_entry	(	CCC_Flat_hash_map *	map,
		void *	type_output,
		CCC_Allocator const *	allocator
	)

Invariantly inserts the key value wrapping out_handle.

Parameters

[in]	map	the pointer to the flat hash map.
[out]	type_output	the complete key and value type to be inserted.
[in]	allocator	the CCC_Allocator needed in case resizing is required.

Returns: an entry. If Vacant, no prior element with key existed and entry may be unwrapped to view the new insertion in the table. If Occupied the old value is written to type_output 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 the second parameter and wraps it in an entry to provide information about the old value.

◆ CCC_flat_hash_map_try_insert()

CCC_Entry CCC_flat_hash_map_try_insert	(	CCC_Flat_hash_map *	map,
		void const *	type,
		CCC_Allocator const *	allocator
	)

Attempts to insert the key value wrapping key_val_handle.

Parameters

[in]	map	the pointer to the flat hash map.
[in]	type	the complete key and value type to be inserted.
[in]	allocator	the CCC_Allocator needed in case resizing is required.

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

Warning: because this function returns a reference to a user type in the table any subsequent insertions or deletions invalidate this reference.

◆ CCC_flat_hash_map_unwrap()

void * CCC_flat_hash_map_unwrap ( CCC_Flat_hash_map_entry const * entry )

Unwraps the provided entry to obtain a view into the table element.

Parameters

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

Returns: an view into the table entry if one is present, or NULL.

◆ CCC_flat_hash_map_validate()

CCC_Tribool CCC_flat_hash_map_validate ( CCC_Flat_hash_map const * map )

Validation of invariants for the hash table.

Parameters

[in] map the table to validate.

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

Detailed Description

Initialization Interface

Entry Interface

Container Types

Membership Interface

Deallocation Interface

Iterator Interface

State Interface

Macro Definition Documentation

◆ CCC_flat_hash_map_and_modify_with

◆ CCC_flat_hash_map_default

◆ CCC_flat_hash_map_entry_wrap

◆ CCC_flat_hash_map_for

◆ CCC_flat_hash_map_from

◆ CCC_flat_hash_map_insert_entry_with

◆ CCC_flat_hash_map_insert_or_assign_with

◆ CCC_flat_hash_map_insert_or_assign_wrap

◆ CCC_flat_hash_map_or_insert_with

◆ CCC_flat_hash_map_remove_entry_wrap

◆ CCC_flat_hash_map_remove_key_value_wrap

◆ CCC_flat_hash_map_storage_for

◆ CCC_flat_hash_map_swap_entry_wrap

◆ CCC_flat_hash_map_try_insert_with

◆ CCC_flat_hash_map_try_insert_wrap

◆ CCC_flat_hash_map_with_capacity

◆ CCC_flat_hash_map_with_storage

Typedef Documentation

◆ CCC_Flat_hash_map

◆ CCC_Flat_hash_map_entry

Function Documentation

◆ CCC_flat_hash_map_and_modify()

◆ CCC_flat_hash_map_begin()

◆ CCC_flat_hash_map_capacity()

◆ CCC_flat_hash_map_clear()

◆ CCC_flat_hash_map_clear_and_free()

◆ CCC_flat_hash_map_contains()

◆ CCC_flat_hash_map_copy()

◆ CCC_flat_hash_map_count()

◆ CCC_flat_hash_map_end()

◆ CCC_flat_hash_map_entry()

◆ CCC_flat_hash_map_entry_status()

◆ CCC_flat_hash_map_get_key_value()

◆ CCC_flat_hash_map_insert_entry()

◆ CCC_flat_hash_map_insert_error()

◆ CCC_flat_hash_map_insert_or_assign()

◆ CCC_flat_hash_map_is_empty()

◆ CCC_flat_hash_map_next()

◆ CCC_flat_hash_map_occupied()

◆ CCC_flat_hash_map_or_insert()

◆ CCC_flat_hash_map_remove_entry()

◆ CCC_flat_hash_map_remove_key_value()

◆ CCC_flat_hash_map_reserve()

◆ CCC_flat_hash_map_swap_entry()

◆ CCC_flat_hash_map_try_insert()

◆ CCC_flat_hash_map_unwrap()

◆ CCC_flat_hash_map_validate()