Count frequency of words and print them in sorted order

Question

Objective:

Write a program to count the frequencies of unique words from standard input, then print them out with their frequencies, ordered most frequent first. For example, given this input:

The foo the foo the
defenestration the

The program should print the following:

the 4
foo 2
defenestration 1

The test input file will be the text of the King James Bible, concatenated 10 times.

Code:

I used the public-domain stb library stb_ds.h for the hash table.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdint.h>
#include <stdbool.h>
#include <limits.h>
#include <ctype.h>

#define STB_DS_IMPLEMENTATION
#include "stb_ds.h"

/* pneumonoultramicroscopicsilicovolcanoconiosis - a lung disease caused by
 * inhaling silica dust. */
#define LONGEST_WORD 45

#define CHUNK_SIZE  (8 * 1024)

typedef struct count {
    char *key;
    size_t value;
} count;

static int cmp_func(const void *a, const void *b)
{
    const count *const p = *(const count * const *) a;
    const count *const q = *(const count * const *) b;

    return (p->value < q->value) - (p->value > q->value);
}

static void replace_punctuation(size_t len, char s[static len])
{
    // ".,;:!?\"()[]{}-"
    static const char table[UCHAR_MAX + 1] = {
        ['.'] = '.' ^ ' ',[','] = ',' ^ ' ',[';'] = ';' ^ ' ',[':'] = ':' ^ ' ',
        ['!'] = '!' ^ ' ',['?'] = '?' ^ ' ',['"'] = '"' ^ ' ',['('] = '(' ^ ' ',
        [')'] = ')' ^ ' ',['['] = '[' ^ ' ',[']'] = ']' ^ ' ',['{'] = '{' ^ ' ',
        ['}'] = '}' ^ ' ',['-'] = '-' ^ ' '
    };

    for (size_t i = 0; i < len; ++i) {
        s[i] ^= table[((unsigned char *) s)[i]];
    }
}

static count *load_ht(FILE * stream)
{
    count *ht = NULL;

    /* Store the string keys in an arena private to this hash table. */
    sh_new_arena(ht);

    char chunk[CHUNK_SIZE];
    size_t offset = 0;

    while (true) {
        const size_t nread =
            fread(chunk + offset, 1, CHUNK_SIZE - offset, stream);

        if (ferror(stream)) {
            shfree(ht);
            return NULL;
        }

        if (nread + offset == 0) {
            break;
        }

        /* Search for last white-space character in chunk and process up to there. */
        /* Can we replace this with a library function? */
        size_t curr_chunk_end;

        for (curr_chunk_end = nread + offset - 1; curr_chunk_end != SIZE_MAX;
            --curr_chunk_end) {
            const unsigned char c = (unsigned char) chunk[curr_chunk_end];

            if (isspace(c)) {
                break;
            }
        }

        /* How can we iterate the chunk just once? */
        const size_t curr_chunk_size =
            curr_chunk_end != SIZE_MAX ? curr_chunk_end : nread + offset;

        replace_punctuation(curr_chunk_size, &chunk[0]);

        size_t i = 0;

        while (true) {
            /* Malformed input? Perhaps add a check and make the program slower,
             * or give the user what it deserves. */
            char word[LONGEST_WORD];
            size_t word_len = 0;

            while (isspace((unsigned char) chunk[i])) {
                ++i;
            }

            const size_t start = i;

            /* Profiling showed that much of the time is spent in this loop. */
            for (; i < curr_chunk_size && !isspace((unsigned char) chunk[i]);
                ++i) {
                word[word_len++] = (char) tolower((unsigned char) chunk[i]);
            }

            if (i == start) {
                break;
            }

            word[word_len] = '\0';

            /* Skip words beginning with a digit. */
            if (!isdigit((unsigned char) word[0])) {
                /* Strip possessive nouns. */
                if (word_len >= 2 && word[word_len - 1] == 's'
                    && word[word_len - 2] == '\'') {
                    word[word_len - 2] = '\0';
                } else if (word[word_len - 1] == '\'') {
                    word[word_len - 1] = '\0';
                }

                const size_t new_count = shget(ht, word);

                shput(ht, word, new_count + 1U);
            }
        }

        /* Move down remaining partial word. */
        if (curr_chunk_end != SIZE_MAX) {
            offset = (nread + offset - 1) - curr_chunk_end;
            memmove(chunk, chunk + curr_chunk_end + 1, offset);
        } else {
            offset = 0;
        }
    }

    return ht;
}

int main(void)
{
    count *ht = load_ht(stdin);

    if (!ht) {
        perror("fread()");
        return EXIT_FAILURE;
    }

    size_t ht_len = shlenu(ht);

    /* Profiling the code didn't show malloc()/mmap()/brk()/sbrk() to be a 
     * bottleneck.
     */
    count **const ordered = malloc(sizeof *ordered * ht_len);
    int rv = EXIT_FAILURE;

    if (!ordered) {
        goto cleanup;
    }

    for (size_t i = 0; i < ht_len; ++i) {
        ordered[i] = malloc(sizeof **ordered);

        if (!ordered[i]) {
            while (i) {
                free(ordered[i--]);
            }
            goto cleanup;
        }

        ordered[i]->key = ht[i].key;
        ordered[i]->value = ht[i].value;
    }

    qsort(ordered, ht_len, sizeof *ordered, cmp_func);

    for (size_t i = 0; i < ht_len; ++i) {
        printf("%-*s\t%zu\n", LONGEST_WORD, ordered[i]->key, ordered[i]->value);
        free(ordered[i]);
    }

    rv = EXIT_SUCCESS;

  cleanup:
    free(ordered);
    shfree(ht);
    return rv;
}

The program has 127 LOC (excluding stb_ds.h), and the final executable (stripped) sizes around 19 KB.

And this is how it performed:

» time ./wordfreq < kjvbible_10.txt 1> /dev/null   
./wordfreq < kjvbible_10.txt > /dev/null  2.39s user 0.10s system 99% cpu 2.507 total

-----------------------------------------------------------------------------------
» time wc kjvbible_10.txt
  998170  8211330 43325060 kjvbible_10.txt
wc kjvbible_10.txt  1.12s user 0.02s system 98% cpu 1.156 total

Review Goals:

• How can the total running time be reduced? What's a better algorithm for processing the file?
• Does any part of my code invokes undefined behavior? Have I missed any edge-cases?
• General coding comments, style, et cetera.

Answer 1

Some subtle concerns.

Same but different

This is an advanced concern that involves portability.

Consider an output where multiple words have the same frequency as with input "the the the foo defenestration foo defenestration foo defenestration". A result of

the 3
foo 3
defenestration 3

would be just as valid as:

defenestration 3
foo 3
the 3

Recall that the specification details of qsort() do not specify the sub-order when the compare returns 0. Not all qsort() sort these equal cases in the same order.

Within a given compiler this is not a issue, yet consider that you are tasked with maintaining code across 10 platforms/compilers and the results were different, yet compliant, as above.

This situation occurred in my career and became a nightmare for our test engineer whose job was to verify equivalent functionality across the multiple platforms/compilers. It was not sufficient to simply compare for identical output, but manual analyses was done.

For OP, cmp_func() could be augmented to differentiate when a, b point to the same .value.

static int cmp_func_alt(const void *a, const void *b) {
    const count *const p = *(const count * const *) a;
    const count *const q = *(const count * const *) b;

    // return (p->value < q->value) - (p->value > q->value);
    int cmp = (p->value < q->value) - (p->value > q->value);
    if (cmp == 0) {
      cmp = (p < q) - (p > q);  // Compare pointers
    }
    return cmp;
}

Similar problems occurred with stricmp() and rand().

stricmp() would convert to upper case and compare on some systems and convert to lower case then compare on others. This made _ before A on some systems and after Z on others, thus affecting the sorted order of strings. This was solved with rolling our own portable stricmp() code which outperformed some systems' stricmp() due to a little "trick".

rand() (this function varied a great deal per systems) was replaced with a superior yet consistent PRNG routine.

---

Pedantic: Access char data consistently

With C2X, this will not likely be a concern.

OP's code uses 2 ways to access char data. Best to use the same.
With char * s, is the following always true?

*((unsigned char *) s) == (unsigned char) *s

It differs when char is signed and negative values are not encoded with 2's compliment.

<string.h> functions access char via unsigned char * and so I recommend this model.

For all functions in this subclause, each character shall be interpreted as if it had the type unsigned char (and therefore every possible object representation is valid and has a different value). C23dr § 7.26.1 4

Answer 2

The code looks clean and structured. It's something I'd enjoy working with, so this is fine. Of course, there are a few things that could be changed, so let's dive into these...

Cleanup On Termination

This cleanup makes memory debuggers happy, but it is completely unnecessary for the program itself. You must flush and close the output file (which is stdout, so there's nothing to do for your), but releasing memory isn't necessary. If lots of fragmented memory shards are used, that may well cause noticeable overhead.

Naming

There is a variable named offset, but it isn't really clear what it means. It is some offset into the buffer, but is it the number of available or used chars?

Separation Of Concerns

At some central point, I would expect a loop like this in pseudocode:

while (word = read_word_from_file())
    process_word(word)

Reading should return a NUL-terminated string. You can get that easily by replacing whitespace and interpunction with NUL bytes in the read buffer. Also, that function could already lowercase the input. Reading should automatically fetch new data from the file if necessary. Putting this into a separate function also allows testing it in isolation.

Processing the input can also be isolated for the same reasons. There isn't really that much to do there, just increment the according counter in the dict.

Maintaining Position vs. Sorting

If you maintain a linked list of words and their frequency, each time you encounter a word, it might need to be moved to an adjacent position, depending on the neighbor's frequency. This might actually be faster than sorting after processing all words. I honestly don't think it will though, because sorting algos are highly optimized and efficient already. Also, maintaining an order must be done for every word, while sorting only needs to be done for every different word.

Nesting

There is a section of code titled "Skip words beginning with a digit.", which doesn't do that. Actually, that section handles words that don't begin with a digit. It would be easier to not nest here and instead use break for words with digits.

unsigned char Casts

There is a bazillion of (unsigned char) casts, which are also necessary. However, I wonder if it wouldn't be easier to use a buffer of unsigned char instead.

Undefined Behaviour

As far as I can tell, none. I'm sure you compiled with warnings enabled and that you also ran the code using e.g. Valgrind or similar tools.

Scanning For The Last Word

There is a loop that counts down from the end while curr_chunk_end != SIZE_MAX. I don't think that is correct. You could well have just a single, short (< SIZE_MAX) word left in the buffer, who's end you wouldn't find.