Jump to content
  • Advertisement
Sign in to follow this  
raccoonone

Bug in Visual C++ 2003?

This topic is 4621 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I was doing my homework for my data structures class, which involves a priority queue using an array based min heap. I wrote the following code. The problem is that when I use the vSwap(), instead of just writting code to do the swap inside the vReheapify() functions, the pointers in my data get messed up. I'm using the queue in the following manner:
struct PathNode
{
	int iCurVert, iTotalWeight;
	CGenericQueue<int> Path;
};
CHeapPriorityQueue<PathNode> MainQueue;

After calling vSwap, the pointers inside CGenericQueue<int> Path; are pointing to garbage. Is there something wrong with my code, or is this a bug in Visual C++? I showed the code to my teacher, and he thought it must be a bug.
template <class DataType> class Node
{
public:
	int iPriority;
	DataType Data;
	Node *next;
};
template <class DataType> class CGenericQueue
{
protected:
	Node<DataType> *head, *tail;
public:
	CGenericQueue();
	~CGenericQueue();
	void vEnque(const DataType &item);
	int iDeque(DataType &returndata);
	CGenericQueue<DataType> & operator = (const CGenericQueue<DataType> &);
};

template <class DataType> CGenericQueue<DataType> & CGenericQueue<DataType>::operator = (const CGenericQueue<DataType> &From)
{
	//remove everything from the queue
	DataType x;
	while(iDeque(x));
	//enque the new data
	Node<DataType> *cur = From.head;
	for(; cur != NULL; cur = cur->next)
	{
		vEnque(cur->Data);
	}
	return *this;
}

template <class DataType> CGenericQueue<DataType>::~CGenericQueue()
{

	while(head != NULL)
	{
		Node<DataType> *temp = head;
		head = head->next;
		delete temp;
	}
}

template <class DataType> int CGenericQueue<DataType>::iDeque(DataType &returndata)
{
	Node<DataType> *temp;
	//Queue is empty
	if(head == NULL)
		return 0;

	returndata = head->Data;
	temp = head;
	head = head->next;
	delete temp;
	return 1;
}

template <class DataType> void CGenericQueue<DataType>::vEnque(const DataType &item)
{
	Node<DataType> *tempnode = new Node<DataType>;
	tempnode->next = NULL;
	tempnode->Data = item;
	tempnode->iPriority = 0;
	if(head == NULL)
		head = tail = tempnode;
	else
	{
		tail->next = tempnode;
		tail = tail->next;
	}
}

template <class DataType> CGenericQueue<DataType>::CGenericQueue()
{
	head = tail = NULL;
}
template <class Typex> void vSwap(Typex &x, Typex &y)
{
	Typex temp = x;
	x = y;
	y = temp;
}

template <class DataType> class ArrayNode
{
public:
	int iPriority;
	DataType Data;
};

template <class DataType> class CHeapPriorityQueue
{
public:
	void vEnque(const DataType &item, int iPriority);
	int iDeque(DataType &ReturnData);
	CHeapPriorityQueue(int x = 100);
	//~CHeapPriorityQueue();
protected:
	void vReheapifyUp(); //Restores the last item
	void vReheapifyDown(); //Restore the first item
	int iGetParent(int x) {return (x - 1) / 2;}
	int iGetRightChild(int x) {return (x + 1) * 2;}
	int iGetLeftChild(int x) {return ((x + 1) * 2) - 1;}
	ArrayNode<DataType> m_Data[25];
	int m_iLength;
};

template <class DataType> void CHeapPriorityQueue<DataType>::vEnque(const DataType &item, int iPriority)
{
	m_Data[m_iLength].Data = item;
	m_Data[m_iLength].iPriority = iPriority;
	m_iLength++;
	vReheapifyUp();
}

template <class DataType> int CHeapPriorityQueue<DataType>::iDeque(DataType &ReturnData)
{
	if(!m_iLength)
		return 0;
	ReturnData = m_Data[0].Data;
	m_Data[0] = m_Data[m_iLength - 1];
	m_iLength--;
	vReheapifyDown();
	return 1;
}

template <class DataType> void CHeapPriorityQueue<DataType>::vReheapifyDown()
{
	for(int cur = 0; iGetLeftChild(cur) < m_iLength;)
	{
		if(m_Data[iGetLeftChild(cur)].iPriority < m_Data[iGetRightChild(cur)].iPriority)
		{
			//vSwap(m_Data[iGetLeftChild(cur)], m_Data[cur]);
			ArrayNode<DataType> temp;
			temp = m_Data[iGetLeftChild(cur)];
			m_Data[iGetLeftChild(cur)] = m_Data[cur];
			m_Data[cur] = temp;
			cur = iGetLeftChild(cur);
		}
		else
		{
			//vSwap(m_Data[iGetRightChild(cur)], m_Data[cur]);
			ArrayNode<DataType> temp;
			temp = m_Data[iGetRightChild(cur)];
			m_Data[iGetRightChild(cur)] = m_Data[cur];
			m_Data[cur] = temp;
			cur = iGetRightChild(cur);
		}
	}
}

template <class DataType> void CHeapPriorityQueue<DataType>::vReheapifyUp()
{
	for(int cur = m_iLength - 1; cur > 0;)
	{
		if(m_Data[cur].iPriority < m_Data[iGetParent(cur)].iPriority)
		{
			//vSwap(m_Data[iGetParent(cur)], m_Data[cur]);
			ArrayNode<DataType> temp;
			temp = m_Data[iGetParent(cur)];
			m_Data[iGetParent(cur)] = m_Data[cur];
			m_Data[cur] = temp;
			cur = iGetParent(cur);
		}
		else
			return;
	}
}

template <class DataType> CHeapPriorityQueue<DataType>::CHeapPriorityQueue(int x)
{
	//m_Data = new ArrayNode<DataType>[x];
	m_iLength = 0;
}

Share this post


Link to post
Share on other sites
Advertisement
Have you stepped through the code in a debugger and seen exactly when the pointers are getting thrashed? You can stare at code all day without learning nearly as much as actually watching the program run for five minutes.

CM

Share this post


Link to post
Share on other sites
Yes I have. The pointers are fine until the vSwap() function returns. In fact inside the function they're ok, but after it returns they point to garbage.

Share this post


Link to post
Share on other sites
From looking at it, it seems the problem is that you haven't declared a copy constructor for your class. The default copy constructor generated by the compiler just copies the pointers, which means that bad voodoo magic happens when the temporary gets deleted.

And yes, I know it looks like you never use the copy constructor, but the temp declaration in your vSwap() function is actually calling a copy constructor instead of default constructing and then calling assign.

Share this post


Link to post
Share on other sites
I declared a copy constuctor here:

*edit* That is a copy constructor that I declared, right? Sorry, I'm not familiar with all the terms yet.


template <class DataType> CGenericQueue<DataType> & CGenericQueue<DataType>::operator = (const CGenericQueue<DataType> &From)
{
//remove everything from the queue
DataType x;
while(iDeque(x));
//enque the new data
Node<DataType> *cur = From.head;
for(; cur != NULL; cur = cur->next)
{
vEnque(cur->Data);
}
return *this;
}




Do I need one for ArrayNode also? I thought that when the default copy constuctor for ArrayNode was called, it would call the custom copy constructor for CGenericQueue.

Share this post


Link to post
Share on other sites
That's not a copy constructor; that's the assignment operator. A copy constructor is a constructor that takes a (const) reference to the type as a parameter. In this case it'd be CGenericQueue(const CGenericQueue &);

Share this post


Link to post
Share on other sites
Quote:
Original post by Procyon Lotor
I declared a copy constuctor here:

That's not a copy constructor, that's an assignment operator. You want both if you have either. Those, plus a destructor [which you've already got under control].

CM

Share this post


Link to post
Share on other sites
Quote:
Original post by Procyon Lotor
Oh ok, thanks:)

And in the copy constructor I would want to do the same thing I did in the assignment operator, basicly?

Exactly the same, except without cleaning up at the begining and returning *this at the end.

CM

Share this post


Link to post
Share on other sites
Yay! You guys are my heros, that's fixed it:) I was pretty dubious when my teacher said he thought it was a bug in Visual C++, but I wasn't in much of a position to argue, since I had no clue what was wrong.

Just so I understand why this happened. Copy constructors are called when I do something like this?

DataType x = y;

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!