Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C Programming > Strange error of memory

Reply
Thread Tools

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.

 
Reply With Quote
 
 
 
 
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));

 
Reply With Quote
 
 
 
 
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
 
Reply With Quote
 
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
 
Reply With Quote
 
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.
 
Reply With Quote
 
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;
}

 
Reply With Quote
 
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

 
Reply With Quote
 
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
 
Reply With Quote
 
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
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.
 
Reply With Quote
 
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
> 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
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Strange error when reallocating memory francesco C Programming 18 12-27-2012 10:52 PM
AVG Email Scanner activating at strange times with strange IP addresses dennispublic@hotmail.com Computer Support 1 08-26-2006 04:27 AM
Strange memory access error after calling dll Mongoose7 C++ 2 03-08-2006 05:31 PM
Differences between Sony Memory Stick & memory Stick Pro vs Memory Stick Duo? zxcvar Digital Photography 3 11-28-2004 10:48 PM
Question About Strange 'C' Code Syntax ( Well strange to me anyway ) Harvey Twyman C Programming 8 10-25-2003 05:54 AM



Advertisments