private_flat_hash_map.h File Reference

Private Flat Hash Map Interface. More...

#include "../types.h"

Include dependency graph for private_flat_hash_map.h:

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

Go to the source code of this file.

Detailed Description

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.

Data Structures
struct	CCC_Flat_hash_map_tag
struct	CCC_Flat_hash_map
struct	CCC_Flat_hash_map_entry

Macros
#define	CCC_private_flat_hash_map_compound_literal_array_capacity( private_type_compound_literal_array)
#define	CCC_private_flat_hash_map_storage_for( private_type_compound_literal_array, optional_storage_specifier...)
#define	CCC_private_flat_hash_map_default( private_type_name, private_key_field, private_hasher...)
#define	CCC_private_flat_hash_map_for( private_type_name, private_key_field, private_hasher, private_capacity, private_map_pointer)
#define	CCC_private_flat_hash_map_from( private_key_field, private_hasher, private_allocator, private_optional_cap, private_array_compound_literal...)
#define	CCC_private_flat_hash_map_with_capacity( private_type_name, private_key_field, private_hasher, private_allocator, private_cap)
#define	CCC_private_flat_hash_map_with_storage( private_key_field, private_hasher, private_compound_literal, private_optional_storage_specifier...)
#define	CCC_private_flat_hash_map_and_modify_with( flat_hash_map_entry_pointer, closure_parameter, closure_over_closure_parameter...)
#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, private_allocator_pointer, type_compound_literal...)
#define	CCC_private_flat_hash_map_insert_or_assign_with( flat_hash_map_pointer, key, private_allocator_pointer, type_compound_literal...)

Enumerations
enum	: typeof((struct CCC_Flat_hash_map_tag)

Functions
struct CCC_Flat_hash_map_entry	CCC_private_flat_hash_map_entry (struct CCC_Flat_hash_map *, void const *, CCC_Allocator const *)
void *	CCC_private_flat_hash_map_data_at (struct CCC_Flat_hash_map const *, size_t)
void *	CCC_private_flat_hash_map_key_at (struct CCC_Flat_hash_map const *, size_t)
void	CCC_private_flat_hash_map_set_insert (struct CCC_Flat_hash_map_entry const *)

Variables
enum { ... }	CCC_FLAT_HASH_MAP_GROUP_COUNT = 8

Macro Definition Documentation

CCC_private_flat_hash_map_and_modify_with

#define CCC_private_flat_hash_map_and_modify_with	(		flat_hash_map_entry_pointer,
			closure_parameter,
			closure_over_closure_parameter...
	)

Value:

    (__extension__({                                                           \
        __auto_type private_flat_hash_map_mod_ent_pointer                      \
            = (flat_hash_map_entry_pointer);                                   \
        struct CCC_Flat_hash_map_entry private_flat_hash_map_mod_with_ent      \
            = {.status = CCC_ENTRY_ARGUMENT_ERROR};                            \
        if (private_flat_hash_map_mod_ent_pointer) {                           \
            private_flat_hash_map_mod_with_ent                                 \
                = *private_flat_hash_map_mod_ent_pointer;                      \
            if (private_flat_hash_map_mod_with_ent.status                      \
                & CCC_ENTRY_OCCUPIED) {                                        \
                closure_parameter = CCC_private_flat_hash_map_data_at(         \
                    private_flat_hash_map_mod_with_ent.map,                    \
                    private_flat_hash_map_mod_with_ent.index                   \
                );                                                             \
                closure_over_closure_parameter                                 \
            }                                                                  \
        }                                                                      \
        private_flat_hash_map_mod_with_ent;                                    \
    }))

A fairly good approximation of closures given C23 capabilities. The user facing docs clarify that T is a correctly typed reference to the desired data if occupied.

CCC_private_flat_hash_map_compound_literal_array_capacity

#define CCC_private_flat_hash_map_compound_literal_array_capacity

(

private_type_compound_literal_array

)

Value:

    (sizeof(private_type_compound_literal_array)                               \
     / sizeof(*(private_type_compound_literal_array)))

CCC_private_flat_hash_map_default

#define CCC_private_flat_hash_map_default	(		private_type_name,
			private_key_field,
			private_hasher...
	)

Value:

    (struct CCC_Flat_hash_map) {                                               \
        .sizeof_type = sizeof(private_type_name),                              \
        .key_offset = offsetof(private_type_name, private_key_field),          \
        .hasher = private_hasher,                                              \
    }

All other fields default to 0 or NULL.

CCC_private_flat_hash_map_for

#define CCC_private_flat_hash_map_for	(		private_type_name,
			private_key_field,
			private_hasher,
			private_capacity,
			private_map_pointer
	)

Value:

    (struct CCC_Flat_hash_map) {                                               \
        .data = (private_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),          \
        .hasher = (private_hasher),                                            \
    }

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 &(struct My_type[MY_POWER_OF_2_CAPACITY]){}. 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.

CCC_private_flat_hash_map_from

#define CCC_private_flat_hash_map_from	(		private_key_field,
			private_hasher,
			private_allocator,
			private_optional_cap,
			private_array_compound_literal...
	)

Initialize dynamic container with a compound literal array.

CCC_private_flat_hash_map_insert_entry_with

#define CCC_private_flat_hash_map_insert_entry_with	(		flat_hash_map_entry_pointer,
			type_compound_literal...
	)

Value:

    (__extension__({                                                           \
        __auto_type private_flat_hash_map_ins_ent_pointer                      \
            = (flat_hash_map_entry_pointer);                                   \
        typeof(type_compound_literal) *private_flat_hash_map_ins_ent_res       \
            = NULL;                                                            \
        if (private_flat_hash_map_ins_ent_pointer) {                           \
            if (!(private_flat_hash_map_ins_ent_pointer->status                \
                  & CCC_ENTRY_INSERT_ERROR)) {                                 \
                private_flat_hash_map_ins_ent_res                              \
                    = CCC_private_flat_hash_map_data_at(                       \
                        private_flat_hash_map_ins_ent_pointer->map,            \
                        private_flat_hash_map_ins_ent_pointer->index           \
                    );                                                         \
                *private_flat_hash_map_ins_ent_res = type_compound_literal;    \
                if (private_flat_hash_map_ins_ent_pointer->status              \
                    == CCC_ENTRY_VACANT) {                                     \
                    CCC_private_flat_hash_map_set_insert(                      \
                        private_flat_hash_map_ins_ent_pointer                  \
                    );                                                         \
                }                                                              \
            }                                                                  \
        }                                                                      \
        private_flat_hash_map_ins_ent_res;                                     \
    }))

Insert entry also should not fail and therefore returns a reference directly. This is similar to insert or assign where overwriting may occur.

CCC_private_flat_hash_map_insert_or_assign_with

#define CCC_private_flat_hash_map_insert_or_assign_with	(		flat_hash_map_pointer,
			key,
			private_allocator_pointer,
			type_compound_literal...
	)

Because this function does not start with an entry it has the option to give user more information and therefore returns an entry. Importantly, this function makes sure the key is in sync with key in table. Similar to insert entry this will overwrite.

CCC_private_flat_hash_map_or_insert_with

#define CCC_private_flat_hash_map_or_insert_with	(		flat_hash_map_entry_pointer,
			type_compound_literal...
	)

Value:

    (__extension__({                                                           \
        __auto_type private_flat_hash_map_or_ins_ent_pointer                   \
            = (flat_hash_map_entry_pointer);                                   \
        typeof(type_compound_literal) *private_flat_hash_map_or_ins_res        \
            = NULL;                                                            \
        if (private_flat_hash_map_or_ins_ent_pointer) {                        \
            if (!(private_flat_hash_map_or_ins_ent_pointer->status             \
                  & CCC_ENTRY_INSERT_ERROR)) {                                 \
                private_flat_hash_map_or_ins_res                               \
                    = CCC_private_flat_hash_map_data_at(                       \
                        private_flat_hash_map_or_ins_ent_pointer->map,         \
                        private_flat_hash_map_or_ins_ent_pointer->index        \
                    );                                                         \
                if (private_flat_hash_map_or_ins_ent_pointer->status           \
                    == CCC_ENTRY_VACANT) {                                     \
                    *private_flat_hash_map_or_ins_res = type_compound_literal; \
                    CCC_private_flat_hash_map_set_insert(                      \
                        private_flat_hash_map_or_ins_ent_pointer               \
                    );                                                         \
                }                                                              \
            }                                                                  \
        }                                                                      \
        private_flat_hash_map_or_ins_res;                                      \
    }))

The or insert method is unique in that it directly returns a reference to the inserted data rather than a entry with a status. This is because it should not fail. If NULL is returned the user knows there is a problem.

CCC_private_flat_hash_map_storage_for

#define CCC_private_flat_hash_map_storage_for	(		private_type_compound_literal_array,
			optional_storage_specifier...
	)

The backing storage is an anonymous struct created at compile time and then provided immediately as a compound literal. Since C11, we can use static asserts within struct definitions which is excellent. This macro is the key to ease of use with fixed size associative containers. It can also be exposed to the user if they wish to know the size in bytes of this object.

CCC_private_flat_hash_map_try_insert_with

#define CCC_private_flat_hash_map_try_insert_with	(		flat_hash_map_pointer,
			key,
			private_allocator_pointer,
			type_compound_literal...
	)

Because this function does not start with an entry it has the option to give user more information and therefore returns an entry. Importantly, this function makes sure the key is in sync with key in table.

CCC_private_flat_hash_map_with_capacity

#define CCC_private_flat_hash_map_with_capacity	(		private_type_name,
			private_key_field,
			private_hasher,
			private_allocator,
			private_cap
	)

Value:

    (struct { struct CCC_Flat_hash_map private; }){(__extension__({            \
        struct CCC_Flat_hash_map private_map                                   \
            = CCC_private_flat_hash_map_default(                               \
                private_type_name, private_key_field, private_hasher           \
            );                                                                 \
        (void)CCC_flat_hash_map_reserve(                                       \
            &private_map, private_cap, &(private_allocator)                    \
        );                                                                     \
        private_map;                                                           \
    }))}.private

Initializes the flat hash map with the specified capacity.

CCC_private_flat_hash_map_with_storage

#define CCC_private_flat_hash_map_with_storage	(		private_key_field,
			private_hasher,
			private_compound_literal,
			private_optional_storage_specifier...
	)

Value:

    (struct CCC_Flat_hash_map) {                                               \
        .data = &CCC_private_flat_hash_map_storage_for(                        \
            private_compound_literal, private_optional_storage_specifier       \
        ),                                                                     \
        .tag = NULL, .count = 0,                                               \
        .remain                                                                \
            = ((CCC_private_flat_hash_map_compound_literal_array_capacity(     \
                    private_compound_literal                                   \
                )                                                              \
                / (size_t)8)                                                   \
               * (size_t)7),                                                   \
        .mask = CCC_private_flat_hash_map_compound_literal_array_capacity(     \
                    private_compound_literal                                   \
                )                                                              \
              - (size_t)1,                                                     \
        .sizeof_type = sizeof(*(private_compound_literal)),                    \
        .key_offset = offsetof(                                                \
            typeof(*(private_compound_literal)), private_key_field             \
        ),                                                                     \
        .hasher = (private_hasher),                                            \
    }

We can cut out boilerplate by assuming fixed size map.

Enumeration Type Documentation

anonymous enum

anonymous enum : typeof((struct CCC_Flat_hash_map_tag)

Vectorized group scanning allows more parallel scans but a fallback of 8 is good for a portable implementation that will use the widest word on a platform for group scanning. Right now, this lib targets 64-bit so that means uint64_t is widest default integer widely supported. That width is still valid on 32-bit but probably very slow due to emulation.

Function Documentation

CCC_private_flat_hash_map_data_at()

void * CCC_private_flat_hash_map_data_at	(	struct CCC_Flat_hash_map const *	,
		size_t
	)

CCC_private_flat_hash_map_entry()

struct CCC_Flat_hash_map_entry CCC_private_flat_hash_map_entry	(	struct CCC_Flat_hash_map *	,
		void const *	,
		CCC_Allocator const *
	)

CCC_private_flat_hash_map_key_at()

void * CCC_private_flat_hash_map_key_at	(	struct CCC_Flat_hash_map const *	,
		size_t
	)

CCC_private_flat_hash_map_set_insert()

void CCC_private_flat_hash_map_set_insert

(

struct CCC_Flat_hash_map_entry const *

)

Variable Documentation

enum { ... } CCC_FLAT_HASH_MAP_GROUP_COUNT

Vectorized group scanning allows more parallel scans but a fallback of 8 is good for a portable implementation that will use the widest word on a platform for group scanning. Right now, this lib targets 64-bit so that means uint64_t is widest default integer widely supported. That width is still valid on 32-bit but probably very slow due to emulation. A group of tags that can be loded into a 64 bit integer.