title: C++ Memory leaks in a linked list (Valgrind)
body: <p>I've been working through some memory leaks on my linked list:
  (Currently edited 3+ times, near the bottom)</p>
  
  <p>Here are the errors:</p>
  
  <pre><code>==348== HEAP SUMMARY:
  ==348==     in use at exit: 32 bytes in 2 blocks
  ==348==   total heap usage: 17 allocs, 15 frees, 272 bytes allocated
  ==348== 
  ==348== 16 bytes in 1 blocks are definitely lost in loss record 1 of 2
  ==348==    at 0x4C2B1C7: operator new(unsigned long) (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
  ==348==    by 0x400A2A: RangeSet::RangeSet() (RangeSet.cpp:14)
  ==348==    by 0x4013ED: main (TestRange.cpp:16)
  ==348== 
  ==348== 16 bytes in 1 blocks are definitely lost in loss record 2 of 2
  ==348==    at 0x4C2B1C7: operator new(unsigned long) (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
  ==348==    by 0x400F54: RangeSet::Union(RangeSet const&amp;, RangeSet const&amp;) (RangeSet.cpp:167)
  ==348==    by 0x401400: main (TestRange.cpp:17)
  </code></pre>
  
  <p>I can tell from the similar questions posted that it is most likely a problem I am freeing the "next" pointer, but I went through and fixed those errors (at least I attempted to) and now I only get this (^) from running valgrind --tool=memcheck --leak-check=yes</p>
  
  <p>Relevant Code:</p>
  
  <pre><code>RangeSet::RangeSet()
  {
    // make a dummy node?
    RNode* newNode = new RNode();
    head = newNode;
    head-&gt;start = 0;
    head-&gt;end = 0;
    head-&gt;next = NULL; // newing this for memory leak??
    len=0;
  } // end of constructor
  
  // copy constructor for Union
  RangeSet::RangeSet(const RangeSet &amp;in)
  {
    RNode* cur;
    RNode* nex;
    head = new RNode();
    head-&gt;start = in.head-&gt;start;
    head-&gt;end   = in.head-&gt;end;
    cur = head;
    nex = in.head-&gt;next;
  
    while (nex){
      cur-&gt;next = new RNode();
      cur = cur-&gt;next;
      cur-&gt;start = nex-&gt;start;
      cur-&gt;end = nex-&gt;end;
  
      nex = nex-&gt;next;
    }
    len = in.len;
  } // end of copy constructor
  
  
  // creates a pointer to new RangeSet that is the union of the two supplied RangeSets
  RangeSet* RangeSet::Union(const RangeSet &amp;alpha, const RangeSet &amp;beta)
  {
    // alpha and beta are const, so create copy
    RangeSet* copAlpha = new RangeSet(alpha);
    RNode *cursor = beta.head;
    // addRange all of beta into alpha's copy
    while (cursor != NULL){
      copAlpha-&gt;addRange(cursor-&gt;start, cursor-&gt;end);
      cursor=cursor-&gt;next;
    }
    return copAlpha;
  } // end of Union
  </code></pre>
  
  <p>Could the problem be my RNode's constructor?</p>
  
  <pre><code>struct RNode {
    int start, end;
    RNode* next;
    // possibly a pointer back to make it doubly linked
    RNode() {
      next = NULL;
    } 
  };
  </code></pre>
  
  <p><strong>EDIT</strong>
  Sorry! Here's my delete function (my destructor just calls it):</p>
  
  <pre><code>// makes the set empty
  void RangeSet::deleteAllElements() 
  {
   // having memory leak problems stemming from this function
   // trying to fix
    RNode *nex = head-&gt;next;
    for (RNode* cursor = head; cursor; cursor=nex){
      nex = cursor-&gt;next;
      RNode *cur = cursor;
      delete(cur);
      //delete(cursor-&gt;next); // Should I do this in a constructor for the RNode
      len--;
    }
  
  } // end of deleteAllElements
  </code></pre>
  
  <p><strong>EDIT 2</strong>
  Updating with addRange and sort (called by addRange at the end). Thank you all for your continued help! (Sorry that addRange is somewhat lengthy and probably convoluted)</p>
  
  <pre><code>// addRange
  void RangeSet::addRange(int rangeStart, int rangeEnd)
  {
    // debug                  
    //cout &lt;&lt; "Adding range: " &lt;&lt; rangeStart &lt;&lt; " to " &lt;&lt; rangeEnd &lt;&lt; endl;
  
    // li'l bit of error checking
    if (rangeStart &gt; rangeEnd){
      cerr &lt;&lt; "Please enter range(s) in the correct order. Exiting." &lt;&lt; endl;
      exit(0);         
    }
  
    // head case
    if (len==0){
      head-&gt;start = rangeStart;
      head-&gt;end = rangeEnd;
      len++;
    // need to account for adding at beginning
    } else if (rangeStart &lt;= head-&gt;start){
         //cout &lt;&lt; "INSERTING AT BEGINNING" &lt;&lt; endl;
         RNode *newNode = new RNode();                 
         newNode-&gt;start = head-&gt;start;             
         newNode-&gt;end   = head-&gt;end;  
         newNode-&gt;next  = head-&gt;next;
         head-&gt;start = rangeStart; 
         head-&gt;end   = rangeEnd;
         head-&gt;next  = newNode;                 
         len++;                 
     } else if (head-&gt;next == NULL){
         RNode *newNode = new RNode();
         newNode-&gt;start = rangeStart;
         newNode-&gt;end = rangeEnd;   
         head-&gt;next = newNode;
         len++;                 
     } else {
         // Moving past any nodes where the start is less than rangeStart
         RNode *cursor = head;
         RNode *past = cursor;
         int count = 1;
         while (cursor!=NULL &amp;&amp; count&lt;=len){
           if (rangeStart &gt; cursor-&gt;start){
             //cout &lt;&lt; rangeStart &lt;&lt; " is &gt; than " &lt;&lt; cursor-&gt;start &lt;&lt; endl;
             //cout &lt;&lt; "DEBUG1(cursor): " &lt;&lt; cursor-&gt;start &lt;&lt; endl;
             //cout &lt;&lt; "DEBUG2(past): " &lt;&lt; past-&gt;start &lt;&lt; endl;   
             past = cursor;
             cursor = cursor-&gt;next;
           }  
           count++;
        }
         //cout &lt;&lt; "INSERTING POS: " &lt;&lt; count &lt;&lt;  endl;
         // creating a new node to insert in middle
         RNode *newNode = new RNode();
         newNode-&gt;start = rangeStart;
         newNode-&gt;end   = rangeEnd;
         if (count == 1){       
           // add it after head (no other nodes)
           head-&gt;next = newNode;
           newNode-&gt;next = NULL;    
         } else {
           if (cursor){              
             newNode-&gt;next = cursor;
           }                  
           past-&gt;next = newNode;
         }   
         len++;
     }
  
    //dump();          
    sort();
  } // end addRange
  </code></pre>
  
  <p>So what I do is I create the new node and add it into the list based on its starting value, then I call sort():</p>
  
  <pre><code>// sort function called by addRange
  void RangeSet::sort()
  {
    //cout &lt;&lt; "SORTING" &lt;&lt; endl;   
    RNode *cursor = head;
    while (cursor-&gt;next != NULL){
      RNode *curPlusOne = cursor-&gt;next;
      if (cursor-&gt;end &gt;= (curPlusOne-&gt;start -1)){
        if (cursor-&gt;end &lt; curPlusOne-&gt;end){
          cursor-&gt;end = curPlusOne-&gt;end;
        }
        cursor-&gt;next = curPlusOne-&gt;next;
        //cout &lt;&lt; "NODE BEING DELETED: " &lt;&lt; curPlusOne-&gt;start &lt;&lt; " to " &lt;&lt; curPlusOne-&gt;end &lt;&lt; endl;
        delete(curPlusOne);
        len--;
      } else {
        cursor=cursor-&gt;next;
      }
    } // end while
    //dump();
  } // end sort
  </code></pre>
  
  <p><strong>EDIT 3</strong> Posting my main and my deleteRange. I also got a different set of errors this time around that I'll post towards the bottom. Thanks again!</p>
  
  <pre><code>// deletes all integers from RANGESTART to RANGEEND inclusive
  void RangeSet::deleteRange(int rangeStart, int rangeEnd)
  {
    RNode *cursor = head;
    RNode *past = cursor;
    RNode *temp = cursor-&gt;next;
    while (cursor){
      temp = cursor-&gt;next;
      if (rangeStart &lt;= cursor-&gt;start &amp;&amp; rangeEnd &gt;= cursor-&gt;end){
      // case 1: if the entire node is encompassed by what is being deleted
        if (cursor==head) { // still at head
          head = head-&gt;next;
          past = cursor;
          delete(cursor);
        } else {
          past-&gt;next = cursor-&gt;next;
          delete(cursor);
        }
        len--;
  
      } else if (rangeStart&lt;=cursor-&gt;start &amp;&amp; rangeEnd&gt;=cursor-&gt;start &amp;&amp; rangeEnd&lt;=cursor-&gt;end) {
      // case 2: the rangeStart is smaller than node's rangeStart
        cursor-&gt;start = rangeEnd+1; 
        len--;
  
      } else if (rangeEnd&gt;=cursor-&gt;end &amp;&amp; rangeStart&gt;=cursor-&gt;start &amp;&amp; rangeStart&lt;=cursor-&gt;end) {
      // case 3: the rangeEnd is larger than node's rangeEnd
        cursor-&gt;end = rangeStart-1;
        len--;
  
      } else if (cursor-&gt;start &lt; rangeStart &amp;&amp; cursor-&gt;end &gt; rangeEnd){
      // case 4: the range is in the middle of a node (split)
        RNode *newNode = new RNode();
        newNode-&gt;start = rangeEnd+1;
        newNode-&gt;end = cursor-&gt;end;
        newNode-&gt;next = cursor-&gt;next;
        cursor-&gt;end=rangeStart-1;
        cursor-&gt;next = newNode;
        len--;
      }
      past = cursor;
      cursor=temp;
    } // end while
  } // end of deleteRange
  
  int main(){
     RangeSet S, T;
     S.addRange(5,10);
     S.addRange(22,33);
     S.addRange(4,6);
     T.addRange(30,35);
     RangeSet U;
     U = *RangeSet::Union(T,S);
     U.addRange(1,1);
     U.addRange(39,40);
     U.addRange(40,150);
     RangeSet B(U);
  
     if (B==U)
       cout &lt;&lt; "COPY CONSTRUCTOR + OVERLOADED OPERATOR WORKED!" &lt;&lt; endl;
     U.dump();
     cout &lt;&lt; endl;
     U.deleteRange(1,35);
     U.deleteRange(75,100);
     U.dump();
  }
  </code></pre>
  
  <p>Here are the new (ish, I was receiving them earlier but I thought I had fixed them) errors I am receiving when I run valgrind:</p>
  
  <pre><code>==22482== Invalid read of size 8
  ==22482==    at 0x40122D: RangeSet::deleteAllElements() (RangeSet.cpp:237)
  ==22482==    by 0x400B79: RangeSet::~RangeSet() (RangeSet.cpp:47)
  ==22482==    by 0x401524: main (TestRange.cpp:30)
  ==22482==  Address 0x5a03368 is 8 bytes inside a block of size 16 free'd
  ==22482==    at 0x4C2A4BC: operator delete(void*) (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
  ==22482==    by 0x401261: RangeSet::deleteAllElements() (RangeSet.cpp:241)
  ==22482==    by 0x400B79: RangeSet::~RangeSet() (RangeSet.cpp:47)
  ==22482==    by 0x401500: main (TestRange.cpp:30)
  </code></pre>
  
  <p>This is why I thought my problem had to lie within deleteAllElements, but I'm still stumped!</p>
  
  <p><strong>EDIT 4</strong> Just a note, the main function is adapted from a skeleton provided to me, so I can't do too much to change it if therein lies the problem.</p>