5
\$\begingroup\$

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. I believe that the author's intention was to give the reader a good exercise, to make him think hard about what he can do with the tools introduced, so I'm sticking to program features introduced so far and using "future" features and standards only if they don't change the program logic.

Compiling with gcc -Wall -Wextra -Wconversion -pedantic -std=c99.

K&R Exercise 1-18

Write a program to remove trailing blanks and tabs from each line of input, and to delete entirely blank lines.

Solution

My solution reuses functions coded in the previous exercises (getline & copy) and adds a new function size_t trimtrail(char line[]); to solve the problem. For lines that can fit in the buffer, the solution is straightforward. However, what if they can't? The main routine deals with that.

Since dynamic memory allocation hasn't been introduced, I don't see a way to completely trim arbitrary length lines. Therefore, solution does the next best thing: trim the ends, and signal whether there's more job to be done. This way, the shell can re-run the program as many times as necessary to finish the job.

Code

/* Exercise 1-18. Write a program to remove trailing blanks and tabs
 * from each line of input, and to delete entirely blank lines.
 */

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

size_t getline(char line[], size_t sz);
void copy(char to[], char from[]);
size_t trimtrail(char line[]);

int main(void)
{
    size_t len;             // working length
    size_t nlen;            // peek length
    size_t tlen;            // trimmed length
    char line[BUFSIZE];     // working buffer
    char nline[BUFSIZE];    // peek buffer
    bool istail = false;
    bool ismore = false;

    len = getline(line, BUFSIZE);
    while (len > 0) {
        if (line[len-1] == '\n') {
            // proper termination can mean either a whole line, or end
            // of one
            tlen = trimtrail(line);
            if (istail == false) {
                // base case, whole line fits in the working buffer
                // print only non-empty lines
                if (line[0] != '\n') {
                    printf("%s", line);
                }
            }
            else {
                // long line case, only the tail in the working buffer
                printf("%s", line);
                if (len != tlen) {
                    // we couldn't keep the whole history so maybe more
                    // blanks were seen which could not be processed;
                    // run the program again to catch those
                    ismore = true;
                }
            }
            // this always gets the [beginning of] next line
            len = getline(line, BUFSIZE);
            istail = 0;
        }
        else {
            // if it was not properly terminated, peek ahead to
            // determine whether there's more of the line or we reached
            // EOF
            nlen = getline(nline, BUFSIZE);
            if (nlen > 0) {
                if (nline[0]=='\n') {
                    // if next read got us just the '\n'
                    // we can safely trim the preceding buffer
                    tlen = trimtrail(line);
                    if (tlen > 0) {
                        printf("%s", line);
                        if (len != tlen)
                            ismore = 1;
                    }
                }
                else {
                    // if still no '\n', we don't know if safe to trim
                    // and can only print the preceding buffer here
                    printf("%s", line);
                }
                // we didn't yet process the 2nd buffer so copy it into
                // 1st and run it through the loop above
                len = nlen;
                copy(line, nline);
                istail = 1;
            }
            else {
                // EOF reached, peek buffer empty
                // means we can safely trim the preceding buffer
                tlen = trimtrail(line);
                if (tlen > 0) {
                    if (line[0]!='\n') {
                        printf("%s", line);
                    }
                    else {
                        ismore = 1;
                    }
                }
                if (len != tlen) {
                    ismore = 1;
                }
                // and we don't need to run the loop anymore, exit here
                len = 0;
            }
        }
    }
    // if there were too long lines, we could not trim them all;
    // signal to the environment that more runs could be required
    return ismore;
}

/* getline: read a line into `s`, return string 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';
}

/* trimtrail: trim trailing tabs and blanks, returns new length
 */
size_t trimtrail(char s[])
{
    size_t lastnb;
    size_t i;
    // find the last non-blank char
    for (i = 0, lastnb = 0; s[i] != '\0'; ++i) {
        if (s[i] != ' ' && s[i] != '\t' && s[i] != '\n') {
            lastnb = i;
        }
    }
    // is it a non-empty string?
    if (i > 0) {
        --i;
        // is there a non-blank char?
        if (lastnb > 0 || 
        (s[0] != ' ' && s[0] != '\t' && s[0] != '\n')) {
            // has non-blanks, but is it properly terminated?
            if (s[i] == '\n') {
                ++lastnb;
                s[lastnb] = '\n';
            }
        }
        else {
            // blanks-only line, but is it properly terminated?
            if (s[i] == '\n') {
                s[lastnb] = '\n';
            }
        }
        ++lastnb;
        s[lastnb] = '\0';
        return lastnb;
    }
    else {
        // empty string
        return 0;
    }
}

Test

Input File

1        
2       



444 4                        
5555 5                           
66666 6                                6
777777 7                               
8888888 8                               
99999999 9                               
000000000 0                                   
1                                         

Test Script (Bash)

i=0
j=1
./ch1-ex-1-18-01 <test.txt >out1.txt
while [ $? -eq 1 ] && [ $j -lt 20 ]; do
    let i+=1
    let j+=1
    ./ch1-ex-1-18-01 <out${i}.txt >out${j}.txt
done
\$\endgroup\$
4
\$\begingroup\$

Review covers only minor stuff.

getline()

Avoid a technical exploit when size == 0. Although this code passes sizes more than 0, the function is hackable with size == 0.

When sz == 0, as type size_t, sz-1 is a huge value. Simply + 1 on the left-hand side instead.

// while (i < sz-1 && el == false)
while (i + 1 < sz && el == false)

Advanced: getline()

When a rare reading error occurs, getchar() returns EOF. Standard functions like fgets() return NULL even if some characters were successfully read prior to the error. This differs from OP's getline() functionality. Since getline() uses a return of 0 to indicate end-of-file (and no data read), a parallel functionality to fgets() would also return 0 when an input error occurs (even if some good data read prior).

Easy, yet pedantic, change suggested:

if (i < sz) {
    // add if
    if (c == EOF && !feof(stdin)) {  // EOF due to error
      i = 0;
    }
    s[i] = '\0';
}

Consider const

When the source data does not change, using const can make for 1) more clarity in function usage 2) greater applicability as then const char *f; copy(..., f); is possible. 3) potentially more efficient code.

// void copy(char to[], char from[]);
void copy(char to[], char const from[]);

Advanced: Consider restrict

restrict, roughly, implies that the data referenced by pointer only changes due to the code's function without side effects. Should from/to overlap, copy() as presently coded, can dramatically fail. restrict informs the caller that to/from should not overlap and thus allows the compiler to perform additional optimizations based on that.

// void copy(char to[], char const from[]);
void copy(char * restrict to, char const * restrict from);

Inconsistent documentation/function

Code is described as "trim trailing tabs and blanks" yet then trims ' ', '\t' and '\n'. Recommended consistent documentation and function.

Sentinels

When printing string test output, especially ones with white-space removal, use sentinels to help show problems.

// printf("%s", line);
printf("<%s>", line);

bool deserves boolean syntax

Style issue.

// while (i < sz-1 && el == false) {
while (i < sz-1 && !el) {

No major issues noted. Well done.

\$\endgroup\$
  • \$\begingroup\$ Thanks! So the EOF test is for when just 1 getchar call returned EOF, but next call would return something else. Currently my program would still read the partial line, and continue reading after the error. With the fix, it would stop at the error, is that right? As for the "trim trailing tabs and blanks", if the string had an \n, it puts it back at the end, if the string didn't have it (too long line, or EOF-terminated), it doesn't add it. \$\endgroup\$ – div0man Nov 4 '18 at 10:22
  • \$\begingroup\$ @div0man ,"it would stop at the error, is that right? " Yes. \$\endgroup\$ – chux Nov 5 '18 at 6:32
  • \$\begingroup\$ Great review; should be pointed out that bool and restrict are a C99 feature and not C90. \$\endgroup\$ – Neil Edelman Nov 7 '18 at 23:09

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.