reverse.c revision 94609 
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#if 0
38#ifndef lint
39static char sccsid[] = "@(#)reverse.c	8.1 (Berkeley) 6/6/93";
40#endif /* not lint */
41#endif
42
43#include <sys/cdefs.h>
44__FBSDID("$FreeBSD: head/usr.bin/tail/reverse.c 94609 2002-04-13 20:59:48Z dwmalone $");
45
46#include <sys/param.h>
47#include <sys/stat.h>
48#include <sys/mman.h>
49
50#include <err.h>
51#include <errno.h>
52#include <limits.h>
53#include <stdio.h>
54#include <stdlib.h>
55#include <string.h>
56#include <unistd.h>
57
58#include "extern.h"
59
60static void r_buf(FILE *);
61static void r_reg(FILE *, enum STYLE, off_t, struct stat *);
62
63/*
64 * reverse -- display input in reverse order by line.
65 *
66 * There are six separate cases for this -- regular and non-regular
67 * files by bytes, lines or the whole file.
68 *
69 * BYTES	display N bytes
70 *	REG	mmap the file and display the lines
71 *	NOREG	cyclically read characters into a wrap-around buffer
72 *
73 * LINES	display N lines
74 *	REG	mmap the file and display the lines
75 *	NOREG	cyclically read lines into a wrap-around array of buffers
76 *
77 * FILE		display the entire file
78 *	REG	mmap the file and display the lines
79 *	NOREG	cyclically read input into a linked list of buffers
80 */
81void
82reverse(fp, style, off, sbp)
83	FILE *fp;
84	enum STYLE style;
85	off_t off;
86	struct stat *sbp;
87{
88	if (style != REVERSE && off == 0)
89		return;
90
91	if (S_ISREG(sbp->st_mode))
92		r_reg(fp, style, off, sbp);
93	else
94		switch(style) {
95		case FBYTES:
96		case RBYTES:
97			bytes(fp, off);
98			break;
99		case FLINES:
100		case RLINES:
101			lines(fp, off);
102			break;
103		case REVERSE:
104			r_buf(fp);
105			break;
106		default:
107			break;
108		}
109}
110
111/*
112 * r_reg -- display a regular file in reverse order by line.
113 */
114static void
115r_reg(fp, style, off, sbp)
116	FILE *fp;
117	enum STYLE style;
118	off_t off;
119	struct stat *sbp;
120{
121	struct mapinfo map;
122	off_t curoff, size, lineend;
123	int i;
124
125	if (!(size = sbp->st_size))
126		return;
127
128	map.start = NULL;
129	map.mapoff = map.maxoff = size;
130	map.fd = fileno(fp);
131
132	/*
133	 * Last char is special, ignore whether newline or not. Note that
134	 * size == 0 is dealt with above, and size == 1 sets curoff to -1.
135	 */
136	curoff = size - 2;
137	lineend = size;
138	while (curoff >= 0) {
139		if (curoff < map.mapoff || curoff >= map.mapoff + map.maplen) {
140			if (maparound(&map, curoff) != 0) {
141				ierr();
142				return;
143			}
144		}
145		for (i = curoff - map.mapoff; i >= 0; i--) {
146			if (style == RBYTES && --off == 0)
147				break;
148			if (map.start[i] == '\n')
149				break;
150		}
151		/* `i' is either the map offset of a '\n', or -1. */
152		curoff = map.mapoff + i;
153		if (i < 0)
154			continue;
155
156		/* Print the line and update offsets. */
157		if (mapprint(&map, curoff + 1, lineend - curoff - 1) != 0) {
158			ierr();
159			return;
160		}
161		lineend = curoff + 1;
162		curoff--;
163
164		if (style == RLINES)
165			off--;
166
167		if (off == 0 && style != REVERSE) {
168			/* Avoid printing anything below. */
169			curoff = 0;
170			break;
171		}
172	}
173	if (curoff < 0 && mapprint(&map, 0, lineend) != 0) {
174		ierr();
175		return;
176	}
177	if (map.start != NULL && munmap(map.start, map.maplen))
178		ierr();
179}
180
181typedef struct bf {
182	struct bf *next;
183	struct bf *prev;
184	int len;
185	char *l;
186} BF;
187
188/*
189 * r_buf -- display a non-regular file in reverse order by line.
190 *
191 * This is the function that saves the entire input, storing the data in a
192 * doubly linked list of buffers and then displays them in reverse order.
193 * It has the usual nastiness of trying to find the newlines, as there's no
194 * guarantee that a newline occurs anywhere in the file, let alone in any
195 * particular buffer.  If we run out of memory, input is discarded (and the
196 * user warned).
197 */
198static void
199r_buf(fp)
200	FILE *fp;
201{
202	BF *mark, *tl, *tr;
203	int ch, len, llen;
204	char *p;
205	off_t enomem;
206
207#define	BSZ	(128 * 1024)
208	for (mark = NULL, enomem = 0;;) {
209		/*
210		 * Allocate a new block and link it into place in a doubly
211		 * linked list.  If out of memory, toss the LRU block and
212		 * keep going.
213		 */
214		if (enomem || (tl = malloc(sizeof(BF))) == NULL ||
215		    (tl->l = malloc(BSZ)) == NULL) {
216			if (!mark)
217				err(1, "malloc");
218			tl = enomem ? tl->next : mark;
219			enomem += tl->len;
220		} else if (mark) {
221			tl->next = mark;
222			tl->prev = mark->prev;
223			mark->prev->next = tl;
224			mark->prev = tl;
225		} else {
226			mark = tl;
227			mark->next = mark->prev = mark;
228		}
229
230		/* Fill the block with input data. */
231		for (p = tl->l, len = 0;
232		    len < BSZ && (ch = getc(fp)) != EOF; ++len)
233			*p++ = ch;
234
235		if (ferror(fp)) {
236			ierr();
237			return;
238		}
239
240		/*
241		 * If no input data for this block and we tossed some data,
242		 * recover it.
243		 */
244		if (!len) {
245			if (enomem)
246				enomem -= tl->len;
247			tl = tl->prev;
248			break;
249		}
250
251		tl->len = len;
252		if (ch == EOF)
253			break;
254	}
255
256	if (enomem) {
257		warnx("warning: %qd bytes discarded", enomem);
258		rval = 1;
259	}
260
261	/*
262	 * Step through the blocks in the reverse order read.  The last char
263	 * is special, ignore whether newline or not.
264	 */
265	for (mark = tl;;) {
266		for (p = tl->l + (len = tl->len) - 1, llen = 0; len--;
267		    --p, ++llen)
268			if (*p == '\n') {
269				if (llen) {
270					WR(p + 1, llen);
271					llen = 0;
272				}
273				if (tl == mark)
274					continue;
275				for (tr = tl->next; tr->len; tr = tr->next) {
276					WR(tr->l, tr->len);
277					tr->len = 0;
278					if (tr == mark)
279						break;
280				}
281			}
282		tl->len = llen;
283		if ((tl = tl->prev) == mark)
284			break;
285	}
286	tl = tl->next;
287	if (tl->len) {
288		WR(tl->l, tl->len);
289		tl->len = 0;
290	}
291	while ((tl = tl->next)->len) {
292		WR(tl->l, tl->len);
293		tl->len = 0;
294	}
295}
296