Dynamically sized queue

Question

This is my first deep dive into C, and I want to make sure that I'm not doing anything stupid. The code below creates an "Array List" of sorts, which automatically resizes itself.

This code is meant to run on a PIC24, where memory is at a premium.

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

#ifndef CHAR_QUEUE_H
#define CHAR_QUEUE_H
#define QUEUE_INIT_SIZE 128

typedef struct CharQueue_t{
    uint16_t size;
    uint16_t capacity;
    unsigned char *data;
    void (*append) (struct CharQueue_t *, unsigned char);
    void (*destroy) (struct CharQueue_t *);
    unsigned char (*get) (struct CharQueue_t *, uint16_t);
    unsigned char (*next) (struct CharQueue_t *);
} CharQueue_t;

CharQueue_t *CharQueueInit();

void CharQueueAppend(struct CharQueue_t *queue, unsigned char value);

void CharQueueDestroy(struct CharQueue_t *queue);

unsigned char CharQueueGet(struct CharQueue_t *queue, uint16_t idx);

unsigned char CharQueueNext(struct CharQueue_t *queue);

#endif  /* CHAR_QUEUE_H */

CharQueue_t *CharQueueInit() {
    CharQueue_t *queue = malloc(sizeof(CharQueue_t));
    // Initialize size and capacity
    queue->size = 0;
    queue->capacity = QUEUE_INIT_SIZE;
    queue->data = malloc(sizeof(unsigned char) * queue->capacity);
    queue->append = CharQueueAppend;
    queue->destroy = CharQueueDestroy;
    queue->get = CharQueueGet;
    queue->next = CharQueueNext;
    return queue;
}

void CharQueueAppend(struct CharQueue_t *queue, unsigned char value) {
    // Resize the queue if it's at capacity
    if (queue->size >= queue->capacity) {
        queue->capacity *= 2;
        queue->data = realloc(queue->data, sizeof(unsigned char) * queue->capacity);
    }
    queue->data[queue->size] = value;
    queue->size++;
}

void CharQueueDestroy(struct CharQueue_t *queue) {
    free(queue->data);
    free(queue);
}

unsigned char CharQueueGet(struct CharQueue_t *queue, uint16_t idx) {
    if (idx >= queue->size || idx < 0) {
        return 0;
    }
    return queue->data[idx];
}

unsigned char CharQueueNext(struct CharQueue_t *queue) {
    char data = queue->data[0];
    queue->size = queue->size - 1;
    // Move the pointer up the stack -- Does this leak memory?
    *queue->data++;
    return data;
}

int main(void) {
    CharQueue_t *queue = CharQueueInit();
    int i;
    for (i = 0; i < 256; i++) {
        queue->append(queue, i);
    }
    printf("Queue Size is %d\r\n", queue->size);
    for (i = 0; i < 256; i++) {
        printf("#%d in queue: 0x%d\r\n", i, queue->next(queue));
    }
    return 0;
}

yuri · Accepted Answer · 2018-06-19 08:05:40Z

Just a few things:

uint16_t for a size type is really small. To be precise, the maximum value of uint16_t is 2^16 - 1, or 65535. That's 64 kb of data only, which is not enough for most applications, if you consider that modern PCs have gigabytes of memory available. For sizes in general, size_t suggests itself, and offers plenty of bits for addresses (on most modern pc architectures, at least).
Why all of these functions pointers in the struct? Unless your main design goal is maximum flexibility and genericity, all you're likely achieving is bloating your struct.
Comparing a variable of type uint16_t against 0 as in if (idx >= queue->size || idx < 0) is pointless. The u in uint16_t stands for "unsigned", and variables of the type can only take values in the range [0, 2^16 - 1].
```
// Move the pointer up the stack -- Does this leak memory?
*queue->data++;
```
Not only does this leak data, it makes freeing the memory actually impossible! free can only be called on pointers directly obtained from malloc and friends. As soon as you increment the pointer, free will automatically cause undefined behavior. Under all circumstances, you have to keep a pointer to the start around, or do some index shenanigans.
sizeof(unsigned char) is guaranteed to be 1 by definition. You don't need to multiply by that when you're allocating memory.
It's usually a good idea to check for malloc failures. If malloc fails to allocate memory, it returns NULL, which can be easily checked against and which allows you to exit gracefully, rather than (hopefully) crashing with a segfault.
For that very same reason, i.e. that malloc can fail, directly assigning from realloc is dangerous, since realloc can also fail and return NULL, in which case you lose the pointer to the original memory if you're not careful (leading to a certain leak down the line).
Similarly, check for NULL on all the pointers you receive from a user. Calling any of your functions with NULL as the first argument is going to lead to undefined behavior, which you should guard against.

Thanks, Ben! This queue is going to be used on a PIC24 to store bytes read off of UART, which is why I was conscious about memory. As for #2, I like the simplicity of referring to CharQueueAppend as append -- is this bad practice? I have addressed your other concerns and updated the OP. The only thing I haven't implemented is checking for null pointers (yet) :). — t3ddftw
– t3ddftw, Commented Jun 18, 2018 at 21:43
@t3ddftw Ah, you should've told us about the memory limitations :P. In that circumstance, uint16_t is probably fine. About the second point: Yes, this is bad practice, because your object grows with each pointer (and also, calling through function pointer is possibly slow). This is a readability tradeoff I would not make. — Ben Steffan
– Ben Steffan, Commented Jun 18, 2018 at 21:49
@t3ddftw Also, please reroll your edit! Here on Code Review, you mustn't implement the code review ideas directly in the question, because this makes the answers meaningless, basically. If you still have questions, please open up a follow up post. — Ben Steffan
– Ben Steffan, Commented Jun 18, 2018 at 21:50
Thanks so much! I've rerolled my edit and the original code is back in place. Sorry about that, this is my first time on Code Review :) — t3ddftw
– t3ddftw, Commented Jun 18, 2018 at 22:14

Toby Speight · Accepted Answer · 2018-06-19 12:24:19Z

3

If memory is at a premium, then realloc() can be problematic. Not only must it find space before the existing block can be released (so requiring more memory than you'll be keeping), but it requires contiguous memory to be available, and can fail in the face of fragmentation.

Consider instead a linked list of reasonable-sized blocks. When you fill the tail block, then append one of the empty blocks from the beginning of the queue; if none have yet been emptied, then allocate a new one.

Alternatively, when you reach the end of a block when reading, add it to the tail of the queue (you might even free() unused blocks if you already have plenty of write space at the tail, allowing your queue to shrink as well as grow).

edited Jun 19, 2018 at 12:24

answered Jun 19, 2018 at 9:47

Toby Speight

88.8k14 gold badges104 silver badges327 bronze badges

2

\$\begingroup\$ Thanks @chux - I was struggling for a good wording for that sentence. I've compromised with a simple "more memory", on the assumption that the reader can figure it out better than I can describe. \$\endgroup\$

Toby Speight
– Toby Speight

2018-06-19 12:25:22 +00:00
Commented Jun 19, 2018 at 12:25

Add a comment |

Stack Exchange Network

Dynamically sized queue

2 Answers 2

You must log in to answer this question.

Hot Network Questions

Dynamically sized queue

2 Answers 2

You must log in to answer this question.

Related

Hot Network Questions