1 /*-
2 * Copyright (c) 1991, 1993
3 * The Regents of the University of California. All rights reserved.
4 *
5 * This code is derived from software contributed to Berkeley by
6 * Edward Sze-Tyan Wang.
7 *
8 * %sccs.include.redist.c%
9 */
10
11 #ifndef lint
12 static char sccsid[] = "@(#)reverse.c 8.1 (Berkeley) 06/06/93";
13 #endif /* not lint */
14
15 #include <sys/param.h>
16 #include <sys/stat.h>
17 #include <sys/mman.h>
18
19 #include <limits.h>
20 #include <errno.h>
21 #include <unistd.h>
22 #include <stdio.h>
23 #include <stdlib.h>
24 #include <string.h>
25 #include "extern.h"
26
27 static void r_buf __P((FILE *));
28 static void r_reg __P((FILE *, enum STYLE, long, struct stat *));
29
30 /*
31 * reverse -- display input in reverse order by line.
32 *
33 * There are six separate cases for this -- regular and non-regular
34 * files by bytes, lines or the whole file.
35 *
36 * BYTES display N bytes
37 * REG mmap the file and display the lines
38 * NOREG cyclically read characters into a wrap-around buffer
39 *
40 * LINES display N lines
41 * REG mmap the file and display the lines
42 * NOREG cyclically read lines into a wrap-around array of buffers
43 *
44 * FILE display the entire file
45 * REG mmap the file and display the lines
46 * NOREG cyclically read input into a linked list of buffers
47 */
48 void
reverse(fp,style,off,sbp)49 reverse(fp, style, off, sbp)
50 FILE *fp;
51 enum STYLE style;
52 long off;
53 struct stat *sbp;
54 {
55 if (style != REVERSE && off == 0)
56 return;
57
58 if (S_ISREG(sbp->st_mode))
59 r_reg(fp, style, off, sbp);
60 else
61 switch(style) {
62 case FBYTES:
63 case RBYTES:
64 bytes(fp, off);
65 break;
66 case FLINES:
67 case RLINES:
68 lines(fp, off);
69 break;
70 case REVERSE:
71 r_buf(fp);
72 break;
73 }
74 }
75
76 /*
77 * r_reg -- display a regular file in reverse order by line.
78 */
79 static void
r_reg(fp,style,off,sbp)80 r_reg(fp, style, off, sbp)
81 FILE *fp;
82 register enum STYLE style;
83 long off;
84 struct stat *sbp;
85 {
86 register off_t size;
87 register int llen;
88 register char *p;
89 char *start;
90
91 if (!(size = sbp->st_size))
92 return;
93
94 if (size > SIZE_T_MAX) {
95 err(0, "%s: %s", fname, strerror(EFBIG));
96 return;
97 }
98
99 if ((start = mmap(NULL, (size_t)size,
100 PROT_READ, 0, fileno(fp), (off_t)0)) == (caddr_t)-1) {
101 err(0, "%s: %s", fname, strerror(EFBIG));
102 return;
103 }
104 p = start + size - 1;
105
106 if (style == RBYTES && off < size)
107 size = off;
108
109 /* Last char is special, ignore whether newline or not. */
110 for (llen = 1; --size; ++llen)
111 if (*--p == '\n') {
112 WR(p + 1, llen);
113 llen = 0;
114 if (style == RLINES && !--off) {
115 ++p;
116 break;
117 }
118 }
119 if (llen)
120 WR(p, llen);
121 if (munmap(start, (size_t)sbp->st_size))
122 err(0, "%s: %s", fname, strerror(errno));
123 }
124
125 typedef struct bf {
126 struct bf *next;
127 struct bf *prev;
128 int len;
129 char *l;
130 } BF;
131
132 /*
133 * r_buf -- display a non-regular file in reverse order by line.
134 *
135 * This is the function that saves the entire input, storing the data in a
136 * doubly linked list of buffers and then displays them in reverse order.
137 * It has the usual nastiness of trying to find the newlines, as there's no
138 * guarantee that a newline occurs anywhere in the file, let alone in any
139 * particular buffer. If we run out of memory, input is discarded (and the
140 * user warned).
141 */
142 static void
r_buf(fp)143 r_buf(fp)
144 FILE *fp;
145 {
146 register BF *mark, *tl, *tr;
147 register int ch, len, llen;
148 register char *p;
149 off_t enomem;
150
151 #define BSZ (128 * 1024)
152 for (mark = NULL, enomem = 0;;) {
153 /*
154 * Allocate a new block and link it into place in a doubly
155 * linked list. If out of memory, toss the LRU block and
156 * keep going.
157 */
158 if (enomem || (tl = malloc(sizeof(BF))) == NULL ||
159 (tl->l = malloc(BSZ)) == NULL) {
160 if (!mark)
161 err(1, "%s", strerror(errno));
162 tl = enomem ? tl->next : mark;
163 enomem += tl->len;
164 } else if (mark) {
165 tl->next = mark;
166 tl->prev = mark->prev;
167 mark->prev->next = tl;
168 mark->prev = tl;
169 } else
170 mark->next = mark->prev = (mark = tl);
171
172 /* Fill the block with input data. */
173 for (p = tl->l, len = 0;
174 len < BSZ && (ch = getc(fp)) != EOF; ++len)
175 *p++ = ch;
176
177 /*
178 * If no input data for this block and we tossed some data,
179 * recover it.
180 */
181 if (!len) {
182 if (enomem)
183 enomem -= tl->len;
184 tl = tl->prev;
185 break;
186 }
187
188 tl->len = len;
189 if (ch == EOF)
190 break;
191 }
192
193 if (enomem) {
194 (void)fprintf(stderr,
195 "tail: warning: %ld bytes discarded\n", enomem);
196 rval = 1;
197 }
198
199 /*
200 * Step through the blocks in the reverse order read. The last char
201 * is special, ignore whether newline or not.
202 */
203 for (mark = tl;;) {
204 for (p = tl->l + (len = tl->len) - 1, llen = 0; len--;
205 --p, ++llen)
206 if (*p == '\n') {
207 if (llen) {
208 WR(p + 1, llen);
209 llen = 0;
210 }
211 if (tl == mark)
212 continue;
213 for (tr = tl->next; tr->len; tr = tr->next) {
214 WR(tr->l, tr->len);
215 tr->len = 0;
216 if (tr == mark)
217 break;
218 }
219 }
220 tl->len = llen;
221 if ((tl = tl->prev) == mark)
222 break;
223 }
224 tl = tl->next;
225 if (tl->len) {
226 WR(tl->l, tl->len);
227 tl->len = 0;
228 }
229 while ((tl = tl->next)->len) {
230 WR(tl->l, tl->len);
231 tl->len = 0;
232 }
233 }
234