The Flat Priority Queue Interface. More...

#include "buffer.h"
#include "impl/impl_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_fpq_pop(&pq, &(int){0});

ccc_fpq_pop

ccc_result ccc_fpq_pop(ccc_flat_priority_queue *fpq, void *tmp)

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

Any user defined struct can also use this technique.

ccc_fpq_pop(&pq, &(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_fpq_init(mem_ptr, any_type_name, cmp_order, cmp_fn, alloc_fn, aux_data, capacity)
	Initialize a fpq as a min or max heap.

#define	ccc_fpq_heapify_init(mem_ptr, any_type_name, cmp_order, cmp_fn, alloc_fn, aux_data, capacity, size)
	Partial order an array of elements as a min or max heap. O(N).

ccc_result	ccc_fpq_copy (ccc_flat_priority_queue dst, ccc_flat_priority_queue const src, ccc_any_alloc_fn *fn)
	Copy the fpq from src to newly initialized dst.

ccc_result	ccc_fpq_reserve (ccc_flat_priority_queue fpq, size_t to_add, ccc_any_alloc_fn fn)
	Reserves space for at least to_add more elements.

Insert and Remove Interface
Insert or remove elements from the flat priority queue.
#define	ccc_fpq_emplace(fpq, val_initializer...) ccc_impl_fpq_emplace(fpq, val_initializer)
	Write a type directly to a priority queue slot. O(lgN).

#define	ccc_fpq_update_w(fpq_ptr, any_type_ptr, update_closure_over_T...) ccc_impl_fpq_update_w(fpq_ptr, any_type_ptr, update_closure_over_T)
	Update the user type stored in the priority queue directly. O(lgN).

#define	ccc_fpq_increase_w(fpq_ptr, any_type_ptr, increase_closure_over_T...) ccc_impl_fpq_increase_w(fpq_ptr, any_type_ptr, increase_closure_over_T)
	Increase the user type stored in the priority queue directly. O(lgN).

#define	ccc_fpq_decrease_w(fpq_ptr, any_type_ptr, decrease_closure_over_T...) ccc_impl_fpq_decrease_w(fpq_ptr, any_type_ptr, decrease_closure_over_T)
	Increase the user type stored in the priority queue directly. O(lgN).

ccc_result	ccc_fpq_heapify (ccc_flat_priority_queue fpq, void tmp, void *input_array, size_t input_n, size_t input_sizeof_type)
	Copy input array into the fpq, organizing into heap. O(N).

ccc_result	ccc_fpq_heapify_inplace (ccc_flat_priority_queue fpq, void tmp, size_t n)
	Order n elements of the underlying fpq buffer as an fpq.

ccc_result	ccc_fpq_alloc (ccc_flat_priority_queue fpq, size_t new_capacity, ccc_any_alloc_fn fn)
	Many allocate memory for the fpq.

void *	ccc_fpq_push (ccc_flat_priority_queue fpq, void const elem, void *tmp)
	Pushes element pointed to at e into fpq. O(lgN).

ccc_result	ccc_fpq_pop (ccc_flat_priority_queue fpq, void tmp)
	Pop the front element (min or max) element in the fpq. O(lgN).

ccc_result	ccc_fpq_erase (ccc_flat_priority_queue fpq, void elem, void *tmp)
	Erase element e that is a handle to the stored fpq element.

void *	ccc_fpq_update (ccc_flat_priority_queue fpq, void elem, void tmp, ccc_any_type_update_fn fn, void *aux)
	Update e that is a handle to the stored fpq element. O(lgN).

void *	ccc_fpq_increase (ccc_flat_priority_queue fpq, void elem, void tmp, ccc_any_type_update_fn fn, void *aux)
	Increase e that is a handle to the stored fpq element. O(lgN).

void *	ccc_fpq_decrease (ccc_flat_priority_queue fpq, void elem, void tmp, ccc_any_type_update_fn fn, void *aux)
	Decrease e that is a handle to the stored fpq element. O(lgN).

Container Types
Types available in the container interface.
typedef struct ccc_fpq	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_fpq_heapsort (ccc_flat_priority_queue fpq, void tmp)
	Destroys the fpq 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_fpq_clear (ccc_flat_priority_queue fpq, ccc_any_type_destructor_fn fn)
	Clears the fpq calling fn on every element if provided. O(1)-O(N).

ccc_result	ccc_fpq_clear_and_free (ccc_flat_priority_queue fpq, ccc_any_type_destructor_fn fn)
	Clears the fpq calling fn on every element if provided and frees the underlying buffer. O(1)-O(N).

ccc_result	ccc_fpq_clear_and_free_reserve (ccc_flat_priority_queue fpq, ccc_any_type_destructor_fn destructor, ccc_any_alloc_fn *alloc)
	Frees all slots in the fpq and frees the underlying buffer that was previously dynamically reserved with the reserve function.

State Interface
Obtain state from the container.
void *	ccc_fpq_front (ccc_flat_priority_queue const *fpq)
	Return a pointer to the front (min or max) element in the fpq. O(1).

ccc_tribool	ccc_fpq_is_empty (ccc_flat_priority_queue const *fpq)
	Returns true if the fpq is empty false if not. O(1).

ccc_ucount	ccc_fpq_count (ccc_flat_priority_queue const *fpq)
	Returns the count of the fpq active slots.

ccc_ucount	ccc_fpq_capacity (ccc_flat_priority_queue const *fpq)
	Returns the capacity of the fpq representing total possible slots.

void *	ccc_fpq_data (ccc_flat_priority_queue const *fpq)
	Return a pointer to the base of the backing array. O(1).

ccc_tribool	ccc_fpq_validate (ccc_flat_priority_queue const *fpq)
	Verifies the internal invariants of the fpq hold.

ccc_threeway_cmp	ccc_fpq_order (ccc_flat_priority_queue const *fpq)
	Return the order used to initialize the fpq.

Macro Definition Documentation

◆ ccc_fpq_decrease_w

#define ccc_fpq_decrease_w	(	fpq_ptr,
		any_type_ptr,
		decrease_closure_over_T...
	)	ccc_impl_fpq_decrease_w(fpq_ptr, any_type_ptr, decrease_closure_over_T)

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

Parameters

[in]	fpq_ptr	a pointer to the flat priority queue.
[in]	any_type_ptr	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 fpq on success, NULL if parameters are invalid or fpq is empty.

Warning: the user must ensure any_type_ptr is in the fpq.

#define FLAT_PRIORITY_QUEUE_USING_NAMESPACE_CCC
flat_priority_queue fpq = build_rand_int_fpq();
(void)fpq_decrease_w(&fpq, get_rand_fpq_elem(&fpq), { (*T)--; });

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

◆ ccc_fpq_emplace

#define ccc_fpq_emplace	(	fpq,
		val_initializer...
	)	ccc_impl_fpq_emplace(fpq, val_initializer)

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

Parameters

[in]	fpq	a pointer to the priority queue.
[in]	val_initializer	the compound literal or direct scalar type.

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

◆ ccc_fpq_heapify_init

#define ccc_fpq_heapify_init	(	mem_ptr,
		any_type_name,
		cmp_order,
		cmp_fn,
		alloc_fn,
		aux_data,
		capacity,
		size
	)

Value:

ccc_impl_fpq_heapify_init(mem_ptr, any_type_name, cmp_order, cmp_fn, \

alloc_fn, aux_data, capacity, size)

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

Parameters

[in]	mem_ptr	a pointer to an array of user types or NULL.
[in]	any_type_name	the name of the user type.
[in]	cmp_order	CCC_LES or CCC_GRT for min or max heap, respectively.
[in]	cmp_fn	the user defined comparison function for user types.
[in]	alloc_fn	the allocation function or NULL if no allocation.
[in]	aux_data	any auxiliary data needed for destruction of elements.
[in]	capacity	the capacity of contiguous elements at mem_ptr.
[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_fpq_heapify_init(...);).

◆ ccc_fpq_increase_w

#define ccc_fpq_increase_w	(	fpq_ptr,
		any_type_ptr,
		increase_closure_over_T...
	)	ccc_impl_fpq_increase_w(fpq_ptr, any_type_ptr, increase_closure_over_T)

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

Parameters

[in]	fpq_ptr	a pointer to the flat priority queue.
[in]	any_type_ptr	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 fpq on success, NULL if parameters are invalid or fpq is empty.

Warning: the user must ensure any_type_ptr is in the fpq.

#define FLAT_PRIORITY_QUEUE_USING_NAMESPACE_CCC
flat_priority_queue fpq = build_rand_int_fpq();
(void)fpq_increase_w(&fpq, get_rand_fpq_elem(&fpq), { (*T)++; });

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

◆ ccc_fpq_init

#define ccc_fpq_init	(	mem_ptr,
		any_type_name,
		cmp_order,
		cmp_fn,
		alloc_fn,
		aux_data,
		capacity
	)

Value:

ccc_impl_fpq_init(mem_ptr, any_type_name, cmp_order, cmp_fn, alloc_fn, \

aux_data, capacity)

Initialize a fpq as a min or max heap.

Parameters

[in]	mem_ptr	a pointer to an array of user types or NULL.
[in]	any_type_name	the name of the user type.
[in]	cmp_order	CCC_LES or CCC_GRT for min or max heap, respectively.
[in]	cmp_fn	the user defined comarison function for user types.
[in]	alloc_fn	the allocation function or NULL if no allocation.
[in]	aux_data	any auxiliary data needed for destruction of elements.
[in]	capacity	the capacity of contiguous elements at mem_ptr.

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

◆ ccc_fpq_update_w

#define ccc_fpq_update_w	(	fpq_ptr,
		any_type_ptr,
		update_closure_over_T...
	)	ccc_impl_fpq_update_w(fpq_ptr, any_type_ptr, update_closure_over_T)

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

Parameters

[in]	fpq_ptr	a pointer to the flat priority queue.
[in]	any_type_ptr	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 fpq on success, NULL if parameters are invalid or fpq is empty.

Warning: the user must ensure any_type_ptr is in the fpq.

#define FLAT_PRIORITY_QUEUE_USING_NAMESPACE_CCC
flat_priority_queue fpq = build_rand_int_fpq();
(void)fpq_update_w(&fpq, get_rand_fpq_elem(&fpq), { *T = rand_key(); });

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

Typedef Documentation

◆ ccc_flat_priority_queue

typedef struct ccc_fpq 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_fpq_alloc()

ccc_result ccc_fpq_alloc	(	ccc_flat_priority_queue *	fpq,
		size_t	new_capacity,
		ccc_any_alloc_fn *	fn
	)

Many allocate memory for the fpq.

Parameters

[in]	fpq	a pointer to the priority queue.
[in]	new_capacity	the desired capacity for the fpq.
[in]	fn	the allocation function. May be the same as used on init.

Returns: OK if allocation was successful or a memory error on failure.

◆ ccc_fpq_capacity()

ccc_ucount ccc_fpq_capacity ( ccc_flat_priority_queue const * fpq )

Returns the capacity of the fpq representing total possible slots.

Parameters

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

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

◆ ccc_fpq_clear()

ccc_result ccc_fpq_clear	(	ccc_flat_priority_queue *	fpq,
		ccc_any_type_destructor_fn *	fn
	)

Clears the fpq calling fn on every element if provided. O(1)-O(N).

Parameters

[in]	fpq	a pointer to the flat priority queue.
[in]	fn	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 fpq. 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 fpq.

◆ ccc_fpq_clear_and_free()

ccc_result ccc_fpq_clear_and_free	(	ccc_flat_priority_queue *	fpq,
		ccc_any_type_destructor_fn *	fn
	)

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

Parameters

[in]	fpq	a pointer to the flat priority queue.
[in]	fn	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 alloc error is returned.

Note that because the priority queue is flat there is no need to free elements stored in the fpq. 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_fpq_clear_and_free_reserve()

ccc_result ccc_fpq_clear_and_free_reserve	(	ccc_flat_priority_queue *	fpq,
		ccc_any_type_destructor_fn *	destructor,
		ccc_any_alloc_fn *	alloc
	)

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

Parameters

[in]	fpq	the fpq to be cleared.
[in]	destructor	the destructor for each element. NULL can be passed if no maintenance is required on the elements in the fpq before their slots are dropped.
[in]	alloc	the required allocation function to provide to a dynamically reserved fpq. Any auxiliary 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 fpq that was not reserved with the provided ccc_any_alloc_fn. The fpq must have existing memory to free.

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

However, to free the fpq in such a case this function must be used because the fpq 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 fpq with allocation permission however the normal ccc_fpq_clear_and_free is sufficient for that use case.

◆ ccc_fpq_copy()

ccc_result ccc_fpq_copy	(	ccc_flat_priority_queue *	dst,
		ccc_flat_priority_queue const *	src,
		ccc_any_alloc_fn *	fn
	)

Copy the fpq from src to newly initialized dst.

Parameters

[in]	dst	the destination that will copy the source fpq.
[in]	src	the source of the fpq.
[in]	fn	the allocation function in case resizing of dst 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 dst fails a memory error is returned.

Note: dst must have capacity greater than or equal to src. If dst capacity is less than src, an allocation function must be provided with the fn argument.

Note that there are two ways to copy data from source to destination: provide sufficient memory and pass NULL as fn, 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 src
    = fpq_init((int[10]){}, CCC_LES, NULL, int_cmp, NULL, 10);
push_rand_ints(&src);
flat_priority_queue dst
    = fpq_init((int[11]){}, CCC_LES, NULL, int_cmp, NULL, 11);
ccc_result res = fpq_copy(&dst, &src, NULL);

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

#define FLAT_PRIORITY_QUEUE_USING_NAMESPACE_CCC
flat_priority_queue src
    = fpq_init((int *)NULL, CCC_LES, std_alloc, int_cmp, NULL, 0);
push_rand_ints(&src);
flat_priority_queue dst
    = fpq_init((int *)NULL, CCC_LES, std_alloc, int_cmp, NULL, 0);
ccc_result res = fpq_copy(&dst, &src, std_alloc);

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

#define FLAT_PRIORITY_QUEUE_USING_NAMESPACE_CCC
flat_priority_queue src
    = fpq_init((int *)NULL, CCC_LES, std_alloc, int_cmp, NULL, 0);
push_rand_ints(&src);
flat_priority_queue dst
    = fpq_init((int *)NULL, CCC_LES, NULL, int_cmp, NULL, 0);
ccc_result res = fpq_copy(&dst, &src, std_alloc);

The above sets up dst with fixed size while src is a dynamic fpq. Because an allocation function is provided, the dst 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 dst 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_fpq_count()

ccc_ucount ccc_fpq_count ( ccc_flat_priority_queue const * fpq )

Returns the count of the fpq active slots.

Parameters

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

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

◆ ccc_fpq_data()

void * ccc_fpq_data ( ccc_flat_priority_queue const * fpq )

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

Parameters

[in] fpq a pointer to the priority queue.

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

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

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

◆ ccc_fpq_decrease()

void * ccc_fpq_decrease	(	ccc_flat_priority_queue *	fpq,
		void *	elem,
		void *	tmp,
		ccc_any_type_update_fn *	fn,
		void *	aux
	)

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

Parameters

[in]	fpq	a pointer to the flat priority queue.
[in]	elem	a pointer to the stored fpq element. Must be in the fpq.
[in]	tmp	a pointer to a dummy user type that will be used for swapping.
[in]	fn	the update function to act on e.
[in]	aux	any auxiliary data needed for the update function.

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

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

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

ccc_result ccc_fpq_erase	(	ccc_flat_priority_queue *	fpq,
		void *	elem,
		void *	tmp
	)

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

Parameters

[in]	fpq	a pointer to the priority queue.
[in]	elem	a pointer to the stored fpq element. Must be in the fpq.
[in]	tmp	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 fpq is empty.

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

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 elem is invalidated after this call.

◆ ccc_fpq_front()

void * ccc_fpq_front ( ccc_flat_priority_queue const * fpq )

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

Parameters

[in] fpq a pointer to the priority queue.

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

◆ ccc_fpq_heapify()

ccc_result ccc_fpq_heapify	(	ccc_flat_priority_queue *	fpq,
		void *	tmp,
		void *	input_array,
		size_t	input_n,
		size_t	input_sizeof_type
	)

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

Parameters

[in]	fpq	a pointer to the priority queue.
[in]	tmp	a pointer to an additional element of array type for swapping.
[in]	input_array	an array of elements of the same size as the type used to initialize fpq.
[in]	input_n	the number of contiguous elements at input_array.
[in]	input_sizeof_type	size of each element in input_array matching element size of fpq.

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 fpq 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_fpq_heapify_inplace()

ccc_result ccc_fpq_heapify_inplace	(	ccc_flat_priority_queue *	fpq,
		void *	tmp,
		size_t	n
	)

Order n elements of the underlying fpq buffer as an fpq.

Parameters

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

Returns: the result of the heapify operation, ok if successful or an error if fpq is NULL or n is larger than the initialized capacity of the fpq.

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 n valid elements starting at index 0 to index n - 1.

◆ ccc_fpq_heapsort()

ccc_buffer ccc_fpq_heapsort	(	ccc_flat_priority_queue *	fpq,
		void *	tmp
	)

Destroys the fpq 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]	fpq	the fpq to be sorted and destroyed.
[in]	tmp	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 fpq order. If the fpq is initialized CCC_LES the returned buffer is sorted in non-increasing order from index [0, N). If the fpq is initialized CCC_GRT the buffer is sorted in non-descending order from index [0, N). If fpq is NULL, the buffer is default initialized and unusable.

Warning: all fields of the fpq are cleared or otherwise default initialized so the fpq is unusable as a container after sorting. This function assumes the fpq has been previously initialized. Therefore, if the returned buffer value is not used the fpq 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 fpq, 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 fpq with the ccc_fpq_copy function first then sort that copy.

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

◆ ccc_fpq_increase()

void * ccc_fpq_increase	(	ccc_flat_priority_queue *	fpq,
		void *	elem,
		void *	tmp,
		ccc_any_type_update_fn *	fn,
		void *	aux
	)

Increase e that is a handle to the stored fpq element. O(lgN).

Parameters

[in]	fpq	a pointer to the flat priority queue.
[in]	elem	a pointer to the stored fpq element. Must be in the fpq.
[in]	tmp	a pointer to a dummy user type that will be used for swapping.
[in]	fn	the update function to act on e.
[in]	aux	any auxiliary data needed for the update function.

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

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

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

ccc_tribool ccc_fpq_is_empty ( ccc_flat_priority_queue const * fpq )

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

Parameters

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

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

◆ ccc_fpq_order()

ccc_threeway_cmp ccc_fpq_order ( ccc_flat_priority_queue const * fpq )

Return the order used to initialize the fpq.

Parameters

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

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

◆ ccc_fpq_pop()

ccc_result ccc_fpq_pop	(	ccc_flat_priority_queue *	fpq,
		void *	tmp
	)

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

Parameters

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

Returns: OK if the pop succeeds or an input error if fpq 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_fpq_push()

void * ccc_fpq_push	(	ccc_flat_priority_queue *	fpq,
		void const *	elem,
		void *	tmp
	)

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

Parameters

[in]	fpq	a pointer to the priority queue.
[in]	elem	a pointer to the user element of same type as in fpq.
[in]	tmp	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 fpq 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_fpq_reserve()

ccc_result ccc_fpq_reserve	(	ccc_flat_priority_queue *	fpq,
		size_t	to_add,
		ccc_any_alloc_fn *	fn
	)

Reserves space for at least to_add more elements.

Parameters

[in]	fpq	a pointer to the flat priority queue.
[in]	to_add	the number of elements to add to the current size.
[in]	fn	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_fpq_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 fpq with or without allocation permission. If the fpq has allocation permission, it will reserve the required space and later resize if more space is needed.

If the fpq 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 fpq in such a case see the ccc_fpq_clear_and_free_reserve function.

◆ ccc_fpq_update()

void * ccc_fpq_update	(	ccc_flat_priority_queue *	fpq,
		void *	elem,
		void *	tmp,
		ccc_any_type_update_fn *	fn,
		void *	aux
	)

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

Parameters

[in]	fpq	a pointer to the flat priority queue.
[in]	elem	a pointer to the stored fpq element. Must be in the fpq.
[in]	tmp	a pointer to a dummy user type that will be used for swapping.
[in]	fn	the update function to act on e.
[in]	aux	any auxiliary data needed for the update function.

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

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

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

ccc_tribool ccc_fpq_validate ( ccc_flat_priority_queue const * fpq )

Verifies the internal invariants of the fpq hold.

Parameters

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

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

Detailed Description

Initialization Interface

Insert and Remove Interface

Container Types

Deallocation Interface

State Interface

Macro Definition Documentation

◆ ccc_fpq_decrease_w

◆ ccc_fpq_emplace

◆ ccc_fpq_heapify_init

◆ ccc_fpq_increase_w

◆ ccc_fpq_init

◆ ccc_fpq_update_w

Typedef Documentation

◆ ccc_flat_priority_queue

Function Documentation

◆ ccc_fpq_alloc()

◆ ccc_fpq_capacity()

◆ ccc_fpq_clear()

◆ ccc_fpq_clear_and_free()

◆ ccc_fpq_clear_and_free_reserve()

◆ ccc_fpq_copy()

◆ ccc_fpq_count()

◆ ccc_fpq_data()

◆ ccc_fpq_decrease()

◆ ccc_fpq_erase()

◆ ccc_fpq_front()

◆ ccc_fpq_heapify()

◆ ccc_fpq_heapify_inplace()

◆ ccc_fpq_heapsort()

◆ ccc_fpq_increase()

◆ ccc_fpq_is_empty()

◆ ccc_fpq_order()

◆ ccc_fpq_pop()

◆ ccc_fpq_push()

◆ ccc_fpq_reserve()

◆ ccc_fpq_update()

◆ ccc_fpq_validate()