Fixed-size priority queue based on binary (max-)heap. More...

#include <assert.h>
#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>
#include <stdlib.h>

Classes
struct	fpqueue_element
	Generated priority queue element struct type for a given `VALUE_TYPE`. More...

struct	fpqueue
	Generated priority queue struct type for a given `VALUE_TYPE`. More...

Macros
#define	PASTE(a, b)
	Paste two tokens together.

#define	XPASTE(a, b)
	First expand tokens, then paste them together.

#define	JOIN(a, b)
	First expand tokens, then paste them together with a _ in between.

#define	FPQUEUE_LEFT_CHILD(index)
	Given an element index, get the index of the left child.

#define	FPQUEUE_RIGHT_CHILD(index)
	Given an element index, get the index of the right child.

#define	FPQUEUE_PARENT(index)
	Given an element index, get the index of the parent.

#define	FPQUEUE_FOR_EACH(self, index, value_)
	Iterate over the values in the priority queue in breadth-first order.

#define	FPQUEUE_CALC_SIZEOF(fpqueue_name, capacity)
	Calculate the size of the pqueue struct. No overflow checks.

#define	FPQUEUE_CALC_SIZEOF_OVERFLOWS(fpqueue_name, capacity)
	Check for a given capacity, if the equivalent size of the pqueue struct overflows.

#define	VALUE_TYPE int
	Priority queue value type. This must be manually defined before including this header file.

#define	FUNCTION_DEFINITIONS
	Define the functions.

#define	TYPE_DEFINITIONS
	Define the types.

#define	FUNCTION_LINKAGE
	Specify function linkage e.g. static inline.

Functions
fpqueue_type *	fpqueue_init (fpqueue_type *self, const uint32_t capacity)
	Initialize a priority queue struct, given a capacity.

fpqueue_type *	fpqueue_create (const uint32_t capacity)
	Create an priority queue struct with a given capacity with malloc().

void	fpqueue_destroy (fpqueue_type *self)
	Destroy an priority queue struct and free the underlying memory with free().

bool	fpqueue_is_empty (const fpqueue_type *self)
	Return whether the priority queue is empty.

bool	fpqueue_is_full (const fpqueue_type *self)
	Return whether the priority queue is full.

VALUE_TYPE	fpqueue_get_max (const fpqueue_type *self)
	Get the max priority value in a non-empty priority queue.

VALUE_TYPE	fpqueue_peek (const fpqueue_type *self)
	Peek a non-empty priority queue and get it's next to-be-popped (max priority) value.

VALUE_TYPE	fpqueue_pop_max (fpqueue_type *self)
	Pop the max priority value away from a non-empty priority queue.

void	fpqueue_push (fpqueue_type *self, VALUE_TYPE value, const uint32_t priority)
	Push a value with given priority onto a non-full priority queue.

void	fpqueue_clear (fpqueue_type *self)
	Clear the elements in the priority queue.

void	fpqueue_copy (fpqueue_type restrict dest_ptr, const fpqueue_type restrict src_ptr)
	Copy the values from a source priority queue to a destination priority queue.

Detailed Description

Fixed-size priority queue based on binary (max-)heap.

The following macros must be defined:

NAME
VALUE_TYPE

Source used:

CLRS

Macro Definition Documentation

◆ FPQUEUE_CALC_SIZEOF

#define FPQUEUE_CALC_SIZEOF	(		fpqueue_name,
			capacity )

Value:

(uint32_t)(offsetof(struct fpqueue_name, elements) + capacity * sizeof(((struct fpqueue_name *)0)->elements[0]))

Calculate the size of the pqueue struct. No overflow checks.

Parameters

[in]	fpqueue_name	Defined pqueue NAME.
[in]	capacity	Capacity input.

Returns: The equivalent size.

◆ FPQUEUE_CALC_SIZEOF_OVERFLOWS

#define FPQUEUE_CALC_SIZEOF_OVERFLOWS	(		fpqueue_name,
			capacity )

Value:

(capacity \

> (UINT32_MAX - offsetof(struct fpqueue_name, elements)) / sizeof(((struct fpqueue_name *)0)->elements[0]))

Check for a given capacity, if the equivalent size of the pqueue struct overflows.

Parameters

[in]	fpqueue_name	Defined pqueue NAME.
[in]	capacity	Capacity input.

Returns: Whether the equivalent size overflows.

◆ FPQUEUE_FOR_EACH

#define FPQUEUE_FOR_EACH	(	self,
		index,
		value_ )

Value:

for ((index) = 0; (index) < (self)->count && ((value_) = (self)->elements[(index)].value, true); (index)++)

Iterate over the values in the priority queue in breadth-first order.

Warning: Modifying the priority queue under the iteration may result in errors.

Parameters

[in]	self	Priority queue pointer.
[in]	index	Temporary indexing variable. Should be `uint32_t`.
[out]	value_	Current value. Should be `VALUE_TYPE`.

Examples: fpqueue_example.c.

◆ FPQUEUE_LEFT_CHILD

#define FPQUEUE_LEFT_CHILD ( index )

Value:

(2 * (index) + 1)

Given an element index, get the index of the left child.

Parameters

[in] index The element index.

Examples: fpqueue_example.c.

◆ FPQUEUE_PARENT

#define FPQUEUE_PARENT ( index )

Value:

(((index) - 1) / 2)

Given an element index, get the index of the parent.

Parameters

[in] index The element index.

◆ FPQUEUE_RIGHT_CHILD

#define FPQUEUE_RIGHT_CHILD ( index )

Value:

(2 * (index) + 2)

Given an element index, get the index of the right child.

Parameters

[in] index The element index.

Examples: fpqueue_example.c.

◆ JOIN

#define JOIN	(		a,
			b )

Value:

XPASTE(a, XPASTE(_, b))

XPASTE

#define XPASTE(a, b)

First expand tokens, then paste them together.

Definition fstack_template.h:42

First expand tokens, then paste them together with a _ in between.

◆ PASTE

#define PASTE	(		a,
			b )

Value:

a##b

Paste two tokens together.

◆ VALUE_TYPE

#define VALUE_TYPE int

Priority queue value type. This must be manually defined before including this header file.

Is undefined after header is included.

◆ XPASTE

#define XPASTE	(		a,
			b )

Value:

PASTE(a, b)

PASTE

#define PASTE(a, b)

Paste two tokens together.

Definition fstack_template.h:34

First expand tokens, then paste them together.

Function Documentation

◆ fpqueue_clear()

void fpqueue_clear ( fpqueue_type * self )

Clear the elements in the priority queue.

Parameters

[in] self The priority queue pointer.

◆ fpqueue_copy()

void fpqueue_copy	(	fpqueue_type *restrict	dest_ptr,
		const fpqueue_type *restrict	src_ptr )

Copy the values from a source priority queue to a destination priority queue.

Parameters

[in,out]	dest_ptr	The destination priority queue.
[in]	src_ptr	The source priority queue.

◆ fpqueue_create()

fpqueue_type * fpqueue_create ( const uint32_t capacity )

Create an priority queue struct with a given capacity with malloc().

Parameters

[in] capacity Maximum number of elements expected to be stored.

Returns: A pointer to the priority queue.

Return values

NULL	If capacity is 0 or the equivalent size overflows. If malloc fails.

◆ fpqueue_destroy()

void fpqueue_destroy ( fpqueue_type * self )

Destroy an priority queue struct and free the underlying memory with free().

Warning: May not be called twice in a row on the same object.

Parameters

[in] self The priority queue pointer.

◆ fpqueue_get_max()

VALUE_TYPE fpqueue_get_max ( const fpqueue_type * self )

Get the max priority value in a non-empty priority queue.

Parameters

[in] self The priority queue pointer.

Returns: The max priority value.

◆ fpqueue_init()

fpqueue_type * fpqueue_init	(	fpqueue_type *	self,
		const uint32_t	capacity )

Initialize a priority queue struct, given a capacity.

Parameters

[in]	self	Priority queue pointer
[in]	capacity	Capacity

◆ fpqueue_is_empty()

bool fpqueue_is_empty ( const fpqueue_type * self )

Return whether the priority queue is empty.

Parameters

[in] self The priority queue pointer.

Returns: Whether the priority queue is empty.

◆ fpqueue_is_full()

bool fpqueue_is_full ( const fpqueue_type * self )

Return whether the priority queue is full.

Parameters

[in] self The priority queue pointer.

Returns: Whether the priority queue is full.

◆ fpqueue_peek()

VALUE_TYPE fpqueue_peek ( const fpqueue_type * self )

Peek a non-empty priority queue and get it's next to-be-popped (max priority) value.

Parameters

[in] self The priority queue pointer.

Returns: The next to-be-popped (max priority) value.

◆ fpqueue_pop_max()

VALUE_TYPE fpqueue_pop_max ( fpqueue_type * self )

Pop the max priority value away from a non-empty priority queue.

Parameters

[in] self The priority queue pointer.

Returns: The max value.

◆ fpqueue_push()

void fpqueue_push	(	fpqueue_type *	self,
		VALUE_TYPE	value,
		const uint32_t	priority )

Push a value with given priority onto a non-full priority queue.

Parameters

[in]	self	The priority queue pointer.
[in]	value	The value.
[in]	priority	The priority (with large number meaning high priority and vice versa).

Classes

Macros

Functions

Detailed Description

Macro Definition Documentation

◆ FPQUEUE_CALC_SIZEOF

◆ FPQUEUE_CALC_SIZEOF_OVERFLOWS

◆ FPQUEUE_FOR_EACH

◆ FPQUEUE_LEFT_CHILD

◆ FPQUEUE_PARENT

◆ FPQUEUE_RIGHT_CHILD

◆ JOIN

◆ PASTE

◆ VALUE_TYPE

◆ XPASTE

Function Documentation

◆ fpqueue_clear()

◆ fpqueue_copy()

◆ fpqueue_create()

◆ fpqueue_destroy()

◆ fpqueue_get_max()

◆ fpqueue_init()

◆ fpqueue_is_empty()

◆ fpqueue_is_full()

◆ fpqueue_peek()

◆ fpqueue_pop_max()

◆ fpqueue_push()