Trouble adding to the rear of a FIFO queue in C, with reference to the last element

Question

I'm having a tough time wrapping my head around C. I'm trying to implement a FIFO linked list where I have a reference to the tail-end of the list for easy access when adding elements. Enqueuing to an empty list works fine where the head and rear would be the same Node. However, when I enqueue for a second time, the rear is correctly the new Node but the head is also updated, which should stay the same. Any thoughts to what I might be doing wrong? I apologize in advance for the one-liner conditional if it's difficult to read.

typedef struct node {
    PCB *pcb;
    struct node *next;
}Node;

typedef struct queue {
    Node *head, *rear;
    int size;
}Queue;

Queue * enqueue (Queue *queue, PCB *pcb) {

    // Ready a new node to add to list:
    Node node = {pcb, NULL};

    // Node becomes head in empty list, otherwise appended to rear.
    queue->size == 0 ? (queue->head = queue->rear = &node) : (queue->rear = &node);

    // Keep track of list size
    queue->size++;

    return queue;
}

UPDATED:

Queue * enqueue (Queue *queue, PCB *pcb) {


    // Ready a new node to add to list:
    Node *node = malloc(sizeof(Node));
    node->pcb = pcb;
    node->next = NULL;

    // Node becomes head in empty list, otherwise appended to rear.
    queue->size == 0 ? (queue->head = queue->rear = node) : (queue->rear->next = node);

    // New node always becomes the new rear node
    queue->rear = node;

    // Keep track of list size
    queue->size++;

    return queue;
}

You store the address of a local variable in your queue. `node` will go out of scope after returning from `enqueue` and will leave your queue pointers pointing to invalid memory. — M Oehm, Jan 15 '16 at 10:20
Complement to M Oehm's comment: if you declare `static Node node = {pcb, NULL};` your code may work, because then `node` will exist during the whole execution of your program and not only when inside the `enqueue` function` — Jabberwocky, Jan 15 '16 at 10:22
@MichaelWalz: Except that the queue will be made up of the same node all over. I don't think you can get around allocating memory on the heap (or creating a pool of nodes) here easily. — M Oehm, Jan 15 '16 at 10:24
The whole thing looks fishy, show more code ([MCVE](http://stackoverflow.com/help/mcve) means Minimal, Complete, and Verifiable example). — Jabberwocky, Jan 15 '16 at 10:31
@MOehm I've updated my code and it looks to work now. But i'm not quite sure why it works. I definitely have to brush up on pointers and addresses in C as it's definitely not my forte. — Arthur Huynh, Jan 15 '16 at 10:34
It works now, because you have allocated memory on the heap. The memory that `calloc` gives you is "yours" until you give it back with `free`. That means you must `free` that memory when you pop elements off the queue. In the first example, the `node` is on the stack. The stack is a good place for local variables that have the same lifespan as the function. If you data must live longer, you cannot use automatic variables on the stack. (By the way, you allocate three times as much memory as needed. A `Node` has three members, but `sizeof(Node)` takes care of that already.) — M Oehm, Jan 15 '16 at 10:40
@MOehm Thanks for the explanation. Last year's course in C is slowly coming back to me now. Thanks a lot! — Arthur Huynh, Jan 15 '16 at 10:42
Just to go by the book, you would check the return value of malloc to see if everything went well. Then you would also have to signal that to the caller somehow. — Selçuk Cihan, Jan 15 '16 at 12:40

Kellerspeicher · Answer 1 · 2016-01-16T16:02:12.063

0

Try this

#include <stdlib.h>
typedef struct node {
  PCB *pcb;
  struct node *next;
} Node;

typedef struct queue {
  Node *head, *rear;
  int size;
} Queue;

Queue *enqueue ( Queue *queue, PCB *pcb ) {
  if ( queue->size == 0 ) {
    queue->head = queue->rear = malloc( sizeof( Node ) );
  }
  else {
    queue->rear->next = malloc( sizeof( Node ) );
    queue->rear = queue->rear->next;
  }
  queue->rear->pcb = pcb;
  queue->rear->next = NULL;
  queue->size++;
  return queue;
}

But using C++ would be much safer and easier. And remember to free() your notes later.

For documentation (see comments): The fault of the first approach in the question was keeping a pointer of a local variable. It is on the stack but only valid until the function terminates. After termination it is a pointer to a location on the stack. This location will be overwritten as soon as the next function is called using sufficient local variables. The solution is allocating on the heap.

edited Jan 16 '16 at 16:02

answered Jan 15 '16 at 10:52

Kellerspeicher

608
4
13

Before I saw this post, I made a fix to my code after realizing my code didn't actually assign next Nodes correctly. But I actually like yours better. Thanks! – Arthur Huynh Jan 15 '16 at 11:07
But take a look at C++ and the STL containers. This is making dynamic data structures easy. Have fun. – Kellerspeicher Jan 15 '16 at 11:10
Addendum: I did the mistake to write this C example using a C++ compiler. Thus if do not cast you get a `invalid conversion from ‘void*’ to ‘node*’`. But if you write C you shall use a C compiler. And in this case it is better practice and safer **not to cast** (e.g. see [here](http://stackoverflow.com/questions/605845) why). I therefore updated the answer. – Kellerspeicher Jan 16 '16 at 15:52

score 0 · Answer 2 · answered Jan 15 '16 at 11:32

Your updated code is not quite right when the first node is added to the queue, because the line queue->head->next = queue->rear; sets node->next = node instead of leaving it set to NULL. Also, the new rear will always be the new node and can be set outside the if/else statement.

Queue * enqueue (Queue *queue, PCB *pcb) {

    // Ready a new node to add to list:
    Node *node = calloc(1, sizeof(Node));
    node->pcb = pcb;
    node->next = NULL;

    // Node becomes head in empty list, otherwise appended to rear.
    if (queue->size == 0) {
        queue->head = node;
    } else {
        queue->rear->next = node;
    }
    queue->rear = node;

    // Keep track of list size
    queue->size++;

    return queue;
}

Then should it be instead `queue->head = queue->rear = node`? — Arthur Huynh, Jan 15 '16 at 11:39

Trouble adding to the rear of a FIFO queue in C, with reference to the last element

2 Answers2