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