private_tree_map.h

Go to the documentation of this file.

 
#ifndef CCC_PRIVATE_TREE_MAP_H
#define CCC_PRIVATE_TREE_MAP_H
 
#include <stddef.h>
#include <stdint.h>
#include "../types.h" /* IWYU pragma: keep */
 
/* NOLINTBEGIN(readability-identifier-naming) */
 
struct CCC_Tree_map_node {
    struct CCC_Tree_map_node *branch[2];
    struct CCC_Tree_map_node *parent;
    uint8_t parity;
};
 
struct CCC_Tree_map {
    struct CCC_Tree_map_node *root;
    size_t count;
    size_t key_offset;
    size_t type_intruder_offset;
    size_t sizeof_type;
    size_t alignof_type;
    CCC_Key_comparator comparator;
};
 
struct CCC_Tree_map_entry {
    struct CCC_Tree_map *map;
    CCC_Order last_order;
    CCC_Entry entry;
};
 
/*=========================   Private Interface  ============================*/
 
void *
CCC_private_tree_map_key_in_slot(struct CCC_Tree_map const *, void const *slot);
struct CCC_Tree_map_node *CCC_private_tree_map_node_in_slot(
    struct CCC_Tree_map const *, void const *slot
);
struct CCC_Tree_map_entry
CCC_private_tree_map_entry(struct CCC_Tree_map const *, void const *key);
void *CCC_private_tree_map_insert(
    struct CCC_Tree_map *,
    struct CCC_Tree_map_node *parent,
    CCC_Order last_order,
    struct CCC_Tree_map_node *type_output_intruder
);
 
/*==========================   Initialization     ===========================*/
 
#define CCC_private_tree_map_for(                                              \
    private_struct_name,                                                       \
    private_node_field,                                                        \
    private_key_node_field,                                                    \
    private_comparator...                                                      \
)                                                                              \
    (struct CCC_Tree_map) {                                                    \
        .root = NULL, .count = 0,                                              \
        .key_offset = offsetof(private_struct_name, private_key_node_field),   \
        .type_intruder_offset                                                  \
            = offsetof(private_struct_name, private_node_field),               \
        .sizeof_type = sizeof(private_struct_name),                            \
        .alignof_type = alignof(private_struct_name),                          \
        .comparator = (private_comparator),                                    \
    }
 
#define CCC_private_tree_map_default(                                          \
    private_struct_name,                                                       \
    private_node_field,                                                        \
    private_key_node_field,                                                    \
    private_comparator...                                                      \
)                                                                              \
    CCC_private_tree_map_for(                                                  \
        private_struct_name,                                                   \
        private_node_field,                                                    \
        private_key_node_field,                                                \
        private_comparator                                                     \
    )
 
#define CCC_private_tree_map_from(                                             \
    private_type_intruder_field_name,                                          \
    private_key_field_name,                                                    \
    private_comparator,                                                        \
    private_allocator,                                                         \
    private_destructor,                                                        \
    private_compound_literal_array...                                          \
)                                                                              \
    (struct { struct CCC_Tree_map private; }){(__extension__({                 \
        typeof(*private_compound_literal_array) *private_tree_map_type_array   \
            = private_compound_literal_array;                                  \
        struct CCC_Tree_map private_map = CCC_private_tree_map_default(        \
            typeof(*private_tree_map_type_array),                              \
            private_type_intruder_field_name,                                  \
            private_key_field_name,                                            \
            private_comparator                                                 \
        );                                                                     \
        CCC_Allocator const *const private_tree_map_allocator                  \
            = &(private_allocator);                                            \
        if (private_tree_map_allocator->allocate) {                            \
            size_t const private_count                                         \
                = sizeof(private_compound_literal_array)                       \
                / sizeof(*private_tree_map_type_array);                        \
            for (size_t private_i = 0; private_i < private_count;              \
                 ++private_i) {                                                \
                struct CCC_Tree_map_entry private_tree_map_entry               \
                    = CCC_private_tree_map_entry(                              \
                        &private_map,                                          \
                        (void *)&private_tree_map_type_array[private_i]        \
                            .private_key_field_name                            \
                    );                                                         \
                if (!(private_tree_map_entry.entry.status                      \
                      & CCC_ENTRY_OCCUPIED)) {                                 \
                    typeof(*private_tree_map_type_array) *const                \
                        private_new_slot                                       \
                        = private_tree_map_allocator->allocate((               \
                            CCC_Allocator_arguments                            \
                        ){                                                     \
                            .input = NULL,                                     \
                            .bytes = private_map.sizeof_type,                  \
                            .alignment = private_map.alignof_type,             \
                            .context = private_tree_map_allocator->context,    \
                        });                                                    \
                    if (!private_new_slot) {                                   \
                        (void)CCC_tree_map_clear(                              \
                            &private_map,                                      \
                            &private_destructor,                               \
                            private_tree_map_allocator                         \
                        );                                                     \
                        break;                                                 \
                    }                                                          \
                    *private_new_slot                                          \
                        = private_tree_map_type_array[private_i];              \
                    CCC_private_tree_map_insert(                               \
                        &private_map,                                          \
                        CCC_private_tree_map_node_in_slot(                     \
                            &private_map, private_tree_map_entry.entry.type    \
                        ),                                                     \
                        private_tree_map_entry.last_order,                     \
                        CCC_private_tree_map_node_in_slot(                     \
                            &private_map, private_new_slot                     \
                        )                                                      \
                    );                                                         \
                } else {                                                       \
                    struct CCC_Tree_map_node private_node_saved                \
                        = *CCC_private_tree_map_node_in_slot(                  \
                            &private_map, private_tree_map_entry.entry.type    \
                        );                                                     \
                    *((typeof(*private_tree_map_type_array) *)                 \
                          private_tree_map_entry.entry.type)                   \
                        = private_tree_map_type_array[private_i];              \
                    *CCC_private_tree_map_node_in_slot(                        \
                        &private_map, private_tree_map_entry.entry.type        \
                    ) = private_node_saved;                                    \
                }                                                              \
            }                                                                  \
        }                                                                      \
        private_map;                                                           \
    }))}.private
 
/*==================   Helper Macros for Repeated Logic     =================*/
 
#define CCC_private_tree_map_new(                                              \
    private_tree_map_entry, private_allocator_pointer                          \
)                                                                              \
    (__extension__({                                                           \
        void *private_tree_map_ins_allocate_ret = NULL;                        \
        if ((private_allocator_pointer)->allocate) {                           \
            private_tree_map_ins_allocate_ret                                  \
                = (private_allocator_pointer)                                  \
                      ->allocate((CCC_Allocator_arguments){                    \
                          .input = NULL,                                       \
                          .bytes = (private_tree_map_entry)->map->sizeof_type, \
                          .alignment                                           \
                          = (private_tree_map_entry)->map->alignof_type,       \
                          .context = (private_allocator_pointer)->context,     \
                      });                                                      \
        }                                                                      \
        private_tree_map_ins_allocate_ret;                                     \
    }))
 
#define CCC_private_tree_map_insert_key_val(                                   \
    private_tree_map_entry, new_data, type_compound_literal...                 \
)                                                                              \
    (__extension__({                                                           \
        if (new_data) {                                                        \
            *new_data = type_compound_literal;                                 \
            new_data = CCC_private_tree_map_insert(                            \
                (private_tree_map_entry)->map,                                 \
                CCC_private_tree_map_node_in_slot(                             \
                    (private_tree_map_entry)->map,                             \
                    (private_tree_map_entry)->entry.type                       \
                ),                                                             \
                (private_tree_map_entry)->last_order,                          \
                CCC_private_tree_map_node_in_slot(                             \
                    (private_tree_map_entry)->map, new_data                    \
                )                                                              \
            );                                                                 \
        }                                                                      \
    }))
 
#define CCC_private_tree_map_insert_and_copy_key(                              \
    tree_map_insert_entry,                                                     \
    tree_map_insert_entry_ret,                                                 \
    key,                                                                       \
    private_allocator_pointer,                                                 \
    type_compound_literal...                                                   \
)                                                                              \
    (__extension__({                                                           \
        typeof(type_compound_literal) *private_tree_map_new_ins_base           \
            = CCC_private_tree_map_new(                                        \
                (&tree_map_insert_entry), private_allocator_pointer            \
            );                                                                 \
        tree_map_insert_entry_ret = (CCC_Entry){                               \
            .type = private_tree_map_new_ins_base,                             \
            .status = CCC_ENTRY_INSERT_ERROR,                                  \
        };                                                                     \
        if (private_tree_map_new_ins_base) {                                   \
            tree_map_insert_entry_ret.status = CCC_ENTRY_VACANT;               \
            *private_tree_map_new_ins_base = type_compound_literal;            \
            *((typeof(key) *)CCC_private_tree_map_key_in_slot(                 \
                tree_map_insert_entry.map, private_tree_map_new_ins_base       \
            )) = key;                                                          \
            (void)CCC_private_tree_map_insert(                                 \
                tree_map_insert_entry.map,                                     \
                CCC_private_tree_map_node_in_slot(                             \
                    tree_map_insert_entry.map,                                 \
                    tree_map_insert_entry.entry.type                           \
                ),                                                             \
                tree_map_insert_entry.last_order,                              \
                CCC_private_tree_map_node_in_slot(                             \
                    tree_map_insert_entry.map, private_tree_map_new_ins_base   \
                )                                                              \
            );                                                                 \
        }                                                                      \
    }))
 
/*==================     Core Macro Implementations     =====================*/
 
#define CCC_private_tree_map_and_modify_with(                                  \
    private_tree_map_entry_pointer,                                            \
    closure_parameter,                                                         \
    closure_over_closure_parameter...                                          \
)                                                                              \
    (__extension__({                                                           \
        struct CCC_Tree_map_entry const *const private_tree_map_ent_pointer    \
            = (private_tree_map_entry_pointer);                                \
        struct CCC_Tree_map_entry private_tree_map_mod_ent                     \
            = {.entry = {.status = CCC_ENTRY_ARGUMENT_ERROR}};                 \
        if (private_tree_map_ent_pointer) {                                    \
            private_tree_map_mod_ent = *private_tree_map_ent_pointer;          \
            if (private_tree_map_mod_ent.entry.status & CCC_ENTRY_OCCUPIED) {  \
                closure_parameter = private_tree_map_mod_ent.entry.type;       \
                closure_over_closure_parameter                                 \
            }                                                                  \
        }                                                                      \
        private_tree_map_mod_ent;                                              \
    }))
 
#define CCC_private_tree_map_or_insert_with(                                   \
    private_tree_map_entry_pointer,                                            \
    private_allocator_pointer,                                                 \
    type_compound_literal...                                                   \
)                                                                              \
    (__extension__({                                                           \
        struct CCC_Tree_map_entry const *const private_or_ins_entry_pointer    \
            = (private_tree_map_entry_pointer);                                \
        typeof(type_compound_literal) *private_tree_map_or_ins_ret = NULL;     \
        CCC_Allocator const *const private_tree_map_allocator                  \
            = (private_allocator_pointer);                                     \
        if (private_tree_map_allocator && private_or_ins_entry_pointer) {      \
            if (private_or_ins_entry_pointer->entry.status                     \
                == CCC_ENTRY_OCCUPIED) {                                       \
                private_tree_map_or_ins_ret                                    \
                    = private_or_ins_entry_pointer->entry.type;                \
            } else {                                                           \
                private_tree_map_or_ins_ret = CCC_private_tree_map_new(        \
                    private_or_ins_entry_pointer, private_tree_map_allocator   \
                );                                                             \
                CCC_private_tree_map_insert_key_val(                           \
                    private_or_ins_entry_pointer,                              \
                    private_tree_map_or_ins_ret,                               \
                    type_compound_literal                                      \
                );                                                             \
            }                                                                  \
        }                                                                      \
        private_tree_map_or_ins_ret;                                           \
    }))
 
#define CCC_private_tree_map_insert_entry_with(                                \
    private_tree_map_entry_pointer,                                            \
    private_allocator_pointer,                                                 \
    type_compound_literal...                                                   \
)                                                                              \
    (__extension__({                                                           \
        struct CCC_Tree_map_entry const *const private_ins_entry_pointer       \
            = (private_tree_map_entry_pointer);                                \
        typeof(type_compound_literal) *private_tree_map_ins_ent_ret = NULL;    \
        CCC_Allocator const *const private_tree_map_allocator                  \
            = (private_allocator_pointer);                                     \
        if (private_tree_map_allocator && private_ins_entry_pointer) {         \
            if (!(private_ins_entry_pointer->entry.status                      \
                  & CCC_ENTRY_OCCUPIED)) {                                     \
                private_tree_map_ins_ent_ret = CCC_private_tree_map_new(       \
                    private_ins_entry_pointer, private_allocator_pointer       \
                );                                                             \
                CCC_private_tree_map_insert_key_val(                           \
                    private_ins_entry_pointer,                                 \
                    private_tree_map_ins_ent_ret,                              \
                    type_compound_literal                                      \
                );                                                             \
            } else if (private_ins_entry_pointer->entry.status                 \
                       == CCC_ENTRY_OCCUPIED) {                                \
                struct CCC_Tree_map_node private_ins_ent_saved                 \
                    = *CCC_private_tree_map_node_in_slot(                      \
                        private_ins_entry_pointer->map,                        \
                        private_ins_entry_pointer->entry.type                  \
                    );                                                         \
                *((typeof(private_tree_map_ins_ent_ret))                       \
                      private_ins_entry_pointer->entry.type)                   \
                    = type_compound_literal;                                   \
                *CCC_private_tree_map_node_in_slot(                            \
                    private_ins_entry_pointer->map,                            \
                    private_ins_entry_pointer->entry.type                      \
                ) = private_ins_ent_saved;                                     \
                private_tree_map_ins_ent_ret                                   \
                    = private_ins_entry_pointer->entry.type;                   \
            }                                                                  \
        }                                                                      \
        private_tree_map_ins_ent_ret;                                          \
    }))
 
#define CCC_private_tree_map_try_insert_with(                                  \
    Tree_map_pointer, key, private_allocator_pointer, type_compound_literal... \
)                                                                              \
    (__extension__({                                                           \
        struct CCC_Tree_map *const private_try_ins_map_pointer                 \
            = (Tree_map_pointer);                                              \
        CCC_Entry private_tree_map_try_ins_ent_ret                             \
            = {.status = CCC_ENTRY_ARGUMENT_ERROR};                            \
        CCC_Allocator const *const private_tree_map_allocator                  \
            = (private_allocator_pointer);                                     \
        if (private_tree_map_allocator && private_try_ins_map_pointer) {       \
            __auto_type private_tree_map_key = (key);                          \
            struct CCC_Tree_map_entry private_tree_map_try_ins_ent             \
                = CCC_private_tree_map_entry(                                  \
                    private_try_ins_map_pointer, (void *)&private_tree_map_key \
                );                                                             \
            if (!(private_tree_map_try_ins_ent.entry.status                    \
                  & CCC_ENTRY_OCCUPIED)) {                                     \
                CCC_private_tree_map_insert_and_copy_key(                      \
                    private_tree_map_try_ins_ent,                              \
                    private_tree_map_try_ins_ent_ret,                          \
                    private_tree_map_key,                                      \
                    private_tree_map_allocator,                                \
                    type_compound_literal                                      \
                );                                                             \
            } else if (private_tree_map_try_ins_ent.entry.status               \
                       == CCC_ENTRY_OCCUPIED) {                                \
                private_tree_map_try_ins_ent_ret                               \
                    = private_tree_map_try_ins_ent.entry;                      \
            }                                                                  \
        }                                                                      \
        private_tree_map_try_ins_ent_ret;                                      \
    }))
 
#define CCC_private_tree_map_insert_or_assign_with(                            \
    Tree_map_pointer, key, private_allocator_pointer, type_compound_literal... \
)                                                                              \
    (__extension__({                                                           \
        struct CCC_Tree_map *const private_ins_or_assign_map_pointer           \
            = (Tree_map_pointer);                                              \
        CCC_Entry private_tree_map_ins_or_assign_ent_ret                       \
            = {.status = CCC_ENTRY_ARGUMENT_ERROR};                            \
        CCC_Allocator const *const private_tree_map_allocator                  \
            = (private_allocator_pointer);                                     \
        if (private_tree_map_allocator && private_ins_or_assign_map_pointer) { \
            __auto_type private_tree_map_key = (key);                          \
            struct CCC_Tree_map_entry private_tree_map_ins_or_assign_ent       \
                = CCC_private_tree_map_entry(                                  \
                    private_ins_or_assign_map_pointer,                         \
                    (void *)&private_tree_map_key                              \
                );                                                             \
            if (!(private_tree_map_ins_or_assign_ent.entry.status              \
                  & CCC_ENTRY_OCCUPIED)) {                                     \
                CCC_private_tree_map_insert_and_copy_key(                      \
                    private_tree_map_ins_or_assign_ent,                        \
                    private_tree_map_ins_or_assign_ent_ret,                    \
                    private_tree_map_key,                                      \
                    private_tree_map_allocator,                                \
                    type_compound_literal                                      \
                );                                                             \
            } else if (private_tree_map_ins_or_assign_ent.entry.status         \
                       == CCC_ENTRY_OCCUPIED) {                                \
                struct CCC_Tree_map_node private_ins_ent_saved                 \
                    = *CCC_private_tree_map_node_in_slot(                      \
                        private_tree_map_ins_or_assign_ent.map,                \
                        private_tree_map_ins_or_assign_ent.entry.type          \
                    );                                                         \
                *((typeof(type_compound_literal) *)                            \
                      private_tree_map_ins_or_assign_ent.entry.type)           \
                    = type_compound_literal;                                   \
                *CCC_private_tree_map_node_in_slot(                            \
                    private_tree_map_ins_or_assign_ent.map,                    \
                    private_tree_map_ins_or_assign_ent.entry.type              \
                ) = private_ins_ent_saved;                                     \
                private_tree_map_ins_or_assign_ent_ret                         \
                    = private_tree_map_ins_or_assign_ent.entry;                \
                *((typeof(private_tree_map_key) *)                             \
                      CCC_private_tree_map_key_in_slot(                        \
                          private_tree_map_ins_or_assign_ent.map,              \
                          private_tree_map_ins_or_assign_ent_ret.type          \
                      )) = private_tree_map_key;                               \
            }                                                                  \
        }                                                                      \
        private_tree_map_ins_or_assign_ent_ret;                                \
    }))
 
/* NOLINTEND(readability-identifier-naming) */
 
#endif /* CCC_PRIVATE_REALTIME__ADAPTIVE_MAP_H */