Find Loop in the linklist (getting Segmentation falut)

Question

This solution is based on a very important observation about computers. A pointer size in my system is 8 bytes. size of the this structure

 struct ll1
 {  
  int data;
  struct ll1 *next;
 };

is 16 bytes. As a structure pointer with more that one members, will always have some trailing zeros. This is due to memory alignment. So i m trying to use that remaining 4 byte to store the visited flag. when i assigns 0 to that four bytes it doesn't gives error but when i assign value other than zero it gives a segmentation fault in the below code. plz Anyone explain why this happens ?

#include<stdio.h>
#include<stdlib.h>
struct ll1
{
    int data;
    struct ll1 *next;
};
typedef struct ll1 ll;

void create(ll **root)
{

int t=1;
printf("\nEnter node value 0 if end:");
    scanf("%d",&t);
    if(t)
    {
        (*root)=(ll*)malloc(sizeof(ll))    ;
        (*root)->data=t;
        create(&(*root)->next); 
    }
    else
    (*root)=NULL;
}
int main()
{

    ll *node;
    create(&node);
    ll *temp=node,*temp2=node;
int j,size=0;

/*printing 4-4 bytes of the node */
while(temp->next)
{
    size++;
    int *p=(int *)temp;
    printf("\n%d %d %d %d",*(p),*(p+1),*(p+2),*(p+3));
    *(p+3)=0; // setting the value of last four byte zero
    temp=temp->next;

} 
printf("\n");

j=size/3;

/* making loop in the linklist */

while(j--)temp2=temp2->next;
temp=node;

while(temp->next!=NULL)temp=temp->next;
temp->next=temp2;   

/*loop created */



/* code for finding loop in the linklist */
printf("\nfinding loop in the linklist\n");
ll *root=node;  
int *pp=(int *)root;
printf("%d %d %d %d\n",*(pp),*(pp+1),*(pp+2),*(pp+3));
printf("%d \n",root->data);
while(*(pp+3)==0) 
{

    *(pp+3)=1; //when changed that line by *(pp+3)=0 it doesn't give any error 
    root=root->next; //move pointer to next
    pp=(int *)root;  // assign adress to integer pointer
    printf("%d %d %d %d\n",*(pp),*(pp+1),*(pp+2),*(pp+3));  // segmentation fault is here 
    printf("%d \n",root->data);
}
printf("%d \n",root->data);
return 0;

}

Ouput in GDB

(gdb) r 
Starting program: /home/kushagra/place/linklist/a.out <ll_in

Enter node value 0 if end:1
Enter node value 0 if end:2
Enter node value 0 if end:3
Enter node value 0 if end:4
Enter node value 0 if end:5
Enter node value 0 if end:6
Enter node value 0 if end:7
Enter node value 0 if end:8
Enter node value 0 if end:8
Enter node value 0 if end:0
1 0 6299696 0
2 0 6299728 0
3 0 6299760 0
4 0 6299792 0
5 0 6299824 0
6 0 6299856 0
7 0 6299888 0
8 0 6299920 0
8 0 6299952 0

finding loop in the linklist
1 0 6299696 0
1 

Program received signal SIGSEGV, Segmentation fault.
0x0000000000400a2e in main () at P_node.c:72
72          printf("%d %d %d %d\n",*(pp),*(pp+1),*(pp+2),*(pp+3));  // segmentation fault is here

Why rely on byte alignment this way? Just add another field to track visited? — Karthik T, Jun 20 '13 at 08:59
@ Karthik T-ya that will work,but why getting error in this code..?? — Kushagra Jaiswal, Jun 20 '13 at 09:02
Am not sure of that.. Have you tried running it with `gdb`, or some similar debugger? — Karthik T, Jun 20 '13 at 09:06
ya i tried thats the output `Program received signal SIGSEGV, Segmentation fault. 0x0000000000400a2e in main () at P_node.c:72 72 printf("%d %d %d %d\n",*(pp),*(pp+1),*(pp+2),*(pp+3)); // segmentation fault is here (gdb)` — Kushagra Jaiswal, Jun 20 '13 at 09:09
[Don't cast the return value of `mallo()` in C](http://stackoverflow.com/a/605858/28169). Not even in C this crazy. — unwind, Jun 20 '13 at 09:22

score 6 · Accepted Answer · answered Jun 20 '13 at 09:07

6

It doesn't have 'trailing zeros'. It probably has 4 unused bytes between the int and the pointer.

This *(pp+3)=1 probably modifies four bytes within the pointer.

Use:

struct ll1
 {  
  int data;
  int visited;
  struct ll1 *next;
 };

answered Jun 20 '13 at 09:07

Henrik

23,186
6
42
92

I will give you +1 if you check/show whether `*(pp+3)=1` really changes the pointer. – Jun 20 '13 at 09:18
2

@Armin: Henrik is right. Just test it on a single instance of your struct. (pp+3) points to the 3rd integer from the start of the struct and this places it in the variable named next... – Malkocoglu Jun 20 '13 at 09:28
1

@Malkocoglu In the second line he is talking about the OP's struct example. And he says probably. I just wanted to be more sure than that. – Jun 20 '13 at 09:30
1

@all - Henrik is right,this code is not giving segfault after i replaced that line `*(pp+3)` by `*(pp+1)` .thanx a ton Henrik. – Kushagra Jaiswal Jun 20 '13 at 09:33
1

@Armin I said probably to emphasize that it's not a good idea to rely on the exact struct layout just to save a few bytes. – Henrik Jun 20 '13 at 09:45

score 1 · Answer 2 · answered Jun 20 '13 at 09:12

1

You are not checking if you have reached the end of the Linked list. You should also check for it.

while(*(pp+3)==0 && root->next)

answered Jun 20 '13 at 09:12

Karthik T

31,456
5
68
87

there is a loop in the linklist so `root->next` is not required. – Kushagra Jaiswal Jun 20 '13 at 09:13
Ah I see you are creating one on purpose. Have you checked if that works as expected? – Karthik T Jun 20 '13 at 09:15
everything is running well except segmentation fault in the line `*(pp+3)=1`.as u can see the output – Kushagra Jaiswal Jun 20 '13 at 09:20
@user2484070 this is a wild shot, but have you tried to display the list after creating the loop? – Karthik T Jun 20 '13 at 09:22

Find Loop in the linklist (getting Segmentation falut)

2 Answers2