confusion of hashtab and linked list

This is a discussion on confusion of hashtab and linked list within the C Programming forums, part of the General Programming Boards category; Code: struct nlist *lookup(char *); char *strdup(char *); /* install: put (name, defn) in hashtab */ struct nlist *install(char *name, ...

  1. #1
    Registered User
    Join Date
    Dec 2004
    Posts
    64

    confusion of hashtab and linked list

    Code:
       struct nlist *lookup(char *);
       char *strdup(char *);
    
       /* install:  put (name, defn) in hashtab */
       struct nlist *install(char *name, char *defn)
       {
           struct nlist *np;
           unsigned hashval;
    
           if ((np = lookup(name)) == NULL) { /* not found */
               np = (struct nlist *) malloc(sizeof(*np));
               if (np == NULL || (np->name = strdup(name)) == NULL)
                   return NULL;
               hashval = hash(name);
               np->next = hashtab[hashval];  /*******************/
               hashtab[hashval] = np;
           } else       /* already there */
               free((void *) np->defn);   /*free previous defn */
           if ((np->defn = strdup(defn)) == NULL)
               return NULL;
           return np;
       }
    Please look at the line with comment of many stars.

    In my understanding, np->next should point to the address of next structure in the linked list. Why here does it point back to the hashtab? I read this code again and again, but just can't understand it.

    It's an example in K&R "The C Programming Language", 6.6, Table Lookup.

  2. #2
    Registered User
    Join Date
    Dec 2004
    Posts
    64
    I've figured out it. I misunderstood the expression.

    It says, if hashtab[hashval] has a value already, np->next will be assigned with that value.
    if hashtab[hashval] doesn't has a value, np->next will be assigned as NULL.

  3. #3
    Gawking at stupidity
    Join Date
    Jul 2004
    Location
    Oregon, USA
    Posts
    3,163
    NULL is a value.
    If you understand what you're doing, you're not learning anything.

  4. #4
    Registered User
    Join Date
    Feb 2004
    Posts
    42
    Hey, I too got confuse...
    But I think that it might be like this:

    /* the 'next' struct is pointed to 'hashtab[hashval]' */
    np->next = hashtab[hashval];

    /* 'hashtab[hashval] = np;' points to a new struct which is next in the list due to the pervious line*/
    hashtab[hashval] = np;

    If its wrong, pls correct me, I too want to know how it work.
    Last edited by Eavan Hyde; 09-14-2006 at 08:03 AM.

Popular pages Recent additions subscribe to a feed

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21