Annotation of src/usr.bin/tail/reverse.c, Revision 1.15
1.15 ! otto 1: /* $OpenBSD: reverse.c,v 1.14 2003/07/01 11:12:59 henning Exp $ */
1.1 deraadt 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.
1.13 millert 19: * 3. Neither the name of the University nor the names of its contributors
1.1 deraadt 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
1.15 ! otto 40: static char rcsid[] = "$OpenBSD: reverse.c,v 1.14 2003/07/01 11:12:59 henning Exp $";
1.1 deraadt 41: #endif /* not lint */
42:
43: #include <sys/param.h>
44: #include <sys/stat.h>
45: #include <sys/mman.h>
46:
1.3 millert 47: #include <err.h>
48: #include <errno.h>
1.1 deraadt 49: #include <limits.h>
50: #include <stdio.h>
51: #include <stdlib.h>
52: #include <string.h>
1.3 millert 53: #include <unistd.h>
54:
1.1 deraadt 55: #include "extern.h"
56:
1.12 millert 57: static void r_buf(FILE *);
1.15 ! otto 58: static int r_reg(FILE *, enum STYLE, off_t, struct stat *);
1.1 deraadt 59:
1.14 henning 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:
1.1 deraadt 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
1.14 henning 79: * REG reverse scan and display the lines
1.1 deraadt 80: * NOREG cyclically read characters into a wrap-around buffer
81: *
82: * LINES display N lines
1.14 henning 83: * REG reverse scan and display the lines
1.1 deraadt 84: * NOREG cyclically read lines into a wrap-around array of buffers
85: *
86: * FILE display the entire file
1.14 henning 87: * REG reverse scan and display the lines
1.1 deraadt 88: * NOREG cyclically read input into a linked list of buffers
89: */
90: void
91: reverse(fp, style, off, sbp)
92: FILE *fp;
93: enum STYLE style;
1.15 ! otto 94: off_t off;
1.1 deraadt 95: struct stat *sbp;
96: {
97: if (style != REVERSE && off == 0)
98: return;
99:
1.4 millert 100: if (!S_ISREG(sbp->st_mode) || r_reg(fp, style, off, sbp) != 0)
1.1 deraadt 101: switch(style) {
102: case FBYTES:
103: case RBYTES:
1.7 ericj 104: (void)bytes(fp, off);
1.1 deraadt 105: break;
106: case FLINES:
107: case RLINES:
1.7 ericj 108: (void)lines(fp, off);
1.1 deraadt 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: */
1.4 millert 119: static int
1.15 ! otto 120: r_reg(FILE *fp, enum STYLE style, off_t off, struct stat *sbp)
1.1 deraadt 121: {
1.14 henning 122: off_t start, pos, end;
123: int ch;
1.1 deraadt 124:
1.14 henning 125: end = sbp->st_size;
126: if (end == 0)
1.4 millert 127: return (0);
1.1 deraadt 128:
1.14 henning 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)
1.1 deraadt 148: break;
149: }
1.14 henning 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: }
1.4 millert 163: return (0);
1.1 deraadt 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
184: r_buf(fp)
185: FILE *fp;
186: {
1.11 mpech 187: BF *mark, *tr, *tl = NULL;
188: int ch, len, llen;
189: char *p;
1.1 deraadt 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)
1.3 millert 202: err(1, NULL);
1.1 deraadt 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;
1.9 pjanzen 210: } else {
211: mark = tl;
212: mark->next = mark->prev = mark;
213: }
1.5 mickey 214:
215: if (!enomem)
216: tl->len = 0;
1.1 deraadt 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,
1.10 pvalchev 241: "tail: warning: %lld bytes discarded\n", (long long)enomem);
1.1 deraadt 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: }