Segfault when attempting to nullify a pointer in C

Question

So right now I'm trying to implement a deltaclock, and the first step that I'm trying is to first make a priority queue which uses a double-linked list (I will do the other deltaclock stuff later). The first element to be popped from the priority queue is the one that is at the root of the linked list (or the deltaClock struct).

I push a few elements onto the queue in my test, and after a few pop operations, there is one case in which it segfaults when it's popping from a nearly empty list.

When I comment out the line in the pop method where I say "clock->root->previous = 0;", the program in the main method does not segfault when I pop off elements. However, the pointer to the previous node needs to be gotten rid of since the previous node will not exist anymore.

How can I make it so that the new root's previous pointer will be null when I perform the pop operation?

#include <stdio.h>
#include <stdlib.h>

struct deltaNode{
    int tics;                  // source
    struct deltaNode* next;
    struct deltaNode* previous;
};

struct deltaClock{
    struct deltaNode* root;
    struct deltaNode* tail;
    int size;
};

void initDeltaClock(struct deltaClock **clock){
    (*clock) = malloc(sizeof(struct deltaClock));
    (*clock)->size = 0;
}

void push(struct deltaClock* clock, int numberOfTics){
if(clock->root == 0){
    // root is empty, initialize it.
    clock->root = malloc(sizeof(struct deltaNode));
    clock->root->tics = numberOfTics;
    clock->tail = clock->root;
} 
else {
    struct deltaNode* newNode = malloc(sizeof(struct deltaNode));
    newNode->tics = numberOfTics;
    struct deltaNode* temp = clock->root;

    if(newNode->tics < temp->tics){
        clock->root->previous = newNode;
        newNode->next = clock->root;
        clock->root = newNode;
    } else {
        while(newNode->tics > temp->tics){
            if(temp->next == 0){
                break;
            }
            temp = temp->next;
        }

        if(temp->next == 0 && newNode->tics > temp->tics){
            clock->tail->next = newNode;
            newNode->previous = clock->tail;
            clock->tail = newNode;
        }
        else{
            temp->previous->next = newNode;
            newNode->previous = temp->previous;
            newNode->next = temp;
            temp->previous = newNode;
        }

    }

}
clock->size++;
}

int pop(struct deltaClock* clock){
    struct deltaNode* temp = clock->root;
       if(temp == 0){
        return -1;
    }
    int result = temp->tics;
    clock->root = clock->root->next;
    clock->root->previous = 0;
    free(temp);
    clock->size--;
    return result;
}

void printClock(struct deltaClock* clock){
    struct deltaNode* iterator;
    iterator = clock->root;
    while(iterator != 0){
            printf("\n%d",iterator->tics);
            iterator = iterator->next;
    }
}


int main(int argc, char* argv[]){
    printf("\nHello world.");
    struct deltaClock* clock;
    initDeltaClock(&clock);
    push(clock, 3);
    push(clock, 2);
    push(clock, 7);
    push(clock, 33);
    push(clock, 221);
    push(clock, 5);
    printClock(clock);
    printf("\npopping %d",pop(clock));
    printf("\npopping %d",pop(clock));
    printf("\npopping %d",pop(clock));
    printf("\npopping %d",pop(clock));
    printf("\npopping %d",pop(clock));
    printf("\npopping %d",pop(clock));
    printf("\npopping %d",pop(clock));
    printf("\npopping %d",pop(clock));
    printf("\npopping %d",pop(clock));
    printf("\npopping %d",pop(clock));
    printf("\npopping %d",pop(clock));
    printf("\npopping %d",pop(clock));
    push(clock, 25);
    printf("\npopping %d",pop(clock));
    printf("\n");
}

Answer 1

In addition to the other advice given, when dealing with pointers, it's a good idea to always initialize them to NULL or to their final value, don't leave them dangling.

For example, in initDeltaClock, (*clock)->root and (*clock)->tail are not initialized. This means that in the first push call, even the check for if (clock->root == 0) will be invalid, since clock->root has not been initialized to 0.

Here's a suggested improvement:

void initDeltaClock(struct deltaClock **clock){
    (*clock) = calloc(sizeof(struct deltaClock));  /* <-- zero out entire contents after alloc */
}

The same applies to structs which are malloc'ed in push, you could use calloc instead of malloc to ensure that the blocks returned are cleared to zero, or you should set the struct's pointers to zero explicitly.

Also, if this is more than a toy project, always check the return value of allocation functions to check for out of memory errors.

Answer 2

For what it's worth, this code runs reasonably sanely:

#include <stdio.h>
#include <stdlib.h>

struct deltaNode
{
    int tics;                  // source
    struct deltaNode *next;
    struct deltaNode *previous;
};

struct deltaClock
{
    struct deltaNode *root;
    struct deltaNode *tail;
    int size;
};

void initDeltaClock(struct deltaClock * *clock);

void initDeltaClock(struct deltaClock * *clock)
{
    (*clock) = malloc(sizeof(struct deltaClock));
    (*clock)->size = 0;
}

void push(struct deltaClock *clock, int numberOfTics);

void push(struct deltaClock *clock, int numberOfTics)
{
    if (clock->root == 0)
    {
        // root is empty, initialize it.
        clock->root = malloc(sizeof(struct deltaNode));
        clock->root->tics = numberOfTics;
        clock->tail = clock->root;
    }
    else
    {
        struct deltaNode *newNode = malloc(sizeof(struct deltaNode));
        newNode->tics = numberOfTics;
        struct deltaNode *temp = clock->root;

        if (newNode->tics < temp->tics)
        {
            clock->root->previous = newNode;
            newNode->next = clock->root;
            clock->root = newNode;
        }
        else
        {
            while (newNode->tics > temp->tics)
            {
                if (temp->next == 0)
                    break;
                temp = temp->next;
            }

            if (temp->next == 0 && newNode->tics > temp->tics)
            {
                clock->tail->next = newNode;
                newNode->previous = clock->tail;
                clock->tail = newNode;
            }
            else
            {
                temp->previous->next = newNode;
                newNode->previous = temp->previous;
                newNode->next = temp;
                temp->previous = newNode;
            }
        }
    }
    clock->size++;
}

int pop(struct deltaClock *clock);

int pop(struct deltaClock *clock)
{
    struct deltaNode *temp = clock->root;
    if (temp == 0)
        return -1;
    int result = temp->tics;
    clock->root = clock->root->next;
    if (clock->root != 0)
        clock->root->previous = 0;
    free(temp);
    clock->size--;
    return result;
}

void printClock(struct deltaClock *clock);

void printClock(struct deltaClock *clock)
{
    struct deltaNode *iterator;
    iterator = clock->root;
    while (iterator != 0)
    {
        printf(" %d", iterator->tics);
        iterator = iterator->next;
    }
    putchar('\n');
}

int main(void)
{
    printf("Hello world.\n");
    struct deltaClock *clock;
    initDeltaClock(&clock);
    push(clock, 3);
    push(clock, 2);
    push(clock, 7);
    push(clock, 33);
    push(clock, 221);
    push(clock, 5);
    printClock(clock);
    printf("popping %d\n", pop(clock));
    printf("popping %d\n", pop(clock));
    printf("popping %d\n", pop(clock));
    printf("popping %d\n", pop(clock));
    printf("popping %d\n", pop(clock));
    printf("popping %d\n", pop(clock));
    printf("popping %d\n", pop(clock));
    printf("popping %d\n", pop(clock));
    printf("popping %d\n", pop(clock));
    printf("popping %d\n", pop(clock));
    printf("popping %d\n", pop(clock));
    printf("popping %d\n", pop(clock));
    push(clock, 25);
    printf("popping %d\n", pop(clock));
    printf("\n");
}

It produces:

Hello world.
 2 3 5 7 33 221
popping 2
popping 3
popping 5
popping 7
popping 33
popping 221
popping -1
popping -1
popping -1
popping -1
popping -1
popping -1
popping 25

The primary change is not setting clock->root->previous = 0; unless clock->root is not null.

Secondary changes are adding newlines to the end of the print statements, and removing them from the beginning. And the list is printed horizontally, multiple numbers per line, rather than one number per line.

The code shown compiles cleanly using:

gcc -O3 -g -std=c11 -Wall -Wextra -Wmissing-prototypes -Wstrict-prototypes \
    -Wold-style-definition pl.c -o pl

The function declarations are needed to compile cleanly with those options; they're a good idea in general. The alternative is to make the functions all static, which also works for single-file programs. The only changes needed to make the code compile cleanly were adding the function prototypes and replacing main(int argc, char **argv) with main(void) — well done, that's unusually good.