Annotation of src/usr.bin/tail/reverse.c, Revision 1.18
1.18 ! otto 1: /* $OpenBSD: reverse.c,v 1.17 2006/03/24 17:10:02 kjell 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.18 ! otto 40: static char rcsid[] = "$OpenBSD: reverse.c,v 1.17 2006/03/24 17:10:02 kjell Exp $";
1.1 deraadt 41: #endif /* not lint */
42:
43: #include <sys/stat.h>
44:
1.3 millert 45: #include <err.h>
1.1 deraadt 46: #include <stdio.h>
47: #include <stdlib.h>
1.3 millert 48: #include <unistd.h>
49:
1.1 deraadt 50: #include "extern.h"
51:
1.12 millert 52: static void r_buf(FILE *);
1.15 otto 53: static int r_reg(FILE *, enum STYLE, off_t, struct stat *);
1.1 deraadt 54:
1.14 henning 55: #define COPYCHAR(fp, ch) \
56: do { \
57: if ((ch = getc(fp)) == EOF) { \
58: ierr(); \
59: return (0); \
60: } \
61: if (putchar(ch) == EOF) { \
62: oerr(); \
63: return (0); \
64: } \
65: } while (0)
66:
1.1 deraadt 67: /*
68: * reverse -- display input in reverse order by line.
69: *
70: * There are six separate cases for this -- regular and non-regular
71: * files by bytes, lines or the whole file.
72: *
73: * BYTES display N bytes
1.14 henning 74: * REG reverse scan and display the lines
1.1 deraadt 75: * NOREG cyclically read characters into a wrap-around buffer
76: *
77: * LINES display N lines
1.14 henning 78: * REG reverse scan and display the lines
1.1 deraadt 79: * NOREG cyclically read lines into a wrap-around array of buffers
80: *
81: * FILE display the entire file
1.14 henning 82: * REG reverse scan and display the lines
1.1 deraadt 83: * NOREG cyclically read input into a linked list of buffers
84: */
85: void
1.17 kjell 86: reverse(FILE *fp, enum STYLE style, off_t off, struct stat *sbp)
1.1 deraadt 87: {
88: if (style != REVERSE && off == 0)
89: return;
90:
1.4 millert 91: if (!S_ISREG(sbp->st_mode) || r_reg(fp, style, off, sbp) != 0)
1.1 deraadt 92: switch(style) {
93: case FBYTES:
94: case RBYTES:
1.7 ericj 95: (void)bytes(fp, off);
1.1 deraadt 96: break;
97: case FLINES:
98: case RLINES:
1.7 ericj 99: (void)lines(fp, off);
1.1 deraadt 100: break;
101: case REVERSE:
102: r_buf(fp);
103: break;
104: }
105: }
106:
107: /*
108: * r_reg -- display a regular file in reverse order by line.
109: */
1.4 millert 110: static int
1.15 otto 111: r_reg(FILE *fp, enum STYLE style, off_t off, struct stat *sbp)
1.1 deraadt 112: {
1.14 henning 113: off_t start, pos, end;
114: int ch;
1.1 deraadt 115:
1.14 henning 116: end = sbp->st_size;
117: if (end == 0)
1.4 millert 118: return (0);
1.1 deraadt 119:
1.14 henning 120: /* Position before char, ignore last char whether newline or not */
121: pos = end-2;
122: ch = EOF;
123: start = 0;
124:
125: if (style == RBYTES && off < end)
126: start = end - off;
127:
128: for (; pos >= start; pos--) {
129: /* A seek per char isn't a problem with a smart stdio */
130: if (fseeko(fp, pos, SEEK_SET) != 0) {
131: ierr();
132: return (0);
133: }
134: if ((ch = getc(fp)) == '\n') {
135: while (--end > pos)
136: COPYCHAR(fp, ch);
137: end++;
138: if (style == RLINES && --off == 0)
1.1 deraadt 139: break;
140: }
1.14 henning 141: else if (ch == EOF) {
142: ierr();
143: return (0);
144: }
145: }
146: if (pos < start) {
147: if (ch != EOF && ungetc(ch, fp) == EOF) {
148: ierr();
149: return (0);
150: }
151: while (--end >= start)
152: COPYCHAR(fp, ch);
153: }
1.4 millert 154: return (0);
1.1 deraadt 155: }
156:
157: typedef struct bf {
158: struct bf *next;
159: struct bf *prev;
1.16 kjell 160: size_t len;
1.1 deraadt 161: char *l;
162: } BF;
163:
164: /*
165: * r_buf -- display a non-regular file in reverse order by line.
166: *
167: * This is the function that saves the entire input, storing the data in a
168: * doubly linked list of buffers and then displays them in reverse order.
169: * It has the usual nastiness of trying to find the newlines, as there's no
170: * guarantee that a newline occurs anywhere in the file, let alone in any
171: * particular buffer. If we run out of memory, input is discarded (and the
172: * user warned).
173: */
174: static void
1.17 kjell 175: r_buf(FILE *fp)
1.1 deraadt 176: {
1.11 mpech 177: BF *mark, *tr, *tl = NULL;
1.16 kjell 178: int ch;
179: size_t len, llen;
1.11 mpech 180: char *p;
1.1 deraadt 181: off_t enomem;
182:
183: #define BSZ (128 * 1024)
184: for (mark = NULL, enomem = 0;;) {
185: /*
186: * Allocate a new block and link it into place in a doubly
187: * linked list. If out of memory, toss the LRU block and
188: * keep going.
189: */
190: if (enomem || (tl = malloc(sizeof(BF))) == NULL ||
191: (tl->l = malloc(BSZ)) == NULL) {
192: if (!mark)
1.3 millert 193: err(1, NULL);
1.1 deraadt 194: tl = enomem ? tl->next : mark;
195: enomem += tl->len;
196: } else if (mark) {
197: tl->next = mark;
198: tl->prev = mark->prev;
199: mark->prev->next = tl;
200: mark->prev = tl;
1.9 pjanzen 201: } else {
202: mark = tl;
203: mark->next = mark->prev = mark;
204: }
1.5 mickey 205:
206: if (!enomem)
207: tl->len = 0;
1.1 deraadt 208:
209: /* Fill the block with input data. */
210: for (p = tl->l, len = 0;
211: len < BSZ && (ch = getc(fp)) != EOF; ++len)
212: *p++ = ch;
213:
214: /*
215: * If no input data for this block and we tossed some data,
216: * recover it.
217: */
218: if (!len) {
219: if (enomem)
220: enomem -= tl->len;
221: tl = tl->prev;
222: break;
223: }
224:
225: tl->len = len;
226: if (ch == EOF)
227: break;
228: }
229:
230: if (enomem) {
231: (void)fprintf(stderr,
1.10 pvalchev 232: "tail: warning: %lld bytes discarded\n", (long long)enomem);
1.1 deraadt 233: rval = 1;
234: }
235:
236: /*
237: * Step through the blocks in the reverse order read. The last char
238: * is special, ignore whether newline or not.
239: */
240: for (mark = tl;;) {
241: for (p = tl->l + (len = tl->len) - 1, llen = 0; len--;
242: --p, ++llen)
243: if (*p == '\n') {
244: if (llen) {
245: WR(p + 1, llen);
246: llen = 0;
247: }
248: if (tl == mark)
249: continue;
250: for (tr = tl->next; tr->len; tr = tr->next) {
251: WR(tr->l, tr->len);
252: tr->len = 0;
253: if (tr == mark)
254: break;
255: }
256: }
257: tl->len = llen;
258: if ((tl = tl->prev) == mark)
259: break;
260: }
261: tl = tl->next;
262: if (tl->len) {
263: WR(tl->l, tl->len);
264: tl->len = 0;
265: }
266: while ((tl = tl->next)->len) {
267: WR(tl->l, tl->len);
268: tl->len = 0;
269: }
270: }