Why am I getting a seg fault with this code? Should be simple?

Question

I'm at a complete loss. I feel like there must be some glaring, stupidly easy mistake here, and my eyes are just too tired to see it. I'd really appreciate any help.

When I run testProb2, the program prints "Pushing:" and then on the next line, "Segmentation fault". I find this really weird, because the next thing after printf("Pushing:\n"); is another call to printf with just a static argument being passed, nothing dynamic that could be doing weird crazy things in some other method, and yet "1 " does not get printed.

I put the call to printf for 1 and 2 in there just as a test, because I initially thought that the problem might be in my first for loop, which is commented out right now, but that's not it. As I said, I believe the problem to be in testProb2.c, but I included stackli.h and stackli.c below it just in case. I'm compiling this with "gcc -ansi stackli.c testProb2.c -o testProb2".

/* testProb2
 * 
 * Demonstrates a stack implementation that allocates a number of nodes at creation of the stack
 * rather than on each call to Push. All methods are O(1) except for GrowFreeList, which is O(n),
 * and CreateStack, which is O(n) because it calls GrowFreeList, and possibly Push, which will be
 * O(1) when called while there are empty nodes, but O(n) when called if there are not empty nodes.
 */

#include "stackli.h"
#include <stdio.h>

int main(void) {
    Stack S;
    int i;

    S = CreateStack(8);

    printf("Pushing:\n");
    printf("1 ");
    Push(1, S);
    printf("2\n");
    Push(2, S);
                /*
                for (i = 0; i < 10; i++) {
                    printf("%d...", i);
                    Push(i, S);
                }
                printf("]\n");
                */

    printf("Popping:\n");
    while (!IsEmpty(S)) {
        printf("%d...", Top(S));
        Pop(S);
    }
    printf("]");
    DisposeStack(S);
}
/* stackli.h */

    typedef int ElementType;

    #ifndef _Stack_h
    #define _Stack_h

    struct Node;
    struct StackRecord;
    typedef struct Node *PtrToNode;
    typedef struct StackRecord *Stack;

    Stack CreateStack( int initialSize );
    void GrowFreeList( Stack S );
    int IsEmpty( Stack S );
    int IsFull( Stack S ) ;
    void MakeEmpty( Stack S );
    void DisposeStack( Stack S );
    void Push( ElementType X, Stack S );
    ElementType Top( Stack S );
    void Pop( Stack S );


    #endif  /* _Stack_h */
/* stackli.c */

#include "stackli.h"
#include "fatal.h"
#include <stdlib.h>

struct StackRecord {
    PtrToNode ThisStack;
    PtrToNode FreeNodes;
    int Size;
};

struct Node {
    ElementType Element;
    PtrToNode   Next;
};

/* O(n) instead of O(1) because it calls GrowFreeList which is O(n) */
Stack CreateStack(int initialSize) {
    Stack S;
    S = malloc( sizeof( struct StackRecord ) );
    S->ThisStack = NULL;
    S->FreeNodes = NULL;
    S->Size = initialSize;            
    GrowFreeList(S);
    return S;
}

/* O(n) function */
void GrowFreeList(Stack S) {
    int i;
    PtrToNode temp;

    for (i = 0; i < S->Size; i++) {
        temp = malloc( sizeof( struct Node) );
        if (temp == NULL)
            FatalError("Out of space!!");
        temp->Next = S->FreeNodes;
        S->FreeNodes = temp;
    }
    S->Size = S->Size * 2;
}

Answer 1

As others are saying, you should use fprintf(stderr,...) to print debug messages.

You can use gdb to see where the problem is and see what's going on in memory. Add the flag -g when compiling to help with debugging in gdb.

This is the output gdb gave me:

(gdb) r
Starting program: .../test 
Pushing:
1 2
2

Program received signal SIGSEGV, Segmentation fault.
0x0000000000400873 in Push (X=1, S=0x601010) at stackli.c:81
81      temp->Next = S->ThisStack->Next;
(gdb) bt
#0  0x0000000000400873 in Push (X=1, S=0x601010) at stackli.c:81
#1  0x0000000000400627 in main () at testprob2.c:20
(gdb) print temp
$1 = (PtrToNode) 0x601110
(gdb) print S->ThisStack
$2 = (PtrToNode) 0x0

The error is occurring in void Push( ElementType X, Stack S ).

As you can see when we print out S->ThisStack we get 0x0, ie. S->ThisStack is pointing to NULL. When you dereference S->ThisStack to get to S->ThisStack->Next you'll get a segmentation fault.

You could add a check for if (S->ThisStack == NULL). I'm not really sure with the way you're going about creating a stack structure.

Also note, this is only one problem with your code, there are potentially (and most likely) a lot more problems, however you should be able to narrow them down with gdb using the backtrace (bt) command, and printing to stderr as opposed to stdout so that your output is not buffered. I don't want to do your homework for you.

Answer 2

Okey doke ... here we go:

You initialize your Stack S with CreateStack(8). This sets ThisStack to NULL inside the struct. Then the first thing you so is call Push(1,S) in which you do ...

temp->Next = S->ThisStack->Next;

Kaboom. You just dereferenced a NULL pointer.

Ideally you want to get familiar with using the debugger (gdb). This will let you step through the execution of your code see exactly where it's blowing up.

Answer 3

The comments about flushing are correct. The problem is in the second to last line of Push. You never initialized ThisStack, so when you try to access its next element you get a segfault. Incidentally, you size is off because you double it after filling it for the first time. Finally, you should try to avoid typedefing away pointers. It's too easy to forget what's a pointer and what's not. Make stack the full struct and declare pointers to it.

Answer 4

The problem is in the last two lines of Push:

void Push( ElementType X, Stack S ) {
    PtrToNode temp;
    ...
    temp->Next = S->ThisStack->Next;
    S->ThisStack = temp;
}

When you first call Push, the ThisStack field is null. When you try to dereference it to access its Next field, you are getting a segfault. However, since the top of the stack is in ThisStack, not ThisStack->next, fixing that problem will get rid of the segfault.

void Push( ElementType X, Stack S ) {
    PtrToNode temp;
    ...
    temp->Next = S->ThisStack;
    S->ThisStack = temp;
}

You make the same mistake in Pop, which would cause you to entirely skip the first element. The assignment to temp should be like this:

temp = S->ThisStack;

Finally, your Size field will always be wrong. It appears that GrowFreeList is supposed to double the size of the stack when it is called, but when you call it from CreateStack, your stack's real size is 0 although the Size field is 8 (in your example). The result is that the stack contains 8 free nodes, but its Size field is 16. In fact, the Size field will always be larger than the actual size by the initial size. This doesn't cause any problems now, since it is only used to determine how many to add, but the fix is simple: reset the Size field after calling GrowFreeList from CreateStack:

Stack CreateStack(int initialSize) {
    Stack S;
    ...
    S->Size = initialSize;
    GrowFreeList(S);
    S->Size = initialSize; // Reset size, since GrowFreeList changed it
    return S;
}