Queue implementation in C

Question

I was reading about opaque pointers and decided to try it with queues. Please review my code and let me know if there are any errors and how to improve code quality and performance.

It uses lines to enqueue and dequeue. All lines have fixed sizes and dequeue/enqueue never share a line. New lines are added only when all lines are full, not counting the dequeue line. The lines are stored in a linked list.

queue.h

#ifndef QUEUE_H
#define QUEUE_H

#include <stdlib.h>
#include <assert.h>

#define QU_SUCCESS 0
#define QU_ERROR 1

typedef struct Queue Queue;

Queue *qu_allocate_custom(size_t lines, size_t capacity);
Queue *qu_allocate(void);
void qu_free(Queue *queue);
int qu_enqueue(Queue *queue, void *content);
void *qu_dequeue(Queue *queue);
size_t qu_get_count(Queue *queue);
void qu_shrink_to_fit(Queue *queue);

#endif

queue.c

#include "queue.h"

#define QU_DEFAULT_LINES 4
#define QU_DEFAULT_LINE_CAPACITY 50

//Data structures
/*
The line has a fixed size. It contains a link to the next and can hold void *.
I'm using double pointers because I expect it to act like an array of void *.
So, when I do position++ it will move sizeof(void *) and point to the next
stored address. Also the end of the line, if it's not full, can be delimited by
simply doing *position = NULL.
*/
typedef struct Line Line;
struct Line {
    void **start;
    void **position;
    void **end;
    Line *next;
};

/*
The queue structure just stores meta info and points to lines. The member index
is there because I thought it would make the the other functions simpler since
they won't have to deal with special cases. They just treat it as if it were a 
regular line. And that's ok because most functions take the line that comes before
the one they are operating on as an argument so they don't have to walk through
the list to find that node in order to update the pointer to the next;

The queue stores only elements of sizeof(void *), whatever is received by enqueue
will be sent back by dequeue, so it can store a pointer to anything and
also work with other data types of size up to sizeof(void *).

The queue works like this:
1 - When it's created, lines of fixed sizes are allocated
2 - Dequeue is set to the first position, enqueue to the second
3 - Both just walk along the list and never share a Line
4 - If dequeue moves to the same line as enqueue, enqueue will go to the next.
If the line is not full, one past the last element will contain NULL to indicate
that's the end.
5 - If enqueue finishes filling a line, it will check if the next is empty. If
that's the case, it will go there. Otherwise dequeue is certainly using the line.
So enqueue will try to create a new line.
*/
struct Queue {
    Line index; //just a pointer to the first line
    Line *enqueue;
    Line *dequeue;
    size_t count;
    size_t line_capacity;
};


//Internal methods
//Take the element that comes before, so it doesn't have to walk through the list
static void free_line_after( Line *previous )
{
    assert(previous->next != NULL);
    Line *line = previous->next;
    previous->next = line->next;
    free(line);
}

static void free_all_lines( Line *first )
{
    void *next;
    for(Line *ite = first; ite != NULL; ite = next){
        next = ite->next;
        free(ite);
    }
}

/*
Allocate a line and space for its contents in a single call to malloc since the
lines have fixed sizes. There's no point in calling malloc twice here.
*/
static Line *push_line_after( Line *previous, size_t capacity )
{
    assert(previous != NULL && capacity > 0);

    //Allocate space for Line and its contents
    Line *new_line = malloc(sizeof(Line) + capacity * sizeof(void **));
    if(new_line == NULL)
        return NULL;

    //Put on the list
    new_line->next = previous->next;
    previous->next = new_line;

    //Set all pointers and add a NULL delimiter so dequeue will be able to recognize
    //this line has nothing to dequeue
    new_line->start = (void **)(new_line + 1);
    new_line->position = new_line->start;
    new_line->end = new_line->start + capacity;
    *new_line->position = NULL;

    return new_line;
}

static inline Line *next_line( Queue *queue, Line *current )
{
    return (current->next != NULL) ? current->next : queue->index.next;
}


//Since it's an opaque pointer, setters/getters
size_t qu_set_capacity(Queue *queue, size_t new_capacity)
{
    if(new_capacity > 0)
        queue->line_capacity = new_capacity;

    return queue->line_capacity;
}

size_t qu_get_count(Queue *queue)
{
    return queue->count;
}


//Public methods
/*
Create a new queue with `lines` starting lines, each with `capacity` for pointers
*/
Queue *qu_allocate_custom( size_t lines, size_t capacity )
{
    if(lines < 2 || capacity < 1)
        return NULL;

    Queue *new_queue = malloc(sizeof(Queue));
    if(new_queue == NULL)
        return NULL;

    //If the value is garbage, push_line_after will break the list
    new_queue->index.next = NULL;

    //Create all starting lines or cancel the operation 
    Line *previous = &new_queue->index;
    while(lines-- > 0){
        previous = push_line_after(previous, capacity);
        if(previous == NULL){
            free_all_lines(new_queue->index.next);
            free(new_queue);
            return NULL;
        }
    }

    //Dequeue starts behind so it doesn't have to iterate through the whole list
    //on the first call
    new_queue->dequeue = new_queue->index.next;
    new_queue->enqueue = new_queue->dequeue->next;
    new_queue->count = 0;
    new_queue->line_capacity = capacity;

    return new_queue;
}

Queue *qu_allocate( void )
{
    return qu_allocate_custom( QU_DEFAULT_LINES, QU_DEFAULT_LINE_CAPACITY );
}

void qu_free(Queue *queue)
{
    free_all_lines(queue->index.next);
    free(queue);
}

int qu_enqueue( Queue *queue, void *content )
{
    //First enqueue will check if the current line is full.
    if(queue->enqueue->end == queue->enqueue->position){

        //If it is it will check if the next line if empty and go there if it is
        Line *next = next_line(queue, queue->enqueue);
        if(next != queue->dequeue)
            queue->enqueue = next;

        //If the next line is not empty, it will try to create a new line
        else {
            next = push_line_after(queue->enqueue, queue->line_capacity);
            if(next == NULL)
                return QU_ERROR;

            queue->enqueue = next;      
        }
    }

    //Store, update position, update count
    *queue->enqueue->position++ = content;
    ++queue->count;

    return QU_SUCCESS;
}

/*Dequeue sets position back to zero when it starts working on a line. NULL also 
delimits the line end when enqueue is moved before the line is full (when dequeue
tells it to move).*/
void *qu_dequeue( Queue *queue )
{
    //If this line is empty
    if(queue->dequeue->end == queue->dequeue->position
                           || *queue->dequeue->position == NULL){   

        //Check if there's something on the next line
        Line *next = next_line(queue, queue->dequeue);
        if(next->start == next->position)
            return NULL;

        //Finish here and go there
        queue->dequeue->position = queue->dequeue->start;
        queue->dequeue = next;

        //Move enqueue if it's on this new line 
        if(queue->dequeue == queue->enqueue){
            queue->enqueue = next_line(queue, queue->enqueue);

            //And add a delimiter if it's not full
            if(queue->dequeue->end != queue->dequeue->position)
                *queue->dequeue->position = NULL;
        }

        //Don't forget to set the position to 0 so it can be processed
        queue->dequeue->position = queue->dequeue->start;
    }

    //There's something to return
    --queue->count;
    return *queue->dequeue->position++; 
}

//Since dequeue is always behind enqueue, all lines between enqueue and dequeue
//must be empty and thus safe to free
void qu_shrink_to_fit( Queue *queue )
{
    //First process all lines after enqueue
    Line *last = queue->enqueue;
    while(last->next != NULL){
        if(last->next == queue->dequeue)
            return;

        free_line_after(last);
    }

    //Now process all starting lines behind dequeue
    last = &queue->index;
    while(last->next != queue->dequeue)
        free_line_after(last);
}

And some code to perform simple tests

#include <stdio.h>
#include "queue.h"

int main(void)
{
    Queue *queue = qu_allocate();
    if(queue == NULL){
        return 1;
    }

    char *words[] = {
        "Highest Priority",
        "High Priority",
        "Almost High Priority",
        "Regular Priority",
        "Almost Low Priority",
        "Low Priority",
        "Lowest Priority",
        "He who laughs last, laughs best.",
        ""
    };

    for(char **ite = words; **ite != '\0'; ++ite){
        qu_enqueue(queue, *ite);
    }

    qu_enqueue(queue, "About the middle.");

    printf("Count is: %zu\n", qu_get_count(queue));

    qu_dequeue(queue);
    qu_dequeue(queue);

    printf("Count is: %zu after dequeuing 2 elements\n\n", qu_get_count(queue));

    for(char **ite = words; **ite != '\0'; ++ite){
        qu_enqueue(queue, *ite);
    }

    qu_enqueue(queue, "Before last.");
    qu_enqueue(queue, "Last.");

    qu_shrink_to_fit(queue);

    for(char *location; (location = qu_dequeue(queue)) != NULL;){
        puts(location);
    }

    for(int i = 0; i < 500; ++i)
        qu_dequeue(queue);

    printf("Count is: %zu\n", qu_get_count(queue));

    qu_free(queue);
    return 0;
}

Answer 1

I did something very similar to this in assembly a looooong long time ago, so I'm going to compare and contrast for the sake of nostalgia. And helping you out, that too.

The main difference in our top level designs is that I was storing values as elements of the Line, whereas you are storing void*. The reason I didn't always store void* was that it didn't require any additional memory management for consuming code by default. If I needed to do memory management separately, I could do that by making it a queue of pointers. In your code, you must either store pointers to static data or malloc and mfree each element separately. I see those two possibilities as a hazard in the case that the consumer doesn't yet know whether dynamic allocation is necessary, or worse, if void* to static data and void* to something on the heap have been mixed in the same Queue somehow. The end result will be an error (trying to mfree static data) or memory leaks (not mfreeing heap data). It's especially error prone because if you need to mfree, you have to do it soon after you dequeue it (possibly happening in many functions) or it leaks, so switching between static data and heap will be hazardous.

On the other hand, believe me when I say you've avoided the following headaches by storing only void*:

• Destructors. You can handle disposal of the structure when it's dequeued or instead store that pointer elsewhere and not dispose of it in your consuming code. My ASM version had to be initialized with an optional pointer to a destructor function, yours leaves that up to the consumer.

• Lots of pointer math internally. It is waaaay simpler to allocate an array of a void* and come up with a pointer to element i than it is to allocate an array of arbitrary sized structures, which may need to have their element size adjusted for alignment, etc. etc.

That would be a really tough thing to change, and ultimately a matter of documentation more than quality, so let's move on.

The fact that your Queue involves a Line by value that doesn't have an accompanying buffer of elements is somewhat of a misuse of the structure. I can see where it looks like it might be necessary in order to have free_line_after and push_line_after take and/or return a Line*, but you can make those functions and the Queue structure simpler and clearer by eliminating the index from Queue. Instead:

struct Queue {
    Line* enqueue;
    Line* dequeue;
    size_t count;
    size_t line_capacity;
}

static void free_line( Line** ppLine ) {
    Line* toFree = *ppLine;
    assert(toFree !== NULL);
    *ppLine = toFree->next;
    free(toFree);
}

// theoretically could make this return a bool indicating error/no error,
// but it's easier to remember that NULL means error.
static Line* push_line_before( Line** ppLine, size_t capacity ) {
    Line* before = *ppLine;
    Line* new_line = malloc(sizeof(Line) + capacity * sizeof(void **));
    if (new_line == NULL)
        return NULL;

    new_line->next = before;
    *ppLine = new_line;
    /* do initialization the same way you did it... */
    return new_line;
}

static void why_this_way_is_better(Queue* someQueue) {
    // Queue has no Line-valued member, and yet we can still use the same
    // functions for a Queue member...
    free_line( &(someQueue->dequeue) );
    push_line_before( &(someQueue->enqueue) );
    // ... as the ones for a line member
    free_line( &(someQueue->dequeue->next) );
    push_line_before( &(someQueue->enqueue->next) );
}

Again, that will change a few things logically throughout your code and header, but it will end up far cleaner and clearer than it started. You've got pointers to pointers in C, an often underestimated advantage over other languages, and so far you're doing great with them. If you can handle using them for pointers to arrays of pointers, you can handle using pointers to members as objects.

Other than that, the nature of the task demands a bunch of hairy pointer-chasing and a little bit of pointer math, which is tough to read. Stuff like return *queue->dequeue->position++; takes a second for me to digest fully. If your comments were at all lacking, I would want some of the longer statements to be broken up and have some intermediates made into local variables with names. However, your comments spell out what's going on very clearly, so I don't think that counts against you.

Answer 2

Your header looks fine - opaque pointers are as simple as that. Don't forget the const on function parameters (pointers) where possible.

Hmmm, a Line structure with double-pointers. That looks suspect. Double pointers are usually unnecessary. We'll see what becomes of these later... It would have been kind to the reader to give a line or two of comment to describe the queue and its components and the purpose of these double pointers.

The use of previous as a parameter name is unsatisfying, somehow confusing. In free_line_after I'm expecting it to free the line after 'this' one or the 'current' one, so previous jars a bit. I would avoid 'this' though and call it just l.

The start parameter to free_all_lines is misnamed as there is a start field in Line. The two are unrelated (I think) and should have different names.

In push_line_after you are allocating

Line *new_line = malloc(sizeof(Line) + capacity * sizeof(void **));

So this makes me think that your Line structure is intended to hold the line data beyond the end of the structure, as in:

struct Line {
    ...
    Line *next;
    char data[];
};

You instantiate Line in Queue for some reason (I imagine from your comment that you just need a pointer to a Line but I haven't checked) so you'd have to have char data[1] to keep that. But this is the normal way to extend a structure with variable data. If you do this, you don't need the double pointers but instead just keep indices.

Maybe I have misinterpreted your intentions, so I will stop there. I haven't read through the rest (as I say double pointers are normally unnecessary and make reading code difficult).

---

EDIT I don't have time to look in detail at the code, but the explanations you added certainly help. I do think the mechanism is rather odd - having two queue mechanisms in one. Your tests only test one of the mechanisms with the code in conditional in qu_enqueue:

if(queue->enqueue->end == queue->enqueue->position){
    ....
}

never entered. Setting QU_DEFAULT_LINE_CAPACITY to something small rectifies this and the code seems to work.