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