Cleaning up a Grid of Memory

Hullo hullo, I was hoping somebody could check my logic (or point out why my reasoning isn't correct) with the following code.

Most people here would've seen linked lists/doubly-linked lists and the such, well I've gone and made a 2-Dimensional Grid of nodes (each with an Up, Down, Next, and Previous pointer) such that at the edges, it loops back to the beginning of the row or column (depending on the direction being travelled). Pictures are wonderful here. (Attached)

Each square represents a node, and the one with the "O" is the OriginNode (there is a seperate pointer for this, kind of like a "head" or "first" pointer).

Now, I call this thing a Quadtree because I set out to create a Quadtree, but I realized I didn't need a lot of the capabilities of a Quadtree, and this Grid would work better, but I was too lazy to change the name of my functions, so don't be surprised when this looks nothing like a Quadtree :) (For those of you that remember, I set out to make this a LONG time ago)

Code:

---

//So, when it's time to destroy my Quadtree, I also want to destroy the Grid
cQUADTREE::~cQUADTREE(void)
{
    DestructTree(OriginLeaf, OriginLeaf->Next);
    //delete(OriginLeaf); //This is the pickle
}
//The rest is taken of recursively with
void cQUADTREE::DestructTree(cLEAF* LeftEnd, cLEAF* Temp)
{
    if(Temp->Next == LeftEnd)
    {
        if(LeftEnd->Down != OriginLeaf)
        {
            DestructTree(LeftEnd->Down, LeftEnd->Down->Next);
        }
        delete(LeftEnd);
        LeftEnd = NULL;
    }
    else
    {
        DestructTree(LeftEnd, Temp->Next);
    }

    delete(Temp);
    Temp = NULL;
}

---

Now, I can guarantee the Grid is setup properly since I've tested it by traversing the nuts out of it in all directions. I drew out a 2x2 and 3x3 grid on paper, and followed it through, and just as I thought, all those nodes get deleted.

So, what's the problem?
Well, according to my drawings and whatnot, the OriginNode should be deleted by the recursive function, since "LeftEnd" is initially set to OriginNode, and at the end of each row, LeftEnd is the first thing to be deleted.

However, if I uncomment that bolded line in the destructor and run the program, then when I exit, it exits happily. This should not be happening. The patented Microsoft "You did something unexpected, tell us about it" message box should pop up. But it doesn't.

So, I guess my most immediate question is, if I have already deleted OriginNode, then I should not be allowed to delete it again, right?

If somebody's up for checking the logic behind this all, feel free, but I would really be surprised if there was something wrong there after all these drawings. But, then again, there must be a mistake somewhere.

Thanks for giving this a read, I know it was a heftier one. As always, I'm open to any ideas or suggestions.

all nodes have either a left pointer, a right pointer, an up pointer or a down pointer that isn't NULL except if there is only one node in the container. When the container is built that single node is the origin, but when it is being destroyed the last node may, or may not be the original origin. I'd probably attempt this by starting the destruction at the original origin, then move right and destroy as long as there is a right, then move down one and destroy, and then destroy as long as there is a left, then move down and destroy it, and then destroy to the right as long as there is a right, etc until I'm left with a node that doesn't have any non NULL pointers, then destroy it. I'd probably assign origin to a temp node at each step, then change origin to the next node right/down/left, as the case may be, then destroy temp node and repeat using a loop and the appropriate case as need be, rather than using recursion, but I'm sure it could be done recursively if you have your heart set on it.

>>So, I guess my most immediate question is, if I have already deleted OriginNode, then I should not be allowed to delete it again, right?

I think you can call delete more than once on an object safely. Also, calling delete on NULL should be safe, and you set your pointers to NULL after you delete it, so I don't know why it would cause problems to delete it again.

Here's a thread that discusses a bit about new and delete.

Thanks for that article JaWiB, it definitely cleared that up (although, my whole reasoning as to why Microsoft's window pops up is completely blown now, but I'll get over it) :)

Elad, I used recursion before because the other method that I had took about 4 for loops and was really inefficient on so many leaves. But, I like the idea of just starting at the beginning and working my way through.

I took your idea Elad, but instead of moving left, then down, then right, then down (the zig-zag effect), I kept it always moving left, since the edges of the grid wrap back around to the beginning anyways, it shouldn't really throw any problems that I could see.

My modified code now is:

Code:

---

cQUADTREE::~cQUADTREE(void)
{
    cLEAF* Temp = OriginLeaf;
    cLEAF* Leaf = NULL;

    if(Temp != NULL)
    {
        while((Temp->Next != NULL)||(Temp->Previous != NULL)||(Temp->Up != NULL)||(Temp->Down != NULL))
        {
            if(Temp->Next == NULL)
            {
                Leaf = Temp;
                Temp = Temp->Down;

                delete(Leaf);
                Leaf = NULL;
            }
            Leaf = Temp;
            Temp = Temp->Next;

            delete(Leaf);
            Leaf = NULL;
        }
        delete(Temp);
        Temp = NULL;
    }
}

---

Again, I re-drew this on paper, and it all seemed fine, but now I am getting Microsoft's famous window. I've got a feeling that the NULL checks aren't actually working as I'd hoped.

I threw together some test code really quickly:

Code:

---

#include <stdio.h>

class TESTER
{
public:
    TESTER(void)
    {
        Next = NULL;
    }
    ~TESTER(void)
    {
       
    }

    TESTER* Next;
};

int main(void)
{
    TESTER* One = new TESTER;
    TESTER* Two = new TESTER;

    One->Next = Two;

   
    if(Two != NULL)
    {
//I double-checked this with a printf() before, and this code is firing
        delete(Two);
        Two = NULL;
    }

    if(One->Next == NULL)
    {
        printf("We should see this\n"); //Which we don't
    }

    return 0;
}

---

And it seems my guess was right, because that printf() isn't displaying anything on to the screen.

My thoughts were:
One->Next points at Two,
Two gets deleted, and NULLed,
So, One->Next points at NULL.
But apparently not?

Considering this test code, I don't see how else I can do my "->Next != NULL" checks if the deleting and nulling don't actually set those pointers to NULL.

Is there something that I'm missing here?

Thanks again for any input.

In your post you have a four by four grid. If you label nodes 1, 2, 3, 4 on the top row and 13, 14, 15, 16 on the bottom row etc, does 1 point to 4 and 13 as well as 2 and 5? I'm not sure it matters in terms of how I'd try to destroy the grid, but it might.


My assumption was that 1, 2, 3, 4 point to each other in sequence either going left or right depending where you start. I'd start at origing = 1, assign it to a temp node pointer, advance origing to 2, then delete temp node. When I get to 4 there is no other node to the right or left (1, 2, and 3 have been deleted) but there is a node to the bottom (and maybe the top), therefore I have to translate a row and start at the opposite end of where I started. My code to do this would start out looking something like:

Code:

---

Node * temp;
while(more)
{
  temp = origin;
  if(origin->right != NULL)  //move right if possible 
        origin = origin->right;
  else if(origin->left != NULL)  //move left if possible
        origin = origin->left;
  else if(origin->down != NULL)  //move down if needed
        origin = origin->down;
  else                                                          //this is last the last node
        more = false;                                //if worked my way down
                                                                          //from the top
 
  delete temp;
  decrease node count;
  display node count and pause so I can internally test my destructor.
}

---

Quote:

---

If you label nodes 1, 2, 3, 4 on the top row and 13, 14, 15, 16 on the bottom row etc, does 1 point to 4 and 13 as well as 2 and 5?

---

Yes, that is the layout. It does change things slightly too, because now, that second If Statement will never fire. You can always move right until a whole row is deleted, then it will jump down one row, and then it can move right again (never getting the chance to move left).

The problem that seems to be arising though is:
Assuming a 3x3 Grid:

1 2 3
4 5 6
7 8 9

(The numbers each represent a node)

Following your code:

Origin = 1

1st time through loop:

Temp = Origin = 1
Origin = 2
1 Gets Deleted

D 2 3
4 5 6
7 8 9

2nd time through loop:

Temp = Origin = 2
Origin = 3
2 Gets Deleted

D D 3
4 5 6
7 8 9

3rd time through loop:

Temp = Origin = 3

Now, on the next check:
if(origin->right != NULL)
Well, origin->right is pointing at 1, which as already been deleted, but I don't think that it means that origin->right equals NULL.

If that was the case, then that sample code I posted with the TESTER class should be displaying the final printf() line, should it not? Or maybe there's a difference I'm not seeing.

I think there's something tricky going on with the delete/not NULL comparisons that follow...

Code:

---

cQUADTREE::~cQUADTREE(void)
{
    cLEAF* Temp = OriginLeaf;
    cLEAF* Leaf = NULL;

    if(Temp != NULL)
    {
        while((Temp->Next != NULL)||(Temp->Previous != NULL)||(Temp->Up != NULL)||(Temp->Down != NULL))
        {
            if(Temp->Next == NULL)
            {
                Leaf = Temp;
                Temp = Temp->Down;

                if(Leaf->Next != NULL) Leaf->Next->Previous = NULL;
                if(Leaf->Previous != NULL) Leaf->Previous->Next = NULL;
                if(Leaf->Down != NULL) Leaf->Down->Up = NULL;
                if(Leaf->Up != NULL) Leaf->Up->Down  = NULL;

                delete(Leaf);
                Leaf = NULL;
            }
            Leaf = Temp;
            Temp = Temp->Next;

            if(Leaf->Next != NULL) Leaf->Next->Previous = NULL;
            if(Leaf->Previous != NULL) Leaf->Previous->Next = NULL;
            if(Leaf->Down != NULL) Leaf->Down->Up = NULL;
            if(Leaf->Up != NULL) Leaf->Up->Down  = NULL;

            delete(Leaf);
            Leaf = NULL;
        }
        delete(Temp);
        Temp = NULL;
    }
}

---

This is my new, edited code from above (note the new if statements). It no longer gives me any problems.

Temp and Leaf start at the Origin.
Temp moves right.
Leaf checks all surrounding nodes, and if there are any pointers coming from those nodes, then it makes them NULL (the 4 If Statements).
Then Leaf is deleted (along with all of its pointers being NULLed, in the destructor of the leaf).

This process is continued to the end of a row, at which point:
Temp drops down one row, Leaf does its job above, and movement to the right commences once again.

I drew out a 2x2 grid on paper and followed it through. All links between nodes, and all nodes are nulled. (I know 2x2 isn't the best sample to check, but anything more would take a lot of time).

At this point, I guess I'm assuming it's doing what I want it to, but, of course, it could be a huge memory leak in disguise. Does anybody know of any simpler (or if there aren't any, complicated) ways to track how much memory a program allocates/deallocates during runtime? (Other than writing the code for it myself into the program) :)

Thanks again for the help so far.

Lost access to the board yesterday afternoon but your last post encorportes the modifications I was thinking. I don't think you have to worry about memory leaks too much. I presume each node is declared with new when it is added to the QuadTree. If you increment a node count with each addition and then decrease the node count with each deletion/destruction you should be able to keep an internal tracking of memory useage.


If you want, I think your code can be streamlined some. During destruction of the Quadtree you don't need to NULL each and every pointer of every node affected by the deletion of a given node. You just need to NULL those you need to accomplish your task. As I see it, the grid is basically an overlapping series of circular lists with each row and each column being a circle, that is each node belongs to a unique row circle and a unique column circle. You can view the rows as the basis of the QuadTree and the last column as the glue holding the individual rows together. Each time you delete the first node of a row you break the row circle (you don't have to, but it seem easiest). Likewise, when you delete the last node in the first row you break the circle of the last column. If you handle those breaks as a separate case, then you don't have to handle all the various pointers for each node. I think the following will work. Note: This hasn't been tested, whereas yours has.

Code:

---

bool more = true;
Node * temp;
while(more)
{
  temp = origin;
 
  //delete all but far right node of this row
  if(origin->right != NULL)       
  {
          if(origin->left != NULL)  //row circle isn't broken yet
                origin->left->right = NULL;  //break circle by assigning NULL to right pointer in far right node of this row
 
          origin = origin->right;
          origin->left = NULL;  //only do nested if once
  }
  //delete last node in each row, ie,  the last column, except the last node in the last column
  else if(origin->right == NULL && origin->down != NULL)
  {
          //if last node in first row need to break circle of last column
          if(origin->up != NULL)
                origin->up->down = NULL;  //break circle by assigning NULL to down pointer in bottom node last column 
 
          //translate down one row to last node in row
          origin = origin->down;
          origin->up = NULL;  //only do nested if once
       
          //translate to first node of this row to start deleting this row from the first column
        origin = origin->right;
  }
  else //last node of last row, last node of QuadTree
          more = false;
 
  delete temp;
 
  //debugging code to confirm accurate destruction process to prevent memory leaks
  //cout << --NodeCount << endl;
  //char ch;
  //cin >> ch;
}

---

Ah yes, there it is, a lovely 0 leaves once the tree's been destructed, thanks for that simple, yet effective, tip elad.

I drew out a 2x2 board (and the top row of a 3x3 board) on paper and followed your code through, and I see what you mean that I don't necesserily have to do all of those checks that I do. Gotta say, that's a pretty impressive thought process you've got there :)

I wrote out your code into a form that'd work with what I have so far:

Code:

---

cQUADTREE::~cQUADTREE(void)
{
        cLEAF* Temp = NULL;

        while((OriginLeaf->Next != NULL)||(OriginLeaf->Down != NULL))
        {
                Temp = OriginLeaf;

                if(OriginLeaf->Next != NULL)
                {
                        if(OriginLeaf->Previous != NULL) OriginLeaf->Previous->Next = NULL;

                        OriginLeaf = OriginLeaf->Next;
                        OriginLeaf->Previous = NULL;
                }
                else if((OriginLeaf->Next == NULL)&&(OriginLeaf->Down != NULL))
                {
                        if(OriginLeaf->Up != NULL) OriginLeaf->Up->Down = NULL;

                        OriginLeaf = OriginLeaf->Down;
                        OriginLeaf->Up = NULL;
                        OriginLeaf = OriginLeaf->Next;
                }

                delete(Temp);
                Temp = NULL;
        }
        delete(OriginLeaf);
        OriginLeaf = NULL;
}

---

That extra delete() at the very end is because of the while condition I used intstead of the boolean flag, but other than that, in essence, it's the same. I tested it out and a solid 0 of 65536 leaves are left lying around.

Another solution to this problem, I'll probably stick with your method for the sake of avoiding the extra checks (although, even with 65536 leaves, it doesn't really add that much time, but still, why not be more efficient?) :)

Thanks again for all your help elad.

Ah the power of C++. Writing code that works for a 4 or 16 item sample and expanding it to over process of over 65000! Gotta luv it.


Congrats!