Inspired by the "bip buffer", I coded a fixed-size circular queue that uses two regions (two pairs of begin/end pointers) to account for the wrap-around.
The main goal of this design was to simplify the queue operations implementation, and in the case of `cqueue_size`, `cqueue_empty` and `cqueue_full` it happened.
However, `cqueue_pop` and `cqueue_push` are messy, and I am concerned that a bug may be hiding in those functions.
#pragma once
#include <stdbool.h>
#include <stddef.h>
#include <string.h>
// WARN: these macros are meant for internal use exclusively!
#define BUFFER_SIZE 8
#define BUFFER_BEGIN(pcq) ((pcq)->buffer)
#define BUFFER_END(pcq) ((pcq)->buffer + BUFFER_SIZE)
#define REGIONA_SIZE(pcq) ((pcq)->ra_end - (pcq)->ra_begin)
#define REGIONB_SIZE(pcq) ((pcq)->rb_end - (pcq)->rb_begin)
#define REGIONB_ACTIVATE(pcq) \
if ((pcq)->rb_begin == NULL && (pcq)->rb_end == NULL) { \
(pcq)->rb_begin = BUFFER_BEGIN(pcq); \
(pcq)->rb_end = BUFFER_BEGIN(pcq); \
} else (void)0
#define REGIONB_DEACTIVATE(pcq) if (true) { \
(pcq)->rb_begin = NULL; \
(pcq)->rb_end = NULL; \
} else (void)0
///
/// @brief Circular queue.
/// @details Circular queue with fixed capacity, with design inspired by the "bip buffer" (bipartite buffer).
/// This implementation attempts to simplify the code of the circular queue operations by
/// abstracting away the wrap-around as two regions in the internal buffer: RegionA and RegionB.
/// RegionA can begin anywhere in the InternalBuffer but only end at the InternalBuffer's end.
/// RegionB can only begin at the beginning of the InternalBuffer.
/// RegionB can only exist if RegionA has reached the end of the InternalBuffer (i.e. RegionA is full).
/// RegionB becomes the new RegionA when the old RegionA becomes empty.
/// @remarks At the cost of keeping two extra pointers for RegionB, the pseudocode is simplified thusly:
/// @remarks CQUEUE_EMPTY: RegionA.begin == RegionA.end
/// @remarks CQUEUE_FULL: RegionA.begin == RegionB.end || RegionA.size == InternalBuffer.size
/// @remarks CQUEUE_SIZE: (RegionA.end - RegionA.begin) + (RegionB.end - RegionB.begin)
///
typedef struct
{
char buffer[BUFFER_SIZE]; ///< The circular queue's byte buffer.
char *ra_begin; ///< RegionA beginning.
char *ra_end; ///< RegionA end.
char *rb_begin; ///< RegionB beginning.
char *rb_end; ///< RegionB end.
} cqueue_t;
// circular queue operations
static inline void cqueue_reset(cqueue_t *cq);
static inline char cqueue_pop(cqueue_t *cq);
static inline void cqueue_push(cqueue_t *cq, char c);
static inline size_t cqueue_size(const cqueue_t *cq);
static inline bool cqueue_empty(const cqueue_t *cq);
static inline bool cqueue_full(const cqueue_t *cq);
///
/// @brief Resets the circular queue `cq` to a default empty state.
/// @note The circular queue's internal buffer is cleared to 0.
/// @param [out] cq Pointer to the circular queue to be reset.
///
static inline void cqueue_reset(cqueue_t *cq)
{
memset(BUFFER_BEGIN(cq), 0, BUFFER_SIZE);
cq->ra_begin = BUFFER_BEGIN(cq);
cq->ra_end = BUFFER_BEGIN(cq);
REGIONB_DEACTIVATE(cq); // RegionB doesn't exist unless RegionA is full
}
///
/// @brief Pops the next byte from the circular queue `cq`.
/// @warning If the circular queue is empty, a spurious value of 0 will be "popped".
/// @param [in,out] cq Pointer to the circular queue to be changed.
/// @returns The value of the current top byte.
/// @retval 0 If the circular queue is empty.
///
static inline char cqueue_pop(cqueue_t *cq)
{
if (REGIONA_SIZE(cq) != 0) // does RegionA have some data?
{
// retrieve value of popped byte
const char r = *(cq->ra_begin)++;
if (REGIONA_SIZE(cq) == 0 && REGIONB_SIZE(cq) != 0) // is RegionA empty while RegionB isn't?
{
// RegionB becomes RegionA
cq->ra_begin = cq->rb_begin;
cq->ra_end = cq->rb_end;
REGIONB_DEACTIVATE(cq);
}
return r;
}
else // the circular queue is empty
return 0;
}
///
/// @brief Pushes the new byte `c` to the circular queue `cq`.
/// @warning If the circular queue is full, the new byte will overwrite the top byte.
/// @param [in,out] cq Pointer to the circular queue to be changed.
/// @param c Byte to be pushed.
///
static inline void cqueue_push(cqueue_t *cq, char c)
{
if (cqueue_full(cq)) // is the circular queue full?
{
// push to RegionB and overwrite the current top byte in RegionA
REGIONB_ACTIVATE(cq);
*(cq->rb_end)++ = c;
++cq->ra_begin;
if (cq->ra_begin == BUFFER_END(cq)) // is RegionA empty?
{
// RegionB becomes RegionA
cq->ra_begin = cq->rb_begin;
REGIONB_DEACTIVATE(cq);
}
}
else
if (cq->ra_end == BUFFER_END(cq)) // is RegionA full?
{
// push to RegionB
REGIONB_ACTIVATE(cq);
*(cq->rb_end)++ = c;
}
else // RegionA is not full
{
// push to RegionA
*(cq->ra_end)++ = c;
}
}
///
/// @brief Returns the size of the circular queue `cq`.
/// @param [in] cq Pointer to the circular queue to be analyzed.
/// @returns The size in bytes of the circular queue.
///
static inline size_t cqueue_size(const cqueue_t *cq)
{
return REGIONA_SIZE(cq) + REGIONB_SIZE(cq);
}
///
/// @brief Returns whether or not the circular queue `cq` is empty.
/// @param [in] cq Pointer to the circular queue to be analyzed.
/// @retval true If the circular queue is empty.
/// @retval false If the circular queue is not empty.
///
static inline bool cqueue_empty(const cqueue_t *cq)
{
// NOTE: if RegionA doesn't exist, neither does RegionB;
// this is why it's enough to check only the size of RegionA
// to determine if the circular queue is empty
return REGIONA_SIZE(cq) == 0;
}
///
/// @brief Returns whether or not the circular queue `cq` is full.
/// @param [in] cq Pointer to the circular queue to be analyzed.
/// @retval true If the circular queue is full.
/// @retval false If the circular queue is not full.
///
static inline bool cqueue_full(const cqueue_t *cq)
{
return cq->ra_begin == cq->rb_end || REGIONA_SIZE(cq) == BUFFER_SIZE;
}