Capstone: word frequency
The capstone pulls together files, strings, pointers, memory and the hash table from lesson 52. Part one reads a text file and counts how often each word appears. Part two, the next lesson, sorts those counts and prints a report. The input is a three-line file created by the shell.
Reading and splitting
Each line is read with fgets into a fixed buffer, and strtok splits it on spaces, tabs and the newline. The token lives in the line buffer, so it is valid only until the next line is read; the counter must copy any word it keeps. The first version only counts the words.
printf 'the quick brown fox\njumps over the lazy dog\nthe fox\n' > sample.txt
#include <stdio.h>
#include <string.h>
int main(void)
{
FILE *file = fopen("sample.txt", "r");
char line[128];
int words = 0;
if (file == NULL) {
return 1;
}
while (fgets(line, sizeof line, file) != NULL) {
char *token = strtok(line, " \t\n");
while (token != NULL) {
words++;
token = strtok(NULL, " \t\n");
}
}
fclose(file);
printf("words: %d\n", words);
return 0;
}
gcc -Wall -Wextra read.c -o read
./read
words: 11
Eleven words in three lines, with the newline swallowed by the delimiter set. The program does not keep any word, so the buffer reuse is harmless. A line longer than 127 characters would be split into two reads, and the count would still be right because the split does not change the words.
Counting in a hash table
The table from lesson 52 uses 16 buckets and chaining. An insert walks the bucket, increments an existing entry or allocates a new one with a copy of the word. The copy is the important part: the token points into the line buffer, so the table would otherwise store a pointer to text that the next line overwrites.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define BUCKETS 16
struct Entry {
char *word;
int count;
struct Entry *next;
};
static struct Entry *table[BUCKETS];
static unsigned long hash(const char *text)
{
unsigned long value = 5381;
while (*text != '\0') {
value = value * 33 + (unsigned char) *text;
text++;
}
return value;
}
static int add(const char *word)
{
unsigned long index = hash(word) % BUCKETS;
for (struct Entry *entry = table[index]; entry != NULL; entry = entry->next) {
if (strcmp(entry->word, word) == 0) {
entry->count++;
return 1;
}
}
struct Entry *entry = malloc(sizeof *entry);
if (entry == NULL) {
return 0;
}
entry->word = strdup(word);
if (entry->word == NULL) {
free(entry);
return 0;
}
entry->count = 1;
entry->next = table[index];
table[index] = entry;
return 1;
}
static int count_of(const char *word)
{
unsigned long index = hash(word) % BUCKETS;
for (struct Entry *entry = table[index]; entry != NULL; entry = entry->next) {
if (strcmp(entry->word, word) == 0) {
return entry->count;
}
}
return 0;
}
int main(void)
{
const char *words[4] = {"the", "fox", "the", "dog"};
for (int i = 0; i < 4; i++) {
add(words[i]);
}
printf("the: %d\n", count_of("the"));
printf("fox: %d\n", count_of("fox"));
printf("cat: %d\n", count_of("cat"));
for (int i = 0; i < BUCKETS; i++) {
struct Entry *entry = table[i];
while (entry != NULL) {
struct Entry *next = entry->next;
free(entry->word);
free(entry);
entry = next;
}
}
return 0;
}
gcc -Wall -Wextra table.c -o table
./table
the: 2
fox: 1
cat: 0
The short table program inserts four words, two of them equal, and asks for three counts. The missing word returns zero, which is the same value as a word that never appeared, and the caller knows the difference because it asked a question. The cleanup loop frees every copy and every entry.
The word frequency program
The full program combines the two halves: read the file, split each line, insert every token, and report. It also counts the unique words as the table grows. The four lookups at the end are a quick check that the counters are right, and they print in a stable order.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define BUCKETS 16
struct Entry {
char *word;
int count;
struct Entry *next;
};
static struct Entry *table[BUCKETS];
static int unique = 0;
static unsigned long hash(const char *text)
{
unsigned long value = 5381;
while (*text != '\0') {
value = value * 33 + (unsigned char) *text;
text++;
}
return value;
}
static int add(const char *word)
{
unsigned long index = hash(word) % BUCKETS;
for (struct Entry *entry = table[index]; entry != NULL; entry = entry->next) {
if (strcmp(entry->word, word) == 0) {
entry->count++;
return 1;
}
}
struct Entry *entry = malloc(sizeof *entry);
if (entry == NULL) {
return 0;
}
entry->word = strdup(word);
if (entry->word == NULL) {
free(entry);
return 0;
}
entry->count = 1;
entry->next = table[index];
table[index] = entry;
unique++;
return 1;
}
static int count_of(const char *word)
{
unsigned long index = hash(word) % BUCKETS;
for (struct Entry *entry = table[index]; entry != NULL; entry = entry->next) {
if (strcmp(entry->word, word) == 0) {
return entry->count;
}
}
return 0;
}
int main(void)
{
FILE *file = fopen("sample.txt", "r");
char line[128];
int total = 0;
if (file == NULL) {
return 1;
}
while (fgets(line, sizeof line, file) != NULL) {
char *token = strtok(line, " \t\n");
while (token != NULL) {
if (!add(token)) {
fclose(file);
return 1;
}
total++;
token = strtok(NULL, " \t\n");
}
}
fclose(file);
printf("total: %d\n", total);
printf("unique: %d\n", unique);
printf("the: %d\n", count_of("the"));
printf("fox: %d\n", count_of("fox"));
printf("cat: %d\n", count_of("cat"));
for (int i = 0; i < BUCKETS; i++) {
struct Entry *entry = table[i];
while (entry != NULL) {
struct Entry *next = entry->next;
free(entry->word);
free(entry);
entry = next;
}
}
return 0;
}
gcc -Wall -Wextra count.c -o count
./count
total: 11
unique: 8
the: 3
fox: 2
cat: 0
Eleven words, eight distinct ones: the, quick, brown, fox, jumps, over, lazy and dog. The table is freed before the exit, and the unique count is maintained at the one place a new entry is linked. Part two takes the same data and prints every word with its count, highest first.
strdup needs a feature macro
strdup is POSIX, not ISO C, and a strict -std=c17 build hides it unless a feature macro asks for POSIX. The course builds with the GCC default (gnu23), where the declaration is visible; the same file with a strict standard fails, which is the portability trap of the capstone.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int main(void)
{
char *copy = strdup("hello");
if (copy == NULL) {
return 1;
}
printf("%s\n", copy);
free(copy);
return 0;
}
gcc -std=c17 -Wall -Wextra nodup.c -o nodup
nodup.c: In function 'main':
nodup.c:7:18: error: implicit declaration of function 'strdup'; did you mean 'strcmp'? [-Wimplicit-function-declaration]
7 | char *copy = strdup("hello");
| ^~~~~~
| strcmp
nodup.c:7:18: error: initialization of 'char *' from 'int' makes pointer from integer without a cast [-Wint-conversion]
The second error follows from the first: an undeclared function is assumed to return int, and an int does not initialise a pointer. The fix is #define _POSIX_C_SOURCE 200809L before the first include, or a local copy_string built from strlen and memcpy.
Exercises
- Make the input file name a command-line argument with lesson 75 and print an error when it cannot be opened.
- Lower-case every word before counting, using tolower from lesson 24.
- Count the words of a file with a hundred thousand lines and print the time it takes with the clock from lesson 59.
Questions
A new set of questions in a new order every time. Choose one answer for each, then check.
-
Why must the counter copy each token before storing it?
Answer
The token points into the line buffer that is reused
strtokreturns a pointer into the current line, and the nextfgetsoverwrites that storage, so a kept word needs its own copy. -
How does the hash table count a repeated word?
Answer
It walks the bucket and increments the matching entry
The insert compares the word with the chain, and a match increments the existing count instead of allocating a node.
-
What does
count_ofreturn for a word that never appeared?Answer
Zero, the same value as a stored zero count
The lookup returns zero on a miss, so the caller must know whether the word was expected to exist.
-
What does the cleanup loop free for every entry?
Answer
The copied word and the entry itself
Each entry owns a
strdupcopy, so the word is freed before the entry that points to it. -
What does this program print?
#include <stdio.h> #include <string.h> int main(void){FILE*f=fopen("/tmp/sample.txt","w");fputs("the quick brown fox\njumps over the lazy dog\nthe fox\n",f);fclose(f);f=fopen("/tmp/sample.txt","r");char line[128];int words=0;while(fgets(line,sizeof line,f)){char*t=strtok(line," \t\n");while(t){words++;t=strtok(NULL," \t\n");}}fclose(f);printf("%d\n",words);return 0;}Answer
11
The file holds eleven tokens, and the newline is one of the delimiters.
-
What does this program print for the, fox and cat?
#include <stdio.h> #include <string.h> static int count(const char **w,int n,const char *k){int c=0;for(int i=0;i<n;i++)if(!strcmp(w[i],k))c++;return c;} int main(void){const char *w[4]={"the","fox","the","dog"};printf("%d %d %d\n",count(w,4,"the"),count(w,4,"fox"),count(w,4,"cat"));return 0;}Answer
2 1 0
The word appears twice, fox once, and cat was never inserted.
-
What does this program print?
#include <stdio.h> #include <string.h> int main(void){FILE*f=fopen("/tmp/sample.txt","w");fputs("the quick brown fox\njumps over the lazy dog\nthe fox\n",f);fclose(f);f=fopen("/tmp/sample.txt","r");char line[128];int total=0,the=0;while(fgets(line,sizeof line,f)){char*t=strtok(line," \t\n");while(t){total++;if(!strcmp(t,"the"))the++;t=strtok(NULL," \t\n");}}fclose(f);printf("%d %d\n",total,the);return 0;}Answer
11 3
Eleven tokens are read, and the word
theappears three times. -
What does the strict C17 build report for
strdup?Answer
An implicit declaration error for
strdupPOSIX hides
strdupunder strict C17, and the undeclared call becomes an error with a note to define the feature macro. -
What goes wrong when the table stores the token pointer without copying?
Answer
The next line overwrites every stored word
All tokens point into the same line buffer, so later reads replace the earlier words and the counts become meaningless.
-
How is
strdupmade visible in a strict C17 build?Answer
Define
_POSIX_C_SOURCEbefore the includesThe feature macro asks the headers for the POSIX declarations, or the program can implement its own copy with
strlenandmemcpy.
The code on this page was run with gcc (Alpine 15.2.0) 15.2.0 on Alpine Linux 3.24.3 (x86_64) in a Docker container.
Article author: Arthur Isaev