471,570 Members | 962 Online
Bytes | Software Development & Data Engineering Community
Post +

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 471,570 software developers and data experts.

Strange error of memory

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.

Nov 20 '05 #1
9 1345

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));

Nov 21 '05 #2
sylsau wrote:

Hi,

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


Post the whole program.

--
pete
Nov 21 '05 #3
us******@gmail.com 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
Nov 21 '05 #4
"us******@gmail.com" <us******@gmail.com> 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) ks***@mib.org <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.
Nov 21 '05 #5
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;
}

Nov 21 '05 #6

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

Nov 21 '05 #7
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
Nov 23 '05 #8
pete <pf*****@mindspring.com> 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
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.
--
Go not to Usenet for counsel, for they will say both no and yes.
Nov 23 '05 #9
Ben Pfaff wrote:

pete <pf*****@mindspring.com> 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
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.

--
pete
Nov 23 '05 #10

This discussion thread is closed

Replies have been disabled for this discussion.

Similar topics

6 posts views Thread by Gary | last post: by
11 posts views Thread by Martin Joergensen | last post: by
11 posts views Thread by VijaKhara | last post: by
5 posts views Thread by Jeff | last post: by
reply views Thread by XIAOLAOHU | last post: by
reply views Thread by leo001 | last post: by
reply views Thread by Vinnie | last post: by
reply views Thread by lumer26 | last post: by

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.