Segmentation Fault in C++

Discussion in 'OT Technology' started by Pudge, Nov 11, 2009.

  1. Pudge

    Pudge New Member

    Joined:
    Nov 24, 2008
    Messages:
    2,572
    Likes Received:
    0
    Location:
    Athens, GA
    I get a segmentation fault whenever I try to access a variable of a variable in a copy constructor. I am creating a copy of a linked list and when I try to access head->next and have it equal something it gives a segmentation error. Why?
     
  2. CodeX

    CodeX Guest

    give us the code.
     
  3. Pudge

    Pudge New Member

    Joined:
    Nov 24, 2008
    Messages:
    2,572
    Likes Received:
    0
    Location:
    Athens, GA
    code in bold is what's giving me trouble

    Code:
    #include <iostream>
    using std::cout;
    using std::endl;
    
    // forward declaration of List class, so ListElement can make 
    // it a friend.  NOTE: If List is a friend of ListElement, that
    // means that the List class has access to the private members
    // of the ListElement class, but no one else does (besides ListElement
    // itself). 
    
    class List;
    class ListIterator;
    
    class ListElement {
     friend class List;
     friend class ListIterator;
     public:
     ListElement(): next(this), prev(this), isHeader(true) {}
     ListElement(int i): item(i), isHeader(false) {}
     ~ListElement() {}  // default destructor
     private:
      int item;
      ListElement *next;    
      ListElement *prev;    
      bool isHeader;
    };
    
    class ListIterator {
     friend class List;
     public:
      ListIterator() : currentPtr(NULL) { }
      ListIterator operator++(){
                   this->currentPtr->prev=this->currentPtr;
                   this->currentPtr->next=this->currentPtr->next->next;              
                   return *this;
                   }  // advance iterator to the next list node; return value is iterator *after* advancing  
      ListIterator operator--(){
                   this->currentPtr->next=this->currentPtr;
                   this->currentPtr->prev=this->currentPtr->prev->prev;
                   return *this;
                   }  // advance iterator to the previous list node; return value is iterator *after* advancing
      ListIterator operator++(int){
                    this->currentPtr->prev=this->currentPtr;
                   this->currentPtr->next=this->currentPtr->next->next;              
                   return *this;
                   }  // advance iterator to the next list node; return value is iterator *before* advancing
      ListIterator operator--(int){
                   this->currentPtr->next=this->currentPtr;
                   this->currentPtr->prev=this->currentPtr->prev->prev;
                   return *this;
                   }  // advance iterator to the previous list node; return value is iterator *before* advancing
      int operator*(){
           if(currentPtr->isHeader){
                    printf("error\n");
                    exit(1); 
                    }
            return currentPtr->item;                
          } // return contents pointed to by iterator; print "error\n"
            // and terminate program if iterator refers to header node
     private:
      ListElement *currentPtr;
    };
    
    class List {
      public:
        List(){
               listSize=0;
               }   // creates an empty list
        ~List(){
        ListIterator *nodePtr, *nextNodePtr;
        nodePtr->currentPtr = head;
        while (nodePtr->currentPtr != NULL)
        {
        nextNodePtr->currentPtr = nodePtr->currentPtr->next;
        delete nodePtr;
        nodePtr = nextNodePtr;
        }      
                }  // *must* deallocate the entire list
       [B] List(const List &L){
           ListIterator p;         
           p.currentPtr=L.head;    
           while(p.currentPtr->next!=L.head){
                   p.currentPtr=p.currentPtr->next;
                   this->Append(*p); 
                   }          
                   }  // copy constructor (*must* be a deep copy)
       [/B] List & operator =(List &L){
            if(this!= &L){
            ListIterator lTemp;
        int value;          
           lTemp.currentPtr=L.head;
           while(lTemp.currentPtr->next!=L.head){
             cout << "= loop" << endl;
                   lTemp.currentPtr=lTemp.currentPtr->next;
                   ListElement *temp= new ListElement();
             temp=lTemp.currentPtr;
                   this->head->next=temp;
                this->head->prev=temp;
             temp->next=this->head;
             temp->prev=this->head; 
                   listSize++;
                   }          
    
            }
                  return *this;      
             }  // *must* (deep) copy list, and must avoid memory leak
    
        // these are functions to set and test the list iterator
        void SetStartList(ListIterator &p) {p.currentPtr = head->next;}
        void SetEndList(ListIterator &p) {p.currentPtr = head->prev;}
        bool IsUndefined(ListIterator p) {return (p.currentPtr == head);}
        bool AtEndList(ListIterator p) {return (p.currentPtr == head);}
        bool AtStartList(ListIterator p) {return (p.currentPtr == head);}
        bool AtFirstNode(ListIterator p) {return (p.currentPtr == head->next);}
        bool AtLastNode(ListIterator p) {return (p.currentPtr == head->prev);}
        // Insert integer at the beginning of the list  
        void Prepend(int it){
             ListIterator p;    
          p.currentPtr=this->head;         
             ListElement *temp= new ListElement(it);  
                  if(this->IsEmpty()){
                                this->head->next=temp;
                    this->head->prev=temp;
                    temp->next=this->head;
                    temp->prev=this->head;   
                                   }   
                else{
                        temp->prev=p.currentPtr;
                        temp->next=p.currentPtr->next;
                        p.currentPtr->next->prev=temp;
                        p.currentPtr->next=temp;
                        p.currentPtr=temp;
                        }
    
                     listSize++;
    }
        // Insert integer at the end of the list
       [B] void Append(int it){
                ListIterator p;
                p.currentPtr=this->head;
             ListElement *temp= new ListElement(it);  
            if(this->IsEmpty()){
                                this->head->next=temp;
                    this->head->prev=temp;
                    temp->next=this->head;
                    temp->prev=this->head;   
                                   }         
                else{ 
                        temp->next=p.currentPtr;
                        temp->prev=p.currentPtr->prev;
                        p.currentPtr->prev->next=temp;
                        p.currentPtr->prev=temp;
                        p.currentPtr=temp;
                        }
         
                     listSize++;
    }[/B]
        // Remove first integer from list, return through first parameter.
        // Success is set to true if original list is nonempty, false if empty
        void Pop(int &it, bool &success){
              if(IsEmpty()){
                                 success=false;         
                       }  
              else{
                   success=true;
                   ListElement *temp= new ListElement(); 
                   temp=this->head->next;
                   it=temp->item;
                   temp->next->prev=this->head;
                   this->head->next=temp->next;
                   temp->prev=NULL;
                   temp->next=NULL;
                   }         
            listSize--;
              }    
        // Remove last integer from list, return through first parameter.
        // Success is set to true if original list is nonempty, false if empty
        void Pull(int &it, bool &success){
              if(IsEmpty()){
                                 success=false;         
                       }  
              else{
                   success=true;
                   ListElement *temp= new ListElement(); 
                   temp=this->head->prev;
                   it=temp->item;
                   temp->prev->next=this->head;
                   this->head->prev=temp->prev;
                   temp->prev=NULL;
                   temp->next=NULL;
                   } 
            listSize--;        
              }      
        // Get first integer on list, return through first parameter
        // Success is set to true if original list is nonempty, false if empty
        void First(int &it, bool &success){
                       if(IsEmpty()){
                                 success=false;         
                       }       
                       else{    
                       success=true;          
                       ListElement *temp= new ListElement();
                       temp=head->next;
                       it=temp->item;        
                       }
    }
        // Get last integer on list, return through first parameter
        // Success is set to true if original list is nonempty, false if empty
        void Last(int &it, bool &success){
                if(IsEmpty()){
                                 success=false;         
                       }       
                       else{    
                       success=true;          
                       ListElement *temp= new ListElement();
                       temp=head->prev;
                       it=temp->item;        
                       }
    }
        // insert integer before list element referred to by p
        void InsertBefore(int it, ListIterator p){ //may need to check if 'p' is NULL
             ListElement *temp= new ListElement();  
             temp->item=it;
             if(p.currentPtr->prev==head){
                    temp->prev=head;
                    head->next=temp;
                    temp->next=p.currentPtr;
                    p.currentPtr->prev=temp;
                    }   
             else{      
                   temp->next=p.currentPtr->next;
                   p.currentPtr->next->prev=temp;
                   temp->prev=p.currentPtr;
                   p.currentPtr->next=temp;
             }
             listSize++;
    }
        // insert integer after list element referred to by p
        void InsertAfter(int it, ListIterator p){ //may need to check if 'p' is NULL
             ListElement *temp= new ListElement();  
             temp->item=it;
             if(p.currentPtr->next==head){
                    temp->next=head;
                    head->prev=temp;
                    temp->prev=p.currentPtr;
                    p.currentPtr->next=temp;
                    }   
             else{        
                    p.currentPtr->next->prev=temp;
                    temp->next=p.currentPtr->next;
                    p.currentPtr->next=temp;
                    temp->prev=p.currentPtr;
             }
             listSize++;
    }
        // delete list element referred to by p; print "error\n"
        // and exit if p refers to the header node
        // p is undefined after this function
        void Delete(ListIterator p){
                if(p.currentPtr==head){
                      printf("error\n");
                      exit(1);
                      }                             
                if(p.currentPtr->prev==head){
                     p.currentPtr->next->prev=head;
                     head->next=p.currentPtr->next;
                     p.currentPtr->next=NULL;
                     p.currentPtr->prev=NULL;
                }
                else if (p.currentPtr->next==head){
                     p.currentPtr->prev->next=head;
                     head->prev=p.currentPtr->prev;
                     p.currentPtr->prev=NULL;
                     p.currentPtr->next=NULL;
        }
        else
        {
        p.currentPtr->prev->next=p.currentPtr->next;
        p.currentPtr->next->prev=p.currentPtr->prev;
        p.currentPtr->next=NULL;
        p.currentPtr->prev=NULL;
        }
        listSize--;
        }
        // apply function "func" to each element on the list
        void MapFunction(void (*func)(int &)){
             ListIterator p;         
             this->AtFirstNode(p);
             for(int i=0;i<listSize;i++){
                     func(p.currentPtr->item);
                     p.currentPtr=p.currentPtr->next;
                     }
    }     
        // returns true if list empty, false otherwise
        bool IsEmpty(){
             if(listSize==0){
             return true;
             }
             return false;
    }
        int GetSize() {return listSize;}
    
        // must print out list elements, one per line
        void Print(){
             ListIterator p;
             p.currentPtr=this->head->next;         
             for(int i=0;i<listSize;i++){
                     cout << p.currentPtr->item << endl;
                     p.currentPtr=p.currentPtr->next;
                     }
    }
      private:
        ListElement *head;
        int listSize;
    };
    
     
  4. Joe_Cool

    Joe_Cool Never trust a woman or a government. Moderator

    Joined:
    Jun 30, 2003
    Messages:
    299,326
    Likes Received:
    566
    I don't have the energy to really pore over it, and I'm a little rusty, so take this with a grain of salt.

    Have you tried changing this:

    this->Append(*p);

    to this:

    this->Append(p);

    ?

    The reason I ask is that the List functions should be written to handle pointers. Using the dereference operator in that case would cause it to use the value stored in the cell being pointed to as an address instead of a value, and then try to modify some random address in memory. And seg fault is usually due to a runaway pointer in my experience.
     
  5. Pudge

    Pudge New Member

    Joined:
    Nov 24, 2008
    Messages:
    2,572
    Likes Received:
    0
    Location:
    Athens, GA
    ^^ no. * in the ListIterator class was changed to return the value (int) stored by that iterator. In my tester class a newly created list that later uses the Append(int) method works perfectly fine. It is only when the copy constructor tries to access this method that I get a segmentation fault. A variable not yet initialized maybe?
     
    Last edited: Nov 11, 2009
  6. skinjob

    skinjob Active Member

    Joined:
    Jan 6, 2001
    Messages:
    2,337
    Likes Received:
    0
    Location:
    Aztlán
    I think it's in the Append function. If the list IsEmpty(), then this->head would be NULL, and this->head->next would be referencing a NULL pointer.
     
  7. Joe_Cool

    Joe_Cool Never trust a woman or a government. Moderator

    Joined:
    Jun 30, 2003
    Messages:
    299,326
    Likes Received:
    566
    Sorry bro. Like I said, I'm a little rusty. :o
     
  8. Pudge

    Pudge New Member

    Joined:
    Nov 24, 2008
    Messages:
    2,572
    Likes Received:
    0
    Location:
    Athens, GA
    but when I run my test case it works and it runs through that
    Code:
    cout << "Test Case #1."<<endl;
        
        cout << "Constructor"<<endl;
        List *plist = new List();
        
        cout << "Append"<<endl;
        for (i=0;i<30;i++){
            (*plist).Append(i);
     
  9. Pudge

    Pudge New Member

    Joined:
    Nov 24, 2008
    Messages:
    2,572
    Likes Received:
    0
    Location:
    Athens, GA
    Plus when I am in the copy constructor if I do head->next=(whatever) I get the same result only the fault occurs at that line. Initially 'next' references 'head' whenever the list is empty.
     
  10. deusexaethera

    deusexaethera OT Supporter

    Joined:
    Jan 27, 2005
    Messages:
    19,712
    Likes Received:
    0
    Just put a 'cout << "line x okay";' after each line until you find the one causing the problem.
     
  11. binary01

    binary01 New Member

    Joined:
    Apr 6, 2007
    Messages:
    3
    Likes Received:
    0
    I don't know what you mean by "works" but this will actually segfault if ran with the code you posted before.

    And skinjob is right, the problem is that when the list is empty "this->head" will be null, so trying to access any members of the head will make it segfault. What you probably want to do is set the head itself to the new element if the list is empty.
     
  12. CodeX

    CodeX Guest

    I really hope that's not how you go about debugging your own code... why not just set a breakpoint at line 1 and iterate through it line by line in mixed mode so you can see the exact assembly instruction that causes the problem?

    I'll look at this after work today if nobody figures it out.
     
  13. Pudge

    Pudge New Member

    Joined:
    Nov 24, 2008
    Messages:
    2,572
    Likes Received:
    0
    Location:
    Athens, GA
    turns out I just needed to initialize 'head=new ListElement()' in both of my constructors so that 'next' and 'prev' would be initialized too. fucking stupid mistake and I should have done that in the first place. God damn stupid mistake cost me hours of time. But maybe now I won't be so dumb :o. Anyway thanks for the replies.
     
  14. skinjob

    skinjob Active Member

    Joined:
    Jan 6, 2001
    Messages:
    2,337
    Likes Received:
    0
    Location:
    Aztlán
    It makes more sense for an empty list to have a NULL head pointer. Prev and next are meaningless when the list is empty. Your append function should set the head pointer to a new element when appending to an empty list.
     
  15. skinjob

    skinjob Active Member

    Joined:
    Jan 6, 2001
    Messages:
    2,337
    Likes Received:
    0
    Location:
    Aztlán
    If you run the program in a debugger, the debugger will tell you where it crashed, and it will let you examine the call stack so you can see what led up to the crash.
     
  16. Limp_Brisket

    Limp_Brisket New Member

    Joined:
    Jan 2, 2006
    Messages:
    48,422
    Likes Received:
    0
    Location:
    Utah
    :ugh:
     
  17. deusexaethera

    deusexaethera OT Supporter

    Joined:
    Jan 27, 2005
    Messages:
    19,712
    Likes Received:
    0
    That works too, if he's using a development environment that's that advanced. When I was in college, we used G++ running on a BASH command line, so (as far as I know) breakpoints weren't an option.
     
  18. skinjob

    skinjob Active Member

    Joined:
    Jan 6, 2001
    Messages:
    2,337
    Likes Received:
    0
    Location:
    Aztlán
    gdb has been around as long as gcc. I remember that if your program core dumped, you'd simply run gdb with the core file and it would tell you where it crashed.
     
  19. Pudge

    Pudge New Member

    Joined:
    Nov 24, 2008
    Messages:
    2,572
    Likes Received:
    0
    Location:
    Athens, GA
    yeah I used gdb to flag the exact line. I was just too blind to see why it was not working.
     
  20. kronik85

    kronik85 New Member

    Joined:
    Feb 8, 2005
    Messages:
    34,837
    Likes Received:
    0
    Location:
    Deutschland
    i always thought you were smart :hs:
     
  21. deusexaethera

    deusexaethera OT Supporter

    Joined:
    Jan 27, 2005
    Messages:
    19,712
    Likes Received:
    0
    I'm not sure whether to say thanks or sorry to disappoint. :confused:
     

Share This Page