«

I'm sorry for asking such a silly question, but I can't quite get my head
around malloc. Using gcc I have always programmed in a lax C/C++ hybrid
(which I suppose is actually c++). But I have started messing around in Plan
9, and that sort of thing is totally no go there .

Is this correct to allocate memory for my struct? It works on my computer,
but I'm suspicious that I'm doing it wrong.

--

struct NODE;

struct NODE {
char string[80];
struct NODE *next;
}

int main()
{
struct NODE *first;

first = (struct NODE) malloc(sizeof(struct NODE));

first->next = (struct NODE) malloc(sizeof(struct NODE));

free(first);

return 0;
}

Is it necessary to malloc the struct 'first'?

Sorry, I see one error in that code already, there should be a semicolon at
the end of the struct .

Richard Hunt wrote:
> I'm sorry for asking such a silly question, but I can't quite get my head
> around malloc. Using gcc I have always programmed in a lax C/C++ hybrid
> (which I suppose is actually c++). But I have started messing around in Plan
> 9, and that sort of thing is totally no go there .
>
> Is this correct to allocate memory for my struct? It works on my computer,
> but I'm suspicious that I'm doing it wrong.

No, it's not correct. It shouldn't even compile. Here are the
diagnostics I got:

"C:\cygwin\bin\gcc.exe" -W -Wall -Wcast-align -Wwrite-strings
-Wno-sign-compare -Wno-unused-parameter -Wpointer-arith -ansi
-pedantic-errors -ggdb -c fun.c
fun.c:9: error: two or more data types in declaration of `main'
fun.c: In function `main':
fun.c:12: warning: implicit declaration of function `malloc'
fun.c:12: error: conversion to non-scalar type requested
fun.c:14: error: conversion to non-scalar type requested
fun.c:16: warning: implicit declaration of function `free'
Terminated with exit code 1

>
> struct NODE;

This forward declaration is not useful.

>
> struct NODE {
> char string[80];
> struct NODE *next;
> }

fun.c:9: error: two or more data types in declaration of `main'

You missed a semicolon here.

>
> int main()

Prefer 'int main(void)'. "()" and "(void)" mean completely different
things in C.

> {
> struct NODE *first;
>
> first = (struct NODE) malloc(sizeof(struct NODE));

fun.c:12: warning: implicit declaration of function `malloc'

malloc has not been declared, so using it causes it to be implicitly
declared to return 'int'. This is wrong, and causes the behavior to be
undefined.


fun.c:12: error: conversion to non-scalar type requested

You've also cast to the wrong type.

You should probably not cast the return from malloc. It doesn't do
anything useful, makes maintenance more difficult, and can hide errors.
If you had cast to the correct type, and the compiler had not bothered
to warn about the implicit declaration of malloc (it's not required to,
and some don't), then you'd have a silent case of undefined behavior.

Finally, consider using the comp.lang.c-approved malloc idiom:

p = malloc(N * sizeof(*p));

This is less error-prone and more self-maintaining than other idioms.

>
> first->next = (struct NODE) malloc(sizeof(struct NODE));

All the same problems as before, plus undefined behavior (probably
causing a crash) if the first malloc fails.

>
> free(first);

Memory leak. You never freed first->next, and now you have no way to do so.

>
> return 0;
> }
>
> Is it necessary to malloc the struct 'first'?
>

I'm not sure I know what you mean. 'first' is a pointer, not a struct.
It has to be made to point to something if you want it to be useful. A
malloced object is one possible choice.

In the context of this example, you didn't need malloc at all. You could
have done this:

struct NODE first, next;
first.next = next;

-Kevin
--
My email address is valid, but changes periodically.
To contact me please use the address from a recent posting.

On Sun, 28 Dec 2003 18:28:52 -0000, "Richard Hunt" <>
wrote:

>I'm sorry for asking such a silly question, but I can't quite get my head
>around malloc. Using gcc I have always programmed in a lax C/C++ hybrid
>(which I suppose is actually c++). But I have started messing around in Plan
>9, and that sort of thing is totally no go there .
>
>Is this correct to allocate memory for my struct? It works on my computer,
>but I'm suspicious that I'm doing it wrong.
>
>--

You shouldn't use this separator. Many news readers treat everything
below as signature material.

>
>struct NODE;
>
>struct NODE {
> char string[80];
> struct NODE *next;
>}

;

>
>int main()
>{
> struct NODE *first;
>
> first = (struct NODE) malloc(sizeof(struct NODE));

This is a constraint violation. You probably meant the cast to be
(struct NODE*).

In C you should never cast the return from malloc. You should also
#include stdlib.h to insure a prototype is in scope. The preferred C
construct is

first = malloc(sizeof *first)

>
> first->next = (struct NODE) malloc(sizeof(struct NODE));

You ought to compile your code before submitting it.

>
> free(first);

You do realize that this creates a memory leak?

>
> return 0;
>}
>
>Is it necessary to malloc the struct 'first'?

If you don't, will first->next even exist?


<<Remove the del for email>>

"Richard Hunt" <> wrote in message
> I'm sorry for asking such a silly question, but I can't quite get my head
> around malloc. Using gcc I have always programmed in a lax C/C++
> hybrid (which I suppose is actually c++).
>
It's C-like C++. Unless you really know what you doing this has the
disadvantages of C and C++, and the advantages of neither.
>
> struct NODE;
>
Get rid of this.
>
> struct NODE {
> char string[80];
> struct NODE *next;
> }
>
OK.
>
> int main()
> {
> struct NODE *first;
>
> first = (struct NODE) malloc(sizeof(struct NODE));
>
You mean first = (struct NODE *) malloc( sizeof(struct NODE));
or you can just say first = malloc( sizeof(struct NODE));

this means that first now points to an area of memory big enough to contain
one struct NODE. ie 80 bytes plus a few for the pointer.

Now you should check that malloc() has succeeded.
if(first == NULL)
{
fprintf(stderr, "Out of memory\n");
exit(EXIT_FAILURE);
}
>
> first->next = (struct NODE) malloc(sizeof(struct NODE));
>
Imagine we want to create a linked list of N nodes.

(temp is a struct NODE *)
temp = first;
for(i=0;i<N-1;i++)
{
temp->next = malloc(sizeof(NODE));
if(!temp->next)
{
fprintf(stderr, "Out of memory\n");
exit(EXIT_FAILURE);
}
strcpy(temp->next->string, "Empty string");
temp ->next->next = 0;
temp = temp->next;
}
>
> free(first);
>
You must free memory you allocate, in this case both first and first->next.
If you free first then you will orphan first->next.
Generally, when freeing a linked list, free the last member first and then
work upwards.
>
> return 0;
> }
>
> Is it necessary to malloc the struct 'first'?
>
You can create a structure on the stack.

struct NODE first.

If you know how many structures you need in the linked list, you can create
an array

struct NODE list[100].
and then set the nest pointers.

However if the list can contain an arbitrary number of members, then you
need to allocate dynamically.

Sorry everyone, I wrote this example out quickly from memory without any
thought, before I went out. Your advice was useful though, thanks for trying
.

Here's a modified version of the program. I realize that it isn't a sensible
program, sorry. Does this look better?

#include <stdlib.h>

struct NODE;

/*
* This was why I had the forward declaration in the original, sorry
*/

struct interior {
char text[100];
struct NODE *next;
};

struct NODE {
char text[100];
struct interior yes;
struct interior no;
};

int main(int argc, char **argv)
{
struct NODE *first;

first=malloc(sizeof(struct NODE));

first->yes.next=malloc(sizeof(struct NODE));
first->no.next=malloc(sizeof(struct NODE));

/*
* free part skipped, see question
*/

return 0;
}

Assuming that I continue creating further nodes in this tree, what would be
the correct way to free them all? I can't work backwards, because there are
no pointers to earlier in the tree. The example I used for this said that I
could just do free(first). (It also claimed to be a C example, but used the
new keyword.)

I learnt what C I know originally from Illustrating ansi C, because it was
about, and I couldn't afford to get any more books. It isn't very
comprehensive, but I think it's accurate. Shame I lost it.

Richard Hunt wrote:

> Here's a modified version of the program. I realize that it isn't a sensible
> program, sorry. Does this look better?
>
> #include <stdlib.h>
>
> struct NODE;
>
> /*
> * This was why I had the forward declaration in the original, sorry
> */
>
> struct interior {
> char text[100];
> struct NODE *next;
> };
>
> struct NODE {
> char text[100];
> struct interior yes;
> struct interior no;
> };
>
> int main(int argc, char **argv)
> {
> struct NODE *first;
>
> first=malloc(sizeof(struct NODE));

I would still recommend applying 'sizeof' to the object, not the type.
Otherwise you are sacrificing a large part of the benefit of the
clc-approved malloc idiom and making it more error-prone.

first = malloc(sizeof(*first));

OR

first = malloc(sizeof *first);

If you really want to give the type here (for some reason), I wouldn't
use the clc idiom at all. I'd probably do something completely
different, like the following:

#define ALLOC(type) (type *)malloc(sizeof(type))
/* ... */
first = ALLOC(struct NODE);

This will cause a diagnostic if you allocate space for the wrong type,
but still may suppress a useful diagnostic if you forget to #include
<stdlib.h>.

>
> first->yes.next=malloc(sizeof(struct NODE));
> first->no.next=malloc(sizeof(struct NODE));
>
> /*
> * free part skipped, see question
> */
>
> return 0;
> }
>
> Assuming that I continue creating further nodes in this tree, what would be
> the correct way to free them all? I can't work backwards, because there are
> no pointers to earlier in the tree. The example I used for this said that I
> could just do free(first). (It also claimed to be a C example, but used the
> new keyword.)

Then the example was crap. You *must* free() everything you malloc() (or
realloc(), or calloc()). That means each malloc() invocation needs a
corresponding free() invocation (applied to a pointer with the same
value as the pointer returned from malloc()).

[OT: Also, even in C++ where the 'new' keyword exists, you cannot free()
memory allocated with 'new' - you have to use 'delete' with 'new' and
free() with malloc(). And even in C++, you have to match every
invocation of an allocation function (or operator) with an invocation of
the corresponding deallocation function (or operator). Neither C nor C++
require any sort of automatic clean-up of dynamically allocated memory
at any time, even at program termination.]

The way memory is usually freed for a tree is to do a regular old
post-order traversal, freeing as you go. Something like this:

void free_tree(NODE *ptr)
{
if (ptr)
{
free_tree(ptr->left_child);
free_tree(ptr->right_child);
free(ptr);
}
}

-Kevin
--
My email address is valid, but changes periodically.
To contact me please use the address from a recent posting.

> I would still recommend applying 'sizeof' to the object, not the type.
> Otherwise you are sacrificing a large part of the benefit of the
> clc-approved malloc idiom and making it more error-prone.
>
> first = malloc(sizeof(*first));
>
> OR
>
> first = malloc(sizeof *first);

Sorry, I hadn't taken in what you said before, I was too busy trying to come
up with a correct example

> [OT: Also, even in C++ where the 'new' keyword exists, you cannot free()
> memory allocated with 'new' - you have to use 'delete' with 'new' and
> free() with malloc(). And even in C++, you have to match every
> invocation of an allocation function (or operator) with an invocation of
> the corresponding deallocation function (or operator). Neither C nor C++
> require any sort of automatic clean-up of dynamically allocated memory
> at any time, even at program termination.]

Ah, free() instead of delete was probably my memory failing me. But my basic
point was definitely what the example said.

> The way memory is usually freed for a tree is to do a regular old
> post-order traversal, freeing as you go. Something like this:
>
> void free_tree(NODE *ptr)
> {
> if (ptr)
> {
> free_tree(ptr->left_child);
> free_tree(ptr->right_child);
> free(ptr);
> }
> }

Thanks, thats what I wanted. I think I should invest in some decent books,
it's alright me soldiering on slowly in private, but I don't want to waste
any more of other peoples time.

Richard Hunt wrote:
>
.... snip ...
>
> Assuming that I continue creating further nodes in this tree,
> what would be the correct way to free them all? I can't work
> backwards, because there are no pointers to earlier in the tree.
> The example I used for this said that I could just do free(first).
> (It also claimed to be a C example, but used the new keyword.)

Study this elementary example:

#include <stdlib.h>

#define ITEMS 10

struct node {
struct node *next;
int datum;
};

int main(void)
{
struct node *root, *temp;;
int i; /* just a counter */

root = NULL;
for (i = 0; i < ITEMS; i++) {
temp = malloc(sizeof *temp);
if (temp) /* i.e temp != NULL */ {
temp->next = root; /* save previous */
root = temp; /* revise root value */
}
else {
/* malloc failed, bail out, temp == NULL */
return EXIT_FAILURE;
}
}
/* now we have allocated 10 nodes, the last of which
is pointed to by root, and each nodes next pointer
points to an earlier node, or is NULL at the end */

/* free them all */
while {root) /* i.e. while (root != NULL) */
temp = root->next; /* won't be available after free */
free(root);
root = temp; /* and see if at the end */
}
return 0;
} /* main untested */

Note that datum has never been used. Most of the comments are not
normally necessary, but I added them to clarify what things were
about to you.

After that is perfectly clear, see if you can create a binary
tree. Then consider ways to walk it, known as preorder, inorder,
and postorder. The sort of node you will want will be something
like:

struct node {
struct node *left, *right;
int datum;
};

Draw pictures with boxes representing nodes and lines representing
pointers. Don't forget that NULL points nowhere.

--
Chuck F () ()
Available for consulting/temporary embedded and systems.
<http://cbfalconer.home.att.net> USE worldnet address!