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