🔒 Locked

Queue

Started by Zaei Oct 20, 2001 at 7:12 PM 4 replies 750+ views

Original Post

Oct 20, 2001 at 7:12 PM

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.

Leecho0

Oct 21, 2001 at 7:39 PM

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?

DerekSaw

Oct 21, 2001 at 8:01 PM

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''.

Stoffel

Oct 21, 2001 at 11:19 PM

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 (); }
};

Zaei

Author

Zaei

Oct 22, 2001 at 6:00 AM

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.

Zaei

Author

Zaei

Oct 23, 2001 at 2:19 PM

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.

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.