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