1 /*-
2 * SPDX-License-Identifier: BSD-3-Clause
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 #if 0
36 #ifndef lint
37 static char sccsid[] = "@(#)reverse.c 8.1 (Berkeley) 6/6/93";
38 #endif /* not lint */
39 #endif
40
41 #include <sys/cdefs.h>
42 #include <sys/param.h>
43 #include <sys/queue.h>
44 #include <sys/stat.h>
45 #include <sys/mman.h>
46
47 #include <err.h>
48 #include <errno.h>
49 #include <limits.h>
50 #include <stdint.h>
51 #include <stdio.h>
52 #include <stdlib.h>
53 #include <string.h>
54 #include <unistd.h>
55
56 #include <libcasper.h>
57 #include <casper/cap_fileargs.h>
58
59 #include "extern.h"
60
61 static void r_buf(FILE *, const char *);
62 static void r_reg(FILE *, const char *, 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 */
82 void
reverse(FILE * fp,const char * fn,enum STYLE style,off_t off,struct stat * sbp)83 reverse(FILE *fp, const char *fn, 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, fn, style, off, sbp);
90 else
91 switch(style) {
92 case FBYTES:
93 case RBYTES:
94 bytes(fp, fn, off);
95 break;
96 case FLINES:
97 case RLINES:
98 lines(fp, fn, off);
99 break;
100 case REVERSE:
101 r_buf(fp, fn);
102 break;
103 default:
104 break;
105 }
106 }
107
108 /*
109 * r_reg -- display a regular file in reverse order by line.
110 */
111 static void
r_reg(FILE * fp,const char * fn,enum STYLE style,off_t off,struct stat * sbp)112 r_reg(FILE *fp, const char *fn, 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 map.maplen = 0;
125
126 /*
127 * Last char is special, ignore whether newline or not. Note that
128 * size == 0 is dealt with above, and size == 1 sets curoff to -1.
129 */
130 curoff = size - 2;
131 lineend = size;
132 while (curoff >= 0) {
133 if (curoff < map.mapoff ||
134 curoff >= map.mapoff + (off_t)map.maplen) {
135 if (maparound(&map, curoff) != 0) {
136 ierr(fn);
137 return;
138 }
139 }
140 for (i = curoff - map.mapoff; i >= 0; i--) {
141 if (style == RBYTES && --off == 0)
142 break;
143 if (map.start[i] == '\n')
144 break;
145 }
146 /* `i' is either the map offset of a '\n', or -1. */
147 curoff = map.mapoff + i;
148 if (i < 0)
149 continue;
150
151 /* Print the line and update offsets. */
152 if (mapprint(&map, curoff + 1, lineend - curoff - 1) != 0) {
153 ierr(fn);
154 return;
155 }
156 lineend = curoff + 1;
157 curoff--;
158
159 if (style == RLINES)
160 off--;
161
162 if (off == 0 && style != REVERSE) {
163 /* Avoid printing anything below. */
164 curoff = 0;
165 break;
166 }
167 }
168 if (curoff < 0 && mapprint(&map, 0, lineend) != 0) {
169 ierr(fn);
170 return;
171 }
172 if (map.start != NULL && munmap(map.start, map.maplen))
173 ierr(fn);
174 }
175
176 #define BSZ (128 * 1024)
177 typedef struct bfelem {
178 TAILQ_ENTRY(bfelem) entries;
179 size_t len;
180 char l[BSZ];
181 } bfelem_t;
182
183 /*
184 * r_buf -- display a non-regular file in reverse order by line.
185 *
186 * This is the function that saves the entire input, storing the data in a
187 * doubly linked list of buffers and then displays them in reverse order.
188 * It has the usual nastiness of trying to find the newlines, as there's no
189 * guarantee that a newline occurs anywhere in the file, let alone in any
190 * particular buffer. If we run out of memory, input is discarded (and the
191 * user warned).
192 */
193 static void
r_buf(FILE * fp,const char * fn)194 r_buf(FILE *fp, const char *fn)
195 {
196 struct bfelem *tl, *first = NULL;
197 size_t llen;
198 char *p;
199 off_t enomem = 0;
200 TAILQ_HEAD(bfhead, bfelem) head;
201
202 TAILQ_INIT(&head);
203
204 while (!feof(fp)) {
205 size_t len;
206
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 while ((tl = malloc(sizeof(bfelem_t))) == NULL) {
213 first = TAILQ_FIRST(&head);
214 if (TAILQ_EMPTY(&head))
215 err(1, "failed to allocate memory");
216 enomem += first->len;
217 TAILQ_REMOVE(&head, first, entries);
218 free(first);
219 }
220 TAILQ_INSERT_TAIL(&head, tl, entries);
221
222 /* Fill the block with input data. */
223 len = 0;
224 while ((!feof(fp)) && len < BSZ) {
225 p = tl->l + len;
226 len += fread(p, 1, BSZ - len, fp);
227 if (ferror(fp)) {
228 ierr(fn);
229 return;
230 }
231 }
232
233 tl->len = len;
234 }
235
236 if (enomem) {
237 warnx("warning: %jd bytes discarded", (intmax_t)enomem);
238 rval = 1;
239 }
240
241 /*
242 * Now print the lines in reverse order
243 * Outline:
244 * Scan backward for "\n",
245 * print forward to the end of the buffers
246 * free any buffers that start after the "\n" just found
247 * Loop
248 */
249 tl = TAILQ_LAST(&head, bfhead);
250 first = TAILQ_FIRST(&head);
251 while (tl != NULL) {
252 struct bfelem *temp;
253
254 for (p = tl->l + tl->len - 1, llen = 0; p >= tl->l;
255 --p, ++llen) {
256 int start = (tl == first && p == tl->l);
257
258 if ((*p == '\n') || start) {
259 struct bfelem *tr;
260
261 if (llen && start && *p != '\n')
262 WR(p, llen + 1);
263 else if (llen) {
264 WR(p + 1, llen);
265 if (start && *p == '\n')
266 WR(p, 1);
267 }
268 tr = TAILQ_NEXT(tl, entries);
269 llen = 0;
270 if (tr != NULL) {
271 TAILQ_FOREACH_FROM_SAFE(tr, &head,
272 entries, temp) {
273 if (tr->len)
274 WR(&tr->l, tr->len);
275 TAILQ_REMOVE(&head, tr,
276 entries);
277 free(tr);
278 }
279 }
280 }
281 }
282 tl->len = llen;
283 tl = TAILQ_PREV(tl, bfhead, entries);
284 }
285 TAILQ_REMOVE(&head, first, entries);
286 free(first);
287 }
288