Jump to content
  • Advertisement
Sign in to follow this  
Endar

doubly linked list erase

This topic is 4609 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
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
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!