Implementing a FIFO queue in C

Question

For an embedded application, I am trying to implement a first-in, first-out (FIFO) queue of structs using ANSI C. The most straightforward way to do this seems to be by implementing a linked-list, so that each structure contains a pointer to the next in the queue. Hence I define the struct itself as:

typedef enum { LED_on, LED_off, etc } Action;
typedef struct Queued_Action QueuedAction;

struct Queued_Action
{
    Action       action;
    int          value;
    QueuedAction *nextAction;
};

So far so good. If I define pointers to the first and last items in the queue as:

QueuedAction *firstAction;
QueuedAction *lastAction;

...then I'd like to be able to add a new action to the queue by stating (for example):

if (!add_action_to_queue(LED_on, 100, &lastAction))
     printf("Error!\n);

...so on return, lastAction would be a pointer to the newly-created last action in the queue. Hence the routine for adding the action to the queue would look like:

int add_action_to_queue(Action newAction, int newValue, QueuedAction **lastAction)
{
    QueuedAction *newQueuedAction;

    // Create a new action in memory
    if ((newQueuedAction = (QueuedAction *)malloc(sizeof(QueuedAction))) == NULL)
        return 0;

    // Make the old 'lastAction' point to the new Action, 
    // and the new Action to point to NULL:
    *lastAction -> nextAction = newQueuedAction;
    newQueuedAction -> nextAction = NULL;
    newQueuedAction -> action = newAction;
    newQueuedAction -> value = newValue;

    // Designate the new Action as the new lastAction:
    *lastAction = newQueuedAction;
    return 1;
}

All would be fine and dandy, except this code won't compile. The error is at the line saying

*lastAction -> nextAction = newQueuedAction;

...where the compiler claims the item to the left of the '->' is not a valid struct. Surely, however, it must be. If in fact I do what ought to be a wholly redundant cast:

fakeAction = (QueuedAction *)(*lastAction);
fakeAction -> nextAction = newQueuedAction;

...then the compiler is quite happy. However, I'm worried that the error message is hinting at something subtle that I may be doing wrong here. So (to come to the point), can anyone tell me why the compiler isn't happy, and whether there is a better way to do what I'm trying to do here.

Answer 1

I hope this will help you in advance. Firstly, sorry for my english. It could have several gramatical or ortographical errors.

The problem I see in your code is mainly you mix definition of a pointer and implementation of the same one.

From ANSI C to C99, even in C++ (not tested in C#), there is a big hack using pointers could be helpful in advance: think the pointer is the first element of a vector, the [0] one.

A great site explaining this concept is: http://boredzo.org/pointers/

This hack is a bare translation, and a nice hacktool to understand better the pointers.

Get into action, boys.

The function you use to add elements into a list,

int add_action_to_queue(Action newAction, int newValue, QueuedAction **lastAction)
{
    QueuedAction *newQueuedAction;

    // Create a new action in memory
    if ((newQueuedAction = (QueuedAction *)malloc(sizeof(QueuedAction))) == NULL)
        return 0;

    // Make the old 'lastAction' point to the new Action, 
    // and the new Action to point to NULL:
    *lastAction -> nextAction = newQueuedAction;
    newQueuedAction -> nextAction = NULL;
    newQueuedAction -> action = newAction;
    newQueuedAction -> value = newValue;

    // Designate the new Action as the new lastAction:
    *lastAction = newQueuedAction;
    return 1;
}

Contains some errors. First of all, think using

*lastAction -> ...;

as

lastAction[0] -> ...;

As you see, you can't use the -> operator to access the inner elements.

The same happens here:

lastAction[0] = newQueuedAction;

You can't copy a pointer inside of a struct. lastAction, using this hack to better understanding, is not a pointer anymore -in fact, is the content of the first element in the structure the compiler has assigned into there- so you need to change this line, too, to change the pointer value:

lastAction = newQueuedAction;

Using this translation and the anotations, your code will be, now:

int add_action_to_queue(Action newAction, int newValue, QueuedAction **lastAction)
{
    QueuedAction *newQueuedAction;

    // Create a new action in memory
    if ((newQueuedAction = (QueuedAction *)malloc(sizeof(QueuedAction))) == NULL)
        return 0;

    // Make the old 'lastAction' point to the new Action, 
    // and the new Action to point to NULL:
    lastAction[0] -> nextAction = newQueuedAction;
    newQueuedAction -> nextAction = NULL;
    newQueuedAction -> action = newAction;
    newQueuedAction -> value = newValue;

    // Designate the new Action as the new lastAction:
    lastAction[0] = newQueuedAction;
    return 1;
}

The errors are, now, visible: you try to use the -> operator wrongly. That means your code will be changed in two ways:

• Use the -> operator

It looks like this:

int add_action_to_queue(Action newAction, int newValue, QueuedAction **lastAction)
{
    QueuedAction *newQueuedAction;

    // Create a new action in memory
    if ((newQueuedAction = (QueuedAction *)malloc(sizeof(QueuedAction))) == NULL)
        return 0;

    // Make the old 'lastAction' point to the new Action, 
    // and the new Action to point to NULL:
    lastAction -> nextAction = newQueuedAction;
    newQueuedAction -> nextAction = NULL;
    newQueuedAction -> action = newAction;
    newQueuedAction -> value = newValue;

    // Designate the new Action as the new lastAction:
    lastAction = newQueuedAction;
    return 1;
}

• Use the . operator with the [0] hack

It looks like this:

int add_action_to_queue(Action newAction, int newValue, QueuedAction **lastAction)
{
    QueuedAction *newQueuedAction;

    // Create a new action in memory
    if ((newQueuedAction = (QueuedAction *)malloc(sizeof(QueuedAction))) == NULL)
        return 0;

    // Make the old 'lastAction' point to the new Action, 
    // and the new Action to point to NULL:
    lastAction[0].nextAction = newQueuedAction;
    newQueuedAction[0].nextAction = NULL;
    newQueuedAction[0].action = newAction;
    newQueuedAction[0].value = newValue;

    // Designate the new Action as the new lastAction:
    lastAction = newQueuedAction;
    return 1;
}

And don't forget erase the == NULL code, you would encounter with a passive-aggresive programmer who defines NULL as something else. Use always braces to ensure extensibility. This line is only a recomendation of code style.

Hope it helps,

Answer 2

You could also do this:

(*lastAction)->nextAction

I think it is an issue of operator pecedence.

Answer 3

I've made a small library that can handle queues. "UltraQueue"

It's written in C++, but is fully compatible with ANSI C. It can be easely converted to ANSI C if you really want to.

Source code is available through GIT.

Grtz

Answer 4

Have you tried:

(*lastAction) -> nextAction = newQueuedAction;