Strange error of memory

[sylsau]

Hi,

I am doing a little program who calculates the permutation of a set of
vertex.
I use the recursivity for this calcul.

My function who calculate the permutations :

void permutation(set *e, int *current, int nbre)
{
set *p, *copie;
int *tmp;
int i;

if(e != NULL)
{
p = e;

tmp = realloc(current, sizeof *current *(nbre+1));

if(tmp == NULL) exit(-1);
else current = tmp;


while(p != NULL)
{
copie = copie_elt(e); // the function copie_elt let to copy the
set e and to return this copy
current[nbre] = p->st;
delete_elt(&copie,p->st); // this function let to delete an
element of copie. The element who

// is associated with the value p->st
permutation(copie,current,nbre+1); // call of permutation with the
set reducted.
p = p->suivant;
}

}else{

// In current, we have stocked the current permutation,
so we print it
for(i=0; i<nbre; i++)
printf("%d - ",current);

printf("\n");

}

}

I call it in the main with :

/* initialization of the variable e */

permutation(set,current,0);

By executing the program, I have this on my screen (I tried to debug
with GDB) :

(gdb) run

3 - 1 - 2 - 4 -
*** glibc detected *** double free or corruption (fasttop): 0x0804a048
***

Program received signal SIGABRT, Aborted.
0x4004ea27 in raise () from /lib/tls/libc.so.6

(gdb)


So, I tried this function with a char * for the variable current, the
code gives it :


void permutation(set *e, char *current, int nbre)
{
set *p, *copie;
char *tmp;
int i;

if(e != NULL)
{
p = e;

tmp = realloc(current, sizeof *current *(nbre+1));

if(tmp == NULL) exit(-1);
else current = tmp;


while(p != NULL)
{
copie = copie_elt(e); // the function copie_elt let to copy the
set e and to return this copy
current[nbre] = p->st;
delete_elt(&copie,p->st); // this function let to delete an
element of copie. The element who

// is associated with the value p->st
permutation(copie,current,nbre+1); // call of permutation with the
set reducted.
p = p->suivant;
}

}else{

// In current, we have stocked the current permutation,
so we print it
for(i=0; i<nbre; i++)
printf("%d - ",current);

printf("\n");

}

}

I call it in the main with :

permutation(e,current,0);


And there, the program gives the waited answer :


(gdb) run
3 - 1 - 2 - 4 -
3 - 1 - 4 - 2 -
3 - 2 - 1 - 4 -
3 - 2 - 4 - 1 -
3 - 4 - 1 - 2 -
3 - 4 - 2 - 1 -
1 - 3 - 2 - 4 -
1 - 3 - 4 - 2 -
1 - 2 - 3 - 4 -
1 - 2 - 4 - 3 -
1 - 4 - 3 - 2 -
1 - 4 - 2 - 3 -
2 - 3 - 1 - 4 -
2 - 3 - 4 - 1 -
2 - 1 - 3 - 4 -
2 - 1 - 4 - 3 -
2 - 4 - 3 - 1 -
2 - 4 - 1 - 3 -
4 - 3 - 1 - 2 -
4 - 3 - 2 - 1 -
4 - 1 - 3 - 2 -
4 - 1 - 2 - 3 -
4 - 2 - 3 - 1 -
4 - 2 - 1 - 3 -

Program exited normally.
(gdb)

Here, the program gives all the permutations for the set = {1,2,3,4}.
It's good but the only thing that I changed between the two functions
is the int * who becam a char *.

So, I don't know what is the probleme in the first version of
permutation with the int *.
Someone would have an idea of the problem who cause this error ?

Thanks for your help.

Sylvain.

 

[usr.root]

sylsau 写é“：

Hi,

I am doing a little program who calculates the permutation of a set of
vertex.
I use the recursivity for this calcul.

My function who calculate the permutations :

void permutation(set *e, int *current, int nbre)
{
set *p, *copie;
int *tmp;
int i;

if(e != NULL)
{
p = e;

tmp = realloc(current, sizeof *current *(nbre+1));

if(tmp == NULL) exit(-1);
else current = tmp;


while(p != NULL)
{
copie = copie_elt(e); // the function copie_elt let to copy the
set e and to return this copy
current[nbre] = p->st;
delete_elt(&copie,p->st); // this function let to delete an
element of copie. The element who

// is associated with the value p->st
permutation(copie,current,nbre+1); // call of permutation with the
set reducted.
p = p->suivant;
}

}else{

// In current, we have stocked the current permutation,
so we print it
for(i=0; i<nbre; i++)
printf("%d - ",current);

printf("\n");

}

}

I call it in the main with :

/* initialization of the variable e */

permutation(set,current,0);

By executing the program, I have this on my screen (I tried to debug
with GDB) :

(gdb) run

3 - 1 - 2 - 4 -
*** glibc detected *** double free or corruption (fasttop): 0x0804a048
***

Program received signal SIGABRT, Aborted.
0x4004ea27 in raise () from /lib/tls/libc.so.6

(gdb)


So, I tried this function with a char * for the variable current, the
code gives it :


void permutation(set *e, char *current, int nbre)
{
set *p, *copie;
char *tmp;
int i;

if(e != NULL)
{
p = e;

tmp = realloc(current, sizeof *current *(nbre+1));

if(tmp == NULL) exit(-1);
else current = tmp;


while(p != NULL)
{
copie = copie_elt(e); // the function copie_elt let to copy the
set e and to return this copy
current[nbre] = p->st;
delete_elt(&copie,p->st); // this function let to delete an
element of copie. The element who

// is associated with the value p->st
permutation(copie,current,nbre+1); // call of permutation with the
set reducted.
p = p->suivant;
}

}else{

// In current, we have stocked the current permutation,
so we print it
for(i=0; i<nbre; i++)
printf("%d - ",current);

printf("\n");

}

}

I call it in the main with :

permutation(e,current,0);


And there, the program gives the waited answer :


(gdb) run
3 - 1 - 2 - 4 -
3 - 1 - 4 - 2 -
3 - 2 - 1 - 4 -
3 - 2 - 4 - 1 -
3 - 4 - 1 - 2 -
3 - 4 - 2 - 1 -
1 - 3 - 2 - 4 -
1 - 3 - 4 - 2 -
1 - 2 - 3 - 4 -
1 - 2 - 4 - 3 -
1 - 4 - 3 - 2 -
1 - 4 - 2 - 3 -
2 - 3 - 1 - 4 -
2 - 3 - 4 - 1 -
2 - 1 - 3 - 4 -
2 - 1 - 4 - 3 -
2 - 4 - 3 - 1 -
2 - 4 - 1 - 3 -
4 - 3 - 1 - 2 -
4 - 3 - 2 - 1 -
4 - 1 - 3 - 2 -
4 - 1 - 2 - 3 -
4 - 2 - 3 - 1 -
4 - 2 - 1 - 3 -

Program exited normally.
(gdb)

Here, the program gives all the permutations for the set = {1,2,3,4}.
It's good but the only thing that I changed between the two functions
is the int * who becam a char *.

So, I don't know what is the probleme in the first version of
permutation with the int *.
Someone would have an idea of the problem who cause this error ?

Thanks for your help.

Sylvain.

because the realloc() return a char* value,if you want to use like
this :
int * tmp;
tmp = realloc(current, sizeof *current *(nbre+1));
you must do a casting, write like this tmp = (char *)realloc(current,
sizeof *current *(nbre+1));

 

[pete]

Hi,

I am doing a little program who
calculates the permutation of a set of vertex.

Post the whole program.

 

[pete]

because the realloc() return a char* value,if you want to use like
this :
int * tmp;
tmp = realloc(current, sizeof *current *(nbre+1));
you must do a casting, write like this tmp = (char *)realloc(current,
sizeof *current *(nbre+1));

I can't make sense out of that.
It almost seems as though you're saying that
realloc returns type char*, and that a (char*) cast
will somehow help you assign that return value
to an int* variable.

 

[Keith Thompson]

because the realloc() return a char* value,if you want to use like
this :
int * tmp;
tmp = realloc(current, sizeof *current *(nbre+1));
you must do a casting, write like this tmp = (char *)realloc(current,
sizeof *current *(nbre+1));

Wrong, and wrong.

realloc() returns a void*, which can be implicitly converted to any
pointer-to-object type (no cast is necessary or recommended).

 

[sylsau]

THe whole program :

#include <stdio.h>
#include <stdlib.h>

typedef struct ensemble{
int st;
struct ensemble *suivant;
}ensemble;


void supprimer_elt(ensemble **e, int nbre)
/* supprime elt nbre de e */
{
ensemble *p, *prec;

prec = NULL;
p = *e;

while(p != NULL && p->st != nbre)
{
prec = p;
p = p->suivant;
}

if(prec == NULL) // on supprime l'elt de tete
*e = (*e)->suivant;
else
prec->suivant = p->suivant;

free(p);

}

ensemble *copie_elt(ensemble *e)
/* renvoie la copie de e */
{
ensemble *copie = NULL, *new, *p, *insertion;

if( e != NULL)
{
copie = copie_elt(e->suivant);
new = (ensemble *) malloc(sizeof *new);
new->st = e->st;
new->suivant = copie;
copie = new;

}

return copie;
}


void permut(ensemble *e, int *current, int nbre)
{
ensemble *p, *copie;
int i;
int *tmp;

if(e != NULL)
{
p = e;

tmp = realloc(current, sizeof *current *(nbre+1));

if(tmp == NULL) exit(-1)
else current = tmp;

while(p != NULL)
{
copie = copie_elt(e);
current[nbre] = p->st;
supprimer_elt(&copie,p->st);
permut(copie,current,nbre+1);
p = p->suivant;
}

}else{


for(i=0; i<nbre; i++)
printf("%d - ",current);

printf("\n");

}

}

int main(int argc, char **argv)
{
ensemble *e1,*e2,*e3,*e4,*p,*copie;
int *res = NULL;

e1 = (ensemble *) malloc(sizeof *e1);
e2 = (ensemble *) malloc(sizeof *e2);
e3 = (ensemble *) malloc(sizeof *e3);
e4 = (ensemble *) malloc(sizeof *e4);

e1->st = 3;
e2->st = 1;
e3->st = 2;
e4->st = 4;

e1->suivant = e2;
e2->suivant = e3;
e3->suivant = e4;
e4->suivant = NULL;

permut(e1,res,0);

return 0;
}

 

[David Resnick]

THe whole program :

#include <stdio.h>
#include <stdlib.h>

typedef struct ensemble{
int st;
struct ensemble *suivant;
}ensemble;


void supprimer_elt(ensemble **e, int nbre)
/* supprime elt nbre de e */
{
ensemble *p, *prec;

prec = NULL;
p = *e;

while(p != NULL && p->st != nbre)
{
prec = p;
p = p->suivant;
}

if(prec == NULL) // on supprime l'elt de tete
*e = (*e)->suivant;
else
prec->suivant = p->suivant;

free(p);

}

ensemble *copie_elt(ensemble *e)
/* renvoie la copie de e */
{
ensemble *copie = NULL, *new, *p, *insertion;

if( e != NULL)
{
copie = copie_elt(e->suivant);
new = (ensemble *) malloc(sizeof *new);
new->st = e->st;
new->suivant = copie;
copie = new;

}

return copie;
}


void permut(ensemble *e, int *current, int nbre)
{
ensemble *p, *copie;
int i;
int *tmp;

if(e != NULL)
{
p = e;

tmp = realloc(current, sizeof *current *(nbre+1));

if(tmp == NULL) exit(-1)
else current = tmp;

while(p != NULL)
{
copie = copie_elt(e);
current[nbre] = p->st;
supprimer_elt(&copie,p->st);
permut(copie,current,nbre+1);
p = p->suivant;
}

}else{


for(i=0; i<nbre; i++)
printf("%d - ",current);

printf("\n");

}

}

int main(int argc, char **argv)
{
ensemble *e1,*e2,*e3,*e4,*p,*copie;
int *res = NULL;

e1 = (ensemble *) malloc(sizeof *e1);
e2 = (ensemble *) malloc(sizeof *e2);
e3 = (ensemble *) malloc(sizeof *e3);
e4 = (ensemble *) malloc(sizeof *e4);

e1->st = 3;
e2->st = 1;
e3->st = 2;
e4->st = 4;

e1->suivant = e2;
e2->suivant = e3;
e3->suivant = e4;
e4->suivant = NULL;

permut(e1,res,0);

return 0;
}

Compiled as is, your program gives these warnings and errors:
foo.c: In function `copie_elt':
foo.c:35: warning: unused variable `p'
foo.c:35: warning: unused variable `insertion'
foo.c: In function `permut':
foo.c:64: syntax error before "else"
foo.c: In function `main':
foo.c:88: warning: unused variable `p'
foo.c:88: warning: unused variable `copie'

Unused variables, OK, missing ;??? Strange, does it compile for you?

Real problem: You are doing a recursive call to permut. In some levels
of recursion
you are reallocing a pointer (current) that other recursion levels
still have and use.
That results in them using freed memory.

-David

 

[pete]

Real problem: You are doing a recursive call to permut.
In some levels of recursion
you are reallocing a pointer (current) that other recursion levels
still have and use.
That results in them using freed memory.

It looks to me like an attempted synthesis
of array and linked list techniques.
Permutating a small array is pretty simple,
but I've also been trying to permutate a linked list
and it's been confusing for me.

 

[Ben Pfaff]

Permutating a small array is pretty simple,
but I've also been trying to permutate a linked list
and it's been confusing for me.

(I believe that "permute", not "permutate", is the verb you are
looking for.)

I have an implementation, if I understand what you're talking
about:

/* Arranges R0...R1 into the lexicographically next greater
permutation. Returns true if successful.
If R0...R1 is already the lexicographically greatest
permutation of its elements (i.e. ordered from greatest to
smallest), arranges them into the lexicographically least
permutation (i.e. ordered from smallest to largest) and
returns false.
COMPARE with auxiliary data AUX is used to compare nodes. */
bool
ll_next_permutation (struct ll *r0, struct ll *r1,
ll_compare_func *compare, void *aux)
{
if (r0 != r1)
{
struct ll *i = ll_prev (r1);
while (i != r0)
{
i = ll_prev (i);
if (compare (i, ll_next (i), aux) < 0)
{
struct ll *j;
for (j = ll_prev (r1); compare (i, j, aux) >= 0; j = ll_prev (j))
continue;
ll_swap (i, j);
ll_reverse (ll_next (j), r1);
return true;
}
}

ll_reverse (r0, r1);
}

return false;
}

Of course there are prerequisites, but I suspect that you won't
have trouble figuring out what they are.

 

[pete]

(I believe that "permute", not "permutate", is the verb you are
looking for.)

I'm sure it is.

I have an implementation, if I understand what you're talking
about:

/* Arranges R0...R1 into the lexicographically next greater
permutation. Returns true if successful.
If R0...R1 is already the lexicographically greatest
permutation of its elements (i.e. ordered from greatest to
smallest), arranges them into the lexicographically least
permutation (i.e. ordered from smallest to largest) and
returns false.
COMPARE with auxiliary data AUX is used to compare nodes. */
bool
ll_next_permutation (struct ll *r0, struct ll *r1,
ll_compare_func *compare, void *aux)
{
if (r0 != r1)
{
struct ll *i = ll_prev (r1);
while (i != r0)
{
i = ll_prev (i);
if (compare (i, ll_next (i), aux) < 0)
{
struct ll *j;
for (j = ll_prev (r1); compare (i, j, aux) >= 0; j = ll_prev (j))
continue;
ll_swap (i, j);
ll_reverse (ll_next (j), r1);
return true;
}
}

ll_reverse (r0, r1);
}

return false;
}

Of course there are prerequisites, but I suspect that you won't
have trouble figuring out what they are.

I'll see what I can do with it.
Thank you.