1/*	$NetBSD: ch.c,v 1.5 2003/08/07 09:27:58 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
36static char sccsid[] = "@(#)ch.c	8.1 (Berkeley) 6/6/93";
37#else
38__RCSID("$NetBSD: ch.c,v 1.5 2003/08/07 09:27:58 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
58int 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 */
63struct buf {
64	struct buf *next, *prev;
65	long block;
66	int datasize;
67	char data[BUFSIZ];
68};
69int 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
79static 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 */
87static long ch_block;
88static int ch_offset;
89
90/* Length of file, needed if input is a pipe. */
91static off_t ch_fsize;
92
93/* Number of bytes read, if input is standard input (a pipe). */
94static 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
106static int fch_get __P((void));
107static int buffered __P((long));
108
109static int
110fch_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
154read_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
221found:
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 */
249static int
250buffered(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 */
265int
266ch_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 */
286int
287ch_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 */
306int
307ch_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 */
335off_t
336ch_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 */
346off_t
347ch_tell()
348{
349	return(ch_block * BUFSIZ + ch_offset);
350}
351
352/*
353 * Get the current char and post-increment the read pointer.
354 */
355int
356ch_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 */
371int
372ch_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 */
391void
392ch_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 */
432int
433ch_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