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 * 4. Neither the name of the University nor the names of its contributors 171590Srgrimes * may be used to endorse or promote products derived from this software 181590Srgrimes * without specific prior written permission. 191590Srgrimes * 201590Srgrimes * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 211590Srgrimes * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 221590Srgrimes * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 231590Srgrimes * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 241590Srgrimes * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 251590Srgrimes * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 261590Srgrimes * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 271590Srgrimes * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 281590Srgrimes * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 291590Srgrimes * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 301590Srgrimes * SUCH DAMAGE. 311590Srgrimes */ 321590Srgrimes 3394609Sdwmalone#if 0 3494609Sdwmalone#ifndef lint 3594609Sdwmalonestatic char sccsid[] = "@(#)reverse.c 8.1 (Berkeley) 6/6/93"; 3694609Sdwmalone#endif /* not lint */ 3794609Sdwmalone#endif 3894609Sdwmalone 3987712Smarkm#include <sys/cdefs.h> 4087712Smarkm__FBSDID("$FreeBSD$"); 4187712Smarkm 421590Srgrimes#include <sys/param.h> 431590Srgrimes#include <sys/stat.h> 441590Srgrimes#include <sys/mman.h> 451590Srgrimes 4687712Smarkm#include <err.h> 4787712Smarkm#include <errno.h> 481590Srgrimes#include <limits.h> 49139994Sdwmalone#include <stdint.h> 501590Srgrimes#include <stdio.h> 511590Srgrimes#include <stdlib.h> 521590Srgrimes#include <string.h> 5387712Smarkm#include <unistd.h> 5487712Smarkm 551590Srgrimes#include "extern.h" 561590Srgrimes 57193488Sbrianstatic void r_buf(FILE *, const char *); 58193488Sbrianstatic void r_reg(FILE *, const char *, enum STYLE, off_t, struct stat *); 591590Srgrimes 601590Srgrimes/* 611590Srgrimes * reverse -- display input in reverse order by line. 621590Srgrimes * 631590Srgrimes * There are six separate cases for this -- regular and non-regular 641590Srgrimes * files by bytes, lines or the whole file. 651590Srgrimes * 661590Srgrimes * BYTES display N bytes 671590Srgrimes * REG mmap the file and display the lines 681590Srgrimes * NOREG cyclically read characters into a wrap-around buffer 691590Srgrimes * 701590Srgrimes * LINES display N lines 711590Srgrimes * REG mmap the file and display the lines 721590Srgrimes * NOREG cyclically read lines into a wrap-around array of buffers 731590Srgrimes * 741590Srgrimes * FILE display the entire file 751590Srgrimes * REG mmap the file and display the lines 761590Srgrimes * NOREG cyclically read input into a linked list of buffers 771590Srgrimes */ 781590Srgrimesvoid 79193488Sbrianreverse(FILE *fp, const char *fn, enum STYLE style, off_t off, struct stat *sbp) 801590Srgrimes{ 811590Srgrimes if (style != REVERSE && off == 0) 821590Srgrimes return; 831590Srgrimes 841590Srgrimes if (S_ISREG(sbp->st_mode)) 85193488Sbrian r_reg(fp, fn, style, off, sbp); 861590Srgrimes else 871590Srgrimes switch(style) { 881590Srgrimes case FBYTES: 891590Srgrimes case RBYTES: 90193488Sbrian bytes(fp, fn, off); 911590Srgrimes break; 921590Srgrimes case FLINES: 931590Srgrimes case RLINES: 94193488Sbrian lines(fp, fn, off); 951590Srgrimes break; 961590Srgrimes case REVERSE: 97193488Sbrian r_buf(fp, fn); 981590Srgrimes break; 9987712Smarkm default: 10094178Smurray break; 1011590Srgrimes } 1021590Srgrimes} 1031590Srgrimes 1041590Srgrimes/* 1051590Srgrimes * r_reg -- display a regular file in reverse order by line. 1061590Srgrimes */ 1071590Srgrimesstatic void 108193488Sbrianr_reg(FILE *fp, const char *fn, enum STYLE style, off_t off, struct stat *sbp) 1091590Srgrimes{ 11074876Sdwmalone struct mapinfo map; 11174876Sdwmalone off_t curoff, size, lineend; 11274876Sdwmalone int i; 1131590Srgrimes 1141590Srgrimes if (!(size = sbp->st_size)) 1151590Srgrimes return; 1161590Srgrimes 11774876Sdwmalone map.start = NULL; 11874876Sdwmalone map.mapoff = map.maxoff = size; 11974876Sdwmalone map.fd = fileno(fp); 1201590Srgrimes 12174876Sdwmalone /* 12274876Sdwmalone * Last char is special, ignore whether newline or not. Note that 12374876Sdwmalone * size == 0 is dealt with above, and size == 1 sets curoff to -1. 12474876Sdwmalone */ 12574876Sdwmalone curoff = size - 2; 12674876Sdwmalone lineend = size; 12774876Sdwmalone while (curoff >= 0) { 128139994Sdwmalone if (curoff < map.mapoff || 129139994Sdwmalone curoff >= map.mapoff + (off_t)map.maplen) { 13074876Sdwmalone if (maparound(&map, curoff) != 0) { 131193488Sbrian ierr(fn); 13274876Sdwmalone return; 13374876Sdwmalone } 13474876Sdwmalone } 13574876Sdwmalone for (i = curoff - map.mapoff; i >= 0; i--) { 13674876Sdwmalone if (style == RBYTES && --off == 0) 13774876Sdwmalone break; 13874876Sdwmalone if (map.start[i] == '\n') 13974876Sdwmalone break; 14074876Sdwmalone } 14174876Sdwmalone /* `i' is either the map offset of a '\n', or -1. */ 14274876Sdwmalone curoff = map.mapoff + i; 14374876Sdwmalone if (i < 0) 14474876Sdwmalone continue; 1451590Srgrimes 14674876Sdwmalone /* Print the line and update offsets. */ 14774876Sdwmalone if (mapprint(&map, curoff + 1, lineend - curoff - 1) != 0) { 148193488Sbrian ierr(fn); 14974876Sdwmalone return; 15074876Sdwmalone } 15174876Sdwmalone lineend = curoff + 1; 15274876Sdwmalone curoff--; 1531590Srgrimes 15474876Sdwmalone if (style == RLINES) 15574876Sdwmalone off--; 15674876Sdwmalone 15774876Sdwmalone if (off == 0 && style != REVERSE) { 15874876Sdwmalone /* Avoid printing anything below. */ 15974876Sdwmalone curoff = 0; 16074876Sdwmalone break; 1611590Srgrimes } 16274876Sdwmalone } 16374876Sdwmalone if (curoff < 0 && mapprint(&map, 0, lineend) != 0) { 164193488Sbrian ierr(fn); 16574876Sdwmalone return; 16674876Sdwmalone } 16774876Sdwmalone if (map.start != NULL && munmap(map.start, map.maplen)) 168193488Sbrian ierr(fn); 1691590Srgrimes} 1701590Srgrimes 1711590Srgrimestypedef struct bf { 1721590Srgrimes struct bf *next; 1731590Srgrimes struct bf *prev; 1741590Srgrimes int len; 1751590Srgrimes char *l; 1761590Srgrimes} BF; 1771590Srgrimes 1781590Srgrimes/* 1791590Srgrimes * r_buf -- display a non-regular file in reverse order by line. 1801590Srgrimes * 1811590Srgrimes * This is the function that saves the entire input, storing the data in a 1821590Srgrimes * doubly linked list of buffers and then displays them in reverse order. 1831590Srgrimes * It has the usual nastiness of trying to find the newlines, as there's no 1841590Srgrimes * guarantee that a newline occurs anywhere in the file, let alone in any 1851590Srgrimes * particular buffer. If we run out of memory, input is discarded (and the 1861590Srgrimes * user warned). 1871590Srgrimes */ 1881590Srgrimesstatic void 189193488Sbrianr_buf(FILE *fp, const char *fn) 1901590Srgrimes{ 19169552Sasmodai BF *mark, *tl, *tr; 19269552Sasmodai int ch, len, llen; 19369552Sasmodai char *p; 1941590Srgrimes off_t enomem; 1951590Srgrimes 196173285Scharnier tl = NULL; 1971590Srgrimes#define BSZ (128 * 1024) 1981590Srgrimes for (mark = NULL, enomem = 0;;) { 1991590Srgrimes /* 2001590Srgrimes * Allocate a new block and link it into place in a doubly 2011590Srgrimes * linked list. If out of memory, toss the LRU block and 2021590Srgrimes * keep going. 2031590Srgrimes */ 2041590Srgrimes if (enomem || (tl = malloc(sizeof(BF))) == NULL || 2051590Srgrimes (tl->l = malloc(BSZ)) == NULL) { 2061590Srgrimes if (!mark) 20717825Speter err(1, "malloc"); 2081590Srgrimes tl = enomem ? tl->next : mark; 2091590Srgrimes enomem += tl->len; 2101590Srgrimes } else if (mark) { 2111590Srgrimes tl->next = mark; 2121590Srgrimes tl->prev = mark->prev; 2131590Srgrimes mark->prev->next = tl; 2141590Srgrimes mark->prev = tl; 21594609Sdwmalone } else { 21694609Sdwmalone mark = tl; 21794609Sdwmalone mark->next = mark->prev = mark; 21894609Sdwmalone } 2191590Srgrimes 2201590Srgrimes /* Fill the block with input data. */ 2211590Srgrimes for (p = tl->l, len = 0; 2221590Srgrimes len < BSZ && (ch = getc(fp)) != EOF; ++len) 2231590Srgrimes *p++ = ch; 2241590Srgrimes 22517339Sadam if (ferror(fp)) { 226193488Sbrian ierr(fn); 22717339Sadam return; 22817339Sadam } 22917339Sadam 2301590Srgrimes /* 2311590Srgrimes * If no input data for this block and we tossed some data, 2321590Srgrimes * recover it. 2331590Srgrimes */ 234143891Siedowse if (!len && enomem) { 235143891Siedowse enomem -= tl->len; 2361590Srgrimes tl = tl->prev; 2371590Srgrimes break; 2381590Srgrimes } 2391590Srgrimes 2401590Srgrimes tl->len = len; 2411590Srgrimes if (ch == EOF) 2421590Srgrimes break; 2431590Srgrimes } 2441590Srgrimes 2451590Srgrimes if (enomem) { 246139994Sdwmalone warnx("warning: %jd bytes discarded", (intmax_t)enomem); 2471590Srgrimes rval = 1; 2481590Srgrimes } 2491590Srgrimes 2501590Srgrimes /* 2511590Srgrimes * Step through the blocks in the reverse order read. The last char 2521590Srgrimes * is special, ignore whether newline or not. 2531590Srgrimes */ 2541590Srgrimes for (mark = tl;;) { 2551590Srgrimes for (p = tl->l + (len = tl->len) - 1, llen = 0; len--; 2561590Srgrimes --p, ++llen) 2571590Srgrimes if (*p == '\n') { 2581590Srgrimes if (llen) { 2591590Srgrimes WR(p + 1, llen); 2601590Srgrimes llen = 0; 2611590Srgrimes } 2621590Srgrimes if (tl == mark) 2631590Srgrimes continue; 2641590Srgrimes for (tr = tl->next; tr->len; tr = tr->next) { 2651590Srgrimes WR(tr->l, tr->len); 2661590Srgrimes tr->len = 0; 2671590Srgrimes if (tr == mark) 2681590Srgrimes break; 2691590Srgrimes } 2701590Srgrimes } 2711590Srgrimes tl->len = llen; 2721590Srgrimes if ((tl = tl->prev) == mark) 2731590Srgrimes break; 2741590Srgrimes } 2751590Srgrimes tl = tl->next; 2761590Srgrimes if (tl->len) { 2771590Srgrimes WR(tl->l, tl->len); 2781590Srgrimes tl->len = 0; 2791590Srgrimes } 2801590Srgrimes while ((tl = tl->next)->len) { 2811590Srgrimes WR(tl->l, tl->len); 2821590Srgrimes tl->len = 0; 2831590Srgrimes } 2841590Srgrimes} 285