CODEWITHSUNDEEP
csegmentation-faultqueuepriority-queue
Manish Sharma
Manish Sharma

Reputation: 142

Why is this queue implementation in C giving segmentation fault?

I have implemented a simple queue in C but its giving segmentation fault when I try to access Q.front after dequeuing (See int main() for example).

To be more precise, the problem occurs when I -

  1. Enqueue a single element.
  2. Dequeue it.
  3. Enqueue one or more elements.
  4. Try to access Q.front

However the program doesn't give segmentation fault or any error when I -

  1. Enqueue more than one element.
  2. Dequeue one time.
  3. Enqueue more elements (optional)
  4. Access Q.front successfully.

So this is my complete program -

#include <stdio.h>
#include <stdlib.h> //for malloc

struct qnode
{
    int r;
    struct qnode *link;
};

typedef struct qnode qNode;

typedef struct
{
    qNode *front;
    qNode *rear;
    int qsize;
}QUEUE;

QUEUE initializeQueue(void)
{
    QUEUE q;
    q.front = NULL;
    q.rear = NULL;
    q.qsize = 0;
    return q;
}


qNode *createQueueNode(int e)
{
    qNode *temp;
    temp = (qNode *) malloc(sizeof(qNode));
    if(temp == NULL)
    {
        printf("INSUFFICIENT MEMORY\n");
        exit(0);
    }
    temp->r = e;
    temp->link = NULL;
    return temp;
}
QUEUE enqueue(QUEUE q, int e)
{
    if(q.rear == NULL)
    {
        q.rear = createQueueNode(e);
        q.front = q.rear;
        q.qsize++;
    }
    else
    {
        q.rear->link = createQueueNode(e);
        q.rear = q.rear->link;
        q.qsize++;
    }
    return q;
}

QUEUE dequeue(QUEUE q)
{
    qNode *temp;
    if(q.front == NULL)
    {
        printf("queue is empty\n");
        exit(0);
    }
    else
    {
        temp = q.front;
        q.front = q.front->link;
        free(temp);
    }

    q.qsize--;
    return q;
}



int main(){

    QUEUE Q = initializeQueue();
    Q = enqueue(Q, 2);
    printf("%d\n",Q.front->r);
    Q = dequeue(Q);
    Q = enqueue(Q,4);
    printf("%d\n",Q.front->r); // This line is giving segmentation fault 

    return 0;
}

Upvotes: 1

Views: 881

Answers (2)

alex.forencich
alex.forencich

Reputation: 1435

dequeue sets q.front to NULL (from q.front->link, which was previously set to NULL in createQueueNode) and leaves a trash pointer (to free()'d memory) in q.rear. Since q.rear is not NULL, the 2nd block in the if statement in enqueue gets executed on the 2nd call to enqueue. Which writes to free()'d memory (q.rear->link), then dereferences that into q.rear. I'm surprised it doesn't crash right there, actually, with the write to free()'d memory. Quick fix would probably be to set q.rear to NULL in dequeue if queue is empty. You should also add a sanity check so dequeue won't run on an empty queue.

Also, you've got an interesting way of passing that structure around like a hot potato. Why not pass it by reference and modify it in place instead of returning it?

Upvotes: 1

jacob
jacob

Reputation: 681

Program terminated with signal 11, Segmentation fault.
#0  0x0000000000400859 in main () at ./2.c:87
87          printf("%d\n",Q.front->r); // This line is giving segmentation fault 
Missing separate debuginfos, use: debuginfo-install glibc-2.12-1.80.el6.x86_64
(gdb) p Q
$1 = {front = 0x0, rear = 0x1636010, qsize = 1}

front is null and you access it. you just need a debuger like gdb to see what's going wrong with your program.

Upvotes: 1

Related Questions