TransWikia.com

Double-ended queue for Embedded Systems with different data size

Code Review Asked by MrBit on February 14, 2021

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);

2 Answers

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.

Correct answer by Lundin on February 14, 2021

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

Answered by Abhay Aravinda on February 14, 2021

Add your own answers!

Ask a Question

Get help from others!

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP