Need help Debugging (ADT)

Hello, I been trying to debug my program for hours, but there still one small bug left that I need help. Please anyone can give me some advice/tip, it would be very much appreciated.

I used gdb to debug my program, and it tell that my program is Segmentation Fault at line 207.

when I run gdb with my program, here what I get:

Code:

(gdb) run in out
Starting program: /afs/cats.ucsc.edu/users/m/ltrinh1/private/cs101/pa5/FindComponents in out

Program received signal SIGSEGV, Segmentation fault.
0x0000000000401dc1 in insertBeforeFirst (L=0x604630, data=1) at List.c:207
207         L->head->prev= temp;

Here's my Code.

Code:

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include "List.h"

typedef struct Node{
  int data;
  struct Node* next;
  struct Node* prev;
} Node;

typedef Node* NodeRef;

typedef struct List{
  NodeRef head;
  NodeRef tail;
  NodeRef curr;
  int length;
} List;

NodeRef newNode(int node_data){
  NodeRef N = malloc(sizeof(Node));
  N->data= node_data;
  N->next= NULL;
  return (N);
}

void freeNode(NodeRef* pN){
  if(pN !=NULL && *pN!=NULL){
    free(*pN);
    *pN= NULL;
  }
} 

ListRef newList(void){
  ListRef L;
  L = malloc(sizeof(List));
  L->head = L->tail = NULL;
  L-> length =0;
  return(L);
}

void freeList(ListRef* pL){
  if(pL== NULL || *pL==NULL){ return;}  
  makeEmpty(*pL);
  free(pL);
  free(*pL);
  *pL= NULL;
}

int isEmpty(ListRef L){ 
   if(L==NULL){
    printf("Error: calling is isEmpty() on NULL ListRef\n");
    exit(1);
   }
   if(L->length==0){
     return 1;
   }
   return (L->length==0);
}

int offEnd(ListRef L){ 
  if(L->curr== NULL){ return 1; }
  if(getLength(L)==0){ return 1;}
  return 0;
  }

int atFirst(ListRef L){ 
  if(isEmpty(L)){ return 0; }
  if(L->head== L->curr){ return 1; }
  return 0;
}

int atLast(ListRef L){ 
  if(isEmpty(L)){ return 0; }
  if(L->tail == L->curr){ return 1; }
  return 0;
}

int getFirst(ListRef L){ 
  if(L ==NULL){
    printf("Called getFirst on NULL ListRef\n");
    exit(1);
  }
  if(isEmpty(L)){
    printf("Called getFirst on an empty list\n");
    exit(1);
  }
  return(L->head->data);
}

int getLast(ListRef L){
  if(L== NULL){
    printf("Error: Called getLast on NULL ListRef\n");
    exit(1);
  }
  if(isEmpty(L)){
    printf("Error: Called getLast on an empty list\n");
    exit(1);
}
  return(L->tail->data);
}

int getCurrent(ListRef L){
  if(L==NULL){
    printf("Error: Called getCurrent on NULL ListRef\n");
    exit(1);
  }
  if(isEmpty(L) && offEnd(L)){
    printf("Error: Called getCurrent on an empty list\n");
    exit(1);
  }
  return(L->curr->data);
}

int getLength(ListRef L){
    if(L== NULL){
      printf("Error: Called getLength on NULL ListRef\n"); 
      exit(1);
    }
    return(L->length);
  }

int equals(ListRef L, ListRef K){
    int flag = 1;
    Node* tempOne= NULL;
    Node* tempTwo= NULL;
    if(L== NULL || K== NULL){
      printf("Error: calling equals() on NULL ListRef\n");
      exit(1);
    }
    if(L->length != K->length){return 0; }
    tempOne= L->head;
    tempTwo= K->head;
    while(flag && tempOne != NULL){
      flag = (tempOne->data == tempTwo->data); 
      tempOne = tempOne->next;
      tempTwo = tempTwo->next;
    }
    return flag;
}

void makeEmpty(ListRef L){
  while(!isEmpty(L)){
    deleteFirst(L);
  }
}

void moveFirst(ListRef L){
  if(L== NULL){
    printf("Error: moveFirst() called on NULL ListRef\n");
    exit(1);
  }
  if(isEmpty(L) && offEnd(L)){
    printf("Error: List is empty. (moveFirst)\n");
    exit(1);
  }
  L->curr = L->head;
}

void moveLast(ListRef L){ 
  if(L== NULL){
    printf("Error: moveLast() called on NULL ListRef\n");
    exit(1);
  }
  if(isEmpty(L)&& offEnd(L)){
    printf("Error: List is empty. (moveLast)\n");
    exit(1);
  }
  L->curr= L->tail;
}

void movePrev(ListRef L){
  if(L== NULL){
    printf("Error: called movePrev() on NULL ListRef\n");
    exit(1);
  }
  if(isEmpty(L) && offEnd(L)){
    printf("Error: List is empty. (movePrev)\n");
    exit(1);
  }
  L->curr= L->curr->prev;
}

void moveNext(ListRef L){ 
  if(L== NULL){
    printf("Error: called moveNext() on NULL ListRef \n");
    exit(1);
  }
  if(isEmpty(L) && offEnd(L)){
    printf("Error: List is empty. (moveNext)");
    exit(1);
  }
  L->curr= L->curr->next;
}
  
void insertBeforeFirst(ListRef L, int data){
  NodeRef temp= newNode(data);
  if(L== NULL){
    printf("Queue Error: called insertBeforeFirst() on NULL ListRef\n");
    exit(1);
  }
  if(isEmpty(L)){ L->head= L->tail= temp; }
  else{
    temp->next = L->head;
    L->head->prev= temp;
    L->head= temp;
  }
  L->length++;
}

void insertAfterLast(ListRef L, int data){ 
  NodeRef temp = newNode(data);
  if(L== NULL){
    printf("Error: called insertAfterLast() on NULL ListRef\n");
    exit(1);
   }
  if(isEmpty(L)){  L->head= L->tail= temp; }
  else{
    temp->prev= L->tail;   
    L->tail->next= temp;
    L->tail= temp; 
  }
  L->length++;
}

void insertBeforeCurrent(ListRef L, int data){ 
  if(L== NULL){
    printf("Error: calling insertBeforeCurrent() on NULL ListRef\n");
    exit(1);
  }
  if(isEmpty(L) || offEnd(L)){
    printf("Error: List is empty or Current node is NULL.\n");
    exit(1);
  }
  if(atFirst(L)){
    insertBeforeFirst(L,data);
  }
  else{
    NodeRef temp = newNode(data);
    temp->prev = L->curr->prev;
    temp->next = L->curr;
    (L->curr->prev)->next= temp;
    L->curr->prev = temp;      
    L->length++;
    freeNode( &temp);
  }
}

void insertAfterCurrent(ListRef L, int data){
  if(L== NULL){
    printf("Error: called insertAfterCurrent() on NULL ListRef\n");
    exit(1);
  }
  if(isEmpty(L) || offEnd(L)){
    printf("Error: List is empty/Current node is NULL.(insertAfterCurrent)\n");
  }
  if(atLast(L)){
    insertAfterLast(L,data);
  }
  else{
    NodeRef temp = newNode(data);
    temp->next= L->curr->next;
    temp->prev= L->curr;
    (L->curr->next)->prev= temp;
    L->curr->next= temp;      
    L->length++;
  }
}

void deleteFirst(ListRef L){ 
  NodeRef temp= NULL;
  if(L== NULL){
    printf("Error: called deleteFirst() on NULL ListRef\n");
    exit(1);
  }
  if(isEmpty(L)){
    printf("Error: deleteFirst called on empty list.");
    exit(1);
  }
  temp= L->head;
  if(L->length>1){
    (L->head->next)->prev= NULL;
    L->head= L->head->next;
    L->length--;
  }
  else{
    L->head= L->tail= NULL;
    L->length= 0;
  }
  freeNode(&temp);
  free(temp);
}

void deleteLast(ListRef L){
  NodeRef temp = NULL;
  if(L== NULL){
    printf("Error: called deleteLast() on NULL ListRef\n");
    exit(1);
  }
  if(isEmpty(L)){
    printf("Error: deleteLast called on empty list.");
    exit(1);
  }
  temp= L->tail;
  if(L->length>1){
    (L->tail->prev)->next= NULL;
    L->tail= L->tail->prev;
    L->length--;
  }
  else{ 
    L->head= L->tail= NULL; 
    L->length=0;
  }
  freeNode(&temp);
}

void deleteCurrent(ListRef L){
  if(L== NULL){
    printf("Error: deleteCurrent() called on NULL ListRef\n");
    exit(1);
  }
  if(isEmpty(L) && offEnd(L)){
    printf("Error: deleteCurrent called on empty list.");
    exit(1);
  }
  if(atFirst(L)){
    deleteFirst(L);
  }
  else if(atLast(L)){
    deleteLast(L);
  }
  else if(L->length>1){
    NodeRef temp = NULL;
    temp= L->curr;
    (L->curr->prev)->next= L->curr->next;
    (L->curr->next)->prev= L->curr->prev;
    L->curr->next= NULL;
    L->curr->prev= NULL;
    L->length--;
    freeNode(&temp);
  }
}

void printList(FILE* out, ListRef L){
  if(out == NULL){
    printf("Unable to open file for writing\n");
    exit(1);
  }
  if(L == NULL){
    printf("Error: Unable to write List to file\n");
    exit(1);
  }
  NodeRef temp;
  for(temp= L->head; temp!=NULL; temp=temp->next){
    fprintf(out, "%d ", temp->data);
  }
  fprintf(out,"\n");
}
ListRef copyList(ListRef L){
  ListRef temp = newList();
  NodeRef tempNode= L->head;
  while( tempNode != NULL){
    insertAfterLast(temp, tempNode->data);
    tempNode= tempNode->next;
  }
  return temp;
}


void shuffleLists(ListRef L, ListRef P){
  moveFirst(P);
  int position, i, j;
  moveLast(L);
  while(!offEnd(P)){
    position = getCurrent(P);
    for(i =1; i< position; i++){
      moveNext(L);
    }
    insertAfterCurrent(L,getFirst(L));
    deleteFirst(L);
    for(j =1; j< position; j++){
      movePrev(L);
    }
    moveNext(P);
  }
}

void printerList(ListRef L){
  NodeRef temp= NULL;
  if(L == NULL){
    printf("Error: Fail.\n");
    exit(1);
  }
  for(temp= L->head; temp!= NULL; temp=temp->next){
    printf("%d ", temp->data);
  }
  printf("\n");
}

Line 207 is

Code:

    L->head->prev= temp;

From

Code:

void insertBeforeFirst(ListRef L, int data){
  NodeRef temp= newNode(data);
  if(L== NULL){
    printf("Queue Error: called insertBeforeFirst() on NULL ListRef\n");
    exit(1);
  }
  if(isEmpty(L)){ L->head= L->tail= temp; }
  else{
    temp->next = L->head;
    L->head->prev= temp;
    L->head= temp;
  }
  L->length++;
}

I don't see what's wrong with line 207, I just did the opposite of insertAfterLast

Well your NewNode doesn't set prev to NULL for starters.
So perhaps your list has trash prev pointers.

Certainly, it's going to go wrong at any test of prev being NULL.

Making InsertBeforeFirst the opposite of InsertAfterLast would have been fine, if InsertAfterLast wasn't broken; since it is, now you have two broken functions. Since your newNode function doesn't set any of the pointers, all your functions that use newNode must; so you're missing a set of prev in the first function and the set of next in the last function.

so what am I suppose to do to fix the bug?

Originally Posted by minidragon

so what am I suppose to do to fix the bug?

Learn to use a debugger.


Quzah.

Originally Posted by quzah

Learn to use a debugger.


Quzah.

I just started learning how, but I don't know how to fix this.

So did you fix the part where you didn't initialize your variables before you start using them as Salem said?


Quzah.

Originally Posted by quzah

So did you fix the part where you didn't initialize your variables before you start using them as Salem said?


Quzah.

yes I initialized it. is this correct?

Code:

NodeRef newNode(int node_data){
  NodeRef N = malloc(sizeof(Node));
  N->data= node_data;
  N->next= NULL;
  N->prev= NULL;
  return (N);
}

I still get Seg Fault

Assuming your malloc worked, yes. So what's the problem you have now?


Quzah.

Originally Posted by quzah

Assuming your malloc worked, yes. So what's the problem you have now?


Quzah.

it's the same problem, gdb is pointing to the same line

You typedefed a pointer, which immediately makes me stop caring about your problem. Other than that, you should have been testing these functions individually as you wrote them, instead of writing a whole bunch of stuff and then hoping it works. Start writing test cases for your individual functions.


Quzah.

When you've got gdb stopped, you are allowed to get more information, such as what is L->length and L->head and so on. Which functions get called to get to the point you've gotten to? Only InsertBeforeFirst, or a bunch of things?

Originally Posted by tabstop

When you've got gdb stopped, you are allowed to get more information, such as what is L->length and L->head and so on. Which functions get called to get to the point you've gotten to? Only InsertBeforeFirst, or a bunch of things?

Here are the steps I did for gdb

Code:

(gdb) run in out
Starting program: /afs/cats.ucsc.edu/users/m/ltrinh1/private/cs101/pa5/FindComponents in out

Breakpoint 1, insertBeforeFirst (L=0x604630, data=1) at List.c:200
200       NodeRef temp= newNode(data);
(gdb) s
newNode (node_data=1) at List.c:23
23        NodeRef N = malloc(sizeof(Node));
(gdb) s
24        N->data= node_data;
(gdb) s
25        N->next= NULL;
(gdb) s
26        N->prev= NULL;
(gdb) s
27        return (N);
(gdb) s
28      }
(gdb) s
insertBeforeFirst (L=0x604630, data=1) at List.c:201
201       if(L== NULL){
(gdb) s
205       if(isEmpty(L)){ L->head= L->tail= temp; }
(gdb) s
isEmpty (L=0x604630) at List.c:54
54         if(L==NULL){
(gdb) s
58         if(L->length==0){
(gdb) s
61         return (L->length==0);
(gdb) s
62      }
(gdb) s
insertBeforeFirst (L=0x604630, data=1) at List.c:207
207         temp->next = L->head;
(gdb) s
208         L->head->prev= temp;
(gdb) s

Program received signal SIGSEGV, Segmentation fault.
0x0000000000401dcd in insertBeforeFirst (L=0x604630, data=1) at List.c:208
208         L->head->prev= temp;

When you've got gdb stopped, you are allowed to get more information, such as what is L->length and L->head and so on. Which functions get called to get to the point you've gotten to? Only InsertBeforeFirst, or a bunch of things?

Originally Posted by tabstop

When you've got gdb stopped, you are allowed to get more information, such as what is L->length and L->head and so on. Which functions get called to get to the point you've gotten to? Only InsertBeforeFirst, or a bunch of things?

sorry I misunderstood, here the functions got called

Code:

(gdb) bt
#0  0x0000000000401dcd in insertBeforeFirst (L=0x604630, data=1) at List.c:208
#1  0x000000000040124c in DFSVisit (G=0x604490, u=1, S=0x604700) at Graph.c:160
#2  0x000000000040106c in DFS (G=0x604490, S=0x604700) at Graph.c:138
#3  0x0000000000400996 in main (argc=3, argv=0x7fffffffe5a8) at FindComponents.c:39