[unix-history] / usr / src / usr.bin / more / ch.c

/*
 * Copyright (c) 1988 Mark Nudleman
 * Copyright (c) 1988 Regents of the University of California.
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms are permitted
 * provided that the above copyright notice and this paragraph are
 * duplicated in all such forms and that any documentation,
 * advertising materials, and other materials related to such
 * distribution and use acknowledge that the software was developed
 * by Mark Nudleman and the University of California, Berkeley.  The
 * name of Mark Nudleman or the
 * University may not be used to endorse or promote products derived
 * from this software without specific prior written permission.
 * THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR
 * IMPLIED WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED
 * WARRANTIES OF MERCHANTIBILITY AND FITNESS FOR A PARTICULAR PURPOSE.
 */

#ifndef lint
static char sccsid[] = "@(#)ch.c	5.5 (Berkeley) %G%";
#endif /* not lint */

/*
 * Low level character input from the input file.
 * We use these special purpose routines which optimize moving
 * both forward and backward from the current read pointer.
 */

#include "less.h"

public int file = -1;		/* File descriptor of the input file */

/*
 * Pool of buffers holding the most recently used blocks of the input file.
 */
#define BUFSIZ	1024
struct buf {
	struct buf *next, *prev;
	long block;
	int datasize;
	char data[BUFSIZ];
};
public int nbufs;

/*
 * The buffer pool is kept as a doubly-linked circular list,
 * in order from most- to least-recently used.
 * The circular list is anchored by buf_anchor.
 */
#define	END_OF_CHAIN	((struct buf *)&buf_anchor)
#define	buf_head	buf_anchor.next
#define	buf_tail	buf_anchor.prev

static struct {
	struct buf *next, *prev;
} buf_anchor = { END_OF_CHAIN, END_OF_CHAIN };

extern int clean_data;
extern int ispipe;
extern int autobuf;
extern int cbufs;
extern int sigs;

/*
 * Current position in file.
 * Stored as a block number and an offset into the block.
 */
static long ch_block;
static int ch_offset;

/* 
 * Length of file, needed if input is a pipe.
 */
static POSITION ch_fsize;

/*
 * Number of bytes read, if input is standard input (a pipe).
 */
static POSITION last_piped_pos;

/*
 * Get the character pointed to by the read pointer.
 * ch_get() is a macro which is more efficient to call
 * than fch_get (the function), in the usual case 
 * that the block desired is at the head of the chain.
 */
#define	ch_get()   ((buf_head->block == ch_block && \
		     ch_offset < buf_head->datasize) ? \
			buf_head->data[ch_offset] : fch_get())
	static int
fch_get()
{
	register struct buf *bp;
	register int n;
	register char *p;
	POSITION pos;

	/*
	 * Look for a buffer holding the desired block.
	 */
	for (bp = buf_head;  bp != END_OF_CHAIN;  bp = bp->next)
		if (bp->block == ch_block)
		{
			if (ch_offset >= bp->datasize)
				/*
				 * Need more data in this buffer.
				 */
				goto read_more;
			/*
			 * On a pipe, we don't sort the buffers LRU
			 * because this can cause gaps in the buffers.
			 * For example, suppose we've got 12 1K buffers,
			 * and a 15K input stream.  If we read the first 12K
			 * sequentially, then jump to line 1, then jump to
			 * the end, the buffers have blocks 0,4,5,6,..,14.
			 * If we then jump to line 1 again and try to
			 * read sequentially, we're out of luck when we
			 * get to block 1 (we'd get the "pipe error" below).
			 * To avoid this, we only sort buffers on a pipe
			 * when we actually READ the data, not when we
			 * find it already buffered.
			 */
			if (ispipe)
				return (bp->data[ch_offset]);
			goto found;
		}
	/*
	 * Block is not in a buffer.  
	 * Take the least recently used buffer 
	 * and read the desired block into it.
	 * If the LRU buffer has data in it, 
	 * and autobuf is true, and input is a pipe, 
	 * then try to allocate a new buffer first.
	 */
	if (autobuf && ispipe && buf_tail->block != (long)(-1))
		(void) ch_addbuf(1);
	bp = buf_tail;
	bp->block = ch_block;
	bp->datasize = 0;

    read_more:
	pos = (ch_block * BUFSIZ) + bp->datasize;
	if (ispipe)
	{
		/*
		 * The data requested should be immediately after
		 * the last data read from the pipe.
		 */
		if (pos != last_piped_pos)
		{
			error("pipe error");
			quit();
		}
	} else
		(void)lseek(file, pos, L_SET);

	/*
	 * Read the block.
	 * If we read less than a full block, we just return the
	 * partial block and pick up the rest next time.
	 */
	n = iread(file, &bp->data[bp->datasize], BUFSIZ - bp->datasize);
	if (n == READ_INTR)
		return (EOI);
	if (n < 0)
	{
		error("read error");
		quit();
	}
	if (ispipe)
		last_piped_pos += n;

	bp->datasize += n;

	/*
	 * Set an EOI marker in the buffered data itself.
	 * Then ensure the data is "clean": there are no 
	 * extra EOI chars in the data and that the "meta"
	 * bit (the 0200 bit) is reset in each char.
	 */
	if (n == 0)
	{
		ch_fsize = pos;
		bp->data[bp->datasize++] = EOI;
	}

	if (!clean_data)
	{
		p = &bp->data[bp->datasize];
		while (--n >= 0)
		{
			*--p &= 0177;
			if (*p == EOI)
				*p = '@';
		}
	}

    found:
	if (buf_head != bp)
	{
		/*
		 * Move the buffer to the head of the buffer chain.
		 * This orders the buffer chain, most- to least-recently used.
		 */
		bp->next->prev = bp->prev;
		bp->prev->next = bp->next;

		bp->next = buf_head;
		bp->prev = END_OF_CHAIN;
		buf_head->prev = bp;
		buf_head = bp;
	}

	if (ch_offset >= bp->datasize)
		/*
		 * After all that, we still don't have enough data.
		 * Go back and try again.
		 */
		goto read_more;

	return (bp->data[ch_offset]);
}

/*
 * Determine if a specific block is currently in one of the buffers.
 */
	static int
buffered(block)
	long block;
{
	register struct buf *bp;

	for (bp = buf_head;  bp != END_OF_CHAIN;  bp = bp->next)
		if (bp->block == block)
			return (1);
	return (0);
}

/*
 * Seek to a specified position in the file.
 * Return 0 if successful, non-zero if can't seek there.
 */
	public int
ch_seek(pos)
	register POSITION pos;
{
	long new_block;

	new_block = pos / BUFSIZ;
	if (!ispipe || pos == last_piped_pos || buffered(new_block))
	{
		/*
		 * Set read pointer.
		 */
		ch_block = new_block;
		ch_offset = pos % BUFSIZ;
		return (0);
	}
	return (1);
}

/*
 * Seek to the end of the file.
 */
	public int
ch_end_seek()
{
	if (!ispipe)
		return (ch_seek(ch_length()));

	/*
	 * Do it the slow way: read till end of data.
	 */
	while (ch_forw_get() != EOI)
		if (sigs)
			return (1);
	return (0);
}

/*
 * Seek to the beginning of the file, or as close to it as we can get.
 * We may not be able to seek there if input is a pipe and the
 * beginning of the pipe is no longer buffered.
 */
	public int
ch_beg_seek()
{
	register struct buf *bp, *firstbp;

	/*
	 * Try a plain ch_seek first.
	 */
	if (ch_seek((POSITION)0) == 0)
		return (0);

	/*
	 * Can't get to position 0.
	 * Look thru the buffers for the one closest to position 0.
	 */
	firstbp = bp = buf_head;
	if (bp == END_OF_CHAIN)
		return (1);
	while ((bp = bp->next) != END_OF_CHAIN)
		if (bp->block < firstbp->block)
			firstbp = bp;
	ch_block = firstbp->block;
	ch_offset = 0;
	return (0);
}

/*
 * Return the length of the file, if known.
 */
	public POSITION
ch_length()
{
	if (ispipe)
		return (ch_fsize);
	return ((POSITION)(lseek(file, (off_t)0, L_XTND)));
}

/*
 * Return the current position in the file.
 */
	public POSITION
ch_tell()
{
	return (ch_block * BUFSIZ + ch_offset);
}

/*
 * Get the current char and post-increment the read pointer.
 */
	public int
ch_forw_get()
{
	register int c;

	c = ch_get();
	if (c != EOI && ++ch_offset >= BUFSIZ)
	{
		ch_offset = 0;
		ch_block ++;
	}
	return (c);
}

/*
 * Pre-decrement the read pointer and get the new current char.
 */
	public int
ch_back_get()
{
	if (--ch_offset < 0)
	{
		if (ch_block <= 0 || (ispipe && !buffered(ch_block-1)))
		{
			ch_offset = 0;
			return (EOI);
		}
		ch_offset = BUFSIZ - 1;
		ch_block--;
	}
	return (ch_get());
}

/*
 * Allocate buffers.
 * Caller wants us to have a total of at least want_nbufs buffers.
 * keep==1 means keep the data in the current buffers;
 * otherwise discard the old data.
 */
	public void
ch_init(want_nbufs, keep)
	int want_nbufs;
	int keep;
{
	register struct buf *bp;
	char message[80];

	cbufs = nbufs;
	if (nbufs < want_nbufs && ch_addbuf(want_nbufs - nbufs))
	{
		/*
		 * Cannot allocate enough buffers.
		 * If we don't have ANY, then quit.
		 * Otherwise, just report the error and return.
		 */
		(void)sprintf(message, "cannot allocate %d buffers",
			want_nbufs - nbufs);
		error(message);
		if (nbufs == 0)
			quit();
		return;
	}

	if (keep)
		return;

	/*
	 * We don't want to keep the old data,
	 * so initialize all the buffers now.
	 */
	for (bp = buf_head;  bp != END_OF_CHAIN;  bp = bp->next)
		bp->block = (long)(-1);
	last_piped_pos = (POSITION)0;
	ch_fsize = NULL_POSITION;
	(void) ch_seek((POSITION)0);
}

/*
 * Allocate some new buffers.
 * The buffers are added to the tail of the buffer chain.
 */
	static int
ch_addbuf(nnew)
	int nnew;
{
	register struct buf *bp;
	register struct buf *newbufs;

	/*
	 * We don't have enough buffers.  
	 * Allocate some new ones.
	 */
	newbufs = (struct buf *) calloc((u_int)nnew, sizeof(struct buf));
	if (newbufs == NULL)
		return (1);

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