xref: /openbsd-src/usr.bin/tail/reverse.c (revision 4c3aa5221481971528d2b80e7ad5c4366594a447)
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