generic type, tree

Discussion in 'C Programming' started by alternative451@gmail.com, May 18, 2008.

  1. Guest

    hi, I having some problem with a void * and tree structure.
    i am sure tha my fuction make tree is ok, but my fuction print return
    adress instead of values.

    Main :

    int main()
    {
    node *n = init(5);
    affiche(n);
    return 0;
    }

    structure :

    typedef struct node
    {
    void *value;
    struct node* right;
    struct node* left;
    }node;

    init :

    node* init(int h)
    {
    if(h == 0)
    return NULL;
    int v = 1;
    node *n = malloc(sizeof(node));
    n->value = &v;
    printf("->%d \t", *((int*)n->value));
    n->right = init(h-1);
    n->left = init(h-1);

    return n;
    }
    print :
    void affiche(node *n)
    {
    if(n != NULL)
    {
    int *v = (int*)n->value;
    affiche(n->left);
    printf("-->%d \t",*v);
    affiche(n->right);

    }
    }

    the problem is not in the fuction init, because the fuction printf
    return good values.
    i think it was in the fuction "affiche"
    please help me, thanks
     
    , May 18, 2008
    #1
    1. Advertising

  2. wrote:
    > hi, I having some problem with a void * and tree structure.
    > i am sure tha my fuction make tree is ok, but my fuction print return
    > adress instead of values.


    > Main :


    > int main()
    > {
    > node *n = init(5);
    > affiche(n);
    > return 0;
    > }


    > structure :


    > typedef struct node
    > {
    > void *value;
    > struct node* right;
    > struct node* left;
    > }node;


    > init :


    > node* init(int h)
    > {
    > if(h == 0)
    > return NULL;
    > int v = 1;
    > node *n = malloc(sizeof(node));
    > n->value = &v;


    Here you have a bad problem. What you store in the 'value' member
    is a pointer to a variable that vanishes the moment you return
    from this function. So any accesses to the 'value' member made
    once you have returned invokes undefined behaviour and what
    'value' points to rather likely has been overwritten by some
    other value.

    The only way to avoid that would be

    int *v = malloc( sizeof *v );
    *v = 1;
    n->value = v;

    since only that will give you a pointer to memory that you
    still "own" after you returned from the function and will
    keep the value you wrote to it.

    > printf("->%d \t", *((int*)n->value));
    > n->right = init(h-1);
    > n->left = init(h-1);


    > return n;
    > }

    Regards, Jens
    --
    \ Jens Thoms Toerring ___
    \__________________________ http://toerring.de
     
    Jens Thoms Toerring, May 18, 2008
    #2
    1. Advertising

  3. On 18 May 2008 at 10:46, Jens Thoms Toerring wrote:
    > wrote:
    >> int v = 1;
    >> node *n = malloc(sizeof(node));
    >> n->value = &v;

    >
    > Here you have a bad problem. What you store in the 'value' member
    > is a pointer to a variable that vanishes the moment you return
    > from this function.


    You're right, but perhaps it will also be helpful to mention to the OP
    that tracking down such bugs is very easy using the valgrind tool, which
    will pick up invalid memory accesses like this. (This is just in case
    the OP isn't a preternaturally talented programmer like all the clc
    regulars, who as we know have no need for debugging tools besides their
    eyes.)
     
    Antoninus Twink, May 18, 2008
    #3
  4. Antoninus Twink <> writes:

    > On 18 May 2008 at 10:46, Jens Thoms Toerring wrote:
    >> wrote:
    >>> int v = 1;
    >>> node *n = malloc(sizeof(node));
    >>> n->value = &v;

    >>
    >> Here you have a bad problem. What you store in the 'value' member
    >> is a pointer to a variable that vanishes the moment you return
    >> from this function.

    >
    > You're right, but perhaps it will also be helpful to mention to the OP
    > that tracking down such bugs is very easy using the valgrind tool, which
    > will pick up invalid memory accesses like this. (This is just in case
    > the OP isn't a preternaturally talented programmer like all the clc
    > regulars, who as we know have no need for debugging tools besides their
    > eyes.)


    If the OP is using Linux (or Windows too I think) then splint is also
    quite good. I got the link from this group I think.
     
    Eligiusz Narutowicz, May 18, 2008
    #4
  5. Eligiusz Narutowicz <> wrote:
    > Antoninus Twink <> writes:


    > > On 18 May 2008 at 10:46, Jens Thoms Toerring wrote:
    > >> wrote:
    > >>> int v = 1;
    > >>> node *n = malloc(sizeof(node));
    > >>> n->value = &v;
    > >>
    > >> Here you have a bad problem. What you store in the 'value' member
    > >> is a pointer to a variable that vanishes the moment you return
    > >> from this function.

    > >
    > > You're right, but perhaps it will also be helpful to mention to the OP
    > > that tracking down such bugs is very easy using the valgrind tool, which
    > > will pick up invalid memory accesses like this. (This is just in case
    > > the OP isn't a preternaturally talented programmer like all the clc
    > > regulars, who as we know have no need for debugging tools besides their
    > > eyes.)


    > If the OP is using Linux (or Windows too I think) then splint is also
    > quite good. I got the link from this group I think.


    While splint indeed gives you some hint at what's going wrong
    (alas in a way that probably will make it hard for the OP to
    grasp) using valgrind seems to me like looking for your mis-
    placed keys with a microscope. All it tells you is something
    about an invalid read in the affiche() function, rather likely
    just reinforcing the OP in the wrong belive that there would
    be something wrong with this function and not helping at all
    in finding the real reason for the problem. I would recommend
    to use valgrind (or similar memory debuggers) only as a last
    resort and instead to learn to avoid such mistakes since val-
    grind can only detect the results of those mistakes, not the
    mistakes themselves.
    Regards, Jens
    --
    \ Jens Thoms Toerring ___
    \__________________________ http://toerring.de
     
    Jens Thoms Toerring, May 18, 2008
    #5
  6. On May 18, 2:50 am, wrote:
    > hi, I having some problem with a void * and tree structure.
    > i am sure tha my fuction make tree is ok, but my fuction print return
    > adress instead of values.
    >
    > Main :
    >
    > int main()
    > {
    >         node *n = init(5);


    This should have produced a diagnostic. There is no prototype in
    scope for init so the compiler is obligated to assume it returns an
    int. There is no implicit conversion between int a pointer to node.
    Since init does not return an int, you also have undefined behavior.

    It doesn't help that node is an unknown type at this point also.


    >         affiche(n);
    >         return 0;
    >
    > }
    >
    > structure :
    >
    > typedef struct node
    > {
    >         void *value;
    >         struct node* right;
    >         struct node* left;
    >
    > }node;
    >
    > init :
    >
    > node* init(int h)
    > {
    >         if(h == 0)
    >                 return NULL;
    >         int v = 1;
    >         node *n = malloc(sizeof(node));


    No prototype for malloc either causing the same problems.

    >         n->value = &v;


    v is an automatic variable. It will cease to exist when init returns
    to main. Once that happens, the value in n->value becomes
    indeterminate and any attempt to evaluate it for any purpose causes
    undefined behavior.

    >         printf("->%d \t", *((int*)n->value));
    >         n->right = init(h-1);
    >         n->left = init(h-1);
    >
    >         return n;}
    >
    > print :
    > void affiche(node *n)
    > {
    >         if(n != NULL)
    >         {
    >                 int *v = (int*)n->value;


    Here is the undefined behavior mentioned above.

    >                 affiche(n->left);
    >                 printf("-->%d \t",*v);
    >                 affiche(n->right);
    >
    >         }
    >
    > }
    >
    > the problem is not in the fuction init, because the fuction printf
    > return good values.


    One of the worst manifestations of undefined behavior is to appear to
    do what is expected. Your design for init is faulty and is the cause
    of at least some of the problems you are experiencing. If you told us
    what those problems were, we might be able to offer better advice.

    > i think it was in the fuction "affiche"


    The undefined behavior occurs in affiche because of the poor design of
    init.
     
    Barry Schwarz, May 19, 2008
    #6
  7. On May 18, 4:54 pm, (Jens Thoms Toerring) wrote:
    > Eligiusz Narutowicz <> wrote:
    > > Antoninus Twink <> writes:
    > > > On 18 May 2008 at 10:46, Jens Thoms Toerring wrote:
    > > >> wrote:
    > > >>> int v = 1;
    > > >>> node *n = malloc(sizeof(node));
    > > >>> n->value = &v;

    >
    > > >> Here you have a bad problem. What you store in the 'value' member
    > > >> is a pointer to a variable that vanishes the moment you return
    > > >> from this function.

    >
    > > > You're right, but perhaps it will also be helpful to mention to the OP
    > > > that tracking down such bugs is very easy using the valgrind tool, which
    > > > will pick up invalid memory accesses like this. (This is just in case
    > > > the OP isn't a preternaturally talented programmer like all the clc
    > > > regulars, who as we know have no need for debugging tools besides their
    > > > eyes.)

    > > If the OP is using Linux (or Windows too I think) then splint is also
    > > quite good. I got the link from this group I think.

    >
    > While splint indeed gives you some hint at what's going wrong
    > (alas in a way that probably will make it hard for the OP to
    > grasp) using valgrind seems to me like looking for your mis-
    > placed keys with a microscope. All it tells you is something
    > about an invalid read in the affiche() function, rather likely
    > just reinforcing the OP in the wrong belive that there would
    > be something wrong with this function and not helping at all
    > in finding the real reason for the problem. I would recommend
    > to use valgrind (or similar memory debuggers) only as a last
    > resort and instead to learn to avoid such mistakes since val-
    > grind can only detect the results of those mistakes, not the
    > mistakes themselves.


    While I don't often agree with Mr. Twink, but I think that (assuming
    the OP is using Linux, of which I can see absolutely no hint in his
    post) using valgrind early and often is a good thing. Even on
    programs that seem to work. I added it to our large regression suite
    a while back at work and found a number of defects that way that had
    not been otherwise noticed. They were of the class of things (e.g.
    off by one errors causing invalid memory reads/writes) that can cause
    difficult to diagnose at the customer site memory corruptions, but
    often aren't detected in unit testing... I'm thus a big fan of using
    valgrind (and in the past purify) at any stage of development...

    I also agree with your point to some degree, that being able to find
    these things by eye is a good thing. A competent code inspector
    should be able to catch return of automatic memory (or putting it into
    a struct that is returned).

    -David
     
    David Resnick, May 19, 2008
    #7
  8. Barry Schwarz <> writes:
    > On May 18, 2:50 am, wrote:
    >> hi, I having some problem with a void * and tree structure.
    >> i am sure tha my fuction make tree is ok, but my fuction print return
    >> adress instead of values.
    >>
    >> Main :
    >>
    >> int main()
    >> {
    >>         node *n = init(5);

    >
    > This should have produced a diagnostic. There is no prototype in
    > scope for init so the compiler is obligated to assume it returns an
    > int. There is no implicit conversion between int a pointer to node.
    > Since init does not return an int, you also have undefined behavior.
    >
    > It doesn't help that node is an unknown type at this point also.


    Not necessarily. The OP presented the code in multiple chunks, with
    no indication of the order in which they appear, or even whether
    they're in the same source file. For example, the "Main :" above
    clearly isn't part of the code.

    Unless the OP was posting code that failed to compile, we can assume
    that the identifier "node" is visible.

    To the original poster: Whenever possible, it's best to post an exact
    copy-and-paste of a single translation unit (source file). If you
    need to post multiple source files, each one should be clearly
    labeled. You've already done the work of getting all these chunks
    into the right order; don't make us do that work all over again.

    --
    Keith Thompson (The_Other_Keith) <http://www.ghoti.net/~kst>
    Nokia
    "We must do something. This is something. Therefore, we must do this."
    -- Antony Jay and Jonathan Lynn, "Yes Minister"
     
    Keith Thompson, May 19, 2008
    #8
  9. David Resnick <> wrote:
    > On May 18, 4:54 pm, (Jens Thoms Toerring) wrote:
    > > While splint indeed gives you some hint at what's going wrong
    > > (alas in a way that probably will make it hard for the OP to
    > > grasp) using valgrind seems to me like looking for your mis-
    > > placed keys with a microscope. All it tells you is something
    > > about an invalid read in the affiche() function, rather likely
    > > just reinforcing the OP in the wrong belive that there would
    > > be something wrong with this function and not helping at all
    > > in finding the real reason for the problem. I would recommend
    > > to use valgrind (or similar memory debuggers) only as a last
    > > resort and instead to learn to avoid such mistakes since val-
    > > grind can only detect the results of those mistakes, not the
    > > mistakes themselves.


    > While I don't often agree with Mr. Twink, but I think that (assuming
    > the OP is using Linux, of which I can see absolutely no hint in his
    > post) using valgrind early and often is a good thing. Even on
    > programs that seem to work. I added it to our large regression suite
    > a while back at work and found a number of defects that way that had
    > not been otherwise noticed. They were of the class of things (e.g.
    > off by one errors causing invalid memory reads/writes) that can cause
    > difficult to diagnose at the customer site memory corruptions, but
    > often aren't detected in unit testing... I'm thus a big fan of using
    > valgrind (and in the past purify) at any stage of development...


    > I also agree with your point to some degree, that being able to find
    > these things by eye is a good thing. A competent code inspector
    > should be able to catch return of automatic memory (or putting it into
    > a struct that is returned).


    I hope I didn't give the impression that I would be somehow
    opposed to using valgrind and similar programs. I use it my-
    self for exactly the purpose you describe, i.e. finding de-
    fects and, if I am lucky, getting some hints what kind of
    problem I have to look for. But what it's not IMHO is an all-
    purpose debugging tool in the sense "write some code, run it
    through valgrind and if it doesn't complain everything is
    fine, otherwise it tells me where to look". It isn't that
    already because to find the mistake one made from what val-
    grind outputs can be a rater lengthy process, often not much
    simpler than getting from e.g. a segmentation fault to the
    exact place where the logical error in the program is. And
    it isn't such an all-purpose debugging tool also since it
    can only collect data from the parts of a program that have
    actually been executed in the test run - running through each
    and every possible path in a program can be nearly impossible.

    I find it rather problematic to recommend valgrind to a relative
    beginner in C programming. To be able to get something out of
    the defects valgrind flags one needs to have at least some aware-
    ness of the errors one can make. And I doubt very much that
    someone who can't debug a <=50 lines program by eye has any
    realistic chance of making head or tail of the output of val-
    grind. The OP's program output clearly showed that there was a
    severe problem and the only information valgrind in this case
    adds is that there is an invalid read, but at a place that's
    not the one where the principal problem is. Since I have a bit
    of experience with C programming and (much too much:) with
    debugging all I would conclude from it is that I made a mistake
    somewhere in the program, using already deallocated memory, ha-
    ving passed back a pointer to a non-static, local variable etc.
    And I know that the mistake can be at a completely different
    place from the one where valgrind found the defect and thus would
    not concentrate my attention unnecessarily to just this place. On
    the other hand, someone relatively new to programming in C will
    rather likely have problems understanding what "invalid read"
    actually signifies and assume that the problem is somewhere near
    to where valgrind found the defect, spending lots of time looking
    for bugs that don't exist. That's at least the conclusion I draw
    from my own learning of how to debug and observing what other
    people struggle with.
    Regards, Jens
    --
    \ Jens Thoms Toerring ___
    \__________________________ http://toerring.de
     
    Jens Thoms Toerring, May 19, 2008
    #9
    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. Murat Tasan
    Replies:
    1
    Views:
    8,071
    Chaitanya
    Feb 3, 2009
  2. Stub

    B tree, B+ tree and B* tree

    Stub, Nov 12, 2003, in forum: C Programming
    Replies:
    3
    Views:
    10,175
  3. minlearn
    Replies:
    2
    Views:
    464
    red floyd
    Mar 13, 2009
  4. Daniel Thoma
    Replies:
    12
    Views:
    1,991
    markspace
    Jul 31, 2009
  5. Noah Roberts
    Replies:
    1
    Views:
    397
    Noah Roberts
    Mar 15, 2010
Loading...

Share This Page