usr.bin/tail/reverse.c

   1 /*-
   2  * Copyright (c) 1991, 1993
   3  *      The Regents of the University of California.  All rights reserved.
   4  *
   5  * This code is derived from software contributed to Berkeley by
   6  * Edward Sze-Tyan Wang.
   7  *
   8  * Redistribution and use in source and binary forms, with or without
   9  * modification, are permitted provided that the following conditions
  10  * are met:
  11  * 1. Redistributions of source code must retain the above copyright
  12  *    notice, this list of conditions and the following disclaimer.
  13  * 2. Redistributions in binary form must reproduce the above copyright
  14  *    notice, this list of conditions and the following disclaimer in the
  15  *    documentation and/or other materials provided with the distribution.
  16  * 3. All advertising materials mentioning features or use of this software
  17  *    must display the following acknowledgement:
  18  *      This product includes software developed by the University of
  19  *      California, Berkeley and its contributors.
  20  * 4. Neither the name of the University nor the names of its contributors
  21  *    may be used to endorse or promote products derived from this software
  22  *    without specific prior written permission.
  23  *
  24  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  25  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  26  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  27  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  28  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  29  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  30  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  31  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  32  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  33  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  34  * SUCH DAMAGE.
  35  */
  36
  37 #ifndef lint
  38 #if 0
  39 static char sccsid[] = "@(#)reverse.c   8.1 (Berkeley) 6/6/93";
  40 #endif
  41 static const char rcsid[] =
  42   "$FreeBSD: src/usr.bin/tail/reverse.c,v 1.9.2.3 2001/12/19 20:29:31 iedowse Exp $";
  43 #endif /* not lint */
  44
  45 #include <sys/param.h>
  46 #include <sys/stat.h>
  47 #include <sys/mman.h>
  48
  49 #include <limits.h>
  50 #include <errno.h>
  51 #include <unistd.h>
  52 #include <stdio.h>
  53 #include <stdlib.h>
  54 #include <string.h>
  55 #include <err.h>
  56 #include "extern.h"
  57
  58 static void r_buf __P((FILE *));
  59 static void r_reg __P((FILE *, enum STYLE, off_t, struct stat *));
  60
  61 /*
  62  * reverse -- display input in reverse order by line.
  63  *
  64  * There are six separate cases for this -- regular and non-regular
  65  * files by bytes, lines or the whole file.
  66  *
  67  * BYTES        display N bytes
  68  *      REG     mmap the file and display the lines
  69  *      NOREG   cyclically read characters into a wrap-around buffer
  70  *
  71  * LINES        display N lines
  72  *      REG     mmap the file and display the lines
  73  *      NOREG   cyclically read lines into a wrap-around array of buffers
  74  *
  75  * FILE         display the entire file
  76  *      REG     mmap the file and display the lines
  77  *      NOREG   cyclically read input into a linked list of buffers
  78  */
  79 void
  80 reverse(fp, style, off, sbp)
  81         FILE *fp;
  82         enum STYLE style;
  83         off_t off;
  84         struct stat *sbp;
  85 {
  86         if (style != REVERSE && off == 0)
  87                 return;
  88
  89         if (S_ISREG(sbp->st_mode))
  90                 r_reg(fp, style, off, sbp);
  91         else
  92                 switch(style) {
  93                 case FBYTES:
  94                 case RBYTES:
  95                         bytes(fp, off);
  96                         break;
  97                 case FLINES:
  98                 case RLINES:
  99                         lines(fp, off);
 100                         break;
 101                 case REVERSE:
 102                         r_buf(fp);
 103                         break;
 104                 }
 105 }
 106
 107 /*
 108  * r_reg -- display a regular file in reverse order by line.
 109  */
 110 static void
 111 r_reg(fp, style, off, sbp)
 112         FILE *fp;
 113         enum STYLE style;
 114         off_t off;
 115         struct stat *sbp;
 116 {
 117         struct mapinfo map;
 118         off_t curoff, size, lineend;
 119         int i;
 120
 121         if (!(size = sbp->st_size))
 122                 return;
 123
 124         map.start = NULL;
 125         map.mapoff = map.maxoff = size;
 126         map.fd = fileno(fp);
 127
 128         /*
 129          * Last char is special, ignore whether newline or not. Note that
 130          * size == 0 is dealt with above, and size == 1 sets curoff to -1.
 131          */
 132         curoff = size - 2;
 133         lineend = size;
 134         while (curoff >= 0) {
 135                 if (curoff < map.mapoff || curoff >= map.mapoff + map.maplen) {
 136                         if (maparound(&map, curoff) != 0) {
 137                                 ierr();
 138                                 return;
 139                         }
 140                 }
 141                 for (i = curoff - map.mapoff; i >= 0; i--) {
 142                         if (style == RBYTES && --off == 0)
 143                                 break;
 144                         if (map.start[i] == '\n')
 145                                 break;
 146                 }
 147                 /* `i' is either the map offset of a '\n', or -1. */
 148                 curoff = map.mapoff + i;
 149                 if (i < 0)
 150                         continue;
 151
 152                 /* Print the line and update offsets. */
 153                 if (mapprint(&map, curoff + 1, lineend - curoff - 1) != 0) {
 154                         ierr();
 155                         return;
 156                 }
 157                 lineend = curoff + 1;
 158                 curoff--;
 159
 160                 if (style == RLINES)
 161                         off--;
 162
 163                 if (off == 0 && style != REVERSE) {
 164                         /* Avoid printing anything below. */
 165                         curoff = 0;
 166                         break;
 167                 }
 168         }
 169         if (curoff < 0 && mapprint(&map, 0, lineend) != 0) {
 170                 ierr();
 171                 return;
 172         }
 173         if (map.start != NULL && munmap(map.start, map.maplen))
 174                 ierr();
 175 }
 176
 177 typedef struct bf {
 178         struct bf *next;
 179         struct bf *prev;
 180         int len;
 181         char *l;
 182 } BF;
 183
 184 /*
 185  * r_buf -- display a non-regular file in reverse order by line.
 186  *
 187  * This is the function that saves the entire input, storing the data in a
 188  * doubly linked list of buffers and then displays them in reverse order.
 189  * It has the usual nastiness of trying to find the newlines, as there's no
 190  * guarantee that a newline occurs anywhere in the file, let alone in any
 191  * particular buffer.  If we run out of memory, input is discarded (and the
 192  * user warned).
 193  */
 194 static void
 195 r_buf(fp)
 196         FILE *fp;
 197 {
 198         BF *mark, *tl, *tr;
 199         int ch, len, llen;
 200         char *p;
 201         off_t enomem;
 202
 203 #define BSZ     (128 * 1024)
 204         for (mark = NULL, enomem = 0;;) {
 205                 /*
 206                  * Allocate a new block and link it into place in a doubly
 207                  * linked list.  If out of memory, toss the LRU block and
 208                  * keep going.
 209                  */
 210                 if (enomem || (tl = malloc(sizeof(BF))) == NULL ||
 211                     (tl->l = malloc(BSZ)) == NULL) {
 212                         if (!mark)
 213                                 err(1, "malloc");
 214                         tl = enomem ? tl->next : mark;
 215                         enomem += tl->len;
 216                 } else if (mark) {
 217                         tl->next = mark;
 218                         tl->prev = mark->prev;
 219                         mark->prev->next = tl;
 220                         mark->prev = tl;
 221                 } else
 222                         mark->next = mark->prev = (mark = tl);
 223
 224                 /* Fill the block with input data. */
 225                 for (p = tl->l, len = 0;
 226                     len < BSZ && (ch = getc(fp)) != EOF; ++len)
 227                         *p++ = ch;
 228
 229                 if (ferror(fp)) {
 230                         ierr();
 231                         return;
 232                 }
 233
 234                 /*
 235                  * If no input data for this block and we tossed some data,
 236                  * recover it.
 237                  */
 238                 if (!len) {
 239                         if (enomem)
 240                                 enomem -= tl->len;
 241                         tl = tl->prev;
 242                         break;
 243                 }
 244
 245                 tl->len = len;
 246                 if (ch == EOF)
 247                         break;
 248         }
 249
 250         if (enomem) {
 251                 warnx("warning: %qd bytes discarded", enomem);
 252                 rval = 1;
 253         }
 254
 255         /*
 256          * Step through the blocks in the reverse order read.  The last char
 257          * is special, ignore whether newline or not.
 258          */
 259         for (mark = tl;;) {
 260                 for (p = tl->l + (len = tl->len) - 1, llen = 0; len--;
 261                     --p, ++llen)
 262                         if (*p == '\n') {
 263                                 if (llen) {
 264                                         WR(p + 1, llen);
 265                                         llen = 0;
 266                                 }
 267                                 if (tl == mark)
 268                                         continue;
 269                                 for (tr = tl->next; tr->len; tr = tr->next) {
 270                                         WR(tr->l, tr->len);
 271                                         tr->len = 0;
 272                                         if (tr == mark)
 273                                                 break;
 274                                 }
 275                         }
 276                 tl->len = llen;
 277                 if ((tl = tl->prev) == mark)
 278                         break;
 279         }
 280         tl = tl->next;
 281         if (tl->len) {
 282                 WR(tl->l, tl->len);
 283                 tl->len = 0;
 284         }
 285         while ((tl = tl->next)->len) {
 286                 WR(tl->l, tl->len);
 287                 tl->len = 0;
 288         }
 289 }