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: stable/11/usr.bin/tail/reverse.c 332600 2018-04-16 16:20:39Z asomers $"); 4187712Smarkm 421590Srgrimes#include <sys/param.h> 43314427Sasomers#include <sys/queue.h> 441590Srgrimes#include <sys/stat.h> 451590Srgrimes#include <sys/mman.h> 461590Srgrimes 4787712Smarkm#include <err.h> 4887712Smarkm#include <errno.h> 491590Srgrimes#include <limits.h> 50139994Sdwmalone#include <stdint.h> 511590Srgrimes#include <stdio.h> 521590Srgrimes#include <stdlib.h> 531590Srgrimes#include <string.h> 5487712Smarkm#include <unistd.h> 5587712Smarkm 561590Srgrimes#include "extern.h" 571590Srgrimes 58193488Sbrianstatic void r_buf(FILE *, const char *); 59193488Sbrianstatic void r_reg(FILE *, const char *, enum STYLE, off_t, 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 80193488Sbrianreverse(FILE *fp, const char *fn, enum STYLE style, off_t off, struct stat *sbp) 811590Srgrimes{ 821590Srgrimes if (style != REVERSE && off == 0) 831590Srgrimes return; 841590Srgrimes 851590Srgrimes if (S_ISREG(sbp->st_mode)) 86193488Sbrian r_reg(fp, fn, style, off, sbp); 871590Srgrimes else 881590Srgrimes switch(style) { 891590Srgrimes case FBYTES: 901590Srgrimes case RBYTES: 91193488Sbrian bytes(fp, fn, off); 921590Srgrimes break; 931590Srgrimes case FLINES: 941590Srgrimes case RLINES: 95193488Sbrian lines(fp, fn, off); 961590Srgrimes break; 971590Srgrimes case REVERSE: 98193488Sbrian r_buf(fp, fn); 991590Srgrimes break; 10087712Smarkm default: 10194178Smurray break; 1021590Srgrimes } 1031590Srgrimes} 1041590Srgrimes 1051590Srgrimes/* 1061590Srgrimes * r_reg -- display a regular file in reverse order by line. 1071590Srgrimes */ 1081590Srgrimesstatic void 109193488Sbrianr_reg(FILE *fp, const char *fn, enum STYLE style, off_t off, struct stat *sbp) 1101590Srgrimes{ 11174876Sdwmalone struct mapinfo map; 11274876Sdwmalone off_t curoff, size, lineend; 11374876Sdwmalone int i; 1141590Srgrimes 1151590Srgrimes if (!(size = sbp->st_size)) 1161590Srgrimes return; 1171590Srgrimes 11874876Sdwmalone map.start = NULL; 11974876Sdwmalone map.mapoff = map.maxoff = size; 12074876Sdwmalone map.fd = fileno(fp); 121313100Sasomers map.maplen = 0; 1221590Srgrimes 12374876Sdwmalone /* 12474876Sdwmalone * Last char is special, ignore whether newline or not. Note that 12574876Sdwmalone * size == 0 is dealt with above, and size == 1 sets curoff to -1. 12674876Sdwmalone */ 12774876Sdwmalone curoff = size - 2; 12874876Sdwmalone lineend = size; 12974876Sdwmalone while (curoff >= 0) { 130139994Sdwmalone if (curoff < map.mapoff || 131139994Sdwmalone curoff >= map.mapoff + (off_t)map.maplen) { 13274876Sdwmalone if (maparound(&map, curoff) != 0) { 133193488Sbrian ierr(fn); 13474876Sdwmalone return; 13574876Sdwmalone } 13674876Sdwmalone } 13774876Sdwmalone for (i = curoff - map.mapoff; i >= 0; i--) { 13874876Sdwmalone if (style == RBYTES && --off == 0) 13974876Sdwmalone break; 14074876Sdwmalone if (map.start[i] == '\n') 14174876Sdwmalone break; 14274876Sdwmalone } 14374876Sdwmalone /* `i' is either the map offset of a '\n', or -1. */ 14474876Sdwmalone curoff = map.mapoff + i; 14574876Sdwmalone if (i < 0) 14674876Sdwmalone continue; 1471590Srgrimes 14874876Sdwmalone /* Print the line and update offsets. */ 14974876Sdwmalone if (mapprint(&map, curoff + 1, lineend - curoff - 1) != 0) { 150193488Sbrian ierr(fn); 15174876Sdwmalone return; 15274876Sdwmalone } 15374876Sdwmalone lineend = curoff + 1; 15474876Sdwmalone curoff--; 1551590Srgrimes 15674876Sdwmalone if (style == RLINES) 15774876Sdwmalone off--; 15874876Sdwmalone 15974876Sdwmalone if (off == 0 && style != REVERSE) { 16074876Sdwmalone /* Avoid printing anything below. */ 16174876Sdwmalone curoff = 0; 16274876Sdwmalone break; 1631590Srgrimes } 16474876Sdwmalone } 16574876Sdwmalone if (curoff < 0 && mapprint(&map, 0, lineend) != 0) { 166193488Sbrian ierr(fn); 16774876Sdwmalone return; 16874876Sdwmalone } 16974876Sdwmalone if (map.start != NULL && munmap(map.start, map.maplen)) 170193488Sbrian ierr(fn); 1711590Srgrimes} 1721590Srgrimes 173314427Sasomers#define BSZ (128 * 1024) 174314427Sasomerstypedef struct bfelem { 175314427Sasomers TAILQ_ENTRY(bfelem) entries; 176314427Sasomers size_t len; 177314427Sasomers char l[BSZ]; 178314427Sasomers} bfelem_t; 1791590Srgrimes 1801590Srgrimes/* 1811590Srgrimes * r_buf -- display a non-regular file in reverse order by line. 1821590Srgrimes * 1831590Srgrimes * This is the function that saves the entire input, storing the data in a 1841590Srgrimes * doubly linked list of buffers and then displays them in reverse order. 1851590Srgrimes * It has the usual nastiness of trying to find the newlines, as there's no 1861590Srgrimes * guarantee that a newline occurs anywhere in the file, let alone in any 1871590Srgrimes * particular buffer. If we run out of memory, input is discarded (and the 1881590Srgrimes * user warned). 1891590Srgrimes */ 1901590Srgrimesstatic void 191193488Sbrianr_buf(FILE *fp, const char *fn) 1921590Srgrimes{ 193314427Sasomers struct bfelem *tl, *first = NULL; 194314427Sasomers size_t llen; 19569552Sasmodai char *p; 196314427Sasomers off_t enomem = 0; 197314427Sasomers TAILQ_HEAD(bfhead, bfelem) head; 1981590Srgrimes 199314427Sasomers TAILQ_INIT(&head); 200314427Sasomers 201314427Sasomers while (!feof(fp)) { 202314427Sasomers size_t len; 203314427Sasomers 2041590Srgrimes /* 2051590Srgrimes * Allocate a new block and link it into place in a doubly 2061590Srgrimes * linked list. If out of memory, toss the LRU block and 2071590Srgrimes * keep going. 2081590Srgrimes */ 209314427Sasomers while ((tl = malloc(sizeof(bfelem_t))) == NULL) { 210314427Sasomers first = TAILQ_FIRST(&head); 211314427Sasomers if (TAILQ_EMPTY(&head)) 21217825Speter err(1, "malloc"); 213314427Sasomers enomem += first->len; 214314427Sasomers TAILQ_REMOVE(&head, first, entries); 215314427Sasomers free(first); 21694609Sdwmalone } 217314427Sasomers TAILQ_INSERT_TAIL(&head, tl, entries); 2181590Srgrimes 2191590Srgrimes /* Fill the block with input data. */ 220314427Sasomers len = 0; 221314427Sasomers while ((!feof(fp)) && len < BSZ) { 222314427Sasomers p = tl->l + len; 223314427Sasomers len += fread(p, 1, BSZ - len, fp); 224314427Sasomers if (ferror(fp)) { 225314427Sasomers ierr(fn); 226314427Sasomers return; 227314427Sasomers } 22817339Sadam } 22917339Sadam 2301590Srgrimes tl->len = len; 2311590Srgrimes } 2321590Srgrimes 2331590Srgrimes if (enomem) { 234139994Sdwmalone warnx("warning: %jd bytes discarded", (intmax_t)enomem); 2351590Srgrimes rval = 1; 2361590Srgrimes } 2371590Srgrimes 2381590Srgrimes /* 239314427Sasomers * Now print the lines in reverse order 240314427Sasomers * Outline: 241314427Sasomers * Scan backward for "\n", 242314427Sasomers * print forward to the end of the buffers 243314427Sasomers * free any buffers that start after the "\n" just found 244314427Sasomers * Loop 2451590Srgrimes */ 246314427Sasomers tl = TAILQ_LAST(&head, bfhead); 247314427Sasomers first = TAILQ_FIRST(&head); 248314427Sasomers while (tl != NULL) { 249314427Sasomers struct bfelem *temp; 250314427Sasomers 251314427Sasomers for (p = tl->l + tl->len - 1, llen = 0; p >= tl->l; 252314427Sasomers --p, ++llen) { 253314427Sasomers int start = (tl == first && p == tl->l); 254314427Sasomers 255314427Sasomers if ((*p == '\n') || start) { 256314427Sasomers struct bfelem *tr; 257314427Sasomers 258332600Sasomers if (llen && start && *p != '\n') 259314427Sasomers WR(p, llen + 1); 260332600Sasomers else if (llen) { 2611590Srgrimes WR(p + 1, llen); 262332600Sasomers if (start && *p == '\n') 263332600Sasomers WR(p, 1); 264332600Sasomers } 265314427Sasomers tr = TAILQ_NEXT(tl, entries); 266314427Sasomers llen = 0; 267314427Sasomers if (tr != NULL) { 268314427Sasomers TAILQ_FOREACH_FROM_SAFE(tr, &head, 269314427Sasomers entries, temp) { 270314427Sasomers if (tr->len) 271314427Sasomers WR(&tr->l, tr->len); 272314427Sasomers TAILQ_REMOVE(&head, tr, 273314427Sasomers entries); 274314427Sasomers free(tr); 275314427Sasomers } 2761590Srgrimes } 2771590Srgrimes } 278314427Sasomers } 2791590Srgrimes tl->len = llen; 280314427Sasomers tl = TAILQ_PREV(tl, bfhead, entries); 2811590Srgrimes } 282314427Sasomers TAILQ_REMOVE(&head, first, entries); 283314427Sasomers free(first); 2841590Srgrimes} 285