reverse.c revision 69552
180709Sjake/*- 280709Sjake * Copyright (c) 1991, 1993 380709Sjake * The Regents of the University of California. All rights reserved. 480709Sjake * 580709Sjake * This code is derived from software contributed to Berkeley by 680709Sjake * Edward Sze-Tyan Wang. 780709Sjake * 880709Sjake * Redistribution and use in source and binary forms, with or without 980709Sjake * modification, are permitted provided that the following conditions 1080709Sjake * are met: 1180709Sjake * 1. Redistributions of source code must retain the above copyright 1280709Sjake * notice, this list of conditions and the following disclaimer. 1380709Sjake * 2. Redistributions in binary form must reproduce the above copyright 1481337Sobrien * notice, this list of conditions and the following disclaimer in the 1580709Sjake * documentation and/or other materials provided with the distribution. 1680709Sjake * 3. All advertising materials mentioning features or use of this software 1781337Sobrien * must display the following acknowledgement: 1880709Sjake * This product includes software developed by the University of 1980709Sjake * California, Berkeley and its contributors. 2080709Sjake * 4. Neither the name of the University nor the names of its contributors 2180709Sjake * may be used to endorse or promote products derived from this software 2280709Sjake * without specific prior written permission. 2380709Sjake * 2480709Sjake * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 2580709Sjake * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 2680709Sjake * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 27155839Smarius * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 28155839Smarius * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 29155839Smarius * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 3080709Sjake * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 3180709Sjake * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 32131952Smarcel * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 3380709Sjake * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 34148666Sjeff * SUCH DAMAGE. 3586525Sjake */ 3680709Sjake 3780709Sjake#ifndef lint 3880709Sjake#if 0 3980709Sjakestatic char sccsid[] = "@(#)reverse.c 8.1 (Berkeley) 6/6/93"; 4080709Sjake#endif 4180709Sjakestatic const char rcsid[] = 42138129Sdas "$FreeBSD: head/usr.bin/tail/reverse.c 69552 2000-12-03 17:05:45Z asmodai $"; 43174195Srwatson#endif /* not lint */ 4480709Sjake 4580709Sjake#include <sys/param.h> 4680709Sjake#include <sys/stat.h> 4780709Sjake#include <sys/mman.h> 4880709Sjake 4980709Sjake#include <limits.h> 5080709Sjake#include <errno.h> 5180709Sjake#include <unistd.h> 5280709Sjake#include <stdio.h> 53131952Smarcel#include <stdlib.h> 54131952Smarcel#include <string.h> 55131952Smarcel#include <err.h> 5680709Sjake#include "extern.h" 57131952Smarcel 58131952Smarcelstatic void r_buf __P((FILE *)); 59131952Smarcelstatic void r_reg __P((FILE *, enum STYLE, long, struct stat *)); 60131952Smarcel 61131952Smarcel/* 62131952Smarcel * reverse -- display input in reverse order by line. 63131952Smarcel * 64131952Smarcel * There are six separate cases for this -- regular and non-regular 65131952Smarcel * files by bytes, lines or the whole file. 66131952Smarcel * 67131952Smarcel * BYTES display N bytes 68131952Smarcel * REG mmap the file and display the lines 69131952Smarcel * NOREG cyclically read characters into a wrap-around buffer 70131952Smarcel * 71131952Smarcel * LINES display N lines 72131952Smarcel * REG mmap the file and display the lines 73131952Smarcel * NOREG cyclically read lines into a wrap-around array of buffers 74131952Smarcel * 75131952Smarcel * FILE display the entire file 7680709Sjake * REG mmap the file and display the lines 7780709Sjake * NOREG cyclically read input into a linked list of buffers 7880709Sjake */ 79131952Smarcelvoid 80131952Smarcelreverse(fp, style, off, sbp) 8180709Sjake FILE *fp; 82131952Smarcel enum STYLE style; 8380709Sjake long off; 84131952Smarcel struct stat *sbp; 85131952Smarcel{ 86131952Smarcel if (style != REVERSE && off == 0) 87131952Smarcel return; 88131952Smarcel 89131952Smarcel if (S_ISREG(sbp->st_mode)) 90131952Smarcel r_reg(fp, style, off, sbp); 91131952Smarcel else 92131952Smarcel switch(style) { 93131952Smarcel case FBYTES: 94131952Smarcel case RBYTES: 95131952Smarcel bytes(fp, off); 96131952Smarcel break; 97131952Smarcel case FLINES: 98160312Sjhb case RLINES: 99131952Smarcel lines(fp, off); 100131952Smarcel break; 101131952Smarcel case REVERSE: 102131952Smarcel r_buf(fp); 103131952Smarcel break; 104131952Smarcel } 105131952Smarcel} 106131952Smarcel 107131952Smarcel/* 108131952Smarcel * r_reg -- display a regular file in reverse order by line. 109131952Smarcel */ 110160312Sjhbstatic void 111131952Smarcelr_reg(fp, style, off, sbp) 112131952Smarcel FILE *fp; 113131952Smarcel enum STYLE style; 114131952Smarcel long off; 115131952Smarcel struct stat *sbp; 116131952Smarcel{ 117131952Smarcel off_t size; 118131952Smarcel int llen; 119131952Smarcel char *p; 12088635Sjake char *start; 12186525Sjake 122131952Smarcel if (!(size = sbp->st_size)) 123131952Smarcel return; 124131952Smarcel 125131952Smarcel if (size > SIZE_T_MAX) { 126131952Smarcel errno = EFBIG; 127131952Smarcel ierr(); 128131952Smarcel return; 129131952Smarcel } 13080709Sjake 13180709Sjake if ((start = mmap(NULL, (size_t)size, 132131952Smarcel PROT_READ, MAP_SHARED, fileno(fp), (off_t)0)) == MAP_FAILED) { 13380709Sjake ierr(); 13480709Sjake return; 13581379Sjake } 136160312Sjhb p = start + size - 1; 13780709Sjake 13893028Sjake if (style == RBYTES && off < size) 13986525Sjake size = off; 14086525Sjake 14186525Sjake /* Last char is special, ignore whether newline or not. */ 14286525Sjake for (llen = 1; --size; ++llen) 14386525Sjake if (*--p == '\n') { 14480709Sjake WR(p + 1, llen); 14588635Sjake llen = 0; 14688635Sjake if (style == RLINES && !--off) { 14788635Sjake ++p; 14888635Sjake break; 14988635Sjake } 15086525Sjake } 15193028Sjake if (llen) 15288635Sjake WR(p, llen); 15380709Sjake if (munmap(start, (size_t)sbp->st_size)) 15493028Sjake ierr(); 15588635Sjake} 15688635Sjake 15786525Sjaketypedef struct bf { 15880709Sjake struct bf *next; 15988635Sjake struct bf *prev; 16088635Sjake int len; 16188635Sjake char *l; 16288635Sjake} BF; 16388635Sjake 16488635Sjake/* 16588635Sjake * r_buf -- display a non-regular file in reverse order by line. 16688635Sjake * 16788635Sjake * This is the function that saves the entire input, storing the data in a 16888635Sjake * doubly linked list of buffers and then displays them in reverse order. 16988635Sjake * It has the usual nastiness of trying to find the newlines, as there's no 17088635Sjake * guarantee that a newline occurs anywhere in the file, let alone in any 17188635Sjake * particular buffer. If we run out of memory, input is discarded (and the 17280709Sjake * user warned). 17388635Sjake */ 17488635Sjakestatic void 17588635Sjaker_buf(fp) 17688635Sjake FILE *fp; 17788635Sjake{ 17888635Sjake BF *mark, *tl, *tr; 17986525Sjake int ch, len, llen; 18086525Sjake char *p; 18188635Sjake off_t enomem; 18286525Sjake 18386525Sjake#define BSZ (128 * 1024) 18486525Sjake for (mark = NULL, enomem = 0;;) { 18586525Sjake /* 18686525Sjake * Allocate a new block and link it into place in a doubly 18786525Sjake * linked list. If out of memory, toss the LRU block and 18886525Sjake * keep going. 18986525Sjake */ 19086525Sjake if (enomem || (tl = malloc(sizeof(BF))) == NULL || 19186525Sjake (tl->l = malloc(BSZ)) == NULL) { 19286525Sjake if (!mark) 19386525Sjake err(1, "malloc"); 19488635Sjake tl = enomem ? tl->next : mark; 19588635Sjake enomem += tl->len; 19688635Sjake } else if (mark) { 19788635Sjake tl->next = mark; 19888635Sjake tl->prev = mark->prev; 19988635Sjake mark->prev->next = tl; 20088635Sjake mark->prev = tl; 20180709Sjake } else 20280709Sjake mark->next = mark->prev = (mark = tl); 20380709Sjake 20493028Sjake /* Fill the block with input data. */ 20593028Sjake for (p = tl->l, len = 0; 20693028Sjake len < BSZ && (ch = getc(fp)) != EOF; ++len) 20788635Sjake *p++ = ch; 20888635Sjake 20988635Sjake if (ferror(fp)) { 21088635Sjake ierr(); 21188635Sjake return; 21288635Sjake } 21388635Sjake 214160312Sjhb /* 21580709Sjake * If no input data for this block and we tossed some data, 21688635Sjake * recover it. 21780709Sjake */ 21893028Sjake if (!len) { 219131952Smarcel if (enomem) 220131952Smarcel enomem -= tl->len; 22193028Sjake tl = tl->prev; 222131952Smarcel break; 223131952Smarcel } 224131952Smarcel 225131952Smarcel tl->len = len; 226131952Smarcel if (ch == EOF) 227131952Smarcel break; 228131952Smarcel } 229131952Smarcel 230131952Smarcel if (enomem) { 23193028Sjake warnx("warning: %qd bytes discarded", enomem); 232131952Smarcel rval = 1; 233131952Smarcel } 234131952Smarcel 235131952Smarcel /* 236131952Smarcel * Step through the blocks in the reverse order read. The last char 237131952Smarcel * is special, ignore whether newline or not. 238160312Sjhb */ 239131952Smarcel for (mark = tl;;) { 240131952Smarcel for (p = tl->l + (len = tl->len) - 1, llen = 0; len--; 241131952Smarcel --p, ++llen) 242131952Smarcel if (*p == '\n') { 243131952Smarcel if (llen) { 24493028Sjake WR(p + 1, llen); 245131952Smarcel llen = 0; 246131952Smarcel } 247131952Smarcel if (tl == mark) 248131952Smarcel continue; 249131952Smarcel for (tr = tl->next; tr->len; tr = tr->next) { 250131952Smarcel WR(tr->l, tr->len); 251131952Smarcel tr->len = 0; 252131952Smarcel if (tr == mark) 253131952Smarcel break; 254131952Smarcel } 255131952Smarcel } 256131952Smarcel tl->len = llen; 257155839Smarius if ((tl = tl->prev) == mark) 258155839Smarius break; 259155839Smarius } 260155839Smarius tl = tl->next; 261131952Smarcel if (tl->len) { 262131952Smarcel WR(tl->l, tl->len); 263131952Smarcel tl->len = 0; 264160312Sjhb } 265131952Smarcel while ((tl = tl->next)->len) { 266131952Smarcel WR(tl->l, tl->len); 267131952Smarcel tl->len = 0; 268131952Smarcel } 269131952Smarcel} 27093028Sjake