Crash in C program while retrieving an item from a stack.

Question

The following code crashes on the second Pop() call. I'm a novice with C and I've been staring at this code now for over an hour and i can't see the error. Any ideas to help me out on why this code is crashing?

#include <stdio.h>

#define StackDataSize 100

typedef struct Stack
{
    int index;
    void *data[StackDataSize];
} Stack;

void* Pop(Stack *s)
{
    if(s->index >= 0)
    {
        return s->data[s->index--];
    }
    else
    {
        fprintf(stderr, "ERROR: Stack Empty\n");
        return NULL;
    }
}

void Push(Stack *s, void *v)
{
    if(s->index < StackDataSize)
    {
        s->data[++s->index] = v;
    }
    else
    {
        fprintf(stderr, "ERROR: Stack Full\n");
    }
}

int main(void)
{
    Stack s = {-1}, *intstack = &s;

    int x = 123456;
    Push(intstack, &x);

    printf("%d\n", *(int*)Pop(intstack));
    printf("%d\n", *(int*)Pop(intstack));

    return 0;
}

Answer 1

Is the "index" member signed or unsigned? If its unsigned, then the expression "s->index--" will result in a very large number.

Answer 2

You're trying to dereference the NULL you return in the empty case.

Answer 3

The second pop tries to pop from an empty stack, and the Pop() function returns NULL. Then the main function tries to dereference this NULL-pointer and print the value that it's pointing to.

Since the NULL-pointer doesn't point to anything valid you get a segmentation fault.

Answer 4

On the second Pop, the stack is empty, and Pop returns NULL if the stack is empty.

So in the second line:

printf("%d\n", *(int*)Pop(intstack));

you are dereferencing NULL as a pointer to an int.

printf("%d\n", *(int*)NULL );

Answer 5

The second call to Pop returns NULL, which you then cast to int * and try to dereference. Dereferencing NULL results in a segfault.

Answer 6

To echo all the previous answers, the problem is that the second call to Pop returns NULL, which you try to dereference in the second call to printf().

On a purely informational note, with array-based stacks, it's a little easier if you grow from the top to the bottom, rather than the other way around:

void Push(Stack *s, void *v)
{
  if (s->index)
    s->data[--s->index] = v;
  else
    // overflow
}

void *Pop(Stack *s)
{
  if (s->index < StackDataSize)
    return s->data[s->index++];
  else
  {
    // underflow
    return NULL;
  }
}
...
Stack s = {StackDataSize, {NULL}};

This way 0 doesn't become a special case.

Answer 7

While I look at your code, I see another issue that would also cause a crash: I think you've got an "off by one" error on the Push() as well, here:

void Push(Stack *s, void *v)
{
    if(s->index < StackDataSize)
    {
        s->data[++s->index] = v;
    }
    ...

Checking s->index < StackDataSize, then doing a pre-increment ++s->index and writing to s->data will write one past the end of the array if s->index == StackDataSize - 1. That would also give you a segmentation fault.