private_array_tree_map.h

Go to the documentation of this file.

 
#ifndef CCC_PRIVATE_ARRAY_TREE_MAP_H
#define CCC_PRIVATE_ARRAY_TREE_MAP_H
 
#include <limits.h>
#include <stddef.h>
#include <stdint.h>
#include "../types.h" /* IWYU pragma: keep */
 
/* NOLINTBEGIN(readability-identifier-naming) */
 
struct CCC_Array_tree_map_node {
    size_t branch[2];
    union {
        size_t parent;
        size_t next_free;
    };
};
 
struct CCC_Array_tree_map {
    void *data;
    struct CCC_Array_tree_map_node *nodes;
    unsigned *parity;
    size_t root;
    size_t free_list;
    size_t capacity;
    size_t count;
    size_t sizeof_type;
    size_t alignof_type;
    size_t key_offset;
    CCC_Key_comparator comparator;
};
 
struct CCC_Array_tree_map_handle {
    struct CCC_Array_tree_map *map;
    size_t index;
    CCC_Order last_order;
    CCC_Entry_status status;
};
 
/*========================  Private Interface  ==============================*/
 
void *
CCC_private_array_tree_map_data_at(struct CCC_Array_tree_map const *, size_t);
void *
CCC_private_array_tree_map_key_at(struct CCC_Array_tree_map const *, size_t);
struct CCC_Array_tree_map_handle CCC_private_array_tree_map_handle(
    struct CCC_Array_tree_map const *, void const *
);
void CCC_private_array_tree_map_insert(
    struct CCC_Array_tree_map *, size_t, CCC_Order, size_t
);
size_t CCC_private_array_tree_map_allocate_slot(
    struct CCC_Array_tree_map *, CCC_Allocator const *
);
 
/*=========================      Initialization     =========================*/
 
#define CCC_private_array_tree_map_blocks(private_cap)                         \
    (((private_cap)                                                            \
      + ((sizeof(*(struct CCC_Array_tree_map){}.parity) * CHAR_BIT) - 1))      \
     / (sizeof(*(struct CCC_Array_tree_map){}.parity) * CHAR_BIT))
 
#define CCC_private_array_tree_map_compound_literal_array_capacity(            \
    private_type_compound_literal_array                                        \
)                                                                              \
    (sizeof(private_type_compound_literal_array)                               \
     / sizeof(*(private_type_compound_literal_array)))
 
#define CCC_private_array_tree_map_storage_for(                                \
    private_type_compound_literal_array, optional_storage_specifier...         \
)                                                                              \
    (optional_storage_specifier struct {                                       \
        static_assert(                                                         \
            CCC_private_array_tree_map_compound_literal_array_capacity(        \
                private_type_compound_literal_array                            \
            ) > 1,                                                             \
            "fixed size map must have capacity greater than 1"                 \
        );                                                                     \
        alignas(                                                               \
            alignof(*(private_type_compound_literal_array))                    \
                    > alignof(struct CCC_Array_tree_map_node)                  \
                ? alignof(*(private_type_compound_literal_array))              \
                : alignof(struct CCC_Array_tree_map_node)                      \
        ) typeof(*(private_type_compound_literal_array))                       \
            data[CCC_private_array_tree_map_compound_literal_array_capacity(   \
                private_type_compound_literal_array                            \
            )];                                                                \
        struct CCC_Array_tree_map_node                                         \
            nodes[CCC_private_array_tree_map_compound_literal_array_capacity(  \
                private_type_compound_literal_array                            \
            )];                                                                \
        typeof(*(struct CCC_Array_tree_map){}.parity)                          \
            parity[CCC_private_array_tree_map_blocks(                          \
                CCC_private_array_tree_map_compound_literal_array_capacity(    \
                    private_type_compound_literal_array                        \
                )                                                              \
            )];                                                                \
    }) {                                                                       \
    }
 
#define CCC_private_array_tree_map_default(                                    \
    private_type_name, private_key_field, private_comparator...                \
)                                                                              \
    (struct CCC_Array_tree_map) {                                              \
        .sizeof_type = sizeof(private_type_name),                              \
        .alignof_type = alignof(private_type_name),                            \
        .key_offset = offsetof(private_type_name, private_key_field),          \
        .comparator = (private_comparator),                                    \
    }
 
#define CCC_private_array_tree_map_for(                                        \
    private_type_name,                                                         \
    private_key_field,                                                         \
    private_comparator,                                                        \
    private_capacity,                                                          \
    private_memory_pointer                                                     \
)                                                                              \
    (struct CCC_Array_tree_map) {                                              \
        .data = (private_memory_pointer), .nodes = NULL, .parity = NULL,       \
        .capacity = (private_capacity), .count = 0, .root = 0, .free_list = 0, \
        .sizeof_type = sizeof(private_type_name),                              \
        .alignof_type = alignof(private_type_name),                            \
        .key_offset = offsetof(private_type_name, private_key_field),          \
        .comparator = (private_comparator),                                    \
    }
 
#define CCC_private_array_tree_map_from(                                       \
    private_key_field,                                                         \
    private_comparator,                                                        \
    private_allocator,                                                         \
    private_optional_cap,                                                      \
    private_array_compound_literal...                                          \
)                                                                              \
    (struct { struct CCC_Array_tree_map private; }){(__extension__({           \
        typeof(*private_array_compound_literal)                                \
            *private_array_tree_map_initializer_list                           \
            = private_array_compound_literal;                                  \
        struct CCC_Array_tree_map private_array_tree_map                       \
            = CCC_private_array_tree_map_default(                              \
                typeof(*private_array_tree_map_initializer_list),              \
                private_key_field,                                             \
                private_comparator                                             \
            );                                                                 \
        size_t const private_array_tree_n                                      \
            = sizeof(private_array_compound_literal)                           \
            / sizeof(*private_array_tree_map_initializer_list);                \
        size_t const private_cap = private_optional_cap;                       \
        CCC_Allocator const *const private_array_tree_map_allocator            \
            = &(private_allocator);                                            \
        if (CCC_array_tree_map_reserve(                                        \
                &private_array_tree_map,                                       \
                (private_array_tree_n > private_cap ? private_array_tree_n     \
                                                    : private_cap),            \
                private_array_tree_map_allocator                               \
            )                                                                  \
            == CCC_RESULT_OK) {                                                \
            for (size_t i = 0; i < private_array_tree_n; ++i) {                \
                struct CCC_Array_tree_map_handle private_array_tree_entry      \
                    = CCC_private_array_tree_map_handle(                       \
                        &private_array_tree_map,                               \
                        (                                                      \
                            void const *                                       \
                        )&private_array_tree_map_initializer_list[i]           \
                            .private_key_field                                 \
                    );                                                         \
                CCC_Handle_index private_index                                 \
                    = private_array_tree_entry.index;                          \
                if (!(private_array_tree_entry.status & CCC_ENTRY_OCCUPIED)) { \
                    private_index = CCC_private_array_tree_map_allocate_slot(  \
                        &private_array_tree_map,                               \
                        private_array_tree_map_allocator                       \
                    );                                                         \
                }                                                              \
                *((typeof(*private_array_tree_map_initializer_list) *)         \
                      CCC_private_array_tree_map_data_at(                      \
                          private_array_tree_entry.map, private_index          \
                      )) = private_array_tree_map_initializer_list[i];         \
                if (!(private_array_tree_entry.status & CCC_ENTRY_OCCUPIED)) { \
                    CCC_private_array_tree_map_insert(                         \
                        private_array_tree_entry.map,                          \
                        private_array_tree_entry.index,                        \
                        private_array_tree_entry.last_order,                   \
                        private_index                                          \
                    );                                                         \
                }                                                              \
            }                                                                  \
        }                                                                      \
        private_array_tree_map;                                                \
    }))}.private
 
#define CCC_private_array_tree_map_with_capacity(                              \
    private_type_name,                                                         \
    private_key_field,                                                         \
    private_comparator,                                                        \
    private_allocator,                                                         \
    private_cap                                                                \
)                                                                              \
    (struct { struct CCC_Array_tree_map private; }){(__extension__({           \
        struct CCC_Array_tree_map private_array_tree_map                       \
            = CCC_private_array_tree_map_default(                              \
                private_type_name, private_key_field, private_comparator       \
            );                                                                 \
        (void)CCC_array_tree_map_reserve(                                      \
            &private_array_tree_map, private_cap, &(private_allocator)         \
        );                                                                     \
        private_array_tree_map;                                                \
    }))}.private
 
#define CCC_private_array_tree_map_with_storage(                               \
    private_key_node_field,                                                    \
    private_comparator,                                                        \
    private_compound_literal,                                                  \
    private_optional_storage_specifier...                                      \
)                                                                              \
    (struct CCC_Array_tree_map) {                                              \
        .data = &CCC_private_array_tree_map_storage_for(                       \
            private_compound_literal, private_optional_storage_specifier       \
        ),                                                                     \
        .nodes = NULL, .parity = NULL,                                         \
        .capacity                                                              \
            = CCC_private_array_tree_map_compound_literal_array_capacity(      \
                private_compound_literal                                       \
            ),                                                                 \
        .count = 0, .root = 0, .free_list = 0,                                 \
        .sizeof_type = sizeof(*(private_compound_literal)),                    \
        .alignof_type = alignof(*(private_compound_literal)),                  \
        .key_offset = offsetof(                                                \
            typeof(*(private_compound_literal)), private_key_node_field        \
        ),                                                                     \
        .comparator = (private_comparator),                                    \
    }
 
#define CCC_private_array_tree_map_as(                                         \
    array_tree_map_pointer, type_name, handle...                               \
)                                                                              \
    ((type_name *)CCC_private_array_tree_map_data_at(                          \
        (array_tree_map_pointer), (handle)                                     \
    ))
 
#define CCC_private_array_tree_map_with_allocator_storage(                     \
    private_key_field,                                                         \
    private_comparator,                                                        \
    private_allocator,                                                         \
    private_compound_literal                                                   \
)                                                                              \
    (__extension__({                                                           \
        CCC_Allocator const *const private_allocator_pointer                   \
            = &(private_allocator);                                            \
        void *private_data_base = NULL;                                        \
        if (private_allocator_pointer->allocate) {                             \
            private_data_base = private_allocator_pointer->allocate(           \
                (CCC_Allocator_arguments){                                     \
                    .input = NULL,                                             \
                    .bytes = sizeof(CCC_private_array_tree_map_storage_for(    \
                        private_compound_literal                               \
                    )),                                                        \
                    .alignment = alignof(struct CCC_Array_tree_map_node)       \
                                       > alignof(*(private_compound_literal))  \
                                   ? alignof(struct CCC_Array_tree_map_node)   \
                                   : alignof(*(private_compound_literal)),     \
                    .context = private_allocator_pointer->context,             \
                }                                                              \
            );                                                                 \
        }                                                                      \
        struct CCC_Array_tree_map private_array_tree_map = {};                 \
        if (private_data_base) {                                               \
            private_array_tree_map = CCC_private_array_tree_map_for(           \
                typeof(*(private_compound_literal)),                           \
                private_key_field,                                             \
                private_comparator,                                            \
                CCC_private_array_tree_map_compound_literal_array_capacity(    \
                    private_compound_literal                                   \
                ),                                                             \
                private_data_base                                              \
            );                                                                 \
        } else {                                                               \
            private_array_tree_map = CCC_private_array_tree_map_for(           \
                typeof(*(private_compound_literal)),                           \
                private_key_field,                                             \
                private_comparator,                                            \
                0,                                                             \
                NULL                                                           \
            );                                                                 \
        }                                                                      \
        private_array_tree_map;                                                \
    }))
 
/*==================     Core Macro Implementations     =====================*/
 
#define CCC_private_array_tree_map_and_modify_with(                            \
    array_tree_map_handle_pointer,                                             \
    closure_parameter,                                                         \
    closure_over_closure_parameter...                                          \
)                                                                              \
    (__extension__({                                                           \
        struct CCC_Array_tree_map_handle const *const                          \
            private_array_tree_map_hndl_pointer                                \
            = (array_tree_map_handle_pointer);                                 \
        struct CCC_Array_tree_map_handle private_array_tree_map_mod_hndl       \
            = {.status = CCC_ENTRY_ARGUMENT_ERROR};                            \
        if (private_array_tree_map_hndl_pointer) {                             \
            private_array_tree_map_mod_hndl                                    \
                = *private_array_tree_map_hndl_pointer;                        \
            if (private_array_tree_map_mod_hndl.status & CCC_ENTRY_OCCUPIED) { \
                closure_parameter = CCC_private_array_tree_map_data_at(        \
                    private_array_tree_map_mod_hndl.map,                       \
                    private_array_tree_map_mod_hndl.index                      \
                );                                                             \
                closure_over_closure_parameter                                 \
            }                                                                  \
        }                                                                      \
        private_array_tree_map_mod_hndl;                                       \
    }))
 
#define CCC_private_array_tree_map_or_insert_with(                             \
    array_tree_map_handle_pointer,                                             \
    private_allocator_pointer,                                                 \
    type_compound_literal...                                                   \
)                                                                              \
    (__extension__({                                                           \
        struct CCC_Array_tree_map_handle const *const                          \
            private_or_ins_handle_pointer = (array_tree_map_handle_pointer);   \
        CCC_Handle_index private_array_tree_map_or_ins_ret = 0;                \
        CCC_Allocator const *const private_array_tree_map_allocator            \
            = (private_allocator_pointer);                                     \
        if (private_array_tree_map_allocator                                   \
            && private_or_ins_handle_pointer) {                                \
            if (private_or_ins_handle_pointer->status == CCC_ENTRY_OCCUPIED) { \
                private_array_tree_map_or_ins_ret                              \
                    = private_or_ins_handle_pointer->index;                    \
            } else {                                                           \
                private_array_tree_map_or_ins_ret                              \
                    = CCC_private_array_tree_map_allocate_slot(                \
                        private_or_ins_handle_pointer->map,                    \
                        private_array_tree_map_allocator                       \
                    );                                                         \
                if (private_array_tree_map_or_ins_ret) {                       \
                    *((typeof(type_compound_literal) *)                        \
                          CCC_private_array_tree_map_data_at(                  \
                              private_or_ins_handle_pointer->map,              \
                              private_array_tree_map_or_ins_ret                \
                          )) = type_compound_literal;                          \
                    CCC_private_array_tree_map_insert(                         \
                        private_or_ins_handle_pointer->map,                    \
                        private_or_ins_handle_pointer->index,                  \
                        private_or_ins_handle_pointer->last_order,             \
                        private_array_tree_map_or_ins_ret                      \
                    );                                                         \
                }                                                              \
            }                                                                  \
        }                                                                      \
        private_array_tree_map_or_ins_ret;                                     \
    }))
 
#define CCC_private_array_tree_map_insert_handle_with(                         \
    array_tree_map_handle_pointer,                                             \
    private_allocator_pointer,                                                 \
    type_compound_literal...                                                   \
)                                                                              \
    (__extension__({                                                           \
        struct CCC_Array_tree_map_handle const *const                          \
            private_ins_handle_pointer = (array_tree_map_handle_pointer);      \
        CCC_Handle_index private_array_tree_map_ins_hndl_ret = 0;              \
        CCC_Allocator const *const private_array_tree_map_allocator            \
            = (private_allocator_pointer);                                     \
        if (private_array_tree_map_allocator && private_ins_handle_pointer) {  \
            if (!(private_ins_handle_pointer->status & CCC_ENTRY_OCCUPIED)) {  \
                private_array_tree_map_ins_hndl_ret                            \
                    = CCC_private_array_tree_map_allocate_slot(                \
                        private_ins_handle_pointer->map,                       \
                        private_array_tree_map_allocator                       \
                    );                                                         \
                if (private_array_tree_map_ins_hndl_ret) {                     \
                    *((typeof(type_compound_literal) *)                        \
                          CCC_private_array_tree_map_data_at(                  \
                              private_ins_handle_pointer->map,                 \
                              private_array_tree_map_ins_hndl_ret              \
                          )) = type_compound_literal;                          \
                    CCC_private_array_tree_map_insert(                         \
                        private_ins_handle_pointer->map,                       \
                        private_ins_handle_pointer->index,                     \
                        private_ins_handle_pointer->last_order,                \
                        private_array_tree_map_ins_hndl_ret                    \
                    );                                                         \
                }                                                              \
            } else if (private_ins_handle_pointer->status                      \
                       == CCC_ENTRY_OCCUPIED) {                                \
                private_array_tree_map_ins_hndl_ret                            \
                    = private_ins_handle_pointer->index;                       \
                *((typeof(type_compound_literal) *)                            \
                      CCC_private_array_tree_map_data_at(                      \
                          private_ins_handle_pointer->map,                     \
                          private_array_tree_map_ins_hndl_ret                  \
                      )) = type_compound_literal;                              \
            }                                                                  \
        }                                                                      \
        private_array_tree_map_ins_hndl_ret;                                   \
    }))
 
#define CCC_private_array_tree_map_try_insert_with(                            \
    array_tree_map_pointer,                                                    \
    key,                                                                       \
    private_allocator_pointer,                                                 \
    type_compound_literal...                                                   \
)                                                                              \
    (__extension__({                                                           \
        struct CCC_Array_tree_map *const private_try_ins_map_pointer           \
            = (array_tree_map_pointer);                                        \
        CCC_Handle private_array_tree_map_try_ins_hndl_ret                     \
            = {.status = CCC_ENTRY_ARGUMENT_ERROR};                            \
        CCC_Allocator const *const private_array_tree_map_allocator            \
            = (private_allocator_pointer);                                     \
        if (private_array_tree_map_allocator && private_try_ins_map_pointer) { \
            __auto_type private_array_tree_map_key = (key);                    \
            struct CCC_Array_tree_map_handle                                   \
                private_array_tree_map_try_ins_hndl                            \
                = CCC_private_array_tree_map_handle(                           \
                    private_try_ins_map_pointer,                               \
                    (void *)&private_array_tree_map_key                        \
                );                                                             \
            if (!(private_array_tree_map_try_ins_hndl.status                   \
                  & CCC_ENTRY_OCCUPIED)) {                                     \
                private_array_tree_map_try_ins_hndl_ret = (CCC_Handle){        \
                    .index = CCC_private_array_tree_map_allocate_slot(         \
                        private_array_tree_map_try_ins_hndl.map,               \
                        private_array_tree_map_allocator                       \
                    ),                                                         \
                    .status = CCC_ENTRY_INSERT_ERROR,                          \
                };                                                             \
                if (private_array_tree_map_try_ins_hndl_ret.index) {           \
                    *((typeof(type_compound_literal) *)                        \
                          CCC_private_array_tree_map_data_at(                  \
                              private_try_ins_map_pointer,                     \
                              private_array_tree_map_try_ins_hndl_ret.index    \
                          )) = type_compound_literal;                          \
                    *((typeof(private_array_tree_map_key) *)                   \
                          CCC_private_array_tree_map_key_at(                   \
                              private_try_ins_map_pointer,                     \
                              private_array_tree_map_try_ins_hndl_ret.index    \
                          )) = private_array_tree_map_key;                     \
                    CCC_private_array_tree_map_insert(                         \
                        private_array_tree_map_try_ins_hndl.map,               \
                        private_array_tree_map_try_ins_hndl.index,             \
                        private_array_tree_map_try_ins_hndl.last_order,        \
                        private_array_tree_map_try_ins_hndl_ret.index          \
                    );                                                         \
                    private_array_tree_map_try_ins_hndl_ret.status             \
                        = CCC_ENTRY_VACANT;                                    \
                }                                                              \
            } else if (private_array_tree_map_try_ins_hndl.status              \
                       == CCC_ENTRY_OCCUPIED) {                                \
                private_array_tree_map_try_ins_hndl_ret = (CCC_Handle){        \
                    .index = private_array_tree_map_try_ins_hndl.index,        \
                    .status = private_array_tree_map_try_ins_hndl.status,      \
                };                                                             \
            }                                                                  \
        }                                                                      \
        private_array_tree_map_try_ins_hndl_ret;                               \
    }))
 
#define CCC_private_array_tree_map_insert_or_assign_with(                      \
    array_tree_map_pointer,                                                    \
    key,                                                                       \
    private_allocator_pointer,                                                 \
    type_compound_literal...                                                   \
)                                                                              \
    (__extension__({                                                           \
        struct CCC_Array_tree_map *const private_ins_or_assign_map_pointer     \
            = (array_tree_map_pointer);                                        \
        CCC_Handle private_array_tree_map_ins_or_assign_hndl_ret               \
            = {.status = CCC_ENTRY_ARGUMENT_ERROR};                            \
        CCC_Allocator const *const private_array_tree_map_allocator            \
            = (private_allocator_pointer);                                     \
        if (private_array_tree_map_allocator                                   \
            && private_ins_or_assign_map_pointer) {                            \
            __auto_type private_array_tree_map_key = (key);                    \
            struct CCC_Array_tree_map_handle                                   \
                private_array_tree_map_ins_or_assign_hndl                      \
                = CCC_private_array_tree_map_handle(                           \
                    private_ins_or_assign_map_pointer,                         \
                    (void *)&private_array_tree_map_key                        \
                );                                                             \
            if (!(private_array_tree_map_ins_or_assign_hndl.status             \
                  & CCC_ENTRY_OCCUPIED)) {                                     \
                private_array_tree_map_ins_or_assign_hndl_ret = (CCC_Handle){  \
                    .index = CCC_private_array_tree_map_allocate_slot(         \
                        private_array_tree_map_ins_or_assign_hndl.map,         \
                        private_array_tree_map_allocator                       \
                    ),                                                         \
                    .status = CCC_ENTRY_INSERT_ERROR,                          \
                };                                                             \
                if (private_array_tree_map_ins_or_assign_hndl_ret.index) {     \
                    *((typeof(type_compound_literal) *)                        \
                          CCC_private_array_tree_map_data_at(                  \
                              private_array_tree_map_ins_or_assign_hndl.map,   \
                              private_array_tree_map_ins_or_assign_hndl_ret    \
                                  .index                                       \
                          )) = type_compound_literal;                          \
                    *((typeof(private_array_tree_map_key) *)                   \
                          CCC_private_array_tree_map_key_at(                   \
                              private_array_tree_map_ins_or_assign_hndl.map,   \
                              private_array_tree_map_ins_or_assign_hndl_ret    \
                                  .index                                       \
                          )) = private_array_tree_map_key;                     \
                    CCC_private_array_tree_map_insert(                         \
                        private_array_tree_map_ins_or_assign_hndl.map,         \
                        private_array_tree_map_ins_or_assign_hndl.index,       \
                        private_array_tree_map_ins_or_assign_hndl.last_order,  \
                        private_array_tree_map_ins_or_assign_hndl_ret.index    \
                    );                                                         \
                    private_array_tree_map_ins_or_assign_hndl_ret.status       \
                        = CCC_ENTRY_VACANT;                                    \
                }                                                              \
            } else if (private_array_tree_map_ins_or_assign_hndl.status        \
                       == CCC_ENTRY_OCCUPIED) {                                \
                *((typeof(type_compound_literal) *)                            \
                      CCC_private_array_tree_map_data_at(                      \
                          private_array_tree_map_ins_or_assign_hndl.map,       \
                          private_array_tree_map_ins_or_assign_hndl.index      \
                      )) = type_compound_literal;                              \
                private_array_tree_map_ins_or_assign_hndl_ret = (CCC_Handle){  \
                    .index = private_array_tree_map_ins_or_assign_hndl.index,  \
                    .status                                                    \
                    = private_array_tree_map_ins_or_assign_hndl.status,        \
                };                                                             \
                *((typeof(private_array_tree_map_key) *)                       \
                      CCC_private_array_tree_map_key_at(                       \
                          private_array_tree_map_ins_or_assign_hndl.map,       \
                          private_array_tree_map_ins_or_assign_hndl.index      \
                      )) = private_array_tree_map_key;                         \
            }                                                                  \
        }                                                                      \
        private_array_tree_map_ins_or_assign_hndl_ret;                         \
    }))
 
/* NOLINTEND(readability-identifier-naming) */
 
#endif /* CCC_PRIVATE_ARRAY_TREE_MAP_H */