C Dynamic allocation of matrices and vectors

Question

I'm writing this code in C to implement a genetic algorthm. This is the part where I do the dynamic allocation of all the working structures (matrices and vectors). When I run this, sometimes (3 times on 5) it crashes. I'm doing something wrong with the allocation?

int main()
{

const char progress[] = "|/-\\";
int n, popSize, numIter,optRoute,minDist,range,globalMin,idx;
int maxcell;
int i,j,p,t,k,d,iter,perm,index,m;
int dists[4];
int* dmat, * totalDist, * distHistory, *randomOrder, *bestOf4Route;
int** pop, ** newPop, ** tmpPop, **rtes;
unsigned int iseed = (unsigned int)time(NULL);

// Values initialization
n = 5;
range = 10;
popSize = 100;
numIter = 1*10^4;
globalMin = 100000;

srand (iseed);

//printf("Insert the number of cities: ");
//scanf("%i",&n);

printf("Matrix costs creation...");
// Creates dmat NxN matrix
// dmat è una matrice triangolare superiore con diag = 0
// declare halfsize 1D array
maxcell = ((n*n)-n)/2;
dmat = (int*)malloc(maxcell * sizeof(int));

//set array
for(i=0; i<maxcell; i++)
    dmat[i] = (rand()%10)+2;

printf("done.\n");

//print entire matrix
//print_triangmat(dmat,n);

printf("Creation of the pop matrix...");
// create popSize x N matrix
pop = (int**)malloc(n * sizeof(int*));
for (i = 0; i < n; i++) {
  pop[i] = (int*)malloc(popSize * sizeof(int));
}

printf("done.\n");
printf("Pop matrix loading...");
// charge the first row of the matrix
for (j = 0; j < n; j++) {
  pop[j][0] = j+1;
}

// charge the rest of the matrix with randperm of the first row
for (i = 0; i < popSize; i++)
{
    for (j = 0; j < n; j++)
    {
        perm = rand()%(n-j)+j;
        t = pop[perm][i];
        pop[perm][i] = pop[j][i];
        if(i!=popSize-1)
        pop[perm][i+1] = pop[j][i];
        pop[j][i] = t;
        if(i!=popSize-1);
        pop[j][i+1] = t;
    }
}
print_matrix(pop,popSize,n);

printf("done.\n");
printf("Creation of the working structures...");

// create 4 x N matrix
rtes = (int**)malloc(n * sizeof(int*));
for (i = 0; i < n; i++) {
  rtes[i] = (int*)malloc(4 * sizeof(int));
}

// Creates an array of popSize
totalDist = (int*)malloc(popSize * sizeof(int));

// Creates an array of numIter
distHistory = (int*)malloc(numIter * sizeof(int));

// Creates an array of n
bestOf4Route = (int*)malloc(n * sizeof(int));

// create 4 x N matrix
tmpPop = (int**)malloc(n * sizeof(int*));
for (i = 0; i < n; i++) {
  tmpPop[i] = (int*)malloc(4 * sizeof(int));
}

// create popSize x N matrix
newPop = (int**)malloc(n * sizeof(int*));
for (i = 0; i < n; i++) {
  newPop[i] = (int*)malloc(popSize * sizeof(int));
}

// Creates an array of popSize
randomOrder = (int*)malloc(popSize * sizeof(int));

printf("done.\n");

Should be "int main(int argc, char* argv[]) { /*...*/ return 0; }" — geometrian, Jan 27 '13 at 21:18
@IanMallett, `main` doesn't have to have arguments, but it should return a value http://c-faq.com/ansi/maindecl.html — Samuel Edwin Ward, Jan 27 '13 at 21:29
I could have sworn up and down that it did, but I'll admit that subsequent checks on the C99 and C++ standards disprove that. Thank you for correcting me. Was the same true in C90?--I can't get a pointer to a copy of that standard. — geometrian, Jan 28 '13 at 05:59
@SamuelEdwinWard int main() is valid but invokes implementation-defined behavior, as opposed to int main(void) and int main(int argc char* argv []) [More info here](http://stackoverflow.com/questions/13876868/void-mainvoid-vs-main/13879155#13879155). Also, main does not need to return a value, [more info here](http://stackoverflow.com/questions/5296163/why-is-the-type-of-the-main-function-in-c-and-c-left-to-the-user-to-define/5296593#5296593). — Lundin, Jan 31 '13 at 09:17
@IanMallett He is actually more confused than you are. See the two above links in my comment above. — Lundin, Jan 31 '13 at 09:19
@Lundin, I know `f()` is different from `f(void)` in a prototype, but isn't `f()` equivalent to `f(void)` in a function definition? — Samuel Edwin Ward, Jan 31 '13 at 14:11
@SamuelEdwinWard f() as definition means "accept anything", unless there is a prototype with a contradicting declaration. You can pass any number of parameters of any kind to such a function, though they will just be ignored. As for main() it is a special case without a prototype. Suppose the OS calls your `main()` with argv+argc - what will happen isn't obvious and left to the implementation (for example, the Windows API has external functions for parameter passing, that you can use even if main happened to be `int main()` with no argv+argc). — Lundin, Jan 31 '13 at 14:29
(But please note that in practice, `int main()` will work just fine on all known compilers.) — Lundin, Jan 31 '13 at 14:31
@Lundin, interesting; I hadn't grasped that distinction. Thanks. — Samuel Edwin Ward, Jan 31 '13 at 15:25

score 2 · Answer 1 · answered Jan 27 '13 at 21:18

2

pop = (int**)malloc(n * sizeof(int*));
for (i = 0; i < popSize; i++) {
  pop[i] = (int*)malloc(popSize * sizeof(int));
}

if popSize > n you are in trouble here...

answered Jan 27 '13 at 21:18

Emanuele Paolini

9,912
3
38
64

woryzower · Accepted Answer · 2013-01-31T09:11:05.883

1

Problem is here. Consider i=popsize-1 then you will write to pop[perm][popsize] which is an invalid memory position. Then when allocations below are requested, sometimes requested memory position is intersected with pop[perm][popsize] so you are getting the runtime error.

for (i = 0; i < popSize; i++) {
    for (j = 0; j < n; j++) {
        perm = rand()%(n-j)+j;
        t = pop[perm][i];
        pop[perm][i] = pop[j][i];
        if(i!=popsize-1)
        pop[perm][i+1] = pop[j][i];
        pop[j][i] = t;
        if(i!=popsize-1)
        pop[j][i+1] = t;
    }
}

On the other hand there many wrong memory allocations:

    pop = (int**)malloc(n * sizeof(int*));
    for (i = 0; i < popSize; i++) {
      pop[i] = (int*)malloc(popSize * sizeof(int));
    }

should be

pop = (int**)malloc(n * sizeof(int*));
for (i = 0; i < n; i++) {
  pop[i] = (int*)malloc(popSize * sizeof(int));
}

and

 rtes = (int**)malloc(n * sizeof(int*));
    for (i = 0; i < 4; i++) {
      rtes[i] = (int*)malloc(4 * sizeof(int));
    }

should be

rtes = (int**)malloc(n * sizeof(int*));
for (i = 0; i < n; i++) {
  rtes[i] = (int*)malloc(4 * sizeof(int));
}

and

tmpPop = (int**)malloc(n * sizeof(int*));
for (i = 0; i < 4; i++) {
  tmpPop[i] = (int*)malloc(4 * sizeof(int));
}

should be

tmpPop = (int**)malloc(n * sizeof(int*));
for (i = 0; i < n; i++) {
  tmpPop[i] = (int*)malloc(4 * sizeof(int));
}

There is one more ambiguity in the problem.

numIter = 1*10^4;

This makes numIter 14 since ^ is logical XOR operator. Are you sure to want to do so?

edited Jan 31 '13 at 09:11

answered Jan 27 '13 at 21:37

woryzower

956
3
15
22

The same should be for pop and newpop? – Malo Jan 28 '13 at 09:03
if you want popsize*n matrix you should first do int** newpop=malloc(popsize*sizeof(int*), then allocate n*sizeof(int) for each newpop[i] – woryzower Jan 28 '13 at 20:52
of course, in fact when I realized, I represented a matrix of NxM whit matrix[M][N]. And that worked...but still it's not my problem. The problem is that sometimes (non everytime but often) it frezees. – Malo Jan 29 '13 at 21:02
Ok, I putted the entire code. It freezes in the point where I do the allocation for all the structures – Malo Jan 30 '13 at 08:19
I edited my answer, problem is in the for loop. Besides don't forget to change array allocations as I wrote. – woryzower Jan 30 '13 at 16:01
Thank you for helping, I've done as you told me. However, when it run the part aofter the printf("Creation of the working structures...");, still the problem. Do I have to modify the matrix rappresentation? For example, if have allocated a matrix NxM, I access it with matrix[M][N] (the opposite), right? I updated the code. – Malo Jan 31 '13 at 08:52
Remove the semicolon after the second if(popsize-1!=0).Sorry about that.On the other hand you can access matrix with the way you wrote but in general mxn matrixes are accesed with matrix[m][n] for simplicity. – woryzower Jan 31 '13 at 09:13

C Dynamic allocation of matrices and vectors

2 Answers2