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);
}
queuePeek()know how much data you copied? \$\endgroup\$datapointer always allocated as 256 bytes ? \$\endgroup\$