Solved

Push function for Linked List leaking memory

Posted on 2009-05-05
9
265 Views
Last Modified: 2012-05-06
Brushing up on linked lists.
I'm detecting a memory leak coming from this function.
I know I can't delete the variable foo without corrupting the data.
How can I get rid of the memory leak?
void push_front( struct node*& head, int data )
{
   node* foo = new node ;
   foo->data = data ;
   foo->next = head ;
   head = foo ;
   //delete foo ;
}

Open in new window

0
Comment
Question by:Dripcode
  • 4
  • 2
  • 2
  • +1
9 Comments
 
LVL 40

Expert Comment

by:evilrix
ID: 24309611
>> How can I get rid of the memory leak?
As you say, you can't delete foo here since it's not the head of the list. The problem isn't going to be this function but its counter part where you remove from the list. It is that function that should be cleaning up (or at least returning a pointer for you to clean up).

Why do you think there is a memory leak?
0
 
LVL 2

Expert Comment

by:Gregdo
ID: 24309924
The memory leak is reported here because that is where "new" is called.  In MSVC++, in debug mode, new is replaced by debug_new which tracks memory allocations and deletions. Since it only knows where you allocated the memory and not where you expect it to be deleted, it reports the memory leak at the point where it was created (new).

As evilrix said, the problem is probably in your cleanup function.
0
 

Author Comment

by:Dripcode
ID: 24309991

I have attached all my code below.

I'm deleting all the new pointers that I have create in the main().

But I'm still getting this message with from MSVC++ :

Detected memory leaks!
Dumping objects ->
{162} normal block at 0x0036A708, 8 bytes long.
 Data: <    P 6 > 01 00 00 00 50 A7 36 00
Object dump complete.
#include "stdafx.h"
#include <iostream>
#include <conio.h>  //for getche()
 
#define _CRTDBG_MAP_ALLOC
 
#include <stdlib.h>
#include <crtdbg.h>
#include <memory>
#include <string>
#include <cstring>
#include <cctype>
#define eq ==
using namespace std ;
 
struct node
{
   int data ;
   node* next ;
} ;
 
void push_front( struct node*& head, int data )
{
   node* foo = new node ;
   foo->data = data ;
   foo->next = head ;
   head = foo ;
   //delete foo ;
}
 
 
void display_contents( struct node* head )
{
   node* foo = head ;
  
   while( foo != NULL )
   {
      cout << "data: " << foo->data << endl ;
      foo = foo->next ;
   }
   
   cout << endl << endl ;
}
 
 
int _tmain(int argc, _TCHAR* argv[])
{
   node* head = new node ;
   node* first_node = new node ;
   node* second_node = new node ;
   node* third_node = new node ;
 
   head->data = 1 ;
   head->next = first_node ;
   
   first_node->data = 2 ;
   first_node->next = second_node ;
   
   second_node->data = 3 ;
   second_node->next = third_node ;
   
   third_node->data = 4 ;
   third_node->next = NULL ;
 
   display_contents( head ) ;
   
   push_front( head, 444 ) ;
 
   display_contents( head ) ;
   
   delete head ;
   delete first_node ;
   delete second_node ;
   delete third_node ;
 
 
   // Dump memory leaks to output window.	
   _CrtSetDbgFlag ( _CRTDBG_ALLOC_MEM_DF | _CRTDBG_LEAK_CHECK_DF);
   _CrtSetReportMode(_CRT_WARN, _CRTDBG_MODE_FILE | _CRTDBG_MODE_DEBUG);
   _CrtSetReportFile(_CRT_WARN, _CRTDBG_FILE_STDOUT);
   _CrtDumpMemoryLeaks();
 
   _getch();
 
	return 0;
}

Open in new window

0
Free Tool: Port Scanner

Check which ports are open to the outside world. Helps make sure that your firewall rules are working as intended.

One of a set of tools we are providing to everyone as a way of saying thank you for being a part of the community.

 
LVL 2

Accepted Solution

by:
Gregdo earned 250 total points
ID: 24311332
Here's what I see.  In main() you allocate memory for 4 pointers and you delete the memory for 4 pointers.  You also call push_front() which creates a new object and puts itself at the front of the list.  It assigns that object to the "head" pointer. The problem is that your main() function no longer has a direct pointer to delete the memory that the "head" pointer was originally pointing too.  That memory is still in the list though.

Replace your 4 deletes with the code below.  It should loop through 5 times and therefore delete all the elements in your list.
// Replace these deletes
//   delete head ;
//   delete first_node ;
//   delete second_node ;
//   delete third_node ;
 
node* p = head;
while (p)
{
    node* x = p->next;
    delete p;
    p = x;
}

Open in new window

0
 
LVL 40

Expert Comment

by:evilrix
ID: 24311763
An alternative is to make your node have a destructor (since C++ uses objects we might as well consider making the code object oriented) that deletes its child. When you delete head it will delete its child, which will delete its child and so on until there is no children left to delete (the last next will be NULL thus stopping the "chain reaction").

Of course, you have to be careful if you delete something and you don't want the children deleted. You need to set next to NULL first and then only that item will be deleted (this is what you'd do anyway since you'd need to unlink it from the list).
struct node
{
	void * data;
	node * next;
 
	~node()
	{
		delete next; // Delete my child
	}
};
 
int main()
{
	delete head; // sets of a "chain reaction" so that each node will delete its child
}

Open in new window

0
 
LVL 1

Assisted Solution

by:jefftope
jefftope earned 250 total points
ID: 24312083
If you add a constructor/destructor your code in main needs to know less about your data and hence is is reduced/clearer...
You can then start thinking about classes/public/private data , member accessors etc.


#include "stdafx.h"
#include <iostream>
#include <conio.h>  //for getche()
 
#define _CRTDBG_MAP_ALLOC
 
#include <stdlib.h>
#include <crtdbg.h>
#include <memory>
#include <string>
#include <cstring>
#include <cctype>
#define eq ==
using namespace std ;
 
struct node
{
    node() : data(0),next(NULL){}
    node(node* next_, int data_) : data(data_),next(next_){}
    ~node(){ delete next;}
 
   int data ;
   node* next ;
} ;
 
void push_front( struct node*& head, int data )
{
   head = new node(head, data) ;
}
 
 
void display_contents( struct node* head )
{
   node* foo = head ;
  
   while( foo != NULL )
   {
      cout << "data: " << foo->data << endl ;
      foo = foo->next ;
   }
   
   cout << endl << endl ;
}
 
 
int _tmain(int argc, _TCHAR* argv[])
{
    node* head = new node(NULL, 4);
    head = new node(head, 3);
    head = new node(head, 2);
    head = new node(head, 1);
 
    display_contents( head ) ;
   
    push_front( head, 444 ) ;
 
   display_contents( head ) ;
   
   delete head ;
 
   // Dump memory leaks to output window.	
   _CrtSetDbgFlag ( _CRTDBG_ALLOC_MEM_DF | _CRTDBG_LEAK_CHECK_DF);
   _CrtSetReportMode(_CRT_WARN, _CRTDBG_MODE_FILE | _CRTDBG_MODE_DEBUG);
   _CrtSetReportFile(_CRT_WARN, _CRTDBG_FILE_STDOUT);
   _CrtDumpMemoryLeaks();
 
   _getch();
 
	return 0;
}

Open in new window

0
 
LVL 40

Expert Comment

by:evilrix
ID: 24312132
>> If you add a constructor/destructor
Now I'm sure I already pointed out about the destructor! {http:#24311763}

@jefftope, I see you are a new expert, welcome. Just a point to note, if you are going to repeat what an expert has already said it is common EE courtesy to refer to the original post and the expert who posted it. To do otherwise just comes across as point stealing.
0
 
LVL 1

Expert Comment

by:jefftope
ID: 24312364
@evilrix apologies.
Personally I am not intrested in scoring points (I am in the wrong timezone to score points anyway). I am intrested in giving a more complete solution and hopefully pointing the members in a direction where they can learn good practices. Code is necessarily brief and seldom complete. If you look at the code I posted, you will notice a restructure using the constructor and (your) destructor in context. Given more time we could both talk about copy constructor, assignment operator etc, but by that time I would have suggested moving to STL unless there was good reason to not do so, e.g. where the member is clearly demonstrating an intrest in how C++ works rather than using the available libraries.
0
 
LVL 40

Expert Comment

by:evilrix
ID: 24312445
@jefftope, no worries... just pointing out that it's common etiquette to refer to an existing post, giving credit to the expert, if you are augmenting what's already been said; much like Gregdo has done in his post {http:#24309924}.

Anyway, like I said, welcome and I look forward to working with you in the future. :)
0

Featured Post

Free Tool: Port Scanner

Check which ports are open to the outside world. Helps make sure that your firewall rules are working as intended.

One of a set of tools we are providing to everyone as a way of saying thank you for being a part of the community.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

  Included as part of the C++ Standard Template Library (STL) is a collection of generic containers. Each of these containers serves a different purpose and has different pros and cons. It is often difficult to decide which container to use and …
This article will show you some of the more useful Standard Template Library (STL) algorithms through the use of working examples.  You will learn about how these algorithms fit into the STL architecture, how they work with STL containers, and why t…
The goal of the video will be to teach the user the difference and consequence of passing data by value vs passing data by reference in C++. An example of passing data by value as well as an example of passing data by reference will be be given. Bot…
The viewer will learn how to use the return statement in functions in C++. The video will also teach the user how to pass data to a function and have the function return data back for further processing.

828 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question