Basic queue design and implementation

Question

In general, I'd love some comments on this basic queue using dynamic allocation. In particular, I want comments about whether this queue is good in embedded systems, for example say a a sensor network gateway, which has to queue up packets to be forwarded on say a UART.

I hear normally that mallocs are a bad idea for embedded, so what are the pitfalls in such a scenario?

One thing is, that malloc could return that it was unable to allocate the required memory. But what I thought was that if I did the calculation and I was reasonably certain that I definitely have MAX_QSIZE amount of memory available for the MAX_DATSIZE then realistically I shouldn't be able to see malloc fail. Is that a correct assumption?

I am rewriting the same code for a version with static array and no mallocs as well, so I'll try to analyze how both behave.

Thank you for your time.

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

#define MAX_QSIZE   100
#define MAX_DATSIZE     128

struct node{
    void *data;
    struct node *next;
};
typedef struct node node_t;

typedef struct queue_t {
    node_t *head;
    node_t *tail;
    int size;
} queue_t;

queue_t *q_init(void)
{
    queue_t *q = malloc(sizeof (*q));
    q->size = 0;
    q->head = q->tail = NULL;
}

int q_push(queue_t *q, const void *pdata, int bsize)
{
    if (q == NULL)
        return -1;
    if (q->size == MAX_QSIZE)
        return -2;
    if (bsize > MAX_DATSIZE)
        return -3;

    node_t *new = malloc(sizeof (*new));
    new->next = NULL;
    new->data = malloc(bsize);
    bzero(new->data, bsize);
    memcpy(new->data, pdata, bsize);

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

    return 0;
}

node_t *q_peek(queue_t *q)
{
    return q->head;
}

void q_pop(queue_t *q)
{
    if (q->size == 0)
        return;
    node_t *this = q->head;
    q->head = this->next;
    free(this);
    q->size--;
    if (q->size == 0)
        q->tail = NULL;
}

void freeq(queue_t *q)
{
    while (q->head != NULL) {
        node_t *t = q->head;
        q->head = t->next;
        free(t);
    }
    free(q);
}

void printq(queue_t *q)
{
    int i = 0;
    for (node_t *h = q->head; h != NULL; h = h->next) {
        printf("[%d] %s\n", i++, (char*)h->data);
    }
}

int main()
{
    char *test[] =
    {
        "January",
        "February",
        "Random"
    };
    int numtest = sizeof test / sizeof test[0];
    queue_t *nameq = q_init();
    for (int i = 0; i < numtest; i++) {
        q_push(nameq, test[i], strlen(test[i]));
    }
    printq(nameq);
    
    q_pop(nameq);
    printq(nameq);

    char *hname = (char*)(q_peek(nameq)->data);
    printf("head name = %s\n", hname);

    freeq(nameq);
    return 0;
}

Answer 1

BUG: q_init() doesn't return a value. Your compiler should have caught this; perhaps you're running without enough diagnostics turned on? (I think this requires a diagnostic, so perhaps you need a better compiler).

---

BUG: We forgot to copy the terminating null character!

for (int i = 0; i < numtest; i++) {
    q_push(nameq, test[i], strlen(test[i]));
}

That should be strlen(test[i])+1. This was quickly revealed by Valgrind.

---

Although you don't ever expect malloc() to fail, I think it's better to be in the habit of coding defensively. "Memory available" might be fragmented, and not available in big enough chunks, for instance. It's not hard to add the necessary tests, and it makes your code more re-usable, saving you much time in the longer term.

queue_t *q_init(void)
{
    queue_t *q = malloc(sizeof *q);
    if (q) {
        q->size = 0;
        q->head = q->tail = NULL;
    }
    return q;
}

---

bzero() isn't standard (i.e. portable) C. Use memset() instead. Actually, just remove that call entirely, as it's immediately followed by a memcpy() that completely overwrites it, making the bzero() a dead store.

---

We don't need to cast here:

    printf("[%d] %s\n", i++, (char*)h->data);

char *hname = (char*)(q_peek(nameq)->data);

data is a pointer to void, which can be assigned to any pointer type in C:

    printf("[%d] %s\n", i++, h->data);

const char *hname = q_peek(nameq)->data;

---

We've included <stdint.h> but then seemingly ignored it. I would normally use size_t for the queue length and element sizes. I certainly wouldn't use a signed type such as int.

---

Naming: why freeq() and not q_free() to match the other functions?

---

When pushing a value, we allocate twice, but q_pop() and freeq() don't release the value storage, only the queue node. So we have a memory leak:

==4943== 
==4943== 21 bytes in 3 blocks are definitely lost in loss record 1 of 1
==4943==    at 0x480B77F: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==4943==    by 0x10922B: q_push (254594.c:40)
==4943==    by 0x10942E: main (254594.c:100)

We can fix this by adding another free() before the one that releases the node object. But a more elegant fix is to allocate just once, for the node and stored value together:

node_t *new = malloc(sizeof *new + bsize);
if (!new) {
    return ENOMEM;
}
new->next = NULL;
new->data = (char*)(new + 1);
memcpy(new->data, pdata, bsize);

We don't really need the data member any more - the value is always at the same offset from the node pointer.

---

The interface can be improved - users shouldn't need to know about node_t. Instead, just return pointer to the data member.

---

Modified code

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

#define MAX_QSIZE   100
#define MAX_DATSIZE 128

typedef struct node {
    struct node *next;
    char data[];               /* flexible array member */
} node_t;

typedef struct queue_t {
    node_t *head;
    node_t *tail;
    size_t size;                /* element count */
} queue_t;

queue_t *q_init(void)
{
    queue_t *q = malloc(sizeof *q);
    if (q) {
        q->size = 0;
        q->head = q->tail = NULL;
    }
    return q;
}

void *q_push(queue_t *q, const void *pdata, size_t bsize)
{
    if (!q || q->size == MAX_QSIZE || bsize > MAX_DATSIZE) {
        return NULL;
    }

    node_t *new = malloc(sizeof *new + bsize);
    if (!new) {
        return NULL;
    }
    new->next = NULL;
    memcpy(&new->data, pdata, bsize);

    if (q->head) {
        q->tail->next = new;
    } else {
        q->head = new;
    }
    q->tail = new;
    q->size++;

    return &new->data;
}

const void *q_peek(queue_t *q)
{
    if (!q || !q->head) { return NULL; }
    return &q->head->data;
}

void q_pop(queue_t *q)
{
    if (!q || !q->size) { return; }
    node_t *this = q->head;
    q->head = this->next;
    free(this);
    if (!--q->size) {
        q->tail = NULL;
    }
}

void q_free(queue_t *q)
{
    if (!q) { return; }
    node_t *h = q->head;
    while (h) {
        node_t *t = h;
        h = t->next;
        free(t);
    }
    free(q);
}


static void printq(queue_t *q)
{
    int i = 0;
    for (const node_t *h = q->head;  h;  h = h->next) {
        printf("[%d] %s\n", i++, &h->data[0]);
    }
}

int main(void)
{
    const char *test[] =
    {
        "January",
        "February",
        "Random"
    };
    int numtest = sizeof test / sizeof test[0];
    queue_t *nameq = q_init();
    if (!nameq) {
        fprintf(stderr, "Failed to create queue\n");
        return EXIT_FAILURE;
    }
    for (int i = 0;  i < numtest;  i++) {
        if (!q_push(nameq, test[i], strlen(test[i]) + 1)) {
            fprintf(stderr, "Failed to create element %i\n", i);
            return EXIT_FAILURE;
        }
    }
    printq(nameq);

    q_pop(nameq);
    printq(nameq);

    const char *hname = q_peek(nameq);
    printf("head name = %s\n", hname);

    q_free(nameq);
}

This version has no errors when compiled by gcc -std=c17 -Wall -Wextra -Wwrite-strings -Wno-parentheses -Wpedantic -Warray-bounds -Wstrict-prototypes -Wconversion, and no issues reported by Valgrind.