reverse.c revision 1590 
1/*-
2 * Copyright (c) 1991, 1993
3 *	The Regents of the University of California.  All rights reserved.
4 *
5 * This code is derived from software contributed to Berkeley by
6 * Edward Sze-Tyan Wang.
7 *
8 * Redistribution and use in source and binary forms, with or without
9 * modification, are permitted provided that the following conditions
10 * are met:
11 * 1. Redistributions of source code must retain the above copyright
12 *    notice, this list of conditions and the following disclaimer.
13 * 2. Redistributions in binary form must reproduce the above copyright
14 *    notice, this list of conditions and the following disclaimer in the
15 *    documentation and/or other materials provided with the distribution.
16 * 3. All advertising materials mentioning features or use of this software
17 *    must display the following acknowledgement:
18 *	This product includes software developed by the University of
19 *	California, Berkeley and its contributors.
20 * 4. Neither the name of the University nor the names of its contributors
21 *    may be used to endorse or promote products derived from this software
22 *    without specific prior written permission.
23 *
24 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
25 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
26 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
27 * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
28 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
29 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
30 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
31 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
32 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
33 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
34 * SUCH DAMAGE.
35 */
36
37#ifndef lint
38static char sccsid[] = "@(#)reverse.c	8.1 (Berkeley) 6/6/93";
39#endif /* not lint */
40
41#include <sys/param.h>
42#include <sys/stat.h>
43#include <sys/mman.h>
44
45#include <limits.h>
46#include <errno.h>
47#include <unistd.h>
48#include <stdio.h>
49#include <stdlib.h>
50#include <string.h>
51#include "extern.h"
52
53static void r_buf __P((FILE *));
54static void r_reg __P((FILE *, enum STYLE, long, struct stat *));
55
56/*
57 * reverse -- display input in reverse order by line.
58 *
59 * There are six separate cases for this -- regular and non-regular
60 * files by bytes, lines or the whole file.
61 *
62 * BYTES	display N bytes
63 *	REG	mmap the file and display the lines
64 *	NOREG	cyclically read characters into a wrap-around buffer
65 *
66 * LINES	display N lines
67 *	REG	mmap the file and display the lines
68 *	NOREG	cyclically read lines into a wrap-around array of buffers
69 *
70 * FILE		display the entire file
71 *	REG	mmap the file and display the lines
72 *	NOREG	cyclically read input into a linked list of buffers
73 */
74void
75reverse(fp, style, off, sbp)
76	FILE *fp;
77	enum STYLE style;
78	long off;
79	struct stat *sbp;
80{
81	if (style != REVERSE && off == 0)
82		return;
83
84	if (S_ISREG(sbp->st_mode))
85		r_reg(fp, style, off, sbp);
86	else
87		switch(style) {
88		case FBYTES:
89		case RBYTES:
90			bytes(fp, off);
91			break;
92		case FLINES:
93		case RLINES:
94			lines(fp, off);
95			break;
96		case REVERSE:
97			r_buf(fp);
98			break;
99		}
100}
101
102/*
103 * r_reg -- display a regular file in reverse order by line.
104 */
105static void
106r_reg(fp, style, off, sbp)
107	FILE *fp;
108	register enum STYLE style;
109	long off;
110	struct stat *sbp;
111{
112	register off_t size;
113	register int llen;
114	register char *p;
115	char *start;
116
117	if (!(size = sbp->st_size))
118		return;
119
120	if (size > SIZE_T_MAX) {
121		err(0, "%s: %s", fname, strerror(EFBIG));
122		return;
123	}
124
125	if ((start = mmap(NULL, (size_t)size,
126	    PROT_READ, 0, fileno(fp), (off_t)0)) == (caddr_t)-1) {
127		err(0, "%s: %s", fname, strerror(EFBIG));
128		return;
129	}
130	p = start + size - 1;
131
132	if (style == RBYTES && off < size)
133		size = off;
134
135	/* Last char is special, ignore whether newline or not. */
136	for (llen = 1; --size; ++llen)
137		if (*--p == '\n') {
138			WR(p + 1, llen);
139			llen = 0;
140			if (style == RLINES && !--off) {
141				++p;
142				break;
143			}
144		}
145	if (llen)
146		WR(p, llen);
147	if (munmap(start, (size_t)sbp->st_size))
148		err(0, "%s: %s", fname, strerror(errno));
149}
150
151typedef struct bf {
152	struct bf *next;
153	struct bf *prev;
154	int len;
155	char *l;
156} BF;
157
158/*
159 * r_buf -- display a non-regular file in reverse order by line.
160 *
161 * This is the function that saves the entire input, storing the data in a
162 * doubly linked list of buffers and then displays them in reverse order.
163 * It has the usual nastiness of trying to find the newlines, as there's no
164 * guarantee that a newline occurs anywhere in the file, let alone in any
165 * particular buffer.  If we run out of memory, input is discarded (and the
166 * user warned).
167 */
168static void
169r_buf(fp)
170	FILE *fp;
171{
172	register BF *mark, *tl, *tr;
173	register int ch, len, llen;
174	register char *p;
175	off_t enomem;
176
177#define	BSZ	(128 * 1024)
178	for (mark = NULL, enomem = 0;;) {
179		/*
180		 * Allocate a new block and link it into place in a doubly
181		 * linked list.  If out of memory, toss the LRU block and
182		 * keep going.
183		 */
184		if (enomem || (tl = malloc(sizeof(BF))) == NULL ||
185		    (tl->l = malloc(BSZ)) == NULL) {
186			if (!mark)
187				err(1, "%s", strerror(errno));
188			tl = enomem ? tl->next : mark;
189			enomem += tl->len;
190		} else if (mark) {
191			tl->next = mark;
192			tl->prev = mark->prev;
193			mark->prev->next = tl;
194			mark->prev = tl;
195		} else
196			mark->next = mark->prev = (mark = tl);
197
198		/* Fill the block with input data. */
199		for (p = tl->l, len = 0;
200		    len < BSZ && (ch = getc(fp)) != EOF; ++len)
201			*p++ = ch;
202
203		/*
204		 * If no input data for this block and we tossed some data,
205		 * recover it.
206		 */
207		if (!len) {
208			if (enomem)
209				enomem -= tl->len;
210			tl = tl->prev;
211			break;
212		}
213
214		tl->len = len;
215		if (ch == EOF)
216			break;
217	}
218
219	if (enomem) {
220		(void)fprintf(stderr,
221		    "tail: warning: %ld bytes discarded\n", enomem);
222		rval = 1;
223	}
224
225	/*
226	 * Step through the blocks in the reverse order read.  The last char
227	 * is special, ignore whether newline or not.
228	 */
229	for (mark = tl;;) {
230		for (p = tl->l + (len = tl->len) - 1, llen = 0; len--;
231		    --p, ++llen)
232			if (*p == '\n') {
233				if (llen) {
234					WR(p + 1, llen);
235					llen = 0;
236				}
237				if (tl == mark)
238					continue;
239				for (tr = tl->next; tr->len; tr = tr->next) {
240					WR(tr->l, tr->len);
241					tr->len = 0;
242					if (tr == mark)
243						break;
244				}
245			}
246		tl->len = llen;
247		if ((tl = tl->prev) == mark)
248			break;
249	}
250	tl = tl->next;
251	if (tl->len) {
252		WR(tl->l, tl->len);
253		tl->len = 0;
254	}
255	while ((tl = tl->next)->len) {
256		WR(tl->l, tl->len);
257		tl->len = 0;
258	}
259}
260