Project: word frequency counter

Why this matters

The modules so far each taught one idea in isolation. Real programs combine them: reading input character by character, managing heap memory, picking a data structure, sorting with a callback, parsing arguments, reporting errors with the right exit status, and cleaning up. This project builds wordfreq, a small but genuinely useful tool (the kind of thing you would otherwise do with a shell pipeline like tr -cs A-Za-z '\n' | sort | uniq -c | sort -rn), in three steps. Along the way, notice how each design decision follows from something you learned earlier.

What we are building

$ ./wordfreq 5 < text.txt
23 words, 14 distinct
      5 the
      3 dog
      3 fox
      2 a
      1 and

Specification:

• Read text from standard input until end of file.
• A word is a maximal run of letters; anything else (spaces, digits, punctuation, apostrophes) separates words. Words are compared case-insensitively, so they are stored in lowercase. This splits doesn't into doesn and t; that is a deliberate simplification you can improve later.
• Print W words, D distinct, then the N most frequent words (default 10), most frequent first, ties in alphabetical order, as %7d %s.
• Bad arguments produce a message on stderr and exit status 2, following the Unix convention that 2 means "usage error".

Design

Three pieces, each a separate concern:

  stdin --> next_word() --> add_word() --> hash table --> array of pointers --> qsort --> print
            tokenizer        counting                      collect             order

Tokenizer. getchar gives one character at a time, which makes "skip non-letters, then copy letters" a pair of simple loops. The caller provides the buffer and its capacity, the safe pattern from the strings module: the function never writes more than cap bytes, and an overlong word is truncated rather than overflowing.

Counting. We need "find this word, or add it" for every word of input, so lookup must be fast. A hash table with separate chaining does that: an array of buckets, each the head of a linked list of entries.

  table[NBUCKETS]
  +-----+
  |  0  | -> NULL
  +-----+
  |  1  | -> ["fox", 3] -> ["end", 1] -> NULL
  +-----+
  | ... |
  +-----+
  | 812 | -> ["the", 5] -> NULL
  +-----+

hash(word) % NBUCKETS picks the bucket. We use the djb2 hash (h = h * 33 + c), simple and good enough for words. A fixed 1024 buckets keeps the code short; the data structures module showed how to grow the table when it fills up.

Each entry owns a heap copy of its word. This is essential: next_word writes into the same local buffer every time, so storing a pointer to that buffer would make every entry point at the last word read. Ownership also decides cleanup: whoever owns the table frees every word and every entry, once, at the end.

Ordering. A hash table has no useful order, so at the end we collect a pointer to every entry into one array and sort that with qsort. Sorting pointers rather than whole structs is cheaper (8 bytes moved per swap) and leaves the table intact for freeing.

Step 1: tokenizing

size_t next_word(char *buf, size_t cap)
{
    int c;
    size_t len = 0;
    while ((c = getchar()) != EOF && !isalpha(c))
        ;                                   /* skip separators */
    while (c != EOF && isalpha(c)) {
        if (len < cap - 1)
            buf[len++] = (char)tolower(c);  /* store, if there is room */
        c = getchar();                      /* but always consume */
    }
    buf[len] = '\0';
    return len;
}

Details that matter:

• c is an int. getchar returns either a byte value (0 to 255) or EOF (-1); a char cannot hold all 257 possibilities.
• isalpha and tolower take an int that must be EOF or an unsigned char value, which is exactly what getchar returns. (Passing a plain char with a negative value is undefined, a classic bug when the input contains non-ASCII bytes.)
• The function returns 0 only when it reached end of input without finding a letter, so the caller can write while (next_word(w, sizeof w) > 0).
• The letter that ends a word is a separator, which the next call skips. Nothing is lost.

Step 2: counting

add_word is the classic "find or insert":

static int add_word(const char *w)
{
    unsigned long b = hash(w) % NBUCKETS;
    for (struct entry *e = table[b]; e != NULL; e = e->next) {
        if (strcmp(e->word, w) == 0) {
            e->count++;
            return 0;
        }
    }
    struct entry *e = malloc(sizeof *e);
    if (e == NULL)
        return -1;
    e->word = malloc(strlen(w) + 1);
    if (e->word == NULL) {
        free(e);              /* do not leak the half-built entry */
        return -1;
    }
    strcpy(e->word, w);
    e->count = 1;
    e->next = table[b];       /* push on the front: O(1) */
    table[b] = e;
    distinct++;
    return 0;
}

Two allocations per new word, and either can fail; if the second fails, the first must be released before reporting the error. Freeing the table walks each list, saving next before each free because the entry's memory is invalid afterwards.

The table and distinct are static globals here to keep the project small. In a library you would wrap them in a struct table and pass a pointer, so a program could have several tables.

Step 3: sorting and finishing

qsort sorts any array given its element size and a comparator: a function that receives pointers to two elements and returns negative, zero or positive. Our elements are struct entry *, so the comparator receives pointers to pointers:

static int by_count(const void *a, const void *b)
{
    const struct entry *x = *(const struct entry *const *)a;
    const struct entry *y = *(const struct entry *const *)b;
    if (x->count != y->count)
        return x->count < y->count ? 1 : -1;   /* bigger counts first */
    return strcmp(x->word, y->word);            /* then alphabetical */
}

Writing return y->count - x->count; also works for word counts, but the subtraction trick overflows for values far apart, so the explicit comparison is the better habit. The tie-breaker matters too: without it, words with equal counts come out in whatever order the hash table and qsort happen to produce, and tests that compare output would be flaky.

Argument parsing uses strtol with its end pointer, as in the robust parsing lesson: "10" is fine; "", "ten", "5x" and "0" are rejected. Allocating the pointer array needs care with an empty input, where distinct is 0: malloc(0) may legally return NULL, which would look like an out-of-memory error, so the solution asks for at least one element.

Testing it

Beyond the example inputs, test the edges, which is where C programs break: empty input, input with no letters, one enormous word, a word that repeats a million times, invalid arguments. And run it under valgrind:

$ valgrind -q --leak-check=full ./wordfreq < text.txt > /dev/null
$

Silence means no errors and no leaks.

Common mistakes

• Storing the buffer pointer instead of a copy in the entry. Every word then shows up as the last word read, and the program may read freed or overwritten memory.
• char c = getchar();: EOF detection breaks (on x86 a byte 0xFF looks like EOF; on platforms with unsigned char, EOF is never seen and the loop never ends).
• Comparator confusion: casting a to struct entry * instead of struct entry ** compiles, and then reads garbage. Draw the picture: the array holds pointers, qsort passes pointers to the array slots.
• Forgetting free(all) or freeing entries before printing from the array.
• No tie-breaker, giving nondeterministic output.

Recap

• A project is a pipeline of small, separately testable functions: tokenize, count, collect, sort, print.
• Caller-provided buffers with a capacity make tokenizing safe.
• A chained hash table gives fast find-or-insert; each entry owns a heap copy of its key.
• qsort with a comparator sorts an array of pointers; always add a tie-breaker.
• Every allocation has one owner and one matching free, including on error paths.

Going further: extend wordfreq to keep apostrophes inside words (doesn't), to read file names given as extra arguments instead of stdin, or to grow the hash table when the average chain length passes 2. Then time it on a big text: seq 1 200000 | sed 's/.*/word&/' | ./wordfreq generates 200,000 distinct words.