freeing simple linked list

[disco]

I am working on this example from a book "C Primer Plus" by Prata 4th
edition - p. 672. There is no erata on this problem at the publisher's
website.

1) Is it a violation of copyright laws to post example code from a
book to a newsgroup?

2) The program crashes as it tries to free memory and I would like to
know the best way to correct THIS section of the code. By assigning
current = head, current now points to the first structure in the
linked list. By freeing the first structure it frees all of the other
structures in the linked list below it. As a result, why isn't
current == NULL now ?

3) Is the author assigning current = current->next to make sure
everything gets freed? It seems unecessary.

Thanks,
disco

problem section:
/* Program is done, so free allocated memory */
current = head;
while (current != NULL)
{
free(current);
current = current->next;
}
printf("Bye!\n");

entire program:
/* Films2.c -- using a linked list of structures */
#include <stdio.h>
#include <stdlib.h> /* contains the malloc prototype */
#include <string.h> /* contains the strcpy prototype */
#define TSIZE 45 /* size of array to hold title */

struct film
{
char title[TSIZE];
int rating;
struct film *next; /* points to next struct in list */
};

int main (void)
{
struct film *head = NULL;
struct film *prev, *current;
char input[TSIZE];

printf("Enter first movie title:");
while (gets(input) !=NULL && input[0] != '\0')
{
current = (struct film*) malloc(sizeof(struct film));

if (head == NULL) /* first structure */
head = current;
else /* subsequent structures */
prev->next = current;

current->next = NULL;

strcpy(current->title, input);
printf("Enter your rating [0 to 10]: ");
scanf("%d", &current->rating);
while (getchar() != '\n')
continue;
printf("Please enter next movie title [enter to end]: ");
prev = current;
}

if (head == NULL)
printf("No data entered. ");
else
printf("Here is the movie list: \n");

current = head;

while (current != NULL)
{
printf("Movie: %s -- Rating: %d\n", current->title,
current->rating);
current = current->next;
}

/* Program is done, so free allocated memory */
current = head;
while (current != NULL)
{
free(current);
/* current = current->next; */
}
printf("Bye!\n");

return 0;
}

[Martin Dickopp]

jp********@hotmail.com (disco) writes:

I am working on this example from a book "C Primer Plus" by Prata 4th
edition - p. 672. There is no erata on this problem at the publisher's
website.

1) Is it a violation of copyright laws to post example code from a
book to a newsgroup?
Unless you have a license to post the material, you can only legally do so
under "fair use" provisions. What constitutes "fair use" varies between
different contries, and many contries don't have an exact definition in
the law, but leave it up to the courts to decide if some use is "fair".
2) The program crashes as it tries to free memory and I would like to
know the best way to correct THIS section of the code. By assigning
current = head, current now points to the first structure in the
linked list. By freeing the first structure it frees all of the other
structures in the linked list below it.
No, freeing the head does not automatically free all the other nodes.
As a result, why isn't current == NULL now ?
Passing a pointer to the `free' function frees the memory pointed to, but
doesn't change the value of the pointer itself. The latter would be
impossible as function arguments are always passed by value in C. Therefore,
`free' cannot modify the pointer value.

So you end up with an invalid pointer (it doesn't point to a valid memory
address any longer), but not a null pointer.
3) Is the author assigning current = current->next to make sure
everything gets freed? It seems unecessary.
It is necessary to free the whole list, which must be done node by
node. However, the way the author does this is incorrect.
/* Program is done, so free allocated memory */
current = head;
while (current != NULL)
{
free(current);
current = current->next;
}

It causes undefined behavior to dereference `current' (as in
`current->next') after it has been passed to `free'. The correct way
is to record a pointer to the next node in a temporary variable
/before/ the current node is freed:

current = head;
while (current != NULL)
{
struct node *const next_node = current->next;

free (current);
current = next_node;
}

Martin

[Richard Heathfield]

disco wrote:

I am working on this example from a book "C Primer Plus" by Prata 4th
edition - p. 672. There is no erata on this problem at the publisher's
website.

1) Is it a violation of copyright laws to post example code from a
book to a newsgroup?
It probably comes under "fair use" if you don't overdo it.
2) The program crashes as it tries to free memory and I would like to
know the best way to correct THIS section of the code. By assigning
current = head, current now points to the first structure in the
linked list. By freeing the first structure it frees all of the other
structures in the linked list below it. As a result, why isn't
current == NULL now ?

3) Is the author assigning current = current->next to make sure
everything gets freed? It seems unecessary.

Thanks,
disco

problem section:
/* Program is done, so free allocated memory */
current = head;
while (current != NULL)
{
free(current);
current = current->next;

Undefined behaviour. Having freed current, you have no right to use its
value.

Here's how it should be done:

while(current != NULL)
{
tmp = current; /* tmp needs to be a pointer of the same type as current */
current = current->next;
free(tmp);
}

The error is a simple one. If there are many such errors, it calls the value
of the book into question.

--
Richard Heathfield : bi****@eton.powernet.co.uk
"Usenet is a strange place." - Dennis M Ritchie, 29 July 1999.
C FAQ: http://www.eskimo.com/~scs/C-faq/top.html
K&R answers, C books, etc: http://users.powernet.co.uk/eton

[CBFalconer]

Malcolm wrote:

.... snip ...
The way to do it is using a recursive function.

void freelist(struct film *ptr)
{
if(ptr->next)
freelist(ptr->next);
free(ptr);
}

If you don't want recursion you can write a somewhat faster
iterative routine with two pointers.

Which is probably wise, since lists can be arbitrarily long. At
any rate, your solution fails if called with a NULL ptr. For a
recursive solution better might be:

void freelist(void *ptr)
{
struct film *tmp = ptr;

if (tmp) {
freelist(tmp->next);
free(ptr);
}
}

which can work with various arrangements of the struct.

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

[CBFalconer]

CBFalconer wrote:

Malcolm wrote:

... snip ...

The way to do it is using a recursive function.

void freelist(struct film *ptr)
{
if(ptr->next)
freelist(ptr->next);
free(ptr);
}

If you don't want recursion you can write a somewhat faster
iterative routine with two pointers.

Which is probably wise, since lists can be arbitrarily long. At
any rate, your solution fails if called with a NULL ptr. For a
recursive solution better might be:

void freelist(void *ptr)
{
struct film *tmp = ptr;

if (tmp) {
freelist(tmp->next);
free(ptr);
}
}

which can work with various arrangements of the struct.

Of course it is rather silly for simple lists. But a variant
handles binary trees nicely:

void freetree(void *ptr)
{
struct film *tmp = ptr;

if (tmp) {
freetree(tmp->left);
freetree(tmp->right);
free(ptr);
}
}

since the recursion depth is usually logarithmic in tree size.

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

[disco]

Richard Heathfield <do******@address.co.uk.invalid> wrote in message news:<bi**********@hercules.btinternet.com>...

Undefined behaviour. Having freed current, you have no right to use its
value.

Here's how it should be done:

while(current != NULL)
{
tmp = current; /* tmp needs to be a pointer of the same type as current */
current = current->next;
free(tmp);
}

The error is a simple one. If there are many such errors, it calls the value
of the book into question.

Thank you everyone for your feedback. It was very informative and
helpful.

I have found this book very helpful, both as a reference and a
tutorial, given my particular experience and requirements to use C.
Has anyone else used it or had problems with it?

Thanks again,
disco