Sign in to follow this  

Stack Overflow(Help)

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

Hi ya! I have a tree and every node in this tree has two adjanced nodes; a 'next' node and a 'successors' node,the tree is realy huge but it eats only 2MB of memory.The problem is that when trying to free this node like:
virtual ~CNode()
{
delete successors;
delete next;

}
 i exit unexpectedly from my infinite loop.
I traced my destructor and i get a Stack Overflow [looksaround]

The main game loop is like:
1.Build Tree
2.FindBestMove
3.Make move
4.Free tree

I used my task manager to figure out if it's really a memory leak and it isn't .If in the begining i have 191MB of used memory
i get 193 after building the tree ,then after the deletion i get those 191 of used memory back,but i exit the loop ???

I realy need to fix this bug,this should be my first game although is not big deal it means a lot to me,breaking the ice[lol]


Thanks for your support!





			
		

Share this post


Link to post
Share on other sites
A stack overflow means you recursed too deep, and so your tree itself is too deep.

It would be possible to request a bigger stack from the compiler...but generally this is frowned upon.


Basically, your destructor is causing too much call depth. Is there any way you can make the tree smaller? Or alternatively, try to allocate less on the stack.

Share this post


Link to post
Share on other sites
Well, it could just be having too much shit on the stack. Try allocating onto the heap - use an auto_ptr instead of a local (actually, you should be using auto_ptrs in general - its much cleaner than delete which can be missed if an exception is thrown).

Share this post


Link to post
Share on other sites
The tree is indeed big ,3 levels of recursion and more then 22 thousand nodes,but it's a chess game it should be big ,and this is a small one[lol].I used recursion to find my best(at the same deapth) move why couldn't i use it to destroy it as well?

ThankX for your answers!

Share this post


Link to post
Share on other sites
Just a thought, you do realize that calling delete on one item in your tree deletes all the others, and then crashes when it reaches the beginning or end of the tree, trying to delete a successor that doesn't exist.
so, as soon as you delete one node, the whole tree is deleted, and, of course, your loop exits.

I am not quite sure of the structure of your tree, but perhaps something like this would be more appropriate:

virtual ~CNode()
{
if (next) next->successors = successors;
if (successors) successors->next = next;
}

aka double-linked list.

but even if it is not a linked list, I don't think you should be deleting next in your destructor.


SwiftCoder

Share this post


Link to post
Share on other sites
Is it possible for all my awake destructor instances on the stack crash into one another?(some kind of overwrite;thread taking the place of another thread).I even tried to declare a big array in my destructor to avoid the crash ,just in case but it doesn't work (as expected).

Share this post


Link to post
Share on other sites
What does it mean if a variable needs a stack frame?This is not related with the folowing(or i think it doesn't)
I found out that it exits with code 128.This means:
There are no child processes to wait for???????????[looksaround]
Does this ring any bell,i have no clue.

Please help me out!



Thanks a lot!

Share this post


Link to post
Share on other sites
Quote:
Original post by swiftcoder
Just a thought, you do realize that calling delete on one item in your tree deletes all the others, and then crashes when it reaches the beginning or end of the tree, trying to delete a successor that doesn't exist.


It won't crash if the pointers are correctly initialized to null. You know deleting null pointers is valid, right?

Share this post


Link to post
Share on other sites
Well on the stack there's only the hidden passed argument,the 'this' pointer right ,so the destructor doesn't put too many things on the stack, it's because the tree is to big

Share this post


Link to post
Share on other sites
Well i fixed the stack overflow exception but now i get an access violation error


void CGameTree::DestroyTree(CNode* node)
{
if(!node)return;

CNode** pp=&node;
CNode*aux=NULL;


_try{

while(*pp)
{


DestroyTree((*pp)->successors);

aux=*pp;

if((*pp)->next)
pp=&(*pp)->next;

delete aux;

}
}
_except(EXCEPTION_EXECUTE_HANDLER)
{
printf("Exception handler:%lx\n",exception_code());

}



}







Can you spot any error???[looksaround]

I appreciate your help!

Share this post


Link to post
Share on other sites
I just wont to also point out that node types don't typically delete there sibling/s, parent/s or children/s them selfs, there not responsible for them besides they never usually allocated them in the first place.

It's the responsibility of the main container/data structure that does the allocation/deallocation & construction/destruction of nodes/elements.

In general when writing a user-defined types rule of thumb is:

if your user-defined type doesn't invoke new then it shouldn't invoke delete either. One exception to this if you where to write your own smart pointer type.

if your user-defined type invokes new then it should invoke delete, the exception to this is for of-course smart pointers or garabage collected environments.

Also if your not going to write iterator types to go with your tree and letting clients use tree nodes directly to iterate the structure don't give them responsibility for creating new nodes with them, only allow them to use nodes to iterate the structure and when clients wont to say add a new child only ask them to give a node that refers to the parent and the element to be used to insert the new kid e.g.:


#include <new>

struct foo { /*...*/ };

struct foo_node {

foo_node* parent;
foo_node* pred_sib, succ_sib;
foo_node* first_kid, last_kid; //<-- doublely linked-list

foo element;

foo_node(const foo& f)
: element(f), parent(0), pred_sib(0), succ_sib(0),
first_kid(0), last_kid(0) {}

};

class foo_tree {

foo_node header;

public:

/* ... emitting code ... */

// get root, one way for clients to iterate the tree
foo_node* root() { /* ... emitting code ... */ }

// get root, one way for clients to iterate the tree
const foo_node* const root() const { /* ... emitting code ... */ }


foo_node* add_child(const foo_node* parent_pos, const foo& f) {
if(!parent_pos)
return 0;

foo_node* __z = new(std::nothrow) foo_node(f);

if(!__z)
return 0;

if(parent_pos->_first_child) {

//append back
__z->parent = parent_pos;
__z->pred_sib = parent_pos->last_kid;
parent_pos->last_kid->succ_sib = __z;
parent_pos->last_kid = __z;

} else {

// append front
__z->parent = pos;
pos->first_kid = __z;
pos->last_kid = __z;

}
return __z;
}

/* ... emitting code ... */

};









The reason being is it makes it clear who is responsible for clean-up instead of guessing if clients/yourself really did allocate the node on the heap or not & if they invoke delete outside the tree and then your tree invoking delete. It just helps (just little) to avoid dangling pointer syndrome.

Granted the above example can be written a million times better and i did write an STL like generic n-ary tree here a while ago.

[Edited by - snk_kid on October 2, 2004 9:26:00 AM]

Share this post


Link to post
Share on other sites

This topic is 4820 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.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this