1*4c3aa522Stedu /* $OpenBSD: reverse.c,v 1.21 2015/11/19 17:50:04 tedu Exp $ */
2df930be7Sderaadt /* $NetBSD: reverse.c,v 1.6 1994/11/23 07:42:10 jtc Exp $ */
3df930be7Sderaadt
4df930be7Sderaadt /*-
5df930be7Sderaadt * Copyright (c) 1991, 1993
6df930be7Sderaadt * The Regents of the University of California. All rights reserved.
7df930be7Sderaadt *
8df930be7Sderaadt * This code is derived from software contributed to Berkeley by
9df930be7Sderaadt * Edward Sze-Tyan Wang.
10df930be7Sderaadt *
11df930be7Sderaadt * Redistribution and use in source and binary forms, with or without
12df930be7Sderaadt * modification, are permitted provided that the following conditions
13df930be7Sderaadt * are met:
14df930be7Sderaadt * 1. Redistributions of source code must retain the above copyright
15df930be7Sderaadt * notice, this list of conditions and the following disclaimer.
16df930be7Sderaadt * 2. Redistributions in binary form must reproduce the above copyright
17df930be7Sderaadt * notice, this list of conditions and the following disclaimer in the
18df930be7Sderaadt * documentation and/or other materials provided with the distribution.
19f75387cbSmillert * 3. Neither the name of the University nor the names of its contributors
20df930be7Sderaadt * may be used to endorse or promote products derived from this software
21df930be7Sderaadt * without specific prior written permission.
22df930be7Sderaadt *
23df930be7Sderaadt * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
24df930be7Sderaadt * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
25df930be7Sderaadt * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
26df930be7Sderaadt * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
27df930be7Sderaadt * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
28df930be7Sderaadt * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
29df930be7Sderaadt * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
30df930be7Sderaadt * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
31df930be7Sderaadt * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
32df930be7Sderaadt * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
33df930be7Sderaadt * SUCH DAMAGE.
34df930be7Sderaadt */
35df930be7Sderaadt
36df930be7Sderaadt #include <sys/stat.h>
37df930be7Sderaadt
387a512528Smillert #include <err.h>
39df930be7Sderaadt #include <stdio.h>
40df930be7Sderaadt #include <stdlib.h>
417a512528Smillert #include <unistd.h>
427a512528Smillert
43df930be7Sderaadt #include "extern.h"
44df930be7Sderaadt
45c72b5b24Smillert static void r_buf(FILE *);
46*4c3aa522Stedu static int r_reg(struct tailfile *, enum STYLE, off_t);
47df930be7Sderaadt
48*4c3aa522Stedu #define COPYCHAR(tf, ch) \
494666f4c8Shenning do { \
50*4c3aa522Stedu if ((ch = getc(tf->fp)) == EOF) { \
51*4c3aa522Stedu ierr(tf->fname); \
524666f4c8Shenning return (0); \
534666f4c8Shenning } \
544666f4c8Shenning if (putchar(ch) == EOF) { \
554666f4c8Shenning oerr(); \
564666f4c8Shenning return (0); \
574666f4c8Shenning } \
584666f4c8Shenning } while (0)
594666f4c8Shenning
60df930be7Sderaadt /*
61df930be7Sderaadt * reverse -- display input in reverse order by line.
62df930be7Sderaadt *
63df930be7Sderaadt * There are six separate cases for this -- regular and non-regular
64df930be7Sderaadt * files by bytes, lines or the whole file.
65df930be7Sderaadt *
66df930be7Sderaadt * BYTES display N bytes
674666f4c8Shenning * REG reverse scan and display the lines
68df930be7Sderaadt * NOREG cyclically read characters into a wrap-around buffer
69df930be7Sderaadt *
70df930be7Sderaadt * LINES display N lines
714666f4c8Shenning * REG reverse scan and display the lines
72df930be7Sderaadt * NOREG cyclically read lines into a wrap-around array of buffers
73df930be7Sderaadt *
74df930be7Sderaadt * FILE display the entire file
754666f4c8Shenning * REG reverse scan and display the lines
76df930be7Sderaadt * NOREG cyclically read input into a linked list of buffers
77df930be7Sderaadt */
78df930be7Sderaadt void
reverse(struct tailfile * tf,int nfiles,enum STYLE style,off_t off)79*4c3aa522Stedu reverse(struct tailfile *tf, int nfiles, enum STYLE style, off_t off)
80df930be7Sderaadt {
81*4c3aa522Stedu int i;
82*4c3aa522Stedu
83df930be7Sderaadt if (style != REVERSE && off == 0)
84df930be7Sderaadt return;
85df930be7Sderaadt
86*4c3aa522Stedu for (i = 0; i < nfiles; i++) {
87*4c3aa522Stedu if (nfiles > 1)
88*4c3aa522Stedu printfname(tf[i].fname);
89*4c3aa522Stedu if (!S_ISREG(tf[i].sb.st_mode) ||
90*4c3aa522Stedu r_reg(&(tf[i]), style, off) != 0) {
91df930be7Sderaadt switch(style) {
92df930be7Sderaadt case FBYTES:
93df930be7Sderaadt case RBYTES:
94*4c3aa522Stedu (void)bytes(&(tf[i]), off);
95df930be7Sderaadt break;
96df930be7Sderaadt case FLINES:
97df930be7Sderaadt case RLINES:
98*4c3aa522Stedu (void)lines(&(tf[i]), off);
99df930be7Sderaadt break;
100df930be7Sderaadt case REVERSE:
101*4c3aa522Stedu r_buf(tf[i].fp);
102df930be7Sderaadt break;
103*4c3aa522Stedu default:
104*4c3aa522Stedu err(1, "Unsupported style");
105*4c3aa522Stedu }
106*4c3aa522Stedu }
107df930be7Sderaadt }
108df930be7Sderaadt }
109df930be7Sderaadt
110df930be7Sderaadt /*
111df930be7Sderaadt * r_reg -- display a regular file in reverse order by line.
112df930be7Sderaadt */
113a8e7967cSmillert static int
r_reg(struct tailfile * tf,enum STYLE style,off_t off)114*4c3aa522Stedu r_reg(struct tailfile *tf, enum STYLE style, off_t off)
115df930be7Sderaadt {
1164666f4c8Shenning off_t start, pos, end;
1174666f4c8Shenning int ch;
118df930be7Sderaadt
119*4c3aa522Stedu end = tf->sb.st_size;
1204666f4c8Shenning if (end == 0)
121a8e7967cSmillert return (0);
122df930be7Sderaadt
1234666f4c8Shenning /* Position before char, ignore last char whether newline or not */
1244666f4c8Shenning pos = end-2;
1254666f4c8Shenning ch = EOF;
1264666f4c8Shenning start = 0;
127df930be7Sderaadt
1284666f4c8Shenning if (style == RBYTES && off < end)
1294666f4c8Shenning start = end - off;
130df930be7Sderaadt
1314666f4c8Shenning for (; pos >= start; pos--) {
1324666f4c8Shenning /* A seek per char isn't a problem with a smart stdio */
133*4c3aa522Stedu if (fseeko(tf->fp, pos, SEEK_SET) != 0) {
134*4c3aa522Stedu ierr(tf->fname);
1354666f4c8Shenning return (0);
1364666f4c8Shenning }
137*4c3aa522Stedu if ((ch = getc(tf->fp)) == '\n') {
1384666f4c8Shenning while (--end > pos)
139*4c3aa522Stedu COPYCHAR(tf, ch);
1404666f4c8Shenning end++;
1414666f4c8Shenning if (style == RLINES && --off == 0)
142df930be7Sderaadt break;
143df930be7Sderaadt }
1444666f4c8Shenning else if (ch == EOF) {
145*4c3aa522Stedu ierr(tf->fname);
1464666f4c8Shenning return (0);
1474666f4c8Shenning }
1484666f4c8Shenning }
1494666f4c8Shenning if (pos < start) {
150*4c3aa522Stedu if (ch != EOF && ungetc(ch, tf->fp) == EOF) {
151*4c3aa522Stedu ierr(tf->fname);
1524666f4c8Shenning return (0);
1534666f4c8Shenning }
1544666f4c8Shenning while (--end >= start)
155*4c3aa522Stedu COPYCHAR(tf, ch);
1564666f4c8Shenning }
157a8e7967cSmillert return (0);
158df930be7Sderaadt }
159df930be7Sderaadt
16039436027Stobias #define BSZ (128 * 1024)
16139436027Stobias struct bf {
162df930be7Sderaadt struct bf *next;
163df930be7Sderaadt struct bf *prev;
1641bc532c6Skjell size_t len;
16539436027Stobias char l[BSZ];
16639436027Stobias };
167df930be7Sderaadt
168df930be7Sderaadt /*
169df930be7Sderaadt * r_buf -- display a non-regular file in reverse order by line.
170df930be7Sderaadt *
171df930be7Sderaadt * This is the function that saves the entire input, storing the data in a
172df930be7Sderaadt * doubly linked list of buffers and then displays them in reverse order.
173df930be7Sderaadt * It has the usual nastiness of trying to find the newlines, as there's no
174df930be7Sderaadt * guarantee that a newline occurs anywhere in the file, let alone in any
175df930be7Sderaadt * particular buffer. If we run out of memory, input is discarded (and the
176df930be7Sderaadt * user warned).
177df930be7Sderaadt */
178df930be7Sderaadt static void
r_buf(FILE * fp)179a1e90a1aSkjell r_buf(FILE *fp)
180df930be7Sderaadt {
18139436027Stobias struct bf *mark, *tr, *tl = NULL;
1821bc532c6Skjell int ch;
1831bc532c6Skjell size_t len, llen;
184c0932ef1Smpech char *p;
185df930be7Sderaadt off_t enomem;
186df930be7Sderaadt
187df930be7Sderaadt for (mark = NULL, enomem = 0;;) {
188df930be7Sderaadt /*
189df930be7Sderaadt * Allocate a new block and link it into place in a doubly
190df930be7Sderaadt * linked list. If out of memory, toss the LRU block and
191df930be7Sderaadt * keep going.
192df930be7Sderaadt */
19339436027Stobias if (enomem || (tl = malloc(sizeof(*tl))) == NULL) {
194df930be7Sderaadt if (!mark)
1957a512528Smillert err(1, NULL);
196df930be7Sderaadt tl = enomem ? tl->next : mark;
197df930be7Sderaadt enomem += tl->len;
198df930be7Sderaadt } else if (mark) {
199df930be7Sderaadt tl->next = mark;
200df930be7Sderaadt tl->prev = mark->prev;
201df930be7Sderaadt mark->prev->next = tl;
202df930be7Sderaadt mark->prev = tl;
2034318df1eSpjanzen } else {
2044318df1eSpjanzen mark = tl;
2054318df1eSpjanzen mark->next = mark->prev = mark;
2064318df1eSpjanzen }
207df930be7Sderaadt
208b2424cb6Smickey if (!enomem)
209b2424cb6Smickey tl->len = 0;
210b2424cb6Smickey
211df930be7Sderaadt /* Fill the block with input data. */
212df930be7Sderaadt for (p = tl->l, len = 0;
213df930be7Sderaadt len < BSZ && (ch = getc(fp)) != EOF; ++len)
214df930be7Sderaadt *p++ = ch;
215df930be7Sderaadt
216df930be7Sderaadt /*
217df930be7Sderaadt * If no input data for this block and we tossed some data,
218df930be7Sderaadt * recover it.
219df930be7Sderaadt */
220df930be7Sderaadt if (!len) {
221df930be7Sderaadt if (enomem)
222df930be7Sderaadt enomem -= tl->len;
223df930be7Sderaadt tl = tl->prev;
224df930be7Sderaadt break;
225df930be7Sderaadt }
226df930be7Sderaadt
227df930be7Sderaadt tl->len = len;
228df930be7Sderaadt if (ch == EOF)
229df930be7Sderaadt break;
230df930be7Sderaadt }
231df930be7Sderaadt
232df930be7Sderaadt if (enomem) {
233df930be7Sderaadt (void)fprintf(stderr,
2340c00f208Spvalchev "tail: warning: %lld bytes discarded\n", (long long)enomem);
235df930be7Sderaadt rval = 1;
236df930be7Sderaadt }
237df930be7Sderaadt
238df930be7Sderaadt /*
239df930be7Sderaadt * Step through the blocks in the reverse order read. The last char
240df930be7Sderaadt * is special, ignore whether newline or not.
241df930be7Sderaadt */
242df930be7Sderaadt for (mark = tl;;) {
243df930be7Sderaadt for (p = tl->l + (len = tl->len) - 1, llen = 0; len--;
244df930be7Sderaadt --p, ++llen)
245df930be7Sderaadt if (*p == '\n') {
246df930be7Sderaadt if (llen) {
247df930be7Sderaadt WR(p + 1, llen);
248df930be7Sderaadt llen = 0;
249df930be7Sderaadt }
250df930be7Sderaadt if (tl == mark)
251df930be7Sderaadt continue;
252df930be7Sderaadt for (tr = tl->next; tr->len; tr = tr->next) {
253df930be7Sderaadt WR(tr->l, tr->len);
254df930be7Sderaadt tr->len = 0;
255df930be7Sderaadt if (tr == mark)
256df930be7Sderaadt break;
257df930be7Sderaadt }
258df930be7Sderaadt }
259df930be7Sderaadt tl->len = llen;
260df930be7Sderaadt if ((tl = tl->prev) == mark)
261df930be7Sderaadt break;
262df930be7Sderaadt }
263df930be7Sderaadt tl = tl->next;
264df930be7Sderaadt if (tl->len) {
265df930be7Sderaadt WR(tl->l, tl->len);
266df930be7Sderaadt tl->len = 0;
267df930be7Sderaadt }
268df930be7Sderaadt while ((tl = tl->next)->len) {
269df930be7Sderaadt WR(tl->l, tl->len);
270df930be7Sderaadt tl->len = 0;
271df930be7Sderaadt }
27239436027Stobias
27339436027Stobias tl->prev->next = NULL;
27439436027Stobias while (tl != NULL) {
27539436027Stobias tr = tl->next;
27639436027Stobias free(tl);
27739436027Stobias tl = tr;
27839436027Stobias }
279df930be7Sderaadt }
280