1 /* $OpenBSD: reverse.c,v 1.18 2007/09/29 12:31:28 otto 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 #ifndef lint 37 #if 0 38 static char sccsid[] = "@(#)reverse.c 8.1 (Berkeley) 6/6/93"; 39 #endif 40 static char rcsid[] = "$OpenBSD: reverse.c,v 1.18 2007/09/29 12:31:28 otto Exp $"; 41 #endif /* not lint */ 42 43 #include <sys/stat.h> 44 45 #include <err.h> 46 #include <stdio.h> 47 #include <stdlib.h> 48 #include <unistd.h> 49 50 #include "extern.h" 51 52 static void r_buf(FILE *); 53 static int r_reg(FILE *, enum STYLE, off_t, struct stat *); 54 55 #define COPYCHAR(fp, ch) \ 56 do { \ 57 if ((ch = getc(fp)) == EOF) { \ 58 ierr(); \ 59 return (0); \ 60 } \ 61 if (putchar(ch) == EOF) { \ 62 oerr(); \ 63 return (0); \ 64 } \ 65 } while (0) 66 67 /* 68 * reverse -- display input in reverse order by line. 69 * 70 * There are six separate cases for this -- regular and non-regular 71 * files by bytes, lines or the whole file. 72 * 73 * BYTES display N bytes 74 * REG reverse scan and display the lines 75 * NOREG cyclically read characters into a wrap-around buffer 76 * 77 * LINES display N lines 78 * REG reverse scan and display the lines 79 * NOREG cyclically read lines into a wrap-around array of buffers 80 * 81 * FILE display the entire file 82 * REG reverse scan and display the lines 83 * NOREG cyclically read input into a linked list of buffers 84 */ 85 void 86 reverse(FILE *fp, enum STYLE style, off_t off, struct stat *sbp) 87 { 88 if (style != REVERSE && off == 0) 89 return; 90 91 if (!S_ISREG(sbp->st_mode) || r_reg(fp, style, off, sbp) != 0) 92 switch(style) { 93 case FBYTES: 94 case RBYTES: 95 (void)bytes(fp, off); 96 break; 97 case FLINES: 98 case RLINES: 99 (void)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 int 111 r_reg(FILE *fp, enum STYLE style, off_t off, struct stat *sbp) 112 { 113 off_t start, pos, end; 114 int ch; 115 116 end = sbp->st_size; 117 if (end == 0) 118 return (0); 119 120 /* Position before char, ignore last char whether newline or not */ 121 pos = end-2; 122 ch = EOF; 123 start = 0; 124 125 if (style == RBYTES && off < end) 126 start = end - off; 127 128 for (; pos >= start; pos--) { 129 /* A seek per char isn't a problem with a smart stdio */ 130 if (fseeko(fp, pos, SEEK_SET) != 0) { 131 ierr(); 132 return (0); 133 } 134 if ((ch = getc(fp)) == '\n') { 135 while (--end > pos) 136 COPYCHAR(fp, ch); 137 end++; 138 if (style == RLINES && --off == 0) 139 break; 140 } 141 else if (ch == EOF) { 142 ierr(); 143 return (0); 144 } 145 } 146 if (pos < start) { 147 if (ch != EOF && ungetc(ch, fp) == EOF) { 148 ierr(); 149 return (0); 150 } 151 while (--end >= start) 152 COPYCHAR(fp, ch); 153 } 154 return (0); 155 } 156 157 typedef struct bf { 158 struct bf *next; 159 struct bf *prev; 160 size_t 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(FILE *fp) 176 { 177 BF *mark, *tr, *tl = NULL; 178 int ch; 179 size_t len, llen; 180 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, NULL); 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 = tl; 203 mark->next = mark->prev = mark; 204 } 205 206 if (!enomem) 207 tl->len = 0; 208 209 /* Fill the block with input data. */ 210 for (p = tl->l, len = 0; 211 len < BSZ && (ch = getc(fp)) != EOF; ++len) 212 *p++ = ch; 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 (void)fprintf(stderr, 232 "tail: warning: %lld bytes discarded\n", (long long)enomem); 233 rval = 1; 234 } 235 236 /* 237 * Step through the blocks in the reverse order read. The last char 238 * is special, ignore whether newline or not. 239 */ 240 for (mark = tl;;) { 241 for (p = tl->l + (len = tl->len) - 1, llen = 0; len--; 242 --p, ++llen) 243 if (*p == '\n') { 244 if (llen) { 245 WR(p + 1, llen); 246 llen = 0; 247 } 248 if (tl == mark) 249 continue; 250 for (tr = tl->next; tr->len; tr = tr->next) { 251 WR(tr->l, tr->len); 252 tr->len = 0; 253 if (tr == mark) 254 break; 255 } 256 } 257 tl->len = llen; 258 if ((tl = tl->prev) == mark) 259 break; 260 } 261 tl = tl->next; 262 if (tl->len) { 263 WR(tl->l, tl->len); 264 tl->len = 0; 265 } 266 while ((tl = tl->next)->len) { 267 WR(tl->l, tl->len); 268 tl->len = 0; 269 } 270 } 271