Pointers to struct

[l-o-s-t]

If I have this struct :

typedef struct node {
  int         key;
  struct node *leftp;
  struct node *rightp;
} *Treep;

and I have this function

int blah (Treep *tree);

How can I pass the tree right pointer again into the blah function, I tried using blah ( tree -> rightp ), but it doesn't work, any help on how to do this ? :o

Thanks in advance

[Clinton Portis]

int blah (Treep *tree);

I think the data type you are attempting to pass is incorrect.. you should be passing in an object of type, "node"

int blah (node *tree);

please post compiler errors for more assistance.

[l-o-s-t]

Thanks, but the arguments of the function is right, however what I am having trouble with is this, the function is recursive, and when I use blah( tree -> rightp ) the compiler raise this error :

blah.c:35: error: request for member `rightp' in something not a structure or union

How I am I supposed to pass the argument of blah ?

[Narue]

>I tried using blah ( tree -> rightp )
Why? tree->rightp is a node*, but the function expects a node** because you typedef'd Treep to be a node*, and blah asks for a Treep*. The progression is like this:

Treep becomes struct node*
so
Treep* becomes struct node**

So you should be calling blah like this:

blah ( &tree->rightp )

Your confusion on this point suggests that you shouldn't be hiding a level of indirection behind a typedef. Declare your struct as:

typedef struct node {
  int         key;
  struct node *leftp;
  struct node *rightp;
} Tree;

And then you'll know that Tree* is the same as node*, and Tree** is the same as node**. Hiding levels of indirection is a bad practice anyway because it confuses so many people.

[l-o-s-t]

Thanks Narue :)

you shouldn't be hiding a level of indirection behind a typedef

I would have declared it in the way u suggested, however I was meant to be using the struct and the prototype of blah as defined in the lab specification.

Thanks again

[Narue]

>I was meant to be using the struct and the prototype of blah as defined in the lab specification.
As usual, I invite your instructor to come here and get schooled about why his code is a bad idea. ;)

[l-o-s-t]

I invite your instructor to come here and get schooled about why his code is a bad idea. ;)

I wish, this guy has a funny way of teaching things, and like to make things as complicated as possible, he is good at giving hideous assignments and lab work, provided with unclear specifications, and no test data *sigh*

[beuls]

I think this will work fine.

[code]
typedef struct node {
int key;
struct node *leftp;
struct node *rightp;
} *Treep;

void blah(node *tree)
{

}
[code]

[Narue]

>I think this will work fine.
You thought wrong. As I so carefully described, node* and Treep* are different types because Treep hides a level of indirection. Your suggestion fails for three very good reasons:

1) The function is an instructor provided function that cannot be modified.
2) You would change the functionality of the code (see below).
3) The function would be a no-op after your change (see below).

The functionality of the code would be changed because the blah function expects a node**, but you end up passing it a node*. This would cause the compiler to complain, and in your infinite wisdom, you would probably change the contents of blah to work with a node*, thus leading you to the next problem.

When working with self-referential data structures like a binary search tree, you need some way to return the modified structure of the tree back to the calling function. My preferred method is to return a pointer to the new tree:

struct node *blah ( struct node *tree );

But an alternative method is to pass a pointer to the pointer so that changes are saved because you have access to the original pointer and not just a copy of it. This way you can return a status code:

int blah ( struct node **tree );

Does that look familiar? If not, try this, it's equivalent:

typedef struct node *Treep;
int blah ( Treep *tree );

The extra level of indirection is thusrequired for changes made to the tree (assuming that blah modifies the tree) to be saved outside of the function. Your suggestion removes that level of indirection, which changes the logic of the code and breaks it.

Don't think. Test. If you don't know, don't post until you do.

[l-o-s-t]

I am trying to allocate memory for tree pointer, in the blah function, by doing this :

*tree = ( Treep * ) malloc ( sizeof ( Treep )  ) ;

However, the compiler gives this error

blah.c:88: warning: assignment from incompatible pointer type

but it works fine if I use

typedef struct node {
  int         key;
  struct node *leftp;
  struct node *rightp;
} *Treep;

int blah (Treep **tree);

Everything works fine, why is this ? how am I supposed to allocate memory for the first case ?

Thanks

[Narue]

>*tree = ( Treep * ) malloc ( sizeof ( Treep ) ) ;
I'll assume you're using C. There's no need to cast the return value of malloc because pointers are implicitly converted to and from void*. It's also a better practice to not use sizeof(Treep) explicitly because it makes maintenance harder if you change types or type names. The accepted way to allocate memory is:

*tree = malloc ( sizeof **tree );

By taking the sizeof the dereferenced pointer that you're assigning to, you get the size of the object you want no matter what it is. Because sizeof doesn't evaluate the expression, the dereference is safe. Without the extra level of indirection, it looks like this:

p = malloc ( sizeof *p );

The first code also fixes your problem if I've guessed it correctly. I imagine that because tree is a pointer to Treep and and thus, a node**, your cast was incorrect because it was trying to assign a pointer to Treep to a Treep since you were dereferencing tree. Which results in trying to assign a node** to a node*; a case of mismatched levels of indirection again, probably caused by that stupid typedef.

[l-o-s-t]

Thanks again Narue, you've been so helpfull, it makes sense now, and works fine :)