Archived

This topic is now archived and is closed to further replies.

Zaei

Queue

Recommended Posts

Ok, This is beginning to get on my nerves. I have designed a simple Queue class (because the STL version was ALSO giveing me problems). Anyway, the problem is, that when I try to "delete" a node, i get an access violation. here is the source:
  
template <class t>
struct QNode
{
	t data;
	QNode* next;
	QNode()
	{
		next = NULL;
	}
};

template <class t>
class Queue
{
public:
	Queue();
	~Queue();

	void push(t item);
	t pop();
	BOOL empty();
	t peek();
private:
	QNode<t>* first;
};

template <class t>
Queue<t>::Queue()
{
	first = NULL;
}

template <class t>
Queue<t>::~Queue()
{
}

template <class t>
void Queue<t>::push(t item)
{
	QNode<t>* c = first;
	QNode<t>* d = first;
	while(c)
	{
		d = c;
		c = c->next;
	}
	c = new QNode<t>;
	c->data = item;
	if(d) d->next = c;
	else first = c;
}

template <class t>
t Queue<t>::pop()
{
	t tmp = first->data;
	QNode<t>* c;
	c = first;
	first = first->next;
	delete c;
	return tmp;
}

template <class t>
BOOL Queue<t>::empty()
{
	return (first == NULL);
}

template <class t>
t Queue<t>::peek()
{
	return first->data;
}
  
It isnt all that complicated, the problem occurs in the pop() function, the line "delete c;". The error, specifically, is
HEAP[Divinity.exe]: Invalid Address specified to RtlValidateHeap( 9b0000, 8b1220 )
 
copied from the debug output. I am assuming that new is giving me memory that starts before the heap does. Anyway, if anyone has ever had this problem before, this is a bit urgent (hint =), and if anyone knows how to fix it, I would be very grateful! Z.

Share this post


Link to post
Share on other sites
humm... I don''t know what you did, it looks just fine. It compiled under Metrowerks Codewarrior without any problems also.
The only error I see in your code is all the return first->data, if first is NULL, then you might get a boo boo.
what compiler are you using?

Share this post


Link to post
Share on other sites
What data you used to test the class? It seems ok to me. Most probably the problem lies within the type ''t'' itself.

Make sure you got a nice Copy Contructor and an Assignment operator overloaded in your ''t''.

Share this post


Link to post
Share on other sites
Returning a T from pop is inherently exception-unsafe, even if you return a copy of data. This is why STL doesn''t do it.

You''re passing data/returning data by value instead of by reference in push and peek. If ''t'' isn''t a built-in type, this can be very expensive.

Your QNode does a 2-step construction of its data each time: first the default ctor, then the assignment operator (manually). This can be expensive. You should have QNode constructed from a ''t'', using the copy constructor to initialize data.

Your push function is just funky. Hard to understand what''s going on, but this is where meaningful variable names and/or comments can help--''c'' and ''d'' aren''t very helpful. Looks like you''re traversing the list on each insert to put the item at the end. This is very inefficient. You should be using a first & last pointer to get constant-time insertions.

It''s strange that you get the error on the line that says ''delete c'', since c is a copy of first, and first is dereferenced before the delete. Therefore first isn''t null when you get this error, but somehow it''s not a legal pointer. Are you sure you aren''t deleting QNodes somewhere else?

Other than that, can''t see why you''re getting the error.

Here''s how to fix your code so that you''ll get no errors, be exception safe (mostly--your pop kinda screws it up) and be extremely efficient:
template
  
class Queue
{
private:
std::list<t> m_list;
public:
void push (const t &item)
{ m_list.push_back (item); }
t pop()
{ t item (m_list.front ()); m_list.pop_front (); return item; }
BOOL empty() const { return m_list.empty (); }
const t &peek() const { return m_list.front (); }
};

Share this post


Link to post
Share on other sites
Thanks for all of the comments. It was really just a quick and dirty class that I hacked up because the STL queue was giving me the exact same problem. I think it''s odd, because I am allocating ~210kb at other places in my app, but only this one is screwing up. Anyway, I will keep searching for the answer to this one. Thanks for the rewrite of my functions though =). Ill try them out to see if it works any better.

Z.

Share this post


Link to post
Share on other sites
I found the solution to this hellish problem, finally. I got bored while trying to make it run, and actually read the description of the function that was crashing me. The problem was that the memory was allocated in a DLL, and I was trying to free it from another DLL. So, the solution was to add an Alloc and Free functions to the DLL where the memory should come from. Solved it quite well. Now I just need to overload new and delete to point to those functions in my other DLLs. Thanks for all your help, guys. Now I can fix that queue up and make it more efficient =).

Z.

Share this post


Link to post
Share on other sites