Private Flat Hash Map Interface.
This flat hash map is a C Container Collection friendly interpretation of the Rust Hashbrown hash table. This in turn is based on the Abseil flat hash table from Google in C++. I simplified and modified the implementation for maximum readability in one header and one file. Tracking how to manage different platform implementations of groups and metadata fingerprint masks should be much easier this way, rather than jumping across countless small implementation files.
One key feature that is rigorously tested via static asserts is the ability to create a static data segment or stack based map. This is a key feature of the implementation but it requires significant set up ahead of time and lazy initialization support. The lazy initialization presents the map with the most complexity in the implementation.
|
| #define | CCC_private_flat_hash_map_declare_fixed_map( fixed_map_type_name, key_val_type_name, capacity) |
| |
| #define | CCC_private_flat_hash_map_fixed_capacity(fixed_map_type_name) (sizeof((fixed_map_type_name){}.tag) - CCC_FLAT_HASH_MAP_GROUP_COUNT) |
| |
| #define | CCC_private_flat_hash_map_initialize( private_fixed_map_pointer, private_type_name, private_key_field, private_hash, private_key_compare, private_allocate, private_context_data, private_capacity) |
| |
| #define | CCC_private_flat_hash_map_from( private_key_field, private_hash, private_key_compare, private_allocate, private_context_data, private_optional_cap, private_array_compound_literal...) |
| |
| #define | CCC_private_flat_hash_map_with_capacity( private_type_name, private_key_field, private_hash, private_key_compare, private_allocate, private_context_data, private_cap) |
| |
| #define | CCC_private_flat_hash_map_and_modify_with( Flat_hash_map_entry_pointer, type_name, closure_over_T...) |
| |
| #define | CCC_private_flat_hash_map_or_insert_with(Flat_hash_map_entry_pointer, type_compound_literal...) |
| |
| #define | CCC_private_flat_hash_map_insert_entry_with( Flat_hash_map_entry_pointer, type_compound_literal...) |
| |
| #define | CCC_private_flat_hash_map_try_insert_with(flat_hash_map_pointer, key, type_compound_literal...) |
| |
| #define | CCC_private_flat_hash_map_insert_or_assign_with( flat_hash_map_pointer, key, type_compound_literal...) |
| |
| #define CCC_private_flat_hash_map_declare_fixed_map |
( |
|
fixed_map_type_name, |
|
|
|
key_val_type_name, |
|
|
|
capacity |
|
) |
| |
Value: static_assert((capacity) > 0, \
"fixed size map must have capacity greater than 0"); \
static_assert( \
"fixed size map must have capacity >= CCC_FLAT_HASH_MAP_GROUP_COUNT " \
"(8 or 16 depending on platform)"); \
static_assert(((capacity) & ((capacity) - 1)) == 0, \
"fixed size map must be a power of 2 capacity (32, 64, " \
"128, 256, etc.)"); \
typedef struct \
{ \
key_val_type_name data[(capacity) + 1]; \
}(fixed_map_type_name)
enum @6 CCC_FLAT_HASH_MAP_GROUP_COUNT
Definition: private_flat_hash_map.h:81
Helps the user declare a type for a fixed size map. They can then use this type when they want a hash map as global, static global, or stack local. They would need to define their fixed size type every time but that should be fine as they are likely to only declare one or two. They would likely only have a one fixed size map per translation unit if they are using these capabilities. They control the name of the type so they can organize types as they wish.
The declaration specifies that we have one extra data slot for swapping during in place rehashing and some interface functions and an extra duplicate group of tags at the end of the tag array for safer group loading.
Finally, we must align the tag array to start on an aligned group size byte boundary to be able to perform aligned loads and stores.
| #define CCC_private_flat_hash_map_initialize |
( |
|
private_fixed_map_pointer, |
|
|
|
private_type_name, |
|
|
|
private_key_field, |
|
|
|
private_hash, |
|
|
|
private_key_compare, |
|
|
|
private_allocate, |
|
|
|
private_context_data, |
|
|
|
private_capacity |
|
) |
| |
Value: { \
.data = (private_fixed_map_pointer), \
.tag = NULL, \
.count = 0, \
.remain = (((private_capacity) / (size_t)8) * (size_t)7), \
.mask \
= (((private_capacity) > (size_t)0) ? ((private_capacity) - (size_t)1) \
: (size_t)0), \
.sizeof_type = sizeof(private_type_name), \
.key_offset = offsetof(private_type_name, private_key_field), \
.compare = (private_key_compare), \
.hash = (private_hash), \
.allocate = (private_allocate), \
.context = (private_context_data), \
}
Initialization is tricky but we simplify by only accepting a pointer to the map this pointer could be any of the following.
- The address of a user defined fixed size map stored in data segment.
- The address of a user defined fixed size map stored on the stack.
- The address of a user defined fixed size map allocated on the heap.
- NULL if the user intends for a dynamic map.
All of the above cases are covered by accepting the pointer at .data and only evaluating the argument once. This also allows the user to pass a compound literal to the first argument and eliminate any dangling references, such as &(static user_defined_map_type){}. However, to accept a map from all of these sources at compile or runtime, we must implement lazy initialization. This is because we can't initialize the tag array at compile time. By setting the tag field to NULL we will be able to tell if our map is initialized whether it is fixed size and has data or is dynamic and has not yet been given allocation.
