reverse.c revision 17339
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) { 1211590Srgrimes err(0, "%s: %s", fname, strerror(EFBIG)); 1221590Srgrimes return; 1231590Srgrimes } 1241590Srgrimes 1251590Srgrimes if ((start = mmap(NULL, (size_t)size, 1261590Srgrimes PROT_READ, 0, fileno(fp), (off_t)0)) == (caddr_t)-1) { 1271590Srgrimes err(0, "%s: %s", fname, strerror(EFBIG)); 1281590Srgrimes return; 1291590Srgrimes } 1301590Srgrimes p = start + size - 1; 1311590Srgrimes 1321590Srgrimes if (style == RBYTES && off < size) 1331590Srgrimes size = off; 1341590Srgrimes 1351590Srgrimes /* Last char is special, ignore whether newline or not. */ 1361590Srgrimes for (llen = 1; --size; ++llen) 1371590Srgrimes if (*--p == '\n') { 1381590Srgrimes WR(p + 1, llen); 1391590Srgrimes llen = 0; 1401590Srgrimes if (style == RLINES && !--off) { 1411590Srgrimes ++p; 1421590Srgrimes break; 1431590Srgrimes } 1441590Srgrimes } 1451590Srgrimes if (llen) 1461590Srgrimes WR(p, llen); 1471590Srgrimes if (munmap(start, (size_t)sbp->st_size)) 1481590Srgrimes err(0, "%s: %s", fname, strerror(errno)); 1491590Srgrimes} 1501590Srgrimes 1511590Srgrimestypedef struct bf { 1521590Srgrimes struct bf *next; 1531590Srgrimes struct bf *prev; 1541590Srgrimes int len; 1551590Srgrimes char *l; 1561590Srgrimes} BF; 1571590Srgrimes 1581590Srgrimes/* 1591590Srgrimes * r_buf -- display a non-regular file in reverse order by line. 1601590Srgrimes * 1611590Srgrimes * This is the function that saves the entire input, storing the data in a 1621590Srgrimes * doubly linked list of buffers and then displays them in reverse order. 1631590Srgrimes * It has the usual nastiness of trying to find the newlines, as there's no 1641590Srgrimes * guarantee that a newline occurs anywhere in the file, let alone in any 1651590Srgrimes * particular buffer. If we run out of memory, input is discarded (and the 1661590Srgrimes * user warned). 1671590Srgrimes */ 1681590Srgrimesstatic void 1691590Srgrimesr_buf(fp) 1701590Srgrimes FILE *fp; 1711590Srgrimes{ 1721590Srgrimes register BF *mark, *tl, *tr; 1731590Srgrimes register int ch, len, llen; 1741590Srgrimes register char *p; 1751590Srgrimes off_t enomem; 1761590Srgrimes 1771590Srgrimes#define BSZ (128 * 1024) 1781590Srgrimes for (mark = NULL, enomem = 0;;) { 1791590Srgrimes /* 1801590Srgrimes * Allocate a new block and link it into place in a doubly 1811590Srgrimes * linked list. If out of memory, toss the LRU block and 1821590Srgrimes * keep going. 1831590Srgrimes */ 1841590Srgrimes if (enomem || (tl = malloc(sizeof(BF))) == NULL || 1851590Srgrimes (tl->l = malloc(BSZ)) == NULL) { 1861590Srgrimes if (!mark) 1871590Srgrimes err(1, "%s", strerror(errno)); 1881590Srgrimes tl = enomem ? tl->next : mark; 1891590Srgrimes enomem += tl->len; 1901590Srgrimes } else if (mark) { 1911590Srgrimes tl->next = mark; 1921590Srgrimes tl->prev = mark->prev; 1931590Srgrimes mark->prev->next = tl; 1941590Srgrimes mark->prev = tl; 1951590Srgrimes } else 1961590Srgrimes mark->next = mark->prev = (mark = tl); 1971590Srgrimes 1981590Srgrimes /* Fill the block with input data. */ 1991590Srgrimes for (p = tl->l, len = 0; 2001590Srgrimes len < BSZ && (ch = getc(fp)) != EOF; ++len) 2011590Srgrimes *p++ = ch; 2021590Srgrimes 20317339Sadam if (ferror(fp)) { 20417339Sadam ierr(); 20517339Sadam return; 20617339Sadam } 20717339Sadam 2081590Srgrimes /* 2091590Srgrimes * If no input data for this block and we tossed some data, 2101590Srgrimes * recover it. 2111590Srgrimes */ 2121590Srgrimes if (!len) { 2131590Srgrimes if (enomem) 2141590Srgrimes enomem -= tl->len; 2151590Srgrimes tl = tl->prev; 2161590Srgrimes break; 2171590Srgrimes } 2181590Srgrimes 2191590Srgrimes tl->len = len; 2201590Srgrimes if (ch == EOF) 2211590Srgrimes break; 2221590Srgrimes } 2231590Srgrimes 2241590Srgrimes if (enomem) { 2251590Srgrimes (void)fprintf(stderr, 2261590Srgrimes "tail: warning: %ld bytes discarded\n", enomem); 2271590Srgrimes rval = 1; 2281590Srgrimes } 2291590Srgrimes 2301590Srgrimes /* 2311590Srgrimes * Step through the blocks in the reverse order read. The last char 2321590Srgrimes * is special, ignore whether newline or not. 2331590Srgrimes */ 2341590Srgrimes for (mark = tl;;) { 2351590Srgrimes for (p = tl->l + (len = tl->len) - 1, llen = 0; len--; 2361590Srgrimes --p, ++llen) 2371590Srgrimes if (*p == '\n') { 2381590Srgrimes if (llen) { 2391590Srgrimes WR(p + 1, llen); 2401590Srgrimes llen = 0; 2411590Srgrimes } 2421590Srgrimes if (tl == mark) 2431590Srgrimes continue; 2441590Srgrimes for (tr = tl->next; tr->len; tr = tr->next) { 2451590Srgrimes WR(tr->l, tr->len); 2461590Srgrimes tr->len = 0; 2471590Srgrimes if (tr == mark) 2481590Srgrimes break; 2491590Srgrimes } 2501590Srgrimes } 2511590Srgrimes tl->len = llen; 2521590Srgrimes if ((tl = tl->prev) == mark) 2531590Srgrimes break; 2541590Srgrimes } 2551590Srgrimes tl = tl->next; 2561590Srgrimes if (tl->len) { 2571590Srgrimes WR(tl->l, tl->len); 2581590Srgrimes tl->len = 0; 2591590Srgrimes } 2601590Srgrimes while ((tl = tl->next)->len) { 2611590Srgrimes WR(tl->l, tl->len); 2621590Srgrimes tl->len = 0; 2631590Srgrimes } 2641590Srgrimes} 265