C Linked list - Conditional jump or move depends on uninitialised value linked list

Question

Hey guys,

so im doing this doubly linked list code, compiling works.. but executing gives me SIGSEGV. When i tried running valgrind it said that there is some uninitialised values.

My best guess would be that this is happening because malloc'd memory scope reach or smthing like.. idk maybe it gets dumped when the function ends?..im not sure, but it still says that there is some memory allocated and reachable...or maybe there is just some semantic error that im not aware of :/

valgrind --track-origins=yes out:

Conditional jump or move depends on uninitialised value(s)
==14798==    at 0x400848: push (in /home/mename/linkedlist/llist)
==14798==    by 0x40088E: main (in /home/mename/linkedlist/llist)
==14798==  Uninitialised value was created by a heap allocation
==14798==    at 0x4C2DB8F: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==14798==    by 0x400879: main (in /home/mename/linkedlist/llist)

==14798== Use of uninitialised value of size 8
==14798==    at 0x4E8476B: _itoa_word (_itoa.c:179)
==14798==    by 0x4E8812C: vfprintf (vfprintf.c:1631)
==14798==    by 0x4E8F898: printf (printf.c:33)
==14798==    by 0x400793: printlist (in /home/mename/linkedlist/llist)
==14798==    by 0x4008CD: main (in /home/mename/linkedlist/llist)
==14798==  Uninitialised value was created by a heap allocation
==14798==    at 0x4C2DB8F: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==14798==    by 0x400879: main (in /home/mename/linkedlist/llist)

==14798== Invalid write of size 8
==14798==    at 0x40071B: pop (in /home/mename/linkedlist/llist)
==14798==    by 0x4008D9: main (in /home/mename/linkedlist/llist)
==14798==  Address 0x0 is not stack'd, malloc'd or (recently) free'd

==14798== Process terminating with default action of signal 11 (SIGSEGV)
==14798==  Access not within mapped region at address 0x0
==14798==    at 0x40071B: pop (in /home/mename/linkedlist/llist)
==14798==    by 0x4008D9: main (in /home/mename/linkedlist/llist)
==14798==  The main thread stack size used in this run was 8388608.
0 -> 0 -> 0 -> 0 -> 0==14798== 
==14798== HEAP SUMMARY:
==14798==     in use at exit: 96 bytes in 4 blocks
==14798==   total heap usage: 6 allocs, 2 frees, 1,144 bytes allocated
==14798== 
==14798== LEAK SUMMARY:
==14798==    definitely lost: 0 bytes in 0 blocks
==14798==    indirectly lost: 0 bytes in 0 blocks
==14798==      possibly lost: 0 bytes in 0 blocks
==14798==    still reachable: 96 bytes in 4 blocks
==14798==         suppressed: 0 bytes in 0 blocks

edit:

added other functions and their libs (pop; clearlist; *.h) changed/updated files as answers suggested

---

clearlist.h

#ifndef CLEARLIST_H
#define CLEARLIST_H

#include "defs.h"
#include <stdlib.h>

int clearlist(node** head);

#endif

pop.h

#ifndef POP_H
#define POP_H
#include "defs.h"
#include <stdlib.h>

int pop(node** head);

#endif

printlist.h

#ifndef PRINTLIST_H
#define PRINTLIST_H

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

int printlist(node* head);

#endif

push.h

#ifndef PUSH_H
#define PUSH_H
#include <stdlib.h>
#include "defs.h"

int push(node** head, int datainput);

#endif

defs.h

#ifndef DEFS_H
#define DEFS_H

#define SUCCESS 0
#define FAIL -1
#define TRUE 0
#define FALSE -1
#define ALLOCFAIL -2
#define EMPTY -3

typedef struct Node{
    struct Node* next;
    struct Node* prev;
    int data;
} node;
#endif

main.c

#include "defs.h"
#include "clearlist.h"
#include "pop.h"
#include "printlist.h"
#include "push.h"

int main(){
    node *head;
    head = (node*) malloc(sizeof(node));

    push(&head, 10);    
    push(&head, 20);    
    push(&head, 30);    
    push(&head, 40);    

    printlist(head);

    pop(&head);

    printlist(head);

    clearlist(&head);

    return SUCCESS;
}

I will show just the functions involved until core dump which i think are responsible for the errors.

push.c

#include "push.h"

int push(node** head, int datainput){

    /* Initialization of new node */
    node* newptr = (node*) malloc(sizeof(node));    
    if(newptr == NULL){
        return ALLOCFAIL;
    }
    newptr->next = NULL;
    newptr->data = datainput;

    /* Check for empty list */
    if(head == NULL){
        newptr->prev = NULL;
        *head = newptr;
        return SUCCESS;
    }

    /* Get to the end of list*/
    node* headptr = *head;
    while(headptr->next != NULL){
        headptr = headptr->next;        
    }

    headptr->next = newptr;
    newptr->prev = headptr;
    return SUCCESS;
 }

printlist.c

#include "printlist.h"

int printlist(node* head){
    /* Check if valid node or empty list */
    if(head == NULL){
        return EMPTY;
    }

    /* Move to first node if not already */
    node* firstptr = head;
    while(firstptr->prev != NULL){
        firstptr = firstptr->prev;
    }

    /* Print entire list*/
    while(firstptr != NULL){
        if(firstptr->next != NULL){
            printf("%d -> ", firstptr->data);
        }
        else{
            printf("%d", firstptr-->data);
        }
        firstptr = firstptr->next;
    }

    return SUCCESS;
}

pop.c

#include "defs.h"
#include "pop.h"
#include <stdio.h>

int pop(node** head){

    /* If no node to pop */
    if(*head == NULL){
        return EMPTY;
    }
    /* Get to the end of list */
    node* headptr = *head;
    while(headptr->next != NULL){
        headptr = headptr->next;        
    }
    /*Pop last*/ 
    node* temp = headptr->prev;
    free(headptr);

    /* po temp - Check if deleted the only node left*/
    if(temp = NULL){
        *head = NULL;
        return EMPTY;
    }
    /* ...if not, make previous node the last node  */

    temp->next = NULL;
    headptr = NULL;

    return SUCCESS; 
}

clearlist.c

#include "clearlist.h"

int clearlist(node** head){
    if(*head == NULL){
        return SUCCESS;
    }

    /* Go to start */
    while((*head)->prev != NULL){
        *head = (*head)->prev;
    }
    /* Delete to the end */
    while(*head != NULL){
        node *prevnode = *head;
        *head = (*head)->next;
        free(prevnode);
    }

    return SUCCESS;
}

---

Thanks for all your help!

I dont really want to ask for a full solution, i want to learn something new but im a bit stuck on this one. :)

Answer 1

The problem is that mallocing doesn't initialize anything, for example:

node *head;
head = (node*) malloc(sizeof(node));

The values of the node could be anything, you need to set the pointers to NULL

head->prev = head->next = NULL;

Further, you should declare and initialize the node on a single line and don't cast the result of malloc, I'd also recommend the other sizeof mechanism. There is a more robust way to zero-initialize everything in the node if you are in C99 or later which is to use a composite literal

node* head = malloc(sizeof *head);
*head = (node){0};

Looking through the rest of your code I'm not positive if this is the same problem everywhere, but you should be following the above pattern for your own safety.

Answer 2

The problem is this:

int main(){
    node *head;
    head = (node*) malloc(sizeof(node));

    push(head, 10);

    ...

}

head is only allocated, it is not initialized!

When you pass that not initialized pointer to push,

 if(head == NULL)

will be false and the block is not going to be executed, however the next block

node* headptr = head;
while(headptr->next != NULL){
    headptr = headptr->next;        
}

is executed. Remeber head is not initialized, so headptr->next points to nowhere and you assign headptr = heatdptr->next and so on. Valgrind is telling you this: Uninitialised value was created by a heap allocation

The push function should take a double pointer to head and change where it's pointing to when a new head is created:

int push(node **head, int datainput){
   /* Initialization of new node */
   node* newptr = (node*) malloc(sizeof(node));    
   if(newptr == NULL){
       return ALLOCFAIL;
   }
   newptr->next = NULL;
   newptr->data = datainput;

   /* Check for empty list */
   if(*head == NULL){
       newptr->prev = NULL;
       *head = newptr; // change where head is pointing to
       return SUCCESS;
   }

   /* Get to the end of list*/
   node* headptr = *head;
   while(headptr->next != NULL){
       headptr = headptr->next;        
   }

   headptr->next = newptr;
   newptr->prev = headptr;
   return SUCCESS;
}

then you can call it like this:

int main(){
    node *head = NULL; // <-- important initialization

    push(&head, 10);
    push(&head, 20);
    ...
}

Also note: don't cast malloc

---

edit

The printlist has also a small errror, you are only printing the head, the correct version should be

int printlist(node* head){
    /* Check if valid node or empty list */
    if(head == NULL){
        return EMPTY;
    }

    /* Move to first node if not already */
    node* firstptr = head;
    while(firstptr->prev != NULL){
        firstptr = firstptr->prev;
    }

    /* Print entire list*/
    while(firstptr != NULL){
        if(firstptr->next != NULL){
            printf("%d -> ", firstptr->data);
        }
        else{
            printf("%d", firstptr->data);
        }
        firstptr = firstptr->next;
    }

    puts("");

    return SUCCESS;
}

Note that C does not have pass by reference, so if you want to modify a value of a variable in other function, you pass a pointer to that variable:

void foo(int *p)
{
    *p = 8;
}

void bar(void)
{
    int c = 4;

    foo(&c);

    // c is now 8
}

That same applies to pointers, if you want to change where a pointer is pointing to in another function, you have to pass a pointer to the pointer (aka double pointer):

void foo(char **str)
{
    *str = "World";
}

void bar(void)
{
    char *x = "Hello";
    puts(x); // prints Hello

    foo(&x);

    // x points now to a different string literal

    puts(x); // print World
}

That's what I'm doing in push.

To prove that this is correct, see this: https://ideone.com/As5XDy

I've used my push function (and the fix of printlist) and the output is

10 -> 20 -> 30 -> 40

Also don't forget to write a function that frees the memory.