private_priority_queue.h File Reference

The Private Priority Queue Types and Interface. More...

#include "../../types.h"

Include dependency graph for private_priority_queue.h:

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

Go to the source code of this file.

Detailed Description

The Private Priority Queue Types and Interface.

The intrusive priority queue is relegated to the specialized directory because it is a niche data structure with interesting space and runtime characteristics. It is not very space efficient as an intruder. However, in exchange we get O(1) push and decrease/increase operations when the decreasing on a min heap and increasing on a max heap. This costs us in later slower pop operations, resulting in an amortized little o(log(N)) runtime for decrease/increase, but the operation itself will always take O(1) time. This can have interesting implications for realtime systems with strict runtime requirements.

Data Structures
struct	CCC_Priority_queue_node
struct	CCC_Priority_queue

Macros
#define	CCC_private_priority_queue_for( private_struct_name, private_type_intruder_field, private_priority_queue_order, private_comparator...)
#define	CCC_private_priority_queue_default( private_struct_name, private_type_intruder_field, private_priority_queue_order, private_comparator)
#define	CCC_private_priority_queue_from( private_type_intruder_field, private_priority_queue_order, private_comparator, private_allocator, private_destructor, private_compound_literal_array...)
#define	CCC_private_priority_queue_emplace( priority_queue_pointer, private_allocator_pointer, type_compound_literal...)
#define	CCC_private_priority_queue_update_with( priority_queue_pointer, private_closure_parameter, private_update_closure_over_closure_parameter...)
#define	CCC_private_priority_queue_increase_with( priority_queue_pointer, private_closure_parameter, private_increase_closure_over_closure_parameter...)
#define	CCC_private_priority_queue_decrease_with( priority_queue_pointer, private_closure_parameter, private_decrease_closure_over_closure_parameter...)

Functions
void	CCC_private_priority_queue_push (struct CCC_Priority_queue *, struct CCC_Priority_queue_node *)
struct CCC_Priority_queue_node *	CCC_private_priority_queue_node_in (struct CCC_Priority_queue const *, void const *)
void	CCC_private_priority_queue_update_fixup (struct CCC_Priority_queue *, struct CCC_Priority_queue_node *)
void	CCC_private_priority_queue_increase_fixup (struct CCC_Priority_queue *, struct CCC_Priority_queue_node *)
void	CCC_private_priority_queue_decrease_fixup (struct CCC_Priority_queue *, struct CCC_Priority_queue_node *)

Macro Definition Documentation

CCC_private_priority_queue_decrease_with

#define CCC_private_priority_queue_decrease_with	(		priority_queue_pointer,
			private_closure_parameter,
			private_decrease_closure_over_closure_parameter...
	)

Value:

    (__extension__({                                                           \
        struct CCC_Priority_queue *const private_priority_queue                \
            = (priority_queue_pointer);                                        \
        typeof(*private_closure_parameter)                                     \
            *private_priority_queue_updated_element                            \
            = (private_closure_parameter);                                     \
        if (private_priority_queue                                             \
            && private_priority_queue_updated_element) {                       \
            struct CCC_Priority_queue_node *const                              \
                private_priority_queue_node_pointer                            \
                = CCC_private_priority_queue_node_in(                          \
                    private_priority_queue,                                    \
                    private_priority_queue_updated_element                     \
                );                                                             \
            {private_decrease_closure_over_closure_parameter};                 \
            CCC_private_priority_queue_decrease_fixup(                         \
                private_priority_queue, private_priority_queue_node_pointer    \
            );                                                                 \
        }                                                                      \
        private_priority_queue_updated_element;                                \
    }))

CCC_private_priority_queue_default

#define CCC_private_priority_queue_default	(		private_struct_name,
			private_type_intruder_field,
			private_priority_queue_order,
			private_comparator
	)

Value:

    CCC_private_priority_queue_for(                                            \
        private_struct_name,                                                   \
        private_type_intruder_field,                                           \
        private_priority_queue_order,                                          \
        private_comparator                                                     \
    )

CCC_private_priority_queue_emplace

#define CCC_private_priority_queue_emplace	(		priority_queue_pointer,
			private_allocator_pointer,
			type_compound_literal...
	)

CCC_private_priority_queue_for

#define CCC_private_priority_queue_for	(		private_struct_name,
			private_type_intruder_field,
			private_priority_queue_order,
			private_comparator...
	)

Value:

    (struct CCC_Priority_queue) {                                              \
        .root = NULL, .count = 0,                                              \
        .type_intruder_offset                                                  \
            = offsetof(private_struct_name, private_type_intruder_field),      \
        .sizeof_type = sizeof(private_struct_name),                            \
        .alignof_type = alignof(private_struct_name),                          \
        .order = (private_priority_queue_order),                               \
        .comparator = (private_comparator),                                    \
    }

CCC_private_priority_queue_from

#define CCC_private_priority_queue_from	(		private_type_intruder_field,
			private_priority_queue_order,
			private_comparator,
			private_allocator,
			private_destructor,
			private_compound_literal_array...
	)

CCC_private_priority_queue_increase_with

#define CCC_private_priority_queue_increase_with	(		priority_queue_pointer,
			private_closure_parameter,
			private_increase_closure_over_closure_parameter...
	)

Value:

    (__extension__({                                                           \
        struct CCC_Priority_queue *const private_priority_queue                \
            = (priority_queue_pointer);                                        \
        typeof(*private_closure_parameter)                                     \
            *private_priority_queue_updated_element                            \
            = (private_closure_parameter);                                     \
        if (private_priority_queue                                             \
            && private_priority_queue_updated_element) {                       \
            struct CCC_Priority_queue_node *const                              \
                private_priority_queue_node_pointer                            \
                = CCC_private_priority_queue_node_in(                          \
                    private_priority_queue,                                    \
                    private_priority_queue_updated_element                     \
                );                                                             \
            {private_increase_closure_over_closure_parameter};                 \
            CCC_private_priority_queue_increase_fixup(                         \
                private_priority_queue, private_priority_queue_node_pointer    \
            );                                                                 \
        }                                                                      \
        private_priority_queue_updated_element;                                \
    }))

CCC_private_priority_queue_update_with

#define CCC_private_priority_queue_update_with	(		priority_queue_pointer,
			private_closure_parameter,
			private_update_closure_over_closure_parameter...
	)

Value:

    (__extension__({                                                           \
        struct CCC_Priority_queue *const private_priority_queue                \
            = (priority_queue_pointer);                                        \
        typeof(*private_closure_parameter)                                     \
            *private_priority_queue_updated_element                            \
            = (private_closure_parameter);                                     \
        if (private_priority_queue                                             \
            && private_priority_queue_updated_element) {                       \
            struct CCC_Priority_queue_node *const                              \
                private_priority_queue_node_pointer                            \
                = CCC_private_priority_queue_node_in(                          \
                    private_priority_queue,                                    \
                    private_priority_queue_updated_element                     \
                );                                                             \
            {private_update_closure_over_closure_parameter};                   \
            CCC_private_priority_queue_update_fixup(                           \
                private_priority_queue, private_priority_queue_node_pointer    \
            );                                                                 \
        }                                                                      \
        private_priority_queue_updated_element;                                \
    }))

Function Documentation

CCC_private_priority_queue_decrease_fixup()

void CCC_private_priority_queue_decrease_fixup	(	struct CCC_Priority_queue *	,
		struct CCC_Priority_queue_node *
	)

CCC_private_priority_queue_increase_fixup()

void CCC_private_priority_queue_increase_fixup	(	struct CCC_Priority_queue *	,
		struct CCC_Priority_queue_node *
	)

CCC_private_priority_queue_node_in()

struct CCC_Priority_queue_node * CCC_private_priority_queue_node_in	(	struct CCC_Priority_queue const *	,
		void const *
	)

CCC_private_priority_queue_push()

void CCC_private_priority_queue_push	(	struct CCC_Priority_queue *	,
		struct CCC_Priority_queue_node *
	)

CCC_private_priority_queue_update_fixup()

void CCC_private_priority_queue_update_fixup	(	struct CCC_Priority_queue *	,
		struct CCC_Priority_queue_node *
	)