Question on free() ing a hash table

Discussion in 'C Programming' started by Chad, Oct 26, 2007.

  1. Chad

    Chad Guest

    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?
     
    Chad, Oct 26, 2007
    #1
    1. Advertising

  2. Chad

    santosh Guest

    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.
     
    santosh, Oct 26, 2007
    #2
    1. Advertising

  3. Chad

    Chad Guest

    On Oct 25, 7:02 pm, santosh <> wrote:
    > 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. 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, Oct 26, 2007
    #3
  4. Chad

    Chad Guest

    On Oct 25, 7:02 pm, santosh <> wrote:
    > 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.
     
    Chad, Oct 26, 2007
    #4
  5. Chad

    santosh Guest

    Chad wrote:

    > On Oct 25, 7:02 pm, santosh <> wrote:
    >> 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.
     
    santosh, Oct 26, 2007
    #5
  6. Chad

    pete Guest

    santosh wrote:
    >
    > Chad wrote:
    >
    > > On Oct 25, 7:02 pm, santosh <> wrote:
    > >> 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.

    --
    pete
     
    pete, Oct 26, 2007
    #6
  7. Chad

    Guest

    On Oct 26, 8:50 am, pete <> wrote:
    >
    > strdup is defined on page 143 of K&R2.


    K&R2 is old.
     
    , Oct 26, 2007
    #7
  8. Chad

    santosh Guest

    wrote:

    > On Oct 26, 8:50 am, pete <> wrote:
    >>
    >> strdup is defined on page 143 of K&R2.

    >
    > 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.
     
    santosh, Oct 26, 2007
    #8
  9. Chad

    Richard Bos Guest

    wrote:

    > On Oct 26, 8:50 am, pete <> wrote:
    > >
    > > strdup is defined on page 143 of K&R2.

    >
    > 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
     
    Richard Bos, Oct 26, 2007
    #9
  10. Chad

    Guest

    On 26 Oct, 03:29, Chad <> wrote:
    > 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.
     
    , Oct 27, 2007
    #10
  11. Chad

    CBFalconer Guest

    Chad wrote:
    >

    .... 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.

    --
    Chuck F (cbfalconer at maineline dot net)
    Available for consulting/temporary embedded and systems.
    <http://cbfalconer.home.att.net>



    --
    Posted via a free Usenet account from http://www.teranews.com
     
    CBFalconer, Oct 27, 2007
    #11
  12. "CBFalconer" <> a écrit dans le message de news:
    ...
    > Chad wrote:
    >>

    > ... 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 */
    > }


    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.

    --
    Chqrlie.
     
    Charlie Gordon, Oct 27, 2007
    #12
  13. santosh wrote:

    > 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.
     
    Peter Pichler, Oct 28, 2007
    #13
  14. Chad

    Guest

    On 27 Oct, 16:17, CBFalconer <> wrote:
    > Chad wrote:
    >
    > ... 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 */
    > }


    Correct me if I'm wrong, but doesn't your version do the opposite of
    the original one?
     
    , Nov 8, 2007
    #14
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. John
    Replies:
    13
    Views:
    723
  2. ravi
    Replies:
    0
    Views:
    469
  3. error while "free"ing memory

    , Feb 8, 2006, in forum: C Programming
    Replies:
    5
    Views:
    311
  4. rp
    Replies:
    1
    Views:
    562
    red floyd
    Nov 10, 2011
  5. Srijayanth Sridhar
    Replies:
    19
    Views:
    656
    David A. Black
    Jul 2, 2008
Loading...

Share This Page