3
\$\begingroup\$

I write this program based on the algorithm of the word frequency counter program on the K&R book, page 139. I added some idioms of mine, some command-line options, and a dynamically allocable buffer.

Use it on stdin or give one or more file as arguments.
The option -k considers only keywords (beginning with _ or alphabetic character), and words consisting of symbols are ignored.
The option -w considers words as a string of characters separated by white space.

Here is the code:

#include <err.h>
#include <errno.h>
#include <stdio.h>
#include <ctype.h>
#include <string.h>
#include <stdlib.h>
#include <unistd.h>

/* the tree node */
struct tnode {
    char *word;            /* pointer to the text */
    unsigned long count;   /* number of occurrences */
    struct tnode *left;    /* left child */
    struct tnode *right;   /* right child */
};

static int exitval = EXIT_SUCCESS;;
static int spaceword = 0;
static int keyword = 0;
static char *buf = NULL;
static size_t bufsize = 0;

#define CHECKBUF(i)                                         \
    {if (bufsize == 0 || (i) >= bufsize - 1) {              \
        size_t newsize = bufsize + BUFSIZ;                  \
                                                            \
        if (newsize <= bufsize)    /* check for overflow */ \
            errc(EXIT_FAILURE, EOVERFLOW, "realloc");       \
        bufsize = newsize;                                  \
        if ((buf = realloc(buf, bufsize)) == NULL)          \
            err(EXIT_FAILURE, "realloc");                   \
    }}

static int getfreq(struct tnode **, FILE *);
static void putfreq(struct tnode *);
static void addtree(struct tnode **, char *);
static char *getword(FILE *);
static void usage(void);

/* word frequency count */
int
main(int argc, char *argv[])
{
    struct tnode *root = NULL;
    FILE *fp;
    int c;

    while ((c = getopt(argc, argv, "kw")) != -1) {
        switch (c) {
        case 'k':
            keyword = 1;
            break;
        case 'w':
            spaceword = 1;
            break;
        default:
            usage();
            break;
        }
    }
    argc -= optind;
    argv += optind;

    if (argc == 0) {
        if (getfreq(&root, stdin) == -1)
            err(EXIT_FAILURE, "stdin");
    } else {
        while (*argv) {
            if ((fp = fopen(*argv, "r")) == NULL) {
                warn("%s", *argv);
                exitval = EXIT_FAILURE;
            } else {
                if (getfreq(&root, fp) == -1) {
                    warn("%s", *argv);
                    exitval = EXIT_FAILURE;
                }
                fclose(fp);
            }
            argv++;
        }
    }
    free(buf);
    putfreq(root);

    if (ferror(stdout))
        err(EXIT_FAILURE, "stdout");

    return exitval;
}

/* print the frequency of each word in tree */
static void
putfreq(struct tnode *tree)
{
    if (tree != NULL) {
        putfreq(tree->left);
        if (printf("%7lu %s\n", tree->count, tree->word) < 0)
            err(EXIT_FAILURE, "stdout");
        free(tree->word);
        putfreq(tree->right);
        free(tree);
    }
}

/* populate tree with the frequences of words in fp; return -1 on error on fp */
static int
getfreq(struct tnode **tree, FILE *fp)
{
    char *buf;

    while ((buf = getword(fp)) != NULL)
        if (!keyword || (keyword && (*buf == '_' || isalpha(*buf))))
            addtree(tree, buf);

    if (ferror(fp))
        return -1;

    return 1;
}

/* add a node with w, at or below p */
static void
addtree(struct tnode **p, char *w)
{
    int cond;

    if (*p == NULL) {    /* if a new word has arrived, make a new node */
        *p = malloc(sizeof **p);
        if (*p == NULL)
            err(EXIT_FAILURE, "malloc");
        if (((*p)->word = strdup(w)) == NULL)
            err(EXIT_FAILURE, "strdup");
        (*p)->count = 1;
        (*p)->left = (*p)->right = NULL;
    } else if ((cond = strcmp(w, (*p)->word)) == 0) { /* repeated word */
        (*p)->count++;
    } else if (cond < 0) {              /* less than into left subtree */
        addtree(&((*p)->left), w);
    } else if (cond > 0) {          /* greater than into right subtree */
        addtree(&((*p)->right), w);
    }
}

/* get next word from fp; if fp is NULL, free buffer and return null */
static char *
getword(FILE *fp)
{
    size_t i = 0;
    int c;

    while (isspace(c = getc(fp)))
        ;

    if (c == EOF)
        return NULL;

    if (spaceword) {
        while (!isspace(c)) {
            CHECKBUF(i);
            buf[i++] = c;
            c = getc(fp);
        }
        goto done;
    }

    if (c == '_' || isalpha(c)) {
        while (c == '_' || isalnum(c)) {
            CHECKBUF(i);
            buf[i++] = c;
            c = getc(fp);
        }
        ungetc(c, fp);
        goto done;
    }

    while (c != '_' && !isalpha(c) && c != EOF && !isspace(c)) {
        CHECKBUF(i);
        buf[i++] = c;
        c = getc(fp);
    }
    ungetc(c, fp);

done:
    buf[i] = '\0';
    return buf;
}

/* show usage */
static void
usage(void)
{
    (void)fprintf(stderr, "usage: wfreq [-kw] [file...]\n");
    exit(EXIT_FAILURE);
}

Here is an example of using wfreq(1) (the name I gave to this word frequency counter) on its own source code, with the option -k:

      1 BUFSIZ
      4 CHECKBUF
      2 EOF
      1 EOVERFLOW
     10 EXIT_FAILURE
      1 EXIT_SUCCESS
      5 FILE
     12 NULL
      4 _
      3 a
      1 add
      5 addtree
      1 and
      4 argc
      8 argv
      1 arrived
      1 at
      1 below
      3 break
     14 buf
      1 buffer
      7 bufsize
     23 c
      2 case
      8 char
      1 check
      2 child
      4 cond
      5 count
      1 ctype
      1 default
      1 define
      3 done
      1 each
      5 else
      7 err
      1 errc
      1 errno
      1 error
      1 exit
      4 exitval
      1 fclose
      2 ferror
      1 file
      1 fopen
      1 for
     18 fp
      1 fprintf
      4 free
      1 frequences
      2 frequency
      1 from
      1 get
      4 getc
      4 getfreq
      1 getopt
      3 getword
      2 goto
      1 greater
      7 h
      1 has
     10 i
     23 if
      2 in
      7 include
     10 int
      2 into
      1 is
      1 isalnum
      3 isalpha
      3 isspace
      1 k
      4 keyword
      2 kw
      6 left
      1 less
      1 long
      1 lu
      1 main
      1 make
      2 malloc
      2 n
      2 new
      3 newsize
      1 next
      3 node
      1 null
      1 number
      1 occurrences
      3 of
      2 on
      2 optind
      1 or
      1 overflow
     14 p
      1 pointer
      1 populate
      1 print
      1 printf
      5 putfreq
      1 r
      3 realloc
      1 repeated
      7 return
      6 right
      4 root
      3 s
      1 show
      3 size_t
      1 sizeof
      3 spaceword
     15 static
      1 stderr
      2 stdin
      1 stdio
      1 stdlib
      3 stdout
      1 strcmp
      2 strdup
      1 string
     10 struct
      2 subtree
      1 switch
      1 text
      2 than
      4 the
     10 tnode
      1 to
     13 tree
      2 ungetc
      1 unistd
      1 unsigned
      5 usage
      9 void
      7 w
      2 warn
      1 wfreq
      7 while
      2 with
     10 word
      1 words
\$\endgroup\$
2
\$\begingroup\$

Overall Impression

This code would be difficult to maintain especially if someone else had to pick up where the original coder had left off. This due primarily to the use of macros, multiple goto's and global variables.

A second consideration is that as the program uses more memory to contain the buffer, performance might be impacted.

A third consideration also about the performance is that the program will perform better if it reads a large block of text from the input file and then processes that text using string or character manipulation rather then using charater based input.

Global Variables

Even though the variables the global namespace is protected from the variables exitval, spaceword, keyword, buf and bufsize by the use of static, programming within the file is still using the variables as global variables. This makes the code harder to write, read and debug because without searching the whole program it's not clear where the variables are modified. Use local variables whenever possible, and pass necessary information into functions as needed.

Use of Macros

It's clear why the code has a macro (CHECKBUF) in it, it is to reduce code repetition which is good, however, it would be better to use a function rather than a macro. One of the drawbacks of using macros is that they are very difficult to debug because the code in them is not expanded in the debugger. Another drawback is that they tend to hide things if memory allocation , goto's or exit() statements are in them, this code has 2 out of 3 of those hidden items in the macro.

Portability

The C programming language is very portable as long as the C programming standard is followed, and not some other standard such as POSIX. Two of the header files in this code (err.h and unistd.h) are not portable to Windows with out additional work being done to port that code or the associated libraries.

More portable code would write error messages and warning messages to stderr and not use err(), warn() or errc(). You could write your own portable library that recreates these functions, it might be a very good learning experience that you could share here on code review.

Another library function you could consider writing because it isn't portable is getopt(). I think this might even be a better learning experience.

The Use of Goto's

There is sometimes a need to use goto's in error handling code, but that is pretty rare. To use multiple goto's for flow control in a function is to return to the original versions of BASIC and FORTRAN which didn't have many of the modern programming constructs. This used to be known as speghetti code. Blocks of code can be nested inside if statements, if the blocks of code ae too large or complex they can become functions. In the C programming language the break; statement can be used to exit a logic block. In the case of the getword() function perhaps it would be better to have it call two function that process the text, one for the -k switch and one for the -w switch.

\$\endgroup\$
8
  • \$\begingroup\$ Detail: "err.h and unistd.h) are not portable to Windows". I just compiled code with #include <err.h> #include <unistd.h> on my Windows PC. The limitations is not an OS one. It is a compiler one. Perhaps you are thinking of VS? \$\endgroup\$ – chux - Reinstate Monica May 7 '20 at 3:34
  • \$\begingroup\$ @chux-ReinstateMonica Well since I have to be able to compile C# and .Net for consulting reasons, yes it is VS, however, before I posted my answer I have checked and neither one of the files are in the C programming standard, they are POSIX. Non of my Linux machine are working at the moment. \$\endgroup\$ – pacmaninbw May 7 '20 at 11:55
  • \$\begingroup\$ On the global variables: exitval has to be global, since it should be modified every time a warning occurs. spaceword and keyword are flags, I could pass then as a single bit set variable as argument to getfreq(). buf and bufsize could be static on getword but then, how would I free(3) buf at the end of main? \$\endgroup\$ – phillbush May 7 '20 at 12:21
  • \$\begingroup\$ Take a good look at the usage of exitval the only place it is used is in main(). \$\endgroup\$ – pacmaninbw May 7 '20 at 12:34
  • 1
    \$\begingroup\$ @barthooper CHECKBUF(i) could replaced with if (i + 1 >= bufsize) checkcode(i, &bufsize, &buf);. Since the if() is seldom true, the function overhead is not significant. \$\endgroup\$ – chux - Reinstate Monica May 7 '20 at 13:35
1
\$\begingroup\$

Some ideas:

Alternative code

// if (bufsize == 0 || (i) >= bufsize - 1)
if ((i) + 1 >= bufsize)

UB when *buf < 0

is...(ch) functions defined for ch in the unsigned char range and EOF.

// isalpha(*buf)
isalpha((unsigned char) *buf)

Help

Too bad usage() does not include option detail like

The option -k considers only keywords (beginning with _ or alphabetic character), and words consisting of symbols are ignored.
The option -w considers words as a string of characters separated by white space.

Creeping feature

Option for output sorted by usage.

Alt code: star reduction

To change most of the (*p) to a tidy tn, consider:

//                                      v--- I'd expect a const
// static void addtree(struct tnode **p, char *w) {
static void addtree(struct tnode **p, const char *w) {
  int cond;
  struct tnode *tn = *p;
  if (tn == NULL) { /* if a new word has arrived, make a new node */
    *p = tn = malloc(sizeof *tn);
    if (tn == NULL)
      err(EXIT_FAILURE, "malloc");
    if ((tn->word = strdup(w)) == NULL)
      err(EXIT_FAILURE, "strdup");
    tn->count = 1;
    tn->left = tn->right = NULL;
  } else if ((cond = strcmp(w, tn->word)) == 0) { /* repeated word */
    tn->count++;
  } else if (cond < 0) { /* less than into left subtree */
    addtree(&(tn->left), w);
  } else if (cond > 0) { /* greater than into right subtree */
    addtree(&(tn->right), w);
  }
}

Reduced allocations by 2 idea

Since allocation of a node always occurs with a string: research Flexible array member and do both in one allocation.

struct tnode {
    unsigned long count;   /* number of occurrences */
    struct tnode *left;    /* left child */
    struct tnode *right;   /* right child */
    char word[];           /* text array*/    // FAM
};

*p = malloc(sizeof **p + strlen(w) + 1);
\$\endgroup\$
2
  • \$\begingroup\$ "if ((i) + 1 >= bufsize)" I was using it in a previous version, but then I thought on the case that (i) + 1 overflow and be less than bufsize and then I decided to check for bufsize == 0 first. \$\endgroup\$ – phillbush May 7 '20 at 12:19
  • \$\begingroup\$ "Reduced allocations by 2 idea": but then I would have to check for overflow for the sum of the three operands, which would make the code more complex. \$\endgroup\$ – phillbush May 7 '20 at 12:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.