5
\$\begingroup\$

As a C programming exercise, I implemented a minimal tac program that prints the input line by line starting from the last line.

I'm looking for feedback on my code. Did I overlook anything? Can the style be improved? Did I miss a major issue?

The code is available here or on GitHub.

/*
** tac [ infd [ outfd ]]
** 
** output each line from infd to oufile, starting from the last line.
** infd and outfd default to stdin and stdout, respectively.
**
*/

#include <stdio.h>
#include <fcntl.h>
#include <stdlib.h>
#include <unistd.h>
#include <sys/types.h>
#include <errno.h>

void
err_exit(char *msg)
{
    perror(msg);
    exit(errno);
}

/*
** write each line starting from the end of the buffer.
** 
** if flush is falsy, don't output characters unless they are preceded by a newline.
** if flush is truthy, write all characters to the output.
** 
** return the number of charaters not outputed.
*/
int
rev_write_lines(int outfd, const char *buf, size_t len, int flush)
{
    int i, prev_eol;
    size_t line_len;

    for(i = prev_eol = len; i >= 0; i--)
        if(buf[i] == '\n') {
            line_len = prev_eol - i;
            if(write(outfd, buf+i+1, line_len) != line_len)
                err_exit("write");

            prev_eol = i;
        }

    if(flush) {
        if(write(outfd, buf, prev_eol+1) != prev_eol+1)
            err_exit("write");
        return 0;
    }

    return prev_eol+1;
}

#define BUF_SIZE 512

/* 
** read size characters from stdin into buffer.
** return the number of characters read.
** stop reading when buffer is full or when EOF is encountered.
*/
size_t
read_in_buf(char *buf, size_t size)
{
    char *p = buf;
    size_t num_read;
    int c;

    if(size == 0)
        return 0;

    while((c = getchar()) != EOF) {
        *p++ = c;
        if(++num_read == size)
            break;
    }

    return num_read;
}

int
stdin_tac(int outfd)
{
    size_t buf_size = BUF_SIZE;
    char *buf;
    ssize_t num_read;
    size_t total_read, read_n;

    if((buf = (char *) malloc(buf_size)) == NULL)
        err_exit("malloc");

    total_read = 0;
    read_n = buf_size;
    while((total_read += num_read = read_in_buf(buf+total_read, read_n))
        , num_read == read_n) {
        if((buf = (char *) realloc(buf, buf_size *= 2)) == NULL)
            err_exit("realloc");
        read_n = buf_size - total_read;
    }

    if(num_read == -1)
        err_exit("read(stdin)");

    return rev_write_lines(outfd, buf, total_read, 1);
}

int
tac(int infd, int outfd)
{
    char *buf;
    size_t buf_size = BUF_SIZE, bytes_left;
    off_t offset, seek_by;
    ssize_t num_read = 0;
    int chars_left_in_line = 0;

    if((buf = (char *) malloc(buf_size)) == NULL)
        err_exit("malloc");

    offset = lseek(infd, 0, SEEK_END);

    seek_by = -buf_size;
/* loop until we try to seek before the start of file  */
    while(offset + seek_by >= 0) {
        if((offset = lseek(infd, seek_by, SEEK_CUR)) == -1)
            err_exit("lseek(SEEK_CUR)");

        if((num_read = read(infd, buf, buf_size)) != buf_size)
            if(num_read == -1)
                err_exit("read(infd)");

        chars_left_in_line = rev_write_lines(
            outfd, buf, num_read, 0);

        if( chars_left_in_line == num_read) {
/*
** buffer is too small to hold this entire line.
** realloc a larger buffer, and (inneficiently) re-read
** the current chunk that we just read in the next iteration. 
*/
            if((buf = (char *) realloc(buf, buf_size *= 2 )) == NULL)
                err_exit("realloc");

            seek_by = -buf_size;
        } else 
            seek_by = -2*buf_size + chars_left_in_line;
    }

    bytes_left = offset + chars_left_in_line;

    if((offset = lseek(infd, 0, SEEK_SET)) == -1)
        err_exit("lseek(SEEK_START)");

    if((num_read = read(infd, buf, bytes_left)) != bytes_left)
        err_exit("read");

    return rev_write_lines(
        outfd, buf, num_read, 1);
}

int
main(int argc, char **argv)
{
    int infd, outfd;

    if(argc == 1)
        return stdin_tac(STDOUT_FILENO);

    if((infd = open(argv[1], O_RDONLY)) == -1) 
        err_exit("open infd");  

    if(argc == 2)
        return tac(infd, STDOUT_FILENO);

    if((outfd = open(argv[2], O_CREAT | O_WRONLY, S_IRWXU)) == -1)
        err_exit("open outfd");

    return tac(infd, outfd);
}

A concession I made is that, on occasion, it is acceptable (though inefficient) to re-read characters that have already been read. For instance, when the buffer overflows in the middle of a line, we re-read the end of the line into a larger buffer as we attempt to read the rest of the line. An alternative would be to copy the incomplete line to the end of the buffer, and read this many less characters. I found that this solution was significantly more complicated to implement, for a negligible performance gain.

\$\endgroup\$
  • 2
    \$\begingroup\$ You are forcing the read of the whole file into memory. You could quite easily get the size of the whole file and pre-allocate the buffer. Or you can use some of the file system calls that maps a file into memory for you. \$\endgroup\$ – Martin York Jul 1 '18 at 16:12
  • 1
    \$\begingroup\$ You could just look at how it is actually implemented: git.savannah.gnu.org/cgit/coreutils.git/tree/src/tac.c. Looking through this code would give you a good indication of what you could improve and what you may have missed. \$\endgroup\$ – esote Jul 1 '18 at 18:02
  • 1
    \$\begingroup\$ the posted code causes the compiler to output LOTS of warning messages, several of which are a significant problem. When compiling, always enable the warnings, then fix those warnings. (for gcc, at a minimum use: -Wall -Wextra -Werror -Wconversion -pedantic -std=gnu11 ) Note: Other compilers have their own unique options for enabling the warnings. \$\endgroup\$ – user3629249 Jul 3 '18 at 16:07
3
\$\begingroup\$

Well, let's make a start with reviewing:

  1. You are assuming that all files the user might name are seekable, even though he might name the console, a socket, a pipe or just about anything else. Also, you assume STDIN is never a normal file.
    So, open files as requested, and then test it for yourself!

  2. If you determine that the input comes from some non-seekable source, consider writing it to a temporary file and then use your normal logic. No need to read it all into memory.

  3. Don't read long blocks with getchar(), fread() is your friend.

  4. Anyway, you might consider just memmap()-ing your input if it's a file, or at least sections of it as needed.

\$\endgroup\$
  • \$\begingroup\$ So, I should be processing seekable and non-seekable files independently without assuming anything about what the user names. For non-seekable files, write them to a temporary file until end of input. Then handle as a seekable file. This makes a lot of sense, thanks ! \$\endgroup\$ – Theo Jul 4 '18 at 22:09
  • \$\begingroup\$ I will look at fread. What is inefficient about getchar when reading stdin? \$\endgroup\$ – Theo Jul 4 '18 at 22:15
  • 1
    \$\begingroup\$ @Theo: Since threading was introduced, each operation on a FILE locks it. And there is various other overhead per call. \$\endgroup\$ – Deduplicator Jul 4 '18 at 22:25
1
\$\begingroup\$

There are several undesirable characteristics to the posted code, However, since the posted code does not cleanly compile, I'll just mention the warnings:

 gcc -ggdb  -Wall -Wextra  -Wconversion -std=gnu11 -pedantic -Wmissing-prototypes  -c "untitled2.c"   -I. (in directory: /home/rkwill/Documents/forum)

 untitled2.c:9:1: warning: no previous prototype for ‘err_exit’ [-Wmissing-prototypes]
 err_exit(char *msg)
 ^

 untitled2.c:24:1: warning: no previous prototype for ‘rev_write_lines’ [-Wmissing-prototypes]
 rev_write_lines(int outfd, const char *buf, size_t len, int flush)
 ^

 untitled2.c: In function ‘rev_write_lines’:
 untitled2.c:29:24: warning: conversion to ‘int’ from ‘size_t {aka long unsigned int}’ may alter its value [-Wconversion]
 for(i = prev_eol = len; i >= 0; i--)
                    ^

 untitled2.c:31:24: warning: conversion to ‘size_t {aka long unsigned int}’ from ‘int’ may change the sign of the result [-Wsign-conversion]
         line_len = prev_eol - i;
                    ^

 untitled2.c:32:48: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if(write(outfd, buf+i+1, line_len) != line_len)
                                            ^
 untitled2.c:39:30: warning: conversion to ‘size_t {aka long unsigned int}’ from ‘int’ may change the sign of the result [-Wsign-conversion]
     if(write(outfd, buf, prev_eol+1) != prev_eol+1)
                          ^
 untitled2.c: At top level:
 untitled2.c:55:1: warning: no previous prototype for ‘read_in_buf’ [-Wmissing-prototypes]
 read_in_buf(char *buf, size_t size)
 ^

 untitled2.c: In function ‘read_in_buf’:
 untitled2.c:65:16: warning: conversion to ‘char’ from ‘int’ may alter its value [-Wconversion]
     *p++ = c;
            ^

 untitled2.c: At top level:
 untitled2.c:74:1: warning: no previous prototype for ‘stdin_tac’ [-Wmissing-prototypes]
 stdin_tac(int outfd)
 ^

 untitled2.c: In function ‘stdin_tac’:
 untitled2.c:86:37: warning: conversion to ‘ssize_t {aka long int}’ from ‘size_t {aka long unsigned int}’ may change the sign of the result [-Wsign-conversion]
 while((total_read += num_read = read_in_buf(buf+total_read, read_n))
                                 ^

 untitled2.c:86:23: warning: conversion to ‘long unsigned int’ from ‘ssize_t {aka long int}’ may change the sign of the result [-Wsign-conversion]
 while((total_read += num_read = read_in_buf(buf+total_read, read_n))
                   ^

 untitled2.c:87:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     , num_read == read_n) {
                ^

 untitled2.c: At top level:
 untitled2.c:100:1: warning: no previous prototype for ‘tac’ [-Wmissing-prototypes]
 tac(int infd, int outfd)
 ^

 untitled2.c: In function ‘tac’:
 untitled2.c:113:15: warning: conversion to ‘off_t {aka long int}’ from ‘size_t {aka long unsigned int}’ may change the sign of the result [-Wsign-conversion]
 seek_by = -buf_size;
           ^

 untitled2.c:119:51: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if((num_read = read(infd, buf, buf_size)) != buf_size)
                                               ^

 untitled2.c:124:25: warning: conversion to ‘size_t {aka long unsigned int}’ from ‘ssize_t {aka long int}’ may change the sign of the result [-Wsign-conversion]
         outfd, buf, num_read, 0);
                     ^

 untitled2.c:135:23: warning: conversion to ‘off_t {aka long int}’ from ‘size_t {aka long unsigned int}’ may change the sign of the result [-Wsign-conversion]
         seek_by = -buf_size;
                   ^

 untitled2.c:137:25: warning: negative integer implicitly converted to unsigned type [-Wsign-conversion]
         seek_by = -2*buf_size + chars_left_in_line;
                     ^

 untitled2.c:137:35: warning: conversion to ‘size_t {aka long unsigned int}’ from ‘int’ may change the sign of the result [-Wsign-conversion]
         seek_by = -2*buf_size + chars_left_in_line;
                               ^

 untitled2.c:137:23: warning: conversion to ‘off_t {aka long int}’ from ‘size_t {aka long unsigned int}’ may change the sign of the result [-Wsign-conversion]
         seek_by = -2*buf_size + chars_left_in_line;
                   ^

 untitled2.c:140:18: warning: conversion to ‘size_t {aka long unsigned int}’ from ‘off_t {aka long int}’ may change the sign of the result [-Wsign-conversion]
  bytes_left = offset + chars_left_in_line;
               ^

 untitled2.c:145:49: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 if((num_read = read(infd, buf, bytes_left)) != bytes_left)
                                             ^

 untitled2.c:149:21: warning: conversion to ‘size_t {aka long unsigned int}’ from ‘ssize_t {aka long int}’ may change the sign of the result [-Wsign-conversion]
     outfd, buf, num_read, 1);
                 ^

Note: not having a prototype for a function is 'ok' if the function is defined before ever being invoked. However, that is not a good programming practice and will 'bite you' in larger programs.

\$\endgroup\$
  • \$\begingroup\$ Thanks for bringing that up. I compiled with -Wall only. Would a good solution to the warnings would be to create a header file with all the prototypes ? \$\endgroup\$ – Theo Jul 4 '18 at 22:02
  • 1
    \$\begingroup\$ @Theo, since no functions are being invoked before they are defined, that will not really help your code. Suggest inserting the function prototypes immediately after the #include statements. \$\endgroup\$ – user3629249 Jul 4 '18 at 22:14
  • \$\begingroup\$ Well, I prefer following DRY and only using forward-declarations if I cannot define it before I have to call it. \$\endgroup\$ – Deduplicator Jul 4 '18 at 22:27
  • \$\begingroup\$ @Deduplicator, when you start working with significant applications (I.E. more than one file) you will be finding it necessary to write header files that have the function prototypes for the related file, \$\endgroup\$ – user3629249 Jul 5 '18 at 21:58
  • \$\begingroup\$ @user3629249: If I want to make it part of the public API (or at least protected API for my other TUs), we have a completely different ball game. But such is not the case here. \$\endgroup\$ – Deduplicator Jul 5 '18 at 22:00

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.