Linked stack in C. Pop causes segmentation fault, but Push does not!

Question

Hey everyone,

I'm doing some simple stuff, so hopefully this question can be easily answered easily. I'm using gcc to compile. The push works perfectly fine. The problem is the pop. I get a segmentation fault whenever I compile and run it.

Here are the pop and push functions:

int push(stack *stk, int data)
{
    stk->head = makeNode(data, stk->head);
    stk->length += 1;
    return data;
}

int pop(stack *stk)
{
    //Returns popped item
    //Returns -1 if stack length is zero
    if (stk->length < 1)
    {
        printf("No items to pop.");
        return -1;
    }
    int data = stk->head->value;
    struct node *toBeFreed = stk->head;
    stk->head = stk->head->ptr;
    free(toBeFreed);
    stk->length -= 1;
    return data;
}

I honestly don't know what the problem is, because the code is similar. I reassign the head variable in the stack in the push function, but it causes errors in the pop function. The assignment to data also gives me a seg fault. Pretty much everything except for the return and stack length assignment statements give me segmentation faults. Can any of you help me figure this out? What is causing these seg faults?

Here is the entire program:

#include <stdio.h>
#include <stdlib.h>
struct node 
{
    int value;
    struct node *ptr;
};

struct node *makeNode(int value, struct node *ptr)
{
    struct node *newNode = malloc(sizeof(struct node));
    newNode->value = value;
    newNode->ptr = ptr;
    return ptr;
}

typedef struct stack
{
    struct node *head;
    int length;
} stack;

stack makeStack()
{
    stack stk;
    stk.head=NULL;
    stk.length = 0;
    return stk;
}

int push(stack *stk, int data)
{
    stk->head = makeNode(data, stk->head);
    stk->length += 1;
    return data;
}

int pop(stack *stk)
{
    if (stk->length < 1)
    {
        printf("No items to pop.");
        return -1;
    }
    int data = stk->head->value;
    struct node *toBeFreed = stk->head;
    stk->head = stk->head->ptr;
    free(toBeFreed);
    stk->length -= 1;
    return data;
}

int main()
{
    stack s = makeStack();
    printf("Pushing ints one through five. Should display ints one through five on separate lines: \n");
    int i;
    for (i = 1; i <= 5; i++)
            printf("%d\n",push(&s, i));
    printf("Popping ten values. Should display ints one through five in reverse order on separate lines along with 5 error statements.\n");
    for (i = 0; i <= 10; i++)
            printf("%d\n",pop(&s));
    return 0;
}

Answer 1

struct node *makeNode(int value, struct node *ptr)
{
    struct node *newNode = malloc(sizeof(struct node));
    newNode->value = value;
    newNode->ptr = ptr;
    return ptr;
}

You want to return newNode, not ptr.

The reason you get the segfault is that due to the mistake in makeNode the stack will remain empty, however the size will be increased to 5, so when you pop the stack doesn't know it's empty and it tries to dereference a null pointer.

Answer 2

In makeNode, you are creating a new node, pointing that node at the passed in value, then returning the passed in value, rather than the new node. Since you pass in stk->head, which starts as NULL, every push will always create a new node pointed at NULL, and then return NULL, so stk->head is not changing as you expect it to. When you pop, you are trying to access NULL->ptr and NULL->value, which obviously isn't working.

If you change makeNode to:

struct node *makeNode(int value, struct node *ptr)
{
    struct node *newNode = malloc(sizeof(struct node));
    newNode->value = value;
    newNode->ptr = ptr;
    return newNode; // pass back the new node
}

it will work.

Answer 3

I suggest you add a check for NULL pointers in pop and push. The makeStack function gives me shivers, as it is returning a local variable.

Also, I advise the following changes:

struct stack * makeStack()
{
    struct stack * p_stk = 0;
    p_stk = (struct stack *) malloc(sizeof(struct stack);
    if (p_stk)
    {
      p_stk->head=NULL;
      p_stk->length = 0;
    }
    return p_stk;
}

Or

void makeStack(stuct stack * p_stack)
{
 // Initialize the stack ...
}

Answer 4

Your head pointer is not changed when you call the function makeNode. You have to make the head point to the newly created node.

Answer 5

I don't think you're returning the correct node in your makeode function. Try

ptr = newNode;

before you return.

Answer 6

sepp2k already gave the correct answer. So I'm just adding some useful advice.

One way that can help you find these kinds of problems in larger programs is a tool called valgrind. For example, if you compile:

$ gcc -Wall -Wextra -g linked_stack.c -o linked_stack

and then run:

$ valgrind ./linked_stack

You'll get the following output:

==1503== Invalid read of size 4
==1503==    at 0x80484C6: pop (linked_stack.c:62)
==1503==    by 0x8048584: main (linked_stack.c:79)
==1503==  Address 0x0 is not stack'd, malloc'd or (recently) free'd
==1503== 
==1503== Process terminating with default action of signal 11 (SIGSEGV)
==1503==  Access not within mapped region at address 0x0
==1503==    at 0x80484C6: pop (linked_stack.c:62)
==1503==    by 0x8048584: main (linked_stack.c:79)

This effectivly tells you that the statement on line 62:

int data = stk->head->value;

is trying to use an invalid pointer with the value 0x0. At that point you just need to trace back and find out why that pointer is invalid.

The extra info provided by compiling with the -g for debug symbols and then running under valgrind can really help you track down these kinds of problems in larger programs.