Strange error of memory

Discussion in 'C Programming' started by sylsau, Nov 20, 2005.

  1. sylsau

    sylsau Guest

    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.
    sylsau, Nov 20, 2005
    #1
    1. Advertising

  2. sylsau

    Guest

    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));
    , Nov 21, 2005
    #2
    1. Advertising

  3. sylsau

    pete Guest

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


    Post the whole program.

    --
    pete
    pete, Nov 21, 2005
    #3
  4. sylsau

    pete Guest

    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
    pete, Nov 21, 2005
    #4
  5. "" <> 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) <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.
    Keith Thompson, Nov 21, 2005
    #5
  6. sylsau

    sylsau Guest

    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;
    }
    sylsau, Nov 21, 2005
    #6
  7. 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);
    >
    > 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
    David Resnick, Nov 21, 2005
    #7
  8. sylsau

    pete Guest

    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
    pete, Nov 22, 2005
    #8
  9. sylsau

    Ben Pfaff Guest

    pete <> 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.
    Ben Pfaff, Nov 22, 2005
    #9
  10. sylsau

    pete Guest

    Ben Pfaff wrote:
    >
    > pete <> 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
    pete, Nov 22, 2005
    #10
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Jan
    Replies:
    2
    Views:
    1,413
    Mike Treseler
    Dec 16, 2004
  2. Harvey Twyman
    Replies:
    8
    Views:
    547
    August Derleth
    Oct 25, 2003
  3. Mongoose7
    Replies:
    2
    Views:
    393
    Kaz Kylheku
    Mar 8, 2006
  4. Todd
    Replies:
    4
    Views:
    519
    Jeff Higgins
    Sep 5, 2007
  5. francesco

    Strange error when reallocating memory

    francesco, Dec 22, 2012, in forum: C Programming
    Replies:
    18
    Views:
    524
    army1987
    Dec 27, 2012
Loading...

Share This Page