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