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>

Classes
struct	fqueue
	Generated queue struct type for a `VALUE_TYPE`. More...

Macros
#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.

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

Detailed Description

Fixed-size queue based on ring buffer.

The following macros must be defined:

NAME
VALUE_TYPE

Macro Definition Documentation

◆ 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

#define NAME fqueue

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

Is undefined after header is included.

◆ VALUE_TYPE

#define VALUE_TYPE int

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

Is undefined after header is included.

Function Documentation

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

Classes

Macros

Functions

Detailed Description

Macro Definition Documentation

◆ fqueue_calc_sizeof

◆ fqueue_calc_sizeof_overflows

◆ fqueue_for_each

◆ fqueue_for_each_reverse

◆ NAME

◆ VALUE_TYPE

Function Documentation

◆ fqueue_at()

◆ fqueue_clear()

◆ fqueue_copy()

◆ fqueue_create()

◆ fqueue_dequeue()

◆ fqueue_destroy()

◆ fqueue_enqueue()

◆ fqueue_get_back()

◆ fqueue_get_front()

◆ fqueue_init()

◆ fqueue_is_empty()

◆ fqueue_is_full()

◆ fqueue_peek()