2
\$\begingroup\$

I decided to modify my last code about a queue intended for embedded systems and make it accept different data types for multiple purposes.

It is a double-ended queue, the user can store and get elements to and from each end of the queue . The queue uses a static allocated buffer - array. The user must pass the size of the array to the queue during the initialization and the size of each element.

My intention is to use the same piece of code for making queue that can hold bytes and structs too (not in the same queue!).

So here's the header file.

#ifndef QUEUE_H
#define QUEUE_H

#include <inttypes.h>
#include <stdbool.h>

struct queue
{
    void * data_buf;
    void * front;
    void * back;
    const uint16_t elements_num_max;
    const uint16_t elements_size;
    uint16_t elements;
};

void queue_init(struct queue * queue);

bool queue_is_full(struct queue * queue);

bool queue_is_empty(struct queue * queue);

bool queue_add_front(struct queue * queue, void * data);

bool queue_add_back(struct queue * queue, void * data);

bool queue_get_front(struct queue * queue, void * data);

bool queue_get_back(struct queue * queue, void * data);

#endif

and the source code.

/**
 * \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"


#define INCREASE_INDEX(queue, ptr)      queue->ptr = (queue->ptr + queue->elements_size) >= (queue->data_buf + queue->elements_num_max * queue->elements_size) ? queue->data_buf : (queue->ptr + queue->elements_size)
#define DECREASE_INDEX(queue, ptr)      queue->ptr = (queue->ptr - queue->elements_size) < queue->data_buf ? (queue->data_buf + (queue->elements_num_max - 1) * queue->elements_size) : (queue->ptr - queue->elements_size)


/**
 * Initializes - resets the queue.
*/
void queue_init(struct queue * queue)
{
    memset((uint8_t *)queue->data_buf, 0, queue->elements_num_max * queue->elements_size);
    
    queue->back = queue->data_buf;
    queue->front = queue->data_buf;
    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->elements_num_max);
}

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

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

    if (queue_is_empty(queue) == false)
    {
        INCREASE_INDEX(queue, front);
    }

    memcpy((uint8_t *)queue->front, (uint8_t *)data, queue->elements_size);
    queue->elements++;
    return true;
}

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

    if (queue_is_empty(queue) == false)
    {
        DECREASE_INDEX(queue, back);
    }

    memcpy((uint8_t *)queue->back, (uint8_t *)data, queue->elements_size);
    queue->elements++;
    return true;    
}

/**
 * Reads one element from the front of the queue.
 * 
 * \returns false if the queue is empty.
*/
bool queue_get_front(struct queue * queue, 
                     void * data)
{
    if (queue_is_empty(queue))
    {
        return false;
    }
    
    memcpy((uint8_t *)data, (uint8_t *)queue->front, queue->elements_size);
    if (queue->front != queue->back)
    {
        DECREASE_INDEX(queue, front);
    }
    queue->elements--;
    return true;
}

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

    memcpy((uint8_t *)data, (uint8_t *)queue->back, queue->elements_size);
    if (queue->front != queue->back)
    {
        INCREASE_INDEX(queue, back);
    }
    queue->elements--;
    return true;
}

How to use it:

#define ELEMENTS    100

MyStruct_t struct_buff[ELEMENTS];

struct queue my_queue = 
{
    .data_buf = struct_buff,
    .elements_num_max = ELEMENTS.
    .elements_size = sizeof(MyStruct_t),
};

queue_init(&my_queue);
\$\endgroup\$
4
  • 2
    \$\begingroup\$ The current implementation is NOT interrupt safe - why not? Is there some global state I'm not seeing? \$\endgroup\$ – Reinderien Nov 1 '20 at 14:05
  • \$\begingroup\$ @Reinderien The code I posted is based on an old implementation I posted before. You can see the detailed explanation here codereview.stackexchange.com/a/245318/155837 about why it is not interrupt safe. \$\endgroup\$ – MrBit Nov 1 '20 at 16:59
  • 1
    \$\begingroup\$ @Reinderien The entire queue state is kind of global. Consider the mainline code and ISR try to operate on the same queue. \$\endgroup\$ – vnp Nov 1 '20 at 17:33
  • \$\begingroup\$ I'm using the latest release of Visual Studio 2019, not the best C compiler in the world. To get the 2 macros in queue.c to compile I had to cast all of the queue->front, queue->back and queue->data_buf pointers to unsigned. Apparently the VC compiler doesn't think void pointers are complete objects. \$\endgroup\$ – pacmaninbw Nov 2 '20 at 2:16
1
\$\begingroup\$

Couple of bugs:

  • queue.c doesn't #include <string.h>.
  • Casting the pointer parameters passed to memset and memcpy isn't necessary, but can hide bugs.
  • Your macros do non-standard pointer arithmetic on void pointers. Don't do that, there's no need to use such pointless non-standard extensions and they are very unlikey to be supported by embedded systems compilers. Use uint8_t* instead.

Overall, make sure you are compiling with a standard C compiler and not a non-standard C++ compiler.

\$\endgroup\$
1
\$\begingroup\$

In queue_init, there's no need to initialize all elements to zero. On the same note, the queue is being partially initialized outside queue_init() and partially within it. You might consider passing buffer, size and maximum elements as parameters to the function or getting rid of it altogether

You can shorten queue_is_full(queue)==false to !queue_is_full(queue) and return (queue->elements==0); to return !(queue->elements);

Also, you could consider renaming the macro to something like INCREASE_INDEX_CYCLICALLY to indicate the two end of array are connected

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.