Fixed-size queue based on ring buffer.
More...
#include "is_pow2.h"
#include "paste.h"
#include "round_up_pow2.h"
#include <assert.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
Go to the source code of this file.
|
struct | fqueue |
| Generated queue struct type for a VALUE_TYPE . More...
|
|
|
#define | fqueue_for_each(self, index, value) |
| Iterate over the values in the queue from the front to back.
|
|
#define | fqueue_for_each_reverse(self, index, value) |
| Iterate over the values in the queue from the back to front.
|
|
#define | fqueue_calc_sizeof(fqueue_name, capacity) |
| Calculate the size of the queue struct. No overflow checks.
|
|
#define | fqueue_calc_sizeof_overflows(fqueue_name, capacity) |
| Check for a given capacity, if the equivalent size of the queue struct overflows.
|
|
#define | NAME fqueue |
| Prefix to queue type and operations. This must be manually defined before including this header file.
|
|
#define | VALUE_TYPE int |
| Queue value type. This must be manually defined before including this header file.
|
|
|
static fqueue_type * | fqueue_init (fqueue_type *self, const uint32_t pow2_capacity) |
| Initialize a queue struct, given a (power-of-2) capacity.
|
|
static fqueue_type * | fqueue_create (const uint32_t min_capacity) |
| Create an queue struct with a given capacity with malloc().
|
|
static void | fqueue_destroy (fqueue_type *self) |
| Destroy an queue struct and free the underlying memory with free().
|
|
static bool | fqueue_is_empty (const fqueue_type *self) |
| Return whether the queue is empty.
|
|
static bool | fqueue_is_full (const fqueue_type *self) |
| Return whether the queue is full.
|
|
static VALUE_TYPE | fqueue_at (const fqueue_type *self, const uint32_t index) |
| Get the value at index.
|
|
static VALUE_TYPE | fqueue_get_front (const fqueue_type *self) |
| Get the value from the front of a non-empty queue.
|
|
static VALUE_TYPE | fqueue_get_back (const fqueue_type *self) |
| Get the value from the back of a non-empty queue.
|
|
static VALUE_TYPE | fqueue_peek (const fqueue_type *self) |
| Peek a non-empty queue and get it's next to-be-dequeued value.
|
|
static bool | fqueue_enqueue (fqueue_type *self, const VALUE_TYPE value) |
| Enqueue a value at the back of a non-full queue.
|
|
static VALUE_TYPE | fqueue_dequeue (fqueue_type *self) |
| Dequeue a value from the front of a non-empty queue.
|
|
static void | fqueue_clear (fqueue_type *self) |
| Clear the elements in the queue.
|
|
static void | fqueue_copy (fqueue_type *restrict dest_ptr, const fqueue_type *restrict src_ptr) |
| Copy the values from a source queue to a destination queue.
|
|
Fixed-size queue based on ring buffer.
The following macros must be defined:
◆ fqueue_calc_sizeof
#define fqueue_calc_sizeof |
( |
| fqueue_name, |
|
|
| capacity ) |
Value: (uint32_t)(offsetof(struct fqueue_name, values) + capacity * sizeof(((struct fqueue_name *)0)->values[0]))
Calculate the size of the queue struct. No overflow checks.
- Parameters
-
[in] | fqueue_name | Defined queue NAME. |
[in] | capacity | Capacity input. |
- Returns
- The equivalent size.
◆ fqueue_calc_sizeof_overflows
#define fqueue_calc_sizeof_overflows |
( |
| fqueue_name, |
|
|
| capacity ) |
Value: (capacity > (UINT32_MAX - offsetof(struct fqueue_name, values)) / sizeof(((struct fqueue_name *)0)->values[0]))
Check for a given capacity, if the equivalent size of the queue struct overflows.
- Parameters
-
[in] | fqueue_name | Defined queue NAME. |
[in] | capacity | Capacity input. |
- Returns
- Whether the equivalent size overflows.
◆ fqueue_for_each
#define fqueue_for_each |
( |
| self, |
|
|
| index, |
|
|
| value ) |
Value: for ((index) = 0; (index) < (self)->count \
&& ((value) = (self)->values[((self)->begin_index + (index)) & ((self)->capacity - 1)], true); \
(index)++)
Iterate over the values in the queue from the front to back.
- Warning
- Modifying the queue under the iteration may result in errors.
- Parameters
-
[in] | self | Queue pointer. |
[in] | index | Temporary indexing variable. Should be uint32_t . |
[out] | value | Current value. Should be VALUE_TYPE . |
◆ fqueue_for_each_reverse
#define fqueue_for_each_reverse |
( |
| self, |
|
|
| index, |
|
|
| value ) |
Value: for ((index) = 0; (index) < (self)->count \
&& ((value) = (self)->values[((self)->end_index - 1 - (index)) & ((self)->capacity - 1)], true); \
(index)++)
Iterate over the values in the queue from the back to front.
- Warning
- Modifying the queue under the iteration may result in errors.
- Parameters
-
[in] | self | Queue pointer. |
[in] | index | Temporary indexing variable. Should be uint32_t . |
[out] | value | Current value. Should be VALUE_TYPE . |
◆ NAME
Prefix to queue type and operations. This must be manually defined before including this header file.
Is undefined after header is included.
◆ VALUE_TYPE
Queue value type. This must be manually defined before including this header file.
Is undefined after header is included.
◆ fqueue_at()
static VALUE_TYPE fqueue_at |
( |
const fqueue_type * | self, |
|
|
const uint32_t | index ) |
|
inlinestatic |
Get the value at index.
- Note
- Index starts from the front as
0
and is counted upward to count - 1
as back.
- Parameters
-
[in] | self | The queue pointer. |
[in] | index | The index to retrieve to value from. |
- Returns
- The value at
index
.
◆ fqueue_clear()
static void fqueue_clear |
( |
fqueue_type * | self | ) |
|
|
inlinestatic |
Clear the elements in the queue.
- Parameters
-
[in] | self | The queue pointer. |
◆ fqueue_copy()
static void fqueue_copy |
( |
fqueue_type *restrict | dest_ptr, |
|
|
const fqueue_type *restrict | src_ptr ) |
|
inlinestatic |
Copy the values from a source queue to a destination queue.
- Parameters
-
[in,out] | dest_ptr | The destination queue. |
[in] | src_ptr | The source queue. |
◆ fqueue_create()
static fqueue_type * fqueue_create |
( |
const uint32_t | min_capacity | ) |
|
|
inlinestatic |
Create an queue struct with a given capacity with malloc().
- Parameters
-
[in] | min_capacity | Maximum number of elements expected to be stored |
- Returns
- A pointer to the queue.
- Return values
-
NULL |
- If malloc fails.
- If capacity is 0 or larger than UINT32_MAX / 2 + 1 or the equivalent size overflows.
|
◆ fqueue_dequeue()
static VALUE_TYPE fqueue_dequeue |
( |
fqueue_type * | self | ) |
|
|
inlinestatic |
Dequeue a value from the front of a non-empty queue.
- Parameters
-
[in] | self | The queue pointer. |
- Returns
- The front value.
◆ fqueue_destroy()
static void fqueue_destroy |
( |
fqueue_type * | self | ) |
|
|
inlinestatic |
Destroy an 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 queue pointer. |
◆ fqueue_enqueue()
static bool fqueue_enqueue |
( |
fqueue_type * | self, |
|
|
const VALUE_TYPE | value ) |
|
inlinestatic |
Enqueue a value at the back of a non-full queue.
- Parameters
-
[in] | self | The queue pointer. |
[in] | value | The value to enqueue. |
◆ fqueue_get_back()
static VALUE_TYPE fqueue_get_back |
( |
const fqueue_type * | self | ) |
|
|
inlinestatic |
Get the value from the back of a non-empty queue.
- Parameters
-
[in] | self | The queue pointer. |
- Returns
- The back value.
◆ fqueue_get_front()
static VALUE_TYPE fqueue_get_front |
( |
const fqueue_type * | self | ) |
|
|
inlinestatic |
Get the value from the front of a non-empty queue.
- Parameters
-
[in] | self | The queue pointer. |
- Returns
- The front value.
◆ fqueue_init()
static fqueue_type * fqueue_init |
( |
fqueue_type * | self, |
|
|
const uint32_t | pow2_capacity ) |
|
inlinestatic |
Initialize a queue struct, given a (power-of-2) capacity.
- Parameters
-
[in] | self | Queue pointer |
[in] | pow2_capacity | Power of 2 capacity |
◆ fqueue_is_empty()
static bool fqueue_is_empty |
( |
const fqueue_type * | self | ) |
|
|
inlinestatic |
Return whether the queue is empty.
- Parameters
-
[in] | self | The queue pointer. |
- Returns
- Whether the queue is empty.
◆ fqueue_is_full()
static bool fqueue_is_full |
( |
const fqueue_type * | self | ) |
|
|
inlinestatic |
Return whether the queue is full.
- Parameters
-
[in] | self | The queue pointer. |
- Returns
- Whether the queue is full.
◆ fqueue_peek()
static VALUE_TYPE fqueue_peek |
( |
const fqueue_type * | self | ) |
|
|
inlinestatic |
Peek a non-empty queue and get it's next to-be-dequeued value.
- Parameters
-
[in] | self | The queue pointer. |
- Returns
- The next to-be-dequeued value.