16
\$\begingroup\$

The following is like the Unix "tail" program. It was assigned as an exercise in Chapter 5 of Kernighan & Ritchie's The C Programming Language. Because I've only read through most of Chapter 5, I'm still unfamiliar with certain topics, such as malloc(), which may have been more appropriate to use, I don't know.

I've done a little bit of programming before, but not enough to consider myself very experienced, so any kind of advice is welcome. : )

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

#define DEFLINES 10
#define MAXBUFF  20000

int findTail(char *lines[][2], int nlines, char buff[], int maxbuff);

/* main() processes optional cli argument '-n', where n is a number of lines.
 * The default is 10.  findTail finds the last n lines from the input so that
 * they can be printed. */

main(int argc, char *argv[])
{
  int nlines; char *endptr;

  endptr = NULL;
  nlines = DEFLINES;
  if (argc > 2) {
    printf("error: too many arguments.\n");
    return EXIT_FAILURE;
  }
  else if (argc == 2) {
    if (*argv[1] == '-') {
      nlines = strtol(argv[1] + 1, &endptr, 10);
      if (*endptr != '\0') {
        printf("error: not a number of lines: %s\n", argv[1] + 1);
        return EXIT_FAILURE;
      }
    }
    else {
      printf("error: malformed argument: %s\n", argv[1]);
      return EXIT_FAILURE;
    }
  }

  int i;
  char *lines[nlines][2], buff[MAXBUFF];

  findTail(lines, nlines, buff, MAXBUFF);
  for (i=0; i < nlines; ++i) {
    if (lines[i][0] != NULL)
      printf(lines[i][0]);
    if (lines[i][1] != NULL)
      printf(lines[i][1]);
  }
}

#define TRUE     1
#define FALSE    0

void shift(char *lines[][2], int nlines);
void testForRoom(char *lines[][2], int index, char *buffp);

/* findTail stores characters from stdin in the buffer 'buff'. When it finds
 * the end of a line, it stores the pointer for the beginning of that line in
 * 'lines'. once nlines have been found, pointers to previous lines are shifted
 * off of the end of 'lines'. If there is space at the start of 'buff' not
 * pointed to by 'lines', then the end of a line that hits the end of the
 * buffer can continue its storage at the beginning of the buffer. This makes
 * the best use of a fixed-sized buffer for long input. */

int findTail(char *lines[][2], int nlines, char buff[], int maxbuff)
{
  char *buffp, *linestart;
  int i, c, wrap, nfound;

  for (i=0; i < nlines; ++i) {
    lines[i][0] = NULL; // [0] for storing line, or beginning of wrapped line
    lines[i][1] = NULL; // [1] for storing second half of a wrapped line
  }

  nfound = 0;
  wrap = FALSE;
  linestart = buffp = buff;
  while ((c=getchar()) != EOF) {
    if (buffp == linestart && wrap == FALSE) {
      if (nfound < nlines)
        ++nfound;
      shift(lines, nlines);
    }

    if (buffp - buff == maxbuff - 1) {
      *buffp = '\0';
      lines[nlines - 1][0] = linestart;
      wrap = TRUE;
      linestart = buffp = buff;
    }

    testForRoom(lines, nlines - nfound, buffp);

    *buffp++ = c;
    if (c == '\n') {
      *buffp++ = '\0';
      lines[nlines - 1][wrap] = linestart;
      wrap = FALSE;
      if (buffp - buff >= maxbuff - 1)
        buffp = buff;
      linestart = buffp;
    }

  }
  // this is in case the input ended without a newline.
  if (c == EOF && buffp != buff && buffp[-1] != '\0') {
    testForRoom(lines, nlines - nfound, buffp);
    *buffp = '\0';
    lines[nlines - 1][wrap] = linestart;
  }

}

/* shift is used upon finding a character that starts a new line. It shifts
 * line pointers in the pointer array to the left, making room for new line
 * pointer(s) and forgetting the pointer(s) for the oldest line in memory. */

void shift(char *lines[][2], int nlines)
{
  int i;
  for (i=0; i < nlines - 1; ++i) {
    lines[i][0] = lines[i + 1][0];
    lines[i][1] = lines[i + 1][1];
  }
  lines[nlines - 1][0] = NULL;
  lines[nlines - 1][1] = NULL;
}

/* testForRoom tests to see if the location for (or the location following the)
 * next character that would be placed in the buffer is pointed to by a line in
 * the lines pointer array. */

void testForRoom(char *lines[][2], int index, char *buffp) {
  if (buffp == lines[index][0]
      || buffp + 1 == lines[index][0]) {
    printf("error: not enough room in buffer.\n");
    exit(EXIT_FAILURE);
  }
}
\$\endgroup\$
13
\$\begingroup\$

You are using some C99 features, such as declaring variables part way through a block of code and VLAs, but not obeying some C99 constraints, such as ensuring that the main() function has an explicit return type of int.

Because you're using C99, you are allowed to leave off the return(0); (or return 0;) from the end of main(). I think that was one of the less good decisions in C++ that was then echoed in C, and don't take that liberty myself; but I can't criticize your code when the standard allows it.

It might be better to use enum instead of #define for the constants; enum makes debugging easier because the values are in the symbol table, whereas #define constants are typically not.

enum { DEFLINES =    10 };
enum { MAXBUFF  = 20000 };

Your design only reads from standard input. That's not bad, though it is lightly limiting.

Your code includes:

printf(lines[i][0]);

This is a very dangerous way to use printf() - it is the ultimate format string vulnerability. The trouble is that if my input to you contains:

%s%n%13$s

then printf() is going to be reading and writing values on the stack which you didn't put there, which leads to great unhappiness. At minimum, use:

printf("%s", lines[i][0]);

Alternatively, use:

fputs(lines[i][0], stdout);

(Do not use puts() because it adds newlines to the end of your data - unless you remove the newlines from the input.)

When I compile your code using my default options, I get two warnings about the printf() - confirmation of what I'd already observed - plus a warning that findTail() does not return a value even though it is declared to return an int. That's best fixed by making it into a void function.

/usr/bin/gcc -g -std=c99 -Wall -Wextra -Wmissing-prototypes \
      -Wstrict-prototypes  cr.c -o cr

That's a pretty stringent set of warning options, and your code is good to generate just those three. I wish all the code I dealt with was as clean.

When I run the program on its own source code, it works fine. When I run it with:

$ perl -e 'for $i (1..12) { print "A" x 2047, "\n"; }' | ./cr
error: not enough room in buffer.
$

That's OK - you did say you weren't using malloc() to do dynamic memory allocation. As a general guideline, though, your error messages should include the name of the program, as found in argv[0], so that if there are multiple processes in a pipeline, for instance, you can tell which of the processes generated the error. I do this by using a function call err_setarg0(argv[0]); at the start of main(). This records the program name for use in subsequent error messages. I then use function calls such as err_error("error: not enough room in the buffer\n"); to report the messages. A minimal implementation of these two functions is:

#include <stdio.h>
#include <stdarg.h>

static const char *err_arg0 = "unknown";

void err_setarg0(const char *arg0)
{
    err_arg0 = arg0;
}

void err_error(const char *fmt, ...)
{
    va_list args;
    fprintf(stderr, "%s: ", err_arg0);
    va_start(args, fmt);
    vfprintf(stderr, fmt, args);
    va_end(args);
    exit(1);
}

I have a fairly complex file with many variations on this theme that provides simple-to-use error reporting, including variations reporting on the system error (via errno) and including time stamps and process ID and ... all selectable based on program design.

Closer scrutiny shows that at any one time, at most one line will be wrapped - it means that the line starts just before the end of the buffer and has to wrap around to the start of the buffer.

Overall, a pretty good program. Well done (and I don't say that lightly).

I'm not sure how easily it will adapt to handle dynamic memory allocation - my suspicion is that you will end up with a rather different scheme for managing memory. This would remove the issues with lots of very long lines at the end of the file overflowing your buffer. Depending on your platform, you might be able to use the POSIX getline() function which will allocate memory for you as it reads lines. Or you might decide to write an emulation of that code. You then only need a simple circular buffer of character pointers to keep the last N lines, and you discard the old one (with free()) before storing the next line.

\$\endgroup\$
  • \$\begingroup\$ Thanks for the detailed analysis. : ) I didn't know that misuse of printf was a security risk! However, I didn't get the warning for that with the compilation flags you mentioned, I did with the -Wformat-security flag though. I've made changes to use argv[0] in error messages, and have applied your other helpful suggestions. \$\endgroup\$ – sudoman Feb 16 '11 at 14:45
  • \$\begingroup\$ @sudoman: I was using GCC 4.2.1 or 4.5.2 (I have and use both) on MacOS X 10.6.6. You may be using a 3.x version (perhaps on Linux) which may not have reported the printf() problem without the extra poking of -Wformat-security. The warning I get is 'warning: format not a string literal and no format arguments'. (I can also confirm that GCC 4.1.2 on RHEL5 does not generate the format warning with -Wall -Wextra.) \$\endgroup\$ – Jonathan Leffler Feb 17 '11 at 3:47
5
\$\begingroup\$

Since you're using C99, you may be interested in the <stdbool.h> header, this includes three macro definitions, similar to ones you've already defined. This header has at least the following macro definitions on any conforming implementation:

#define bool _Bool
#define true 1
#define false 0

In C99, _Bool is a native Boolean data type, it contains only 0, or 1. When converting any scalar type to _Bool, it will convert to 0 if the scalar type is equal to 0, otherwise it will convert to 1.

Also, in C99, the “implicit int” has been removed, so you must give every function a return type, even main. In older C, functions without an explicit return type would “default” to int type (as would arguments, I think).

\$\endgroup\$
  • \$\begingroup\$ Note that there is a fourth macro that's defined: __bool_true_false_are_defined which expands to 1. It allows you to detect that the other three have been defined by the standard header. Exceptionally: Notwithstanding the provisions of 7.1.3, a program may undefine and perhaps then redefine the macros bool, true, and false.259) (and the footnote refers to the 'Future Directions' where it says (paraphrasing) "this exceptional permission may be removed in the future". \$\endgroup\$ – Jonathan Leffler Sep 6 '15 at 16:17
3
\$\begingroup\$

Interesting design. Performance could probably be improved by allocating a couple of large buffers, and reading large blocks of input alternately into the two buffers until EOF is encountered. At that point, count backward through the two blocks until the proper number of newlines have been found, and then print everything from there to the end.

If the input happens to be a disk file, one could seek to a spot near the end and count the number of newlines from that point on; if there aren't enough, seek back some distance and count the number of newlines between that point to the previous seek point. This would allow "tail" to operate efficiently even if the input is a multi-gigabyte disk file.

\$\endgroup\$
  • \$\begingroup\$ The standard streams are already buffered. Buffering manually is counter productive. \$\endgroup\$ – Martin York Feb 15 '11 at 17:51
  • \$\begingroup\$ @Martin: The standard C streams are already buffered? I knew iostream did buffering but I was not aware C did so... \$\endgroup\$ – Billy ONeal Feb 15 '11 at 17:58
  • \$\begingroup\$ @Billy: At several layers. Hardware/OS/C-Runtime and check fflush \$\endgroup\$ – Martin York Feb 15 '11 at 19:21
  • \$\begingroup\$ @Martin: Ah -- knew somewhat about the OS caching, but not in the CRT. \$\endgroup\$ – Billy ONeal Feb 15 '11 at 20:39
  • \$\begingroup\$ @Martin York: The streams are typically buffered, but the purpose of allocating the buffers in my suggested approach wouldn't just be to improve I/O throughput, but rather to avoid the need to scan the input for newlines until an EOF is detected. I suppose if one were doing character-at-a-time reads, one could guarantee that one would have the last N bytes of a file using a single buffer of size N, but I would expect that even with CRT buffering it would be faster to use two buffers of size N and request N bytes at a time. \$\endgroup\$ – supercat Feb 15 '11 at 20:49
0
\$\begingroup\$

This example implements the -n option of the tail command.

#define _FILE_OFFSET_BITS 64
#include <stdio.h>
#include <stdlib.h>
#include <fcntl.h>
#include <errno.h>
#include <unistd.h>
#include <getopt.h>

#define BUFF_SIZE 4096

FILE *openFile(const char *filePath)
{
  FILE *file;
  file= fopen(filePath, "r");
  if(file == NULL)
  {
    fprintf(stderr,"Error opening file: %s\n",filePath);
    exit(errno);
  }
  return(file);
}

void printLine(FILE *file, off_t startline)
{
  int fd;
  fd= fileno(file);
  int nread;
  char buffer[BUFF_SIZE];
  lseek(fd,(startline + 1),SEEK_SET);
  while((nread= read(fd,buffer,BUFF_SIZE)) > 0)
  {
    write(STDOUT_FILENO, buffer, nread);
  }
}

void walkFile(FILE *file, long nlines)
{
  off_t fposition;
  fseek(file,0,SEEK_END);
  fposition= ftell(file);
  off_t index= fposition;
  off_t end= fposition;
  long countlines= 0;
  char cbyte;

  for(index; index >= 0; index --)
  {
    cbyte= fgetc(file);
    if (cbyte == '\n' && (end - index) > 1)
    {
      countlines ++;
      if(countlines == nlines)
      {
    break;
      }
     }
    fposition--;
    fseek(file,fposition,SEEK_SET);
  }
  printLine(file, fposition);
  fclose(file);
}

int main(int argc, char *argv[])
{
  FILE *file;
  file= openFile(argv[2]);
  walkFile(file, atol(argv[1]));
  return 0;
}

Note: keep in mind that i didn't write code to parse input options or arguments, nor code to check if the argument is really a number.

\$\endgroup\$

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.