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 and callbacks.
#define	CCC_priority_queue_default( type_name, type_intruder_field, order, comparator)
	Initialize a default priority queue at runtime or compile time.

#define	CCC_priority_queue_for( type_name, type_intruder_field, order, comparator...)
	Initialize a priority queue at runtime or compile time.

#define	CCC_priority_queue_from( type_intruder_field, order, comparator, allocator, destructor, 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, allocator_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, closure_parameter, update_closure_over_closure_parameter...)
	Update the priority in the user type stored in the container.

#define	CCC_priority_queue_increase_with( priority_queue_pointer, closure_parameter, increase_closure_over_closure_parameter...)
	Increases the priority of the user type stored in the container.

#define	CCC_priority_queue_decrease_with( priority_queue_pointer, closure_parameter, decrease_closure_over_closure_parameter...)
	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, CCC_Allocator const *allocator)
	Adds an element to the priority queue in correct total order. O(1).

CCC_Result	CCC_priority_queue_pop (CCC_Priority_queue priority_queue, CCC_Allocator const allocator)
	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, CCC_Allocator const *allocator)
	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_Modifier const *modifier)
	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_Modifier const *modifier)
	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_Modifier const *modifier)
	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_Destructor const destructor, CCC_Allocator const *allocator)
	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,
		closure_parameter,
		decrease_closure_over_closure_parameter...
	)

Value:

    CCC_private_priority_queue_decrease_with(                                  \
        priority_queue_pointer,                                                \
        closure_parameter,                                                     \
        decrease_closure_over_closure_parameter                                \
    )

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

Parameters

[in]	priority_queue_pointer	a pointer to the priority queue.
[in]	closure_parameter	a pointer variable to the user type being updated.
[in]	decrease_closure_over_closure_parameter	the semicolon separated statements to execute on the user type provided (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();
struct Val *e = get_rand_priority_queue_node(&priority_queue);
priority_queue_decrease_with(&priority_queue, e, { e->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 amortized o(lgN) runtime for this function.

◆ CCC_priority_queue_default

#define CCC_priority_queue_default	(	type_name,
		type_intruder_field,
		order,
		comparator
	)

Value:

    CCC_private_priority_queue_for(                                            \
        type_name, type_intruder_field, order, comparator                      \
    )

Initialize a default priority queue at runtime or compile time.

Parameters

[in]	type_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]	comparator	the pointer to CCC_Comparator for type comparison.

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

◆ CCC_priority_queue_emplace

#define CCC_priority_queue_emplace	(	priority_queue_pointer,
		allocator_pointer,
		type_compound_literal...
	)

Value:

    CCC_private_priority_queue_emplace(                                        \
        priority_queue_pointer, allocator_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]	allocator_pointer	the pointer for allocation. It is required.
[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.

Warning: a non-empty &(CCC_Allocator){.allocate = my_allocate} must be provided so that memory can be allocated for the compound literal data.

◆ CCC_priority_queue_for

#define CCC_priority_queue_for	(	type_name,
		type_intruder_field,
		order,
		comparator...
	)

Value:

    CCC_private_priority_queue_for(                                            \
        type_name, type_intruder_field, order, comparator                      \
    )

Initialize a priority queue at runtime or compile time.

Parameters

[in]	type_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]	comparator	the CCC_Comparator for type comparison.

Returns: the priority_queue on the right side of equality operator.

◆ CCC_priority_queue_from

#define CCC_priority_queue_from	(	type_intruder_field,
		order,
		comparator,
		allocator,
		destructor,
		compound_literal_array...
	)

Value:

    CCC_private_priority_queue_from(                                           \
        type_intruder_field,                                                   \
        order,                                                                 \
        comparator,                                                            \
        allocator,                                                             \
        destructor,                                                            \
        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]	comparator	the CCC_Comparator to compare two user types.
[in]	allocator	the CCC_Allocator for construction.
[in]	destructor	optional CCC_Destructor if insertion fails.
[in]	compound_literal_array	the array of user types to insert.

Returns: the priority_queue on the right side of an equality operator

◆ CCC_priority_queue_increase_with

#define CCC_priority_queue_increase_with	(	priority_queue_pointer,
		closure_parameter,
		increase_closure_over_closure_parameter...
	)

Value:

    CCC_private_priority_queue_increase_with(                                  \
        priority_queue_pointer,                                                \
        closure_parameter,                                                     \
        increase_closure_over_closure_parameter                                \
    )

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

Parameters

[in]	priority_queue_pointer	a pointer to the priority queue.
[in]	closure_parameter	a pointer variable to the user type being updated.
[in]	increase_closure_over_closure_parameter	the semicolon separated statements to execute on the user type provided (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 or NULL if update failed due to bad arguments provided.

Warning: the user must ensure the closure parameter is a reference to an instance of the type 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();
struct Val *e = get_rand_val(&priority_queue);
priority_queue_increase_with(&priority_queue, e, { e->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 amortized o(lgN) runtime for this function.

◆ CCC_priority_queue_update_with

#define CCC_priority_queue_update_with	(	priority_queue_pointer,
		closure_parameter,
		update_closure_over_closure_parameter...
	)

Value:

    CCC_private_priority_queue_update_with(                                    \
        priority_queue_pointer,                                                \
        closure_parameter,                                                     \
        update_closure_over_closure_parameter                                  \
    )

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

Parameters

[in]	priority_queue_pointer	a pointer to the priority queue.
[in]	closure_parameter	a pointer variable to the user type being updated.
[in]	update_closure_over_closure_parameter	the semicolon separated statements to execute on the user type provided (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 or NULL if update failed due to bad arguments provided.

Warning: the user must ensure the closure parameter is a reference to an instance of the type 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();
struct Val *e = get_rand_val(&priority_queue);
priority_queue_update_with(&priority_queue, e, { e->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_Destructor const *	destructor,
		CCC_Allocator const *	allocator
	)

Removes all elements from the priority_queue, freeing if needed.

Parameters

[in]	priority_queue	a pointer to the priority queue.
[in]	destructor	the CCC_Destructor if needed.
[in]	allocator	the CCC_Allocator to free elements, if needed.

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

◆ 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_Modifier const *	modifier
	)

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]	modifier	the CCC_Modifier to act on the type_intruder wrapping elem.

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 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,
		CCC_Allocator const *	allocator
	)

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.
[in]	allocator	the CCC_Allocator to free the element, if needed.

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_Modifier const *	modifier
	)

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]	modifier	the CCC_Modifier to act on the type_intruder wrapping elem.

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 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,
		CCC_Allocator const *	allocator
	)

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

Parameters

[in]	priority_queue	a pointer to the priority queue.
[in]	allocator	the CCC_Allocator to free the element, if needed.

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,
		CCC_Allocator const *	allocator
	)

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.
[in]	allocator	the CCC_Allocator for insertion allocation, if needed.

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_Modifier const *	modifier
	)

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]	modifier	the CCC_Modifier to act on the type_intruder wrapping elem.

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_default

◆ CCC_priority_queue_emplace

◆ CCC_priority_queue_for

◆ CCC_priority_queue_from

◆ CCC_priority_queue_increase_with

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