generic type, tree

[alternative451]

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

 

[Jens Thoms Toerring]

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

 

[Antoninus Twink]

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

 

[Eligiusz Narutowicz]

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.

 

[Jens Thoms Toerring]

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

 

[Barry Schwarz]

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.

 

[David Resnick]

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

 

[Keith Thompson]

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.

 

[Jens Thoms Toerring]

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