What is root cause for segmentation fault for below linked list program?

Question

Below is the Program to add a new node to the ascending order linked list.

There was bug in below program which causing segmentation Fault I figured out the cause for segmentation Fault using gdb.

But i did not get what is reason for segmentation Fault. Can anyone tell reason for segmentation Fault.

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

  struct node
 {
     int data ;
     struct node *link ;
 } ;

 void add ( struct node **, int ) ;
 void display ( struct node * ) ;

 int  main( )
{
       struct node *p ;
        p = NULL ;  

    add ( &p, 5 ) ;
    add ( &p, 1 ) ;
    add ( &p, 6 ) ;
    add ( &p, 4 ) ;
    add ( &p, 7 ) ;


    display ( p ) ;

}


void add ( struct node **q, int num )
{
    struct node *r, *temp = *q ;

    r = ( struct node *)  malloc ( sizeof ( struct node ) ) ;
    r -> data = num ;


  if ( *q == NULL || ( *q ) -> data > num )
 {
    *q = r ;
    ( *q ) -> link = temp ;
 }
 else
 {
    while ( temp != NULL )
    {
        if ( temp -> data <= num && ( temp -> link -> data > num || 
                                    temp -> link == NULL ))
        {
            r -> link = temp -> link ;
            temp -> link = r ;
            return ;
        }
        temp = temp -> link ;  
    }
  }
}


void display ( struct node *q )
{
    printf ( "\n" ) ;


    while ( q != NULL )
    {
        printf ( "%d ", q -> data ) ;
       q = q -> link ;
    }
}

I changed the order in this line from

if ( temp -> data <= num && ( temp -> link -> data > num || temp -> link == NULL ))
//                          ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

to

if ( temp -> data <= num && ( temp -> link == NULL || temp -> link -> data > num  ))
//                          ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

The above changed work like a charm But i dint get reason behind this changes.

So help me to figure out the reason

**Updated

If short-circuit evalution is real cause then why this below program works

      int main()
     {

       int a=10,b=1,c=0;
       int d;
       d = (a && (c || b));

       printf("%d",d);
      getchar();
      }

ya gdb is used to debug and its stopped @ above changed line — vinay hunachyal, Aug 11 '14 at 10:24
@pmg in the case int main() { int a=10,b=1,c=0; int d; d = (a && (c || b)); printf("%d",d); getchar(); } in that case this program should yield 0 right? — vinay hunachyal, Aug 11 '14 at 10:24
If `( *q ) -> data > num )` is true then you reassign `*q` to point to your new node, but what happens to the list already pointed to by `*q`? — Some programmer dude, Aug 11 '14 at 10:26
You are dereferencing `temp -> link` without checking it for NULL and thus a segfault. In second case, you check it for NULL, and if it is NULL, [dereferencing is not done](http://en.wikipedia.org/wiki/Short-circuit_evaluation). — Mohit Jain, Aug 11 '14 at 10:26
Also, [don't cast the return of `malloc`](http://stackoverflow.com/questions/605845/do-i-cast-the-result-of-malloc). — Some programmer dude, Aug 11 '14 at 10:30
The working program you added in your edit works because the expression `c` doesn't dereference a `NULL` pointer. — Some programmer dude, Aug 11 '14 at 10:34

Some programmer dude · Answer 1 · 2014-08-11T10:38:12.627

The expression

temp -> link -> data > num || temp -> link == NULL

will first evaluate the left hand side of the logical or, and if it's false then the right hand side will be evaluated. That means if temp->link is NULL then you have undefined behavior as you dereference a NULL pointer.

What the change does is that it changes the evaluation order of the two sub-expressions in the logical or expression, so it first check temp->link not being NULL, and then dereferences temp->link.

score 1 · Answer 2 · answered Aug 11 '14 at 10:40

When you do like this-

if ( temp -> data <= num && ( temp -> link -> data > num || temp -> link == NULL ))

In temp -> link -> data, If temp -> link is equal to or when temp -> link is NULL means this expression becomes NULL -> data. you are trying to dereferencing NULL. so you will get segmentation fault.

if ( temp -> data <= num && ( temp -> link == NULL || temp -> link -> data > num  ))

In this case you won't get segmentation fault. because when temp -> link is NULL condition becomes true, Program execution enters into the body of the loop. So you wont get segmentation fault here. But when temp -> link is not NULL then it will dereference it.

score 0 · Answer 3 · answered Aug 11 '14 at 10:27

0

In the second version of the if statement, short-circuit evaluation will make sure that temp->link is never dereferenced.

answered Aug 11 '14 at 10:27

Tom Moers

1,243
8
13

What is root cause for segmentation fault for below linked list program?

3 Answers3