The Flat Priority Queue Interface. More...

#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:

Initialization Interface
Initialize the container with memory, callbacks, and permissions.
#define	ccc_fpq_init(mem_ptr, capacity, cmp_order, alloc_fn, cmp_fn, aux_data) ccc_impl_fpq_init(mem_ptr, capacity, cmp_order, alloc_fn, cmp_fn, aux_data)
	Initialize a fpq as a min or max heap.

#define	ccc_fpq_heapify_init(mem_ptr, capacity, size, cmp_order, alloc_fn, cmp_fn, aux_data)
	Order an existing 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_alloc_fn *fn)
	Copy the fpq from src to newly initialized dst.

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, T_ptr, update_closure_over_T...) ccc_impl_fpq_update_w(fpq_ptr, T_ptr, update_closure_over_T)
	Update the user type stored in the priority queue directly. O(lgN).

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

#define	ccc_fpq_decrease_w(fpq_ptr, T_ptr, decrease_closure_over_T...) ccc_impl_fpq_decrease_w(fpq_ptr, T_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 input_array, size_t input_n, size_t input_elem_size)
	Copy input array into the fpq, organizing into heap. O(N).

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

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

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

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

void *	ccc_fpq_update (ccc_flat_priority_queue fpq, void e, ccc_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 e, ccc_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 e, ccc_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.
ccc_result	ccc_fpq_clear (ccc_flat_priority_queue fpq, ccc_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_destructor_fn fn)
	Clears the fpq calling fn on every element if provided and frees the underlying buffer. O(1)-O(N).

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

ptrdiff_t	ccc_fpq_i (ccc_flat_priority_queue const fpq, void const e)
	Return the index of an element known to be in the fpq. O(1).

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

size_t	ccc_fpq_size (ccc_flat_priority_queue const *fpq)
	Returns the size of the fpq.

size_t	ccc_fpq_capacity (ccc_flat_priority_queue const *fpq)
	Returns the capacity of the fpq.

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

bool	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.

Detailed Description

The Flat Priority Queue Interface.

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

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.

Macro Definition Documentation

◆ ccc_fpq_decrease_w

#define ccc_fpq_decrease_w	(	fpq_ptr,
		T_ptr,
		decrease_closure_over_T...
	)	ccc_impl_fpq_decrease_w(fpq_ptr, T_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]	T_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_ptr (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 T_ptr is in the fpq.

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

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,
		capacity,
		size,
		cmp_order,
		alloc_fn,
		cmp_fn,
		aux_data
	)

Value:

ccc_impl_fpq_heapify_init(mem_ptr, capacity, size, cmp_order, alloc_fn, \

cmp_fn, aux_data)

Order an existing array of elements as a min or max heap. O(N).

Parameters

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

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

Note that to avoid temporary or unpredictable allocation the fpq requires one slot for swapping. Therefore if the user wants a fixed size fpq of size N, N + 1 capacity is required.

◆ ccc_fpq_increase_w

#define ccc_fpq_increase_w	(	fpq_ptr,
		T_ptr,
		increase_closure_over_T...
	)	ccc_impl_fpq_increase_w(fpq_ptr, T_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]	T_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_ptr (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 T_ptr is in the fpq.

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

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

◆ ccc_fpq_init

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

Initialize a fpq as a min or max heap.

Parameters

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

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

Note that to avoid temporary or unpredictable allocation the fpq requires one slot for swapping. Therefore if the user wants a fixed size fpq of size N, N + 1 capacity is required.

◆ ccc_fpq_update_w

#define ccc_fpq_update_w	(	fpq_ptr,
		T_ptr,
		update_closure_over_T...
	)	ccc_impl_fpq_update_w(fpq_ptr, T_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]	T_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_ptr (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 T_ptr is in the fpq.

#define FLAT_PRIORITY_QUEUE_USING_NAMESPACE_CCC
flat_priority_queue fpq = build_rand_int_fpq();
int *i = get_rand_fpq_elem(&fpq);
(void)fpq_update_w(&fpq, i, { *i = 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_alloc_fn *	fn
	)

Many allocate memory for the fpq.

Parameters

[in]	fpq	a pointer to the priority queue.
[in]	new_capacity	the desirect 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()

size_t ccc_fpq_capacity ( ccc_flat_priority_queue const * fpq )

Returns the capacity of the fpq.

Parameters

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

Returns: the capacity of the fpq or 0 if fpq is NULL or fpq is empty.

◆ ccc_fpq_clear()

ccc_result ccc_fpq_clear	(	ccc_flat_priority_queue *	fpq,
		ccc_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_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_copy()

ccc_result ccc_fpq_copy	(	ccc_flat_priority_queue *	dst,
		ccc_flat_priority_queue const *	src,
		ccc_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]){}, 10, CCC_LES, NULL, int_cmp, NULL);
push_rand_ints(&src);
flat_priority_queue dst
    = fpq_init((int[11]){}, 11, CCC_LES, NULL, int_cmp, NULL);
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, 0, CCC_LES, std_alloc, int_cmp, NULL);
push_rand_ints(&src);
flat_priority_queue dst
    = fpq_init((int *)NULL, 0, CCC_LES, std_alloc, int_cmp, NULL);
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, 0, CCC_LES, std_alloc, int_cmp, NULL);
push_rand_ints(&src);
flat_priority_queue dst
    = fpq_init((int *)NULL, 0, CCC_LES, NULL, int_cmp, NULL);
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_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 *	e,
		ccc_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]	e	a handle to the stored fpq element. Must be in the fpq.
[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.

◆ ccc_fpq_erase()

ccc_result ccc_fpq_erase	(	ccc_flat_priority_queue *	fpq,
		void *	e
	)

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

Parameters

[in]	fpq	a pointer to the priority queue.
[in]	e	a handle to the stored fpq element. Must be in the fpq.

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.

Note that the reference to e 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 *	input_array,
		size_t	input_n,
		size_t	input_elem_size
	)

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

Parameters

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

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

ptrdiff_t ccc_fpq_i	(	ccc_flat_priority_queue const *	fpq,
		void const *	e
	)

Return the index of an element known to be in the fpq. O(1).

Parameters

[in]	fpq	a pointer to the priority queue.
[in]	e	an element known to be in the fpq.

Returns: the index of the element known to be in the fpq or -1 if e is out of range of the fpq.

◆ ccc_fpq_increase()

void * ccc_fpq_increase	(	ccc_flat_priority_queue *	fpq,
		void *	e,
		ccc_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]	e	a handle to the stored fpq element. Must be in the fpq.
[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.

◆ ccc_fpq_is_empty()

bool 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 or fpq is NULL, false if not empty.

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

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

Parameters

[in] fpq a pointer to the priority queue.

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

◆ ccc_fpq_push()

void * ccc_fpq_push	(	ccc_flat_priority_queue *	fpq,
		void const *	e
	)

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

Parameters

[in]	fpq	a pointer to the priority queue.
[in]	e	a pointer to the user element of same type as in fpq.

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.

◆ ccc_fpq_size()

size_t ccc_fpq_size ( ccc_flat_priority_queue const * fpq )

Returns the size of the fpq.

Parameters

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

Returns: the size of the fpq or 0 if fpq is NULL or fpq is empty.

◆ ccc_fpq_update()

void * ccc_fpq_update	(	ccc_flat_priority_queue *	fpq,
		void *	e,
		ccc_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]	e	a handle to the stored fpq element. Must be in the fpq.
[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.

◆ ccc_fpq_validate()

bool 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 fpq is NULL or invalid.

Initialization Interface

Insert and Remove Interface

Container Types

Deallocation Interface

State Interface

Detailed Description

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

◆ ccc_fpq_data()

◆ ccc_fpq_decrease()

◆ ccc_fpq_erase()

◆ ccc_fpq_front()

◆ ccc_fpq_heapify()

◆ ccc_fpq_i()

◆ ccc_fpq_increase()

◆ ccc_fpq_is_empty()

◆ ccc_fpq_order()

◆ ccc_fpq_pop()

◆ ccc_fpq_push()

◆ ccc_fpq_size()

◆ ccc_fpq_update()

◆ ccc_fpq_validate()