Double-ended queue for Embedded Systems

Question

Following my previous question about a FIFO for embedded systems and the very detailed answer I got, I made some modifications to convert a simple FIFO to double-ended queue for Embedded Systems. It is using a circular buffer.

How it works: When an element is added and the queue is not empty, the corresponding index is increased or decreased according to the side the element is added. When the queue is empty, and an element is added, neither index is changed so that the element can be accessed from either side. The size of the queue is constant and it must be defined at compile time. The data pointer must point to a static array that is also defined at compile time with the same size.

So here it is:

queue.h

#ifndef QUEUE_H
#define QUEUE_H

#include <inttypes.h>

typedef uint16_t QueueDataType_t;

struct queue
{
    QueueDataType_t * data;
    QueueDataType_t front_idx;
    QueueDataType_t back_idx;
    const QueueDataType_t size;
    QueueDataType_t elements;
};

#endif

queue.c

/**
 * \file queue.c
 *
 * \brief   A double-ended queue (deque). Elements can be added or removed from
 *          either the front or the back side.
 * \warning The current implementation is NOT interrupt safe. Make sure interrupts
 *          are disabled before access the QUEUE otherwise the program might yield
 *          unexpected results.
*/

#include "queue.h"
#include <stdbool.h>


/**
 * Initializes - resets the queue.
*/
void queue_init(struct queue * queue)
{
    memset(queue->data, 0, queue->size);
    queue->back_idx = 0;
    queue->front_idx = 0;
    queue->elements = 0;
}

/**
 * Checks if queue is full.
 * 
 * \returns true if queue is full.
*/
bool queue_is_full(struct queue * queue)
{
    return (queue->elements == queue->size);
}

/**
 * Checks if queue is empty
 * 
 * \returns true if queue is empty.
*/
bool queue_is_empty(struct queue * queue)
{
    return (queue->elements == 0);
}

/**
 * Adds one byte to the front of the queue. 
 * 
 * \returns false if the queue is full. 
*/
bool queue_add_front(struct queue * queue, 
                     QueueDataType_t data)
{
    if (queue_is_full(queue))
    {
        return 0;
    }

    if (queue_is_empty(queue) == 0)
    {
        queue->front_idx = (queue->front_idx + 1) >= queue->size ? 0 : (queue->front_idx + 1);
    }

    queue->data[queue->front_idx] = data;    
    queue->elements++;
    return 1;
}

/**
 * Adds one byte to the back of the queue.
 * 
 * \returns false if the queue is full. 
*/
bool queue_add_back(struct queue * queue, 
                    QueueDataType_t data)
{
    if (queue_is_full(queue))
    {
        return 0;
    }

    if (queue_is_empty(queue) == 0)
    {
        queue->back_idx = (queue->back_idx == 0) ? (queue->size - 1) : (queue->back_idx - 1);
    }

    queue->data[queue->back_idx] = data;
    queue->elements++;
    return 1;    
}

/**
 * Reads one byte from the front of the queue.
 * 
 * \returns false if the queue is empty.
*/
bool queue_get_front(struct queue * queue, 
                     QueueDataType_t * data)
{
    if (queue_is_empty(queue))
    {
        return 0;
    }
    
    *data = queue->data[queue->front_idx];
    queue->front_idx = (queue->front_idx == 0) ? (queue->size - 1) : (queue->front_idx - 1);
    queue->elements--;
    return 1;
}

/**
 * Reads one byte from the back of the queue.
 * 
 * \returns false if the queue is empty.
*/
bool queue_get_back(struct queue * queue, 
                    QueueDataType_t * data)
{
    if (queue_is_empty(queue))
    {
        return 0;
    }

    *data = queue->data[queue->back_idx];
    queue->back_idx = (queue->back_idx + 1) >= queue->size ? 0 : (queue->back_idx + 1);
    queue->elements--;
    return 1;
}

Initializing the queue

#define MY_QUEUE_DATA_SIZE  50
static QueueDataType_t q_data[MY_QUEUE_DATA_SIZE];
static struct queue my_queue =
{
    .data = q_data,
    .size = MY_QUEUE_DATA_SIZE,
};

queue_init(&my_queue);

Answer 1

For consistency with your use of the <stdbool.h> header and the bool macro, your functions that return a bool should use return true; or return false; instead of returning 0 or 1. There will be no difference in the code but it is easier for a person reading the code to recognize what the return is (and this would also align better with your function documentation where you say that it "returns false").

Also related to comments, the add and get functions say that they add or read "one byte" but, because QueueDataType_t is a 16 bit type, they add or read two bytes.

If supported in your tool chain, queue_is_full and queue_is_empty could take their parameters as const struct queue * queue since they do not make any chances to the queue.

There is a subtle bug when removing the last element from the queue. When a queue is initialized, and when the first element is added, the front_idx and back_idx values both refer to the same slot in the data array. However, when you remove this single element, you still change the idx variable, so the resulting empty queue has the front and back indexes referring to different slots. Then when you add a new element, the indexes are not changed so that this element isn't pointed to by both indexes. This can result in an incorrect value being returned when this elements are removed from the queue. The fix is to not change the idx value when removing the last element.

You can create a function to adjust the indexes forward or backward to avoid having similar and duplicated code. This could then use the % operator (instead of a conditional branch) if appropriate on your embedded system.