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 decide the flat priority queue has no allocation permission, 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){0});

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_initialize( data_pointer, type_name, order, compare, allocate, context_data, capacity)
	Initialize a priority_queue as a min or max heap.

#define	CCC_flat_priority_queue_heapify_initialize( data_pointer, type_name, order, compare, allocate, context_data, capacity, size)
	Partial order an array of elements as a min or max heap. O(N).

#define	CCC_flat_priority_queue_from(order, compare, allocate, context_data, 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, compare, allocate, context_data, capacity)
	Initialize a Flat_priority_queue with a capacity.

CCC_Result	CCC_flat_priority_queue_copy (CCC_Flat_priority_queue destination, CCC_Flat_priority_queue const source, CCC_Allocator *allocate)
	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 allocate)
	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, type_compound_literal...)
	Write a type directly to a priority queue slot. O(lgN).

#define	CCC_flat_priority_queue_update_with( priority_queue_pointer, type_pointer, update_closure_over_T...)
	Update the user type stored in the priority queue directly. O(lgN).

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

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

CCC_Result	CCC_flat_priority_queue_heapify (CCC_Flat_priority_queue priority_queue, void temp, void *type_array, size_t count, size_t sizeof_type)
	Copy input array into the flat_priority_queue, organizing into heap. O(N).

CCC_Result	CCC_flat_priority_queue_heapify_inplace (CCC_Flat_priority_queue priority_queue, void temp, size_t count)
	Order count elements of the underlying priority_queue Buffer as an flat_priority_queue.

void *	CCC_flat_priority_queue_push (CCC_Flat_priority_queue priority_queue, void const type, void *temp)
	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_Type_modifier modify, void *context)
	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_Type_modifier modify, void *context)
	Increase e 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_Type_modifier modify, void *context)
	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_Buffer	CCC_flat_priority_queue_heapsort (CCC_Flat_priority_queue priority_queue, void temp)
	Destroys the priority_queue by sorting its data and returning the underlying buffer. The data is sorted in `O(N * log(N))` time and `O(1)` space.

CCC_Result	CCC_flat_priority_queue_clear (CCC_Flat_priority_queue priority_queue, CCC_Type_destructor destroy)
	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_Type_destructor destroy)
	Clears the priority_queue calling destroy on every element if provided and frees the underlying buffer. O(1)-O(N).

CCC_Result	CCC_flat_priority_queue_clear_and_free_reserve (CCC_Flat_priority_queue priority_queue, CCC_Type_destructor destructor, CCC_Allocator *allocate)
	Frees all slots in the priority_queue and frees the underlying Buffer that was previously dynamically reserved with the reserve function.

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,
		type_pointer,
		decrease_closure_over_T...
	)

Value:

CCC_private_flat_priority_queue_decrease_with( \

flat_priority_queue_pointer, type_pointer, decrease_closure_over_T)

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]	type_pointer	a pointer to the user type being updated.
[in]	decrease_closure_over_T	the semicolon separated statements to execute on the user type at T (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 flat_priority_queue on success, NULL if parameters are invalid or flat_priority_queue is empty.

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

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

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

◆ CCC_flat_priority_queue_emplace

#define CCC_flat_priority_queue_emplace	(	priority_queue_pointer,
		type_compound_literal...
	)

Value:

CCC_private_flat_priority_queue_emplace(priority_queue_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]	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_from

#define CCC_flat_priority_queue_from	(	order,
		compare,
		allocate,
		context_data,
		optional_capacity,
		compound_literal_array...
	)

Value:

    CCC_private_flat_priority_queue_from(order, compare, allocate,             \
                                         context_data, 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]	compare	the user defined comparison function for user types.
[in]	allocate	the allocation function or NULL if no allocation.
[in]	context_data	any context data needed for destruction of elements.
[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. (e.g. CCC_Flat_priority_queue q = CCC_flat_priority_queue_from(...);).

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,
        compare_ints,
        std_allocate,
        NULL,
        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,
        compare_ints,
        std_allocate,
        NULL,
        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 buffers with contents known at compile time, see the CCC_flat_priority_queue_initialize() macro.

◆ CCC_flat_priority_queue_heapify_initialize

#define CCC_flat_priority_queue_heapify_initialize	(	data_pointer,
		type_name,
		order,
		compare,
		allocate,
		context_data,
		capacity,
		size
	)

Value:

    CCC_private_flat_priority_queue_heapify_initialize(                        \
        data_pointer, type_name, order, compare, allocate, context_data,       \
        capacity, size)

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

Parameters

[in]	data_pointer	a pointer to an array of user types or NULL.
[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]	compare	the user defined comparison function for user types.
[in]	allocate	the allocation function or NULL if no allocation.
[in]	context_data	any context data needed for destruction of elements.
[in]	capacity	the capacity of contiguous elements at data_pointer.
[in]	size	the size <= capacity.

Returns: the initialized priority queue on the right hand side of an equality operator. (i.e. CCC_Flat_priority_queue q = CCC_flat_priority_queue_heapify_initialize(...);).

◆ CCC_flat_priority_queue_increase_with

#define CCC_flat_priority_queue_increase_with	(	flat_priority_queue_pointer,
		type_pointer,
		increase_closure_over_T...
	)

Value:

CCC_private_flat_priority_queue_increase_with( \

flat_priority_queue_pointer, type_pointer, increase_closure_over_T)

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]	type_pointer	a pointer to the user type being updated.
[in]	increase_closure_over_T	the semicolon separated statements to execute on the user type at T (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 flat_priority_queue on success, NULL if parameters are invalid or flat_priority_queue is empty.

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

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

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

◆ CCC_flat_priority_queue_initialize

#define CCC_flat_priority_queue_initialize	(	data_pointer,
		type_name,
		order,
		compare,
		allocate,
		context_data,
		capacity
	)

Value:

    CCC_private_flat_priority_queue_initialize(data_pointer, type_name, order, \
                                               compare, allocate,              \
                                               context_data, capacity)

Initialize a priority_queue as a min or max heap.

Parameters

[in]	data_pointer	a pointer to an array of user types or NULL.
[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]	compare	the user defined comarison function for user types.
[in]	allocate	the allocation function or NULL if no allocation.
[in]	context_data	any context data needed for destruction of elements.
[in]	capacity	the capacity of contiguous elements at data_pointer.

Returns: the initialized priority queue on the right hand side of an equality operator. (i.e. CCC_Flat_priority_queue q = CCC_flat_priority_queue_initialize(...);).

◆ CCC_flat_priority_queue_update_with

#define CCC_flat_priority_queue_update_with	(	priority_queue_pointer,
		type_pointer,
		update_closure_over_T...
	)

Value:

CCC_private_flat_priority_queue_update_with( \

priority_queue_pointer, type_pointer, update_closure_over_T)

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

Parameters

[in]	priority_queue_pointer	a pointer to the flat priority queue.
[in]	type_pointer	a pointer to the user type being updated.
[in]	update_closure_over_T	the semicolon separated statements to execute on the user type at T (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 flat_priority_queue on success, NULL if parameters are invalid or flat_priority_queue is empty.

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

#define FLAT_PRIORITY_QUEUE_USING_NAMESPACE_CCC
Flat_priority_queue priority_queue = build_rand_int_flat_priority_queue();
(void)flat_priority_queue_update_with(&flat_priority_queue,
get_rand_flat_priority_queue_node(&flat_priority_queue), { *T = 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,
		compare,
		allocate,
		context_data,
		capacity
	)

Value:

CCC_private_flat_priority_queue_with_capacity( \

type_name, order, compare, allocate, context_data, 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]	compare	the user defined comparison function for user types.
[in]	allocate	the allocation function or NULL if no allocation.
[in]	context_data	any context data needed for destruction of elements.
[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 (e.g. CCC_Flat_priority_queue b = CCC_flat_priority_queue_with_capacity(...);).

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,
        NULL,
        4096
    );
    return 0;
}

Only dynamic Flat_priority_queues may be initialized this way. For static or stack based initialization of fixed flat_priority_queues with contents known at compile time, see the CCC_flat_priority_queue_initialize() macro.

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_Type_destructor *	destroy
	)

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]	destroy	the destructor function or NULL if not 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 NULL, 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_Type_destructor *	destroy
	)

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

Parameters

[in]	priority_queue	a pointer to the flat priority queue.
[in]	destroy	the destructor function or NULL if not needed.

Returns: OK if input is valid and clear succeeds, otherwise input error. If the Buffer attempts to free but is not allowed a no allocate error is returned.

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 NULL, the function is O(1) and only relies on the runtime of the provided allocation function free operation.

◆ CCC_flat_priority_queue_clear_and_free_reserve()

CCC_Result CCC_flat_priority_queue_clear_and_free_reserve	(	CCC_Flat_priority_queue *	priority_queue,
		CCC_Type_destructor *	destructor,
		CCC_Allocator *	allocate
	)

Frees all slots in the priority_queue and frees the underlying Buffer that was previously dynamically reserved with the reserve function.

Parameters

[in]	priority_queue	the priority_queue to be cleared.
[in]	destructor	the destructor for each element. NULL can be passed if no maintenance is required on the elements in the priority_queue before their slots are dropped.
[in]	allocate	the required allocation function to provide to a dynamically reserved flat_priority_queue. Any context data provided upon initialization will be passed to the allocation function when called.

Returns: the result of free operation. OK if success, or an error status to indicate the error.

Warning: It is an error to call this function on a priority_queue that was not reserved with the provided CCC_Allocator. The priority_queue must have existing memory to free.

This function covers the edge case of reserving a dynamic capacity for a flat_priority_queue at runtime but denying the priority_queue allocation permission to resize. This can help prevent a priority_queue from growing untree. The user in this case knows the priority_queue does not have allocation permission and therefore no further memory will be dedicated to the flat_priority_queue.

However, to free the priority_queue in such a case this function must be used because the priority_queue has no ability to free itself. Just as the allocation function is required to reserve memory so to is it required to free memory.

This function will work normally if called on a priority_queue with allocation permission however the normal CCC_flat_priority_queue_clear_and_free is sufficient for that use case.

◆ 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 *	allocate
	)

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]	allocate	the allocation function in case resizing of destination is needed.

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_initialize(
    (int[10]){},
    int,
    CCC_ORDER_LESSER,
    int_order,
    NULL,
    NULL,
    10
);
push_rand_ints(&source);
Flat_priority_queue destination = flat_priority_queue_initialize(
    (int[11]){},
    int,
    CCC_ORDER_LESSER,
    int_order,
    NULL,
    NULL,
    11
);
CCC_Result res = flat_priority_queue_copy(&destination, &source, NULL);

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_initialize(
    NULL,
    int,
    CCC_ORDER_LESSER,
    int_order,
    std_allocate,
    NULL,
    0
);
push_rand_ints(&source);
Flat_priority_queue destination = flat_priority_queue_initialize(
    NULL,
    int,
    CCC_ORDER_LESSER,
    int_order,
    std_allocate,
    NULL,
    0
);
CCC_Result res = flat_priority_queue_copy(&destination, &source, std_allocate);

The above allows destination to have a capacity less than that of the source as long as copy has been provided an allocation function to resize destination. Note that this would still work if copying to a destination that the user wants as a fixed size flat_priority_queue.

#define FLAT_PRIORITY_QUEUE_USING_NAMESPACE_CCC
Flat_priority_queue source = flat_priority_queue_initialize(
    NULL,
    int,
    CCC_ORDER_LESSER,
    int_order,
    std_allocate,
    NULL,
    0
);
push_rand_ints(&source);
Flat_priority_queue destination = flat_priority_queue_initialize(
    NULL,
    int,
    CCC_ORDER_LESSER,
    int_order,
    NULL,
    NULL,
    0
);
CCC_Result res = flat_priority_queue_copy(&destination, &source, std_allocate);

The above sets up destination with fixed size while source is a dynamic flat_priority_queue. Because an allocation function is provided, the destination is resized once for the copy and retains its fixed size after the copy is complete. This would require the user to manually free the underlying Buffer at destination eventually if this method is used. Usually it is better to allocate the memory explicitly before the copy if copying between ring buffers.

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

◆ 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_Type_modifier *	modify,
		void *	context
	)

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]	modify	the update function to act on e.
[in]	context	any context data needed for the update function.

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 args 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_heapify()

CCC_Result CCC_flat_priority_queue_heapify	(	CCC_Flat_priority_queue *	priority_queue,
		void *	temp,
		void *	type_array,
		size_t	count,
		size_t	sizeof_type
	)

Copy input array into the flat_priority_queue, organizing into heap. O(N).

Parameters

[in]	priority_queue	a pointer to the priority queue.
[in]	temp	a pointer to an additional element of array type for swapping.
[in]	type_array	an array of elements of the same size as the type used to initialize flat_priority_queue.
[in]	count	the number of contiguous elements at type_array.
[in]	sizeof_type	size of each element in type_array matching element size of flat_priority_queue.

Returns: OK if sorting was successful or an input error if bad input is provided. A permission error will occur if no allocation is allowed and the input array is larger than the fixed priority_queue capacity. A memory error will occur if reallocation is required to fit all elements but reallocation fails.

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 this version of heapify copies elements from the input array. If an in place heapify is required use the initializer version of this method.

◆ CCC_flat_priority_queue_heapify_inplace()

CCC_Result CCC_flat_priority_queue_heapify_inplace	(	CCC_Flat_priority_queue *	priority_queue,
		void *	temp,
		size_t	count
	)

Order count elements of the underlying priority_queue Buffer as an flat_priority_queue.

Parameters

[in]	priority_queue	a pointer to the flat priority queue.
[in]	temp	a pointer to a dummy user type that will be used for swapping.
[in]	count	the number count of elements where 0 < (n + 1) <= capacity.

Returns: the result of the heapify operation, ok if successful or an error if flat_priority_queue is NULL or count is larger than the initialized capacity of 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){}.

This is another method to order a heap that already has all the elements one needs sorted. The underlying Buffer will be interpreted to have count valid elements starting at index 0 to index count - 1.

◆ CCC_flat_priority_queue_heapsort()

CCC_Buffer CCC_flat_priority_queue_heapsort	(	CCC_Flat_priority_queue *	priority_queue,
		void *	temp
	)

Destroys the priority_queue by sorting its data and returning the underlying buffer. The data is sorted in O(N * log(N)) time and O(1) space.

Parameters

[in]	priority_queue	the priority_queue to be sorted and destroyed.
[in]	temp	a pointer to a dummy user type that will be used for swapping.

Returns: a Buffer filled from the back to the front by the flat_priority_queue order. If the priority_queue is initialized CCC_ORDER_LESSER the returned Buffer is sorted in non-increasing order from index [0, N). If the flat_priority_queue is initialized CCC_ORDER_GREATER the buffer is sorted in non-descending order from index [0, N). If priority_queue is NULL, the buffer is default initialized and unusable.

Warning: all fields of the priority_queue are cleared or otherwise default initialized so the priority_queue is unusable as a container after sorting. This function assumes the priority_queue has been previously initialized. Therefore, if the returned Buffer value is not used the flat_priority_queue memory is leaked.

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){}.

The underlying memory storage source for the flat_priority_queue, a buffer, is not moved or copied during the sort. If a copy of the sorted data is preferred copy the data the data to another initialized priority_queue with the CCC_flat_priority_queue_copy function first then sort that copy.

The sort is not inherently stable and uses the provided comparison function to the priority_queue to order the elements.

◆ CCC_flat_priority_queue_increase()

void * CCC_flat_priority_queue_increase	(	CCC_Flat_priority_queue *	priority_queue,
		void *	type,
		void *	temp,
		CCC_Type_modifier *	modify,
		void *	context
	)

Increase 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]	modify	the update function to act on e.
[in]	context	any context data needed for the update function.

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_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
	)

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.

Returns: a pointer to the inserted element or NULl if NULL args 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 *	allocate
	)

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]	allocate	the allocation function to use to reserve memory.

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_Type_modifier *	modify,
		void *	context
	)

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]	modify	the update function to act on e.
[in]	context	any context data needed for the update function.

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_emplace

◆ CCC_flat_priority_queue_from

◆ CCC_flat_priority_queue_heapify_initialize

◆ CCC_flat_priority_queue_increase_with

◆ CCC_flat_priority_queue_initialize

◆ CCC_flat_priority_queue_update_with

◆ CCC_flat_priority_queue_with_capacity

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_clear_and_free_reserve()

◆ CCC_flat_priority_queue_copy()

◆ 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_heapify()

◆ CCC_flat_priority_queue_heapify_inplace()

◆ CCC_flat_priority_queue_heapsort()

◆ 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()