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 #include <sys/cdefs.h> 38 39 __FBSDID("$FreeBSD$"); 40 41 #ifndef lint 42 static const char sccsid[] = "@(#)reverse.c 8.1 (Berkeley) 6/6/93"; 43 #endif 44 45 #include <sys/param.h> 46 #include <sys/stat.h> 47 #include <sys/mman.h> 48 49 #include <err.h> 50 #include <errno.h> 51 #include <limits.h> 52 #include <stdio.h> 53 #include <stdlib.h> 54 #include <string.h> 55 #include <unistd.h> 56 57 #include "extern.h" 58 59 static void r_buf __P((FILE *)); 60 static void r_reg __P((FILE *, enum STYLE, off_t, struct stat *)); 61 62 /* 63 * reverse -- display input in reverse order by line. 64 * 65 * There are six separate cases for this -- regular and non-regular 66 * files by bytes, lines or the whole file. 67 * 68 * BYTES display N bytes 69 * REG mmap the file and display the lines 70 * NOREG cyclically read characters into a wrap-around buffer 71 * 72 * LINES display N lines 73 * REG mmap the file and display the lines 74 * NOREG cyclically read lines into a wrap-around array of buffers 75 * 76 * FILE display the entire file 77 * REG mmap the file and display the lines 78 * NOREG cyclically read input into a linked list of buffers 79 */ 80 void 81 reverse(fp, style, off, sbp) 82 FILE *fp; 83 enum STYLE style; 84 off_t off; 85 struct stat *sbp; 86 { 87 if (style != REVERSE && off == 0) 88 return; 89 90 if (S_ISREG(sbp->st_mode)) 91 r_reg(fp, style, off, sbp); 92 else 93 switch(style) { 94 case FBYTES: 95 case RBYTES: 96 bytes(fp, off); 97 break; 98 case FLINES: 99 case RLINES: 100 lines(fp, off); 101 break; 102 case REVERSE: 103 r_buf(fp); 104 break; 105 default: 106 } 107 } 108 109 /* 110 * r_reg -- display a regular file in reverse order by line. 111 */ 112 static void 113 r_reg(fp, style, off, sbp) 114 FILE *fp; 115 enum STYLE style; 116 off_t off; 117 struct stat *sbp; 118 { 119 struct mapinfo map; 120 off_t curoff, size, lineend; 121 int i; 122 123 if (!(size = sbp->st_size)) 124 return; 125 126 map.start = NULL; 127 map.mapoff = map.maxoff = size; 128 map.fd = fileno(fp); 129 130 /* 131 * Last char is special, ignore whether newline or not. Note that 132 * size == 0 is dealt with above, and size == 1 sets curoff to -1. 133 */ 134 curoff = size - 2; 135 lineend = size; 136 while (curoff >= 0) { 137 if (curoff < map.mapoff || curoff >= map.mapoff + map.maplen) { 138 if (maparound(&map, curoff) != 0) { 139 ierr(); 140 return; 141 } 142 } 143 for (i = curoff - map.mapoff; i >= 0; i--) { 144 if (style == RBYTES && --off == 0) 145 break; 146 if (map.start[i] == '\n') 147 break; 148 } 149 /* `i' is either the map offset of a '\n', or -1. */ 150 curoff = map.mapoff + i; 151 if (i < 0) 152 continue; 153 154 /* Print the line and update offsets. */ 155 if (mapprint(&map, curoff + 1, lineend - curoff - 1) != 0) { 156 ierr(); 157 return; 158 } 159 lineend = curoff + 1; 160 curoff--; 161 162 if (style == RLINES) 163 off--; 164 165 if (off == 0 && style != REVERSE) { 166 /* Avoid printing anything below. */ 167 curoff = 0; 168 break; 169 } 170 } 171 if (curoff < 0 && mapprint(&map, 0, lineend) != 0) { 172 ierr(); 173 return; 174 } 175 if (map.start != NULL && munmap(map.start, map.maplen)) 176 ierr(); 177 } 178 179 typedef struct bf { 180 struct bf *next; 181 struct bf *prev; 182 int len; 183 char *l; 184 } BF; 185 186 /* 187 * r_buf -- display a non-regular file in reverse order by line. 188 * 189 * This is the function that saves the entire input, storing the data in a 190 * doubly linked list of buffers and then displays them in reverse order. 191 * It has the usual nastiness of trying to find the newlines, as there's no 192 * guarantee that a newline occurs anywhere in the file, let alone in any 193 * particular buffer. If we run out of memory, input is discarded (and the 194 * user warned). 195 */ 196 static void 197 r_buf(fp) 198 FILE *fp; 199 { 200 BF *mark, *tl, *tr; 201 int ch, len, llen; 202 char *p; 203 off_t enomem; 204 205 #define BSZ (128 * 1024) 206 for (mark = NULL, enomem = 0;;) { 207 /* 208 * Allocate a new block and link it into place in a doubly 209 * linked list. If out of memory, toss the LRU block and 210 * keep going. 211 */ 212 if (enomem || (tl = malloc(sizeof(BF))) == NULL || 213 (tl->l = malloc(BSZ)) == NULL) { 214 if (!mark) 215 err(1, "malloc"); 216 tl = enomem ? tl->next : mark; 217 enomem += tl->len; 218 } else if (mark) { 219 tl->next = mark; 220 tl->prev = mark->prev; 221 mark->prev->next = tl; 222 mark->prev = tl; 223 } else 224 mark->next = mark->prev = (mark = tl); 225 226 /* Fill the block with input data. */ 227 for (p = tl->l, len = 0; 228 len < BSZ && (ch = getc(fp)) != EOF; ++len) 229 *p++ = ch; 230 231 if (ferror(fp)) { 232 ierr(); 233 return; 234 } 235 236 /* 237 * If no input data for this block and we tossed some data, 238 * recover it. 239 */ 240 if (!len) { 241 if (enomem) 242 enomem -= tl->len; 243 tl = tl->prev; 244 break; 245 } 246 247 tl->len = len; 248 if (ch == EOF) 249 break; 250 } 251 252 if (enomem) { 253 warnx("warning: %qd bytes discarded", enomem); 254 rval = 1; 255 } 256 257 /* 258 * Step through the blocks in the reverse order read. The last char 259 * is special, ignore whether newline or not. 260 */ 261 for (mark = tl;;) { 262 for (p = tl->l + (len = tl->len) - 1, llen = 0; len--; 263 --p, ++llen) 264 if (*p == '\n') { 265 if (llen) { 266 WR(p + 1, llen); 267 llen = 0; 268 } 269 if (tl == mark) 270 continue; 271 for (tr = tl->next; tr->len; tr = tr->next) { 272 WR(tr->l, tr->len); 273 tr->len = 0; 274 if (tr == mark) 275 break; 276 } 277 } 278 tl->len = llen; 279 if ((tl = tl->prev) == mark) 280 break; 281 } 282 tl = tl->next; 283 if (tl->len) { 284 WR(tl->l, tl->len); 285 tl->len = 0; 286 } 287 while ((tl = tl->next)->len) { 288 WR(tl->l, tl->len); 289 tl->len = 0; 290 } 291 } 292