5
\$\begingroup\$

I'm working on creating a queue to hold variable sized data buffers up to 256 bytes in length, however most often the buffers will be much smaller (typically around 10-15 bytes).

To avoid the wasted memory I attempted to create a queue based on a linked list with variable sized dynamically allocated items the size of which is stored in each node.

I've never done something like this before so I'm hoping someone could take a look to see if what I've done makes sense.

Note: There's a queueTest at the bottom of queue.c that shows how I'm using this.

queue.h

/* Define to prevent recursive inclusion -------------------------------------*/
#ifndef __SB_QUEUE_H
#define __SB_QUEUE_H

#ifdef __cplusplus
 extern "C" {
#endif

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

#define QUEUE_CAPACITY_BYTES 1000

/* Node structure including data length */
typedef struct node {
    uint8_t     *data;
    uint8_t     size;
    struct node *next;
} node_t;


/* Queue structure */
typedef struct myque {
    node_t   *head;
    node_t   *tail;
    uint16_t size;
    uint16_t footprint;
} myque_t; 


void    queueInitialize ( myque_t * q );
int     queuePush       ( myque_t * q, const void * data, uint8_t dataLen );
int     queuePop        ( myque_t * q, uint8_t * data );
void    queuePeek       ( const myque_t * q, uint8_t * data );
bool    queueIsFull     ( myque_t * q );
uint8_t queueGetSize    ( myque_t * q );
void    queueClear      ( myque_t * q );

void queueTest ( void );
void queuePrint ( myque_t * q );

#ifdef __cplusplus
}
#endif
#endif /* __SB_QUEUE_H */

queue.c

/* Includes ------------------------------------------------------------------*/
#include "sb_queue.h"

#include <stdlib.h>
#include <string.h>

/**@brief Initializes a queue
 * @details Sets the read and write pointers to NULL, and initializes the size as 0
 *
 * @param[in]  q - pointer to queue to initialize
 * @param[in]  capacity - number of elements in the queue
 */
void queueInitialize(myque_t * q)
{
    q->size = 0;
    q->footprint = 0;
    q->head = NULL;
    q->tail = NULL;
}

/**@brief Pushes a data buffer to the queue
 * @details Allocates space for a new node, and a variable length data buffer and pushes
 *          it to the specified queue
 *
 * @param[in]  q - pointer to queue to push to
 * @param[in]  data - pointer to data to be pushed
 * @param[in]  dataLen - number of bytes in data buffer
 */
int queuePush(myque_t *q, const void *data, uint8_t dataLen)
{
    /* Check that data will fit */
    if (q->footprint + (dataLen * sizeof(uint8_t)) > QUEUE_CAPACITY_BYTES)
    {
        return -1;
    }
    else
    {  
        /* Allocate memory for node */
        node_t *newNode = (node_t *)malloc(sizeof(node_t));

        if(newNode == NULL)
        {
            return -1;
        }

        /* Allocate memory for data */
        newNode->data = malloc(dataLen * sizeof(uint8_t));

        if(newNode->data == NULL)
        {
            free(newNode);
            return -1;
        }

        newNode->size = dataLen;
        newNode->next = NULL;

        memcpy(newNode->data, data, newNode->size);

        if(q->size == 0)
        {
            q->head = q->tail = newNode;
        }
        else
        {
            q->tail->next = newNode;
            q->tail = newNode;
        }

        q->size++;
        q->footprint+= dataLen * sizeof(uint8_t);
        //queuePrint(q);
        return 0;
    }
}


/**@brief Remove an item from the queue. Changes the front of queue
 * 
 * @param[in]  queue - pointer to the queue to pop from
 * @param[in]  data - pointer to where to store the item
 */
int queuePop(myque_t * q, uint8_t * data)
{
    if(q->size > 0)
    {
        node_t *tempNode = q->head;

        if (data != NULL)
        {
            memcpy(data, tempNode->data, tempNode->size);
        }

        if(q->size > 1)
        {
            q->head = q->head->next;
        }
        else
        {
            q->head = NULL;
            q->tail = NULL;
        }

        q->size--;
        free(tempNode->data);
        free(tempNode);

        return 0;
    }
    else
    {
        return -1;
    }
}

/**@brief Inspect the item at the head of the queue without altering the queue
 * 
 * @param[in]  queue - pointer to the queue to inspect
 * @param[in]  data - pointer to where to store the item
 */
void queuePeek(const myque_t *q, uint8_t *data)
{
    if(q->size > 0)
    {
       node_t *tempNode = q->head;
       memcpy(data, tempNode->data, tempNode->size);
    }
}

/**@brief Frees all the memory used by the queue
 * 
 * @param[in]  queue - pointer to the queue to free
 */
void queueClear(myque_t *q)
{
  node_t * tempNode;

  while(q->size > 0)
  {
      tempNode = q->head;
      q->head  = tempNode->next;
      free(tempNode->data);
      free(tempNode);
      q->size--;
  }

  q->head = q->tail = NULL;
}

/**@brief Returns true if the queue is empty. The queue is full when it's size is 0
 * 
 * @param[in]  queue - pointer to the queue to check
 *
 * @return Whether or not the queue is empty
 */
uint8_t queueGetSize( myque_t * q )
{  
    return q->size;
}

/**@brief Prints the contents of the queue
 * 
 * @param[in]  queue - pointer to the queue to print
 */
void queuePrint ( myque_t * q )
{
    uint8_t ii = 0;
    uint8_t pp = 0;
    node_t * tempNode = q->head;

    while(ii < q->size)
    {
        printf("Queue %d: ", ii);
        for (pp = 0; pp < tempNode->size; pp++)
        {
            printf("0x%x, ", tempNode->data[pp]);
        }
        printf("\r\n");
        tempNode = tempNode->next;
        ii++;
    }
}


/**@brief Prints the contents of the queue
 * 
 * @param[in]  queue - pointer to the queue to print
 */
void queueTest ( void )
{
    uint8_t ii = 0;
    uint8_t pp = 0;
    myque_t q;
    uint8_t data[10] = {0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 0x08, 0x09};

    queueInitialize(&q);

    /* Fill queue (should stop pushing at around 100) */
    for (ii = 0; ii < 120; ii++)
    {
        queuePush(&q, data, 10);
        for (pp = 0; pp < 10; pp++)
        {
            data[pp]++;
        }
    }

    queuePrint(&q);
    printf("\r\nCLEAR QUEUE\r\n");
    queueClear(&q);
    queuePrint(&q);
}
\$\endgroup\$
3
  • \$\begingroup\$ Why does the queue have a max capacity of 1000 when it is really only limited by how much memory you can malloc? Also, how does the caller of queuePeek() know how much data you copied? \$\endgroup\$
    – JS1
    Feb 8, 2018 at 21:18
  • \$\begingroup\$ The capacity of 1000 is arbitrary right now, but this is running on a small microcontroller so the heap will be limited. The data length is actually encoded in the message itself so I haven't run into that issue but that's a good point about the peek function. \$\endgroup\$
    – Otus
    Feb 8, 2018 at 21:56
  • \$\begingroup\$ Is the passed in data pointer always allocated as 256 bytes ? \$\endgroup\$ Feb 8, 2018 at 22:56

2 Answers 2

3
\$\begingroup\$

Overall looks pretty reasonable, i'm missing the queueIsFull() implementation. I didn't try to compile

Use of bool

You're using bool only in one function, other functions indicate success via int values, be consistent.

queuePush()

When calculating the footprint you're ignoring the size of the next ptr in your calculation, if you're on a system that is that tight that you are limiting the size of the queue to basically 1KB then you probably want to include this in the footprint calculation.

queuePop()

There is a big assumption in this that expects the data pointer to be able to be big enough to take the amount of data available, and as JS1 pointed out you for queuePeek() the caller doesn't know how much data was copied. I don't know about the environment that you are using this in, but as you are deallocating the data pointer in the node, you might save that allocation at this point and just return it. This makes it the responsibility of the caller to release it but it might save you an allocation for the one that is passed into pop.

queuePeek()

As written, no check for going out of bounds on the data that is written to. As above no response on how much data was available.

Tests

Your tests only allow for a 'visual' check, ideally you should be able to test your queue through unit tests with specific assumptions and checks against these assumptions. assert works very well for that.

Niggle ...

  • The queue.size and data.size fields while having the same name indicate different kinds of sizes, one is a count, the other is an amount of memory ...

  • myque_thas a typo in it, also is not really an ideal structure name, fixed_capacity_queue or something else might be more helpful and give you a little bit of reusability.

  • The node structure should probably be private in the implementation there is no need to put it in the include file

  • queueClear() could be written without updating size, just check on head != NULL

  • queueGetSize() is not really very useful, you do have access to the structure or ?

Suggestions

You are trying to optimize the storage size, at the cost of allocations, i am assuming you have looked at the amounts that you have/need and decided that this is a necessary step. By itself the this looks fine, you'll have to be the judge of whether it actually does what you think it should accomplish.

You could introduce a buffer structure just to carry the data and size pairs, this might make peek and pop more clear, but there probably would always be a difference between the allocated amount from the pointer passed in and the actual written amount. Unless the amount of reserved memory is fixed.

You could implement this as a circular buffer on a fixed amount of memory. This might have some advantages depending on your needs. If you are low on memory you might want to save on allocations as well.

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

Information hiding

The typedef struct node { .... } node_t and typedef struct node { ... } node_t; are not needed in "queue.h".

typedef struct myque *myque_t; is sufficient for "queue.h". The complete typedefs below in "queue.c".


To avoid the wasted memory

A .head and .tail member are not both needed for a circular queue. One is enough.

This may be advanced for a someone who "never done something like this before".

Although conceptually the .head and .tail works wells, code can get by with only .tail and have .tail->next point to the "head" node.

With an empty queue, .tail == NULL. With an N > 0 item queue, the last node points to the first, even if it is itself. The end of the list is determined by node->next == q->tail->next rather than NULL compare.

This approach reduces the memory need by one pointer/queue.

In realizing this code, I have found it to be the same speed or a bit slower. This approach is most useful in reducing memory when there are large count of queues, perhaps many empty ones, in a program run.


Other memory reductions possible too.


const

const missing? I'd expect the following signature instead.

// bool    queueIsFull (myque_t * q);
// uint8_t queueGetSize(myque_t * q);
bool    queueIsFull (const myque_t * q);
uint8_t queueGetSize(const myque_t * q);

Missing include

As "queue.h" uses uint8_t, add #include <stdint.h>


Types

Better to use size_t for sizes and void * for user data. To be clear: design the interface (function signatures) in ways that make most sense for the user. Code the structure members as you see fit. Perhaps a size for this queue can only be 255, still use size_t dataLen and test that for a valid range. int queuePush() has a nice way to return error indications.

// int queuePush( myque_t * q, const void * data, uint8_t dataLen );
// int queuePop( myque_t * q, uint8_t * data );
int queuePush( myque_t * q, const void * data, size_t dataLen);
int queuePop( myque_t * q, void * data );

Overflow

Overflow possible. q->size++; may overflow uint8_t. Try calling int queuePush(q, "", 1) 256 times.


Other

I'd expect queueGetSize to return unsigned of size_t, even if the .size member was a narrower type.

\$\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.