Velocity Reviews > Strange error of memory

# Strange error of memory

sylsau
Guest
Posts: n/a

 11-20-2005
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[i]);

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[i]);

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@gmail.com
Guest
Posts: n/a

 11-21-2005

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[i]);
>
> 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[i]);
>
> 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
Guest
Posts: n/a

 11-21-2005
sylsau wrote:
>
> Hi,
>
> I am doing a little program who
> calculates the permutation of a set of vertex.

Post the whole program.

--
pete

pete
Guest
Posts: n/a

 11-21-2005
http://www.velocityreviews.com/forums/(E-Mail Removed) wrote:

> 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.

--
pete

Keith Thompson
Guest
Posts: n/a

 11-21-2005
"(E-Mail Removed)" <(E-Mail Removed)> writes:
[...]
> 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).

--
Keith Thompson (The_Other_Keith) (E-Mail Removed) <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <*> <http://users.sdsc.edu/~kst>
We must do something. This is something. Therefore, we must do this.

sylsau
Guest
Posts: n/a

 11-21-2005
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[i]);

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
Guest
Posts: n/a

 11-21-2005

sylsau wrote:
> 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[i]);
>
> 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
Guest
Posts: n/a

 11-22-2005
David Resnick wrote:
>
> sylsau wrote:
> > THe whole program :

> 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.

--
pete

Ben Pfaff
Guest
Posts: n/a

 11-22-2005
pete <(E-Mail Removed)> writes:

> 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

/* 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.
--
Go not to Usenet for counsel, for they will say both no and yes.

pete
Guest
Posts: n/a

 11-22-2005
Ben Pfaff wrote:
>
> pete <(E-Mail Removed)> writes:
>
> > 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'm sure it is.

> I have an implementation, if I understand what you're talking
>
> /* 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.

--
pete