Dynamically sized queue

Question 1

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 %drn", queue->size);
    for (i = 0; i < 256; i++) {
        printf("#%d in queue: 0x%drn", i, queue->next(queue));
    }
    return 0;
}

Question 2

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.

Question 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).

Leave a Reply Cancel reply