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