Capstone: word frequency report
The hash table stores the counts in bucket order, which is not the order a reader wants. The report sorts the entries by count, then by word, and prints them with a rank. The sorting uses the qsort of lesson 54, and the test from lesson 63 checks the order.
Collect the entries
qsort needs contiguous elements, and the table is a set of linked lists. The first step copies the pointers into an array of keys, one per unique word. Sorting the pointers moves no strings, only the array; the entries themselves stay where the table put them.
#include <stdio.h>
struct Entry {
const char *word;
int count;
};
int main(void)
{
struct Entry entries[4] = {
{"the", 3},
{"quick", 1},
{"brown", 1},
{"fox", 2},
};
struct Entry *order[4];
for (int i = 0; i < 4; i++) {
order[i] = &entries[i];
printf("%d: %s %d\n", i, order[i]->word, order[i]->count);
}
printf("collected: 4\n");
return 0;
}
gcc -Wall -Wextra collect.c -o collect
./collect
0: the 3
1: quick 1
2: brown 1
3: fox 2
collected: 4
The array holds addresses, so its element type is struct Entry *, and qsort will pass the address of such an element to the comparator. That extra level is the source of the bug at the end of the lesson.
Sort by count, then word
The comparator orders by descending count and breaks a tie with strcmp, so equal counts come out alphabetically. The two fields are compared in that order, and the subtraction is safe because both counts are small; the sign is what qsort uses, not the exact difference.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
struct Count {
const char *word;
int count;
};
static int compare(const void *left, const void *right)
{
const struct Count *a = left;
const struct Count *b = right;
if (a->count != b->count) {
return b->count - a->count;
}
return strcmp(a->word, b->word);
}
int main(void)
{
struct Count counts[4] = {{"the", 3}, {"quick", 1}, {"brown", 1}, {"fox", 2}};
qsort(counts, 4, sizeof counts[0], compare);
for (int i = 0; i < 4; i++) {
printf("%s %d\n", counts[i].word, counts[i].count);
}
return 0;
}
gcc -Wall -Wextra sort.c -o sort
./sort
the 3
fox 2
brown 1
quick 1
The entry with count 3 is first, then the count 2, and the two count 1 words are alphabetical. The array here holds structs directly, not pointers, so the comparator's cast is the simple one from lesson 54.
The formatted report
The full program repeats the word count of lesson 76, collects the pointers, sorts them and prints a ranked table. The rank is the loop index, the word is left-aligned in eight characters, and the count is right-aligned in three. The header line is printed before the rows.
#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 compare(const void *left, const void *right)
{
const struct Entry *const *pa = left;
const struct Entry *const *pb = right;
const struct Entry *a = *pa;
const struct Entry *b = *pb;
if (a->count != b->count) {
return b->count - a->count;
}
return strcmp(a->word, b->word);
}
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);
struct Entry **entries = malloc((size_t) unique * sizeof *entries);
if (entries == NULL) {
return 1;
}
int next = 0;
for (int i = 0; i < BUCKETS; i++) {
for (struct Entry *entry = table[i]; entry != NULL; entry = entry->next) {
entries[next++] = entry;
}
}
qsort(entries, (size_t) unique, sizeof entries[0], compare);
printf("total: %d, unique: %d\n", total, unique);
for (int i = 0; i < unique; i++) {
printf("%2d %-8s %3d\n", i + 1, entries[i]->word, entries[i]->count);
}
free(entries);
for (int i = 0; i < BUCKETS; i++) {
struct Entry *entry = table[i];
while (entry != NULL) {
struct Entry *ne = entry->next;
free(entry->word);
free(entry);
entry = ne;
}
}
return 0;
}
gcc -Wall -Wextra report.c -o report
./report
total: 11, unique: 8
1 the 3
2 fox 2
3 brown 1
4 dog 1
5 jumps 1
6 lazy 1
7 over 1
8 quick 1
The output is stable: the same input and the same comparator always give this order, because the word breaks every tie. The report frees the pointer array first, then every entry and its copied word, so the leak counter from lesson 32 would show zero.
Test the order
A report is a behavior that can be tested: give the comparator a small array with a known order and check the three positions. The test uses the same struct and comparator, without the file and the table, so a failure points at the sorting rule and not at the input.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
struct Count {
const char *word;
int count;
};
static int compare(const void *left, const void *right)
{
const struct Count *a = left;
const struct Count *b = right;
if (a->count != b->count) {
return b->count - a->count;
}
return strcmp(a->word, b->word);
}
int main(void)
{
struct Count counts[3] = {{"fox", 2}, {"the", 3}, {"dog", 1}};
int failures = 0;
qsort(counts, 3, sizeof counts[0], compare);
if (strcmp(counts[0].word, "the") != 0 || counts[0].count != 3) {
printf("first entry wrong\n");
failures++;
}
if (strcmp(counts[1].word, "fox") != 0 || counts[1].count != 2) {
printf("second entry wrong\n");
failures++;
}
if (strcmp(counts[2].word, "dog") != 0 || counts[2].count != 1) {
printf("third entry wrong\n");
failures++;
}
printf("checks: 3, failures: %d\n", failures);
return failures == 0 ? 0 : 1;
}
gcc -Wall -Wextra test.c -o test
./test; echo "status: $?"
checks: 3, failures: 0
status: 0
The test passes silently apart from the summary, and its exit status is the answer a script reads. A wrong comparator fails the first or second check, and the printed word shows which one. The three cases cover the count order and one tie only by construction; a larger table would add a tie case.
A comparator at the wrong level
qsort passes the address of an array element. When the array holds struct Entry *, the comparator receives struct Entry **. Casting it to struct Entry * reads the pointer bytes as if they were the struct and produces a plausible but wrong order without a warning, because the parameter type is void *.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define BUCKETS 4
struct Entry {
char *word;
int count;
struct Entry *next;
};
static int compare(const void *left, const void *right)
{
const struct Entry *a = left;
const struct Entry *b = right;
if (a->count != b->count) {
return b->count - a->count;
}
return strcmp(a->word, b->word);
}
int main(void)
{
struct Entry first = {"the", 3, NULL};
struct Entry second = {"quick", 1, NULL};
struct Entry third = {"fox", 2, NULL};
struct Entry *entries[3] = {&first, &second, &third};
qsort(entries, 3, sizeof entries[0], compare);
for (int i = 0; i < 3; i++) {
printf("%s %d\n", entries[i]->word, entries[i]->count);
}
return 0;
}
gcc -Wall -Wextra wrongcmp.c -o wrongcmp
./wrongcmp
quick 1
the 3
fox 2
The order ignores the counts, because the comparator read the wrong memory. The fix is the double indirection from the report section, const struct Entry *const * and then the dereference. A comparator with the wrong signature is caught by the compiler, as the same qsort call would show if the function took three parameters; the wrong level of pointer is not.
Exercises
- Print only the ten most frequent words and the total number of words outside that list.
- Add a second sort order, alphabetical, selected with a command-line option from lesson 75.
- Write a test that checks a tie between two words with the same count and fails if the alphabetical order is broken.
Questions
A new set of questions in a new order every time. Choose one answer for each, then check.
-
Why collect the entries into an array before sorting?
Answer
qsortneeds contiguous elementsThe table is a set of linked lists, so an array of pointers gives
qsortthe contiguous range it requires. -
How does the report comparator order two entries?
Answer
Count descending, then word ascending
A larger count sorts first, and equal counts are broken alphabetically with
strcmp. -
What does the pointer-level bug in the comparator do?
Answer
It reads the pointer bytes as a struct and misorders
qsortpassesstruct Entry **, and casting that tostruct Entry *makes the fields come from the wrong memory. -
Why free the pointer array before the entries?
Answer
The array is separate from the table's blocks
The array only holds addresses, so it is released first, and then every entry and its copied word are freed.
-
What does this program print?
#include <stdio.h> int main(void){struct E{const char*w;int c;} e[4]={{"the",3},{"quick",1},{"brown",1},{"fox",2}};for(int i=0;i<4;i++)printf("%d: %s %d\n",i,e[i].w,e[i].c);printf("collected: 4\n");return 0;}Answer
0: the 3 / 1: quick 1 / 2: brown 1 / 3: fox 2 / collected: 4
The entries print in the original array order before any sorting.
-
What does this program print?
#include <stdio.h> #include <stdlib.h> #include <string.h> struct C{const char*w;int c;}; static int cmp(const void*a,const void*b){const struct C*x=a,*y=b;if(x->c!=y->c)return y->c-x->c;return strcmp(x->w,y->w);} int main(void){struct C v[4]={{"the",3},{"quick",1},{"brown",1},{"fox",2}};qsort(v,4,sizeof v[0],cmp);for(int i=0;i<4;i++)printf("%s %d\n",v[i].w,v[i].c);return 0;}Answer
the 3 / fox 2 / brown 1 / quick 1
The count orders the first three, and the two count-1 words come out alphabetically.
-
What does the full report print as its first ranked row?
Answer
1 the 3
The most frequent word is the with count 3, so the rank is 1 and the row is
1 the 3. -
What does the comparator test report?
Answer
checks: 3, failures: 0 and status 0
All three positions match the expected order, so the summary counts no failures and exits zero.
-
What is the fix for a comparator that receives
struct Entry *instead ofstruct Entry **?Answer
Dereference the pointer to the element pointer
The parameter is the address of an array element, so it is read as
const struct Entry *const *and then dereferenced. -
What leak appears if the pointer array from the report is never freed?
Answer
The array block stays allocated until exit
The entries are freed separately, but the array of pointers is one more block that needs its own
free.
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