C/C++ Help
 
Forums: » Register « |  User CP |  Games |  Calendar |  Members |  FAQs |  Sitemap |  Support | 
 
User Name:
Password:
Remember me
 
Go Back   Dev Articles Community ForumsProgrammingC/C++ Help

Reply
Add This Thread To:
  Del.icio.us   Digg   Google   Spurl   Blink   Furl   Simpy   Y! MyWeb 
Thread Tools Search this Thread Display Modes
 
Unread Dev Articles Community Forums Sponsor:
  #1  
Old April 10th, 2005, 03:30 PM
MealMan401 MealMan401 is offline
Registered User
Dev Articles Newbie (0 - 499 posts)
 
Join Date: Apr 2005
Posts: 2 MealMan401 User rank is Just a Lowly Private (1 - 20 Reputation Level) 
Time spent in forums: 39 m 25 sec
Reputation Power: 0
Exclamation deallocation problem, never been so stuck before.

Hey, I am stuck with something that i don't usually get stuck with. So i am thinking that either i have stumbled across some gotcha quality with the operator delete that i did not know about before, or that the problem is staring me in the face and i just can't see it!!!!!

this is the problem:
I have an array which i allocated. Each item in the array has a linked list tied to it.

So to delete I iterate through the array, and at each index i deallocate the linked list.
and at the end of that, i delete the array with delete [] array

I have done this very same thing many times before. So i would think i know what I am doing,
but apprently i don't because this is the message i get on the very first index while deallocating its linked list:
*** glibc detected *** free(): invalid pointer: 0x0804ee70 ***
Aborted

Also, if i skip the deallocation of the linked lists, and just try deallocating the array with delete [] array, i get almost the same message (with a different pointer value):
*** glibc detected *** double free or corruption (!prev): 0x0804fa70 ***
Aborted

here is the entire code ,the functions that pertain are:
void Mygraph::deletelist()
void file_createlist(const char* filename);
void string_createedges(int v, string* str_edges);

thank you very much to whoever figures it out!!!!

Code:
 /////////////.h////////////////////////
 #include <ostream>
 #include <fstream>
 #include <iostream>
 //#include "Mystack.h"
 using namespace std;
 
 struct EdgeData
 {
 	int weight;
 	struct Node* dest; 
 };
 struct Edge
 {
 	struct EdgeData data;
 	Edge* nextedge;
 };
 
 struct NodeData
 {
 	int nodenumber;
 };
 
 struct Node
 {
 	NodeData data;//container holding node data
 	
 	struct Edge* edges;//list of directed edges connecting vertex (node) to other vertices
 };
 
 
 class Mygraph
 {
 	private:
 	Node* vlist;
 	int size;
 	
 	
 	public:
 	Mygraph();
 	~Mygraph();
 	
 	int getsize();
 	void printlist(ostream& out);
 	void deletelist();
 	bool inorderpath(int source, int dest, bool *visited ,ostream& out);
 	//breadthprint(ostream& out);
 	void file_createlist(const char* filename);
 	void string_createedges(int v, string* str_edges);
 	
 };
 
 /////////////.cpp//////////
 
 Mygraph::Mygraph()
 {
 vlist = 0;
 size = 0;
 }
 
 Mygraph::~Mygraph()
 {
 	deletelist();
 	
 }
 
 void Mygraph::printlist(ostream& out)
 {
 	Edge* edge = 0;
 	out<<"Adjacency List has "<<size<<" vertices"<<endl;
 	for(int i = 0; i < size; i++)
 	{
 		out<<vlist[i].data.nodenumber<<"\t";
 		edge = vlist[i].edges;
 		
 		while(edge)
 		{
 			out<<edge->data.dest->data.nodenumber<<" ";
 			edge = edge->nextedge;
 		}
 		out<<endl;
 	
 	
 	}
 	
 
 }
 
 int Mygraph::getsize()
 {
 	return size;
 }
 
 void Mygraph::deletelist()
 {
 	Edge *nextedge;
 	Edge *doomed;
 	for(int i = 0; i < size; i++)
 	{	
 		doomed = vlist[i].edges;
 		while(doomed)
 		{	cout<<"deleting..."<<endl;
 			nextedge = doomed->nextedge;
 			//delete doomed;
 			doomed = nextedge;
 		}
 	}
 	
 	delete [] vlist;
 }
 bool Mygraph::inorderpath(int source, int dest, bool *visited ,ostream& out)
 {
 	Edge* edge = 0;
 	bool found = false;
 	//check to see if this node has been visited
 	if( !visited[source] )
 	{	
 		//check to see if the this node is the destination node
 		if(vlist[source].data.nodenumber == dest)
 		{
 			found = true;
 			cout<<"Cool..we found a path to "<<dest<<endl;
 			//stack.push(source);
 		}
 		//mark it as visited
 		visited[source] = true;
 		
 		//go through all nodes connected to this one
 		edge = vlist[source].edges;
 		
 		while(edge && !found)
 		{
 			found = inorderpath(edge->data.dest->data.nodenumber,dest, visited,out);
 			if(found)//last node visited was the destination node
 			{
 				//stack.push(source);
 		    cout<<"Currently visiting "<<vlist[source].data.nodenumber<<" on path back from  "<<dest<<endl;
 			}
 			edge = edge->nextedge;
 		}	
 	}
 	return found;
 }
 //void Mygraph::breadthprint(ostream& out);
 void Mygraph::file_createlist(const char* filename)
 {
 	string stringbuf;
 	fstream file;
 	int vindex = 0;
 		
 	file.open(filename,ios::in);
 	if(file.fail())
 	{
 		vlist = 0;
 		return;
 	}
 	
 	
 	//matrix is n by n so find number
 	//of vertices to make array.
 	getline(file,stringbuf);
 	size = stringbuf.length() - 31;
 	vlist = new Node[size];
 	string_createedges(vindex,&stringbuf);
 	
 	
 	
 	for(vindex = 1; !file.eof(); vindex++)
 	{
 		getline(file,stringbuf);
 		if(file.eof())
 			break;
 		vlist[vindex].data.nodenumber = vindex;
 		string_createedges(vindex,&stringbuf);
 		
 	}
 	
 	file.close();
 	return;
 }
 void Mygraph::string_createedges(int v, string* str_edges)
 {
 	Edge** stitch = &(vlist[v].edges);
 	*stitch = 0;
 	
 	int strlength = str_edges->length();
 	
 	for(int i = 0; i < strlength; i+=2)
 	{
 		if( (*str_edges)[i] == '1')
 		{
 			*stitch = new Edge;
 			(**stitch).data.dest = &(vlist[i/2]);
 			stitch = &((**stitch).nextedge);
 			*stitch = 0;//tie up end
 		}
 	}
 }
 
 

Reply With Quote
  #2  
Old April 12th, 2005, 02:05 PM
BoolBooB BoolBooB is offline
Contributing User
Dev Articles Newbie (0 - 499 posts)
 
Join Date: Feb 2005
Posts: 36 BoolBooB User rank is Just a Lowly Private (1 - 20 Reputation Level) 
Time spent in forums: 9 h 35 m 42 sec
Reputation Power: 4
Some comments would help as it's next to impossible to understand what you are trying to do. You're doing some wierd stuff with the pointers and I can't conceptualize what you are trying to build. However this looks mighty suspect to me:
Code:
 
void Mygraph::string_createedges(int v, string* str_edges)
{
	Edge** stitch = &(vlist[v].edges);
	*stitch = 0;
 
	int strlength = str_edges->length();
 
	for(int i = 0; i < strlength; i+=2)
	{
		if( (*str_edges)[i] == '1')
		{
			*stitch = new Edge;	 <- you allocate a new Edge here
			(**stitch).data.dest = &(vlist[i/2]);
			stitch = &((**stitch).nextedge);
			*stitch = 0;//tie up end <- and here you blow away the pointer to it. 
		}
	}
}


This looks suspect as well:
Code:
	
for(vindex = 1; !file.eof(); vindex++) <- why are you starting at index 1 and not index 0?
{
	getline(file,stringbuf)
	if(file.eof())
			break;
	vlist[vindex].data.nodenumber = vindex;
	string_createedges(vindex,&stringbuf);
}



Also just a coding style question but your struct NodeData only has one element and it's a simple type of int. Why make this a struct at all?

Also, this seems kind of convoluted: your Node points to an Edge, but then your Edge points at a Node through the EdgeData. I can't picture what you are trying to build, or what goes where.

Reply With Quote
  #3  
Old April 12th, 2005, 11:17 PM
MealMan401 MealMan401 is offline
Registered User
Dev Articles Newbie (0 - 499 posts)
 
Join Date: Apr 2005
Posts: 2 MealMan401 User rank is Just a Lowly Private (1 - 20 Reputation Level) 
Time spent in forums: 39 m 25 sec
Reputation Power: 0
Well basically its a graph. The structures are are only in place in case that more data is added to the nodes and /or edges.
As for the pointer stuff, I am using a double pointer to build the list as it doesn't need special cases for the root pointer and the end pointer in case of a doubly linked list.


I did actually figure out my problem. I was passing my graph to a function by value, so when the function was done the graph was destroyed, but since the freed memory did not have much time to get currupted, only a bit of would be and it wasn't readily apparent.

Yes I acknowledge the program is bloated beyond the point of ridiculous....but i was trying stuff out!


thanks for the reply!

Reply With Quote
Reply

Viewing: Dev Articles Community ForumsProgrammingC/C++ Help > deallocation problem, never been so stuck before.


Thread Tools  Search this Thread 
Search this Thread:

Advanced Search
Display Modes  Rate This Thread 
Rate This Thread:


Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

vB code is On
Smilies are On
[IMG] code is On
HTML code is Off
View Your Warnings | New Posts | Latest News | Latest Threads | Shoutbox
Forum Jump

 Free IT White Papers!
 
How to Present Effectively Online
This white paper offers practical and actionable advice on the key steps that any presenter should consider as they plan and execute a Webinar or online meeting.

Request Your Free Technology Downloads!
 
Open Source Security Myths
Open Source Software (OSS) is computer software whose source code is available to the general public with relaxed or non-existent intellectual property restrictions (or arrangement such as the public domain), and is usually developed with the input of many contributors.

Request Your Free Technology Downloads!
 
Power and Cooling Capacity Management for Data Centers
This paper describes the principles for achieving power and cooling capacity management.

Request Your Free Technology Downloads!
 
Scalable, Fault-Tolerant NAS for Oracle - The Next Generation
For several years NAS has been evolving as a storage alternative for Oracle databases, and for good reason: NAS is quite often the simplest, most cost-effective storage approach for Oracle. Learn about the benefits that HP's approach to scalable NAS brings to Oracle environments in this comprehensive white paper.

Request Your Free Technology Downloads!
 
Understanding Web Application Security Challenges
This white paper discusses many common threats and preventive measures for Web application security, and explains what you can do to help protect your organization.

Request Your Free Technology Downloads!
 

Forums: » Register « |  User CP |  Games |  Calendar |  Members |  FAQs |  Sitemap |  Support | 
  
 





© 2003-2008 by Developer Shed. All rights reserved. DS Cluster 4 hosted by Hostway
Stay green...Green IT