Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C Programming > generic type, tree

Reply
Thread Tools

generic type, tree

 
 
alternative451@gmail.com
Guest
Posts: n/a
 
      05-18-2008
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
 
Reply With Quote
 
 
 
 
Jens Thoms Toerring
Guest
Posts: n/a
 
      05-18-2008
http://www.velocityreviews.com/forums/(E-Mail Removed) 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 ___ (E-Mail Removed)
\__________________________ http://toerring.de
 
Reply With Quote
 
 
 
 
Antoninus Twink
Guest
Posts: n/a
 
      05-18-2008
On 18 May 2008 at 10:46, Jens Thoms Toerring wrote:
> (E-Mail Removed) 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.)

 
Reply With Quote
 
Eligiusz Narutowicz
Guest
Posts: n/a
 
      05-18-2008
Antoninus Twink <(E-Mail Removed)> writes:

> On 18 May 2008 at 10:46, Jens Thoms Toerring wrote:
>> (E-Mail Removed) 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.

 
Reply With Quote
 
Jens Thoms Toerring
Guest
Posts: n/a
 
      05-18-2008
Eligiusz Narutowicz <(E-Mail Removed)> wrote:
> Antoninus Twink <(E-Mail Removed)> writes:


> > On 18 May 2008 at 10:46, Jens Thoms Toerring wrote:
> >> (E-Mail Removed) 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 ___ (E-Mail Removed)
\__________________________ http://toerring.de
 
Reply With Quote
 
Barry Schwarz
Guest
Posts: n/a
 
      05-19-2008
On May 18, 2:50*am, (E-Mail Removed) 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.
 
Reply With Quote
 
David Resnick
Guest
Posts: n/a
 
      05-19-2008
On May 18, 4:54 pm, (E-Mail Removed) (Jens Thoms Toerring) wrote:
> Eligiusz Narutowicz <(E-Mail Removed)> wrote:
> > Antoninus Twink <(E-Mail Removed)> writes:
> > > On 18 May 2008 at 10:46, Jens Thoms Toerring wrote:
> > >> (E-Mail Removed) 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
 
Reply With Quote
 
Keith Thompson
Guest
Posts: n/a
 
      05-19-2008
Barry Schwarz <(E-Mail Removed)> writes:
> On May 18, 2:50*am, (E-Mail Removed) 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) (E-Mail Removed) <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"
 
Reply With Quote
 
Jens Thoms Toerring
Guest
Posts: n/a
 
      05-19-2008
David Resnick <(E-Mail Removed)> wrote:
> On May 18, 4:54 pm, (E-Mail Removed) (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 ___ (E-Mail Removed)
\__________________________ http://toerring.de
 
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
not just generic type programming,but also parallism generic syntaxprogramming?? minlearn C++ 2 03-13-2009 05:17 PM
generic interfaces with generic methods Murat Tasan Java 1 02-03-2009 12:17 PM
Generic class in a non generic class nramnath@gmail.com Java 2 07-04-2006 07:24 AM
B tree, B+ tree and B* tree Stub C Programming 3 11-12-2003 01:51 PM
generic tree pathfinding Nevyn C++ 2 08-14-2003 09:26 AM



Advertisments