Question on free() ing a hash table

[Chad]

Excercise 6-5

Write a functon undef that will remove a name and defintion from the
table maintained by lookup and install.

Code:

unsigned hash(char *s);

void undef(char *s)
{
int h;
struct nlist *prev, *np;

prev = NULL;
h = hash(s);
for(np = hashtab[h]; np!=NULL; np = np->next){
if(strcmp(s, np->name) == 0)
break;
prev = np;
}

if(np !=NULL) {
if(prev == NULL)
hashtab[h] = np->next;
else
prev->next = np->next;
free((void *) np->name);
free((void *) np->defn);
free((void *) np);
}
}

The question is, how come I have to free() both np->name and np->defn?
Ie, how come I can't just free() np?

 

[santosh]

Excercise 6-5

Write a functon undef that will remove a name and defintion from the
table maintained by lookup and install.

Code:

unsigned hash(char *s);

void undef(char *s)
{
int h;
struct nlist *prev, *np;

prev = NULL;
h = hash(s);
for(np = hashtab[h]; np!=NULL; np = np->next){
if(strcmp(s, np->name) == 0)
break;
prev = np;
}

if(np !=NULL) {
if(prev == NULL)
hashtab[h] = np->next;
else
prev->next = np->next;
free((void *) np->name);
free((void *) np->defn);
free((void *) np);
}
}

The question is, how come I have to free() both np->name and np->defn?
Ie, how come I can't just free() np?

Because memory for them was allocated separately.
You need a call to free() for every call to malloc(). You construct the
struct np with three calls to malloc - one for the struct itself and
two more to initialise it's members 'name' and 'defn' to point to
usable storage. Thus when destroying the struct you need to deallocate
storage pointed to by these members too.

In particular if 'name' and 'defn' are the only pointers that point to
their storage, then you must free() them _before_ calling free() on np,
or else you'll create a memory leak.

Note that the casts to void * within the calls to free() are not needed.

 

[Chad]

Excercise 6-5

Write a functon undef that will remove a name and defintion from the
table maintained by lookup and install.

unsigned hash(char *s);

void undef(char *s)
{
int h;
struct nlist *prev, *np;

prev = NULL;
h = hash(s);
for(np = hashtab[h]; np!=NULL; np = np->next){
if(strcmp(s, np->name) == 0)
break;
prev = np;
}

if(np !=NULL) {
if(prev == NULL)
hashtab[h] = np->next;
else
prev->next = np->next;
free((void *) np->name);
free((void *) np->defn);
free((void *) np);
}
}

The question is, how come I have to free() both np->name and np->defn?
Ie, how come I can't just free() np?

Because memory for them was allocated separately.
You need a call to free() for every call to malloc(). You construct the
struct np with three calls to malloc - one for the struct itself and
two more to initialise it's members 'name' and 'defn' to point to
usable storage. Thus when destroying the struct you need to deallocate
storage pointed to by these members too.

In particular if 'name' and 'defn' are the only pointers that point to
their storage, then you must free() them _before_ calling free() on np,
or else you'll create a memory leak.

Note that the casts to void * within the calls to free() are not needed.

The question was taken from page 145 in the "The C Programming
Langauge" by K & R. I think what is tripping me up when trying to free
the structure is the following line of code on page 145.

In install(), they have the following line of code:

if((np->defn = strdup(defn)) == NULL)
return NULL.

For reasons that still elude me, every time I see this line of code, I
keep thinking that memory ISN'T allocated for np->defn.

 

[Chad]

Excercise 6-5

Write a functon undef that will remove a name and defintion from the
table maintained by lookup and install.

unsigned hash(char *s);

void undef(char *s)
{
int h;
struct nlist *prev, *np;

prev = NULL;
h = hash(s);
for(np = hashtab[h]; np!=NULL; np = np->next){
if(strcmp(s, np->name) == 0)
break;
prev = np;
}

if(np !=NULL) {
if(prev == NULL)
hashtab[h] = np->next;
else
prev->next = np->next;
free((void *) np->name);
free((void *) np->defn);
free((void *) np);
}
}

The question is, how come I have to free() both np->name and np->defn?
Ie, how come I can't just free() np?

Because memory for them was allocated separately.
You need a call to free() for every call to malloc(). You construct the
struct np with three calls to malloc - one for the struct itself and
two more to initialise it's members 'name' and 'defn' to point to
usable storage. Thus when destroying the struct you need to deallocate
storage pointed to by these members too.

In particular if 'name' and 'defn' are the only pointers that point to
their storage, then you must free() them _before_ calling free() on np,
or else you'll create a memory leak.

Note that the casts to void * within the calls to free() are not needed.

The question was taken from page 145 in the "The C Programming
Langauge" by K & R (Second Edition). I think what is tripping me up
when trying to free the structure is the following line of code on
page 145.

In install(), they have the following line of code:

if((np->defn = strdup(defn)) == NULL)
return NULL;

For reasons that still elude me, every time I see this line of code, I
keep thinking that memory ISN'T allocated for np->defn.

 

[santosh]

Excercise 6-5

Write a functon undef that will remove a name and defintion from
the table maintained by lookup and install.

unsigned hash(char *s);

void undef(char *s)
{
int h;
struct nlist *prev, *np;

prev = NULL;
h = hash(s);
for(np = hashtab[h]; np!=NULL; np = np->next){
if(strcmp(s, np->name) == 0)
break;
prev = np;
}

if(np !=NULL) {
if(prev == NULL)
hashtab[h] = np->next;
else
prev->next = np->next;
free((void *) np->name);
free((void *) np->defn);
free((void *) np);
}
}

The question is, how come I have to free() both np->name and
np->defn? Ie, how come I can't just free() np?

Because memory for them was allocated separately.
You need a call to free() for every call to malloc(). You construct
the struct np with three calls to malloc - one for the struct itself
and two more to initialise it's members 'name' and 'defn' to point to
usable storage. Thus when destroying the struct you need to
deallocate storage pointed to by these members too.

In particular if 'name' and 'defn' are the only pointers that point
to their storage, then you must free() them _before_ calling free()
on np, or else you'll create a memory leak.

Note that the casts to void * within the calls to free() are not
needed.

The question was taken from page 145 in the "The C Programming
Langauge" by K & R (Second Edition). I think what is tripping me up
when trying to free the structure is the following line of code on
page 145.

In install(), they have the following line of code:

if((np->defn = strdup(defn)) == NULL)
return NULL;

For reasons that still elude me, every time I see this line of code, I
keep thinking that memory ISN'T allocated for np->defn.

This line attempts to duplicate the string pointed to by 'defn' passed
to strdup() at 'np-defn.' If strdup() fails it returns NULL. Otherwise
you have to explicitly free() memory allocated by it.

Note that strdup() is not defined by ISO C, though it's a common
extension.

See man strdup on UNIX systems.

 

[pete]

Chad wrote:
Excercise 6-5

Write a functon undef that will remove a name and defintion from
the table maintained by lookup and install.

Code:

unsigned hash(char *s);

void undef(char *s)
{
int h;
struct nlist *prev, *np;

prev = NULL;
h = hash(s);
for(np = hashtab[h]; np!=NULL; np = np->next){
if(strcmp(s, np->name) == 0)
break;
prev = np;
}

if(np !=NULL) {
if(prev == NULL)
hashtab[h] = np->next;
else
prev->next = np->next;
free((void *) np->name);
free((void *) np->defn);
free((void *) np);
}
}

The question is, how come I have to free() both np->name and
np->defn? Ie, how come I can't just free() np?

Because memory for them was allocated separately.
You need a call to free() for every call to malloc(). You construct
the struct np with three calls to malloc
- one for the struct itself
and two more to initialise it's members 'name'
and 'defn' to point to
usable storage. Thus when destroying the struct you need to
deallocate storage pointed to by these members too.

In particular if 'name' and 'defn' are the only pointers that point
to their storage, then you must free() them _before_ calling free()
on np, or else you'll create a memory leak.

Note that the casts to void * within the calls to free() are not
needed.

The question was taken from page 145 in the "The C Programming
Langauge" by K & R (Second Edition). I think what is tripping me up
when trying to free the structure is the following line of code on
page 145.

In install(), they have the following line of code:

if((np->defn = strdup(defn)) == NULL)
return NULL;

For reasons that still elude me,
every time I see this line of code, I
keep thinking that memory ISN'T allocated for np->defn.

This line attempts to duplicate the string pointed to by 'defn' passed
to strdup() at 'np-defn.' If strdup() fails it returns NULL. Otherwise
you have to explicitly free() memory allocated by it.

Note that strdup() is not defined by ISO C, though it's a common
extension.

See man strdup on UNIX systems.

strdup is defined on page 143 of K&R2.

 

[vipvipvipvipvip.ru]

strdup is defined on page 143 of K&R2.

K&R2 is old.

 

[santosh]

K&R2 is old.

It's age is irrelevant to the problem at hand. As pete says strdup is
defined elsewhere in the book.

I think that Chad's confusion stems from the fact that he believes 'np'
may be uninitialised. It is however initialised by the function lookup.

 

[Richard Bos]

K&R2 is old.

True, but irrelevant. strdup() is normally considered a Unixoid function
here (and with reason), but in the context of the OP's problem, it is
allowed, simply because that problem itself is from K&R, and presumes
the existence of K&R's, just a little earlier defined, strdup(), not
POSIX's one.

Richard

 

[gw7rib]

In install(), they have the following line of code:

if((np->defn = strdup(defn)) == NULL)
return NULL;

For reasons that still elude me, every time I see this line of code, I
keep thinking that memory ISN'T allocated for np->defn.

Perhaps you could try rewriting it as:

np->defn = strdup(defn);
if(np->defn == NULL) return NULL;

Readability is important, and this version is only a smidgeon less
efficient.

Paul.

 

[CBFalconer]

.... snip ...

if ((np->defn = strdup(defn)) == NULL)
return NULL;

For reasons that still elude me, every time I see this line of
code, I keep thinking that memory ISN'T allocated for np->defn.

Why? The dependency is obviously on strdup, and the return of NULL
presumably means that it failed. (strdup is non-standard.)
Therefore passing this test means it succeeded.

A better form IMO would be:

if (np->defn = strdup(defn)) return NULL;
else {
/* whatever is required */
}

and you can omit the else if you wish. But this form is clearer in
the middle of a function, while the omitted else is better used at
the start of the function.

 

[Charlie Gordon]

Why? The dependency is obviously on strdup, and the return of NULL
presumably means that it failed. (strdup is non-standard.)
Therefore passing this test means it succeeded.

A better form IMO would be:

if (np->defn = strdup(defn)) return NULL;
else {
/* whatever is required */
}

Ugly style:
- assignment as a test expression: a classic cause of stupid bugs.
- if and then clauses on the same line.
- no symmetry between then and else clause.

and you can omit the else if you wish. But this form is clearer in
the middle of a function, while the omitted else is better used at
the start of the function.

Actually, direct return of NULL at the start of the function is better
without an else clause and is OK because it is easy to assert correctness.
This form would be quite error prone in the middle of a large function,
where returning NULL without proper cleanup of locally allocated memory
and/or acquired ressources would go unnoticed precisely because the return
statement does not stand out on its own. Definitely avoid this style.

 

[Peter Pichler]

In particular if 'name' and 'defn' are the only pointers that point to
their storage, then you must free() them _before_ calling free() on np,
or else you'll create a memory leak.

Your emphasis on before makes it look like the alternative is after (as
opposed to "not at all"). Doing that would be an undefined behaviour,
not just a memory leak.

 

[gw7rib]

Chad wrote:

... snip ...



Why? The dependency is obviously on strdup, and the return of NULL
presumably means that it failed. (strdup is non-standard.)
Therefore passing this test means it succeeded.

A better form IMO would be:

if (np->defn = strdup(defn)) return NULL;
else {
/* whatever is required */
}

Correct me if I'm wrong, but doesn't your version do the opposite of
the original one?