Want to win a PS4? Go Premium and enter to win our High-Tech Treats giveaway. Enter to Win

x
?
Solved

Push function for Linked List leaking memory

Posted on 2009-05-05
9
Medium Priority
?
279 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
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
  • 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
Independent Software Vendors: We Want Your Opinion

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

 
LVL 2

Accepted Solution

by:
Gregdo earned 1000 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 1000 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

Independent Software Vendors: We Want Your Opinion

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

Question has a verified solution.

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

Often, when implementing a feature, you won't know how certain events should be handled at the point where they occur and you'd rather defer to the user of your function or class. For example, a XML parser will extract a tag from the source code, wh…
Go is an acronym of golang, is a programming language developed Google in 2007. Go is a new language that is mostly in the C family, with significant input from Pascal/Modula/Oberon family. Hence Go arisen as low-level language with fast compilation…
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.
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.
Suggested Courses

610 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