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 * Redistribution and use in source and binary forms, with or without
7 * modification, are permitted provided that the following conditions
8 * are met:
9 * 1. Redistributions of source code must retain the above copyright
10 * notice, this list of conditions and the following disclaimer.
11 * 2. Redistributions in binary form must reproduce the above copyright
12 * notice, this list of conditions and the following disclaimer in the
13 * documentation and/or other materials provided with the distribution.
14 * 3. All advertising materials mentioning features or use of this software
15 * must display the following acknowledgement:
16 * This product includes software developed by the University of
17 * California, Berkeley and its contributors.
18 * 4. Neither the name of the University nor the names of its contributors
19 * may be used to endorse or promote products derived from this software
20 * without specific prior written permission.
21 *
22 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
23 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
24 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
25 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
26 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
27 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
28 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
29 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
30 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
31 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
32 * SUCH DAMAGE.
33 */
34
35 #ifndef lint
36 static char sccsid[] = "@(#)ch.c 8.1 (Berkeley) 6/6/93";
37 #endif /* not lint */
38
39 #ifndef lint
40 static const char rcsid[] =
41 "$FreeBSD$";
42 #endif /* not lint */
43
44 /*
45 * Low level character input from the input file.
46 * We use these special purpose routines which optimize moving
47 * both forward and backward from the current read pointer.
48 */
49
50 #include <sys/types.h>
51 #include <stdlib.h>
52 #include <sys/file.h>
53 #include <unistd.h>
54 #include <stdio.h>
55 #include <less.h>
56
57 int file = -1; /* File descriptor of the input file */
58
59 /*
60 * Pool of buffers holding the most recently used blocks of the input file.
61 */
62 struct buf {
63 struct buf *next, *prev;
64 long block;
65 int datasize;
66 char data[BUFSIZ];
67 };
68 int nbufs;
69
70 /*
71 * The buffer pool is kept as a doubly-linked circular list. For the ispipe
72 * case, this list will always be ordered from highest-numbered block downto
73 * lowest-numbered block, skipping no blocks. For the !ispipe case,
74 * it may become disordered. It is not clear that this is a feature.
75 */
76 #define END_OF_CHAIN ((struct buf *)&buf_anchor)
77 #define buf_head buf_anchor.next
78 #define buf_tail buf_anchor.prev
79
80 static struct {
81 struct buf *next, *prev;
82 long block; /* this is never changed from -1 */
83 } buf_anchor = { END_OF_CHAIN, END_OF_CHAIN, (long)-1 };
84
85 /*
86 * The last buffer in the circular list that was accessed, and correspondingly
87 * the most likely to be accessed in the future.
88 */
89 static struct buf *buf_lastacc = END_OF_CHAIN;
90
91 extern int ispipe, cbufs, sigs;
92
93 /*
94 * Current position in file.
95 * Stored as a block number and an offset into the block.
96 */
97 static long ch_block;
98 static int ch_offset;
99
100 /* Length of file, needed if input is a pipe. */
101 static off_t ch_fsize;
102
103 /* Number of bytes read, if input is standard input (a pipe). */
104 static off_t last_piped_pos;
105
106 /*
107 * Get the character pointed to by the read pointer. ch_get() is a macro
108 * which is more efficient to call than fch_get (the function), in the usual
109 * case that the block desired is at the head of the chain.
110 */
111 #define ch_get() \
112 ((buf_lastacc->block == ch_block && \
113 ch_offset < buf_lastacc->datasize) ? \
114 (unsigned char)buf_lastacc->data[ch_offset] : fch_get())
115
116 static
fch_get()117 fch_get()
118 {
119 register struct buf *bp;
120 register char *p, *t;
121 int n, gofor;
122 off_t pos, lseek();
123
124 /*
125 * look for a buffer holding the desired block.
126 */
127 if (abs(buf_lastacc->next->block - ch_block) <
128 abs(buf_lastacc->prev->block - ch_block))
129 gofor = 1; /* Look forwards through the buffer queue */
130 else
131 gofor = 0; /* Look backwards through the buffer queue */
132
133 bp = buf_lastacc;
134 do {
135 if (bp->block == ch_block) {
136 buf_lastacc = bp;
137 if (ch_offset >= bp->datasize)
138 goto read_more;
139 return((unsigned char)bp->data[ch_offset]);
140 }
141 if (gofor)
142 bp = bp->next;
143 else
144 bp = bp->prev;
145 } while (bp != buf_lastacc);
146
147 /*
148 * Block is not in a buffer. Take the buffer from the tail and
149 * read the desired block into it. If the input is a pipe, we try
150 * to buffer as much input as possible since the input will be
151 * permanently lost if we throw it from the buffer queue.
152 */
153 if (ispipe && buf_tail->block != (long)(-1))
154 (void)ch_addbuf(1);
155 bp = buf_tail;
156 bp->block = ch_block;
157 bp->datasize = 0;
158
159 read_more:
160 pos = (ch_block * BUFSIZ) + bp->datasize;
161 if (ispipe) {
162 /*
163 * The data requested should be immediately after
164 * the last data read from the pipe.
165 */
166 if (pos != last_piped_pos) {
167 error("pipe error");
168 quit();
169 }
170 } else
171 (void)lseek(file, pos, L_SET);
172
173 /*
174 * Read the block.
175 *
176 * If we read less than a full block, we just return the
177 * partial block and pick up the rest next time.
178 */
179 n = iread(file, &bp->data[bp->datasize], BUFSIZ - bp->datasize);
180 if (n == READ_INTR)
181 return (EOI);
182 if (n < 0) {
183 error("read error");
184 quit();
185 }
186 if (ispipe)
187 last_piped_pos += n;
188
189 bp->datasize += n;
190
191 if (n == 0) {
192 ch_fsize = pos;
193 bp->data[bp->datasize++] = EOI;
194 }
195
196 /*
197 * Turn other EOI (nul) chars into 0200 since EOI has special meaning.
198 */
199 for (p = &bp->data[bp->datasize]; --n >= 0;) {
200 --p;
201 if (*p == EOI)
202 *p = 0200;
203 }
204
205 found:
206 if (buf_head != bp) {
207 /*
208 * Move the buffer to the head of the buffer chain. This
209 * ensures correct order for the ispipe case and prevents
210 * needless buffer thrashing for the !ispipe case. It's not
211 * clear that buffer thrashing isn't desirable in this latter
212 * case, since the VM should probably be handling the file
213 * buffer...
214 */
215 bp->next->prev = bp->prev;
216 bp->prev->next = bp->next;
217
218 bp->next = buf_head;
219 bp->prev = END_OF_CHAIN;
220 buf_head->prev = bp;
221 buf_head = bp;
222 }
223
224 if (ch_offset >= bp->datasize)
225 /*
226 * After all that, we still don't have enough data.
227 * Go back and try again.
228 */
229 goto read_more;
230
231 return((unsigned char)bp->data[ch_offset]);
232 }
233
234 /*
235 * Determine if a specific block is currently in one of the buffers.
236 *
237 * In general, this function is only called for the ispipe case. For the
238 * !ispipe case, ch.c generally assumes that any given block is accessible
239 * through ch_get(), even though ch_get() may not have it buffered.
240 */
241 static
buffered(block)242 buffered(block)
243 long block;
244 {
245 register struct buf *bp;
246
247 /* For the ispipe case, we know that the buffer queue is sequentially
248 * ordered from tail to head. */
249 if (ispipe && (block <= buf_head->block && block >= buf_tail->block))
250 return(1);
251
252 /*
253 * XXX This is dead code.
254 */
255 for (bp = buf_head; bp != END_OF_CHAIN; bp = bp->next)
256 if (bp->block == block)
257 return(1);
258 return(0);
259 }
260
261 /*
262 * Seek to a specified position in the file.
263 * Return 0 if successful, non-zero if can't seek there.
264 */
ch_seek(pos)265 ch_seek(pos)
266 register off_t pos;
267 {
268 long new_block;
269
270 new_block = pos / BUFSIZ;
271 if (!ispipe || pos == last_piped_pos || buffered(new_block)) {
272 /*
273 * Set read pointer.
274 */
275 ch_block = new_block;
276 ch_offset = pos % BUFSIZ;
277 return(0);
278 }
279 return(1);
280 }
281
282 /*
283 * Seek to the end of the file.
284 */
ch_end_seek()285 ch_end_seek()
286 {
287 off_t ch_length();
288
289 if (!ispipe)
290 return(ch_seek(ch_length()));
291
292 /*
293 * Do it the slow way: read till end of data.
294 */
295 while (ch_forw_get() != EOI)
296 if (sigs)
297 return(1);
298 return(0);
299 }
300
301 /*
302 * Seek to the beginning of the file, or as close to it as we can get.
303 * We may not be able to seek there if input is a pipe and the
304 * beginning of the pipe is no longer buffered.
305 */
ch_beg_seek()306 ch_beg_seek()
307 {
308 register struct buf *bp, *firstbp;
309
310 /*
311 * Try a plain ch_seek first.
312 */
313 if (ch_seek((off_t)0) == 0)
314 return(0);
315
316 /*
317 * Can't get to position 0.
318 * Look thru the buffers for the one closest to position 0.
319 *
320 * This should use the obvious optimization that applies for the
321 * ispipe case (which is also the only case under which this
322 * code will be executed, ie. the only case under which ch_seek()
323 * will fail).
324 */
325 firstbp = bp = buf_head;
326 if (bp == END_OF_CHAIN)
327 return(1);
328 while ((bp = bp->next) != END_OF_CHAIN)
329 if (bp->block < firstbp->block)
330 firstbp = bp;
331 ch_block = firstbp->block;
332 ch_offset = 0;
333 return(0);
334 }
335
336 /*
337 * Return the length of the file, if known.
338 */
339 off_t
ch_length()340 ch_length()
341 {
342 off_t lseek();
343
344 if (ispipe)
345 return(ch_fsize);
346 return((off_t)(lseek(file, (off_t)0, L_XTND)));
347 }
348
349 /*
350 * Return the current position in the file.
351 */
352 off_t
ch_tell()353 ch_tell()
354 {
355 return(ch_block * BUFSIZ + ch_offset);
356 }
357
358 /*
359 * Get the current char and post-increment the read pointer.
360 */
ch_forw_get()361 ch_forw_get()
362 {
363 register int c;
364
365 c = ch_get();
366 if (c != EOI && ++ch_offset >= BUFSIZ) {
367 ch_offset = 0;
368 ++ch_block;
369 }
370 return(c);
371 }
372
373 /*
374 * Pre-decrement the read pointer and get the new current char.
375 */
ch_back_get()376 ch_back_get()
377 {
378 if (--ch_offset < 0) {
379 if (ch_block <= 0 || (ispipe && !buffered(ch_block-1))) {
380 ch_offset = 0;
381 return(EOI);
382 }
383 ch_offset = BUFSIZ - 1;
384 ch_block--;
385 }
386 return(ch_get());
387 }
388
389 /*
390 * Allocate buffers.
391 * Caller wants us to have a total of at least want_nbufs buffers.
392 * keep==1 means keep the data in the current buffers;
393 * otherwise discard the old data.
394 */
395 void
ch_init(want_nbufs,keep)396 ch_init(want_nbufs, keep)
397 int want_nbufs;
398 int keep;
399 {
400 register struct buf *bp;
401 char message[80];
402
403 cbufs = nbufs;
404 if (nbufs < want_nbufs && ch_addbuf(want_nbufs - nbufs)) {
405 /*
406 * Cannot allocate enough buffers.
407 * If we don't have ANY, then quit.
408 * Otherwise, just report the error and return.
409 */
410 (void)snprintf(message, sizeof(message),
411 "cannot allocate %d buffers", want_nbufs - nbufs);
412 error(message);
413 if (nbufs == 0)
414 quit();
415 return;
416 }
417
418 if (keep)
419 return;
420
421 /*
422 * We don't want to keep the old data,
423 * so initialize all the buffers now.
424 */
425 for (bp = buf_head; bp != END_OF_CHAIN; bp = bp->next)
426 bp->block = (long)(-1);
427 last_piped_pos = (off_t)0;
428 ch_fsize = NULL_POSITION;
429 (void)ch_seek((off_t)0);
430 }
431
432 /*
433 * Allocate some new buffers.
434 * The buffers are added to the tail of the buffer chain.
435 */
ch_addbuf(nnew)436 ch_addbuf(nnew)
437 int nnew;
438 {
439 register struct buf *bp;
440 register struct buf *newbufs;
441 // char *calloc();
442
443 /*
444 * We don't have enough buffers.
445 * Allocate some new ones.
446 */
447 newbufs = (struct buf *)calloc((u_int)nnew, sizeof(struct buf));
448 if (newbufs == NULL)
449 return(1);
450
451 /*
452 * Initialize the new buffers and link them together.
453 * Link them all onto the tail of the buffer list.
454 */
455 nbufs += nnew;
456 cbufs = nbufs;
457 for (bp = &newbufs[0]; bp < &newbufs[nnew]; bp++) {
458 bp->next = bp + 1;
459 bp->prev = bp - 1;
460 bp->block = (long)(-1);
461 }
462 newbufs[nnew-1].next = END_OF_CHAIN;
463 newbufs[0].prev = buf_tail;
464 buf_tail->next = &newbufs[0];
465 buf_tail = &newbufs[nnew-1];
466 return(0);
467 }
468