Issue with dynamic array Queue data structure with void pointer

Question

Hi,

Maybe there's no way to solve this the way I'd like it but I don't know everything so I better ask...

I've implemented a simple Queue with a dynamic array so the user can initialize with whatever number of items it wants. I'm also trying to use a void pointer as to allow any data type, but that's the problem.

Here's my code:

typedef void * QueueValue;

typedef struct sQueueItem {
    QueueValue value;
} QueueItem;

typedef struct sQueue {
    QueueItem *items;

    int first;
    int last;
    int size;
    int count;
} Queue;

void queueInitialize(Queue **queue, size_t size) {
    *queue = xmalloc(sizeof(Queue));

    QueueItem *items = xmalloc(sizeof(QueueItem) * size);

    (*queue)->items = items;
    (*queue)->first = 0;
    (*queue)->last = 0;
    (*queue)->size = size;
    (*queue)->count = 0;
}

Bool queuePush(Queue * const queue, QueueValue value, size_t val_sz) {
    if(isNull(queue) || isFull(queue)) return FALSE;

    queue->items[queue->last].value = xmalloc(val_sz);
    memcpy(queue->items[queue->last].value, value, val_sz);

    queue->last = (queue->last+1) % queue->size;
    queue->count += 1;

    return TRUE;
}

Bool queuePop(Queue * const queue, QueueValue *value) {
    if(isEmpty(queue)) return FALSE;

    *value = queue->items[queue->first].value;

    free(queue->items[queue->first].value);

    queue->first = (queue->first+1) % queue->size;
    queue->count -= 1;

    return TRUE;
}

The problem lies on the queuePop function. When I call it, I lose the value because I free it right away. I can't seem to solve this dilemma. I want my library to be generic and modular. The user should not care about allocating and freeing memory, that's the library's job.

How can the user still get the value from queuePop and let the library handle all memory allocs/frees?

Answer 1

I think you want to change your idea about what to store. A user gives you a pointer to some memory that she allocated, so she should expect to deallocate it. You don't need to memcpy or free the value, you just need to keep track of the pointer. Pushing in the queue should transfer ownership to the queue, and popping from the queue should transfer ownership back to the user. So all you need to do is copy around the 'val' pointer.

Also, to clean up the queue storage when finished, you probably want a queueDestroy(Queue* q) function.

Edit:

• Notice, you don't need QueueItem and you can store an array of QueueValues.
• Also, I realize you explicitly said that memory management was the job of the library, but that's when you run into problems (like the one you're running into). The library should take care of its own memory management (the queue). But the alloc & dealloc of the items should be the user's job.
• Another option is to provide a queueFront(Queue *q) which passes back the value, but then it gets deallocated by queuePop(Queue *q). I prefer your current approach though :)
• Requiring the user to define a max size for the queue is kinda restricting. If you want this to be generic++,modular++ then you should use a predefined constant, then grow on queuePush(), if it's full. Alternatively you can use a linked list implementation (but contiguous memory is generally much much faster).

Answer 2

Others have (correctly) pointed out the severe limitations of your design, but this will fix what you have. It assumes that the caller knows what size object is getting pushed and popped.

Theoretically, only two of these changes are absolutely essential, but the others serve to lower the likelihood of a crash (due to programmer error) from ~100% to ~80%.

typedef struct sQueueItem {
    QueueValue value;
    size_t     item_size;               // <-- you'll need this for the Pop
} QueueItem;

Bool queuePush(Queue * const queue, QueueValue value, size_t val_sz) {
    if(isNull(queue) || isFull(queue)) return FALSE;

    queue->items[queue->last].value = xmalloc(val_sz);
    memcpy(queue->items[queue->last].value, value, val_sz);
    queue->items[queue->last].item_size = val_sz;        // <-- save the size

    queue->last = (queue->last+1) % queue->size;
    queue->count += 1;

    return TRUE;
}

Bool queuePop(Queue * const queue, 
               QueueValue **value, // ESSENTIAL: now char **
               size_t item_size)   // so we can ensure enough room
{                                         
    if(isEmpty(queue)) return FALSE;

     // just for readability
    QueueItem *p = queue->items[queue->first];

    // watch for programmer error (maybe you should throw() something)
    assert(p->item_size == item_size);       

    // ESSENTIAL: copy the item to the caller's memory
    memcpy(*value, p->value, p->item_size); 

    free(queue->items[queue->first].value);

    queue->first = (queue->first+1) % queue->size;
    queue->count -= 1;

    return TRUE;
}

Edit:

It's been pointed out that I could have left queuePop as

Bool queuePop(Queue * const queue, 
               QueueValue *value,  // stet
               size_t item_size)   // so we can ensure enough room

and changed the `memcpy` to 

    // ESSENTIAL: copy the item to the caller's memory
    memcpy(value, p->value, p->item_size); 

I had at some point written it so if the caller passed a NULL in item_size, queuePop would do a malloc() and pass the pointer back to the caller via **value. I changed my mind and thought I reverted completely, but SO doesn't have Version Control :)

Answer 3

Your queuePop() function needs to work the same way as queuePush() - take the size of the location and memcpy() to it.

Bool queuePop(Queue * const queue, QueueValue value, size_t val_sz)
{
    if (isEmpty(queue)) return FALSE;

    memcpy(value, queue->items[queue->first].value, val_sz);

    free(queue->items[queue->first].value);

    queue->first = (queue->first+1) % queue->size;
    queue->count -= 1;

    return TRUE;
}