K&R C Programs Exercise 6-5 - C Program Examples

Exercise 6-5. Write a function undef that will remove a name and definition from the table maintained by lookup and install.

K&R Section 6.6 presents a hash table with separate chaining: an array of HASHSIZE buckets, each being the head of a linked list of struct nlist nodes. install adds a name/definition pair; lookup finds it. undef must find the node and splice it out of its bucket’s list — a standard singly-linked-list deletion requiring a “previous node” pointer.

Solution

/* K&R Exercise 6-5 — hash table with lookup, install, and undef
 * Compile: gcc -ansi -Wall ex6-5.c -o ex6-5
 * No runtime input: self-contained test in main() */
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define HASHSIZE 101

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

static struct nlist *hashtab[HASHSIZE];   /* initialised to NULL */

static unsigned int hash(const char *s)
{
    unsigned int hashval;
    for (hashval = 0; *s; s++)
        hashval = (unsigned int)*s + 31u * hashval;
    return hashval % HASHSIZE;
}

struct nlist *lookup(const char *s)
{
    struct nlist *np;
    for (np = hashtab[hash(s)]; np; np = np->next)
        if (strcmp(s, np->name) == 0)
            return np;
    return NULL;
}

struct nlist *install(const char *name, const char *defn)
{
    struct nlist *np;
    unsigned int  hval;

    if ((np = lookup(name)) == NULL) {   /* not found: create new entry */
        np = (struct nlist *)malloc(sizeof(*np));
        if (!np) return NULL;
        np->name = (char *)malloc(strlen(name) + 1);
        if (!np->name) { free(np); return NULL; }
        strcpy(np->name, name);
        hval = hash(name);
        np->next = hashtab[hval];
        hashtab[hval] = np;
        np->defn = NULL;
    } else {
        free(np->defn);   /* replace existing definition */
    }
    np->defn = (char *)malloc(strlen(defn) + 1);
    if (!np->defn) return NULL;
    strcpy(np->defn, defn);
    return np;
}

/* undef: remove name from the table; no-op if not found */
void undef(const char *name)
{
    unsigned int   hval = hash(name);
    struct nlist  *prev = NULL;
    struct nlist  *np   = hashtab[hval];

    while (np) {
        if (strcmp(name, np->name) == 0) {
            /* splice out */
            if (prev)
                prev->next = np->next;
            else
                hashtab[hval] = np->next;
            free(np->name);
            free(np->defn);
            free(np);
            return;
        }
        prev = np;
        np   = np->next;
    }
    /* name not in table: silently ignore */
}

int main(void)
{
    /* --- install some definitions --- */
    install("MAX",   "100");
    install("PI",    "3.14159");
    install("DEBUG", "1");

    printf("After install:\n");
    printf("  MAX   = %s\n", lookup("MAX")   ? lookup("MAX")->defn   : "(not found)");
    printf("  PI    = %s\n", lookup("PI")    ? lookup("PI")->defn    : "(not found)");
    printf("  DEBUG = %s\n", lookup("DEBUG") ? lookup("DEBUG")->defn : "(not found)");

    /* --- remove one --- */
    undef("PI");

    printf("\nAfter undef(\"PI\"):\n");
    printf("  MAX   = %s\n", lookup("MAX")   ? lookup("MAX")->defn   : "(not found)");
    printf("  PI    = %s\n", lookup("PI")    ? lookup("PI")->defn    : "(not found)");
    printf("  DEBUG = %s\n", lookup("DEBUG") ? lookup("DEBUG")->defn : "(not found)");

    /* --- undef something that doesn't exist: no crash --- */
    undef("NOSUCHNAME");
    printf("\nundef of missing name: OK (no crash)\n");

    /* --- re-install after undef --- */
    install("PI", "3.14");
    printf("Re-installed PI = %s\n", lookup("PI")->defn);

    return 0;
}

Compile and Run

gcc -ansi -Wall ex6-5.c -o ex6-5
./ex6-5

Expected Output

After install:
  MAX   = 100
  PI    = 3.14159
  DEBUG = 1

After undef("PI"):
  MAX   = 100
  PI    = (not found)
  DEBUG = 1

undef of missing name: OK (no crash)
Re-installed PI = 3.14

How `undef` Works

The bucket is a singly-linked list. To remove a node you need a pointer to the node before it:

struct nlist *prev = NULL;
struct nlist *np   = hashtab[hval];

while (np) {
    if (strcmp(name, np->name) == 0) {
        if (prev)  prev->next      = np->next;  /* mid/tail removal */
        else       hashtab[hval]   = np->next;  /* head removal     */
        free(np->name); free(np->defn); free(np);
        return;
    }
    prev = np;
    np   = np->next;
}

When prev == NULL the matched node is the bucket head, so we update the bucket array directly. When prev != NULL we update prev->next. Both name and defn must be freed to avoid memory leaks.

What This Exercise Teaches

Singly-linked-list deletion — requires tracking the previous node; the head-of-list case is special because there is no previous node to update
Ownership and freeing — install owns the memory for name and defn; undef must free both before freeing the node itself to avoid leaks
Hash table invariants — undef must use the same hash() function as lookup to find the right bucket; using any other bucket leaves the node unreachable (a leak)

Set Up Your C Environment

← Exercise 6-4 |
Chapter 6 Solutions |
Exercise 6-6 →

Book: The C Programming Language, 2nd Ed — Kernighan & Ritchie