Any ideas for a generic queue implementation that can have a variable size that can be allowed at compile time?

Question

I am using 3 different UARTs in my system. I defined a software buffer for RX data and TX data to be placed in.

/*! Queue Size for all UARTS. Defines the size of static memory allocated for
RX and TX Buffers. */
#define QUEUE_SIZE 300u

/*!
* \brief Arbitrary FIFO queue structure used to store RAW serial data
* \ingroup uart
*/
typedef struct
{
   uchar8_t x[QUEUE_SIZE];
   uint16_t head_index;
   uint16_t tail_index;
   uint16_t length;
} serial_queue_t;

I declare 6 instances of this structure - an RX and TX buffer for each of my UARTs.

Right now I have a generic method to pull a character from a UART or push a character to a UART.

/*!
* \brief Private method used to get and remove the next character in an
* arbitrary UART FIFO queue.
* \ingroup uart
* \param[in] *p_queue The queue to get data from
* \param[out] *p_pull The next character in the buffer. This will not be
* assigned if the character is unavailable.
* \returns TRUE if the next character is available, FALSE if that character is
* not available.
*
* \note This Function is Atomic
* If this function is executing and a UART ISR occurs which would recall this
* function before the tail index has been updated it could cause a memory
* leak/data loss. Therefore this function is not reentrant and must block
* interrupts.
*/
static bool_t uart_pull(serial_queue_t volatile * p_queue, uchar8_t * p_pull);

/*!
* \brief Private method to push a character onto an arbitrary UART queue.
* \ingroup uart
* \param[in,out] *p_queue The queue to push data onto.
* \param[in] push The next character in the buffer. This will not be assigned
* if the character is unavilable.
* \returns TRUE if the character was placed in the queue successfully, FALSE
* if the queue is full.
*
* \note This Function is Atomic
* If this function is executing and a UART ISR occurs which would recall this
* function before the head index has been updated it could cause a memory
* leak/data loss. Therefore this function is not reentrant and must block
* interrupts.
*/
static bool_t uart_push(serial_queue_t volatile * p_queue, uchar8_t push);

Now I need to change my implementation. I need to resize a few of the buffers to make them much larger so I can transmit bigger data frames. I also plan to downsize a few of the buffers to reclaim some of the space because 300 bytes is overkill for them. I am trying to come up with a clean way to do this so I can keep my implementation generic.

My best idea so far has been to simply define a couple of different structs with a different array defined in each of a different size, and then make the p_queue pointer void. I could add a parameter to each of these functions which could tell the function which UART buffer is being used so they will know which struct to use when dealing with the buffers, or add another field to the queue structure that stores the max_length of that queue, and relocate the max_length, head_index, and tail_index in front of the character array.

Anyone have any better ideas - because defining up to 6 different structures for pretty much the same thing isn't all that clean? I don't want to put the whole thing on the heap and allocate runtime either - I want the allocation to be handled by the linker at compile time.

Answer 1

I'm using the ring buffers from Adam Dunkels ContikiOS: http://contiki.sourceforge.net/docs/2.6/a01686.html

I had to modify them a bit to get what I wanted, but as a platform to build on, it is rock solid.

I've replaced int with int32_t from <stdint.h> etc. to make sure I have a portable implementation. Other than that, I don't think I've changed much. I am using that code on a variety of different processors with different word size, endianness etc. it Just Works (TM) :)

EDIT: After re-reading your question, are you sure you mean you want to change the size at compile time and not at run-time ? Compile time is easy, run-time usually means dynamic allocation or at least a common memory buffer with some homemade allocator.