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

#include "paste.h"
#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	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	NAME fpqueue
	Prefix to priority queue types and operations. This must be manually defined before including this header file.

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

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

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

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

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

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

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

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

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

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

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

static 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`.

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

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

◆ NAME

#define NAME fpqueue

Prefix to priority queue types and operations. This must be manually defined before including this header file.

Is undefined after header is included.

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

Function Documentation

◆ fpqueue_clear()

static void fpqueue_clear ( fpqueue_type * self )

inlinestatic

Clear the elements in the priority queue.

Parameters

[in] self The priority queue pointer.

◆ fpqueue_copy()

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

inlinestatic

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

static fpqueue_type * fpqueue_create ( const uint32_t capacity )

inlinestatic

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

static void fpqueue_destroy ( fpqueue_type * self )

inlinestatic

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

static VALUE_TYPE fpqueue_get_max ( const fpqueue_type * self )

inlinestatic

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

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

inlinestatic

Initialize a priority queue struct, given a capacity.

Parameters

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

◆ fpqueue_is_empty()

static bool fpqueue_is_empty ( const fpqueue_type * self )

inlinestatic

Return whether the priority queue is empty.

Parameters

[in] self The priority queue pointer.

Returns: Whether the priority queue is empty.

◆ fpqueue_is_full()

static bool fpqueue_is_full ( const fpqueue_type * self )

inlinestatic

Return whether the priority queue is full.

Parameters

[in] self The priority queue pointer.

Returns: Whether the priority queue is full.

◆ fpqueue_peek()

static VALUE_TYPE fpqueue_peek ( const fpqueue_type * self )

inlinestatic

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

static VALUE_TYPE fpqueue_pop_max ( fpqueue_type * self )

inlinestatic

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

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

inlinestatic

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

◆ NAME

◆ VALUE_TYPE

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