The Priority Queue Interface. More...

#include "impl/impl_priority_queue.h"
#include "types.h"

Include dependency graph for 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_pq_init(struct_name, pq_elem_field, pq_order, alloc_fn, cmp_fn, aux_data)
	Initialize a priority queue at runtime or compile time.

Insert and Remove Interface
Insert and remove elements from the priority queue.
#define	ccc_pq_emplace(priority_queue_ptr, lazy_value...) ccc_impl_pq_emplace(priority_queue_ptr, lazy_value)
	Write user type directly to a newly allocated priority queue elem.

#define	ccc_pq_update_w(pq_ptr, pq_elem_ptr, update_closure_over_T...) ccc_impl_pq_update_w(pq_ptr, pq_elem_ptr, update_closure_over_T)
	Update the priority in the user type stored in the container.

#define	ccc_pq_increase_w(pq_ptr, pq_elem_ptr, increase_closure_over_T...) ccc_impl_pq_increase_w(pq_ptr, pq_elem_ptr, increase_closure_over_T)
	Increases the priority of the user type stored in the container.

#define	ccc_pq_decrease_w(pq_ptr, pq_elem_ptr, decrease_closure_over_T...) ccc_impl_pq_decrease_w(pq_ptr, pq_elem_ptr, decrease_closure_over_T)
	Decreases the priority of the user type stored in the container.

void *	ccc_pq_push (ccc_priority_queue pq, ccc_pq_elem elem)
	Adds an element to the priority queue in correct total order. O(1).

ccc_result	ccc_pq_pop (ccc_priority_queue *pq)
	Pops the front element from the priority queue. Amortized O(lgN).

void *	ccc_pq_extract (ccc_priority_queue pq, ccc_pq_elem elem)

ccc_result	ccc_pq_erase (ccc_priority_queue pq, ccc_pq_elem elem)
	Erase elem from the pq. Amortized O(lgN).

bool	ccc_pq_update (ccc_priority_queue pq, ccc_pq_elem elem, ccc_update_fn fn, void aux)
	Update the priority in the user type wrapping elem.

bool	ccc_pq_increase (ccc_priority_queue pq, ccc_pq_elem elem, ccc_update_fn fn, void aux)
	Increases the priority of the type wrapping elem. O(1) or O(lgN)

bool	ccc_pq_decrease (ccc_priority_queue pq, ccc_pq_elem elem, ccc_update_fn fn, void aux)
	Decreases the value of the type wrapping elem. O(1) or O(lgN)

Container Types
Types available in the container interface.
typedef struct ccc_pq_	ccc_priority_queue
	A container for pointer stability and an O(1) push and amortized o(lg N) increase/decrease key.

typedef struct ccc_pq_elem_	ccc_pq_elem
	The embedded struct type for operation of the priority queue.

Deallocation Interface
Deallocate the container.
ccc_result	ccc_pq_clear (ccc_priority_queue pq, ccc_destructor_fn fn)
	Removes all elements from the pq, freeing if needed.

State Interface
Obtain state from the container.
void *	ccc_pq_front (ccc_priority_queue const *pq)
	Obtain a reference to the front of the priority queue. O(1).

bool	ccc_pq_is_empty (ccc_priority_queue const *pq)
	Returns true if the priority queue is empty false if not. O(1).

size_t	ccc_pq_size (ccc_priority_queue const *pq)
	Returns the size of the priority queue.

bool	ccc_pq_validate (ccc_priority_queue const *pq)
	Verifies the internal invariants of the pq hold.

ccc_threeway_cmp	ccc_pq_order (ccc_priority_queue const *pq)
	Return the order used to initialize the pq.

Detailed Description

The Priority Queue Interface.

A priority queue offers simple, fast, pointer stable management of a priority queue. Push is O(1). The cost to execute the increase key in a max heap and decrease key in a min heap is O(1). However, due to the restructuring this causes that increases the cost of later pops, the more accurate runtime is o(lg N). The cost of a pop operation is O(lg N).

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

#define PRIORITY_QUEUE_USING_NAMESPACE_CCC

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

Macro Definition Documentation

◆ ccc_pq_decrease_w

#define ccc_pq_decrease_w	(	pq_ptr,
		pq_elem_ptr,
		decrease_closure_over_T...
	)	ccc_impl_pq_decrease_w(pq_ptr, pq_elem_ptr, decrease_closure_over_T)

Decreases the priority of the user type stored in the container.

Parameters

[in]	pq_ptr	a pointer to the priority queue.
[in]	pq_elem_ptr	a pointer to the intrusive handle in the user type.
[in]	decrease_closure_over_T	the semicolon separated statements to execute on the user type which wraps pq_elem_ptr (optionally wrapping {code here} in braces may help with formatting). This closure may safely decrease the key used to track the user element's priority in the priority queue.

Returns: true if the decrease occurred false if parameters were invalid or the function can deduce elem is not in the pq.

Warning: the user must ensure elem is in the pq and pq_elem_ptr points to the intrusive element in the same user type that is being decreased. The data structure will be in an invalid state if the user decreases the priority by mistake in this function.

#define PRIORITY_QUEUE_USING_NAMESPACE_CCC
struct val
{
    pq_elem e;
    int key;
};
priority_queue pq = build_rand_pq();
struct val *i = get_rand_pq_elem(&pq);
pq_decrease_w(&pq, &i->e, { i->key--; });

Note that this is optimal update technique if the priority queue has been initialized as a min queue and the new value is known to be less than the old value. If this is a min heap O(1), otherwise O(lgN).

While the best case operation is O(1) the impact of restructuring on future pops from the pq creates an amortized o(lgN) runtime for this function.

◆ ccc_pq_emplace

#define ccc_pq_emplace	(	priority_queue_ptr,
		lazy_value...
	)	ccc_impl_pq_emplace(priority_queue_ptr, lazy_value)

Write user type directly to a newly allocated priority queue elem.

Parameters

[in]	priority_queue_ptr	a pointer to the priority queue.
[in]	lazy_value	the compound literal to write to the allocation.

Returns: a reference to the successfully inserted element or NULL if allocation fails or is not allowed.

Note that the priority queue must be initialized with allocation permission to use this macro.

◆ ccc_pq_increase_w

#define ccc_pq_increase_w	(	pq_ptr,
		pq_elem_ptr,
		increase_closure_over_T...
	)	ccc_impl_pq_increase_w(pq_ptr, pq_elem_ptr, increase_closure_over_T)

Increases the priority of the user type stored in the container.

Parameters

[in]	pq_ptr	a pointer to the priority queue.
[in]	pq_elem_ptr	a pointer to the intrusive handle in the user type.
[in]	increase_closure_over_T	the semicolon separated statements to execute on the user type which wraps pq_elem_ptr (optionally wrapping {code here} in braces may help with formatting). This closure may safely increase the key used to track the user element's priority in the priority queue.

Returns: true if the increase occurred false if parameters were invalid or the function can deduce elem is not in the pq.

Warning: the user must ensure elem is in the pq and pq_elem_ptr points to the intrusive element in the same user type that is being increased. The data structure will be in an invalid state if the user decreases the priority by mistake in this function.

#define PRIORITY_QUEUE_USING_NAMESPACE_CCC
struct val
{
    pq_elem e;
    int key;
};
priority_queue pq = build_rand_pq();
struct val *i = get_rand_pq_elem(&pq);
pq_increase_w(&pq, &i->e, { i->key++; });

Note that this is optimal update technique if the priority queue has been initialized as a max queue and the new value is known to be greater than the old value. If this is a max heap O(1), otherwise O(lgN).

While the best case operation is O(1) the impact of restructuring on future pops from the pq creates an amortized o(lgN) runtime for this function.

◆ ccc_pq_init

#define ccc_pq_init	(	struct_name,
		pq_elem_field,
		pq_order,
		alloc_fn,
		cmp_fn,
		aux_data
	)

Value:

ccc_impl_pq_init(struct_name, pq_elem_field, pq_order, alloc_fn, cmp_fn, \

aux_data)

Initialize a priority queue at runtime or compile time.

Parameters

[in]	struct_name	the name of the user type wrapping pq elems.
[in]	pq_elem_field	the name of the field for the pq elem.
[in]	pq_order	CCC_LES for a min pq or CCC_GRT for a max pq.
[in]	alloc_fn	the allocation function or NULL if allocation is banned.
[in]	cmp_fn	the function used to compare two user types.
[in]	aux_data	auxiliary data needed for comparison or destruction.

Returns: the initialized pq on the right side of an equality operator (e.g. ccc_priority_queue pq = ccc_pq_init(...);)

◆ ccc_pq_update_w

#define ccc_pq_update_w	(	pq_ptr,
		pq_elem_ptr,
		update_closure_over_T...
	)	ccc_impl_pq_update_w(pq_ptr, pq_elem_ptr, update_closure_over_T)

Update the priority in the user type stored in the container.

Parameters

[in]	pq_ptr	a pointer to the priority queue.
[in]	pq_elem_ptr	a pointer to the intrusive handle in the user type.
[in]	update_closure_over_T	the semicolon separated statements to execute on the user type which wraps pq_elem_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: true if the update occurred false if parameters were invalid or the function can deduce elem is not in the pq.

Warning: the user must ensure elem is in the pq and pq_elem_ptr points to the intrusive element in the same user type that is being updated.

#define PRIORITY_QUEUE_USING_NAMESPACE_CCC
struct val
{
    pq_elem e;
    int key;
};
priority_queue pq = build_rand_pq();
struct val *i = get_rand_pq_elem(&pq);
pq_update_w(&pq, &i->e, { i->key = rand_key(); });

Note that this operation may incur unnecessary overhead if the user can't deduce if an increase or decrease is occurring. See the increase and decrease operations. O(1) best case, O(lgN) worst case.

Typedef Documentation

◆ ccc_pq_elem

typedef struct ccc_pq_elem_ ccc_pq_elem

The embedded struct type for operation of the priority queue.

It can be used in an allocating or non allocating container. If allocation is prohibited the container assumes the element is wrapped in pre-allocated memory with the appropriate lifetime and scope for the user's needs; the container does not allocate or free in this case. If allocation is allowed the container will handle copying the data wrapping the element to allocations and deallocating when necessary.

◆ ccc_priority_queue

typedef struct ccc_pq_ ccc_priority_queue

A container for pointer stability and an O(1) push and amortized o(lg N) increase/decrease key.

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

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

Function Documentation

◆ ccc_pq_clear()

ccc_result ccc_pq_clear	(	ccc_priority_queue *	pq,
		ccc_destructor_fn *	fn
	)

Removes all elements from the pq, freeing if needed.

Parameters

[in]	pq	a pointer to the priority queue.
[in]	fn	the destructor function or NULL if not needed.

Returns: ok if the clear was successful or an input error for NULL args.

Note that if allocation is allowed the container will free the user type wrapping each element in the pq. Therefore, the user should not free in the destructor function. Only perform auxiliary cleanup operations if needed.

If allocation is not allowed, the user may free their stored types in the destructor function if they wish to do so. The container simply removes all the elements from the pq, calling fn on each user type if provided, and sets the size to zero.

◆ ccc_pq_decrease()

bool ccc_pq_decrease	(	ccc_priority_queue *	pq,
		ccc_pq_elem *	elem,
		ccc_update_fn *	fn,
		void *	aux
	)

Decreases the value of the type wrapping elem. O(1) or O(lgN)

Parameters

[in]	pq	a pointer to the priority queue.
[in]	elem	a pointer to the intrusive element in the user type.
[in]	fn	the update function to act on the type wrapping elem.
[in]	aux	any auxiliary data needed for the update function.

Returns: true if the decrease occurred false if parameters were invalid or the function can deduce elem is not in the pq.

Note that this is optimal update technique if the priority queue has been initialized as a min queue and the new value is known to be less than the old value. If this is a min heap O(1), otherwise O(lgN).

While the best case operation is O(1) the impact of restructuring on future pops from the pq creates an amortized o(lgN) runtime for this function.

◆ ccc_pq_erase()

ccc_result ccc_pq_erase	(	ccc_priority_queue *	pq,
		ccc_pq_elem *	elem
	)

Erase elem from the pq. Amortized O(lgN).

Parameters

[in]	pq	a pointer to the priority queue.
[in]	elem	a pointer to the intrusive element in the user type.

Returns: ok if erase was successful or an input error if pq or elem is NULL or pq is empty.

Note that the user must ensure that elem is in the priority queue.

◆ ccc_pq_extract()

void * ccc_pq_extract	(	ccc_priority_queue *	pq,
		ccc_pq_elem *	elem
	)

Extract the element known to be in the pq without freeing memory. Amortized O(lgN).

Parameters

[in]	pq	a pointer to the priority queue.
[in]	elem	a pointer to the intrusive element in the user type.

Returns: a pointer to the extracted user type.

Note that the user must ensure that elem is in the priority queue.

◆ ccc_pq_front()

void * ccc_pq_front ( ccc_priority_queue const * pq )

Obtain a reference to the front of the priority queue. O(1).

Parameters

[in] pq a pointer to the priority queue.

Returns: a reference to the front element in the pq.

◆ ccc_pq_increase()

bool ccc_pq_increase	(	ccc_priority_queue *	pq,
		ccc_pq_elem *	elem,
		ccc_update_fn *	fn,
		void *	aux
	)

Increases the priority of the type wrapping elem. O(1) or O(lgN)

Parameters

[in]	pq	a pointer to the priority queue.
[in]	elem	a pointer to the intrusive element in the user type.
[in]	fn	the update function to act on the type wrapping elem.
[in]	aux	any auxiliary data needed for the update function.

Returns: true if the increase occurred false if parameters were invalid or the function can deduce elem is not in the pq.

Warning: the data structure will be in an invalid state if the user decreases the priority by mistake in this function.

Note that this is optimal update technique if the priority queue has been initialized as a max queue and the new value is known to be greater than the old value. If this is a max heap O(1), otherwise O(lgN).

While the best case operation is O(1) the impact of restructuring on future pops from the pq creates an amortized o(lgN) runtime for this function.

◆ ccc_pq_is_empty()

bool ccc_pq_is_empty ( ccc_priority_queue const * pq )

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

Parameters

[in] pq a pointer to the priority queue.

Returns: true if the size is 0 or pq is NULL, false if not empty.

◆ ccc_pq_order()

ccc_threeway_cmp ccc_pq_order ( ccc_priority_queue const * pq )

Return the order used to initialize the pq.

Parameters

[in] pq a pointer to the priority queue.

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

◆ ccc_pq_pop()

ccc_result ccc_pq_pop ( ccc_priority_queue * pq )

Pops the front element from the priority queue. Amortized O(lgN).

Parameters

[in] pq a pointer to the priority queue.

Returns: ok if pop was successful or an input error if pq is NULL or empty.

◆ ccc_pq_push()

void * ccc_pq_push	(	ccc_priority_queue *	pq,
		ccc_pq_elem *	elem
	)

Adds an element to the priority queue in correct total order. O(1).

Parameters

[in]	pq	a pointer to the priority queue.
[in]	elem	a pointer to the intrusive element in the user type.

Returns: a reference to the newly inserted user type or NULL if NULL arguments are provided or allocation fails when permitted.

Note that if allocation is permitted the user type is copied into a newly allocated node.

If allocation is not permitted this function assumes the memory wrapping elem has been allocated with the appropriate lifetime for the user's needs.

◆ ccc_pq_size()

size_t ccc_pq_size ( ccc_priority_queue const * pq )

Returns the size of the priority queue.

Parameters

[in] pq a pointer to the priority queue.

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

◆ ccc_pq_update()

bool ccc_pq_update	(	ccc_priority_queue *	pq,
		ccc_pq_elem *	elem,
		ccc_update_fn *	fn,
		void *	aux
	)

Update the priority in the user type wrapping elem.

Parameters

[in]	pq	a pointer to the priority queue.
[in]	elem	a pointer to the intrusive element in the user type.
[in]	fn	the update function to act on the type wrapping elem.
[in]	aux	any auxiliary data needed for the update function.

Returns: true if the update occurred false if parameters were invalid or the function can deduce elem is not in the pq.

Warning: the user must ensure elem is in the pq.

Note that this operation may incur unnecessary overhead if the user can't deduce if an increase or decrease is occurring. See the increase and decrease operations. O(1) best case, O(lgN) worst case.

◆ ccc_pq_validate()

bool ccc_pq_validate ( ccc_priority_queue const * pq )

Verifies the internal invariants of the pq hold.

Parameters

[in] pq a pointer to the priority queue.

Returns: true if the pq is valid false if pq is NULL or invalid.

Initialization Interface

Insert and Remove Interface

Container Types

Deallocation Interface

State Interface

Detailed Description

Macro Definition Documentation

◆ ccc_pq_decrease_w

◆ ccc_pq_emplace

◆ ccc_pq_increase_w

◆ ccc_pq_init

◆ ccc_pq_update_w

Typedef Documentation

◆ ccc_pq_elem

◆ ccc_priority_queue

Function Documentation

◆ ccc_pq_clear()

◆ ccc_pq_decrease()

◆ ccc_pq_erase()

◆ ccc_pq_extract()

◆ ccc_pq_front()

◆ ccc_pq_increase()

◆ ccc_pq_is_empty()

◆ ccc_pq_order()

◆ ccc_pq_pop()

◆ ccc_pq_push()

◆ ccc_pq_size()

◆ ccc_pq_update()

◆ ccc_pq_validate()