# Stack Overflow(Help)

## Recommended Posts

Hermes    144
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]



##### Share on other sites
Promit    13246
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 on other sites
Pxtl    354
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 on other sites
Hermes    144
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?

##### Share on other sites
swiftcoder    18432
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;}

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

SwiftCoder

##### Share on other sites
Hermes    144
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 on other sites
Hermes    144
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.

Thanks a lot!

##### Share on other sites
Promit    13246
Quote:
 Original post by swiftcoderJust 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 on other sites
Hermes    144
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 on other sites
Hermes    144
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]

##### Share on other sites
snk_kid    1312
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]