Archived

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

Linked list Pains....

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

Hey, I am working on a asteroids clone and I am having a big problem with linked lists. Right now, the way that my program stands, each object (ship, asteroids, bullets, particles, etc.) is in a linked list. I go through this list each frame and run each object's main function. That all works great, but whenever I need to delete a node from the list I have a big problem. Here general code I use and where it crashes.
      

void RemoveExplosion(CExplosionNode *Node) {

if(CExplosionNode::s_pFirst && CExplosionNode::s_pLast == Node) {

		CExplosionNode::s_pFirst = NULL;
		CExplosionNode::s_pLast = NULL;
		delete Node; <- Crashes here /////////////

	}
	else {

		if(Node->m_pPrev == NULL) 
			CExplosionNode::s_pFirst = Node->m_pNext;			
		else 
			Node->m_pPrev->m_pNext = Node->m_pNext;
				
		if(Node->m_pNext == NULL) 
			CExplosionNode::s_pLast = Node->m_pPrev;
		else
			Node->m_pNext->m_pPrev = Node->m_pPrev;

		delete Node; <- Or crashes here /////////////


	}

}
      
I have remote debugging, and I checked to see whether the pointers were good or not and they are. They are legit pointers, but for some reason, whenever I delete the node, the program crashes. It is really pissing my off, I have been trying to fix this for eons. Does anyone know why this is happening. Or, maybe even better. Is my approach to this object thing entirely wrong?? Are linked lists bad? Well if you could answer ether of these questions I would appreciate it. Thanks.. later Edited by - JSCFaith on October 22, 2001 12:03:10 AM Edited by - JSCFaith on October 23, 2001 11:01:39 AM

Share this post


Link to post
Share on other sites
Linked lists = good. Rolling your own linked lists = fair. Using STL''s std::list = very good.

What you might want to do is put traces in the ctor and the dtor of the value of "this" is, make sure you''re not deleting the same thing twice. Also trace the address of what you''re trying to delete. If you can''t use a TRACE macro or something, log it to a file.

Share this post


Link to post
Share on other sites
Hey, Thanks for your help guys. I tried what you said and for some reason it still does not work. I logged the destructor information to a file. This is how the class hierarchy works.

COBject->CMultiFramed->CExplosion;

So when I log it too a file this is what happens. First, ~CExplosion() runs and is successful, then ~CMultiFramed() runs and it is successful aswell. Finnaly, ~CObject() runs and it is successful as well. So in escense, the object is total deleted. All the destructors are run, but for some reason it still crashes when I call, delete Node;

For some reason though, it only crashes if I am running through a loop like so.

    
CExplosion *TempNode; // Temporary node used to carry contents of Node->m_pNext in the loop.


for(CExplosionNode *Node = CExplosionNode::s_pFirst; Node != NULL; Node = Node->m_pNext) {

if(Node->m_Data->GetState() == DEAD) {

TempNode = Node->m_pNext;
RemoveExplosion(Node); // This is the functions above

Node = TempNode;

}
else {

Node->m_Data->Main(); // Run the main function of the explosion


}


Now this loop runs fine except when RemoveExplosion(). It crashes anytime I try to delete the Node. Like I said though, all the destructors are run and are successful, so I don't see why it is crashing.

If I run remote debugging and debug the program, it crashes at that exact line: delete Node;

Well if someone can help I would appreciate it. [/source]

Edited by - JSCFaith on October 23, 2001 11:03:54 PM

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
Hi.

In the code above, inside the loop, you''ve declared the pointer
Node to point to an object of class CExplosionNode, but the
function RemoveExplosion treats it like a pointer to a CExplosion
object. Maybe you''ve got an error in the declaration of the
function or in the declaration of the pointer types.

I think you''re mixing pointers to CExplosion and
CExplosionNodes.




"If you''''re gonna die, die with your boots on"

Share this post


Link to post
Share on other sites
Well, maybe I should use that STL thing you were talking about Stoffell. Could anyone tell me what exactly that is? Also, where I can find more information about using it. Thanks.



Edited by - JSCFaith on October 23, 2001 11:17:50 PM

Share this post


Link to post
Share on other sites
I don''t know if this would help, but it works for me.

void updateList(void)
{
STRUCT *current;
current=STRUCT1;

while(current!=NULL)
{
if(current->state==INACTIVE)
{
STRUCT *temp;
temp=current;
if(temp==STRUCT1)
{
STRUCT1=temp->next;
LocalFree(temp);
temp=NULL;
}
else
{
STRUCT *prev;
prev=STRUCT1;
while(prev->next!=temp)
prev=prev->next;
prev->next=temp->next;
if(temp!=NULL)
{
LocalFree(temp);
temp=NULL;
}
}
}

current=current->next;
}
}

Using a simple single linked list. I couldn''t get it to work though unless all the artwork was from the same bitmap, and it goes through the whole list every time. Like I said, it works for me. Although when I get time I''d rather rework it as it strikes me as kinda inefficient.

"A man can''t just sit around." ''Lawn Chair'' Larry Walters (1982)

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
You should be able to use the STL linked list like so:


#include

// The list template is in the std namespace.
using namespace std;

// Here''s how you would create a list of pointers to explosions
// for example.
list< CExplosion* > MyExplosionList;

// Say you want to remove an explosion pointed to by
// pExplosionToRemove, just do this.
MyExplosionList.remove( pExplosionToRemove );



If you want to loop through every thing in your list (to say update them on a frame) try looking into an STL template function called for_each. You will find using the STL instead of writing your own code a lot more enjoyable and productive. I suggest you try reading up on STL because you may find other templates that are useful to you.

Share this post


Link to post
Share on other sites
Any modern C++ compiler supports the Standard Template Library, a collection of templated data structures, algorithms, objects and common operations such as linked lists, stacks, queues, deques (double-ended queues), vectors (arrays), trees, etc. The new C++ header files have no ".h" extensions, and also employ namespaces. Everything in the STL and the Standard C++ Library is encapsulated in the "std" (standard) namespace, invoked as follows:
using namespace std; 

All code following this line can address Standard Library constructs by identifier only. You can also import only certain identifiers into your namespace:
using std::cout; 

(Note that cout, cin, endl, etc are also part of the std namespace now).

Here are some headers you should be very familiar with:

#include <deque> // std::deque
#include <iostream> // std::cout, std::cin, std::endl, etc
#include <stack> // std::stack
#include <queue> // std::queue
#include <vector> // std::vector

The STL is implemented almost entirely in header files, so you can view the source as well.

This is only a brief primer. Your compiler/environment help files should have decent documentation on all of this. If not, there''s always MSDN.

Share this post


Link to post
Share on other sites
You could use STL, but I think the problem is because you are trying to delete a static object. Correct me if I''m wrong (since I''ve never read anything about deleting a static object and have never needed to) but deleting a static object wont work.

If you make you class so those two objects aren''t static then:
A) Your code should then work
B) You''ll be able to have more than one CExplosionNode

Invader X
Invader''s Realm

Share this post


Link to post
Share on other sites
I assume the pointer is static, and that to which it points is dynamically allocated:
  
class C
{
static int *m_pInt;
C () : m_pInt (new int) { }
~C () { delete m_pInt; }
};

This is fine.

To JSCFaith: STL has a steep initial learning curve, but you get a bucketload of knowledge and tools once you understand how the parts of the library work together. algorithm.h is worth learning STL alone, not to mention map--many people can hack together their own lists, but not many can hack together their own maps correctly or efficiently.

Here''s how your function would look if you were using STL''s list:
  
typedef list<CExplosion *> ExplosionList;
static ExplosionList s_expList;
void RemoveExplosion (ExplosionList::iterator &it)
{
s_expList.erase (it); // no need for function really

}
void AppendExplosion (CExplosion *pExp)
{
s_expList.push_back (pExp); // again, really no need for fncn

}
// usage example:

AppendExplosion (new CExplosion (/* whatever your ctor takes));
// example of main loop

ExplosionList::iterator it = s_expList.begin ();
const ExplosionList::iterator end = s_expList.end ();
while (it != end)
{
CExplosion &exp = **it; // *it dereferences data, which is

// CExplosion*, so you need **it

if (exp.DoneExploding ())
RemoveExplosion (it++); // or just it = s_expList.erase (it)

else
++it;
}

I tried to say so in the comments, but if you use STL you really don''t even need those functions; they''re already part of list.

While push STL is all well and good, I still think we haven''t gotten to the root of your problem. The fact that the error is always on a delete suggests you''re deleting something you shouldn''t. Does the delete always crash the program? Maybe your destructor is throwing an exception (which isn''t allowed)? Otherwise, just double check that you have new''d everything you''re deleting, and you''re deleting nodes only once, not multiple times.

Share this post


Link to post
Share on other sites
Only mention I can find on a product in Gamasutra is for Star Wars Starfighter. However, they had to ditch STL because of multiple tiny string allocations (sounds like they didn''t know how to write their own allocator object--not like I do). However, STL is mentioned in several of the technical articles there.

Share this post


Link to post
Share on other sites
But, Stoffel... If they should rewrite allocator than wouldn''t it be more reliable to rewrite the whole string class?
The reason for me asking that is simple. Though using STL I am not sure if I should keep using it when, say I''m going to write "that kickass 3d engine myself"
I don''t believe developers in all that companies that stupid and lazy and they don''t know about STL classes.
At the same time I haven''t seen yet ANY game code with std::list, for example.
The question is what the real reason of skipping such a beautiful and powerful things?

Share this post


Link to post
Share on other sites
quote:
Original post by Halloween
But, Stoffel... If they should rewrite allocator than wouldn't it be more reliable to rewrite the whole string class?
The reason for me asking that is simple. Though using STL I am not sure if I should keep using it when, say I'm going to write "that kickass 3d engine myself"
I don't believe developers in all that companies that stupid and lazy and they don't know about STL classes.
At the same time I haven't seen yet ANY game code with std::list, for example.
The question is what the real reason of skipping such a beautiful and powerful things?


There is simply no reasons.

I believe Unreal uses the STL because Tim Sweeny said a long time ago that they had problems with list and dll with VC++ because there was a bug in VC++ stl which is now fixed.


Why not rewrite strings with the allocator? Because it makes more code to test! I have better things to do than write supporting classes and I am sure your manager or investors think so too!

quote:

I don't believe developers in all that companies that stupid and lazy and they don't know about STL classes.



I don't believe so too, but my experience is that people don't really know about the STL.

Arg #1 : People on Gamedev. You see lots of people writing code that the stl can already do.

Arg #2 : The company I worked at has 20 programmers. Only 3-4 can name 90% of the services it provides.

The stl is not a simple piece of code. You cannot just look at the headers and figure out how to use it. You have to sit down and read books and/or articles. Unfortunetly, not a lot of people are willing to do that.



Edited by - Gorg on October 24, 2001 2:48:59 PM

Share this post


Link to post
Share on other sites
Well, what it sounds like is STL is very powerful and useful, so I will certainly learn it. Thanks for the tips/info on it.

Now, here is a question. When I log everything to a file something like this happens:

// File Output //////
Created Explosion
About to Remove Explosion
ExplosionNode Destructor Run
Explosion Destructor Run
MultiFramed Destructor Run
Object Destructor Run

// End File Output //

Now if all the destructors are being run and completed. What could be making my program crash. What else is delete calling that could make it crash? In the VC++ 6 debugger... Everything runs fine, then it gets to the delete call and all this Assembly code pops up. I don't understand it, but it is there. It runs about 100 assembly calls, then crashes. Finnally VC++ askes for the location or something called "DGBHeap.c" or something like that.

BTW, I added this code...

         
if(Node) delete Node;


...but, it still crashes. And like I said above, all the destructors are run. Any other ideas from what I said above as to what could be going wrong. I really do want to find out whats going on, even if I do use STL. That way I can learn from the mistake in my code that I obviously must of made.

Back to the STL thing. Does anyone recommend any books or free articles/tutorials on the subject. It sounds like a worth while thing to learn.

Also, here is my CExplosion and CExplosionNode classes, they are quite short.

    

class CExplosion : public CMultiFramed {

friend class CExplosionNode;

public:

CExplosion(char *, int, int, int);
~CExplosion();

int Main();
void Animate();

protected:


};

class CExplosionNode {

friend class CObjectManager;

public:

CExplosionNode(CExplosion *);
~CExplosionNode();

CExplosionNode *m_pNext;
CExplosionNode *m_pPrev;
CExplosion *m_Data;

static CExplosionNode *s_pFirst;
static CExplosionNode *s_pLast;


};



Also, I want to thank you guys for helping me. I have already learned a great deal from this short form.

Well I will continue trying everything I can think off. I hope someone can see what I am doing wrong. It would sure be a big help. Of course, the problem could be in something other than the code I have shown so far, but who knows.

Later guys.

... damn, my fingers hurt, lol.



Edited by - JSCFaith on October 24, 2001 3:59:13 PM

Share this post


Link to post
Share on other sites
STL books :

The C++ Standard Library : A Tutorial and Reference

Effective STL: 50 Specific Ways to Improve Your Use of the Standard Template Library

Share this post


Link to post
Share on other sites
''k, you need more helpful debugging messages. In your ctor:
{
log ("Created Explosion: 0x%08X\n", this);
}

In your code that deletes stuff:
log ("About to delete: 0x%08X\n", pExplosion);
delete pExplosion;

You need to make sure that the physical objects you''re allocating and deleting are what you think they are.

PS: Are your destructors virtual? I assume so since your log output seemed to go up the inheritence chain correctly.

Share this post


Link to post
Share on other sites
No, they are not virtual. I will do that with the messages. One thing I noticed is this. When I run this same code in DOS it doesn''t crash. Is that becuase dos is less restrictive, or that the code I think is bad isn''t? The only thing different between the DOS and Windows version is that the dos version does not have a LPDIRECTDRAWSURFACE, but that shouldn''t affect it at all.

Share this post


Link to post
Share on other sites