Table lookup install function from k&r

Section 6.6 of K&R discusses a hash table using a linked list.

In short, a hash table is an array of pointers. The pointers point to a linked list. The linked list is a struct that looks like:

struct nlist {             /* table entry: */
    struct nlist *next;    /* next entry in chain */
    char *name;            /* defined name */
    char *defn;            /* replacement text */
};

The name is hashed, and this hash determines the index in the table. The chapter then shows code to add a name/defn pair to the table:

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;
}

Everything makes sense except for the following 2 lines:

np->next = hashtab[hashval];
hashtab[hashval] = np;

When I try to understand this, I keep coming to the conclusion that the list now links back to itself and if you try to traverse the linked list it will be like a dog chasing its own tail. I would expect the code to set np->next to NULL.

What am I not understanding? How come this co开发者_开发百科de works ?

It results in the new value being inserted at the beginning of the list.

So it goes from:

hashtab[hashval]   -->  original_list

to:

hashtab[hashval]   -->  original_list
np->next           -->  original_list

to:

hashtab[hashval]  -->  *np
        np->next  -->  original_list

The golden rule is, if linked-list code doesn't make sense, always draw out a diagram!

hashtab[hashval] is a pointer, not a value. It is a pointer to the address in memory where the first element of that particular row in the pointer table (static struct nlist *hashtab[HASHSIZE]) resides. np and np->next are also pointers. So here is what happens in these two lines: First line: The pointer of the first element in that row of the table is copied into np->next. np->next now points at the address in memory where the first element of that row used to point. Second line: The pointer to the address in memory where the new *np resides is now copied into the pointer variable hastab[hashval]. hastab[hashval] now once again becomes the pointer to where the first element of that table row resides. So, just as Oli wrote, the new *np is inserted at the beginning of that particular row in the table.

There is already a node there. That node is null. By defining the nlist struct as static, it is automatically initiates all its element pointers to NULL.

Correct me if I'm wrong.

But there is no original list here. It is inserting a node where no key is found, right?

if ((np = lookup(name)) == NULL) { /* not found */ 

Actually its really simple consider two strings "IN" and "Hm" . these two have the same hash value and hence the hashing function returns 18 in both the cases . so when a new string or data comes with the same hash , then a linked list comes into existence . the new node with the same hash is attached to the beginning of the list and its next link contains the previous node ...

AND TO MAKE THINGS MORE BEAUTIFUL TRY THIS CODE OUT ...

enter code here

#include <stdlib.h>
#include <stdio.h>
#include <string.h>

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

# define  HASHSIZE 101


static struct nlist *hashtab[HASHSIZE];


unsigned hash (char *name );
struct nlist *lookup ( char *name );

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

unsigned hash ( char *s ){

    printf("entered hashing function \n ");

    unsigned hashval ;
    for ( hashval = 0 ; *s!='\0';s++)
    {printf("*s= %d %c ",*s,*s);hashval = *s + 31 * hashval ;}

    printf(" hashval = %d exiting hashing function returning  %d  \n ",hashval , hashval%HASHSIZE);

    return hashval%HASHSIZE ;

}

struct nlist * lookup (char *name ){
    struct nlist *np ;

    printf("entered lookup \n");

    for (np = hashtab[hash(name)];np!=NULL; )
        {
            printf("entered for loop");
        
        if(strcmp ( name, np -> name  )== 0 )
        {printf("returning np with name =  %s\t and data = %s\n ",np->name , np->defn );
         return np;}
         np=np->next;
        if(np!=NULL)
        printf("np->next has name = %s\t and defn = %s\n", np->name , np->defn );

        }

    printf("exiting lookup returning null \n "); 
    return NULL ;

}


struct nlist * install (char * name , char * defn){
    struct nlist *np;
    unsigned hashval ;
    printf(" entered install routine \n ");
    if( (np = lookup (name)) == NULL){
        np = (struct nlist * ) malloc (sizeof (*np));
        if(np==NULL|| (np->name = strdup (name ))==NULL)
        return NULL ;
        hashval=hash (name);
        printf("hashing function gave %d \n", hashval );        
        np->next = hashtab[hashval];
        if(hashtab[hashval]==NULL && np->next == NULL)
        printf(" it is null\n ");
        else 
        printf("assigned np->next = hashtab[hashval]   where name = %s & defn= %s \n",hashtab[hashval]->name  ,hashtab[hashval]->defn    );
        hashtab[hashval] = np ;
        //  this printf doesnt work because the defn is not yet assigned and its a pointer to an empty location printf("assigned hashtab[hashval] = np   which has name = %s \t and defn = %s \n ", np->name , np->defn  );
        printf("assigned hashtab[hashval] = np   which has name = %s \n" , np->name );

    }else {
        free((void*) np->defn);
    }

    if((np->defn = strdup(defn))== NULL)
    return NULL ; 
    printf("new defination given = %s\n" , np->defn );
    printf( " exiting install returning np where  name  = %s\t amd defn = %s \n ", np->name , np->defn );
    return np ;

}

int main(){
    printf("entered main " ) ;
    struct nlist *np ;
    install("IN","1");
    install("IN","3");
    install("Hm","3");
    install("OUT","0");
    install("IN","0");
    install("IN","9");

    
    // for ( np = lookup("IN"); np!=NULL; np= np->next )  // standard idom of walking along a linked list 
    np= lookup("IN");
    printf("%s\t%s \n", np->name  , np->defn);
    np = lookup ( "OUT");
    printf("%s\t%s \n" , np->name , np->defn);
    np = lookup ("Hm");
    printf("%s\t%s \n" , np->name , np->defn);

    printf(" main exitted ");

}