K&R2 6.6 example

#include <stdio.h>
#include <string.h>     //for strcmp(), strlen(), strcpy()
#include <stdlib.h>     //for malloc(), free()
//compile with: gcc -Wall -Wextra cc-c.c -o cc-c
//run with:     ./cc-c

//K&R2 6.6 Table Lookup: the symbol table of a #define processor.
//
//install(name, defn)  remember that name stands for defn
//lookup(s)            find s's entry, or NULL
//
//hashtab is an array of 101 POINTERS, each the head of a linked list
//("chain"). hash(s) picks the chain; strcmp picks the entry within it.
//
//  hashtab
//   [0]  NULL
//   ...
//   [18] --> {next, "Hm", "oops"} --> {next, "IN", "1"} --> NULL
//   ...
//
//main installs a few names and prints every non-empty chain, to show:
//  - "IN" and "Hm" hash to the same slot (31*73+78 == 31*72+109 == 2341,
//    and 2341 % 101 == 18), so they share chain 18
//  - new entries go at the HEAD of a chain, so "Hm" comes before "IN"
//  - installing "IN" again replaces its defn; no new entry is made
//
//The book's strdup is called mystrdup here: <string.h> already declares
//a strdup of its own, and a second definition would clash with it.
#define HASHSIZE 101

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

static struct nlist *hashtab[HASHSIZE];     //pointer table, all NULL

unsigned hash(char *);
struct nlist *lookup(char *);
struct nlist *install(char *, char *);
char *mystrdup(char *);
void dump(void);

int main(void)
{
    struct nlist *np;

    install("IN", "1");
    install("OUT", "0");
    install("MAXLINE", "1000");
    install("Hm", "oops");          //collides with "IN"
    printf("hash(\"IN\") = %u   hash(\"Hm\") = %u\n\n", hash("IN"), hash("Hm"));
    dump();

    install("IN", "2");             //redefine: same entry, new defn
    printf("\nafter install(\"IN\", \"2\"):\n");
    dump();

    printf("\n");
    if ((np = lookup("MAXLINE")) != NULL)
        printf("lookup(\"MAXLINE\") -> %s\n", np->defn);
    if ((np = lookup("EOF")) == NULL)
        printf("lookup(\"EOF\")     -> NULL (never installed)\n");
    return 0;
}

//hash:  form hash value for string s
unsigned hash(char *s)
{
    unsigned hashval;

    //IDIOM: walk a string by moving the pointer itself -- s++ steps to
    //the next char, *s != '\0' stops at the terminator; no index needed
    for (hashval = 0; *s != '\0'; s++)
        hashval = *s + 31 * hashval;
    return hashval % HASHSIZE;
}

//lookup:  look for s in hashtab
struct nlist *lookup(char *s)
{
    struct nlist *np;

    //IDIOM: walk a linked list -- for (p = head; p != NULL; p = p->next)
    //is the list version of for (i = 0; i < n; i++)
    for (np = hashtab[hash(s)]; np != NULL; np = np->next)
        if (strcmp(s, np->name) == 0)
            return np;      //found
    return NULL;            //not found
}

//install:  put (name, defn) in hashtab
struct nlist *install(char *name, char *defn)
{
    struct nlist *np;
    unsigned hashval;

    //IDIOM: assign and test in one go, like while ((c = getchar()) != EOF);
    //the inner parens matter: = binds more loosely than ==
    if ((np = lookup(name)) == NULL) {      //not found
        //IDIOM: sizeof(*np) -- the size of whatever np points to; sizeof
        //never evaluates *np, so using the not-yet-set np is safe
        np = (struct nlist *) malloc(sizeof(*np));
        //IDIOM: guard with || -- the right side only runs if np != NULL,
        //so np->name is never touched through a null pointer
        if (np == NULL || (np->name = mystrdup(name)) == NULL)
            return NULL;
        hashval = hash(name);
        //IDIOM: insert at the head of a list -- link to the old head
        //FIRST, then make the new node the head; swap them and the
        //rest of the chain is lost
        np->next = hashtab[hashval];        //new entry points at old head
        hashtab[hashval] = np;              //and becomes the new head
    } else                                  //already there
        free((void *) np->defn);            //free previous defn
    if ((np->defn = mystrdup(defn)) == NULL)
        return NULL;
    return np;
}

//mystrdup:  make a duplicate of s (the book's strdup)
char *mystrdup(char *s)
{
    char *p;

    //IDIOM: malloc(strlen(s) + 1) -- strlen doesn't count the '\0',
    //so a string copy always needs one byte more than its length
    p = (char *) malloc(strlen(s) + 1);     //+1 for '\0'
    if (p != NULL)
        strcpy(p, s);
    return p;
}

//dump:  print every non-empty chain, head first
void dump(void)
{
    int i;
    struct nlist *np;

    for (i = 0; i < HASHSIZE; i++)
        if (hashtab[i] != NULL) {
            printf("[%3d]", i);
            for (np = hashtab[i]; np != NULL; np = np->next)
                printf(" --> %s=%s", np->name, np->defn);
            printf(" --> NULL\n");
        }
}

win@DESKTOP-MEIH88T:~$ cd webdev-projects
win@DESKTOP-MEIH88T:~/webdev-projects$ gcc -Wall -Wextra cc-c.c -o cc-c
win@DESKTOP-MEIH88T:~/webdev-projects$ ./cc-c
hash("IN") = 18   hash("Hm") = 18

[ 18] --> Hm=oops --> IN=1 --> NULL
[ 60] --> OUT=0 --> NULL
[ 73] --> MAXLINE=1000 --> NULL

after install("IN", "2"):
[ 18] --> Hm=oops --> IN=2 --> NULL
[ 60] --> OUT=0 --> NULL
[ 73] --> MAXLINE=1000 --> NULL

lookup("MAXLINE") -> 1000
lookup("EOF")     -> NULL (never installed)