1 /*
2 * Copyright (c) 1988 Mark Nudleman
3 * Copyright (c) 1988, 1993
4 * The Regents of the University of California. All rights reserved.
5 *
6 * %sccs.include.redist.c%
7 */
8
9 #ifndef lint
10 static char sccsid[] = "@(#)ch.c 8.1 (Berkeley) 06/06/93";
11 #endif /* not lint */
12
13 /*
14 * Low level character input from the input file.
15 * We use these special purpose routines which optimize moving
16 * both forward and backward from the current read pointer.
17 */
18
19 #include <sys/types.h>
20 #include <sys/file.h>
21 #include <unistd.h>
22 #include <stdio.h>
23 #include <less.h>
24
25 int file = -1; /* File descriptor of the input file */
26
27 /*
28 * Pool of buffers holding the most recently used blocks of the input file.
29 */
30 struct buf {
31 struct buf *next, *prev;
32 long block;
33 int datasize;
34 char data[BUFSIZ];
35 };
36 int nbufs;
37
38 /*
39 * The buffer pool is kept as a doubly-linked circular list, in order from
40 * most- to least-recently used. The circular list is anchored by buf_anchor.
41 */
42 #define END_OF_CHAIN ((struct buf *)&buf_anchor)
43 #define buf_head buf_anchor.next
44 #define buf_tail buf_anchor.prev
45
46 static struct {
47 struct buf *next, *prev;
48 } buf_anchor = { END_OF_CHAIN, END_OF_CHAIN };
49
50 extern int ispipe, cbufs, sigs;
51
52 /*
53 * Current position in file.
54 * Stored as a block number and an offset into the block.
55 */
56 static long ch_block;
57 static int ch_offset;
58
59 /* Length of file, needed if input is a pipe. */
60 static off_t ch_fsize;
61
62 /* Number of bytes read, if input is standard input (a pipe). */
63 static off_t last_piped_pos;
64
65 /*
66 * Get the character pointed to by the read pointer. ch_get() is a macro
67 * which is more efficient to call than fch_get (the function), in the usual
68 * case that the block desired is at the head of the chain.
69 */
70 #define ch_get() \
71 ((buf_head->block == ch_block && \
72 ch_offset < buf_head->datasize) ? \
73 buf_head->data[ch_offset] : fch_get())
74
75 static
fch_get()76 fch_get()
77 {
78 extern int bs_mode;
79 register struct buf *bp;
80 register int n, ch;
81 register char *p, *t;
82 off_t pos, lseek();
83
84 /* look for a buffer holding the desired block. */
85 for (bp = buf_head; bp != END_OF_CHAIN; bp = bp->next)
86 if (bp->block == ch_block) {
87 if (ch_offset >= bp->datasize)
88 /*
89 * Need more data in this buffer.
90 */
91 goto read_more;
92 /*
93 * On a pipe, we don't sort the buffers LRU
94 * because this can cause gaps in the buffers.
95 * For example, suppose we've got 12 1K buffers,
96 * and a 15K input stream. If we read the first 12K
97 * sequentially, then jump to line 1, then jump to
98 * the end, the buffers have blocks 0,4,5,6,..,14.
99 * If we then jump to line 1 again and try to
100 * read sequentially, we're out of luck when we
101 * get to block 1 (we'd get the "pipe error" below).
102 * To avoid this, we only sort buffers on a pipe
103 * when we actually READ the data, not when we
104 * find it already buffered.
105 */
106 if (ispipe)
107 return(bp->data[ch_offset]);
108 goto found;
109 }
110 /*
111 * Block is not in a buffer. Take the least recently used buffer
112 * and read the desired block into it. If the LRU buffer has data
113 * in it, and input is a pipe, then try to allocate a new buffer first.
114 */
115 if (ispipe && buf_tail->block != (long)(-1))
116 (void)ch_addbuf(1);
117 bp = buf_tail;
118 bp->block = ch_block;
119 bp->datasize = 0;
120
121 read_more:
122 pos = (ch_block * BUFSIZ) + bp->datasize;
123 if (ispipe) {
124 /*
125 * The data requested should be immediately after
126 * the last data read from the pipe.
127 */
128 if (pos != last_piped_pos) {
129 error("pipe error");
130 quit();
131 }
132 } else
133 (void)lseek(file, pos, L_SET);
134
135 /*
136 * Read the block.
137 * If we read less than a full block, we just return the
138 * partial block and pick up the rest next time.
139 */
140 n = iread(file, &bp->data[bp->datasize], BUFSIZ - bp->datasize);
141 if (n == READ_INTR)
142 return (EOI);
143 if (n < 0) {
144 error("read error");
145 quit();
146 }
147 if (ispipe)
148 last_piped_pos += n;
149
150 p = &bp->data[bp->datasize];
151 bp->datasize += n;
152
153 /*
154 * Set an EOI marker in the buffered data itself. Then ensure the
155 * data is "clean": there are no extra EOI chars in the data and
156 * that the "meta" bit (the 0200 bit) is reset in each char;
157 * also translate \r\n sequences to \n if -u flag not set.
158 */
159 if (n == 0) {
160 ch_fsize = pos;
161 bp->data[bp->datasize++] = EOI;
162 }
163
164 if (bs_mode) {
165 for (p = &bp->data[bp->datasize]; --n >= 0;) {
166 *--p &= 0177;
167 if (*p == EOI)
168 *p = 0200;
169 }
170 }
171 else {
172 for (t = p; --n >= 0; ++p) {
173 ch = *p & 0177;
174 if (ch == '\r' && n && (p[1] & 0177) == '\n') {
175 ++p;
176 *t++ = '\n';
177 }
178 else
179 *t++ = (ch == EOI) ? 0200 : ch;
180 }
181 if (p != t) {
182 bp->datasize -= p - t;
183 if (ispipe)
184 last_piped_pos -= p - t;
185 }
186 }
187
188 found:
189 if (buf_head != bp) {
190 /*
191 * Move the buffer to the head of the buffer chain.
192 * This orders the buffer chain, most- to least-recently used.
193 */
194 bp->next->prev = bp->prev;
195 bp->prev->next = bp->next;
196
197 bp->next = buf_head;
198 bp->prev = END_OF_CHAIN;
199 buf_head->prev = bp;
200 buf_head = bp;
201 }
202
203 if (ch_offset >= bp->datasize)
204 /*
205 * After all that, we still don't have enough data.
206 * Go back and try again.
207 */
208 goto read_more;
209
210 return(bp->data[ch_offset]);
211 }
212
213 /*
214 * Determine if a specific block is currently in one of the buffers.
215 */
216 static
buffered(block)217 buffered(block)
218 long block;
219 {
220 register struct buf *bp;
221
222 for (bp = buf_head; bp != END_OF_CHAIN; bp = bp->next)
223 if (bp->block == block)
224 return(1);
225 return(0);
226 }
227
228 /*
229 * Seek to a specified position in the file.
230 * Return 0 if successful, non-zero if can't seek there.
231 */
ch_seek(pos)232 ch_seek(pos)
233 register off_t pos;
234 {
235 long new_block;
236
237 new_block = pos / BUFSIZ;
238 if (!ispipe || pos == last_piped_pos || buffered(new_block)) {
239 /*
240 * Set read pointer.
241 */
242 ch_block = new_block;
243 ch_offset = pos % BUFSIZ;
244 return(0);
245 }
246 return(1);
247 }
248
249 /*
250 * Seek to the end of the file.
251 */
ch_end_seek()252 ch_end_seek()
253 {
254 off_t ch_length();
255
256 if (!ispipe)
257 return(ch_seek(ch_length()));
258
259 /*
260 * Do it the slow way: read till end of data.
261 */
262 while (ch_forw_get() != EOI)
263 if (sigs)
264 return(1);
265 return(0);
266 }
267
268 /*
269 * Seek to the beginning of the file, or as close to it as we can get.
270 * We may not be able to seek there if input is a pipe and the
271 * beginning of the pipe is no longer buffered.
272 */
ch_beg_seek()273 ch_beg_seek()
274 {
275 register struct buf *bp, *firstbp;
276
277 /*
278 * Try a plain ch_seek first.
279 */
280 if (ch_seek((off_t)0) == 0)
281 return(0);
282
283 /*
284 * Can't get to position 0.
285 * Look thru the buffers for the one closest to position 0.
286 */
287 firstbp = bp = buf_head;
288 if (bp == END_OF_CHAIN)
289 return(1);
290 while ((bp = bp->next) != END_OF_CHAIN)
291 if (bp->block < firstbp->block)
292 firstbp = bp;
293 ch_block = firstbp->block;
294 ch_offset = 0;
295 return(0);
296 }
297
298 /*
299 * Return the length of the file, if known.
300 */
301 off_t
ch_length()302 ch_length()
303 {
304 off_t lseek();
305
306 if (ispipe)
307 return(ch_fsize);
308 return((off_t)(lseek(file, (off_t)0, L_XTND)));
309 }
310
311 /*
312 * Return the current position in the file.
313 */
314 off_t
ch_tell()315 ch_tell()
316 {
317 return(ch_block * BUFSIZ + ch_offset);
318 }
319
320 /*
321 * Get the current char and post-increment the read pointer.
322 */
ch_forw_get()323 ch_forw_get()
324 {
325 register int c;
326
327 c = ch_get();
328 if (c != EOI && ++ch_offset >= BUFSIZ) {
329 ch_offset = 0;
330 ++ch_block;
331 }
332 return(c);
333 }
334
335 /*
336 * Pre-decrement the read pointer and get the new current char.
337 */
ch_back_get()338 ch_back_get()
339 {
340 if (--ch_offset < 0) {
341 if (ch_block <= 0 || (ispipe && !buffered(ch_block-1))) {
342 ch_offset = 0;
343 return(EOI);
344 }
345 ch_offset = BUFSIZ - 1;
346 ch_block--;
347 }
348 return(ch_get());
349 }
350
351 /*
352 * Allocate buffers.
353 * Caller wants us to have a total of at least want_nbufs buffers.
354 * keep==1 means keep the data in the current buffers;
355 * otherwise discard the old data.
356 */
ch_init(want_nbufs,keep)357 ch_init(want_nbufs, keep)
358 int want_nbufs;
359 int keep;
360 {
361 register struct buf *bp;
362 char message[80];
363
364 cbufs = nbufs;
365 if (nbufs < want_nbufs && ch_addbuf(want_nbufs - nbufs)) {
366 /*
367 * Cannot allocate enough buffers.
368 * If we don't have ANY, then quit.
369 * Otherwise, just report the error and return.
370 */
371 (void)sprintf(message, "cannot allocate %d buffers",
372 want_nbufs - nbufs);
373 error(message);
374 if (nbufs == 0)
375 quit();
376 return;
377 }
378
379 if (keep)
380 return;
381
382 /*
383 * We don't want to keep the old data,
384 * so initialize all the buffers now.
385 */
386 for (bp = buf_head; bp != END_OF_CHAIN; bp = bp->next)
387 bp->block = (long)(-1);
388 last_piped_pos = (off_t)0;
389 ch_fsize = NULL_POSITION;
390 (void)ch_seek((off_t)0);
391 }
392
393 /*
394 * Allocate some new buffers.
395 * The buffers are added to the tail of the buffer chain.
396 */
ch_addbuf(nnew)397 ch_addbuf(nnew)
398 int nnew;
399 {
400 register struct buf *bp;
401 register struct buf *newbufs;
402 char *calloc();
403
404 /*
405 * We don't have enough buffers.
406 * Allocate some new ones.
407 */
408 newbufs = (struct buf *)calloc((u_int)nnew, sizeof(struct buf));
409 if (newbufs == NULL)
410 return(1);
411
412 /*
413 * Initialize the new buffers and link them together.
414 * Link them all onto the tail of the buffer list.
415 */
416 nbufs += nnew;
417 cbufs = nbufs;
418 for (bp = &newbufs[0]; bp < &newbufs[nnew]; bp++) {
419 bp->next = bp + 1;
420 bp->prev = bp - 1;
421 bp->block = (long)(-1);
422 }
423 newbufs[nnew-1].next = END_OF_CHAIN;
424 newbufs[0].prev = buf_tail;
425 buf_tail->next = &newbufs[0];
426 buf_tail = &newbufs[nnew-1];
427 return(0);
428 }
429