5
\$\begingroup\$

Continuing to slowly progress through The C Programming Language by Brian Kernighan and Dennis Ritchie.

The code I came up with below is for 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.

Feedback is much appreciated.

// 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>

void reverseLine(char *s);

void reverseLine(char *s) {
    int count;
    count = 0;
    for (int i = 0; s[i] != '\0'; i++) {
        count++;
    }
    for (int j = count - 1; j >= 0; j--) {
        putchar(s[j -1]);
    }
    putchar('\n');
}

int main() {
    int ch, charCount;
    char line[BUFSIZ];
    charCount = 0;

    while ((ch = getchar()) != EOF) {
        if (charCount >= BUFSIZ - 1) {
            fprintf(stderr, "Overly long line ignored.\n");
            while ((ch = getchar()) != EOF && ch != '\n') {
                ;
            }
            line[charCount] = ch;
            charCount = 0;
            continue;
        }
        line[charCount++] = ch;
        if (ch == '\n') {
            line[charCount++] = '\0';
            reverseLine(line);
            charCount = 0;
        }
    }
}
\$\endgroup\$
4
  • 3
    \$\begingroup\$ Please do not update the code in your question to incorporate feedback from answers, doing so goes against the Question + Answer style of Code Review. This is not a forum where you should keep the most updated version in your question. Please see what you may and may not do after receiving answers. \$\endgroup\$
    – Mast
    Jan 15, 2023 at 13:40
  • 2
    \$\begingroup\$ What you can do is write a follow up question with a link back to this question with your new improved code. \$\endgroup\$
    – pacmaninbw
    Jan 15, 2023 at 15:31
  • \$\begingroup\$ Wow, that is an old book. Don't expect everything in it to be up-to-date with current programming practices. \$\endgroup\$
    – fishinear
    Jan 15, 2023 at 16:12
  • \$\begingroup\$ Thanks, @fishinear - Although it is old, I think it's a terrific book, especially for someone like myself who has a grasp on the basics of programming, albeit not at a deep level. The words on the pages flowed from two unbelievable minds. I owe it to myself to read their words in this book. Plus, the exercises are proving to be extraordinarily valuable. \$\endgroup\$
    – Eric
    Jan 15, 2023 at 18:44

6 Answers 6

6
\$\begingroup\$

Your implementation is not what the exercise asked for. It asked for a function that reverses a string (implied: in-place), and separately, I/O to read and print lines using that function. What it did not ask for is a function that immediately prints the reverse of the string.

Your declaration of reverseLine is redundant so delete it; only the definition is needed.

In your current intepretation, s should be a const char *s since it isn't mutated, but again, the problem asks for in-place mutation.

Rather than ignoring long lines, just truncate them.

reverseLine should be static.

C allows for int main to omit the return, but that's a bad idea. Write the return.

In-predicate mutation, i.e. while ((ch = getchar()), is common but an anti-pattern. Do not mutate your variables on the inside of predicates.

reverseLine has re-implemented strlen. Don't do that; just call strlen.

\$\endgroup\$
11
  • 5
    \$\begingroup\$ Surely "foo bar" should become "rab oof"? Reverse whole string. Reversing individual words is a step further, perhaps. \$\endgroup\$ Jan 14, 2023 at 20:51
  • 1
    \$\begingroup\$ You need just a single additional char for the swap . \$\endgroup\$ Jan 14, 2023 at 20:52
  • 1
    \$\begingroup\$ @iamericfletcher in-place means that the function works like this: char s[8] = "foo bar"; reverse(s); printf("%s", s); prints rab oof. In-place means that the original string, passed to the function, gets overwritten with the new reversed string. It does not mean that each space-separated word in the string should be reversed on its own and then concatenated in original order \$\endgroup\$
    – minseong
    Jan 15, 2023 at 0:02
  • 1
    \$\begingroup\$ @iamericfletcher (works like char s[8] = "foo bar"; reverse(s); printf("%s", s);, which is in-place, as opposed to char s[8] = "foo bar"; char *result = reverse(s); printf("%s", result); where s still refers to its original value at the end.) \$\endgroup\$
    – minseong
    Jan 15, 2023 at 0:04
  • 2
    \$\begingroup\$ Please post your edit in a new question \$\endgroup\$
    – Reinderien
    Jan 15, 2023 at 13:42
4
\$\begingroup\$

Independent of whether the function reverseString as written is doing what it should, it has an off-by-one error. In the loop putcharing the characters of the input string in reverse order,

for (int j = count - 1; j >= 0; j--) {
    putchar(s[j - 1]);
}

consider that for any count > 0, the last iteration will execute with j equal to 0, causing s[-1] to be accessed, which is out-of-bounds. The argument to putchar should be just s[j]. Note also that even with this correction, your loop would fail to terminate if j were an unsigned type (due to underflow). A correct version of this loop that works for both signed and unsigned loop indexes is

for (int j = count; j > 0; ) {
    putchar(s[--j]);
}
\$\endgroup\$
4
\$\begingroup\$

The main program can be simplified by using a function you probably haven't read about yet called fgets. This function reads a line of text at a time. The variable line will contain the new line after the function has been called; you would need to remove the newline before you reverse the input.

int main() {
    char line[BUFSIZ];

    while (fgets(line, BUFSIZ, stdin) != NULL) {
        if (line[0]) {
            reverseLine(line);
            printf("%s\n", line);
        }
    }
}
\$\endgroup\$
1
  • \$\begingroup\$ Thanks for the suggestion. I'm going to go with what I've learned thus far, but I'm sure it's only a matter of time before this function is introduced. \$\endgroup\$
    – Eric
    Jan 15, 2023 at 13:35
2
\$\begingroup\$

Much focus on how to read a line, yet the coding goal was more on

Write a function reverse(s) that reverses the character string s.

  • OP's reverseLine() is not too bad, yet the stated goal does not include printing.

  • Strings are rarely, yet could be longer than INT_MAX. To handle all strings use size_t count for determining string length. Alternatively, simply use an end pointer.

    void reverseLine(char *s) {
      // for (int i = 0; s[i] != '\0'; i++) {
      //  count++;
      //}
      char *endptr = s;
      while (*endptr) {
        endptr++;
      }
      // endptr now points to the string's null character.

      // walk the start and end pointers together until they meet.
      while (s < endptr) {
        endptr--; 
        char t = *endptr;
        *endptr = *s;
        *s = t;
        s++;
      }
    }

Often it is useful to consider the 0 length case as in reverseLine(""). OP's code does that OK with int, yet if size_t (an unsigned type), it would have trouble when count == 0 and j = count - 1. Instead test for > 0, and then decrement.

// for (int j = count - 1; j >= 0; j--) {
for (size_t j = count; j > 0; ) {
    j--; // add
    putchar(s[j -1]);

reverseLine() will now reverse a string, as was the coding goal.
Now for the next goal.

Use it to write a program that reverses its input a line at a time.

To reverse the input, OP's code is OK, yet ++ not needed in charCount++. Also, since a revised reverseLine() only reverses the string and not print it, we should print the result.

    if (ch == '\n') {
        //line[charCount++] = '\0';
        line[charCount] = '\0';
        reverseLine(line);
        puts(line); // add
        charCount = 0;

The last line

Under various conditions, the last line before end-of-file might not end with a '\n'. So it makes sense after the while ((ch = getchar()) != EOF) { to test for a rump line.

while ((ch = getchar()) != EOF) {
  ...
}

if (charCount > 0) {
  line[charCount] = '\0';
  reverseLine(line);
  puts(line); // Add if reverseLine() does not print.
}
  
\$\endgroup\$
-1
\$\begingroup\$

For your edification, here's a relatively efficient program which fits the exercise and imposes no specific limit in line length nor in number of lines.

A few notes:

  1. The program assumes Linux-style line endings (aka LF, not CRLF).
  2. The program's efficiency could be improved by calling fgets directly on string.data.
    • But to avoid allocation in the common case, it would make String slightly more complicated.
  3. The program uses // instead of /**/ for comments, this is not strictly compliant, but much easier.
  4. The program has been compiled cleanly with -Wall -Wextra -Werror, but has not been tested.

Without further ado [and on godbolt](https://godbolt.org/z/3ozh8z8j4:

#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

//  In-place reverses the string `s` of length `length`.
static void reverse(char* s, size_t length) {
    for (size_t i = 0; i < length / 2; ++i) {
        char temp = s[i];
        s[i] = s[length - 1 - i];
        s[length - 1 - i] = temp;
    }
}

struct String {
    //  NUL-terminated, if non-NULL.
    char* data;
    //  Length exclusive of NUL-terminator.
    size_t length;
    //  Allocated size of the `data`.
    size_t capacity;
};

//  Increase the capacity of `this->data` to be able to fit at least `extra` characters.
static void str_grow(struct String* this, size_t extra) {
    size_t new_capacity = this->capacity > 0 ? this->capacity * 2 : BUFSIZ * 2;

    while (extra > new_capacity - this->length) {
        new_capacity *= 2;
    }

    this->data = this->capacity == 0 ? malloc(new_capacity) : realloc(this->data, new_capacity);

    if (this->data == NULL) {
        fprintf(stderr, "Out of memory");
        exit(1);
    }

    this->capacity = new_capacity;
}

//  Appends the first `length` characters of `s` to `this`.
static void str_append(struct String* this, char const* s, size_t length) {
    if (length > this->capacity - this->length) {
        str_grow(this, length);
    }

    memcpy(this->data + this->length, s, length);
    this->length += length;
    this->data[this->length] = '\0';
}

int main() {
    char buffer[BUFSIZ];
    struct String string = {};

    while (fgets(buffer, sizeof(buffer), stdin) != NULL) {
        size_t read = strlen(buffer);
        assert(read > 0 && "fgets returns either when the input is exhausted, the buffer is full, or when \n is encountered");

        //  Accumulate into heap-allocated buffer if the line is incomplete, and keep reading.
        if (read != BUFSIZ - 1 && buffer[read - 1] != '\n') {
            str_append(&string, buffer, read);
            continue;
        }

        //  Trim the newline character as it shouldn't be reversed.
        //  Portability note: assumes end of lines are LF only, on Windows they may be CRLF instead.
        if (buffer[read - 1] == '\n') {
            buffer[read - 1] = '\0';
            read -= 1;
        }

        //  Speed up common case of short lines by avoiding the copy to `string.data`.
        //  Also avoids memory allocations altogether if all lines are short.
        if (string.length == 0) {
            reverse(buffer, read);

            printf("%s\n", buffer);

            continue;
        }

        str_append(&string, buffer, read);

        reverse(string.data, string.length);

        printf("%s\n", string.data);

        //  Reset string length after use, next read will be a new line.
        string.length = 0;
    }

    free(string.data);
}
\$\endgroup\$
14
  • \$\begingroup\$ Wow - there is a lot to unpack in this implementation! Memory management, structs, etc. Thank you for this - lots to learn! \$\endgroup\$
    – Eric
    Jan 15, 2023 at 13:40
  • 1
    \$\begingroup\$ @iamericfletcher: Yes, not really a beginner's implementation, but hopefully it can help you in your journey :) \$\endgroup\$ Jan 15, 2023 at 14:16
  • \$\begingroup\$ Corner case: fgets() and potentially reading a null character, as the first character leads triggering the assert. In production code, leads to UB with buffer[read - 1]. Maybe if (read == 0) continue;? \$\endgroup\$ Jan 15, 2023 at 15:50
  • \$\begingroup\$ The "\n" vs. "\r\n" is a valid concern, yet more a compiler/shell issue than an OS one. Could use buffer[strcspn(buffer, "\r\n")] to find potential line endings. \$\endgroup\$ Jan 15, 2023 at 15:54
  • \$\begingroup\$ Rather than double the buffer size, consider new_size = old_size*2 + 1. This nicely handle the old_size==0 case and allows growth up to SIZE_MAX, rather than half that. \$\endgroup\$ Jan 15, 2023 at 15:57
-2
\$\begingroup\$

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

OP's code has a line length of BUFSIZ.
Alternative, use recursion, without a line length limit - at least until stack depth is reached.

static int reverse_helper(void) {
  int ch = getchar();
  if (ch != EOF && ch != '\n') {
    int ch2 = reverse_helper();
    putchar(ch);
    ch = ch2;
  }
  return ch;
}

int reverse(void) {
  int ch = reverse_helper();
  if (ch == '\n') {
    putchar(ch);
  }
  fflush(stdout);
  return ch;
}

int main(void) {
  while (reverse() != EOF)
    ;
}

\$\endgroup\$
2
  • \$\begingroup\$ No line limit perhaps, but definitely lines limit. A too large number of lines will lead to stack overflow. With function stack frames typically being 16 bytes aligned, I'd expect this function to cause a stack overflow with as few as 700K lines on FreeBSD (1MB stack). \$\endgroup\$ Jan 15, 2023 at 12:16
  • 1
    \$\begingroup\$ @MatthieuM. Concern about stack overflow is valid (I think the math is off, perhaps you meant 70,000) - comment added about that, yet it is the other way around. The stack unwinds with each line ('\n' or EOF), so any stack concern is with the line length, not the number of lines. The number of lines remains unlimited. Code did have a problem with printing the '\n' before the line and has been rectified. \$\endgroup\$ Jan 15, 2023 at 15:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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