The C Programming Language, 2nd Edition, by Kernighan and Ritchie
Exercise 5.13 on page 118
tail, which prints the last n lines of its input. By default, n is 10, say, but it can be changed by an optional argument, so that tail -n
prints the last
n lines. The program should behave rationally no matter how unreasonable the input or the value of n. Write the program so it makes the best use of available storage; lines should be stored as in the sorting program of Section 5.6, not in a two-dimensional array of fixed size.Solutions by Gregory Pietsch and Steven Huang
Gregory Pietsch's solution
/**************************************************************************** tail.c - Source code for the tail command AUTHOR: Gregory Pietsch <gkp1@flash.net> DESCRIPTION: tail prints the last part of each file on the command line (10 lines by default); it reads from standard input if no files are given or when a filename of `-' is encountered. If more than one file is given, it prints a header consisting of the file's name enclosed in `==>' and `<==' before the output for each file. There are two option formats for tail: the new one, in which numbers are arguments to the option letters; and the old one, in which the number precedes any option letters. In this version, the old format is barely supported. Supporting it fully is left as an exercise to the reader ;-). GNU's -f (or --follow) option is not supported. With that option, the program loops forever on the assumption that the file being tailed is growing. I couldn't figure out how to determine if the program is reading from a pipe in ANSI C; this option is ignored if reading from a pipe. ****************************************************************************/ /* include files */ #include <ctype.h> #include <stdio.h> #include <stdlib.h> #include <string.h> /* macros */ #define NO_ARG 0 #define REQUIRED_ARG 1 #define OPTIONAL_ARG 2 /* how many characters will fill one's tail (literally) */ #define TAIL_BUFFER_SIZE 16384 /* how much for a string buffer */ #define TAIL_STRING_BUFFER_SIZE 256 /* need MIN */ #ifndef MIN #define MIN(x,y) ((x)<(y)?(x):(y)) #endif /* types */ typedef enum VERBOSITY_T { NEVER, SOMETIMES, ALWAYS } VERBOSITY_T; typedef struct LINE_QUEUE_EL_T { char *s; struct LINE_QUEUE_EL_T *next; } LINE_QUEUE_EL_T; typedef struct LINE_QUEUE_T { struct LINE_QUEUE_EL_T *first; struct LINE_QUEUE_EL_T *last; unsigned long num_elements; } LINE_QUEUE_T; /* GETOPT_LONG_OPTION_T: The type of long option */ typedef struct GETOPT_LONG_OPTION_T { char *name; /* the name of the long option */ int has_arg; /* one of the above macros */ int *flag; /* determines if getopt_long() returns a * value for a long option; if it is * non-NULL, 0 is returned as a function * value and the value of val is stored in * the area pointed to by flag. Otherwise, * val is returned. */ int val; /* determines the value to return if flag is * NULL. */ } GETOPT_LONG_OPTION_T; typedef enum GETOPT_ORDERING_T { PERMUTE, RETURN_IN_ORDER, REQUIRE_ORDER } GETOPT_ORDERING_T; /* globally-defined variables */ char *optarg = NULL; int optind = 0; int opterr = 1; int optopt = '?'; /* statically-defined variables */ static int show_help = 0; static int show_version = 0; static char *shortopts = "c:l:n:qv"; static GETOPT_LONG_OPTION_T longopts[] = { {"bytes", REQUIRED_ARG, NULL, 'c'}, {"lines", REQUIRED_ARG, NULL, 'n'}, {"quiet", NO_ARG, NULL, 'q'}, {"silent", NO_ARG, NULL, 'q'}, {"verbose", NO_ARG, NULL, 'v'}, {"help", NO_ARG, &show_help, 1}, {"version", NO_ARG, &show_version, 1}, {NULL, 0, 0, 0} }; static char *program_name; static int flag_bytes = 0; static VERBOSITY_T flag_verbosity = SOMETIMES; static unsigned long number = 0; static int flag_skip = 0; /* functions */ /* reverse_argv_elements: reverses num elements starting at argv */ static void reverse_argv_elements(char **argv, int num) { int i; char *tmp; for (i = 0; i < (num >> 1); i++) { tmp = argv[i]; argv[i] = argv[num - i - 1]; argv[num - i - 1] = tmp; } } /* permute: swap two blocks of argv-elements given their lengths */ static void permute(char **argv, int len1, int len2) { reverse_argv_elements(argv, len1); reverse_argv_elements(argv, len1 + len2); reverse_argv_elements(argv, len2); } /* is_option: is this argv-element an option or the end of the option list? */ static int is_option(char *argv_element, int only) { return ((argv_element == NULL) || (argv_element[0] == '-') || (only && argv_element[0] == '+')); } /* getopt_internal: the function that does all the dirty work */ static int getopt_internal(int argc, char **argv, char *shortopts, GETOPT_LONG_OPTION_T * longopts, int *longind, int only) { GETOPT_ORDERING_T ordering = PERMUTE; static size_t optwhere = 0; size_t permute_from = 0; int num_nonopts = 0; int optindex = 0; size_t match_chars = 0; char *possible_arg = NULL; int longopt_match = -1; int has_arg = -1; char *cp; int arg_next = 0; /* first, deal with silly parameters and easy stuff */ if (argc == 0 || argv == NULL || (shortopts == NULL && longopts == NULL)) return (optopt = '?'); if (optind >= argc || argv[optind] == NULL) return EOF; if (strcmp(argv[optind], "--") == 0) { optind++; return EOF; } /* if this is our first time through */ if (optind == 0) optind = optwhere = 1; /* define ordering */ if (shortopts != NULL && (*shortopts == '-' || *shortopts == '+')) { ordering = (*shortopts == '-') ? RETURN_IN_ORDER : REQUIRE_ORDER; shortopts++; } else ordering = (getenv("POSIXLY_CORRECT") != NULL) ? REQUIRE_ORDER : PERMUTE; /* * based on ordering, find our next option, if we're at the beginning of * one */ if (optwhere == 1) { switch (ordering) { case PERMUTE: permute_from = optind; num_nonopts = 0; while (!is_option(argv[optind], only)) { optind++; num_nonopts++; } if (argv[optind] == NULL) { /* no more options */ optind = permute_from; return EOF; } else if (strcmp(argv[optind], "--") == 0) { /* no more options, but have to get `--' out of the way */ permute(argv + permute_from, num_nonopts, 1); optind = permute_from + 1; return EOF; } break; case RETURN_IN_ORDER: if (!is_option(argv[optind], only)) { optarg = argv[optind++]; return (optopt = 1); } break; case REQUIRE_ORDER: if (!is_option(argv[optind], only)) return EOF; break; } } /* we've got an option, so parse it */ /* first, is it a long option? */ if (longopts != NULL && (memcmp(argv[optind], "--", 2) == 0 || (only && argv[optind][0] == '+')) && optwhere == 1) { /* handle long options */ if (memcmp(argv[optind], "--", 2) == 0) optwhere = 2; longopt_match = -1; possible_arg = strchr(argv[optind] + optwhere, '='); if (possible_arg == NULL) { /* no =, so next argv might be arg */ match_chars = strlen(argv[optind]); possible_arg = argv[optind] + match_chars; match_chars = match_chars - optwhere; } else match_chars = (possible_arg - argv[optind]) - optwhere; for (optindex = 0; longopts[optindex].name != NULL; optindex++) { if (memcmp(argv[optind] + optwhere, longopts[optindex].name, match_chars) == 0) { /* do we have an exact match? */ if (match_chars == (int)(strlen(longopts[optindex].name))) { longopt_match = optindex; break; } /* do any characters match? */ else { if (longopt_match < 0) longopt_match = optindex; else { /* we have ambiguous options */ if (opterr) fprintf(stderr, "%s: option `%s' is ambiguous " "(could be `--%s' or `--%s')\n", argv[0], argv[optind], longopts[longopt_match].name, longopts[optindex].name); return (optopt = '?'); } } } } if (longopt_match >= 0) has_arg = longopts[longopt_match].has_arg; } /* if we didn't find a long option, is it a short option? */ if (longopt_match < 0 && shortopts != NULL) { cp = strchr(shortopts, argv[optind][optwhere]); if (cp == NULL) { /* couldn't find option in shortopts */ if (opterr) fprintf(stderr, "%s: invalid option -- `-%c'\n", argv[0], argv[optind][optwhere]); optwhere++; if (argv[optind][optwhere] == '\0') { optind++; optwhere = 1; } return (optopt = '?'); } has_arg = ((cp[1] == ':') ? ((cp[2] == ':') ? OPTIONAL_ARG : REQUIRED_ARG) : NO_ARG); possible_arg = argv[optind] + optwhere + 1; optopt = *cp; } /* get argument and reset optwhere */ arg_next = 0; switch (has_arg) { case OPTIONAL_ARG: if (*possible_arg == '=') possible_arg++; if (*possible_arg != '\0') { optarg = possible_arg; optwhere = 1; } else optarg = NULL; break; case REQUIRED_ARG: if (*possible_arg == '=') possible_arg++; if (*possible_arg != '\0') { optarg = possible_arg; optwhere = 1; } else if (optind + 1 >= argc) { if (opterr) { fprintf(stderr, "%s: argument required for option `", argv[0]); if (longopt_match >= 0) fprintf(stderr, "--%s'\n", longopts[longopt_match].name); else fprintf(stderr, "-%c'\n", *cp); } optind++; return (optopt = ':'); } else { optarg = argv[optind + 1]; arg_next = 1; optwhere = 1; } break; case NO_ARG: if (longopt_match < 0) { optwhere++; if (argv[optind][optwhere] == '\0') optwhere = 1; } else optwhere = 1; optarg = NULL; break; } /* do we have to permute or otherwise modify optind? */ if (ordering == PERMUTE && optwhere == 1 && num_nonopts != 0) { permute(argv + permute_from, num_nonopts, 1 + arg_next); optind = permute_from + 1 + arg_next; } else if (optwhere == 1) optind = optind