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$";
  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, long, 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         long 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         register enum STYLE style;
 114         long off;
 115         struct stat *sbp;
 116 {
 117         register off_t size;
 118         register int llen;
 119         register char *p;
 120         char *start;
 121
 122         if (!(size = sbp->st_size))
 123                 return;
 124
 125         if (size > SIZE_T_MAX) {
 126                 errno = EFBIG;
 127                 ierr();
 128                 return;
 129         }
 130
 131         if ((start = mmap(NULL, (size_t)size,
 132             PROT_READ, MAP_SHARED, fileno(fp), (off_t)0)) == MAP_FAILED) {
 133                 ierr();
 134                 return;
 135         }
 136         p = start + size - 1;
 137
 138         if (style == RBYTES && off < size)
 139                 size = off;
 140
 141         /* Last char is special, ignore whether newline or not. */
 142         for (llen = 1; --size; ++llen)
 143                 if (*--p == '\n') {
 144                         WR(p + 1, llen);
 145                         llen = 0;
 146                         if (style == RLINES && !--off) {
 147                                 ++p;
 148                                 break;
 149                         }
 150                 }
 151         if (llen)
 152                 WR(p, llen);
 153         if (munmap(start, (size_t)sbp->st_size))
 154                 ierr();
 155 }
 156
 157 typedef struct bf {
 158         struct bf *next;
 159         struct bf *prev;
 160         int len;
 161         char *l;
 162 } BF;
 163
 164 /*
 165  * r_buf -- display a non-regular file in reverse order by line.
 166  *
 167  * This is the function that saves the entire input, storing the data in a
 168  * doubly linked list of buffers and then displays them in reverse order.
 169  * It has the usual nastiness of trying to find the newlines, as there's no
 170  * guarantee that a newline occurs anywhere in the file, let alone in any
 171  * particular buffer.  If we run out of memory, input is discarded (and the
 172  * user warned).
 173  */
 174 static void
 175 r_buf(fp)
 176         FILE *fp;
 177 {
 178         register BF *mark, *tl, *tr;
 179         register int ch, len, llen;
 180         register char *p;
 181         off_t enomem;
 182
 183 #define BSZ     (128 * 1024)
 184         for (mark = NULL, enomem = 0;;) {
 185                 /*
 186                  * Allocate a new block and link it into place in a doubly
 187                  * linked list.  If out of memory, toss the LRU block and
 188                  * keep going.
 189                  */
 190                 if (enomem || (tl = malloc(sizeof(BF))) == NULL ||
 191                     (tl->l = malloc(BSZ)) == NULL) {
 192                         if (!mark)
 193                                 err(1, "malloc");
 194                         tl = enomem ? tl->next : mark;
 195                         enomem += tl->len;
 196                 } else if (mark) {
 197                         tl->next = mark;
 198                         tl->prev = mark->prev;
 199                         mark->prev->next = tl;
 200                         mark->prev = tl;
 201                 } else
 202                         mark->next = mark->prev = (mark = tl);
 203
 204                 /* Fill the block with input data. */
 205                 for (p = tl->l, len = 0;
 206                     len < BSZ && (ch = getc(fp)) != EOF; ++len)
 207                         *p++ = ch;
 208
 209                 if (ferror(fp)) {
 210                         ierr();
 211                         return;
 212                 }
 213
 214                 /*
 215                  * If no input data for this block and we tossed some data,
 216                  * recover it.
 217                  */
 218                 if (!len) {
 219                         if (enomem)
 220                                 enomem -= tl->len;
 221                         tl = tl->prev;
 222                         break;
 223                 }
 224
 225                 tl->len = len;
 226                 if (ch == EOF)
 227                         break;
 228         }
 229
 230         if (enomem) {
 231                 warnx("warning: %qd bytes discarded", enomem);
 232                 rval = 1;
 233         }
 234
 235         /*
 236          * Step through the blocks in the reverse order read.  The last char
 237          * is special, ignore whether newline or not.
 238          */
 239         for (mark = tl;;) {
 240                 for (p = tl->l + (len = tl->len) - 1, llen = 0; len--;
 241                     --p, ++llen)
 242                         if (*p == '\n') {
 243                                 if (llen) {
 244                                         WR(p + 1, llen);
 245                                         llen = 0;
 246                                 }
 247                                 if (tl == mark)
 248                                         continue;
 249                                 for (tr = tl->next; tr->len; tr = tr->next) {
 250                                         WR(tr->l, tr->len);
 251                                         tr->len = 0;
 252                                         if (tr == mark)
 253                                                 break;
 254                                 }
 255                         }
 256                 tl->len = llen;
 257                 if ((tl = tl->prev) == mark)
 258                         break;
 259         }
 260         tl = tl->next;
 261         if (tl->len) {
 262                 WR(tl->l, tl->len);
 263                 tl->len = 0;
 264         }
 265         while ((tl = tl->next)->len) {
 266                 WR(tl->l, tl->len);
 267                 tl->len = 0;
 268         }
 269 }