reverse.c revision 74876
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 3828150Scharnier#if 0 391590Srgrimesstatic char sccsid[] = "@(#)reverse.c 8.1 (Berkeley) 6/6/93"; 4028150Scharnier#endif 4128150Scharnierstatic const char rcsid[] = 4250477Speter "$FreeBSD: head/usr.bin/tail/reverse.c 74876 2001-03-27 20:37:34Z dwmalone $"; 431590Srgrimes#endif /* not lint */ 441590Srgrimes 451590Srgrimes#include <sys/param.h> 461590Srgrimes#include <sys/stat.h> 471590Srgrimes#include <sys/mman.h> 481590Srgrimes 491590Srgrimes#include <limits.h> 501590Srgrimes#include <errno.h> 511590Srgrimes#include <unistd.h> 521590Srgrimes#include <stdio.h> 531590Srgrimes#include <stdlib.h> 541590Srgrimes#include <string.h> 5517826Speter#include <err.h> 561590Srgrimes#include "extern.h" 571590Srgrimes 581590Srgrimesstatic void r_buf __P((FILE *)); 591590Srgrimesstatic void r_reg __P((FILE *, enum STYLE, long, struct stat *)); 601590Srgrimes 611590Srgrimes/* 621590Srgrimes * reverse -- display input in reverse order by line. 631590Srgrimes * 641590Srgrimes * There are six separate cases for this -- regular and non-regular 651590Srgrimes * files by bytes, lines or the whole file. 661590Srgrimes * 671590Srgrimes * BYTES display N bytes 681590Srgrimes * REG mmap the file and display the lines 691590Srgrimes * NOREG cyclically read characters into a wrap-around buffer 701590Srgrimes * 711590Srgrimes * LINES display N lines 721590Srgrimes * REG mmap the file and display the lines 731590Srgrimes * NOREG cyclically read lines into a wrap-around array of buffers 741590Srgrimes * 751590Srgrimes * FILE display the entire file 761590Srgrimes * REG mmap the file and display the lines 771590Srgrimes * NOREG cyclically read input into a linked list of buffers 781590Srgrimes */ 791590Srgrimesvoid 801590Srgrimesreverse(fp, style, off, sbp) 811590Srgrimes FILE *fp; 821590Srgrimes enum STYLE style; 831590Srgrimes long off; 841590Srgrimes struct stat *sbp; 851590Srgrimes{ 861590Srgrimes if (style != REVERSE && off == 0) 871590Srgrimes return; 881590Srgrimes 891590Srgrimes if (S_ISREG(sbp->st_mode)) 901590Srgrimes r_reg(fp, style, off, sbp); 911590Srgrimes else 921590Srgrimes switch(style) { 931590Srgrimes case FBYTES: 941590Srgrimes case RBYTES: 951590Srgrimes bytes(fp, off); 961590Srgrimes break; 971590Srgrimes case FLINES: 981590Srgrimes case RLINES: 991590Srgrimes lines(fp, off); 1001590Srgrimes break; 1011590Srgrimes case REVERSE: 1021590Srgrimes r_buf(fp); 1031590Srgrimes break; 1041590Srgrimes } 1051590Srgrimes} 1061590Srgrimes 1071590Srgrimes/* 1081590Srgrimes * r_reg -- display a regular file in reverse order by line. 1091590Srgrimes */ 1101590Srgrimesstatic void 1111590Srgrimesr_reg(fp, style, off, sbp) 1121590Srgrimes FILE *fp; 11369552Sasmodai enum STYLE style; 1141590Srgrimes long off; 1151590Srgrimes struct stat *sbp; 1161590Srgrimes{ 11774876Sdwmalone struct mapinfo map; 11874876Sdwmalone off_t curoff, size, lineend; 11974876Sdwmalone int i; 1201590Srgrimes 1211590Srgrimes if (!(size = sbp->st_size)) 1221590Srgrimes return; 1231590Srgrimes 12474876Sdwmalone map.start = NULL; 12574876Sdwmalone map.mapoff = map.maxoff = size; 12674876Sdwmalone map.fd = fileno(fp); 1271590Srgrimes 12874876Sdwmalone /* 12974876Sdwmalone * Last char is special, ignore whether newline or not. Note that 13074876Sdwmalone * size == 0 is dealt with above, and size == 1 sets curoff to -1. 13174876Sdwmalone */ 13274876Sdwmalone curoff = size - 2; 13374876Sdwmalone lineend = size; 13474876Sdwmalone while (curoff >= 0) { 13574876Sdwmalone if (curoff < map.mapoff || curoff >= map.mapoff + map.maplen) { 13674876Sdwmalone if (maparound(&map, curoff) != 0) { 13774876Sdwmalone ierr(); 13874876Sdwmalone return; 13974876Sdwmalone } 14074876Sdwmalone } 14174876Sdwmalone for (i = curoff - map.mapoff; i >= 0; i--) { 14274876Sdwmalone if (style == RBYTES && --off == 0) 14374876Sdwmalone break; 14474876Sdwmalone if (map.start[i] == '\n') 14574876Sdwmalone break; 14674876Sdwmalone } 14774876Sdwmalone /* `i' is either the map offset of a '\n', or -1. */ 14874876Sdwmalone curoff = map.mapoff + i; 14974876Sdwmalone if (i < 0) 15074876Sdwmalone continue; 1511590Srgrimes 15274876Sdwmalone /* Print the line and update offsets. */ 15374876Sdwmalone if (mapprint(&map, curoff + 1, lineend - curoff - 1) != 0) { 15474876Sdwmalone ierr(); 15574876Sdwmalone return; 15674876Sdwmalone } 15774876Sdwmalone lineend = curoff + 1; 15874876Sdwmalone curoff--; 1591590Srgrimes 16074876Sdwmalone if (style == RLINES) 16174876Sdwmalone off--; 16274876Sdwmalone 16374876Sdwmalone if (off == 0 && style != REVERSE) { 16474876Sdwmalone /* Avoid printing anything below. */ 16574876Sdwmalone curoff = 0; 16674876Sdwmalone break; 1671590Srgrimes } 16874876Sdwmalone } 16974876Sdwmalone if (curoff < 0 && mapprint(&map, 0, lineend) != 0) { 17017833Sadam ierr(); 17174876Sdwmalone return; 17274876Sdwmalone } 17374876Sdwmalone if (map.start != NULL && munmap(map.start, map.maplen)) 17474876Sdwmalone ierr(); 1751590Srgrimes} 1761590Srgrimes 1771590Srgrimestypedef struct bf { 1781590Srgrimes struct bf *next; 1791590Srgrimes struct bf *prev; 1801590Srgrimes int len; 1811590Srgrimes char *l; 1821590Srgrimes} BF; 1831590Srgrimes 1841590Srgrimes/* 1851590Srgrimes * r_buf -- display a non-regular file in reverse order by line. 1861590Srgrimes * 1871590Srgrimes * This is the function that saves the entire input, storing the data in a 1881590Srgrimes * doubly linked list of buffers and then displays them in reverse order. 1891590Srgrimes * It has the usual nastiness of trying to find the newlines, as there's no 1901590Srgrimes * guarantee that a newline occurs anywhere in the file, let alone in any 1911590Srgrimes * particular buffer. If we run out of memory, input is discarded (and the 1921590Srgrimes * user warned). 1931590Srgrimes */ 1941590Srgrimesstatic void 1951590Srgrimesr_buf(fp) 1961590Srgrimes FILE *fp; 1971590Srgrimes{ 19869552Sasmodai BF *mark, *tl, *tr; 19969552Sasmodai int ch, len, llen; 20069552Sasmodai char *p; 2011590Srgrimes off_t enomem; 2021590Srgrimes 2031590Srgrimes#define BSZ (128 * 1024) 2041590Srgrimes for (mark = NULL, enomem = 0;;) { 2051590Srgrimes /* 2061590Srgrimes * Allocate a new block and link it into place in a doubly 2071590Srgrimes * linked list. If out of memory, toss the LRU block and 2081590Srgrimes * keep going. 2091590Srgrimes */ 2101590Srgrimes if (enomem || (tl = malloc(sizeof(BF))) == NULL || 2111590Srgrimes (tl->l = malloc(BSZ)) == NULL) { 2121590Srgrimes if (!mark) 21317825Speter err(1, "malloc"); 2141590Srgrimes tl = enomem ? tl->next : mark; 2151590Srgrimes enomem += tl->len; 2161590Srgrimes } else if (mark) { 2171590Srgrimes tl->next = mark; 2181590Srgrimes tl->prev = mark->prev; 2191590Srgrimes mark->prev->next = tl; 2201590Srgrimes mark->prev = tl; 2211590Srgrimes } else 2221590Srgrimes mark->next = mark->prev = (mark = tl); 2231590Srgrimes 2241590Srgrimes /* Fill the block with input data. */ 2251590Srgrimes for (p = tl->l, len = 0; 2261590Srgrimes len < BSZ && (ch = getc(fp)) != EOF; ++len) 2271590Srgrimes *p++ = ch; 2281590Srgrimes 22917339Sadam if (ferror(fp)) { 23017339Sadam ierr(); 23117339Sadam return; 23217339Sadam } 23317339Sadam 2341590Srgrimes /* 2351590Srgrimes * If no input data for this block and we tossed some data, 2361590Srgrimes * recover it. 2371590Srgrimes */ 2381590Srgrimes if (!len) { 2391590Srgrimes if (enomem) 2401590Srgrimes enomem -= tl->len; 2411590Srgrimes tl = tl->prev; 2421590Srgrimes break; 2431590Srgrimes } 2441590Srgrimes 2451590Srgrimes tl->len = len; 2461590Srgrimes if (ch == EOF) 2471590Srgrimes break; 2481590Srgrimes } 2491590Srgrimes 2501590Srgrimes if (enomem) { 25137453Sbde warnx("warning: %qd bytes discarded", enomem); 2521590Srgrimes rval = 1; 2531590Srgrimes } 2541590Srgrimes 2551590Srgrimes /* 2561590Srgrimes * Step through the blocks in the reverse order read. The last char 2571590Srgrimes * is special, ignore whether newline or not. 2581590Srgrimes */ 2591590Srgrimes for (mark = tl;;) { 2601590Srgrimes for (p = tl->l + (len = tl->len) - 1, llen = 0; len--; 2611590Srgrimes --p, ++llen) 2621590Srgrimes if (*p == '\n') { 2631590Srgrimes if (llen) { 2641590Srgrimes WR(p + 1, llen); 2651590Srgrimes llen = 0; 2661590Srgrimes } 2671590Srgrimes if (tl == mark) 2681590Srgrimes continue; 2691590Srgrimes for (tr = tl->next; tr->len; tr = tr->next) { 2701590Srgrimes WR(tr->l, tr->len); 2711590Srgrimes tr->len = 0; 2721590Srgrimes if (tr == mark) 2731590Srgrimes break; 2741590Srgrimes } 2751590Srgrimes } 2761590Srgrimes tl->len = llen; 2771590Srgrimes if ((tl = tl->prev) == mark) 2781590Srgrimes break; 2791590Srgrimes } 2801590Srgrimes tl = tl->next; 2811590Srgrimes if (tl->len) { 2821590Srgrimes WR(tl->l, tl->len); 2831590Srgrimes tl->len = 0; 2841590Srgrimes } 2851590Srgrimes while ((tl = tl->next)->len) { 2861590Srgrimes WR(tl->l, tl->len); 2871590Srgrimes tl->len = 0; 2881590Srgrimes } 2891590Srgrimes} 290