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>
Go to the source code of this file.
|
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...
|
|
|
#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.
|
|
|
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.
|
|
Fixed-size priority queue based on binary (max-)heap.
The following macros must be defined:
Source used:
◆ 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:
Given an element index, get the index of the left child.
- Parameters
-
[in] | index | The element index. |
◆ fpqueue_parent
#define fpqueue_parent |
( |
| index | ) |
|
Value:
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:
Given an element index, get the index of the right child.
- Parameters
-
[in] | index | The element index. |
◆ NAME
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
Priority queue value type. This must be manually defined before including this header file.
Is undefined after header is included.
◆ 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). |