Segmentation Faults in Treap Code

VTU (Vishveshwaraya Technological University)

SJCE - Computer Science and Engineering Department

Why does a Segmentation Fault occur in Unix/Linux Systems? (or why it does not happen in Turbo C).

Statements like the below from GDB,
Program received signal SIGSEGV, Segmentation fault.
0x0000000000400e99 in insertInLeaf ()
Current language: auto; currently asm
are common.

Segmentation fault occurs mainly due to following known facts:
a) Occurs when a previliged memory location is accessed by the program.
b) Occurs when a NULL pointed object's member is accessed (like, node->info is meaningful, while NULL->info is meaningless).
c) Occurs when the program runs into an infinite loop, the Unix based systems generate a segmentation fault in such cases.

This blog on segmentation fault will be updated shortly.

Just send the fault producing program and we too will try debugging them.

Also visit my another blog and a blog on Namma Mysooru.

There are 2 or more segmentation faults in the below treap (tree + heap) codes.

You need to debug those segmentation faults.

Program 1:
#include <stdio.h>
#include<time.h>
#include<stdlib.h>
#include<unistd.h>
struct nodes
{
int key,priority;
struct nodes *f;
struct nodes *left;
struct nodes *right;
};
typedef struct nodes *node;
node root;
node getnode()
{
node p;
p=(struct nodes *)calloc(1,sizeof(struct nodes));
p->key=(random()%100);
p->f=p->left=p->right=NULL;
p->priority=(random()%100);
return (p);
}

void left_rotate(node p)
{
if(p!=NULL)
{
node q=p->right;
p->right=q->left;
q->f=p->f;
if(p->f==NULL)
root=q;
else if(p==(p->f)->left)
(p->f)->left=q;
else
(p->f)->right=q;
q->left=p;
p->f=q;
}
}
void right_rotate(node p)
{
if(p!=NULL)
{
node q=p->left;
p->left=q->right;
q->f=p->f;
if(p->f==NULL)
root=q;
else if(p==(p->f)->right)
(p->f)->right=q;
(p->f)->left=q;
q->right=p;
p->f=q;
}
}
void insert_fix_up(node p)
{
while((p->f!=NULL)&&((p->priority) < (p->f->priority)))
{
if(p==(p->f)->left)
right_rotate(p->f);
else
left_rotate(p->f);

}
while(root->f!=NULL)
root=root->f;
}
node insert()
{
node p,q,r;
unsigned long int n,i;
printf("Enter the number of elements to be inserted:");
scanf("%ld",&n);
for (i=0;i < n;i++)
{
p=getnode();
q=NULL;
r=root;
while(r!=NULL)
{
q=r;
if ((p->key) < (r->key))
r=r->left;
else
r=r->right;
}
p->f=q;
if(q==NULL)
root=p;
else if((p->key) < (q->key))
q->left=p;
else
q->right=p;
insert_fix_up(p);
}
}
void display(node p,int level)
{
int i;
if(p==NULL)
return;
display(p->right,level+1);
for(i=0;i < level;i++)
printf("R# %d:%d \n",p->key,p->priority);
else
printf("L# %d:%d \n",p->key,p->priority);
display(p->left,level+1);
}

int main(void)
{
int ch;
int j;
j=1;
root=NULL;
while(j)
{
printf("1:insert\t2:display\nEnter your choice:");
scanf("%d",&ch);
switch(ch)
{
case 1: insert();
break;
case 2: display(root,1);
break;
case 4: j=0;
break;
default: printf("enter correct option\n");
break;
}
}
return(1);
}




Program 2:
#include<stdio.h>

#include<time.h>
#include<stdlib.h>
#include<unistd.h>
struct nodes
{
int key,priority;
struct nodes *f; // father (parent ;) )
struct nodes *left;
struct nodes *right;
};
typedef struct nodes *node;
node root;
node getnode()
{
node p;
p=(struct nodes *)calloc(1,sizeof(struct nodes));
p->key=(random()%100);
p->f=p->left=p->right=NULL;
p->priority=(random()%100);
return (p);
}

void left_rotate(node p)
{
if(p!=NULL)
{
node q=p->right;
p->right=q->left;
//(q->f)->left=p;
q->f=p->f;
if(p->f==NULL)
root=q;
else if(p==(p->f)->left)
(p->f)->left=q;
else
(p->f)->right=q;
q->left=p;
p->f=q;
}
}

void right_rotate(node p)
{
if(p!=NULL)
{
node q=p->left;
p->left=q->right;
//(q->f)->right=p;
q->f=p->f;
if(p->f==NULL)
root=q;
else if(p==(p->f)->right)
(p->f)->right=q;
else
(p->f)->left=q;
q->right=p;
p->f=q;
}
}


void insert_fix_up(node p)
{
while((p->priority) < (p->f->priority))
{
if(p==(p->f)->left)
right_rotate(p->f);
else
left_rotate(p->f);

}
while(root->f!=NULL)
root=root->f;
}
node insert()
{
node p,q,r;
unsigned long int n,i;
printf("Enter the number of elements to be inserted:");
scanf("%ld",&n);
for (i=0;i < n;i++)
{
p=getnode();
q=NULL;
//r=root;
while(r!=NULL)
{
q=r;
if ((p->key) < (r->key))
r=r->left;
else
r=r->right;
}
p->f=q;
if(q==NULL)
root=p;
else if((p->key) < (q->key))
q->left=p;
else
q->right=p;
insert_fix_up(p);
}
}
void display(node p,int level)
{
int i;

display(p->right,level+1);
for(i=0;i < level;i++)
printf("\t");
/*if(p->right!=NULL)
{
printf("\t");
display(p->right);
}*/
if(p==(p->f->right))
printf("R# %d:%d \n",p->key,p->priority);
else
printf("L# %d:%d \n",p->key,p->priority);
display(p->left,level+1);
}

int main(void)
{
int ch;
int j;
j=1;
printf("%d",j);
root=NULL;
while(j)
{
printf("1:insert\t2:display\nEnter your choice:");
scanf("%d",&ch);
switch(ch)
{
case 1: insert();
break;
case 2: display(root,1);
break;
case 4: j=0;
break;
default: printf("enter correct option\n");
break;
}
}