Solved

Push function for Linked List leaking memory

Posted on 2009-05-05
9
259 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
Comment Utility
>> 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
Comment Utility
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
Comment Utility

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
 
LVL 2

Accepted Solution

by:
Gregdo earned 250 total points
Comment Utility
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
Better Security Awareness With Threat Intelligence

See how one of the leading financial services organizations uses Recorded Future as part of a holistic threat intelligence program to promote security awareness and proactively and efficiently identify threats.

 
LVL 40

Expert Comment

by:evilrix
Comment Utility
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
Comment Utility
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
Comment Utility
>> 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
Comment Utility
@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
Comment Utility
@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

How to improve team productivity

Quip adds documents, spreadsheets, and tasklists to your Slack experience
- Elevate ideas to Quip docs
- Share Quip docs in Slack
- Get notified of changes to your docs
- Available on iOS/Android/Desktop/Web
- Online/Offline

Join & Write a Comment

Errors will happen. It is a fact of life for the programmer. How and when errors are detected have a great impact on quality and cost of a product. It is better to detect errors at compile time, when possible and practical. Errors that make their wa…
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 be introduced to the technique of using vectors in C++. The video will cover how to define a vector, store values in the vector and retrieve data from the values stored in the vector.

762 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

Need Help in Real-Time?

Connect with top rated Experts

6 Experts available now in Live!

Get 1:1 Help Now