Odd NULL pointer behavior

Question

I'm attempting to implement a stack using a linked list. My stack constructor createStack() creates an empty (dummy) Element and returns a double pointer to that element (top of stack). My push() method checks if the stack has a dummy element; if it does it fills the dummy and returns, otherwise it allocates memory for a new element and does the necessary pointer updates.

The problem I have is that my *stack->next pointer apparently points to NULL (0x0) as it should, and then two lines later it doesn't equal NULL (0x17) but somehow passes the NULL test. Inside the call to push it equals (0x17) again but this time it fails the NULL test, as it should.

So my question is, what the heck is going on with this pointer? How/why did it change from (0x0) to (0x17), and if it equals (0x17) how did it pass the ==NULL test??

//main.c
int main () {

    struct Element **stack;

    stack = createStack();

    printf("stack: %p\n", stack );

    printf("*stack->next: %p\n", (*stack)->next );

    if ( (*stack)->next == NULL )
        printf("yes the pointer is null\n" );

    printf("*stack->next: %p\n", (*stack)->next );

    if ( (*stack)->next == NULL )
        printf("yes the pointer is null\n" );

    push ( stack, 1000 );

//stack.c

struct Element {
    int value;
    struct Element *next;
};

int push ( struct Element **stack, int el ) {

    if ( (*stack)->next == NULL) {
        // first element, fill dummy element and return
        printf("first value: %i !", el);
        (*stack)->value = el;
        return 1;
    }

    printf("the pointer is not null\n");

    struct Element *newElement = malloc( sizeof( struct Element ) );

    if ( !newElement )
        return -1;

    newElement->value = el;

    //add element to front of list
    newElement->next = *stack;

    //update pointer to new first element
    *stack = newElement;

    return 1;
}

struct Element** createStack() { 

    struct Element *dummy = malloc( sizeof( struct Element ) );

    if (dummy == NULL )
        printf("malloc failed...");

    dummy->value = 99;
    dummy->next = NULL;

    struct Element **stack;

    stack = &dummy;

    return stack;
}

The code above produces the following output:

stack: 0x7fff6c385ba8
*stack->next: 0x0
yes the pointer is null
*stack->next: 0x17
yes the pointer is null
the pointer is not null

Answer 1

In the createStack function you are returning the address of a local variable which leads to undefined behaviour:

struct Element** createStack() {

        struct Element *dummy = malloc( sizeof( struct Element ) );    
        ...
        struct Element **stack;    
        stack = &dummy;    
        return stack;
}

Instead you can just have a pointer to struct Element in main and return the pointer to the newly created node from the createStack function:

struct Element *stack = createStack();

And pass the address of the pointer stack to the ush function:

push ( &stack, 1000 );

Answer 2

The variable dummy within createStack() ceases to exist when that function returns - so the pointer that you return points at a variable which doesn't exist anymore.

This is why you see the odd behaviour - printf() is likely writing over the memory that formerly contained dummy, so when you try to examine that memory via your dangling pointer, you see it change unexpectedly.

You can fix the code by changing createStack() to return a struct Element * value:

struct Element *createStack(void)
{  
    struct Element *dummy = malloc( sizeof( struct Element ) );

    if (dummy == NULL )
        printf("malloc failed...");
    else {
        dummy->value = 99;
        dummy->next = NULL;
    }

    return dummy;
}

and changing main() to suit (push() can remain unchanged):

int main ()
{
    struct Element *stack;

    stack = createStack();

    printf("stack: %p\n", stack );

    printf("stack->next: %p\n", stack->next );

    if ( stack->next == NULL )
        printf("yes the pointer is null\n" );

    printf("stack->next: %p\n", stack->next );

    if ( stack->next == NULL )
        printf("yes the pointer is null\n" );

    push ( &stack, 1000 );

Answer 3

Forget for a moment that you're working with pointers and pointers-to-pointers, and suppose your createStack() routine looked like this:

int *createInt() {
    int dummy = 1;
    return &dummy;
}

The function allocates (temporary) space on the stack for the local variable dummy, assigns it a value, and then returns a pointer to it. This is exactly what your createStack() does, except that your dummy happens to be a more complicated data type.

The problem is that the memory allocated to dummy itself is released when the function returns and pops its local variables off the stack. So the function returns a pointer to memory that has become available for re-use. It then can (and does) change as data is pushed and popped from the stack during subsequent function calls.