K&R Exercise 1-19. Reverse program input one line at a time

Question

Intro

I'm going through the K&R book (2nd edition, ANSI C ver.) and want to get the most from it: learn (outdated) C and practice problem-solving at the same time. For that reason, I'm trying to solve the exercises "hardcore" - without using any knowledge from the "future". I'll catch-up with it after I finish the book.

I believe that the author's intention was to give the reader a good exercise, to make the reader think hard about what he can do with the tools introduced, and not to skip ahead to find an easier way. For that reason, I'm only using language features introduced up to this point in the book. That also means I'm using an old C standard.

Compiling with gcc -Wall -Wextra -Wconversion -pedantic -ansi.

K&R Exercise 1-19

Write a function reverse(s) that reverses the character string s. Use it to write a program that reverses its input a line at a time.

Solution

The task explicitly states how the function should look like. For that reason, I've coded it similarly to how the author made his copy function.

The 2nd part of the challenge is to reverse the program input a line at a time, but how long can the line be? It would be too easy to set a hard limit for line length, just loop line by line and return an error if it's exceeded. I can't use dynamic memory allocation to deal with arbitrary long lines since it hasn't been introduced yet so what's left? The book already introduced all the building blocks I need for recursion, so at this point it the only solution.

Code

/* Exercise 1-19. Write a function `reverse(s)` that reverses the
 * character string `s`. Use it to write a program that reverses its
 * input a line at a time. */

#include <stdio.h>
#define BUFSIZE 10 /* line buffer size */

int getline(char line[], int maxline);
void copy(char to[], char from[]);
void reverse(char s[]);
int reverseinput(char lastchar[]);

main()
{
    char lastchar[1];

    while (reverseinput(lastchar) != 0)
        if (lastchar[0] == '\n')
            putchar('\n');
    return 0;
}

/* reverseinput: read from input until end of line is reached and then
 * print the line in reverse */
int reverseinput(char lastchar[])
{
    int len;
    char line[BUFSIZE];
    int retval;

    if ((len = getline(line, BUFSIZE)) > 0) {
        if ((lastchar[0] = line[len-1]) == '\n') {
            line[len-1] = '\0';
            retval = 1;
        }
        else
            retval = reverseinput(lastchar);
        reverse(line);
        printf("%s", line);
    }
    else
        retval = 0;
    return retval;
}

/* getline: read a line into s, return length */
int getline(char s[],int lim)
{
    int c, i;

    for (i=0; i < lim-1 && (c=getchar())!=EOF && c!='\n'; ++i)
        s[i] = c;
    if (c == '\n') {
        s[i] = c;
        ++i;
    }
    s[i] = '\0';
    return i;
}

/* copy: copy 'from' into 'to'; assume to is big enough */
void copy(char to[], char from[])
{
    int i;

    i = 0;
    while ((to[i] = from[i]) != '\0')
        ++i;
}

/* reverse: reverse a '\0' terminated string */
void reverse(char s[])
{
    int tail;
    int head;
    char c;

    /* find the last character index */
    tail = 0;
    while (s[tail] != '\0')
        ++tail;
    if (tail > 0)
        --tail;
    /* reverse the string by swapping first and last elements */
    for (head = 0; head < tail; ++head && --tail) {
        c = s[head];
        s[head] = s[tail];
        s[tail] = c;
    }
}

Test

Running $ ./ch1-ex-1-19-01 <ch1-ex-1-19-01.c | ./ch1-ex-1-19-01 prints the program code :)

Answer 1

Performance

• Avoid recursion like the plague. It is dangerous, it is slow, it leads to greater stack peak use, it is often hard to read. In your case, you don't have tail recursion so the compiler is not likely able to optimize away the recursion with a loop.

  There is almost never a reason to use recursion outside algorithm theory and when designing ADTs with very specific requirements.

Style/best practices

• Always use { } after every control/loop statement, even if the following is only one line. Using this style consistently will prevent you from writing numerous bugs.

• Assignment inside if/loop control expressions should be avoided, as it is dangerous and sometimes makes the code harder to read. For example if you would be tempted to change while ((to[i] = from[i]) != '\0') ++i; to while ((to[i] = from[i++]) != '\0') then you suddenly have a severe bug caused by your (K&R's) coding style.

  In addition, if you never use assignment inside control expressions, you don't have to worry about = vs ==. Most compilers warn against assignment for this reason.

  Alternative code:

  for(i=0; from[i] != '\0'; i++)
  {
    to[i] = from[i];
  }
  to[i] = '\0';
  

• Similarly, try to keep loops and expressions simple, by splitting them over several lines. Code such as for (i=0; i < lim-1 && (c=getchar())!=EOF && c!='\n'; ++i) is hard to read and maintain. This could be rewritten to for example

  for (int i=0; i < lim-1; ++i)
  {
    c=getchar();
    if(c==EOF || c=='\n')
    {
      break;
    }
    s[i] = c;
  }
  

  which means the same and results in exactly the same machine code. But it is multiple times easier to read.

• The most correct type to use for array/string sizes is size_t and not int. This is an unsigned type used by all standard library functions and also what the sizeof operator returns.
• The line ++head && --tail) is just weird, this shouldn't be a boolean condition. Replace it with the comma operator: ++head, --tail).

Modern standard C remarks

• The form of main you should use (on hosted systems) is int main (void). Functions relying on implicit int are not standard.
• Declare the loop iterator i (i stands for iterator) inside for loops, unless you actually intend to use it once the loop is done. A common source for bugs in C90 code was that the same i was re-used between loops, potentially carrying garbage values with it.
• Don't use 1 and 0 for function results, use bool with true/false.
• // line comments are very handy.

Other issues

• The function getline exists as part of POSIX. It is not a standard C function, but the name might collide on compilers where non-standard POSIX extensions are enabled, such as gcc -std=gnu90.

Answer 2

Minor:

getline()

When size is pathologically small (sz <= 1), if (c == '\n') { tests the uninitialized c leading to undefined behavior.

With sz <= 0, s[i] = '\0'; is not valid either.

I'd recommend to note the condition that sz > 1 is expected.

---

Further, I'd use size_t rather than int for the buffer size and re-code to handle those edge cases.

size_t getline(char s[], size_t sz) {
    int c = 0;
    size_t i;

    for (i=0; i + 1 < sz && (c=getchar())!='\n' && c!=EOF; ++i) {
        s[i] = c;
    }
    if (c == '\n') {
        s[i] = c;
        ++i;
    }
    if (i < sz) {
      s[i] = '\0';
    }
    return i;
}

Answer 3

It's good practice to use prototypes for all functions, including main(). Don't rely on unspecified argument lists and on return type defaulting to int - which goes away in later standards:

int main(void)

---

It seems odd to use an length-1 array lastchar rather than a plain char:

int main(void)
{
    char lastchar;

    while (reverseinput(&lastchar) != 0)
        if (lastchar[0] == '\n')
            putchar('\n');
    return 0;
}

Similarly for lastchar within the function - treat it as a pointer to a single char (i.e. write *lastchar rather than lastchar[0], for instance).

Answer 4

Revised Solution

My intention was to use only language features introduced up to this point in the book but after receiving some comments I will make exceptions so that I will use new features only where it doesn't change the program logic.

Example is letting myself use a pointer because the author already introduced "by ref" logic for function arguments so I can write size_t reverseinput(char* lastchar); instead of int reverseinput(char lastchar[]);, using declarations inside for, using , operator because a dirty way to achieve its function has been introduced (&&), using explicit cast, using bool type because it's good practice etc.

Now compiling with gcc -Wall -Wextra -Wconversion -pedantic -std=c99.

Note that the break statement hasn't been introduced yet so I've rewritten the relevant part by using a state, which changes the logic a little.

Apart from avoiding break and having to use recursion, I think I've captured all the comments received.

Code

/* Exercise 1-19. Write a function `reverse(s)` that reverses the
 * character string `s`. Use it to write a program that reverses its
 * input a line at a time.
 */

/* Some improvements after comments received:
 * https://codereview.stackexchange.com/questions/206064/kr-exercise-1-19-reverse-program-input-one-line-at-a-time
 */

#include <stdio.h>
#include <stdbool.h>
#define BUFSIZE 10      // line buffer size

size_t getline(char line[], size_t maxsz);
void copy(char to[], char from[]);
void reverse(char s[]);
bool reverseinput(char lastchar[]);

int main(void)
{
    char lastchar;
    while (reverseinput(&lastchar) != 0) {
        if (lastchar == '\n') {
            putchar('\n');
        }
    }
    return 0;
}

/* reverseinput: read from input until end of line ('\n' or EOF) is
 * reached and then print the line in reverse, excluding the '\n';
 * keep track of the last character to detect EOF terminated line;
 * returns true if there's more of the input
 */
bool reverseinput(char* lastcharpt)
{
    size_t len;
    char line[BUFSIZE];
    bool retval;

    len = getline(line, BUFSIZE);
    if (len > 0) {
        *lastcharpt = line[len-1];
        if (line[len-1] == '\n') {
            // delete the '\n', we'll add it back to the end
            line[len-1] = '\0';
            retval = true;
        }
        else {
            retval = reverseinput(lastcharpt);
        }
        reverse(line);
        printf("%s", line);
    }
    else {
        retval = false;
    }
    return retval;
}

/* getline: read a line into `s`, return length;
 * `sz` must be >1 to accomodate at least one character and string
 * termination '\0'
 */
size_t getline(char s[], size_t sz)
{
    int c;
    size_t i = 0;
    bool el = false;
    while (i < sz-1 && el == false) {
        c = getchar();
        if (c == EOF) {
            el = true;
        }
        else {
            s[i] = (char) c;
            ++i;
            if (c == '\n') {
                el = true;
            }
        }
    }
    if (i < sz) {
        s[i] = '\0';
    }
    return i;
}

/* copy: copy a '\0' terminated string `from` into `to`;
 * assume `to` is big enough;
 */
void copy(char to[], char from[])
{
    size_t i;
    for (i = 0; from[i] != '\0'; ++i) {
        to[i] = from[i];
    }
    to[i] = '\0';
}

/* reverse: reverse a '\0' terminated string
 */
void reverse(char s[])
{
    // find the end of character array
    size_t tail = 0;
    while (s[tail] != '\0') {
        ++tail;
    }
    // move back to last character index
    if (tail > 0) {
        --tail;
    }
    // reverse the string by swapping first and last elements
    char c = 0;
    for (size_t head = 0; head < tail; ++head, --tail) {
        c = s[head];
        s[head] = s[tail];
        s[tail] = c;
    }
}