Control flow · about 55 min

Processing input until end of file

Why this matters

A huge class of useful programs read some input, transform it, and write output: wc, grep, sort, sed, compilers, log analyzers. On Unix they are called filters, and they are designed to be chained with pipes (cat log | grep error | wc -l). A filter cannot know in advance how much input is coming. It reads until the input runs out, a condition called end of file. Getting that loop right is a small piece of code that you will write over and over, and it has two classic traps.

Standard input, redirection and pipes

Every process starts with three open streams: standard input (stdin), standard output (stdout) and standard error (stderr). By default stdin is the keyboard and stdout the terminal, but the shell can connect them elsewhere without the program knowing:

$ ./prog                    # stdin from the keyboard
$ ./prog < notes.txt        # stdin from a file
$ ls -l | ./prog            # stdin from another program's output
$ ./prog < in.txt > out.txt # and stdout to a file

Your program reads stdin the same way in every case. "End of file" means: the file has no more bytes, or the program writing into the pipe has finished, or, at the keyboard, the user pressed Ctrl+D at the start of a line. (Ctrl+D is not a character that gets read; it tells the terminal to report end of input.)

getchar, putchar and EOF

getchar() reads one byte from stdin and returns it as an int in the range 0 to 255. When there is nothing more to read, it returns the special value EOF, a macro from <stdio.h> that is -1 on Linux. putchar(c) writes one byte to stdout.

The canonical loop copies input to output:

#include <stdio.h>

int main(void)
{
    int c;
    while ((c = getchar()) != EOF)
        putchar(c);
    return 0;
}

The condition does three things in one expression, which is why it looks dense at first:

   ( c = getchar() )  != EOF
     |    |                 |
     |    1. read a byte    |
     2. store it in c       |
     3. the value of the assignment is the stored value; compare it with EOF

The extra parentheses around the assignment are required: != binds more tightly than =, so c = getchar() != EOF would store the comparison result (0 or 1) in c.

A small change gives a counting program:

int c;
long chars = 0, lines = 0;
while ((c = getchar()) != EOF) {
    chars++;
    if (c == '\n')
        lines++;
}
printf("%ld lines, %ld characters\n", lines, chars);

$ printf 'one two\nthree\n' | ./prog
2 lines, 14 characters

(long and %ld are used so the counts cannot overflow on big inputs.)

What is underneath: buffering

Calling the kernel once per byte would be very slow. Instead, stdin has a buffer inside your process. The first getchar asks the kernel for a large chunk (typically 4096 bytes, or one line at a terminal) with a single read system call; later getchar calls just hand out bytes from the buffer until it is empty. Output is buffered the same way: putchar adds to a buffer that is written out when it fills, at a newline (for a terminal), or when the program exits.

  kernel  --read(4096 bytes)-->  [ stdin buffer: o n e   t w o \n t h r e e \n ]
                                   ^
                                   getchar() returns the next byte from here

That is why character-at-a-time loops in C are fast, and why at the keyboard your program sees nothing until you press Enter: the terminal delivers a whole line at a time.

Character classification: ctype.h

<ctype.h> provides functions to classify and convert characters. They take an int (a getchar result or EOF) and return nonzero for true:

function	true for
`isspace(c)`	space, `\t`, `\n`, `\r`, `\v`, `\f`
`isdigit(c)`	`0` to `9`
`isalpha(c)`	letters
`isalnum(c)`	letters and digits
`isupper(c)`, `islower(c)`	upper / lower case letters
`toupper(c)`, `tolower(c)`	convert case (other characters unchanged)

An uppercase filter is three lines:

int c;
while ((c = getchar()) != EOF)
    putchar(toupper(c));

$ echo "hello, world" | ./prog
HELLO, WORLD

Remembering where you are: state

Many filters need to remember something about what they have already seen. Counting words is the classic example: a word starts when a non-space character follows a space (or the start of input). One int flag is enough:

            non-space: words++            non-space: (nothing)
  OUTSIDE -------------------------> INSIDE ------+
     ^  |                              |   ^      |
     |  +-- space: (nothing)           |   +------+
     +---------------------------------+
                 space

This is a tiny state machine: the program is always in one of a few states, and each input character moves it between them. The exercises use this idea twice. State machines scale up to tokenizers, protocol parsers and regular expression engines.

Reading numbers until end of file

For numbers, use scanf and make its return value the loop condition, exactly as in the sentinel loop of the previous lesson:

int x;
long sum = 0;
while (scanf("%d", &x) == 1)
    sum += x;

scanf returns the number of items it converted: 1 on success, 0 if the next input is not a number (for example a letter), and EOF at end of input. Testing == 1 stops on both.

Common mistakes

Storing getchar's result in a char. On x86, char is signed, so the byte 0xFF becomes -1, equal to EOF. This copy loop stops early:

char c;                             /* BUG */
while ((c = getchar()) != EOF)
    putchar(c);

$ printf 'ab\xffcd\n' | ./prog | od -c
0000000   a   b

The bytes after 0xFF are lost. On platforms where char is unsigned (common on ARM), the loop instead never ends. Always use int.

Looping on feof. feof(stdin) becomes true only after a read has failed, so this loop runs one time too many:

while (!feof(stdin)) {              /* BUG */
    scanf("%d", &x);
    sum += x;
}

With input 10 20 30 it prints sum = 90: the final, failing scanf leaves x at 30, which is added again. Test the read itself.

Forgetting the parentheses: while (c = getchar() != EOF) sets c to 1 for every byte. gcc warns suggest parentheses around assignment used as truth value.

Waiting at the keyboard. If you run a filter with no redirection, it waits for you to type. Press Ctrl+D (on a new line) to send end of file, or Ctrl+C to abort.

Recap

Filters read stdin until end of file; the shell can connect stdin to a file (<) or a pipe (|) transparently.
while ((c = getchar()) != EOF) with int c is the standard byte loop; putchar writes bytes.
stdin and stdout are buffered, so byte-at-a-time code is still efficient.
<ctype.h> classifies and converts characters.
A flag variable turns a loop into a state machine (inside a word, at the start of a line).
Never store getchar's result in a char, and never loop on feof; test the read itself.

Going further: compare your word counter from the exercises with the real thing: printf 'the quick brown\n fox jumps\n' | wc. Read man 3 getchar and man 3 isalpha.

Exercises

Exercise 1 · quiz

Why int c?

Why does the standard idiom declare int c; rather than char c; in while ((c = getchar()) != EOF)?

Because getchar is faster when it returns an int
Because getchar must be able to return every possible byte value (0 to 255) plus one extra, distinct value, EOF, and a char cannot hold 257 different values
Because char variables cannot be compared with !=
It makes no difference; char works the same way

Answer

Because getchar must be able to return every possible byte value (0 to 255) plus one extra, distinct value, EOF, and a char cannot hold 257 different values

getchar returns the byte it read as an unsigned char value converted to int (0 to 255), or EOF (which is -1 on glibc) when there is no more input. That is 257 possible results. If you store the result in a char, two of them collapse into one: on x86, where char is signed, the byte 0xFF becomes -1 and looks exactly like EOF, so the loop stops early on binary data or some non-ASCII text. Where char is unsigned, EOF becomes 255 and never compares equal to -1, so the loop never ends.

Exercise 2 · write code

A tiny wc

Read all of standard input with getchar and print one line with the number of lines, words and characters, in this format:

lines=2 words=5 chars=28

characters: every byte read, including newlines;
lines: the number of newline characters;
words: maximal runs of characters that are not whitespace. Use isspace(c) from <ctype.h> to test for whitespace (space, tab, newline and a few others).

For example the input the quick brown\n fox jumps\n has 2 lines, 5 words and 28 characters.

File: main.c

Starting point

#include <stdio.h>
#include <ctype.h>

int main(void)
{
    int c;
    long lines = 0, words = 0, chars = 0;
    int in_word = 0;   /* 1 while we are inside a word */
    while ((c = getchar()) != EOF) {
        chars++;
    }
    printf("lines=%ld words=%ld chars=%ld\n", lines, words, chars);
    return 0;
}

Example

input

the quick brown
  fox jumps

expected output

lines=2 words=5 chars=28

Example

expected output

lines=0 words=0 chars=0

Hint 1

Count a line every time c == '\n'.

Hint 2

A word starts when you see a non-space character while in_word is 0. Count it then and set in_word = 1.

Hint 3

Any whitespace character sets in_word back to 0.

Reference solution

#include <stdio.h>
#include <ctype.h>

int main(void)
{
    int c;
    long lines = 0, words = 0, chars = 0;
    int in_word = 0;   /* 1 while we are inside a word */
    while ((c = getchar()) != EOF) {
        chars++;
        if (c == '\n')
            lines++;
        if (isspace(c)) {
            in_word = 0;
        } else if (!in_word) {
            in_word = 1;
            words++;
        }
    }
    printf("lines=%ld words=%ld chars=%ld\n", lines, words, chars);
    return 0;
}

Exercise 3 · write code

Number the lines

Write a filter that copies standard input to standard output, putting the line number, a colon and a space in front of every line, like this:

1: first line
2: second line

Work character by character with getchar and putchar (or printf for the number); do not assume any maximum line length. A final line without a trailing newline still gets a number (and you should not add a newline that was not there). Empty input produces no output.

File: main.c

Starting point

#include <stdio.h>

int main(void)
{
    int c;
    while ((c = getchar()) != EOF) {
        putchar(c);
    }
    return 0;
}

Example

input

first line
second line

expected output

1: first line
2: second line

Example

input

a
b

expected output

1: a
2: b

Hint 1

You cannot print the number when you see a newline, because there may be no next line. Print it when the first character of a line arrives.

Hint 2

Keep a flag at_start that is 1 at the beginning and is set to 1 again after each newline.

Hint 3

When at_start is 1 and a character arrives: increment the counter, print "%d: ", clear the flag, then print the character.

Reference solution

#include <stdio.h>

int main(void)
{
    int c;
    int line = 0;
    int at_start = 1;   /* the next character begins a new line */
    while ((c = getchar()) != EOF) {
        if (at_start) {
            line++;
            printf("%d: ", line);
            at_start = 0;
        }
        putchar(c);
        if (c == '\n')
            at_start = 1;
    }
    return 0;
}

Exercise 4 · quiz

The feof trap

Given the input lines 10, 20, 30, this program prints sum = 90. Why?

int x, sum = 0;
while (!feof(stdin)) {
    scanf("%d", &x);
    sum += x;
}
printf("sum = %d\n", sum);

scanf reads the last number twice
feof only becomes true after a read has already failed, so the loop runs one extra time; that scanf fails, x keeps its old value 30, and 30 is added again
feof(stdin) is true before the last line is read, so the loop skips 30
It is undefined behavior and 90 is a random result

Answer

feof only becomes true after a read has already failed, so the loop runs one extra time; that scanf fails, x keeps its old value 30, and 30 is added again

feof does not predict the future: it reports that a previous read hit end of file. After 30 is read, no read has failed yet, so the loop goes around again; scanf finds end of file and returns EOF without touching x, and the stale 30 is added a second time. The fix is to make the read itself the loop condition: while (scanf("%d", &x) == 1). The same goes for getchar: test its return value, not feof.