reverse.c revision 139994
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 3794609Sdwmalone#if 0 3894609Sdwmalone#ifndef lint 3994609Sdwmalonestatic char sccsid[] = "@(#)reverse.c 8.1 (Berkeley) 6/6/93"; 4094609Sdwmalone#endif /* not lint */ 4194609Sdwmalone#endif 4294609Sdwmalone 4387712Smarkm#include <sys/cdefs.h> 4487712Smarkm__FBSDID("$FreeBSD: head/usr.bin/tail/reverse.c 139994 2005-01-10 20:19:46Z dwmalone $"); 4587712Smarkm 461590Srgrimes#include <sys/param.h> 471590Srgrimes#include <sys/stat.h> 481590Srgrimes#include <sys/mman.h> 491590Srgrimes 5087712Smarkm#include <err.h> 5187712Smarkm#include <errno.h> 521590Srgrimes#include <limits.h> 53139994Sdwmalone#include <stdint.h> 541590Srgrimes#include <stdio.h> 551590Srgrimes#include <stdlib.h> 561590Srgrimes#include <string.h> 5787712Smarkm#include <unistd.h> 5887712Smarkm 591590Srgrimes#include "extern.h" 601590Srgrimes 6192922Simpstatic void r_buf(FILE *); 6292922Simpstatic void r_reg(FILE *, enum STYLE, off_t, struct stat *); 631590Srgrimes 641590Srgrimes/* 651590Srgrimes * reverse -- display input in reverse order by line. 661590Srgrimes * 671590Srgrimes * There are six separate cases for this -- regular and non-regular 681590Srgrimes * files by bytes, lines or the whole file. 691590Srgrimes * 701590Srgrimes * BYTES display N bytes 711590Srgrimes * REG mmap the file and display the lines 721590Srgrimes * NOREG cyclically read characters into a wrap-around buffer 731590Srgrimes * 741590Srgrimes * LINES display N lines 751590Srgrimes * REG mmap the file and display the lines 761590Srgrimes * NOREG cyclically read lines into a wrap-around array of buffers 771590Srgrimes * 781590Srgrimes * FILE display the entire file 791590Srgrimes * REG mmap the file and display the lines 801590Srgrimes * NOREG cyclically read input into a linked list of buffers 811590Srgrimes */ 821590Srgrimesvoid 83137157Spaulreverse(FILE *fp, enum STYLE style, off_t off, struct stat *sbp) 841590Srgrimes{ 851590Srgrimes if (style != REVERSE && off == 0) 861590Srgrimes return; 871590Srgrimes 881590Srgrimes if (S_ISREG(sbp->st_mode)) 891590Srgrimes r_reg(fp, style, off, sbp); 901590Srgrimes else 911590Srgrimes switch(style) { 921590Srgrimes case FBYTES: 931590Srgrimes case RBYTES: 941590Srgrimes bytes(fp, off); 951590Srgrimes break; 961590Srgrimes case FLINES: 971590Srgrimes case RLINES: 981590Srgrimes lines(fp, off); 991590Srgrimes break; 1001590Srgrimes case REVERSE: 1011590Srgrimes r_buf(fp); 1021590Srgrimes break; 10387712Smarkm default: 10494178Smurray break; 1051590Srgrimes } 1061590Srgrimes} 1071590Srgrimes 1081590Srgrimes/* 1091590Srgrimes * r_reg -- display a regular file in reverse order by line. 1101590Srgrimes */ 1111590Srgrimesstatic void 112137157Spaulr_reg(FILE *fp, enum STYLE style, off_t off, struct stat *sbp) 1131590Srgrimes{ 11474876Sdwmalone struct mapinfo map; 11574876Sdwmalone off_t curoff, size, lineend; 11674876Sdwmalone int i; 1171590Srgrimes 1181590Srgrimes if (!(size = sbp->st_size)) 1191590Srgrimes return; 1201590Srgrimes 12174876Sdwmalone map.start = NULL; 12274876Sdwmalone map.mapoff = map.maxoff = size; 12374876Sdwmalone map.fd = fileno(fp); 1241590Srgrimes 12574876Sdwmalone /* 12674876Sdwmalone * Last char is special, ignore whether newline or not. Note that 12774876Sdwmalone * size == 0 is dealt with above, and size == 1 sets curoff to -1. 12874876Sdwmalone */ 12974876Sdwmalone curoff = size - 2; 13074876Sdwmalone lineend = size; 13174876Sdwmalone while (curoff >= 0) { 132139994Sdwmalone if (curoff < map.mapoff || 133139994Sdwmalone curoff >= map.mapoff + (off_t)map.maplen) { 13474876Sdwmalone if (maparound(&map, curoff) != 0) { 13574876Sdwmalone ierr(); 13674876Sdwmalone return; 13774876Sdwmalone } 13874876Sdwmalone } 13974876Sdwmalone for (i = curoff - map.mapoff; i >= 0; i--) { 14074876Sdwmalone if (style == RBYTES && --off == 0) 14174876Sdwmalone break; 14274876Sdwmalone if (map.start[i] == '\n') 14374876Sdwmalone break; 14474876Sdwmalone } 14574876Sdwmalone /* `i' is either the map offset of a '\n', or -1. */ 14674876Sdwmalone curoff = map.mapoff + i; 14774876Sdwmalone if (i < 0) 14874876Sdwmalone continue; 1491590Srgrimes 15074876Sdwmalone /* Print the line and update offsets. */ 15174876Sdwmalone if (mapprint(&map, curoff + 1, lineend - curoff - 1) != 0) { 15274876Sdwmalone ierr(); 15374876Sdwmalone return; 15474876Sdwmalone } 15574876Sdwmalone lineend = curoff + 1; 15674876Sdwmalone curoff--; 1571590Srgrimes 15874876Sdwmalone if (style == RLINES) 15974876Sdwmalone off--; 16074876Sdwmalone 16174876Sdwmalone if (off == 0 && style != REVERSE) { 16274876Sdwmalone /* Avoid printing anything below. */ 16374876Sdwmalone curoff = 0; 16474876Sdwmalone break; 1651590Srgrimes } 16674876Sdwmalone } 16774876Sdwmalone if (curoff < 0 && mapprint(&map, 0, lineend) != 0) { 16817833Sadam ierr(); 16974876Sdwmalone return; 17074876Sdwmalone } 17174876Sdwmalone if (map.start != NULL && munmap(map.start, map.maplen)) 17274876Sdwmalone ierr(); 1731590Srgrimes} 1741590Srgrimes 1751590Srgrimestypedef struct bf { 1761590Srgrimes struct bf *next; 1771590Srgrimes struct bf *prev; 1781590Srgrimes int len; 1791590Srgrimes char *l; 1801590Srgrimes} BF; 1811590Srgrimes 1821590Srgrimes/* 1831590Srgrimes * r_buf -- display a non-regular file in reverse order by line. 1841590Srgrimes * 1851590Srgrimes * This is the function that saves the entire input, storing the data in a 1861590Srgrimes * doubly linked list of buffers and then displays them in reverse order. 1871590Srgrimes * It has the usual nastiness of trying to find the newlines, as there's no 1881590Srgrimes * guarantee that a newline occurs anywhere in the file, let alone in any 1891590Srgrimes * particular buffer. If we run out of memory, input is discarded (and the 1901590Srgrimes * user warned). 1911590Srgrimes */ 1921590Srgrimesstatic void 193137157Spaulr_buf(FILE *fp) 1941590Srgrimes{ 19569552Sasmodai BF *mark, *tl, *tr; 19669552Sasmodai int ch, len, llen; 19769552Sasmodai char *p; 1981590Srgrimes off_t enomem; 1991590Srgrimes 2001590Srgrimes#define BSZ (128 * 1024) 2011590Srgrimes for (mark = NULL, enomem = 0;;) { 2021590Srgrimes /* 2031590Srgrimes * Allocate a new block and link it into place in a doubly 2041590Srgrimes * linked list. If out of memory, toss the LRU block and 2051590Srgrimes * keep going. 2061590Srgrimes */ 2071590Srgrimes if (enomem || (tl = malloc(sizeof(BF))) == NULL || 2081590Srgrimes (tl->l = malloc(BSZ)) == NULL) { 2091590Srgrimes if (!mark) 21017825Speter err(1, "malloc"); 2111590Srgrimes tl = enomem ? tl->next : mark; 2121590Srgrimes enomem += tl->len; 2131590Srgrimes } else if (mark) { 2141590Srgrimes tl->next = mark; 2151590Srgrimes tl->prev = mark->prev; 2161590Srgrimes mark->prev->next = tl; 2171590Srgrimes mark->prev = tl; 21894609Sdwmalone } else { 21994609Sdwmalone mark = tl; 22094609Sdwmalone mark->next = mark->prev = mark; 22194609Sdwmalone } 2221590Srgrimes 2231590Srgrimes /* Fill the block with input data. */ 2241590Srgrimes for (p = tl->l, len = 0; 2251590Srgrimes len < BSZ && (ch = getc(fp)) != EOF; ++len) 2261590Srgrimes *p++ = ch; 2271590Srgrimes 22817339Sadam if (ferror(fp)) { 22917339Sadam ierr(); 23017339Sadam return; 23117339Sadam } 23217339Sadam 2331590Srgrimes /* 2341590Srgrimes * If no input data for this block and we tossed some data, 2351590Srgrimes * recover it. 2361590Srgrimes */ 2371590Srgrimes if (!len) { 2381590Srgrimes if (enomem) 2391590Srgrimes enomem -= tl->len; 2401590Srgrimes tl = tl->prev; 2411590Srgrimes break; 2421590Srgrimes } 2431590Srgrimes 2441590Srgrimes tl->len = len; 2451590Srgrimes if (ch == EOF) 2461590Srgrimes break; 2471590Srgrimes } 2481590Srgrimes 2491590Srgrimes if (enomem) { 250139994Sdwmalone warnx("warning: %jd bytes discarded", (intmax_t)enomem); 2511590Srgrimes rval = 1; 2521590Srgrimes } 2531590Srgrimes 2541590Srgrimes /* 2551590Srgrimes * Step through the blocks in the reverse order read. The last char 2561590Srgrimes * is special, ignore whether newline or not. 2571590Srgrimes */ 2581590Srgrimes for (mark = tl;;) { 2591590Srgrimes for (p = tl->l + (len = tl->len) - 1, llen = 0; len--; 2601590Srgrimes --p, ++llen) 2611590Srgrimes if (*p == '\n') { 2621590Srgrimes if (llen) { 2631590Srgrimes WR(p + 1, llen); 2641590Srgrimes llen = 0; 2651590Srgrimes } 2661590Srgrimes if (tl == mark) 2671590Srgrimes continue; 2681590Srgrimes for (tr = tl->next; tr->len; tr = tr->next) { 2691590Srgrimes WR(tr->l, tr->len); 2701590Srgrimes tr->len = 0; 2711590Srgrimes if (tr == mark) 2721590Srgrimes break; 2731590Srgrimes } 2741590Srgrimes } 2751590Srgrimes tl->len = llen; 2761590Srgrimes if ((tl = tl->prev) == mark) 2771590Srgrimes break; 2781590Srgrimes } 2791590Srgrimes tl = tl->next; 2801590Srgrimes if (tl->len) { 2811590Srgrimes WR(tl->l, tl->len); 2821590Srgrimes tl->len = 0; 2831590Srgrimes } 2841590Srgrimes while ((tl = tl->next)->len) { 2851590Srgrimes WR(tl->l, tl->len); 2861590Srgrimes tl->len = 0; 2871590Srgrimes } 2881590Srgrimes} 289