K&R2 exercise 6-5

#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 exercise 6-5: write a function undef that will remove a name and
//definition from the table maintained by lookup and install.
//
//Removing a node from a chain means: whatever points AT the node must be
//made to point PAST it, to node->next. The trouble is that "whatever
//points at it" is one of two different things:
//
//  - the node is first in its chain:   hashtab[h] points at it
//  - the node is further along:        the previous node's next does
//
//                 hashtab[18]          Hm's next
//                     |                    |
//                     v                    v
//  hashtab[18] --> {Hm, next} ----------> {IN, next} --> NULL
//
//The usual answer is to remember the previous node while walking, and
//write if (prev == NULL) hashtab[h] = ...; else prev->next = ...;
//
//undef below uses a pointer to a POINTER instead: pp holds the address
//of the arrow itself -- first &hashtab[h], then &node->next for each
//node. Both are just "a struct nlist * stored somewhere", so one
//statement, *pp = np->next, unlinks the first node and a middle node
//alike. No prev, no special case.
//
//main installs IN and Hm (both in chain 18, Hm at the head) and OUT,
//then removes a middle node, a head node, and a name that isn't there.
#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 *);
int undef(char *);
char *mystrdup(char *);
void dump(void);

int main(void)
{
    install("IN", "1");
    install("OUT", "0");
    install("Hm", "oops");          //same chain as IN, goes in front of it
    dump();

    printf("\nundef(\"IN\")  = %d   (middle of chain 18)\n", undef("IN"));
    dump();

    printf("\nundef(\"Hm\")  = %d   (head of chain 18)\n", undef("Hm"));
    dump();

    printf("\nundef(\"EOF\") = %d   (never installed)\n", undef("EOF"));
    printf("lookup(\"IN\") = %s\n", lookup("IN") == NULL ? "NULL" : "found");
    return 0;
}

//undef:  remove name and its definition from hashtab;
//        return 1 if it was there, 0 if not
int undef(char *name)
{
    struct nlist **pp;      //address of the pointer that points at a node
    struct nlist *np;

    //IDIOM: pointer to pointer for list removal -- pp starts at the
    //address of the chain's head, then moves to the address of each
    //node's next; *pp is always "the arrow pointing at the current node"
    for (pp = &hashtab[hash(name)]; *pp != NULL; pp = &(*pp)->next)
        if (strcmp(name, (*pp)->name) == 0) {
            np = *pp;
            *pp = np->next;     //the arrow now skips np: np is unlinked
            //IDIOM: free in reverse of allocation -- the strings first,
            //while np still exists to reach them, then np itself
            free(np->name);
            free(np->defn);
            free(np);
            return 1;
        }
    return 0;
}

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

    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;

    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;

    if ((np = lookup(name)) == NULL) {      //not found
        np = (struct nlist *) malloc(sizeof(*np));
        if (np == NULL || (np->name = mystrdup(name)) == NULL)
            return NULL;
        hashval = hash(name);
        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;

    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:~/webdev-projects$ gcc -Wall -Wextra cc-c.c -o cc-c
win@DESKTOP-MEIH88T:~/webdev-projects$  ./cc-c
[ 18] --> Hm=oops --> IN=1 --> NULL
[ 60] --> OUT=0 --> NULL

undef("IN")  = 1   (middle of chain 18)
[ 18] --> Hm=oops --> NULL
[ 60] --> OUT=0 --> NULL

undef("Hm")  = 1   (head of chain 18)
[ 60] --> OUT=0 --> NULL

undef("EOF") = 0   (never installed)
lookup("IN") = NULL