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