FIFO

FIFO (first in, first out) queue implementation. More...

Data Structures
struct	fifo
	FIFO instance. More...

Macros
#define	FIFO_INIT(fifo, elem_size, fifo_capacity)
	Allocates buffer and initializes fifo instance. More...

Functions
bool	fifo_init (struct fifo *fifo)
	Initializes FIFO. More...
size_t	fifo_capacity (const struct fifo *fifo)
	Returns number of elements the FIFO can hold. More...
size_t	fifo_readable (const struct fifo *fifo)
	Returns number of elements which can be read from the FIFO. More...
size_t	fifo_writable (const struct fifo *fifo)
	Returns number of elements which can be written to the FIFO. More...
size_t	fifo_read (struct fifo *fifo, void *dst, size_t count)
	Reads data from FIFO. More...
size_t	fifo_write (struct fifo *fifo, const void *src, size_t count)
	Writes data to FIFO. More...
size_t	fifo_gets (struct fifo *fifo, char *str)
	Reads null-terminated string from FIFO. More...
size_t	fifo_puts (struct fifo *fifo, const char *str)
	Writes null-terminated string to FIFO. More...

Detailed Description

FIFO (first in, first out) queue implementation.

The queue is lock-free as long as there is only one consumer and producer thread (i.e. there cannot be multiple threads writing to the queue or multiple threads reading from it). Use an appropriate locking mechanism if there are multiple producers or consumers accessing the queue.

The lock-free behavior is achieved by having a head index only updated by the producer and a tail index only updated by the consumer, both in an "atomic" way where it does not contain invalid intermediary values. To distinguish between the empty (head == tail) and full (head+1 == tail) states, a single element in the internal buffer is sacrificed as a trade-off for not having a third "full" flag (which would have to be updated by both consumer and producer, requiring a locking mechanism).

The implementation is thus not lock-free on architectures where loading or storing a size_t variable (used for the head and tail indexes) takes more than a single instruction (e.g. 8-bit CPUs).

Macro Definition Documentation

FIFO_INIT

#define FIFO_INIT	(		fifo,
			elem_size,
			fifo_capacity
	)

Value:

        do { \
                static char buffer[(elem_size)*((fifo_capacity)+1)]; \
                (fifo)->buffer = buffer; \
                (fifo)->element_size = (elem_size); \
                (fifo)->buffer_capacity = (fifo_capacity)+1; \
                fifo_init(fifo); \
        } while (0)

Allocates buffer and initializes fifo instance.

Parameters

fifo	Pointer to the fifo structure
elem_size	Size of a single element (see fifo.element_size)
fifo_capacity	Maximum number of elements in FIFO

Function Documentation

fifo_init()

bool fifo_init

(

struct fifo *

fifo

)

Initializes FIFO.

Parameters

fifo	Pointer to the fifo structure

Returns

true if initialization succeeds, false otherwise

fifo_capacity()

size_t fifo_capacity

(

const struct fifo *

fifo

)

Returns number of elements the FIFO can hold.

Parameters

fifo	Pointer to the fifo structure

Returns

The maximum number of elements the FIFO can hold

fifo_readable()

size_t fifo_readable

(

const struct fifo *

fifo

)

Returns number of elements which can be read from the FIFO.

Parameters

fifo	Pointer to the fifo structure

Returns

The number of elements available to read (0 to fifo_capacity())

fifo_writable()

size_t fifo_writable

(

const struct fifo *

fifo

)

Returns number of elements which can be written to the FIFO.

Parameters

fifo	Pointer to the fifo structure

Returns

The number of elements available to write (0 to fifo_capacity())

fifo_read()

size_t fifo_read	(	struct fifo *	fifo,
		void *	dst,
		size_t	count
	)

Reads data from FIFO.

Parameters

	fifo	Pointer to the fifo structure
[out]	dst	Pointer where the read data will be stored to
	count	Number of elements to be read

Returns

The number of elements actually read (0 to count)

fifo_write()

size_t fifo_write	(	struct fifo *	fifo,
		const void *	src,
		size_t	count
	)

Writes data to FIFO.

Parameters

	fifo	Pointer to the fifo structure
[in]	src	Pointer to the data written
	count	Number of elements to be written

Returns

The number of elements actually written (0 to count)

fifo_gets()

size_t fifo_gets	(	struct fifo *	fifo,
		char *	str
	)

Reads null-terminated string from FIFO.

This function assumes that fifo.element_size equals to one.

Parameters

	fifo	Pointer to the fifo structure
[out]	str	Pointer where the string will be stored to

Returns

Length of the string read (excluding terminating null-character)

fifo_puts()

size_t fifo_puts	(	struct fifo *	fifo,
		const char *	str
	)

Writes null-terminated string to FIFO.

This function assumes that fifo.element_size equals to one.

Parameters

	fifo	Pointer to the fifo structure
[in]	str	Pointer to the string to be written

Returns

Length of the string actually written (excluding terminating null-character)