p 145 K&R

Discussion in 'C Programming' started by mdh, Sep 1, 2008.

  1. mdh

    mdh Guest

    Hi all,
    I have a question about an aspect of the hash table implementation
    from p 145.

    The code, stripped as far as possble, is as follows.

    /*******/

    #define HASHSIZE 101

    struct nlist{
    struct nlist *next;
    char *defn;
    char *name;
    };


    struct nlist *hashtable[HASHSIZE];


    struct nlist *install( char *name, char *defn);

    int main (int argc, const char * argv[]) {

    struct nlist *np;
    np = install("test", "12");

    }


    struct nlist *install( char *name, char *defn){
    struct nlist *np;
    unsigned hashval;

    if ( (np=lookup(name) )== NULL) {
    np= malloc(sizeof(*np));
    if ( np == NULL || (np->name = str_dup(name)) == NULL)
    return NULL;
    hashval = hash(name);
    np->next = hashtable[hashval]; /******** Question 1*******/
    hashtable[hashval]=np;
    }
    else
    free((void *) np->defn); /********* Question 2 **********/
    if ( ( np->defn = str_dup(defn)) == NULL)
    return NULL;
    return np;
    }

    Question 1;
    What exactly does this line do? It seems to be assigning a pointer at
    element "hasval" to the member nlist.next, but my question is
    why? :) I assume to create the linked list...but the logic escapes
    me.

    Question 2:

    free casts np-> defn to a void pointer. K&R do not go into great
    detail about free here, but seeing that free and malloc seem tied
    close together, does the admonition of not using a cast in malloc
    apply to free to. Of note, the errata pages do not make mention of
    this.

    Thanks as always.
     
    mdh, Sep 1, 2008
    #1
    1. Advertisements

  2. mdh

    Chris Torek Guest

    [regarding free((void *)expr) in K&R2]

    K&R2 was indeed published pre- (or at least co-) Standard, and
    there were no "ANSI C" compilers available at the time. They have
    mentioned, here and/or in the front of the book (my K&R is missing
    and/or in a box so I cannot check) that the code was compiled with
    a then-C++ compiler, rather than either a K&R-1 C compiler or an
    ANSI C compiler, and C++ (both then and now) had and has different
    rules for type conversions, particularly with regard to "void *".

    (The C++ language that existed in 1987/88 was quite different from
    today's C++ language. I would say it was more different from
    today's C++ than today's C99 is from K&R-1 C. But it -- then-C++,
    I mean -- was the only way to work with function prototypes, back
    then.)
     
    Chris Torek, Sep 1, 2008
    #2
    1. Advertisements

  3. mdh

    Ian Collins Guest

    You remember well, it's the second from last sentence in the preface.
     
    Ian Collins, Sep 1, 2008
    #3
  4. According to the Preface "We used Bjarne Stroustrup's C++
    translator extensively for local testing of our programs,
    and Dave Kristol provided us with an ANSI C compiler for
    final testing."

    Depending on what you mean by 'work', it's worth noting
    that C99 still doesn't _require_ function prototypes.
     
    Peter Nilsson, Sep 1, 2008
    #4
  5. mdh

    mdh Guest


    I think I may be making this more complicated than it should be...and
    I keep thinking the list is broken at some point...but ..

    let me see if this makes sense to you.



    if "name does not exist" {

    np = malloc(sizeof(*np));


    /* malloc returns a pointer to a struct of type nplist.*/
    /* this pointer 'np' points to some memory somewhere that I
    need not be concerned with */

    if ("errors found")
    return NULL;


    hashval = "create a hash vauel from name";


    np->next = hashtable[hashval];

    /* whatever is currently pointed to ( be it a single struct
    or a list) by the nth element of the hashtable, is now assigned to be
    pointed to by the "next" pointer of the current struct ie np.ie the
    single struct/list is attached to the "end" of the current struct.

    At this point, and I tread carefully, knowing that events do not
    happen in sequential order between sequence points...I think :),
    there **could** be no connection at all between the "new" struct
    linked list and the hashtable, but np still exists? as it still points
    to the original "space" assigned by malloc ( and presumably all the
    other structs to which it is linked do the same ).

    hashtable[hashval]=np;

    /* the entire new linked list is once again assigned to the hashtable
    */


    **if** this is vaguely correct, is this the usual way a new struct is
    "lined" to the chain ie last is placed first in a list?

    thank you as always.
     
    mdh, Sep 2, 2008
    #5
  6. Since there's only a head node, it's the simplest way.
    e.g. you could traverse to the end of the list and
    attach it to the last node, but why bother? If the
    number of clashes increases to the point where a linear
    search of a small unordered list becomes too costly, then
    it's time to review the hash algorithm and/or the size of
    the hash table. Incorporating a more elaborate mechanism
    to manage clashes tends to defeat the purposes of using
    a hash table in the first place. Of course that's not
    to say it never happens.
     
    Peter Nilsson, Sep 2, 2008
    #6
  7. mdh

    mdh Guest

    Having not worked with Hash tables extensively, it seems from what you
    say, that the essence is to distribute the input evenly across as many
    "buckets" as possible, and keep the actual linked list reasonably
    small? Is that a fair statement ?. Thank you.
     
    mdh, Sep 2, 2008
    #7
  8. mdh

    mdh Guest

    Eric...thank you. Actually, I do draw things and certainly try to
    mentally visualize things as you say. In fact, in writing the reply to
    you, it did become clearer as well.
    As far as progress goes, I finally do feel some. As per another
    frequent replier to my endless questions ( :) ) where I had referred
    to something in the "cretaceous" period, the "bronze age" is a
    significant step forward!!!! :)

    As always, thank you for your answer.
     
    mdh, Sep 2, 2008
    #8
  9. mdh

    Bill Reid Guest

     
    Bill Reid, Sep 2, 2008
    #9
  10. mdh

    Richard Guest

     
    Richard, Sep 2, 2008
    #10
  11. mdh

    gw7rib Guest

    That sounds a fair statement. Remember, however, that even with a
    perfect hash function you have:

    Number of items = size of hashtable * average length of list

    so you may have to trade off the size of the hashtable (which takes
    memory to strore) against how long you want the lists to be (takes
    time to look up items).
     
    gw7rib, Sep 2, 2008
    #11
  12. mdh

    gw7rib Guest

    I think you're worrying unduly about whether the code happens in
    sequential order here. Each of the semicolons gives you a sequence
    point. The usual problems with sequence points (or rather, the lack of
    them) tend to happen when you use ++ or --.

    Hope that helps.
    Paul.
     
    gw7rib, Sep 2, 2008
    #12
  13. mdh

    Dan Henry Guest

    A reasonable reading order could be:

    1. K&R as a decent tutorial.
    2. H&S as a decent reference.
    3. The Standard (year of your interest) as the definitive
    reference.
     
    Dan Henry, Sep 4, 2008
    #13
  14. It seems not to suit complete beginners (or some of them). I know
    someone who became a very competant programmer who couldn't get on
    with K&R. A bit too information dense I think. And a lack of
    answers to the exercises.

    I thought K&R was great, but C was my Nth language
     
    Nick Keighley, Sep 4, 2008
    #14
  15. My favorite book for complete beginners is Tom Plum's Learning to
    Program in C, but I have no idea whether it's still available or not.
     
    lawrence.jones, Sep 4, 2008
    #15
    1. Advertisements

Ask a Question

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

You'll need to choose a username for the site, which only take a couple of moments (here). After that, you can post your question and our members will help you out.