Spot the leak! Programming Challenge!!!

[xenovacivus]

Here's a fun one. This program has a memory leak. See if you can find it!

I had a much larger program with this same memory problem in it, took me a good deal of time and a half a 2 liter of mountain dew to figure it out...

#include <iostream>
using namespace std;

struct Thing
{
    int *deally;     // used for a dynamic array if integers.
    int deallysize;  // something to keep track of the array size.
};


int main()
{
    int thingCount = 10;
    Thing things [thingCount];
    for (int i=0; i<thingCount; i++)
    {
        things [i].deallysize = i+1;
        things [i].deally = new int [i+1];
        things [i].deally [0] = 100 + i;
    }

    // Print things-
    for (int i=0; i<thingCount; i++)
        cout << "thing# " << i << " = " << things [i].deally [0] << endl;

    /// Remove element x from the list.
    /// Instead of leaving the space
    /// empty, replace it with the last
    /// element.
    int x = 4;

    cout << endl;
    cout << "removing element " << x << " and replacing with last" << endl;
    cout << endl;

    thingCount--;                              // thingCount has decreased by one.
    things [x] = things [thingCount];          // replace element x with the last element.

    /// delete the last element
    things [thingCount].deallysize = 0;        // set the size of the array to zero.
    if (things [thingCount].deally !=0)        // check if the array exists.
    {
        delete [] things [thingCount].deally;  // if it does, delete the array.
        things [thingCount].deally = 0;        // and set the pointer to zero.
    }


    // Print things-
    for (int i=0; i<thingCount; i++)
        cout << "thing# " << i << " = " << things [i].deally [0] << endl;

    /// delete the remaining elements in the array before exiting
    for (int i=0; i<thingCount; i++)
    {
        things [i].deallysize = 0;
        if (things [i].deally != 0)
        {
            delete [] things [i].deally;
            things [i].deally = 0;

        }
    }

    cin.get ();
	return 0;
}

K, it might be obvious to anybody familiar with pointers and memory allocation, but I'll bet a few of you have done the same thing sometime or another! Please, post a solution and let me know how quick you figured it out! :D

[Danny]

I didn't test the code but I think your last loop shouldn't check
if (things [i].deally != 0)

Simply use
delete [] things [i].deally;

in a loop that has thingscount iterations. Deleting a NULL pointer is harmless and safe, and besides, I would simply move the allocation and deallocation stuff to a constructor and destructor inside Thing. It's so much simpler!

[xenovacivus]

I was reading through this very good c++ tutorial and it gave me the impression I should delete each pointer once, and only once... http://www.informit.com/guides/conte...seqNum=42&rl=1

No matter.
As for the program- it would be easier/cleaner to use a constructor/destructor to alloc/delete the data, but the idea was to code up a quick example demonstrating a major flaw I came across in a much larger program (without posting not-working pieces of the larger program here).

And for those who are to lazy (or just don't have the time to figure it out), here's where the memory leak happens.

    things [x] = things [thingCount]; 

    things [thingCount].deallysize = 0;       
    if (things [thingCount].deally !=0)     
    {
        delete [] things [thingCount].deally; 
        things [thingCount].deally = 0;       
    }

The leak occurs when assigning things [x] to things [thingCount]. Normally, this would work fine. All the elements in things [x] are set to the values in things [thingCount]. BUT! there's a pointer in them thar elements!!! meaning, the pointer in things [x] is overwritten and LOST! Leak!!! This is kinda a harmless leak, since the data lost was to be deleted anyway (and not accessed again). The larger problem is the next few lines, where thing [thingCount] is deleted. Since the pointer here is the same address as the one in things [x], the array in things [x] is deleted! And the program may expect to access (read and write) data to that array! It's not an easy error to catch when you've got to go through hundreds of lines of code...

The solution: Realizing that the pointer will be overwritten anyway, delete it and prevent that part of the leak. Then, do not delete the array in the last element. Instead, set the pointer to null and "deallysize" to zero. Setting the pointer to null without deleting the array is very wrong by any tutorial standards I've come across, but since the array exists twice, it's safe to remove the reference to it once.

Here's the fixed code-

    
    if (things [x].deally !=0)
    {
        delete [] things [x].deally;
        things [x].deally = 0;
    }

    things [x] = things [thingCount];    

    things [thingCount].deallysize =0;
    things [thingCount].deally = 0;

or alternatively and possibly safer-

    
    // swap element x with the last-
    Thing temp;
    temp = things [x];
    things [x] = things [thingCount];
    things [thingCount] = temp;

    // completely delete the last element-
    things [thingCount].deallysize = 0;
    if (things [thingCount].deally !=0)
    {
        delete [] things [thignCount].deally;
        things [thingCount].deally = 0;
    }
    // no need to delete the array in temp, 
    // it's already been deleted when the last
    // element was deleted (since both pointers
    // point toward the same spot in memory).

[Danny]

Nice example.
It's worth noting though that in real world programming, struct Thing would be implemented as follows:
struct Thing
{
vector<int> vi;
};

This way, not only is the memory management completely automatic, you don't need to track the size of the array manually. Additionally, copying a Thing object is perfectly safe because vector defines a copy ctor and assignment opeartor. I think that your example is a compelling argument in favor of vector and STL in general.

[xenovacivus]

haha, yes, I suppose it is. :D