   Quadtree delete-method
  Hello,I need your help. I´m developing a quadtree class for a small game engine. Currently my project targets normal Windows but in the future I will migrate the code to compile for Windows Mobile. So don´t wonder about using fixed-point math.The creation of a quadtree runs fine but my deletion method works not right.Every quadtree-node has a pointer to its parent and 4 pointers to its children. The method should delete this node and all its children. The quadrant order is 1 -> top left, 2->top right, 3->bottom left, 4->bottom right.Please have a look at my code. I´m staring at it but I can´t find anything wrong.I don´t know if I can do "delete this" at the last line of the code?Thank you for your help!// Delete a QuadtreeNode and its childrenvoid QuadtreeNode::DeleteQuadtree(){for(int i = 0; i < 4; i++){// Recursively delete children of this nodeif(mpChild){mpChild->DeleteQuadtree();}}// Update parents child pointer to NULLif(mpParent){// Compute the quadrant the obects AAR is in// and set parents child pointer to NULLif(mCenter.y > mpParent->mCenter.y){if(mCenter.x < mpParent->mCenter.x)mpParent->mpChild[0] = NULL;elsempParent->mpChild[1] = NULL;}else{if(mCenter.x < mpParent->mCenter.x)mpParent->mpChild[2] = NULL;elsempParent->mpChild[3] = NULL;}}// Delete this nodedelete this;}
You shouldn't ever delete the this pointer.The best way to do this would probably be to have DeleteQuadtree delete the node's four children.  Then to delete a quadtree you'd call root_node->DeleteQuadtree and then delete the root node.Or, you could delete the node's children in the node's destructor, and thus be able to destroy the entire quadtree with:delete root_node;;  Thank you for the fast answer!I allready thought off that deleting the this-pointer can´t be good. ;)I will try your suggestion as soon I´ve some time!Thx   ;  Deleting 'this' is perfectly fine, as long as you don't use any of the object's members after doing so. Some design patterns even rely on this mechanism.To elaborate, consider this code:#include <iostream>struct A {void Addr() { std::cout << std::hex << this << std::endl; }};int main(){A* b = new A();std::cout << std::hex << b << std::endl;b->Addr();  // should print the same addressreturn 0;}You should get the same address in both cases which means 'this' is just an ordinary pointer that happens to point to the current object.Hope this helps.[Edited by - Prototype on June 8, 2006 1:49:22 PM];Quote:Original post by PrototypeDeleting 'this' is perfectly fine, as long as you don't use any of the object's members after doing so. Some design patterns even rely on this mechanism.Legal or not, it makes code harder to understand and I've never seen a situation where it couldn't be removed in favor of something clearer.  (Perhaps I'm wrong though... do you have any examples?)   ;  Refcounted objects come to mind.For example COM often uses this construct.SomeClass::Release() {  refcount--;  if (!refcount) delete this;};I agree, "delete this" is perfectly fine.I am not sure what is the purpose for you to give the node itself a self-deletion possibility. I can imagine that there are some uses for it too.However, if that feature isn't needed, why not just write : void Quadtree::~Quadtree(){for(int i = 0; i < 4; i++){// Recursively delete children of this nodeif(mpChild){delete mpChild;    mpChild = NULL;}}}This way you don't have to worry about NULLifying the parents pointer.What actually happens with your code ? It crashes or something ?   ;  First, thank you.But the problem still exists:I´ve implented the destructor variant from Demus79. The child-pointers were correctly set to NULL in the destructor but after the "delete node;" command has finished the child pointers point to the address 0xfeeefeee ?? This is != NULL and so my other methods try to use the data members of the deleted node and my programm crashes.   ;When running under debug mode the debug runtime fills freed memory areas with 0xfeeefeee (stands for free). So if you "delete this" node, it will happen that all the member variables of "this" will receive 0xfeeefeee value.What you seem to be doing wrong is that you are accessing an object after it has been deleted.Could you show your code again ? Best regards;  Yes Demus that´s right. I´m accessing an object after it is deleted because the pointer that points on this (deleted) object points to 0xfeeefeee and not to NULL!In my code I try the following:// Creates a quadtree (depth=3)a = BuildQuadtree(Vector2(), 200, 3);// Deletes first subtreedelete (a->mpChild[0]);// ... some time laterif(a->mpChild[0]){drawQuadtree(node->mpChild[0], hdc, ...);}a->mpChild[0] == TRUE because it doesn´t points to NULL and the drawQuadtree()-Function accesses data from the deleted subtree and it crashes. :(   