private_flat_priority_queue.h File Reference

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

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

Include dependency graph for private_flat_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 Flat Priority Queue Types and Interface.

The private flat priority queue interface manages the types and macros for the flat priority queue. The implementation attempts to be as efficient as possible by using bottom-up reheap operations to avoid extensive use of comparison callbacks. We also try to avoid swapping elements whenever possible. Instead, we use our temp slot to hold an element and then shift everything down or up tree levels depending on the operations. This saves 2 calls to memcpy per tree level.

Data Structures
struct	CCC_Flat_priority_queue

Macros
#define	CCC_private_flat_priority_queue_default( private_type_name, private_order, private_comparator...)
#define	CCC_private_flat_priority_queue_for( private_type_name, private_order, private_comparator, private_capacity, private_data_pointer)
#define	CCC_private_flat_priority_queue_heapify( private_type_name, private_order, private_comparator, private_capacity, private_size, private_data_pointer...)
#define	CCC_private_flat_priority_queue_from( private_order, private_comparator, private_allocator, private_optional_capacity, private_compound_literal_array...)
#define	CCC_private_flat_priority_queue_with_capacity( private_type_name, private_order, private_comparator, private_allocator, private_capacity)
#define	CCC_private_flat_priority_queue_with_storage( private_order, private_comparator, private_compound_literal)
#define	CCC_private_flat_priority_queue_emplace( flat_priority_queue, private_allocator_pointer, type_compound_literal...)
#define	CCC_private_flat_priority_queue_update_with( flat_priority_queue_pointer, closure_parameter, update_closure_over_closure_parameter...)
#define	CCC_private_flat_priority_queue_increase_with( flat_priority_queue_pointer, closure_parameter, increase_closure_over_closure_parameter...)
#define	CCC_private_flat_priority_queue_decrease_with( flat_priority_queue_pointer, closure_parameter, decrease_closure_over_closure_parameter...)

Functions
size_t	CCC_private_flat_priority_queue_bubble_up (struct CCC_Flat_priority_queue const *, void *, size_t)
void	CCC_private_flat_priority_queue_heap_order (struct CCC_Flat_priority_queue const *, void *)
void *	CCC_private_flat_priority_queue_update_fixup (struct CCC_Flat_priority_queue const *, void *, void *)

Macro Definition Documentation

CCC_private_flat_priority_queue_decrease_with

#define CCC_private_flat_priority_queue_decrease_with	(		flat_priority_queue_pointer,
			closure_parameter,
			decrease_closure_over_closure_parameter...
	)

Value:

    CCC_private_flat_priority_queue_update_with(                               \
        flat_priority_queue_pointer,                                           \
        closure_parameter,                                                     \
        decrease_closure_over_closure_parameter                                \
    )

CCC_private_flat_priority_queue_default

#define CCC_private_flat_priority_queue_default	(		private_type_name,
			private_order,
			private_comparator...
	)

Value:

    (struct CCC_Flat_priority_queue) {                                         \
        .buffer = CCC_flat_buffer_default(private_type_name),                  \
        .order = (private_order), .comparator = private_comparator,            \
    }

CCC_private_flat_priority_queue_emplace

#define CCC_private_flat_priority_queue_emplace	(		flat_priority_queue,
			private_allocator_pointer,
			type_compound_literal...
	)

Value:

    (__extension__({                                                           \
        struct CCC_Flat_priority_queue *private_flat_priority_queue            \
            = (flat_priority_queue);                                           \
        typeof(type_compound_literal) *private_flat_priority_queue_res         \
            = CCC_flat_buffer_allocate_back(                                   \
                &private_flat_priority_queue->buffer,                          \
                private_allocator_pointer                                      \
            );                                                                 \
        if (private_flat_priority_queue_res) {                                 \
            *private_flat_priority_queue_res = type_compound_literal;          \
            if (private_flat_priority_queue->buffer.count > 1) {               \
                private_flat_priority_queue_res = CCC_flat_buffer_at(          \
                    &private_flat_priority_queue->buffer,                      \
                    CCC_private_flat_priority_queue_bubble_up(                 \
                        private_flat_priority_queue,                           \
                        &(typeof(type_compound_literal)){},                    \
                        private_flat_priority_queue->buffer.count - 1          \
                    )                                                          \
                );                                                             \
            } else {                                                           \
                private_flat_priority_queue_res = CCC_flat_buffer_at(          \
                    &private_flat_priority_queue->buffer, 0                    \
                );                                                             \
            }                                                                  \
        }                                                                      \
        private_flat_priority_queue_res;                                       \
    }))

This macro "returns" a value thanks to clang and gcc statement expressions. See documentation in the flat priority_queueueue header for usage. The ugly details of the macro are hidden here in the impl header.

CCC_private_flat_priority_queue_for

#define CCC_private_flat_priority_queue_for	(		private_type_name,
			private_order,
			private_comparator,
			private_capacity,
			private_data_pointer
	)

Value:

    (struct CCC_Flat_priority_queue) {                                         \
        .buffer = CCC_flat_buffer_for(                                         \
            private_type_name, private_capacity, 0, private_data_pointer       \
        ),                                                                     \
        .order = (private_order), .comparator = (private_comparator),          \
    }

CCC_private_flat_priority_queue_from

#define CCC_private_flat_priority_queue_from	(		private_order,
			private_comparator,
			private_allocator,
			private_optional_capacity,
			private_compound_literal_array...
	)

Value:

    (struct { struct CCC_Flat_priority_queue private; }){(__extension__({      \
        struct CCC_Flat_priority_queue private_flat_priority_queue = {         \
            .buffer = CCC_flat_buffer_from(                                    \
                private_allocator,                                             \
                private_optional_capacity,                                     \
                private_compound_literal_array                                 \
            ),                                                                 \
            .order = (private_order),                                          \
            .comparator = (private_comparator),                                \
        };                                                                     \
        if (private_flat_priority_queue.buffer.count) {                        \
            CCC_private_flat_priority_queue_heap_order(                        \
                &private_flat_priority_queue,                                  \
                &(typeof(*private_compound_literal_array)){}                   \
            );                                                                 \
        }                                                                      \
        private_flat_priority_queue;                                           \
    }))}.private

CCC_private_flat_priority_queue_heapify

#define CCC_private_flat_priority_queue_heapify	(		private_type_name,
			private_order,
			private_comparator,
			private_capacity,
			private_size,
			private_data_pointer...
	)

Value:

    (struct { struct CCC_Flat_priority_queue private; }){(__extension__({      \
        typeof(*(                                                              \
            private_data_pointer                                               \
        )) *private_flat_priority_queue_heapify_data = private_data_pointer;   \
        struct CCC_Flat_priority_queue private_flat_priority_queue_heapify_res \
            = CCC_private_flat_priority_queue_for(                             \
                private_type_name,                                             \
                private_order,                                                 \
                private_comparator,                                            \
                private_capacity,                                              \
                private_flat_priority_queue_heapify_data                       \
            );                                                                 \
        private_flat_priority_queue_heapify_res.buffer.count = (private_size); \
        CCC_private_flat_priority_queue_heap_order(                            \
            &private_flat_priority_queue_heapify_res, &(private_type_name){}   \
        );                                                                     \
        private_flat_priority_queue_heapify_res;                               \
    }))}.private

CCC_private_flat_priority_queue_increase_with

#define CCC_private_flat_priority_queue_increase_with	(		flat_priority_queue_pointer,
			closure_parameter,
			increase_closure_over_closure_parameter...
	)

Value:

    CCC_private_flat_priority_queue_update_with(                               \
        flat_priority_queue_pointer,                                           \
        closure_parameter,                                                     \
        increase_closure_over_closure_parameter                                \
    )

CCC_private_flat_priority_queue_update_with

#define CCC_private_flat_priority_queue_update_with	(		flat_priority_queue_pointer,
			closure_parameter,
			update_closure_over_closure_parameter...
	)

Value:

    (__extension__({                                                           \
        struct CCC_Flat_priority_queue const *const                            \
            private_flat_priority_queue = (flat_priority_queue_pointer);       \
        typeof(*closure_parameter) *                                           \
            private_flat_priority_queue_updated_element = (closure_parameter); \
        if (private_flat_priority_queue                                        \
            && !CCC_flat_buffer_is_empty(                                      \
                &private_flat_priority_queue->buffer                           \
            )) {                                                               \
            {update_closure_over_closure_parameter};                           \
            private_flat_priority_queue_updated_element                        \
                = CCC_private_flat_priority_queue_update_fixup(                \
                    private_flat_priority_queue,                               \
                    private_flat_priority_queue_updated_element,               \
                    &(typeof(*closure_parameter)){}                            \
                );                                                             \
        }                                                                      \
        private_flat_priority_queue_updated_element;                           \
    }))

Only one update fn is needed because there is no advantage to updates if it is known they are min/max increase/decrease etc.

CCC_private_flat_priority_queue_with_capacity

#define CCC_private_flat_priority_queue_with_capacity	(		private_type_name,
			private_order,
			private_comparator,
			private_allocator,
			private_capacity
	)

Value:

    (struct { struct CCC_Flat_priority_queue private; }){(__extension__({      \
        struct CCC_Flat_priority_queue private_flat_priority_queue = {         \
            .buffer = CCC_flat_buffer_with_capacity(                           \
                private_type_name, private_allocator, private_capacity         \
            ),                                                                 \
            .order = (private_order),                                          \
            .comparator = (private_comparator),                                \
        };                                                                     \
        private_flat_priority_queue;                                           \
    }))}.private

CCC_private_flat_priority_queue_with_storage

#define CCC_private_flat_priority_queue_with_storage	(		private_order,
			private_comparator,
			private_compound_literal
	)

Value:

        (struct CCC_Flat_priority_queue) {                                     \
            .buffer                                                            \
                = CCC_flat_buffer_with_storage(0, private_compound_literal),   \
                .order = (private_order), .comparator = (private_comparator),  \
        }

Clang is more forgiving with what qualifies as a constant expression for both constructing compound literals and using static asserts. The static asserts are so helpful that it is worth every effort to give them to the user. GCC is not so forgiving.

Function Documentation

CCC_private_flat_priority_queue_bubble_up()

size_t CCC_private_flat_priority_queue_bubble_up	(	struct CCC_Flat_priority_queue const *	,
		void *	,
		size_t
	)

CCC_private_flat_priority_queue_heap_order()

void CCC_private_flat_priority_queue_heap_order	(	struct CCC_Flat_priority_queue const *	,
		void *
	)

CCC_private_flat_priority_queue_update_fixup()

void * CCC_private_flat_priority_queue_update_fixup	(	struct CCC_Flat_priority_queue const *	,
		void *	,
		void *
	)