The Flat Priority Queue Interface. More...

#include "buffer.h"
#include "private/private_flat_priority_queue.h"
#include "types.h"

Include dependency graph for flat_priority_queue.h:

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

Detailed Description

The Flat Priority Queue Interface.

A flat priority queue is a contiguous container storing elements in heap order. This offers tightly packed data for efficient push, pop, min/max operations in O(lg N) time.

A flat priority queue can use memory sources from the stack, heap, or data segment and can be initialized at compile or runtime. The container offers efficient initialization options such as an O(N) heap building initializer. The flat priority queue also offers a destructive heap sort option if the user desires an in-place strict O(N * log(N)) and O(1) space sort that does not use recursion.

Many functions in the interface request a temporary argument be passed as a swap slot. This is because a flat priority queue is backed by a binary heap and swaps elements to maintain its properties. Because the user may forgo passing an allocator, the user must provide this swap slot. An easy way to do this in C99 and later is with anonymous compound literal references. For example, if we have a int flat priority queue we can provide a temporary slot inline to a function as follows.

CCC_flat_priority_queue_pop(&priority_queue, &(int){});

CCC_flat_priority_queue_pop

CCC_Result CCC_flat_priority_queue_pop(CCC_Flat_priority_queue *priority_queue, void *temp)

Pop the front element (min or max) element in the flat_priority_queue. O(lgN).

Any user defined struct can also use this technique.

CCC_flat_priority_queue_pop(&priority_queue, &(struct My_type){});

This is the preferred method because the storage remains anonymous and inaccessible to other code in the calling scope.

To shorten names in the interface, define the following preprocessor directive at the top of your file.

#define FLAT_PRIORITY_QUEUE_USING_NAMESPACE_CCC

All types and functions can then be written without the CCC_ prefix.

Initialization Interface
Initialize the container with memory, callbacks, and permissions.
#define	CCC_flat_priority_queue_default(type_name, order, comparator...) CCC_private_flat_priority_queue_default(type_name, order, comparator)
	Initialize an empty priority queue.

#define	CCC_flat_priority_queue_for( type_name, order, comparator, capacity, data_pointer)
	Initialize a priority_queue as a min or max heap.

#define	CCC_flat_priority_queue_heapify( type_name, order, comparator, capacity, count, data_pointer...)
	Partial order an array of elements as a min or max heap at runtime in O(N) time and space equal to the provided data capacity.

#define	CCC_flat_priority_queue_from( order, comparator, allocator, optional_capacity, compound_literal_array...)
	Partial order a compound literal array of elements as a min or max heap. O(N).

#define	CCC_flat_priority_queue_with_capacity( type_name, order, comparator, allocator, capacity)
	Initialize a Flat_priority_queue with a capacity.

#define	CCC_flat_priority_queue_with_storage( order, comparator, compound_literal_array)
	Initialize a priority_queue as a min or max heap with no allocation permission, no context data, and a compound literal as backing storage.

CCC_Result	CCC_flat_priority_queue_copy (CCC_Flat_priority_queue destination, CCC_Flat_priority_queue const source, CCC_Allocator const *allocator)
	Copy the priority_queue from source to newly initialized destination.

CCC_Result	CCC_flat_priority_queue_reserve (CCC_Flat_priority_queue priority_queue, size_t to_add, CCC_Allocator const allocator)
	Reserves space for at least to_add more elements.

Insert and Remove Interface
Insert or remove elements from the flat priority queue.
#define	CCC_flat_priority_queue_emplace( priority_queue_pointer, allocator_pointer, type_compound_literal...)
	Write a type directly to a priority queue slot. O(lgN).

#define	CCC_flat_priority_queue_update_with( priority_queue_pointer, closure_parameter, update_closure_over_closure_parameter...)
	Update the held user type stored in the priority queue. O(lgN).

#define	CCC_flat_priority_queue_increase_with( flat_priority_queue_pointer, closure_parameter, increase_closure_over_closure_parameter...)
	Increase the user type stored in the priority queue directly. O(lgN).

#define	CCC_flat_priority_queue_decrease_with( flat_priority_queue_pointer, closure_parameter, decrease_closure_over_closure_parameter...)
	Increase the user type stored in the priority queue directly. O(lgN).

CCC_Result	CCC_flat_priority_queue_copy_heapify (CCC_Flat_priority_queue priority_queue, CCC_Buffer const buffer, void temp, CCC_Allocator const allocator)
	Copy input buffer into the flat priority queue, organizing into data into heap order in O(N) time.

CCC_Flat_priority_queue	CCC_flat_priority_queue_in_place_heapify (CCC_Buffer buffer, void temp, CCC_Order order, CCC_Comparator const *comparator)
	Order count elements of the input Buffer as a flat priority queue, destroying the input metadata Buffer struct taking ownership of its underlying memory.

void *	CCC_flat_priority_queue_push (CCC_Flat_priority_queue priority_queue, void const type, void temp, CCC_Allocator const allocator)
	Pushes element pointed to at e into flat_priority_queue. O(lgN).

CCC_Result	CCC_flat_priority_queue_pop (CCC_Flat_priority_queue priority_queue, void temp)
	Pop the front element (min or max) element in the flat_priority_queue. O(lgN).

CCC_Result	CCC_flat_priority_queue_erase (CCC_Flat_priority_queue priority_queue, void type, void *temp)
	Erase element e that is a handle to the stored flat_priority_queue element.

void *	CCC_flat_priority_queue_update (CCC_Flat_priority_queue priority_queue, void type, void temp, CCC_Modifier const modifier)
	Update e that is a handle to the stored priority_queue element. O(lgN).

void *	CCC_flat_priority_queue_increase (CCC_Flat_priority_queue priority_queue, void type, void temp, CCC_Modifier const modifier)
	Increase type that is a handle to the stored flat_priority_queue element. O(lgN).

void *	CCC_flat_priority_queue_decrease (CCC_Flat_priority_queue priority_queue, void type, void temp, CCC_Modifier const modifier)
	Decrease e that is a handle to the stored flat_priority_queue element. O(lgN).

Container Types
Types available in the container interface.
typedef struct CCC_Flat_priority_queue	CCC_Flat_priority_queue
	A container offering direct storage and sorting of user data by heap order.

Deallocation Interface
Deallocate the container or destroy the heap invariants.
CCC_Result	CCC_flat_priority_queue_clear (CCC_Flat_priority_queue priority_queue, CCC_Destructor const destructor)
	Clears the priority_queue calling destroy on every element if provided. O(1)-O(N).

CCC_Result	CCC_flat_priority_queue_clear_and_free (CCC_Flat_priority_queue priority_queue, CCC_Destructor const destructor, CCC_Allocator const *allocator)
	Clears the priority_queue calling destroy on every element if provided. O(1)-O(N).

State Interface
Obtain state from the container.
void *	CCC_flat_priority_queue_front (CCC_Flat_priority_queue const *priority_queue)
	Return a pointer to the front (min or max) element in the flat_priority_queue. O(1).

CCC_Tribool	CCC_flat_priority_queue_is_empty (CCC_Flat_priority_queue const *priority_queue)
	Returns true if the priority_queue is empty false if not. O(1).

CCC_Count	CCC_flat_priority_queue_count (CCC_Flat_priority_queue const *priority_queue)
	Returns the count of the priority_queue active slots.

CCC_Count	CCC_flat_priority_queue_capacity (CCC_Flat_priority_queue const *priority_queue)
	Returns the capacity of the priority_queue representing total possible slots.

void *	CCC_flat_priority_queue_data (CCC_Flat_priority_queue const *priority_queue)
	Return a pointer to the base of the backing array. O(1).

CCC_Tribool	CCC_flat_priority_queue_validate (CCC_Flat_priority_queue const *priority_queue)
	Verifies the internal invariants of the priority_queue hold.

CCC_Order	CCC_flat_priority_queue_order (CCC_Flat_priority_queue const *priority_queue)
	Return the order used to initialize the flat_priority_queue.

Macro Definition Documentation

◆ CCC_flat_priority_queue_decrease_with

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

Value:

    CCC_private_flat_priority_queue_decrease_with(                             \
        flat_priority_queue_pointer,                                           \
        closure_parameter,                                                     \
        decrease_closure_over_closure_parameter                                \
    )

Increase the user type stored in the priority queue directly. O(lgN).

Parameters

[in]	flat_priority_queue_pointer	a pointer to the flat priority queue.
[in]	closure_parameter	a pointer variable to user type being decreased.
[in]	decrease_closure_over_closure_parameter	the semicolon separated statements to execute on the user type provided (optionally wrapping {code here} in braces may help with formatting). This closure may safely decrease the key used to track the user element's priority in the priority queue.

Returns: a reference to the element at its new position in the priority queue on success, NULL if parameters are invalid or the priority queue is empty.

Warning: the user must ensure type_pointer is in the priority queue.

#define FLAT_PRIORITY_QUEUE_USING_NAMESPACE_CCC
Flat_priority_queue priority_queue = build_rand_int_flat_priority_queue();
int *e = get_rand_flat_priority_queue_node(&flat_priority_queue);
(void)flat_priority_queue_decrease_with(&flat_priority_queue, e, { (*e)--; });

Note that if this priority queue is min or max, the runtime is the same.

◆ CCC_flat_priority_queue_default

#define CCC_flat_priority_queue_default	(	type_name,
		order,
		comparator...
	)	CCC_private_flat_priority_queue_default(type_name, order, comparator)

Initialize an empty priority queue.

Parameters

[in]	type_name	the name of the user type.
[in]	order	desired order of this priority queue.
[in]	comparator	a pointer to the CCC_Comparator.

Returns: the initialized priority queue on the right hand side of an equality operator.

◆ CCC_flat_priority_queue_emplace

#define CCC_flat_priority_queue_emplace	(	priority_queue_pointer,
		allocator_pointer,
		type_compound_literal...
	)

Value:

    CCC_private_flat_priority_queue_emplace(                                   \
        priority_queue_pointer, allocator_pointer, type_compound_literal       \
    )

Write a type directly to a priority queue slot. O(lgN).

Parameters

[in]	priority_queue_pointer	a pointer to the priority queue.
[in]	allocator_pointer	a pointer to CCC_Allocator.
[in]	type_compound_literal	the compound literal or direct scalar type.

Returns: a reference to the inserted element or NULL if allocation failed.

◆ CCC_flat_priority_queue_for

#define CCC_flat_priority_queue_for	(	type_name,
		order,
		comparator,
		capacity,
		data_pointer
	)

Value:

    CCC_private_flat_priority_queue_for(                                       \
        type_name, order, comparator, capacity, data_pointer                   \
    )

Initialize a priority_queue as a min or max heap.

Parameters

[in]	type_name	the name of the user type.
[in]	order	CCC_ORDER_LESSER or CCC_ORDER_GREATER for min or max heap, respectively.
[in]	comparator	a CCC_Comparator for comparing two user types.
[in]	capacity	the capacity of contiguous elements at data_pointer.
[in]	data_pointer	a pointer to an array of user types or NULL.

Returns: the initialized priority queue on the right hand side of an equality operator.

◆ CCC_flat_priority_queue_from

#define CCC_flat_priority_queue_from	(	order,
		comparator,
		allocator,
		optional_capacity,
		compound_literal_array...
	)

Value:

    CCC_private_flat_priority_queue_from(                                      \
        order,                                                                 \
        comparator,                                                            \
        allocator,                                                             \
        optional_capacity,                                                     \
        compound_literal_array                                                 \
    )

Partial order a compound literal array of elements as a min or max heap. O(N).

Parameters

[in]	order	CCC_ORDER_LESSER or CCC_ORDER_GREATER for min or max heap, respectively.
[in]	comparator	a CCC_Comparator for comparing two user types.
[in]	allocator	a CCC_Allocator for allocating the needed memory to copy in the provided compound literal data.
[in]	optional_capacity	the optional capacity larger than the input compound literal array array to reserve. If capacity provided is less than the size of the input compound literal array, the capacity is set to the size of the input compound literal array. If not needed, simply leave as zero.
[in]	compound_literal_array	the initializer of the type stored in flat priority queue (e.g. `(int[]){1,2,3}`).

Returns: the initialized priority queue on the right hand side of an equality operator.

Warning: One additional element of the provided type is allocated on the stack for swapping purposes.

Initialize a dynamic Flat_priority_queue with capacity equal to size.

#define FLAT_PRIORITY_QUEUE_USING_NAMESPACE_CCC
int
main(void)
{
    Flat_priority_queue f = flat_priority_queue_from(
        CCC_ORDER_LESSER,
        int_comparator,
        std_allocator,
        0,
        (int[]){6, 99, 32, 44, 1, 0}
    );
    return 0;
}

Initialize a dynamic Flat_priority_queue with a large capacity.

#define FLAT_PRIORITY_QUEUE_USING_NAMESPACE_CCC
int
main(void)
{
    Flat_priority_queue f = flat_priority_queue_from(
        CCC_ORDER_LESSER,
        int_comparator,
        std_allocator,
        4096,
        (int[]){6, 99, 32, 44, 1, 0}
    );
    return 0;
}

Only dynamic priority queues may be initialized this way. For static or stack based initialization of fixed capacity compound literals with no elements see the CCC_flat_priority_queue_with_storage() macro.

◆ CCC_flat_priority_queue_heapify

#define CCC_flat_priority_queue_heapify	(	type_name,
		order,
		comparator,
		capacity,
		count,
		data_pointer...
	)

Value:

    CCC_private_flat_priority_queue_heapify(                                   \
        type_name, order, comparator, capacity, count, data_pointer            \
    )

Partial order an array of elements as a min or max heap at runtime in O(N) time and space equal to the provided data capacity.

Parameters

[in]	type_name	the name of the user type.
[in]	order	CCC_ORDER_LESSER or CCC_ORDER_GREATER for min or max heap, respectively.
[in]	comparator	a CCC_Comparator for comparing two user types.
[in]	capacity	the capacity of contiguous elements at data_pointer.
[in]	count	the count <= capacity of valid elements.
[in]	data_pointer	a pointer to an array of user types or NULL.

Returns: the initialized priority queue on the right hand side of an equality operator.

Warning: One additional element of the provided type is allocated on the stack for swapping purposes.

◆ CCC_flat_priority_queue_increase_with

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

Value:

    CCC_private_flat_priority_queue_increase_with(                             \
        flat_priority_queue_pointer,                                           \
        closure_parameter,                                                     \
        increase_closure_over_closure_parameter                                \
    )

Increase the user type stored in the priority queue directly. O(lgN).

Parameters

[in]	flat_priority_queue_pointer	a pointer to the flat priority queue.
[in]	closure_parameter	a pointer variable to user type being increased.
[in]	increase_closure_over_closure_parameter	the semicolon separated statements to execute on the user type provided (optionally wrapping {code here} in braces may help with formatting). This closure may safely increase the key used to track the user element's priority in the priority queue.

Returns: a reference to the element at its new position in the flat_priority_queue on success, NULL if parameters are invalid or flat_priority_queue is empty.

Warning: the user must ensure the closure parameter is in the priority queue.

#define FLAT_PRIORITY_QUEUE_USING_NAMESPACE_CCC
Flat_priority_queue priority_queue = build_rand_int_flat_priority_queue();
int *e = get_rand_flat_priority_queue_node(&flat_priority_queue);
(void)flat_priority_queue_increase_with(&flat_priority_queue, e, { (*e)++; });

Note that if this priority queue is min or max, the runtime is the same.

◆ CCC_flat_priority_queue_update_with

#define CCC_flat_priority_queue_update_with	(	priority_queue_pointer,
		closure_parameter,
		update_closure_over_closure_parameter...
	)

Value:

    CCC_private_flat_priority_queue_update_with(                               \
        priority_queue_pointer,                                                \
        closure_parameter,                                                     \
        update_closure_over_closure_parameter                                  \
    )

Update the held user type stored in the priority queue. O(lgN).

Parameters

[in]	priority_queue_pointer	a pointer to the flat priority queue.
[in]	closure_parameter	a pointer variable to the user type being updated.
[in]	update_closure_over_closure_parameter	the semicolon separated statements to execute on the user type provided (optionally wrapping {code here} in braces may help with formatting). This closure may safely modify the key used to track the user element's priority in the priority queue.

Returns: a reference to the element at its new position in the priority queue on success, NULL if parameters are invalid or priority queue is empty.

Warning: This operation assumes the held closure parameter is in the priority queue.

#define FLAT_PRIORITY_QUEUE_USING_NAMESPACE_CCC
Flat_priority_queue priority_queue = build_rand_int_flat_priority_queue();
int *e = get_rand_flat_priority_queue_node(&flat_priority_queue);
(void)flat_priority_queue_update_with(&flat_priority_queue, e, {
    *e = rand_key();
});

Note that whether the key increases or decreases does not affect runtime.

◆ CCC_flat_priority_queue_with_capacity

#define CCC_flat_priority_queue_with_capacity	(	type_name,
		order,
		comparator,
		allocator,
		capacity
	)

Value:

    CCC_private_flat_priority_queue_with_capacity(                             \
        type_name, order, comparator, allocator, capacity                      \
    )

Initialize a Flat_priority_queue with a capacity.

Parameters

[in]	type_name	the name of the user type.
[in]	order	CCC_ORDER_LESSER or CCC_ORDER_GREATER for min or max heap, respectively.
[in]	comparator	a CCC_Comparator for comparing user types.
[in]	allocator	a pointer to CCC_Allocator for allocating the needed memory to reserve capacity.
[in]	capacity	the capacity of contiguous elements at data_pointer.

Returns: the initialized flat_priority_queue. Directly assign to Flat_priority_queue on the right hand side of the equality operator.

Initialize a dynamic Flat_priority_queue.

#define FLAT_PRIORITY_QUEUE_USING_NAMESPACE_CCC
int
main(void)
{
    Flat_priority_queue f = flat_priority_queue_with_capacity(
        int,
        CCC_ORDER_LESSER,
        compare_ints,
        std_allocate,
        4096
    );
    return 0;
}

Only dynamic priority queues may be initialized this way. For static or stack based initialization of fixed capacity compound literals with no elements see the CCC_flat_priority_queue_with_storage() macro.

◆ CCC_flat_priority_queue_with_storage

#define CCC_flat_priority_queue_with_storage	(	order,
		comparator,
		compound_literal_array
	)

Value:

    CCC_private_flat_priority_queue_with_storage(                              \
        order, comparator, compound_literal_array                              \
    )

Initialize a priority_queue as a min or max heap with no allocation permission, no context data, and a compound literal as backing storage.

Parameters

[in]	order	CCC_ORDER_LESSER or CCC_ORDER_GREATER for min or max heap, respectively.
[in]	comparator	CCC_Comparator for comparing user types.
[in]	compound_literal_array	the compound literal array of fixed capacity.

Returns: the initialized priority queue on the right hand side of an equality operator. Capacity of the compound literal is capacity of the priority queue.

Warning: The compound literal is NOT swapped into heap order upon initialization. This initializer is meant for compile or runtime initialization with a fixed capacity compound literal with a count of 0.

Typedef Documentation

◆ CCC_Flat_priority_queue

typedef struct CCC_Flat_priority_queue CCC_Flat_priority_queue

A container offering direct storage and sorting of user data by heap order.

Warning: it is undefined behavior to access an uninitialized container.

A flat priority queue can be initialized on the stack, heap, or data segment at runtime or compile time.

Function Documentation

◆ CCC_flat_priority_queue_capacity()

CCC_Count CCC_flat_priority_queue_capacity ( CCC_Flat_priority_queue const * priority_queue )

Returns the capacity of the priority_queue representing total possible slots.

Parameters

[in] priority_queue a pointer to the flat priority queue.

Returns: the capacity of the priority_queue or an argument error is set if flat_priority_queue is NULL.

◆ CCC_flat_priority_queue_clear()

CCC_Result CCC_flat_priority_queue_clear	(	CCC_Flat_priority_queue *	priority_queue,
		CCC_Destructor const *	destructor
	)

Clears the priority_queue calling destroy on every element if provided. O(1)-O(N).

Parameters

[in]	priority_queue	a pointer to the flat priority queue.
[in]	destructor	the destructor function and context, if needed.

Returns: OK if input is valid and clear succeeds, otherwise input error.

Note that because the priority queue is flat there is no need to free elements stored in the flat_priority_queue. However, the destructor is free to manage cleanup in other parts of user code as needed upon destruction of each element.

If the destructor is empty, &(CCC_Destructor){}, the function is O(1) and no attempt is made to free capacity of the flat_priority_queue.

◆ CCC_flat_priority_queue_clear_and_free()

CCC_Result CCC_flat_priority_queue_clear_and_free	(	CCC_Flat_priority_queue *	priority_queue,
		CCC_Destructor const *	destructor,
		CCC_Allocator const *	allocator
	)

Clears the priority_queue calling destroy on every element if provided. O(1)-O(N).

Parameters

[in]	priority_queue	a pointer to the flat priority queue.
[in]	destructor	the destructor function and context, if needed.
[in]	allocator	the allocator context needed to free storage.

Returns: OK if input is valid and clear succeeds, otherwise input error.

Note that because the priority queue is flat there is no need to free elements stored in the flat_priority_queue. However, the destructor is free to manage cleanup in other parts of user code as needed upon destruction of each element.

If the destructor is empty, &(CCC_Destructor){}, the function is O(1) and no attempt is made to free capacity of the flat_priority_queue.

◆ CCC_flat_priority_queue_copy()

CCC_Result CCC_flat_priority_queue_copy	(	CCC_Flat_priority_queue *	destination,
		CCC_Flat_priority_queue const *	source,
		CCC_Allocator const *	allocator
	)

Copy the priority_queue from source to newly initialized destination.

Parameters

[in]	destination	the destination that will copy the source flat_priority_queue.
[in]	source	the source of the flat_priority_queue.
[in]	allocator	a CCC_Allocator for resizing.

Returns: the result of the copy operation. If the destination capacity is less than the source capacity and no allocation function is provided an input error is returned. If resizing is required and resizing of destination fails a memory error is returned.

Note: destination must have capacity greater than or equal to source. If destination capacity is less than source, an allocation function must be provided with the allocate argument.

Note that there are two ways to copy data from source to destination: provide sufficient memory and pass NULL as allocate, or allow the copy function to take care of allocation for the copy.

Manual memory management with no allocation function provided.

#define FLAT_PRIORITY_QUEUE_USING_NAMESPACE_CCC
Flat_priority_queue source = flat_priority_queue_with_storage(
    CCC_ORDER_LESSER,
    int_comparator,
    (int[10]){}
);
push_rand_ints(&source, &std_allocator);
Flat_priority_queue destination = flat_priority_queue_with_storage(
    CCC_ORDER_LESSER,
    int_comparator,
    (int[11]){}
);
CCC_Result res = flat_priority_queue_copy(&destination, &source,
                                          &(CCC_Allocator){});

The above requires destination capacity be greater than or equal to source capacity. Here is memory management handed over to the copy function.

#define FLAT_PRIORITY_QUEUE_USING_NAMESPACE_CCC
Flat_priority_queue source = flat_priority_queue_default(
    int,
    CCC_ORDER_LESSER,
    int_comparator,
);
push_rand_ints(&source);
Flat_priority_queue destination = flat_priority_queue_default(
    int,
    CCC_ORDER_LESSER,
    int_comparator,
);
CCC_Result res
    = flat_priority_queue_copy(&destination, &source, &std_allocator);

These options allow users to stay consistent across containers with their memory management strategies.

◆ CCC_flat_priority_queue_copy_heapify()

CCC_Result CCC_flat_priority_queue_copy_heapify	(	CCC_Flat_priority_queue *	priority_queue,
		CCC_Buffer const *	buffer,
		void *	temp,
		CCC_Allocator const *	allocator
	)

Copy input buffer into the flat priority queue, organizing into data into heap order in O(N) time.

Parameters

[in]	priority_queue	a pointer to the priority queue.
[in]	buffer	a pointer to the buffer of types to copy into the flat priority queue and heapify.
[in]	temp	a pointer to an additional element of array type for swapping.
[in]	allocator	a pointer to CCC_Allocator for resizing.

Returns: OK if ordering was successful or an input error if bad input is provided. A permission error will occur if no allocation is allowed and the input buffer is larger than the flat priority queue capacity. A memory error will occur if reallocation is required to fit all elements but reallocation fails.

Warning: Assumes the input buffer has been initialized correctly via its interface.; Any elements in the original flat priority queue are overwritten or lost when the buffer contents are copied.

A simple way to provide a temp for swapping is with an inline compound literal reference provided directly to the function argument &(My_type){}.

Note that this version of heapify copies elements from the input buffer. If an in place heapify is required see any of the following functions.

CCC_flat_priority_queue_in_place_heapify()
CCC_flat_priority_queue_heapify()
CCC_flat_priority_queue_context_heapify_storage()
CCC_flat_priority_queue_heapify_storage()

This function does not modify the input buffer.

◆ CCC_flat_priority_queue_count()

CCC_Count CCC_flat_priority_queue_count ( CCC_Flat_priority_queue const * priority_queue )

Returns the count of the priority_queue active slots.

Parameters

[in] priority_queue a pointer to the flat priority queue.

Returns: the size of the priority_queue or an argument error is set if flat_priority_queue is NULL.

◆ CCC_flat_priority_queue_data()

void * CCC_flat_priority_queue_data ( CCC_Flat_priority_queue const * priority_queue )

Return a pointer to the base of the backing array. O(1).

Parameters

[in] priority_queue a pointer to the priority queue.

Returns: A pointer to the base of the backing array or NULL if flat_priority_queue is NULL.

Note: this reference starts at index 0 of the backing array. All flat_priority_queue elements are stored contiguously starting at the base through size of the flat_priority_queue.

Warning: it is the users responsibility to ensure that access to any data is within the capacity of the backing buffer.

◆ CCC_flat_priority_queue_decrease()

void * CCC_flat_priority_queue_decrease	(	CCC_Flat_priority_queue *	priority_queue,
		void *	type,
		void *	temp,
		CCC_Modifier const *	modifier
	)

Decrease e that is a handle to the stored flat_priority_queue element. O(lgN).

Parameters

[in]	priority_queue	a pointer to the flat priority queue.
[in]	type	a pointer to the stored priority_queue element. Must be in the flat_priority_queue.
[in]	temp	a pointer to a dummy user type that will be used for swapping.
[in]	modifier	the CCC_Modifier to operate on an element.

Returns: a reference to the element at its new position in the flat_priority_queue on success, NULL if parameters are invalid or flat_priority_queue is empty.

Warning: the user must ensure e is in the flat_priority_queue.

A simple way to provide a temp for swapping is with an inline compound literal reference provided directly to the function argument &(name_of_type){}.

◆ CCC_flat_priority_queue_erase()

CCC_Result CCC_flat_priority_queue_erase	(	CCC_Flat_priority_queue *	priority_queue,
		void *	type,
		void *	temp
	)

Erase element e that is a handle to the stored flat_priority_queue element.

Parameters

[in]	priority_queue	a pointer to the priority queue.
[in]	type	a pointer to the stored priority_queue element. Must be in the flat_priority_queue.
[in]	temp	a pointer to a dummy user type that will be used for swapping.

Returns: OK if the erase is successful or an input error if NULL arguments are provided or the priority_queue is empty.

Warning: the user must ensure e is in the flat_priority_queue.

A simple way to provide a temp for swapping is with an inline compound literal reference provided directly to the function argument &(name_of_type){}.

Note that the reference to type is invalidated after this call.

◆ CCC_flat_priority_queue_front()

void * CCC_flat_priority_queue_front ( CCC_Flat_priority_queue const * priority_queue )

Return a pointer to the front (min or max) element in the flat_priority_queue. O(1).

Parameters

[in] priority_queue a pointer to the priority queue.

Returns: A pointer to the front element or NULL if empty or flat_priority_queue is NULL.

◆ CCC_flat_priority_queue_in_place_heapify()

CCC_Flat_priority_queue CCC_flat_priority_queue_in_place_heapify	(	CCC_Buffer *	buffer,
		void *	temp,
		CCC_Order	order,
		CCC_Comparator const *	comparator
	)

Order count elements of the input Buffer as a flat priority queue, destroying the input metadata Buffer struct taking ownership of its underlying memory.

Parameters

[in]	buffer	a pointer to a buffer with memory that will be sorted into heap order, given to the flat priority queue, and its metadata struct will be cleared.
[in]	temp	a pointer to a dummy user type that will be used for swapping.
[in]	order	the order of the heap, minimum or maximum priority queue.
[in]	comparator	the comparison function used during heapify.

Returns: a flat priority queue that now owns the underlying buffer storage and is in correct heap order. If an error occurs all fields are set to 0 or NULL and the order of the priority queue is set to CCC_ORDER_ERROR. The order can be read with CCC_flat_priority_queue_order(). If an error occurs, the buffer remains unmodified.

Warning: Assumed the buffer has been correctly initialized.; All fields in the input buffer are cleared, zeroed, or set to NULL.

A simple way to provide a temp for swapping is with an inline compound literal reference provided directly to the function argument &(name_of_type){}.

◆ CCC_flat_priority_queue_increase()

void * CCC_flat_priority_queue_increase	(	CCC_Flat_priority_queue *	priority_queue,
		void *	type,
		void *	temp,
		CCC_Modifier const *	modifier
	)

Increase type that is a handle to the stored flat_priority_queue element. O(lgN).

Parameters

[in]	priority_queue	a pointer to the flat priority queue.
[in]	type	a pointer to the stored priority_queue element. Must be in the flat_priority_queue.
[in]	temp	a pointer to a dummy user type that will be used for swapping.
[in]	modifier	the CCC_Modifier to operate on an element.

Returns: a reference to the element at its new position in the flat_priority_queue on success, NULL if parameters are invalid or flat_priority_queue is empty.

Warning: the user must ensure type is in the flat_priority_queue.

A simple way to provide a temp for swapping is with an inline compound literal reference provided directly to the function argument &(name_of_type){}.

◆ CCC_flat_priority_queue_is_empty()

CCC_Tribool CCC_flat_priority_queue_is_empty ( CCC_Flat_priority_queue const * priority_queue )

Returns true if the priority_queue is empty false if not. O(1).

Parameters

[in] priority_queue a pointer to the flat priority queue.

Returns: true if the size is 0, false if not empty. Error if flat_priority_queue is NULL.

◆ CCC_flat_priority_queue_order()

CCC_Order CCC_flat_priority_queue_order ( CCC_Flat_priority_queue const * priority_queue )

Return the order used to initialize the flat_priority_queue.

Parameters

[in] priority_queue a pointer to the flat priority queue.

Returns: LES or GRT ordering. Any other ordering is invalid.

◆ CCC_flat_priority_queue_pop()

CCC_Result CCC_flat_priority_queue_pop	(	CCC_Flat_priority_queue *	priority_queue,
		void *	temp
	)

Pop the front element (min or max) element in the flat_priority_queue. O(lgN).

Parameters

[in]	priority_queue	a pointer to the priority queue.
[in]	temp	a pointer to a dummy user type that will be used for swapping.

Returns: OK if the pop succeeds or an input error if priority_queue is NULL or empty.

A simple way to provide a temp for swapping is with an inline compound literal reference provided directly to the function argument &(name_of_type){}.

◆ CCC_flat_priority_queue_push()

void * CCC_flat_priority_queue_push	(	CCC_Flat_priority_queue *	priority_queue,
		void const *	type,
		void *	temp,
		CCC_Allocator const *	allocator
	)

Pushes element pointed to at e into flat_priority_queue. O(lgN).

Parameters

[in]	priority_queue	a pointer to the priority queue.
[in]	type	a pointer to the user element of same type as in flat_priority_queue.
[in]	temp	a pointer to a dummy user type that will be used for swapping.
[in]	allocator	a pointer to CCC_Allocator for resizing.

Returns: a pointer to the inserted element or NULl if NULL arguments are provided or push required more memory and failed. Failure can occur if the flat_priority_queue is full and allocation is not allowed or a resize failed when allocation is allowed.

A simple way to provide a temp for swapping is with an inline compound literal reference provided directly to the function argument &(name_of_type){}.

◆ CCC_flat_priority_queue_reserve()

CCC_Result CCC_flat_priority_queue_reserve	(	CCC_Flat_priority_queue *	priority_queue,
		size_t	to_add,
		CCC_Allocator const *	allocator
	)

Reserves space for at least to_add more elements.

Parameters

[in]	priority_queue	a pointer to the flat priority queue.
[in]	to_add	the number of elements to add to the current size.
[in]	allocator	a pointer to CCC_Allocator for resizing.

Returns: the result of the reservation. OK if successful, otherwise an error status is returned.

Note: see the CCC_flat_priority_queue_clear_and_free_reserve function if this function is being used for a one-time dynamic reservation.

This function can be used for a dynamic priority_queue with or without allocation permission. If the priority_queue has allocation permission, it will reserve the required space and later resize if more space is needed.

If the priority_queue has been initialized with no allocation permission and no memory this function can serve as a one-time reservation. This is helpful when a fixed size is needed but that size is only known dynamically at runtime. To free the priority_queue in such a case see the CCC_flat_priority_queue_clear_and_free_reserve function.

◆ CCC_flat_priority_queue_update()

void * CCC_flat_priority_queue_update	(	CCC_Flat_priority_queue *	priority_queue,
		void *	type,
		void *	temp,
		CCC_Modifier const *	modifier
	)

Update e that is a handle to the stored priority_queue element. O(lgN).

Parameters

[in]	priority_queue	a pointer to the flat priority queue.
[in]	type	a pointer to the stored priority_queue element. Must be in the flat_priority_queue.
[in]	temp	a pointer to a dummy user type that will be used for swapping.
[in]	modifier	the modifier function to call with context, if needed.

Returns: a reference to the element at its new position in the flat_priority_queue on success, NULL if parameters are invalid or flat_priority_queue is empty.

Warning: the user must ensure e is in the flat_priority_queue.

A simple way to provide a temp for swapping is with an inline compound literal reference provided directly to the function argument &(name_of_type){}.

◆ CCC_flat_priority_queue_validate()

CCC_Tribool CCC_flat_priority_queue_validate ( CCC_Flat_priority_queue const * priority_queue )

Verifies the internal invariants of the priority_queue hold.

Parameters

[in] priority_queue a pointer to the flat priority queue.

Returns: true if the priority_queue is valid false if invalid. Error if flat_priority_queue is NULL.

Detailed Description

Initialization Interface

Insert and Remove Interface

Container Types

Deallocation Interface

State Interface

Macro Definition Documentation

◆ CCC_flat_priority_queue_decrease_with

◆ CCC_flat_priority_queue_default

◆ CCC_flat_priority_queue_emplace

◆ CCC_flat_priority_queue_for

◆ CCC_flat_priority_queue_from

◆ CCC_flat_priority_queue_heapify

◆ CCC_flat_priority_queue_increase_with

◆ CCC_flat_priority_queue_update_with

◆ CCC_flat_priority_queue_with_capacity

◆ CCC_flat_priority_queue_with_storage

Typedef Documentation

◆ CCC_Flat_priority_queue

Function Documentation

◆ CCC_flat_priority_queue_capacity()

◆ CCC_flat_priority_queue_clear()

◆ CCC_flat_priority_queue_clear_and_free()

◆ CCC_flat_priority_queue_copy()

◆ CCC_flat_priority_queue_copy_heapify()

◆ CCC_flat_priority_queue_count()

◆ CCC_flat_priority_queue_data()

◆ CCC_flat_priority_queue_decrease()

◆ CCC_flat_priority_queue_erase()

◆ CCC_flat_priority_queue_front()

◆ CCC_flat_priority_queue_in_place_heapify()

◆ CCC_flat_priority_queue_increase()

◆ CCC_flat_priority_queue_is_empty()

◆ CCC_flat_priority_queue_order()

◆ CCC_flat_priority_queue_pop()

◆ CCC_flat_priority_queue_push()

◆ CCC_flat_priority_queue_reserve()

◆ CCC_flat_priority_queue_update()

◆ CCC_flat_priority_queue_validate()