Thread: Need help Debugging (ADT)

  1. #1
    Registered User
    Join Date
    May 2011
    Posts
    9

    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
    Last edited by minidragon; 08-08-2011 at 06:16 AM.

  2. #2
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    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.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  3. #3
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    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.

  4. #4
    Registered User
    Join Date
    May 2011
    Posts
    9
    so what am I suppose to do to fix the bug?

  5. #5
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Quote Originally Posted by minidragon View Post
    so what am I suppose to do to fix the bug?
    Learn to use a debugger.


    Quzah.
    Hope is the first step on the road to disappointment.

  6. #6
    Registered User
    Join Date
    May 2011
    Posts
    9
    Quote Originally Posted by quzah View Post
    Learn to use a debugger.


    Quzah.

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

  7. #7
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    So did you fix the part where you didn't initialize your variables before you start using them as Salem said?


    Quzah.
    Hope is the first step on the road to disappointment.

  8. #8
    Registered User
    Join Date
    May 2011
    Posts
    9
    Quote Originally Posted by quzah View Post
    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

  9. #9
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Assuming your malloc worked, yes. So what's the problem you have now?


    Quzah.
    Hope is the first step on the road to disappointment.

  10. #10
    Registered User
    Join Date
    May 2011
    Posts
    9
    Quote Originally Posted by quzah View Post
    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

  11. #11
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    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.
    Hope is the first step on the road to disappointment.

  12. #12
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    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?

  13. #13
    Registered User
    Join Date
    May 2011
    Posts
    9
    Quote Originally Posted by tabstop View Post
    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;

  14. #14
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    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?

  15. #15
    Registered User
    Join Date
    May 2011
    Posts
    9
    Quote Originally Posted by tabstop View Post
    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
    Last edited by minidragon; 08-08-2011 at 06:39 PM.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Help debugging this
    By CoreLink in forum C Programming
    Replies: 17
    Last Post: 04-25-2010, 08:19 PM
  2. Debugging help
    By kpridd in forum C++ Programming
    Replies: 3
    Last Post: 12-06-2009, 12:04 PM
  3. debugging in VC++
    By cwmccart in forum C++ Programming
    Replies: 1
    Last Post: 07-11-2008, 01:32 AM
  4. debugging
    By St0rM-MaN in forum Tech Board
    Replies: 13
    Last Post: 07-06-2007, 02:03 PM
  5. VC++ Debugging
    By neandrake in forum C++ Programming
    Replies: 5
    Last Post: 12-02-2003, 07:31 PM