Solved

Push function for Linked List leaking memory

Posted on 2009-05-05
9
264 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
PRTG Network Monitor: Intuitive Network Monitoring

Network Monitoring is essential to ensure that computer systems and network devices are running. Use PRTG to monitor LANs, servers, websites, applications and devices, bandwidth, virtual environments, remote systems, IoT, and many more. PRTG is easy to set up & use.

 
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

PRTG Network Monitor: Intuitive Network Monitoring

Network Monitoring is essential to ensure that computer systems and network devices are running. Use PRTG to monitor LANs, servers, websites, applications and devices, bandwidth, virtual environments, remote systems, IoT, and many more. PRTG is easy to set up & use.

Question has a verified solution.

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

Unlike C#, C++ doesn't have native support for sealing classes (so they cannot be sub-classed). At the cost of a virtual base class pointer it is possible to implement a pseudo sealing mechanism The trick is to virtually inherit from a base class…
This article shows you how to optimize memory allocations in C++ using placement new. Applicable especially to usecases dealing with creation of large number of objects. A brief on problem: Lets take example problem for simplicity: - I have a G…
The viewer will learn additional member functions of the vector class. Specifically, the capacity and swap member functions will be introduced.
The viewer will be introduced to the member functions push_back and pop_back of the vector class. The video will teach the difference between the two as well as how to use each one along with its functionality.

810 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