impl_priority_queue.h

 
#ifndef CCC_IMPL_PRIORITY_QUEUE_H
#define CCC_IMPL_PRIORITY_QUEUE_H
 
#include <stddef.h>
#include "../types.h"
 
/* NOLINTBEGIN(readability-identifier-naming) */
 
struct ccc_pq_elem
{
    struct ccc_pq_elem *child;
    struct ccc_pq_elem *next;
    struct ccc_pq_elem *prev;
    struct ccc_pq_elem *parent;
};
 
struct ccc_pq
{
    struct ccc_pq_elem *root;
    size_t count;
    size_t pq_elem_offset;
    size_t sizeof_type;
    ccc_threeway_cmp order;
    ccc_any_type_cmp_fn *cmp;
    ccc_any_alloc_fn *alloc;
    void *aux;
};
 
/*=========================  Private Interface     ==========================*/
 
void ccc_impl_pq_push(struct ccc_pq *, struct ccc_pq_elem *);
struct ccc_pq_elem *ccc_impl_pq_elem_in(struct ccc_pq const *, void const *);
ccc_threeway_cmp ccc_impl_pq_cmp(struct ccc_pq const *,
                                 struct ccc_pq_elem const *,
                                 struct ccc_pq_elem const *);
struct ccc_pq_elem *ccc_impl_pq_merge(struct ccc_pq *pq,
                                      struct ccc_pq_elem *old,
                                      struct ccc_pq_elem *new);
void ccc_impl_pq_cut_child(struct ccc_pq_elem *);
void ccc_impl_pq_init_node(struct ccc_pq_elem *);
struct ccc_pq_elem *ccc_impl_pq_delete_node(struct ccc_pq *,
                                            struct ccc_pq_elem *);
void *ccc_impl_pq_struct_base(struct ccc_pq const *,
                              struct ccc_pq_elem const *);
 
/*=========================  Macro Implementations     ======================*/
 
#define ccc_impl_pq_init(impl_struct_name, impl_pq_elem_field, impl_pq_order,  \
                         impl_cmp_fn, impl_alloc_fn, impl_aux_data)            \
    {                                                                          \
        .root = NULL,                                                          \
        .count = 0,                                                            \
        .pq_elem_offset = offsetof(impl_struct_name, impl_pq_elem_field),      \
        .sizeof_type = sizeof(impl_struct_name),                               \
        .alloc = (impl_alloc_fn),                                              \
        .cmp = (impl_cmp_fn),                                                  \
        .order = (impl_pq_order),                                              \
        .aux = (impl_aux_data),                                                \
    }
 
#define ccc_impl_pq_emplace(pq_ptr, lazy_value...)                             \
    (__extension__({                                                           \
        typeof(lazy_value) *impl_pq_res = NULL;                                \
        struct ccc_pq *impl_pq = (pq_ptr);                                     \
        if (impl_pq)                                                           \
        {                                                                      \
            if (!impl_pq->alloc)                                               \
            {                                                                  \
                impl_pq_res = NULL;                                            \
            }                                                                  \
            else                                                               \
            {                                                                  \
                impl_pq_res = impl_pq->alloc(NULL, impl_pq->sizeof_type,       \
                                             impl_pq->aux);                    \
                if (impl_pq_res)                                               \
                {                                                              \
                    *impl_pq_res = lazy_value;                                 \
                    ccc_impl_pq_push(                                          \
                        impl_pq, ccc_impl_pq_elem_in(impl_pq, impl_pq_res));   \
                }                                                              \
            }                                                                  \
        }                                                                      \
        impl_pq_res;                                                           \
    }))
 
#define ccc_impl_pq_update_w(pq_ptr, any_type_ptr, update_closure_over_T...)   \
    (__extension__({                                                           \
        struct ccc_pq *const impl_pq = (pq_ptr);                               \
        typeof(*any_type_ptr) *T = (any_type_ptr);                             \
        if (impl_pq && T)                                                      \
        {                                                                      \
            struct ccc_pq_elem *const impl_pq_elem_ptr                         \
                = ccc_impl_pq_elem_in(impl_pq, T);                             \
            if (impl_pq_elem_ptr->parent                                       \
                && ccc_impl_pq_cmp(impl_pq, impl_pq_elem_ptr,                  \
                                   impl_pq_elem_ptr->parent)                   \
                       == impl_pq->order)                                      \
            {                                                                  \
                ccc_impl_pq_cut_child(impl_pq_elem_ptr);                       \
                {update_closure_over_T} impl_pq->root = ccc_impl_pq_merge(     \
                    impl_pq, impl_pq->root, impl_pq_elem_ptr);                 \
            }                                                                  \
            else                                                               \
            {                                                                  \
                impl_pq->root                                                  \
                    = ccc_impl_pq_delete_node(impl_pq, impl_pq_elem_ptr);      \
                ccc_impl_pq_init_node(impl_pq_elem_ptr);                       \
                {update_closure_over_T} impl_pq->root = ccc_impl_pq_merge(     \
                    impl_pq, impl_pq->root, impl_pq_elem_ptr);                 \
            }                                                                  \
        }                                                                      \
        T;                                                                     \
    }))
 
#define ccc_impl_pq_increase_w(pq_ptr, any_type_ptr,                           \
                               increase_closure_over_T...)                     \
    (__extension__({                                                           \
        struct ccc_pq *const impl_pq = (pq_ptr);                               \
        typeof(*any_type_ptr) *T = (any_type_ptr);                             \
        if (impl_pq && T)                                                      \
        {                                                                      \
            struct ccc_pq_elem *const impl_pq_elem_ptr                         \
                = ccc_impl_pq_elem_in(impl_pq, T);                             \
            if (impl_pq->order == CCC_GRT)                                     \
            {                                                                  \
                ccc_impl_pq_cut_child(impl_pq_elem_ptr);                       \
            }                                                                  \
            else                                                               \
            {                                                                  \
                impl_pq->root                                                  \
                    = ccc_impl_pq_delete_node(impl_pq, impl_pq_elem_ptr);      \
                ccc_impl_pq_init_node(impl_pq_elem_ptr);                       \
            }                                                                  \
            {increase_closure_over_T} impl_pq->root                            \
                = ccc_impl_pq_merge(impl_pq, impl_pq->root, impl_pq_elem_ptr); \
        }                                                                      \
        T;                                                                     \
    }))
 
#define ccc_impl_pq_decrease_w(pq_ptr, any_type_ptr,                           \
                               decrease_closure_over_T...)                     \
    (__extension__({                                                           \
        struct ccc_pq *const impl_pq = (pq_ptr);                               \
        typeof(*any_type_ptr) *T = (any_type_ptr);                             \
        if (impl_pq && T)                                                      \
        {                                                                      \
            struct ccc_pq_elem *const impl_pq_elem_ptr                         \
                = ccc_impl_pq_elem_in(impl_pq, T);                             \
            if (impl_pq->order == CCC_LES)                                     \
            {                                                                  \
                ccc_impl_pq_cut_child(impl_pq_elem_ptr);                       \
            }                                                                  \
            else                                                               \
            {                                                                  \
                impl_pq->root                                                  \
                    = ccc_impl_pq_delete_node(impl_pq, impl_pq_elem_ptr);      \
                ccc_impl_pq_init_node(impl_pq_elem_ptr);                       \
            }                                                                  \
            {decrease_closure_over_T} impl_pq->root                            \
                = ccc_impl_pq_merge(impl_pq, impl_pq->root, impl_pq_elem_ptr); \
        }                                                                      \
        T;                                                                     \
    }))
 
/* NOLINTEND(readability-identifier-naming) */
 
#endif /* CCC_IMPL_PRIORITY_QUEUE_H */