reverse.c revision 17825
11590Srgrimes/*- 21590Srgrimes * Copyright (c) 1991, 1993 31590Srgrimes * The Regents of the University of California. All rights reserved. 41590Srgrimes * 51590Srgrimes * This code is derived from software contributed to Berkeley by 61590Srgrimes * Edward Sze-Tyan Wang. 71590Srgrimes * 81590Srgrimes * Redistribution and use in source and binary forms, with or without 91590Srgrimes * modification, are permitted provided that the following conditions 101590Srgrimes * are met: 111590Srgrimes * 1. Redistributions of source code must retain the above copyright 121590Srgrimes * notice, this list of conditions and the following disclaimer. 131590Srgrimes * 2. Redistributions in binary form must reproduce the above copyright 141590Srgrimes * notice, this list of conditions and the following disclaimer in the 151590Srgrimes * documentation and/or other materials provided with the distribution. 161590Srgrimes * 3. All advertising materials mentioning features or use of this software 171590Srgrimes * must display the following acknowledgement: 181590Srgrimes * This product includes software developed by the University of 191590Srgrimes * California, Berkeley and its contributors. 201590Srgrimes * 4. Neither the name of the University nor the names of its contributors 211590Srgrimes * may be used to endorse or promote products derived from this software 221590Srgrimes * without specific prior written permission. 231590Srgrimes * 241590Srgrimes * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 251590Srgrimes * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 261590Srgrimes * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 271590Srgrimes * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 281590Srgrimes * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 291590Srgrimes * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 301590Srgrimes * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 311590Srgrimes * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 321590Srgrimes * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 331590Srgrimes * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 341590Srgrimes * SUCH DAMAGE. 351590Srgrimes */ 361590Srgrimes 371590Srgrimes#ifndef lint 381590Srgrimesstatic char sccsid[] = "@(#)reverse.c 8.1 (Berkeley) 6/6/93"; 391590Srgrimes#endif /* not lint */ 401590Srgrimes 411590Srgrimes#include <sys/param.h> 421590Srgrimes#include <sys/stat.h> 431590Srgrimes#include <sys/mman.h> 441590Srgrimes 451590Srgrimes#include <limits.h> 461590Srgrimes#include <errno.h> 471590Srgrimes#include <unistd.h> 481590Srgrimes#include <stdio.h> 491590Srgrimes#include <stdlib.h> 501590Srgrimes#include <string.h> 511590Srgrimes#include "extern.h" 521590Srgrimes 531590Srgrimesstatic void r_buf __P((FILE *)); 541590Srgrimesstatic void r_reg __P((FILE *, enum STYLE, long, struct stat *)); 551590Srgrimes 561590Srgrimes/* 571590Srgrimes * reverse -- display input in reverse order by line. 581590Srgrimes * 591590Srgrimes * There are six separate cases for this -- regular and non-regular 601590Srgrimes * files by bytes, lines or the whole file. 611590Srgrimes * 621590Srgrimes * BYTES display N bytes 631590Srgrimes * REG mmap the file and display the lines 641590Srgrimes * NOREG cyclically read characters into a wrap-around buffer 651590Srgrimes * 661590Srgrimes * LINES display N lines 671590Srgrimes * REG mmap the file and display the lines 681590Srgrimes * NOREG cyclically read lines into a wrap-around array of buffers 691590Srgrimes * 701590Srgrimes * FILE display the entire file 711590Srgrimes * REG mmap the file and display the lines 721590Srgrimes * NOREG cyclically read input into a linked list of buffers 731590Srgrimes */ 741590Srgrimesvoid 751590Srgrimesreverse(fp, style, off, sbp) 761590Srgrimes FILE *fp; 771590Srgrimes enum STYLE style; 781590Srgrimes long off; 791590Srgrimes struct stat *sbp; 801590Srgrimes{ 811590Srgrimes if (style != REVERSE && off == 0) 821590Srgrimes return; 831590Srgrimes 841590Srgrimes if (S_ISREG(sbp->st_mode)) 851590Srgrimes r_reg(fp, style, off, sbp); 861590Srgrimes else 871590Srgrimes switch(style) { 881590Srgrimes case FBYTES: 891590Srgrimes case RBYTES: 901590Srgrimes bytes(fp, off); 911590Srgrimes break; 921590Srgrimes case FLINES: 931590Srgrimes case RLINES: 941590Srgrimes lines(fp, off); 951590Srgrimes break; 961590Srgrimes case REVERSE: 971590Srgrimes r_buf(fp); 981590Srgrimes break; 991590Srgrimes } 1001590Srgrimes} 1011590Srgrimes 1021590Srgrimes/* 1031590Srgrimes * r_reg -- display a regular file in reverse order by line. 1041590Srgrimes */ 1051590Srgrimesstatic void 1061590Srgrimesr_reg(fp, style, off, sbp) 1071590Srgrimes FILE *fp; 1081590Srgrimes register enum STYLE style; 1091590Srgrimes long off; 1101590Srgrimes struct stat *sbp; 1111590Srgrimes{ 1121590Srgrimes register off_t size; 1131590Srgrimes register int llen; 1141590Srgrimes register char *p; 1151590Srgrimes char *start; 1161590Srgrimes 1171590Srgrimes if (!(size = sbp->st_size)) 1181590Srgrimes return; 1191590Srgrimes 1201590Srgrimes if (size > SIZE_T_MAX) { 12117825Speter errno = EFBIG; 12217825Speter err(0, "%s", fname); 1231590Srgrimes return; 1241590Srgrimes } 1251590Srgrimes 1261590Srgrimes if ((start = mmap(NULL, (size_t)size, 1271590Srgrimes PROT_READ, 0, fileno(fp), (off_t)0)) == (caddr_t)-1) { 12817825Speter err(0, "%s", fname); 1291590Srgrimes return; 1301590Srgrimes } 1311590Srgrimes p = start + size - 1; 1321590Srgrimes 1331590Srgrimes if (style == RBYTES && off < size) 1341590Srgrimes size = off; 1351590Srgrimes 1361590Srgrimes /* Last char is special, ignore whether newline or not. */ 1371590Srgrimes for (llen = 1; --size; ++llen) 1381590Srgrimes if (*--p == '\n') { 1391590Srgrimes WR(p + 1, llen); 1401590Srgrimes llen = 0; 1411590Srgrimes if (style == RLINES && !--off) { 1421590Srgrimes ++p; 1431590Srgrimes break; 1441590Srgrimes } 1451590Srgrimes } 1461590Srgrimes if (llen) 1471590Srgrimes WR(p, llen); 1481590Srgrimes if (munmap(start, (size_t)sbp->st_size)) 14917825Speter err(0, "%s", fname); 1501590Srgrimes} 1511590Srgrimes 1521590Srgrimestypedef struct bf { 1531590Srgrimes struct bf *next; 1541590Srgrimes struct bf *prev; 1551590Srgrimes int len; 1561590Srgrimes char *l; 1571590Srgrimes} BF; 1581590Srgrimes 1591590Srgrimes/* 1601590Srgrimes * r_buf -- display a non-regular file in reverse order by line. 1611590Srgrimes * 1621590Srgrimes * This is the function that saves the entire input, storing the data in a 1631590Srgrimes * doubly linked list of buffers and then displays them in reverse order. 1641590Srgrimes * It has the usual nastiness of trying to find the newlines, as there's no 1651590Srgrimes * guarantee that a newline occurs anywhere in the file, let alone in any 1661590Srgrimes * particular buffer. If we run out of memory, input is discarded (and the 1671590Srgrimes * user warned). 1681590Srgrimes */ 1691590Srgrimesstatic void 1701590Srgrimesr_buf(fp) 1711590Srgrimes FILE *fp; 1721590Srgrimes{ 1731590Srgrimes register BF *mark, *tl, *tr; 1741590Srgrimes register int ch, len, llen; 1751590Srgrimes register char *p; 1761590Srgrimes off_t enomem; 1771590Srgrimes 1781590Srgrimes#define BSZ (128 * 1024) 1791590Srgrimes for (mark = NULL, enomem = 0;;) { 1801590Srgrimes /* 1811590Srgrimes * Allocate a new block and link it into place in a doubly 1821590Srgrimes * linked list. If out of memory, toss the LRU block and 1831590Srgrimes * keep going. 1841590Srgrimes */ 1851590Srgrimes if (enomem || (tl = malloc(sizeof(BF))) == NULL || 1861590Srgrimes (tl->l = malloc(BSZ)) == NULL) { 1871590Srgrimes if (!mark) 18817825Speter err(1, "malloc"); 1891590Srgrimes tl = enomem ? tl->next : mark; 1901590Srgrimes enomem += tl->len; 1911590Srgrimes } else if (mark) { 1921590Srgrimes tl->next = mark; 1931590Srgrimes tl->prev = mark->prev; 1941590Srgrimes mark->prev->next = tl; 1951590Srgrimes mark->prev = tl; 1961590Srgrimes } else 1971590Srgrimes mark->next = mark->prev = (mark = tl); 1981590Srgrimes 1991590Srgrimes /* Fill the block with input data. */ 2001590Srgrimes for (p = tl->l, len = 0; 2011590Srgrimes len < BSZ && (ch = getc(fp)) != EOF; ++len) 2021590Srgrimes *p++ = ch; 2031590Srgrimes 20417339Sadam if (ferror(fp)) { 20517339Sadam ierr(); 20617339Sadam return; 20717339Sadam } 20817339Sadam 2091590Srgrimes /* 2101590Srgrimes * If no input data for this block and we tossed some data, 2111590Srgrimes * recover it. 2121590Srgrimes */ 2131590Srgrimes if (!len) { 2141590Srgrimes if (enomem) 2151590Srgrimes enomem -= tl->len; 2161590Srgrimes tl = tl->prev; 2171590Srgrimes break; 2181590Srgrimes } 2191590Srgrimes 2201590Srgrimes tl->len = len; 2211590Srgrimes if (ch == EOF) 2221590Srgrimes break; 2231590Srgrimes } 2241590Srgrimes 2251590Srgrimes if (enomem) { 2261590Srgrimes (void)fprintf(stderr, 2271590Srgrimes "tail: warning: %ld bytes discarded\n", enomem); 2281590Srgrimes rval = 1; 2291590Srgrimes } 2301590Srgrimes 2311590Srgrimes /* 2321590Srgrimes * Step through the blocks in the reverse order read. The last char 2331590Srgrimes * is special, ignore whether newline or not. 2341590Srgrimes */ 2351590Srgrimes for (mark = tl;;) { 2361590Srgrimes for (p = tl->l + (len = tl->len) - 1, llen = 0; len--; 2371590Srgrimes --p, ++llen) 2381590Srgrimes if (*p == '\n') { 2391590Srgrimes if (llen) { 2401590Srgrimes WR(p + 1, llen); 2411590Srgrimes llen = 0; 2421590Srgrimes } 2431590Srgrimes if (tl == mark) 2441590Srgrimes continue; 2451590Srgrimes for (tr = tl->next; tr->len; tr = tr->next) { 2461590Srgrimes WR(tr->l, tr->len); 2471590Srgrimes tr->len = 0; 2481590Srgrimes if (tr == mark) 2491590Srgrimes break; 2501590Srgrimes } 2511590Srgrimes } 2521590Srgrimes tl->len = llen; 2531590Srgrimes if ((tl = tl->prev) == mark) 2541590Srgrimes break; 2551590Srgrimes } 2561590Srgrimes tl = tl->next; 2571590Srgrimes if (tl->len) { 2581590Srgrimes WR(tl->l, tl->len); 2591590Srgrimes tl->len = 0; 2601590Srgrimes } 2611590Srgrimes while ((tl = tl->next)->len) { 2621590Srgrimes WR(tl->l, tl->len); 2631590Srgrimes tl->len = 0; 2641590Srgrimes } 2651590Srgrimes} 266