Ring buffers

Ring buffer implementation. More...

Macros
#define	csnip_ringbuf_Init(head, len, N)
	Initialize an empty ring buffer. More...
#define	csnip_ringbuf_GetHeadIdx(head, len, N, ret, err)
	Compute the location of the head in the backing array. More...
#define	csnip_ringbuf_GetTailIdx(head, len, N, ret, err)    csnip_ringbuf__GetTailIdx((head), (len), (N), (ret), (err))
	Compute the location of the tail in the backing array. More...
#define	csnip_ringbuf_PushHeadIdx(head, len, N, err)    csnip_ringbuf__PushHeadIdx((head), (len), (N), (err))
	Add an element at the head. More...
#define	csnip_ringbuf_PopHeadIdx(head, len, N, err)    csnip_ringbuf__PopHeadIdx((head), (len), (N), (err))
	Remove an element from the head.
#define	csnip_ringbuf_PushTailIdx(head, len, N, err)    csnip_ringbuf__PushTailIdx((head), (len), (N), (err))
	Add an element to the tail. More...
#define	csnip_ringbuf_PopTailIdx(head, len, N, err)    csnip_ringbuf__PopTailIdx((head), (len), (N), (err))
	Remove an element from the tail.
#define	csnip_ringbuf_IsFull(head, len, N)   ((len) == (N))
	Check whether a ringbuffer is full. More...
#define	csnip_ringbuf_IsEmpty(head, len, N)   ((len) == 0)
	Check whether a ringbuffer is empty. More...
#define	csnip_ringbuf_CheckIdx(head, len, N, idx, err)    csnip_ringbuf__CheckIdx((head), (len), (N), (idx), (err))
	Check whether a given index is valid. More...
#define	csnip_ringbuf_AddWrap(N, amount, idx)
	Compute the sum idx + amount with cyclic wrap. More...
#define	csnip_ringbuf_AddWrapSet(N, amount, idx)
	Compute idx += amount. More...
#define	csnip_ringbuf_SubWrap(N, amount, idx)
	Compute idx - amount with cyclic wrap. More...
#define	csnip_ringbuf_SubWrapSet(N, amount, idx)
	Compute idx -= amount with cyclic wrap. More...
#define	csnip_ringbuf_PushHead(head, len, N, arr, val, err)
	Add an element to the head. More...
#define	csnip_ringbuf_PopHead(head, len, N, arr, ret, err)
	Remove an element from the head. More...
#define	csnip_ringbuf_PushTail(head, len, N, arr, val, err)
	Add an element to the tail. More...
#define	csnip_ringbuf_PopTail(head, len, N, arr, ret, err)
	Remove an element from the tail. More...
#define	CSNIP_RINGBUF_DECL_IDX_FUNCS(scope, prefix, idx_type, gen_args)
	Generator macro to declare index functions. More...
#define	CSNIP_RINGBUF_DECL_VAL_FUNCS(scope, prefix, val_type, gen_args)
	Declare value functions. More...
#define	CSNIP_RINGBUF_DEF_IDX_FUNCS(scope, prefix, idx_type, gen_args, head, len, N, err)
	Define Ringbuffer index functions. More...
#define	CSNIP_RINGBUF_DEF_VAL_FUNCS(scope, prefix, val_type, gen_args, head, len, N, arr, err)
	Define Ringbuffer value functions. More...

Detailed Description

This module provides a simple ring buffer. That is to say, it provides two indices, head and tail, that wrap around at the end of the array. The following illustrates a ring buffer with elements X, Y and Z from head to tail.

    ,---------------------------.
    |  ...  | X | Y | Z |  ...  |
    `---------------------------'
              ^       ^          ^
              head    tail       N (capacity)

The ring buffer can wrap around at the edges, thus the following picture gives a ring buffer with the same entries in the same order as above:

    ,---------------------------.
    | Y | Z |    ...        | X |
    `---------------------------'
          ^                   ^  ^
          tail             head  N (capacity)

Ring buffers are represented with three integers: head, len and N: head is the location of the head of the buffer in the backing array, len is the number of members, and N is the size of the backing array. Thus 0 <= head < N and 0 <= len <= N . The value N is read only.

Elements can be added (pushed) or removed (popped) from either end, head or tail. Thus, ring buffers provide essentially the functionality of a deque of fixed capacity. The fixed size of the backing array has an important advantage: inserted elements will have a fixed location in the backing array for their entire lifetime. This allows updating specific elements of the ring buffer after they were added.

There are three families of macros or functions provided, the index macros, including csnip_ringbuf_Init(), which operate exclusively on backing array indices; those generally have names ending in Idx. Then there are the index arithmetic macros which perform simple index arithmetic mod N in a safe way; they have "Wrap" in their name. Finally there are the value macros, which do access the backing array as well.

Comment. The alert user may wonder whether it is really neccessary to implement the Idx macros as macros, or whether they should have been functions; they don't really need template-esque properties. It is the case, however, that it's fashionable, these days, to use size_t to loop over array indices. I personally think that doing so is unwise and there are important reasons to stick to int in almost all cases.

Using macros allows the use of size_t if it is preferred or necessary, but allows the use of int in all other cases.

Why do I not like size_t as array index?

1. It is ugly, though not quite as ugly as std::vector<mytype>::size_type.
2. It has interesting problems due to its unsigned nature, chiefly the following doesn't work:

   for (size_t i = N - 1; i >= 0; --i) { ... }

3. I've seen it affect performance (program speed) quite dramatically in some cases.

In the vast majority of cases, it is known that int will be large enough as array index, and for those cases, I recommend sticking to it.

Macro Definition Documentation

csnip_ringbuf_AddWrap

#define csnip_ringbuf_AddWrap	(		N,
			amount,
			idx
	)

Value:

    ((amount) >= 0 ? csnip_ringbuf__AddWrap((N), (amount), (idx)) \
        : csnip_ringbuf__SubWrap((N), -(amount), (idx)))

Expression macro. Increases idx by amount, wrapping around at the array boundary. Thus, this is similar to computing

(idx + amount) % N

with the exceptions that possible overflow is handled correctly, and that the amount can be negative. (However, the allowable range for base and amount is restricted as described below.)

Increasing the index by a positive amount corresponds to moving toward the tail.

Parameters

[in]	N	the modulus, i.e., the size of the backing array.
[in]	amount	the number of entries to advance base. Needs to be in the range -N < amount < N.
[in]	idx	the index to advance from. Needs to be in the range 0 <= idx < N.

csnip_ringbuf_AddWrapSet

#define csnip_ringbuf_AddWrapSet	(		N,
			amount,
			idx
	)

Value:

    ((amount) >= 0 ? csnip_ringbuf__AddWrapSet((N), (amount), (idx)) \
        : csnip_ringbuf__SubWrapSet((N), -(amount), (idx)))

Expression Macro. Similar to csnip_ringbuf_AddWrap(), except the result is assigned to idx.

csnip_ringbuf_CheckIdx

#define csnip_ringbuf_CheckIdx	(		head,
			len,
			N,
			idx,
			err
	)		csnip_ringbuf__CheckIdx((head), (len), (N), (idx), (err))

Checks whether a given index points to within the ring buffer as currently occupied. A range error is raised if this is not the case; otherwise nothing happens.

CSNIP_RINGBUF_DECL_IDX_FUNCS

#define CSNIP_RINGBUF_DECL_IDX_FUNCS	(		scope,
			prefix,
			idx_type,
			gen_args
	)

Parameters

scope	Scope in which the functions are declared.
prefix	Prefix to the name of the functions declared.
idx_type	Type used for indexing.
gen_args	Generic argument list.

For details,

See also

CSNIP_RINGBUF_DEF_IDX_FUNCS().

CSNIP_RINGBUF_DECL_VAL_FUNCS

#define CSNIP_RINGBUF_DECL_VAL_FUNCS	(		scope,
			prefix,
			val_type,
			gen_args
	)

Generator macro to declare value functions.

Parameters

scope	function scope.
prefix	function name prefix.
val_type	ringbuffer value type.
gen_args	generic arguments to pass to the ringbuffer functions.

For details,

See also

CSNIP_RINGBUF_DEF_VAL_FUNCS().

CSNIP_RINGBUF_DEF_IDX_FUNCS

#define CSNIP_RINGBUF_DEF_IDX_FUNCS	(		scope,
			prefix,
			idx_type,
			gen_args,
			head,
			len,
			N,
			err
	)

Generator macro to define the index computation functions for a ring buffer.

Parameters

scope	Function scope.
prefix	Function name prefixes for the defined functions.
idx_type	Type used for indexing; common choices are int or size_t.
gen_args	General argument list (function prototype).
head	The head variable of the ring buffer; can be a function of the gen_args arguments.
len	The number of members currently contained in the ring buffer; can be a function of the gen_args arguments
N	The size of the ring buffer, can be a function of the gen_args arguments.
err	The error return value; can be a function of the gen_args arguments.

The following functions are defined:

• void init(gen_args): Zero-initialize the indices.

  See also

  csnip_ringbuf_Init()

• size_t get_head_idx(gen_args): Get the head index.

  See also

  csnip_ringbuf_GetHeadIdx()

• size_t get_tail_idx(gen_args): Get the tail index.

  See also

  csnip_ringbuf_GetTailIdx()

• void push_head_idx(gen_args): Push to the head.

  See also

  csnip_ringbuf_PushHeadIdx()

• void pop_head_idx(gen_args): Pop from the head.

  See also

  csnip_ringbuf_PopHeadIdx()

• void push_tail_idx(gen_args): Push to the tail.

  See also

  csnip_ringbuf_PushTailIdx()

• void pop_tail_idx(gen_args): Pop from the tail; wraps.

  See also

  csnip_ringbuf_PopTailIdx()

• int is_full(gen_args): Check if ringbuffer is full.

  See also

  csnip_ringbuf_IsFull()

• int is_empty(gen_args): Check if ringbuffer is empty.

  See also

  csnip_ringbuf_IsEmpty()

• void check_idx(gen_args, idx_type i): Check if the index i points to within a currently occupied slot of the ring buffer.

  See also

  csnip_ringbuf_CheckIdx()

• idx_type add_wrap(gen_args, idx_type off, idx_type i): Add off to i modulo N.

  See also

  csnip_ringbuf_AddWrap()

• idx_type sub_wrap(gen_args, idx_type off, idx_type i): Add off from i modulo N.

  See also

  csnip_ringbuf_SubWrap()

CSNIP_RINGBUF_DEF_VAL_FUNCS

#define CSNIP_RINGBUF_DEF_VAL_FUNCS	(		scope,
			prefix,
			val_type,
			gen_args,
			head,
			len,
			N,
			arr,
			err
	)

Generator macro to define ringbuffer value functions. The functions defined are:

• void push_head(gen_args, val);
• val_type pop_head(gen_args, val);
• void push_tail(gen_args, val);
• val_type pop_tail(gen_args);

csnip_ringbuf_GetHeadIdx

#define csnip_ringbuf_GetHeadIdx	(		head,
			len,
			N,
			ret,
			err
	)

This macro computes the array index of the current head in the backing array. If the ring buffer is empty, csnip_err_UNDERFLOW is raised.

Thus, save for checking whether the ring buffer is empty, this macro simply sets ret to head.

Parameters

head	index to head element in ring buffer.
len	amount of data filled into ring buffer.
N	ring buffer array size.
ret	l-value to assign the computed index.
err	error return.

csnip_ringbuf_GetTailIdx

#define csnip_ringbuf_GetTailIdx	(		head,
			len,
			N,
			ret,
			err
	)		csnip_ringbuf__GetTailIdx((head), (len), (N), (ret), (err))

This macro computes the array index of the current tail in the backing array. If the ring buffer is empty, csnip_err_UNDERFLOW is raised.

Thus, for non-empty ring buffers, this computes (head + len - 1) mod N in the range 0, ..., N - 1.

csnip_ringbuf_Init

#define csnip_ringbuf_Init	(		head,
			len,
			N
	)

Sets the head and length of the ring buffer to 0. Note that the capacity value N is not initialized. (Not all ring buffers allow for the N parameter to be set, e.g. it may be a compile time constant.)

csnip_ringbuf_IsEmpty

#define csnip_ringbuf_IsEmpty	(		head,
			len,
			N
	)		((len) == 0)

Expression macro to check whether a ringbuffer is empty, i.e., whether it contains 0 elements.

csnip_ringbuf_IsFull

#define csnip_ringbuf_IsFull	(		head,
			len,
			N
	)		((len) == (N))

Expression macro to check whether a ringbuffer is full, i.e., whether there is no space to insert another element into it.

csnip_ringbuf_PopHead

#define csnip_ringbuf_PopHead	(		head,
			len,
			N,
			arr,
			ret,
			err
	)

Like csnip_ringbuf_PopHeadIdx, except that the removed head element is assigned to ret .

csnip_ringbuf_PopTail

#define csnip_ringbuf_PopTail	(		head,
			len,
			N,
			arr,
			ret,
			err
	)

Like csnip_ringbuf_PopHead(), except that it's acting on the tail.

csnip_ringbuf_PushHead

#define csnip_ringbuf_PushHead	(		head,
			len,
			N,
			arr,
			val,
			err
	)

This is a value-version of csnip_ringbuf_PushHeadIdx which also performs the assignment of val to the new head location of the backing array arr.

csnip_ringbuf_PushHeadIdx

#define csnip_ringbuf_PushHeadIdx	(		head,
			len,
			N,
			err
	)		csnip_ringbuf__PushHeadIdx((head), (len), (N), (err))

This changes head and len as if an element had been added to the buffer at the head. Since this is an index function, it does not actually add any element, only update the pointers/indices. In other works, the macro "makes space" for an element that can be added by assigning to the new head index in the backing array.

Possible errors include csnip_err_NOMEM, for when the ring buffer is full.

csnip_ringbuf_PushTail

#define csnip_ringbuf_PushTail	(		head,
			len,
			N,
			arr,
			val,
			err
	)

Like csnip_ringbuf_PushHead(), but for the tail.

csnip_ringbuf_PushTailIdx

#define csnip_ringbuf_PushTailIdx	(		head,
			len,
			N,
			err
	)		csnip_ringbuf__PushTailIdx((head), (len), (N), (err))

Similar to csnip_ringbuf_PushHeadIdx() but adding at the tail.

csnip_ringbuf_SubWrap

#define csnip_ringbuf_SubWrap	(		N,
			amount,
			idx
	)

Value:

    ((amount) >= 0 ? csnip_ringbuf__SubWrap((N), (amount), (idx)) \
        : csnip_ringbuf__AddWrap((N), -(amount), (idx)))

Expression macro. Subtracts amount from amount, wrapping around at the array boundary. Thus, this is similar to computing

(idx - amount + N) % N

with the exceptions that possible overflow is handled correctly. (However, the allowable range for base and amount is restricted as described below.)

Decreasing the index amount by a positive amount results in a move toward the head.

Parameters

[in]	N	size of the ring buffer
[in]	amount	the number of entries to subtract from idx. Needs to be in the range -N < amount < N.
[in]	idx	the index to advance from. Needs to be in the range 0 <= idx < N.

csnip_ringbuf_SubWrapSet

#define csnip_ringbuf_SubWrapSet	(		N,
			amount,
			idx
	)

Value:

    ((amount) >= 0 ? csnip_ringbuf__SubWrapSet((N), (amount), (idx)) \
        : csnip_ringbuf__AddWrapSet((N), -(amount), (idx)sebase))

Expression Macro. Similar to csnip_ringbuf_SubWtap(), except that the result is assigned to idx.