Function works for only 201700 times?

[Nuserame]

Hi everyone,

I've got another beginner question so I hope you can help me.
In my code I have a struct called 'test', a function called 'add' to connect a test-struct to another test-struct and a main method in which I try to execute the code.

Now here's the thing, the add function seems to work fine, but when executing this function for about 201700 times, the program hangs and shuts down immediately.
I don't understand how this function seems to work fine for the first 201700 times, but then suddenly stops.

Another weird thing is, when removing the line int matrix[50][50]; there seems to be no problem at all! But I can't just remove this line since I need it later for other functions.

Here's the code I'm talking about:

#include <cstdlib>
#include <iostream>

using namespace std;

struct test{
   int matrix[50][50];
   test* next;
   test* child;
   test* parent;
};

void add(test* & start, test* addm){
   test* copy = new test;
   copy->child = NULL;
   copy->parent = addm->parent;
   copy->next = start;
   start = copy;
}

int main(int argc, char *argv[])
{
    test *b = new test;
    test *k = new test;
    int i = 0; 
    while(i < 999999){
         i++;
         add(b, k);
         //hangs and shuts down immediately 
         //when i is about 201700 - 201720
    }   
    return EXIT_SUCCESS;
}

I hope you could help me, thanks for reading!

[GhqjLyTq]

You're allocating a new test on line 14, but never freeing it. It's done every time add is called. It probably stops because new returns a null pointer after it runs out of memory, and it then crashes when it attempts to access it.

Removing the int matrix[50][50]; makes it not happen because it significantly reduces the size of test (from 2512 bytes to 12 bytes), so it would take many more calls to add for it to still happen.

[tntxtnt]

int [50][50] = 10k bytes

add 200k times... 200k * 10k = 2 GB memory

I guess your RAM is 3-4GB, and 1-2GB is already used for other processes. So there is no space left in your memory -> program stops

[Nuserame]

OK! Thank you very much! Now I finally understand :)

To fix this, I should just add free(copy); at the and of the add-function? Or does it not work like that?

[tntxtnt]

because your struct test is too big (10k bytes), you can't add 1000000 distinct copies of it, unless your computer has more than 10GB RAM...

you can have 1mil pointers point to the same 2D array, but if you changed values of array which pointer 1 point to, pointer 2,3,4,...,1000000 will have their array changed, too, because they use the same array...

[GhqjLyTq]

free(copy); should work, but make sure that you're done using it when you free it. Since you're using new to allocate it, you probably should use delete copy; to free it instead. The shared_ptr class ( http://www.cplusplus.com/reference/memory/shared_ptr/ ) might be helpful also.

[Nuserame]

OK, thank you very much again!

But now I have another problem, when I use free(copy); or delete copy;, this whole list becomes messed up.
It looks like the add function adds infinite test* k's to test* b, or it looks like some object may point to itself or something.

When removing free(copy); or delete copy; and replacing while(i < 999999){ by while(i < 9){, the list doesn't look messed up.

What am I doing wrong?

[tntxtnt]

if you use delete or free while adding, your list will look like this
[?]->[?]->[?]->[?]->……->[?]->null //? is location of deleted memory

instead of
[a]->[b]->[c]->[d]->……->[z]->null

because after added a, or b, or c,... to your list, you delete it immidiately. So you can't use it.

only delete when you are done.

change int[50][50] to int[20][20] and add a free( test* & start) function. Put free(b); before return EXIT_SUCCESS;

DO NOT loop 1mil times without a free() function, or you'll have to restart your computer.

[Nuserame]

OK thanks!
But this means I have to change int[50][50] to int[20][20] while I really need int[50][50] for my other functions.
Isn't there another way to solve this so I can keep the int[50][50] without a crashing program or an infinite list?

[Chervil]

Buy a bigger computer with more RAM maybe?

Or re-consider the design for whatever it is you are trying to achieve. It's hard to say, as the code posted is presumably a proposed solution to a problem. But what was the original problem, what is the code intended to achieve?

[Nuserame]

Haha I could indeed buy more RAM but since this is a part of school assignment I need to get this code running on one of these crappy school computers as well, so unfortunately that won't help :(

The code must create a list of all possible end states from a stupid two player game. Calculating all possible end states goes fine, but the problem is that I can't put them in a linked list.

As soon as I figured out how to create this list and keep the int[50][50], well then I think I'm almost with this assignment.

[Chervil]

But what sort of values do you need to store in the array? An int usually occupies 4 bytes, but maybe you don't need all of that space, perhaps a short int or even a char would do?

[Nuserame]

Well maybe you're right since I need to store int's of only 1 digit: zero's or 1's. What should I use?

[Chervil]

Well, as a first step, you could try char matrix[50][50];
That should be a drop-in replacement for the existing code.

Though that is still using much more storage than required.

You could take a look at bitset too. I don't have experience using this, but it seems capable of doing the job. Then instead of a 2-D array, you'd have a 1-D array of bitsets, I think.
http://www.cplusplus.com/reference/bitset/bitset/

[Chervil]

Comparison of int, char and bitset.

#include <iostream>
#include <bitset>
#include <cstdlib>

    using namespace std;

int main()
{
    int  imatrix[50][50];
    char cmatrix[50][50];
    bitset<50> bmatrix[50];

    cout << "sizeof(imatrix) = " << sizeof(imatrix) << endl;
    cout << "sizeof(cmatrix) = " << sizeof(cmatrix) << endl;
    cout << "sizeof(bitset) = "  << sizeof(bmatrix) << endl;

    for (int i=0; i<5; i++)
    {
        for (int j=0; j<5; j++)
        {
            int x = rand() % 2;
            imatrix[i][j] = x;
            cmatrix[i][j] = x;
            bmatrix[i][j] = x;
        }
    }

    for (int i=0; i<5; i++)
    {
        for (int j=0; j<5; j++)
        {
            cout << "int - char - bitset: " << imatrix[i][j]
                 << " " << (int) cmatrix[i][j]
                 << " " << bmatrix[i][j] << endl;
        }
    }

    return 0;
}