The Priority Queue Interface. More...

#include "private/private_priority_queue.h"
#include "types.h"

Include dependency graph for priority_queue.h:

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

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(log(N)). The cost of a pop operation is O(log(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.

Initialization Interface
Initialize the container with memory, callbacks, and permissions.
#define	CCC_priority_queue_initialize(struct_name, type_intruder_field, order, compare, allocate, context_data)
	Initialize a priority queue at runtime or compile time.

#define	CCC_priority_queue_from(type_intruder_field, order, compare, allocate, destroy, context_data, compound_literal_array...)
	Initialize a priority queue at runtime from a compound literal array.

Insert and Remove Interface
Insert and remove elements from the priority queue.
#define	CCC_priority_queue_emplace(Priority_queue_pointer, type_compound_literal...)
	Write user type_intruder directly to a newly allocated priority queue elem.

#define	CCC_priority_queue_update_with(priority_queue_pointer, type_pointer, update_closure_over_T...)
	Update the priority in the user type_intruder stored in the container.

#define	CCC_priority_queue_increase_with(priority_queue_pointer, type_pointer, increase_closure_over_T...)
	Increases the priority of the user type_intruder stored in the container.

#define	CCC_priority_queue_decrease_with(priority_queue_pointer, type_pointer, decrease_closure_over_T...)
	Decreases the priority of the user type_intruder stored in the container.

void *	CCC_priority_queue_push (CCC_Priority_queue priority_queue, CCC_Priority_queue_node type_intruder)
	Adds an element to the priority queue in correct total order. O(1).

CCC_Result	CCC_priority_queue_pop (CCC_Priority_queue *priority_queue)
	Pops the front element from the priority queue. Amortized O(lgN).

void *	CCC_priority_queue_extract (CCC_Priority_queue priority_queue, CCC_Priority_queue_node type_intruder)

CCC_Result	CCC_priority_queue_erase (CCC_Priority_queue priority_queue, CCC_Priority_queue_node type_intruder)
	Erase type_intruder from the priority_queue. Amortized O(lgN).

void *	CCC_priority_queue_update (CCC_Priority_queue priority_queue, CCC_Priority_queue_node type_intruder, CCC_Type_modifier modify, void context)
	Update the priority in the user type_intruder wrapping elem.

void *	CCC_priority_queue_increase (CCC_Priority_queue priority_queue, CCC_Priority_queue_node type_intruder, CCC_Type_modifier modify, void context)
	Increases the priority of the type_intruder wrapping elem. O(1) or O(lgN)

void *	CCC_priority_queue_decrease (CCC_Priority_queue priority_queue, CCC_Priority_queue_node type_intruder, CCC_Type_modifier modify, void context)
	Decreases the value of the type_intruder wrapping elem. O(1) or O(lgN)

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

typedef struct CCC_Priority_queue_node	CCC_Priority_queue_node
	The embedded struct type_intruder for operation of the priority queue.

Deallocation Interface
Deallocate the container.
CCC_Result	CCC_priority_queue_clear (CCC_Priority_queue priority_queue, CCC_Type_destructor destroy)
	Removes all elements from the priority_queue, freeing if needed.

State Interface
Obtain state from the container.
void *	CCC_priority_queue_front (CCC_Priority_queue const *priority_queue)
	Obtain a reference to the front of the priority queue. O(1).

CCC_Tribool	CCC_priority_queue_is_empty (CCC_Priority_queue const *priority_queue)
	Returns true if the priority queue is empty false if not. O(1).

CCC_Count	CCC_priority_queue_count (CCC_Priority_queue const *priority_queue)
	Returns the count of priority queue occupied nodes.

CCC_Tribool	CCC_priority_queue_validate (CCC_Priority_queue const *priority_queue)
	Verifies the internal invariants of the priority_queue hold.

CCC_Order	CCC_priority_queue_order (CCC_Priority_queue const *priority_queue)
	Return the order used to initialize the priority_queue.

Macro Definition Documentation

◆ CCC_priority_queue_decrease_with

#define CCC_priority_queue_decrease_with	(	priority_queue_pointer,
		type_pointer,
		decrease_closure_over_T...
	)

Value:

CCC_private_priority_queue_decrease_with( \

priority_queue_pointer, type_pointer, decrease_closure_over_T)

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

Parameters

[in]	priority_queue_pointer	a pointer to the priority queue.
[in]	type_pointer	a pointer to the user struct type_intruder in the priority_queue.
[in]	decrease_closure_over_T	a pointer to the user struct type_intruder T is made available. Use a semicolon separated statements to execute on the user type which wraps priority_queue_node_pointer (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 updated user type_intruder or NULL if update failed due to bad arguments provided.

Warning: the user must ensure the type_pointer is a reference to an instance of the type_intruder actively stored in the priority queue. 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
{
    priority_queue_node e;
    int key;
};
Priority_queue priority_queue = build_rand_priority_queue();
priority_queue_decrease_with(&priority_queue,
get_rand_priority_queue_node(&priority_queue), { T->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 priority_queue creates an amortized o(lgN) runtime for this function.

◆ CCC_priority_queue_emplace

#define CCC_priority_queue_emplace	(	Priority_queue_pointer,
		type_compound_literal...
	)

Value:

CCC_private_priority_queue_emplace(Priority_queue_pointer, \

type_compound_literal)

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

Parameters

[in]	Priority_queue_pointer	a pointer to the priority queue.
[in]	type_compound_literal	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_priority_queue_from

#define CCC_priority_queue_from	(	type_intruder_field,
		order,
		compare,
		allocate,
		destroy,
		context_data,
		compound_literal_array...
	)

Value:

    CCC_private_priority_queue_from(type_intruder_field, order, compare,       \
                                    allocate, destroy, context_data,           \
                                    compound_literal_array)

Initialize a priority queue at runtime from a compound literal array.

Parameters

[in]	type_intruder_field	the name of the field intruding on user's type.
[in]	order	CCC_ORDER_LESSER for a min priority queue or CCC_ORDER_GREATER for a max priority queue.
[in]	compare	the function used to compare two user types.
[in]	allocate	the allocation function required for construction.
[in]	destroy	the optional destructor to run if insertion fails.
[in]	context_data	context data needed for comparison or destruction.
[in]	compound_literal_array	the array of user types to insert into the map (e.g. (struct My_type[]){ {.key = 1, .val = 1}, {.key = 2, .val = 2}}).

Returns: the initialized priority_queue on the right side of an equality operator (e.g. CCC_Priority_queue priority_queue = CCC_priority_queue_from(...);)

◆ CCC_priority_queue_increase_with

#define CCC_priority_queue_increase_with	(	priority_queue_pointer,
		type_pointer,
		increase_closure_over_T...
	)

Value:

CCC_private_priority_queue_increase_with( \

priority_queue_pointer, type_pointer, increase_closure_over_T)

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

Parameters

[in]	priority_queue_pointer	a pointer to the priority queue.
[in]	type_pointer	a pointer to the user struct type_intruder in the priority_queue.
[in]	increase_closure_over_T	a pointer to the user struct type_intruder T is made available. Use a semicolon separated statements to execute on the user type which wraps priority_queue_node_pointer (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 updated user type_intruder or NULL if update failed due to bad arguments provided.

Warning: the user must ensure the type_pointer is a reference to an instance of the type_intruder actively stored in the priority queue. 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
{
    priority_queue_node e;
    int key;
};
Priority_queue priority_queue = build_rand_priority_queue();
priority_queue_increase_with(&priority_queue, get_rand_val(&priority_queue), {
T->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 priority_queue creates an amortized o(lgN) runtime for this function.

◆ CCC_priority_queue_initialize

#define CCC_priority_queue_initialize	(	struct_name,
		type_intruder_field,
		order,
		compare,
		allocate,
		context_data
	)

Value:

    CCC_private_priority_queue_initialize(struct_name, type_intruder_field,    \
                                          order, compare, allocate,            \
                                          context_data)

Initialize a priority queue at runtime or compile time.

Parameters

[in]	struct_name	the name of the user type_intruder wrapping priority_queue elems.
[in]	type_intruder_field	the name of the field for the priority_queue elem.
[in]	order	CCC_ORDER_LESSER for a min priority_queue or CCC_ORDER_GREATER for a max priority_queue.
[in]	compare	the function used to compare two user types.
[in]	allocate	the allocation function or NULL if allocation is banned.
[in]	context_data	context data needed for comparison or destruction.

Returns: the initialized priority_queue on the right side of an equality operator (e.g. CCC_Priority_queue priority_queue = CCC_priority_queue_initialize(...);)

◆ CCC_priority_queue_update_with

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

Value:

CCC_private_priority_queue_update_with( \

priority_queue_pointer, type_pointer, update_closure_over_T)

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

Parameters

[in]	priority_queue_pointer	a pointer to the priority queue.
[in]	type_pointer	a pointer to the user struct type_intruder in the priority_queue.
[in]	update_closure_over_T	a pointer to the user struct type_intruder T is made available. Use a semicolon separated statements to execute on the user type which wraps priority_queue_node_pointer (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 updated user type_intruder or NULL if update failed due to bad arguments provided.

Warning: the user must ensure the type_pointer is a reference to an instance of the type_intruder actively stored in the priority queue.

#define PRIORITY_QUEUE_USING_NAMESPACE_CCC
struct Val
{
    priority_queue_node e;
    int key;
};
Priority_queue priority_queue = build_rand_priority_queue();
priority_queue_update_with(&priority_queue, get_rand_val(&priority_queue), {
T->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_Priority_queue

typedef struct CCC_Priority_queue 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.

◆ CCC_Priority_queue_node

typedef struct CCC_Priority_queue_node CCC_Priority_queue_node

The embedded struct type_intruder 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.

Function Documentation

◆ CCC_priority_queue_clear()

CCC_Result CCC_priority_queue_clear	(	CCC_Priority_queue *	priority_queue,
		CCC_Type_destructor *	destroy
	)

Removes all elements from the priority_queue, freeing if needed.

Parameters

[in]	priority_queue	a pointer to the priority queue.
[in]	destroy	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 priority_queue. Therefore, the user should not free in the destructor function. Only perform context 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 priority_queue, calling destroy on each user type_intruder if provided, and sets the size to zero.

◆ CCC_priority_queue_count()

CCC_Count CCC_priority_queue_count ( CCC_Priority_queue const * priority_queue )

Returns the count of priority queue occupied nodes.

Parameters

[in] priority_queue a pointer to the priority queue.

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

◆ CCC_priority_queue_decrease()

void * CCC_priority_queue_decrease	(	CCC_Priority_queue *	priority_queue,
		CCC_Priority_queue_node *	type_intruder,
		CCC_Type_modifier *	modify,
		void *	context
	)

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

Parameters

[in]	priority_queue	a pointer to the priority queue.
[in]	type_intruder	a pointer to the intrusive element in the user type.
[in]	modify	the update function to act on the type_intruder wrapping elem.
[in]	context	any context data needed for the update function.

Returns: a reference to the updated user type_intruder or NULL if update failed due to bad arguments provided.

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 priority_queue creates an amortized o(lgN) runtime for this function.

◆ CCC_priority_queue_erase()

CCC_Result CCC_priority_queue_erase	(	CCC_Priority_queue *	priority_queue,
		CCC_Priority_queue_node *	type_intruder
	)

Erase type_intruder from the priority_queue. Amortized O(lgN).

Parameters

[in]	priority_queue	a pointer to the priority queue.
[in]	type_intruder	a pointer to the intrusive element in the user type.

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

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

◆ CCC_priority_queue_extract()

void * CCC_priority_queue_extract	(	CCC_Priority_queue *	priority_queue,
		CCC_Priority_queue_node *	type_intruder
	)

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

Parameters

[in]	priority_queue	a pointer to the priority queue.
[in]	type_intruder	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 type_intruder is in the priority queue.

◆ CCC_priority_queue_front()

void * CCC_priority_queue_front ( CCC_Priority_queue const * priority_queue )

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

Parameters

[in] priority_queue a pointer to the priority queue.

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

◆ CCC_priority_queue_increase()

void * CCC_priority_queue_increase	(	CCC_Priority_queue *	priority_queue,
		CCC_Priority_queue_node *	type_intruder,
		CCC_Type_modifier *	modify,
		void *	context
	)

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

Parameters

[in]	priority_queue	a pointer to the priority queue.
[in]	type_intruder	a pointer to the intrusive element in the user type.
[in]	modify	the update function to act on the type_intruder wrapping elem.
[in]	context	any context data needed for the update function.

Returns: a reference to the updated user type_intruder or NULL if update failed due to bad arguments provided.

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 priority_queue creates an amortized o(lgN) runtime for this function.

◆ CCC_priority_queue_is_empty()

CCC_Tribool CCC_priority_queue_is_empty ( CCC_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 priority queue.

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

◆ CCC_priority_queue_order()

CCC_Order CCC_priority_queue_order ( CCC_Priority_queue const * priority_queue )

Return the order used to initialize the priority_queue.

Parameters

[in] priority_queue a pointer to the priority queue.

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

◆ CCC_priority_queue_pop()

CCC_Result CCC_priority_queue_pop ( CCC_Priority_queue * priority_queue )

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

Parameters

[in] priority_queue a pointer to the priority queue.

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

◆ CCC_priority_queue_push()

void * CCC_priority_queue_push	(	CCC_Priority_queue *	priority_queue,
		CCC_Priority_queue_node *	type_intruder
	)

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

Parameters

[in]	priority_queue	a pointer to the priority queue.
[in]	type_intruder	a pointer to the intrusive element in the user type.

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

Note that if allocation is permitted the user type_intruder 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_priority_queue_update()

void * CCC_priority_queue_update	(	CCC_Priority_queue *	priority_queue,
		CCC_Priority_queue_node *	type_intruder,
		CCC_Type_modifier *	modify,
		void *	context
	)

Update the priority in the user type_intruder wrapping elem.

Parameters

[in]	priority_queue	a pointer to the priority queue.
[in]	type_intruder	a pointer to the intrusive element in the user type.
[in]	modify	the update function to act on the type_intruder wrapping elem.
[in]	context	any context data needed for the update function.

Returns: a reference to the updated user type_intruder or NULL if update failed due to bad arguments provided.

Warning: the user must ensure type_intruder is in the priority_queue.

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

CCC_Tribool CCC_priority_queue_validate ( CCC_Priority_queue const * priority_queue )

Verifies the internal invariants of the priority_queue hold.

Parameters

[in] priority_queue a pointer to the priority queue.

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

Detailed Description

Initialization Interface

Insert and Remove Interface

Container Types

Deallocation Interface

State Interface

Macro Definition Documentation

◆ CCC_priority_queue_decrease_with

◆ CCC_priority_queue_emplace

◆ CCC_priority_queue_from

◆ CCC_priority_queue_increase_with

◆ CCC_priority_queue_initialize

◆ CCC_priority_queue_update_with

Typedef Documentation

◆ CCC_Priority_queue

◆ CCC_Priority_queue_node

Function Documentation

◆ CCC_priority_queue_clear()

◆ CCC_priority_queue_count()

◆ CCC_priority_queue_decrease()

◆ CCC_priority_queue_erase()

◆ CCC_priority_queue_extract()

◆ CCC_priority_queue_front()

◆ CCC_priority_queue_increase()

◆ CCC_priority_queue_is_empty()

◆ CCC_priority_queue_order()

◆ CCC_priority_queue_pop()

◆ CCC_priority_queue_push()

◆ CCC_priority_queue_update()

◆ CCC_priority_queue_validate()