appending a linklist node that has a linklist as a member

[Khillz3000]

I am having trouble appending a class object node that has a member that is a linklist to that class object's linklist. The main linklist is called CDList. It is made of of CD class objects. One of the members of the CD class object is a linklist of structures called CdContence. It has members that hold a song title and length. I cant seem to get the program to append a CD class object to the CDList linklist. I can make it work just fine IF the members(song/songLength) of the CD node's linklist are empty. If I have assigned values to the members song and songLength and have appended those to the linklist in the CD class node, then I cannot get the program to append the CD node to CDList. (I hope the wording of my question makes sense cause this is hard to explain).

Ex.

Linklist<CD> CDList;

CD album1;

CDList.appendNode(album1); //this works fine

****However******

Linklist<CD> CDList; //Linklist that stores CD class objects

CD album1;  //CD class object has a member 'contence' that is a linklist

CdContence temp; //structure for linklist in the CD class that holds song titles and length's

temp.song = "song 1";

temp.length = "2:34";

album1.contence.appendNode(temp); //cont is the name of the linklist member in CD class

//now the list in the CD class object has at least one node that has data.

CDList.appendNode(album1);// This is where the program thows an error and quits working.  I don't understand why.

Any Ideas??

[ShodanHo]

Can you post the error, and the code?

[Khillz3000]

Here are the classes and the appendNode function. I can post more code if needed.

template <class T>
class ListNode
{
	public:
		
		T value1;
		ListNode<T> *next;
		
	public:
	
		//***Constructors***
		ListNode();
		ListNode(T);
		
};
template <class T>
class LinkList
{
		private:
		
		ListNode<T>  *head;
	
		public:
		//***Constructor***
		LinkList();
		
		//***Destructor***
		~LinkList();
		

		//***LinkList Operations***
		
		void appendNode(T);
		void insertNode(T);
		void deleteNode(T);
		T getNodeData();
		T getNext();
		void displayList() const;
		T getHead();
		bool searchList(T);

};

class CD : public Media
{
	public:
		
		LinkList<CdContence> contence;
		
	public:
		
		//***Constructors***
		CD(string, string);
	        CD();
		
		//***Mutators***
		void setCD(string, string, string, string);
		

		//***Accessors***
		LinkList<CdContence> getCD();
	

		//Overloaded Operators
		
		bool operator < (CD &);
		bool operator > (CD &);
		bool operator != (CD &);
		bool operator == (CD &);
};

class Media
{
	private:
		
		string title;
		string length;
		

	public:
		
		//***Constructors***
		Media();
		Media(string, string);
		
		//***Mutators***
		void setTitle(string);
		void setLength(string);

		//***Accessors***
		string getTitle();
		string getLength();

		//Overloaded Operators
		
		bool operator < (const Media &);
		bool operator > (const Media &);
		bool operator != (const Media &);
		bool operator == (const Media &right);
};


//LinkList template function to append a node
template <class T>
void LinkList<T>::appendNode(T val1)
{
	ListNode<T> *newNode;
	ListNode<T> *nodePtr;

	newNode = new ListNode<T>(val1);

	if (!head)
	{
		head = newNode;
	}
	else
	{
		nodePtr = head;

		while (nodePtr->next)
			
			nodePtr = nodePtr->next;

		nodePtr->next = newNode;
	}
}		

The error is actually and exception:

First-chance exception at 0x523A7508 (msvcr110d.dll) in FinnalProjectMain.exe: 0xC0000005: Access violation reading location 0xFEEEFEE2.

Using the debugger it brings up this:

            /* get a pointer to memory block header */
            pHead = pHdr(pUserData);

             /* verify block type */
            _ASSERTE(_BLOCK_TYPE_IS_VALID(pHead->nBlockUse));

[Khillz3000]

Should I post more code?

[Khillz3000]

Still need help with this one. I have played witht he debugger a little. The program runs through the appendNode function but executes an exception as soon as it leaves the function. The debugger brings up a delete function from a file called dbgdel.cpp

void operator delete(
        void *pUserData
        )
{
        _CrtMemBlockHeader * pHead;

        RTCCALLBACK(_RTC_Free_hook, (pUserData, 0));

        if (pUserData == NULL)
            return;

        _mlock(_HEAP_LOCK);  /* block other threads */
        __TRY

            /* get a pointer to memory block header */
            pHead = pHdr(pUserData);

             /* verify block type */
            _ASSERTE(_BLOCK_TYPE_IS_VALID(pHead->nBlockUse));

            _free_dbg( pUserData, pHead->nBlockUse );

        __FINALLY
            _munlock(_HEAP_LOCK);  /* release other threads */
        __END_TRY_FINALLY

        return;
}

Is this some kind of destructor issue?

[AbstractionAnon]

Clearly delete is being called somewhere. I see no calls to delete in AppendNode. Nor do I see any objects allocated locally which would implicity call their destructor when they go out of scope.

However, at liner 105 you're passing val1 in by value. This means that val1 was constructed before the call to AppendNode and T's destructor will be called upon the return from AppendNode. I would suggest looking at T's desctructor and make sure any deletes in T's destructor are valid.

Using your debugger, you should be able to see the call stack and that should show the caller of delete.

[Khillz3000]

Looking at the call stack is a bit confusing for a noob like my self but I will try and interpret it.

 	msvcr110d.dll!operator delete(void * pUserData) Line 52	C++
 	FinnalProjectMain.exe!std::allocator<char>::deallocate(char * _Ptr, unsigned int __formal) Line 586	C++
 	FinnalProjectMain.exe!std::_Wrap_alloc<std::allocator<char> >::deallocate(char * _Ptr, unsigned int _Count) Line 888	C++
 	FinnalProjectMain.exe!std::basic_string<char,std::char_traits<char>,std::allocator<char> >::_Tidy(bool _Built, unsigned int _Newsize) Line 2265	C++
 	FinnalProjectMain.exe!std::basic_string<char,std::char_traits<char>,std::allocator<char> >::~basic_string<char,std::char_traits<char>,std::allocator<char> >() Line 965	C++

I think I understand whats going on from here down. Its what is above this that I don't get.
I think that its having trouble deleting a node pointer for the CD class. I don't have a destructor written for the CD class and haven't been successful at writing one. If that's the problem I would sure love some help writing one.

FinnalProjectMain.exe!CdContence::~CdContence()	C++
 	FinnalProjectMain.exe!ListNode<CdContence>::~ListNode<CdContence>()	C++
>	FinnalProjectMain.exe!ListNode<CdContence>::`scalar deleting destructor'(unsigned int)	C++
 	FinnalProjectMain.exe!LinkList<CdContence>::~LinkList<CdContence>() Line 96	C++
 	FinnalProjectMain.exe!CD::~CD()	C++
 	FinnalProjectMain.exe!LinkList<CD>::appendNode(CD val1) Line 126	C++
 	FinnalProjectMain.exe!main() Line 70	C++
 	FinnalProjectMain.exe!__tmainCRTStartup() Line 536	C
 	FinnalProjectMain.exe!mainCRTStartup() Line 377	C
 	kernel32.dll!7609338a()	Unknown
 	[Frames below may be incorrect and/or missing, no symbols loaded for kernel32.dll]	
 	ntdll.dll!76f39f72()	Unknown
 	ntdll.dll!76f39f45()	Unknown

[Khillz3000]

Still need help. This is the line that the program stops at:

 /* verify block type */
            _ASSERTE(_BLOCK_TYPE_IS_VALID(pHead->nBlockUse));

Do i need a destructor for CD class?

[Khillz3000]

Any ideas? Im still not sure whats going on.

[AbstractionAnon]

Let's work our way backwards.

msvcr110d.dll!operator delete(void * pUserData) Line 52

In the delete routine, the code is stopping on the _ASSERTE statement which is checking that the block that is about to be released is valid. That check is failing for one of two reasons. 1) The pointer to the block is bad, or 2) the pointer is valid, but the block has been corrupted.

delete was called from std::allocator<char>::deallocate(char * _Ptr, unsigned int __formal) Line 586. This the deallocate funtion of an allocator of type char.

Backing up farther we see std::basic_string<char,std::char_traits<char>,std::allocator<char> >::~basic_string<char,std::char_traits<char>,std::allocator<char> >() Line 965 we see a desctrcutor for ~basic_string. So we can conclude that a std::string is being destructed.

Backing up one more level, we see one CdContence::~CdContence which is CdContence's destructor. From that and the previous stack frame, we can conclude that a std::string inside CdContence is being destructed. I don't see any code for your CdContence class, so I can't tell what's happening in CdContence's destructor.

[Khillz3000]

Cdcontence is a struct that has two string members. How do check to see if the problem is the pointer or the block? Once i figure that out how do i fix it. I feel like Im a bit over my head but I really want to understand this, learn from it and move on. Thank you for you help and explinations. Im certi.anly learning from this.
EDIT: I dont have any char member variables iny any of the classes or structs. Why is it deallocating char?

[AbstractionAnon]

How do check to see if the problem is the pointer or the block?

Change your scope in the debugger to CdContence's destructor. If you're using Visual Studio, double click on the destructor's line in the call stack. You should now be able to see the members of CdContence and determine if they're valid. It would also help if you posted the declaration for your CdContence class.

Why is it deallocating char?

std::string is a template which inherits std::basic_string. In this case, basic_string is specialized by type char. There is also a class wstring which also inherits basic_string, but specializes it with wchar_t to support wide characters. At the lowest level, basic_string is allocating and deallocating space to hold your string. It does that by using an allocator that is specialized by either char or wchar_t.

[Khillz3000]

Here is the declaration of CdContence:

struct CdContence
{
	string song;
	string length;

};

I don't have a destructor written for it or any constructors, accessors or mutators. Do I need those?

Thanks again for the explanation of the stack call and what was going on. I definitely am getting a better feel for the details and look forward to understanding exactly why it is having problems deallocating.

[AbstractionAnon]

I don't have a destructor written for it or any constructors, accessors or mutators. Do I need those?

No. That struct is very straight forward. The strings should clean themselves up.

Since you have no explicit dynamic allocation taking place, I have to assume that one or both of the strings have been overwritten somehow.

If you change the scope of the debugger to CdContence's destructor as I suggested earlier, you should be able to see both song and length variables. Understand that each string is a class instance and each instance will have a struct that is used to manage the string. You haven't said what compiler you're using. In Visual Studio, you should see something like the following for each of your strings.

  _alval - Ignore this.  It is used by the allocator
  _bx - This is a union.  Only one of the following two items will be valid. 
    _buf - Used only if string is <= 15 bytes
    _ptr - Points to dynamic memory if string is > 15 bytes
  _mysize - How big is the string
  _myres - how much space is reserved for the string

If you expand these two structs in your debugger, you should be able to determine if the string structs are valid, or if one or both have been overwritten.

[Khillz3000]

I'm using visual studio, sorry. I clicked on the call stack line below (I assume this is the destructor call) to change the scope of my debugger.

FinnalProjectMain.exe!CdContence::~CdContence()	C++

this is what I got(The arrow was pointing at line 12):

00EF50EB  push        edi  
00EF50EC  push        ecx  
00EF50ED  lea         edi,[ebp-0CCh]  
00EF50F3  mov         ecx,33h  
00EF50F8  mov         eax,0CCCCCCCCh  
00EF50FD  rep stos    dword ptr es:[edi]  
00EF50FF  pop         ecx  
00EF5100  mov         dword ptr [this],ecx  
00EF5103  mov         ecx,dword ptr [this]  
00EF5106  add         ecx,1Ch  
00EF5109  call        std::basic_string<char,std::char_traits<char>,std::allocator<char> >::~basic_string<char,std::char_traits<char>,std::allocator<char> > (0EF146Ah)  
00EF510E  mov         ecx,dword ptr [this]  
00EF5111  call        std::basic_string<char,std::char_traits<char>,std::allocator<char> >::~basic_string<char,std::char_traits<char>,std::allocator<char> > (0EF146Ah)  
00EF5116  pop         edi  

It kind of looks like your example. Looking at it though I can see where it called the allocator for the strings....so...it doesn't look like anything is wrong (of course I've never seen this before so I'm not sure what exactly to look for)

[Khillz3000]

00EF5111  call        std::basic_string<char,std::char_traits<char>,std::allocator<char> >::~basic_string<char,std::char_traits<char>,std::allocator<char> > (0EF146Ah)  
00EF5116  pop         edi  
00EF5117  pop         esi  
00EF5118  pop         ebx  
00EF5119  add         esp,0CCh  
00EF511F  cmp         ebp,esp  
00EF5121  call        __RTC_CheckEsp (0EF149Ch)  
00EF5126  mov         esp,ebp  
00EF5128  pop         ebp  
00EF5129  ret  
00EF512A  int         3  

These are the lines below the call in case you need those. It repeats " int 3 " for many lines below that. Then stops at a file path for the file the program is written in.

[AbstractionAnon]

That looks more like the constructor. Note the calls to basic_string at lines 11 and 13.

I wasn't looking for the assembly window. I was referring to the locals window. Sorry about not making that clear.

[Khillz3000]

Still need help.... so after messing with this for a while and with help from AbstractAnon i have definetly determined that it is in fact a CD or LinkList destructor that is trying to free memory at the same location twice. I however cannot seem to get around it. I'm posting my code and hoping that some one will run it and perhaps show me a way around this problem. I commented the point that I'm having the issure. It has to do with when I pass the temp CD object into insert node. Line 61 in main below.

//Header file for LinkList Class
#ifndef LINKLIST_H
#define LINKLIST_H

//#include "stdafx.h"

#include <iostream>

using namespace std;


template <class T>
class LinkList
{
		private:
		
		struct ListNode
		 {
			 T value1;                
			 struct ListNode *next;  
		 }; 

		ListNode *head;   // List head pointer
	
		public:
		//***Constructor***
		LinkList();
		
		//***Destructor***
		~LinkList();
		
		//***LinkList Operations***
		void appendNode(T);
		void insertNode(T);
};

//Implimentation for LinkList

//***Constructor***
template <class T>
LinkList<T>::LinkList()
{
	head = NULL;
}

//***Destructor***
template <class T>
LinkList<T>::~LinkList()
{
	ListNode *nodePtr;
	ListNode *nextNode;

	nodePtr = head;

	while(nodePtr != NULL)
	{
		nextNode = nodePtr->next;
		delete nodePtr;

		nodePtr = nextNode;
	}
}


//***LinkList Operations***
template <class T>
void LinkList<T>::appendNode(T val1)
{
	ListNode *newNode;
	ListNode *nodePtr;

	//newNode = new ListNode(val1);
   newNode = new ListNode;
   newNode->value1 = val1;
   newNode->next = NULL;
	if (!head)
	{
		head = newNode;
	}
	else
	{
		nodePtr = head;

		while (nodePtr->next)
			
			nodePtr = nodePtr->next;

		nodePtr->next = newNode;
	}
}

template <class T>
void LinkList<T>::insertNode(T val1)
{
	ListNode *newNode;
	ListNode *nodePtr;
	ListNode *prevNode = NULL;

	//newNode = new ListNode(val1);
   newNode = new ListNode;
   newNode->value1 = val1;
   newNode->next = NULL;
	
	if (!head)
	{
		head = newNode;
		newNode->next = NULL;
	}
	else
	{
		nodePtr = head;
		prevNode = NULL;
		
		while(nodePtr != NULL && nodePtr->value1 < val1)
		{
			prevNode = nodePtr;
			nodePtr = nodePtr->next;
		}

		if(prevNode == NULL)
		{	
			head = newNode;
			newNode->next = nodePtr;
		}
		else
		{
			prevNode->next = newNode;
			newNode->next = nodePtr;
		}
	}
}
#endif 

//Media Header File
//
#ifndef MEDIA_H
#define MEDIA_H
#include "stdafx.h"
#include <iostream>
#include <iomanip>
#include <string>

using namespace std;

class Media
{
	private:
		
		string title;
		string length;
		
         public:
		
		//***Constructors***
		Media();
		Media(string, string);
		
		//***destructor***
		~Media();
		
		//***Mutators***
		void setTitle(string);
		void setLength(string);

		//***Accessors***
		string getTitle();
		string getLength();

		//Overloaded Operators
		
		bool operator < (const Media &);
		bool operator > (const Media &);
		bool operator != (const Media &);
		bool operator == (const Media &right);
};

/*****Implimentation*********/
//***Constructors***
Media::Media()
{
	title = "  ";
	length = " ";
}

//***Constructors***
Media::Media(string t, string l)
{
	title = t;
	length = l;
}

Media::~Media()
{
	cout<<"Media destructor"<<endl;
}

//***Mutators***		
void Media::setTitle(string t)
{
	title = t;
}


void Media::setLength(string l)
{
	length = l;
}

//***Accessors***
string Media::getTitle()
{
	return title;
}

string Media::getLength()
{
	return length;
}

//***Overloades operators***
bool Media::operator < (const Media &right)
{
   bool status;

   if (title < right.title)
      status = true;
   
   else
      status = false;

   return status;
}

bool Media::operator > (const Media &right)
{
   bool status;

   if (title > right.title)
      status = true;
   else
      status = false;

   return status;
}

bool Media::operator != (const Media &right)
{
   bool status;

   if (*this == right)
      status = false;
   else 
      status = true;

   return status;
}

bool Media::operator == (const Media &right)
{
   bool status;

   if (title == right.title)
      status = true;
   
   else
      status = false;

   return status;
}

ostream &operator<<(ostream &strm, Media &obj)
{
	strm <<"Media Title:  "<< obj.getTitle() << "\n"
		 <<"Media Length: "<< obj.getLength() <<endl;
   return strm;
}
#endif 

//Class CD Header File
//
#ifndef CD_H
#define CD_H
#include "stdafx.h"
#include "LinkList.h"
#include "Media.h"
#include <iostream>
#include <iomanip>
#include <string>

using namespace std;

//LinkList structure for CD class
struct CdContence
{
	string song;
	string length;

	
};

class CD : public Media
{
	public:
		
		LinkList<CdContence> Cd;

		//***Constructors***
		CD(string, string);
	    CD();
		
		//***destructor***
		~CD();
		
		//***Accessors***
		LinkList<CdContence> getCD();
	
		//Overloaded Operators
		bool operator < (CD &);
		bool operator > (CD &);
		bool operator != (CD &);
		bool operator == (CD &);
};

/*****Implimentation*********/
//***Constructors***
CD::CD(string T, string L)
{
	setTitle(T);
	setLength(L);
	LinkList<CdContence>();
	cout<<"CD CONSTRUCTOR2"<<endl;
}

CD::CD()
{
	setTitle(" ");
	setLength(" ");
	LinkList<CdContence>();
cout<<"CD CONSTRUCTOR"<<endl;
}

CD::~CD()
{
	cout<<"CD destructor"<<endl;	
}



//***Accessors***
LinkList<CdContence> CD::getCD()
{
	return Cd;
}


//***Overloades operators***
bool CD::operator < (CD &right)
{
   bool status;

   if (getTitle() < right.getTitle())
      status = true;
   
   else
      status = false;

   return status;
}

bool CD::operator > (CD &right)
{
   bool status;

   if (getTitle() > right.getTitle())
      status = true;
   else
      status = false;

   return status;
}

bool CD::operator != (CD &right)
{
   bool status;

   if (*this == right)
      status = false;
   else 
      status = true;

   return status;
}

bool CD::operator == (CD &right)
{
   bool status;

   if (getTitle() == right.getTitle())
      status = true;
   
   else
      status = false;

   return status;
}

ostream &operator<<(ostream &strm, CD &obj)
{
	strm 
		<<"CD Title:  "<< obj.getTitle() << "\n"
		<<"CD Length: "<< obj.getLength()<< "\n"
		<<endl;

	return strm;
}
ostream &operator<<(ostream &strm, CdContence &obj)
{
	strm 
		<<"Song Title:  "<< obj.song << "\n"
		<<"Song Length: "<< obj.length << "\n"
		<<endl;
  
	return strm;
}
#endif 

// FinnalProjectMain.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include "CD.h"

void addCD(LinkList<CD> *);
int main()
{
	LinkList<CD> CDList;
	
	addCD(&CDList);
	
	cout<<"got here"<<endl;
	return 0;
}
void addCD(LinkList<CD> *cdList)
{
	
	CD temp;
	CdContence contTemp;
	string title;
	string cdLength;
	string song;
	string songLength;
	char another;
	char anotherCD;
	
	do
	{
		cout<<"Please enter Title of the CD:"<<endl;
		cout<<"Title: ";getline(cin,title);
	
		cout<<"Please enter the Length of the CD: "<<endl;
		cout<<"Length: ";getline(cin,cdLength);

		do
		{
			cout<<"Please enter Title of a song"<<endl;
 			cout<<"Song title: ";getline(cin,song);
		
			cout<<"Please enter the Length of that song"<<endl;
			cout<<"Song length: ";getline(cin,songLength);
			
			contTemp.song = song;
			contTemp.length = songLength;

			temp.Cd.appendNode(contTemp);

			cout<<"Would you like to enter another song?"<<endl;
			cout<<"Another: ";cin>>another;
	
			cin.ignore();
			while(toupper(another)!='Y' && toupper(another)!='N')
			{
				cout<<"Please enter Y or N"<<endl;
				cin>>another;
			}
		}while (toupper(another)=='Y');
	
	//This is where I think the problem is and I cant
        //figure out how to get past it.

               cdList->insertNode(temp);

		cout<<"Would you like to enter another CD?"<<endl;
		cout<<"Another CD: ";cin>>anotherCD;
		
		cin.ignore();
		while(toupper(anotherCD)!='Y' && toupper(anotherCD)!='N')
		{
			cout<<"Please enter Y or N"<<endl;
			cin>>anotherCD;
		}

	}while (toupper(anotherCD)=='Y');

}//end function 

[cire]

Your LinkList type has no copy constructor and you're making copies of LinkList instances.

[Edit: Btw, it's spelled "contents"]

[Khillz3000]

I was told that template copy constructors was a no no(not that I cant use one but its a bad practice to do so). Also I'm not sure where exactly I would use it. Should I copy the CD temp before I pass it to the CDList.insertNode()?