Fixed-size queue based on ring buffer. More...

#include <assert.h>
#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include "round_up_pow2_32.h"

Classes
struct	fqueue
	Generated queue struct type for a `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	IS_POW2(X)
	Macro to check if a number is a power of two.

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

#define	FUNCTION_DEFINITIONS
	Define the functions.

#define	TYPE_DEFINITIONS
	Define the types.

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

Functions
fqueue_type *	fqueue_init (fqueue_type *self, const uint32_t pow2_capacity)
	Initialize a queue struct, given a (power-of-2) capacity.

fqueue_type *	fqueue_create (const uint32_t min_capacity)
	Create an queue struct with a given capacity with malloc().

void	fqueue_destroy (fqueue_type *self)
	Destroy an queue struct and free the underlying memory with free().

bool	fqueue_is_empty (const fqueue_type *self)
	Return whether the queue is empty.

bool	fqueue_is_full (const fqueue_type *self)
	Return whether the queue is full.

VALUE_TYPE	fqueue_at (const fqueue_type *self, const uint32_t index)
	Get the value at index.

VALUE_TYPE	fqueue_get_front (const fqueue_type *self)
	Get the value from the front of a non-empty queue.

VALUE_TYPE	fqueue_get_back (const fqueue_type *self)
	Get the value from the back of a non-empty queue.

VALUE_TYPE	fqueue_peek (const fqueue_type *self)
	Peek a non-empty queue and get it's next to-be-dequeued value.

bool	fqueue_enqueue (fqueue_type *self, const VALUE_TYPE value)
	Enqueue a value at the back of a non-full queue.

VALUE_TYPE	fqueue_dequeue (fqueue_type *self)
	Dequeue a value from the front of a non-empty queue.

void	fqueue_clear (fqueue_type *self)
	Clear the elements in the queue.

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.

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

Examples: fqueue_example.c.

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

Examples: fqueue_example.c.

◆ IS_POW2

#define IS_POW2 ( X )

Value:

((X) != 0 && ((X) & ((X) - 1)) == 0)

Macro to check if a number is a power of two.

Parameters

[in] X The number at hand.

Returns: A boolean value indicating whether the number is a power of two.

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

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

◆ PASTE

#define PASTE	(		a,
			b )

Value:

a##b

Paste two tokens together.

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

◆ 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

◆ fqueue_at()

VALUE_TYPE fqueue_at	(	const fqueue_type *	self,
		const uint32_t	index )

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

void fqueue_clear ( fqueue_type * self )

Clear the elements in the queue.

Parameters

[in] self The queue pointer.

◆ fqueue_copy()

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.

Parameters

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

◆ fqueue_create()

fqueue_type * fqueue_create ( const uint32_t min_capacity )

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

VALUE_TYPE fqueue_dequeue ( fqueue_type * self )

Dequeue a value from the front of a non-empty queue.

Parameters

[in] self The queue pointer.

Returns: The front value.

◆ fqueue_destroy()

void fqueue_destroy ( fqueue_type * self )

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

bool fqueue_enqueue	(	fqueue_type *	self,
		const VALUE_TYPE	value )

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

VALUE_TYPE fqueue_get_back ( const fqueue_type * self )

Get the value from the back of a non-empty queue.

Parameters

[in] self The queue pointer.

Returns: The back value.

◆ fqueue_get_front()

VALUE_TYPE fqueue_get_front ( const fqueue_type * self )

Get the value from the front of a non-empty queue.

Parameters

[in] self The queue pointer.

Returns: The front value.

◆ fqueue_init()

fqueue_type * fqueue_init	(	fqueue_type *	self,
		const uint32_t	pow2_capacity )

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

bool fqueue_is_empty ( const fqueue_type * self )

Return whether the queue is empty.

Parameters

[in] self The queue pointer.

Returns: Whether the queue is empty.

◆ fqueue_is_full()

bool fqueue_is_full ( const fqueue_type * self )

Return whether the queue is full.

Parameters

[in] self The queue pointer.

Returns: Whether the queue is full.

◆ fqueue_peek()

VALUE_TYPE fqueue_peek ( const fqueue_type * self )

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

◆ IS_POW2

◆ JOIN

◆ NAME

◆ PASTE

◆ VALUE_TYPE

◆ XPASTE

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