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