• Advertisement
Sign in to follow this  

doubly linked list erase

This topic is 4432 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

Okay, I'm having a slight problem here: I have written a doubly linked list (links go both ways), and the erase function keeps giving me grief. I really don't know why, and since this list is at the base of my engine, that causes me slight problems. I have everything inheriting from a common base class, and I'm using reference counting to do basic memory management. My problem is that, well, my erase function doesn't work, so, when I shut down my engine, and I go about deleting the memory being taken up by all the objects in the engine, I end up just deleting the memory, and not the list elements, which gets confusing.
/**
 * Erase the element at this iterator.
 * \param i A reference to an iterator object
 */
void erase(iterator& i)
{
	iterator j, p;

	if( i.current == NULL )
		return;

	if( i.current == head && head != NULL ){
		i++;
		delete head;
		head = i.current;
		
		if( head != NULL )		// just in case 'head' is the only element in the list
			head->prev = NULL;	// front of the list, nothing behind

		size--;
		return;
	}

	p.current = i.current->next;		// assign 'p' to the element after 'i'

	j.current = i.current->prev;		// assign 'j' to the element before 'i'
	j.current->next = i.current->next;	// the element after 'j' is now the one after 'i'

	if( p.current != NULL )				// just in case 'i' is the last in the list
		p.current->prev = j.current;
	
	size--;
	delete i.current;
}// erase


This code uses iterators with the operator overloads you'd expect, and list nodes with 'current' which is the object pointer, and you can guess what 'next' and 'prev' are. 'head' is simply a node pointer which is the head of the list. This is the clean up code which is pretty self explanatory:
/**
 * Deletes all the items in the deadList from memory.
 */
static void collectGarbage()
{
	util::list<IMBase*>::iterator i = deadList.begin();
	for( ; i != deadList.end(); i++ ){
		delete (*i);
	}
}

/**
 * Delete all the items in the deadList and activeList.
 */
static void collectAllGarbage()
{
	collectGarbage();	// delete all in deadList

	// delete all items in the activeList
	util::list<IMBase*>::iterator i = activeList.begin();
	for( ; i != activeList.end(); i++ ){
		delete (*i);
	}
}


See, the problem here is that I'm deleting the memory pointed to by the iterators, instead of calling the erase function which would delete the memory and remove the element from the list. And, I know, I know, I should just use std::list. But, I'm using this one because I like to be able to see every stage of the code, and I simply can't understand anything when the view changes to the std::list code. Plus I'm sick of getting the "debug something truncated 255 characters" warning. And, I know I can disable it, but again, I like to see everything that's going on. If you can help either by gently guiding, or by hitting me over the head, it would be much appreciated.

Share this post


Link to post
Share on other sites
Advertisement
Are you using smart pointers? If not then things might go wrong if you first delete the head element and then the current item whenever they are equal.

Share this post


Link to post
Share on other sites

void erase(iterator& i)
{
if( i.current == NULL || head == NULL)
return;

if (i.current->prev != NULL)
i.current->prev->next = i.current->next;

if( i.current->next != NULL)
i.current->next->prev = i.current->prev;

if (i.current == head)
head = i.current->next;

size--;
delete i.current;
}



Does that work? Also, isn't it weird that the contained object has links to the next and previous elements of the list? Shouldn't that be the job of the iterator?

-Alex



Share this post


Link to post
Share on other sites
In principle, I see the following design problems with the original erase method:

(1) The state of the overhanded and also returned iterator isn't clear. In the case of deleting the head, the iterator will point to the new head, but in case of deleting another node it will not. This behaviour is inconsistent.

(2) Moreover, the iterator will have a _dangling_ pointer if deleting a non-head node, i.e. the node i.current points to is deleted but i.current isn't annuled. NEVER do something like this!

Notice e.g. that your code uses a condition i.current == NULL, what is a candidate for illegal memory access due to dangling pointer.

To overcome (1) and (2), either set the iterator always to the node behind the erased one (maybe null, of course), or make i.current always null. I would prefer the former solution. BTW: The NULL macro (if the NULL your code contains is that) is obsolete in C++. Please replace it by a static_cast.

The irregular structure of your code isn't problematic but makes it less readable. The solution cypherx has posted is more regular. Please take into account to prefer it. However, also cypherx solution violates point (2) I've mentioned above!

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
I'm not going to be much helpful, sorry...

Anyways, I think it's because of the i.current links...

This is how I did my doubly linked list (uses id's, but isn't that hard...):

template<typename Type, typename Id> void List<Type, Id>::Remove(const Id &NodeId) {
SNode *pRemove = m_pHead;

if (pRemove == NULL) {
throw Error("Tried to remove id from no nodes.");
return;
}

while (pRemove->NodeId != NodeId && pRemove->pNext)
pRemove = pRemove->pNext;

if (pRemove->NodeId != NodeId) {
throw Error("Tried to remove non-existent node.");
return;
}

if (pRemove->pNext && pRemove->pPrev) {
pRemove->pPrev->pNext = pRemove->pNext;
pRemove->pNext = pRemove->pPrev;

delete pRemove;
} else if (pRemove->pNext) {
pRemove->pNext->pPrev = NULL;

m_pHead = pRemove->pNext;

delete pRemove;
} else if (pRemove->pPrev) {
pRemove->pPrev->pNext = NULL;

m_pTail = pRemove->pPrev;

delete pRemove;
} else {
delete pRemove;

m_pHead = NULL;
m_pTail = NULL;
}

m_Size--;
}


No comments, although the variable names pretty much explain themselves.

What I did is check where the node is - beginning, ending, or middle. Then, according to its position in the list I 'linked' each 'link' to the appropriate 'link', looking like this:

//pseudo code
previous->next = todelete->next
next->previous = todelete->previous
delete todelete

// in case of it being the head
next->previos = null
head = next
delete todelete

// in case of it being the tail
previous = null
delete todelete


Good luck! A doubly linked list is VERY fun!

C++

Share this post


Link to post
Share on other sites
I would seriously reconsider that decision. At least work you way through "The C++ Standard Library" first so that you make an informed decision. Even if you decide to do your own implementation it will be better for it. The STL does a lot more than simply provide containers. It also provides algorithms that operate on those containers as well as function objects for use by those algorithms. Additionally you have a lot of meta-data provided that makes it possible to build your own templates using them. Chances are you'll lose a lot of flexibility and performance using your own and if not then you take far longer rolling your own than it would take to learn what's already there.

Share this post


Link to post
Share on other sites
Good point haegarr, I didn't think about the hanging pointer. Setting it to NULL before returning ought to take care of that...but still, the whole affair is messy. For anything other than learning about linked lists use STL. It always seems easier to roll your own than learn someone else's code, but all those sneaky little bugs won't leave you time to work on your game.

-Alex

Share this post


Link to post
Share on other sites
haegarr,

You mean "#define NULL 0" is obsolete? How do you replace that with static_cast?

-Alex

Share this post


Link to post
Share on other sites
Quote:
static void collectGarbage()
{
util::list<IMBase*>::iterator i = deadList.begin();
for( ; i != deadList.end(); i++ ){
delete (*i);
}
}
See, the problem here is that I'm deleting the memory pointed to by the iterators, instead of calling the erase function which would delete the memory and remove the element from the list.
So you already know what the problem is then. So you just need to know how to do what you mentioned, to fix it?
static void collectGarbage()
{
util::list<IMBase*>::iterator i = deadList.begin();
for( ; i != deadList.end(); ){
util::list<IMBase*>::iterator j = i;
i++;
erase(j);
}
}
btw you shold be using preincrement (++i) when it comes to iterators because it eliminates unnecessary temporaries. However I'm not sure if you've even implemented the preincrement operator (so I didn't use it), and would guess that you could have even implemented the post-increment incorrectly, in the way that preincrement should be, as I've seen done before. Or I could be totally wrong. Do you understand the difference between pre- and post- increment, and how each should be implemented?

Share this post


Link to post
Share on other sites
Quote:
Original post by LilBudyWizer
I would seriously reconsider that decision. At least work you way through "The C++ Standard Library" first so that you make an informed decision. Even if you decide to do your own implementation it will be better for it. The STL does a lot more than simply provide containers. It also provides algorithms that operate on those containers as well as function objects for use by those algorithms. Additionally you have a lot of meta-data provided that makes it possible to build your own templates using them. Chances are you'll lose a lot of flexibility and performance using your own and if not then you take far longer rolling your own than it would take to learn what's already there.

I'm not saying that I'll never be using it for a serious project. I'm just saying that while I'm learning the basics of writing an engine I don't want to have to slog through lines and lines code that looks like they did their best to make it really hard to read.


Quote:
Original post by iMalc
btw you shold be using preincrement (++i) when it comes to iterators because it eliminates unnecessary temporaries. However I'm not sure if you've even implemented the preincrement operator (so I didn't use it), and would guess that you could have even implemented the post-increment incorrectly, in the way that preincrement should be, as I've seen done before. Or I could be totally wrong. Do you understand the difference between pre- and post- increment, and how each should be implemented?

Pre-increment acts on the memory that the object/variable is currently taking up, and post-increment makes a temp, increments the temp and then assigns the original, right? And the difference in overloaded functions is that the post takes an unsigned int as a param, and the pre does not.

I know this now, but at the time that I wrote this code I didn't. And, when I found out, I didn't really think of this code to change it.



haegarr:

(1) Absolutely. I looked at that 5 minutes ago and wondered what the hell I had been thinking. In the erase method, I should have assigned 'p' to 'i', so that 'i' would be pointing to the next element in the list. Currently the problem is that I keep getting pointers with the value 0xdddddddd creeping in, and I'm not sure why. I'm going to work on it some more this morning.

(2) Absolutely. I looked at that 5 minutes ago and wondered what the hell I had been thinking. Fixed it.

Also with the NULL macro, do you use 0? Or do you use the static cast? I'm using NULL because it is more descriptive than simply 0.


Quote:
Original post by cypherx
haegarr,

You mean "#define NULL 0" is obsolete? How do you replace that with static_cast?

-Alex

Probably "static_cast<void*> 0". I think.

Share this post


Link to post
Share on other sites
Quote:
Original post by Endar
I'm not saying that I'll never be using it for a serious project. I'm just saying that while I'm learning the basics of writing an engine I don't want to have to slog through lines and lines code that looks like they did their best to make it really hard to read.

While I admire your attempts to learn, if you find yourself slogging through the STL source then you're doing something wrong. That code already works, so what steps it takes isn't so important. Do you try and step through DirectX calls?

Keep working on this linked list for learning purposes, because that's a valuable experience when studying data structures. But then scrap it and use the standard library while learning about engines. Why force yourself to debug two separate sources of bugs when all you want to do is focus on engine writing?
Quote:

Probably "static_cast<void*> 0". I think.

0 can be automatically converted to any pointer type, so that cast is unneccessary. I have no idea what that guy meant about using a static_cast instead of NULL.

CM

Share this post


Link to post
Share on other sites
The point is the foundation upon which you build. Rolling your own means starting with a foundation of just the language. So everything you do basically starts at a lower level and you have to build more to reach a given height. Much of the readability issues with the STL are complexity. Both complexity to provide flexibility and to improve performance. This is a core library used extensively. Readability is secondary to performance and flexibility.

I'm not saying don't do it, but rather simply know what you are choosing not to do. Working throug a book like "The C++ Standard Library" will make you aware of many possibilities you most likely have not considered. Even if you still decide to roll your own what you roll will be better for understanding how and why the STL does what it does.

Share this post


Link to post
Share on other sites
I believe I have hit success.


/**
* Erase the element at this iterator.
* \param i A reference to an iterator object
* \return The iterator next in the list after the deleted iterator
*/

iterator erase(iterator& i)
{
iterator j, p;

// if we're attempting to delete nothing
if( i.current == NULL )
return iterator(NULL);

// if the iterator points to the head node.
// (if the head node was NULL, then it would have been picked up by the first 'if')
if( i.current == head && head != NULL ){
i++; // next list element
delete head;
head = i.current; // basically assigning head to head->next

if( head != NULL ) // just in case 'head' is the only element in the list
head->prev = NULL; // front of the list, nothing behind

size--;
return iterator(head);
}

p.current = i.current->next; // assign 'p' to the element after 'i'

j.current = i.current->prev; // assign 'j' to the element before 'i'
j.current->next = i.current->next; // the element after 'j' is now the one after 'i'

if( p.current != NULL ) // just in case 'i' is the last in the list
p.current->prev = j.current;


size--;
delete i.current;
i.current = NULL;

return p; // return the iterator after i
}// erase





Conner McCloud: I suppose I also wanted to find out if I could do it. Write almost every scrap of code (excepting API) for a large project. This really is the biggest project I've ever worked on.

For future engines that I write, I'll be using STL a lot more than I am now, but, for the moment with my first engine, where a lot of things simply aren't an issue (high-grade performance, etc) I feel comfortable using my code, even when my code is inferior to standard C++ lib code.

Share this post


Link to post
Share on other sites
Quote:
Original post by cypherx
You mean "#define NULL 0" is obsolete? How do you replace that with static_cast?

One problem with NULL is its variety of definitions. I think often you could find
#define NULL ((void*)0)
what is evil due to the void*. A problem occurs in general if the NULL is defined already with any type of pointer. From this point of view the definition written above (typeless literal 0) is ok in principle. But it is suggested to avoid the use of NULL due to its inconsistent use.

Second, we could discuss once more the pros & cons of pre-processor macros in general ;-) But as a hint: Try to encapsulate a macro in a namespace or any other language given scope; there is no chance.

The C++ replacement is
static_cast<type_of_class*>(0)
as e.g. Endar has stated above. It is also correct that the literal 0 "as is" would work also, since it would be casted automatically to the correct pointer type.

[Edited by - haegarr on January 1, 2006 4:06:02 AM]

Share this post


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

  • Advertisement