getline.c

minix软件源代码

/* Copyright (c) 1985 Ceriel J.H. Jacobs */

# ifndef lint
static char rcsid[] = "$Header: getline.c,v 7.7 89/12/15 11:43:43 ceriel Exp $";
# endif

# define _GETLINE_

# include <errno.h>
# include "in_all.h"
# include "getline.h"
# include "options.h"
# include "process.h"
# include "term.h"
# include "main.h"
# include "display.h"
# include "output.h"
# include "assert.h"

extern int errno;

# define BLOCKSIZE 2048		/* size of blocks */
# define CHUNK 50		/* # of blockheaders allocated at a time */

/*
 * The blockheaders of the blocks that are in core are kept in a linked list.
 * The last added block is indicated by b_head,
 * the tail of the list is indicated by b_tail.
 * The links go from b_tail to b_head.
 * The blockheaders are all in an array, in the order of the line numbers.
 * Also, the blockheaders must always be in core, so they have to be rather
 * small. On systems with a small address space, yap can run out of core,
 * and panic. However, this should only happen with very large files (>> 1M).
 */

struct block {
	int		b_flags;	/* Contains the following flags: */
# define DUMPED		01		/* block dumped on temporary file */
# define PARTLY		02		/* block not filled completely (eof) */
	int		b_next;		/* ptr in linked list */
	long		b_end;		/* line number of last line in block */
	char	 *	b_info;		/* the block */
	int      *	b_offs;		/* line offsets within the block */
	long		b_foff;		/* offset of block in file */
};

static struct block *	blocklist,	/* beginning of the list of blocks */
		    *	maxblocklist,	/* first free entry in the list */
		    *	topblocklist;	/* end of allocated core for the list */
static int	b_head,
		b_tail;
static int	tfdes, ifdes;		/* File descriptors for temporary's */
static long	lastreadline;		/* lineno of last line read */
static int	ENDseen;

STATIC VOID readblock();
STATIC VOID nextblock();
STATIC char *re_alloc();

STATIC struct block *
new_block()
{
	register struct block *pblock = maxblocklist - 1;

	if (!maxblocklist || !(pblock->b_flags & PARTLY)) {
		/*
		 * There is no last block, or it was filled completely,
		 * so allocate a new blockheader.
		 */
		register int siz;

		pblock = blocklist;
		if (maxblocklist == topblocklist) {
			/*
			 * No blockheaders left. Allocate new ones
			 */
			siz = topblocklist - pblock;
			blocklist = pblock = (struct block *)
			re_alloc((char *) pblock,
			(unsigned) (siz * sizeof(*pblock)),
			(unsigned) ((siz + CHUNK) * sizeof(*pblock)));
			pblock += siz;
			topblocklist = pblock + CHUNK;
			maxblocklist = pblock;
			for (; pblock < topblocklist; pblock++) {
				pblock->b_end = 0;
				pblock->b_info = 0;
				pblock->b_flags = 0;
			}
			if (!siz) {
				/*
				 * Create dummy header cell.
				 */
				maxblocklist++;
			}
		}
		pblock = maxblocklist++;
	}
	nextblock(pblock);
	return pblock;
}

/*
 * Return the block in which line 'n' of the current file can be found.
 * If "disable_interrupt" = 0, the call may be interrupted, in which
 * case it returns 0.
 */

STATIC struct block *
getblock(n, disable_interrupt) register long n; {
	register struct block * pblock;

	if (stdf < 0) {
		/*
		 * Not file descriptor, so return end of file
		 */
		return 0;
	}
	pblock = maxblocklist - 1;
	if (n < lastreadline ||
	    (n == lastreadline && !(pblock->b_flags & PARTLY))) {
		/*
		 * The line asked for has been read already.
		 * Perform binary search in the blocklist to find the block
		 * where it's in.
		 */
		register struct block *min, *mid;

		min = blocklist + 1;
		do {
			mid = min + (pblock - min) / 2;
			if (n > mid->b_end) {
				min = mid + 1;
			}
			else pblock = mid;
		} while (min < pblock);
		/* Found, pblock is now a reference to the block wanted */
		if (!pblock->b_info) readblock(pblock);
		return pblock;
	}

	/*
	 * The line was'nt read yet, so read blocks until found
	 */
	for (;;) {
		if (interrupt && !disable_interrupt) return 0;
		pblock = new_block();
		if (pblock->b_end >= n) {
			return pblock;
		}
		if (pblock->b_flags & PARTLY) {
			/*
			 * We did not find it, and the last block could not be
			 * read completely, so return 0;
			 */
			return	0;
		}
	}
	/* NOTREACHED */
}

char *
getline(n, disable_interrupt) long n; {
	register struct block *pblock;

	if (!(pblock = getblock(n, disable_interrupt))) {
		return (char *) 0;
	}
	return pblock->b_info + pblock->b_offs[n - ((pblock-1)->b_end + 1)];
}

/*
 * Find the last line of the input, and return its number
 */

long
to_lastline() {

	for (;;) {
		if (!getline(lastreadline + 1, 0)) {
			/*
			 * "lastreadline" always contains the linenumber of
			 * the last line read. So, if the call to getline
			 * succeeds, "lastreadline" is affected
			 */
			if (interrupt) return -1L;
			return lastreadline;
		}
	}
	/* NOTREACHED */
}

#if MAXNBLOCKS
int nblocks;		/* Count number of large blocks */
#endif

/*
 * Allocate some memory. If unavailable, free some and try again.
 * If all fails, panic.
 */

char *
alloc(size, isblock) unsigned size; {

	register char *pmem;
	register struct block *pblock, *bllist;
	char *malloc();
	long lseek();
	register long i;

	bllist = blocklist;
	while (
#if MAXNBLOCKS
	   (isblock && nblocks >= MAXNBLOCKS) ||
#endif
	   !(pmem = malloc(size))   /* No space */
	) {
		if (b_tail == 0) {
			/*
			 * Also, no blocks in core. Pity
			 */
			panic("No core");
		}
#if MAXNBLOCKS
		nblocks--;
#endif
		pblock = bllist + b_tail;
		b_tail = pblock->b_next;
		if (!nopipe && !(pblock->b_flags & DUMPED)) {
			/*
			 * Dump the block on a temporary file
			 */
			if (!tfdes) {
				/*
				 * create and open temporary files
				 */
				tfdes = opentemp(0);
				ifdes = opentemp(1);
			}
			pblock->b_flags |= DUMPED;
			/*
			 * Find out where to dump the block, and dump it
			 */
			i = (pblock-1)->b_end * sizeof(int);
			(VOID) lseek(tfdes,
				((long) BLOCKSIZE * (pblock - bllist)), 0);
			if (write(tfdes, pblock->b_info, BLOCKSIZE)
			    != BLOCKSIZE) {
				panic("write failed");
			}
			/*
			 * Also dump the offsets of the lines in the block
			 */
			(VOID) lseek(ifdes, i, 0);
			i = pblock->b_end * sizeof(int) - i;
			if (write(ifdes, (char *) pblock->b_offs, (int) i)
			    != (int) i) {
				panic("Write failed");
			}
		}
		/*
		 * Now that the block is dumped, the space taken by it can
		 * be freed
		 */
		free((char *) pblock->b_offs);
		free(pblock->b_info);
		pblock->b_info = (char *) 0;
	}
#if MAXNBLOCKS
	if (isblock) nblocks++;
#endif
	return pmem;
}

/*
 * Re-allocate the memorychunk pointed to by ptr, to let it
 * grow or shrink.
 * realloc of the standard C library is useless, as it is destructive
 * if the malloc fails.
 */

STATIC char *
re_alloc(ptr,oldsize, newsize)
char *ptr; unsigned oldsize; unsigned newsize; {
	register char *pmem;
	register char *c1, *c2;

	/*
	 * We could be smarter here, by checking if newsize < oldsize, and in
	 * that case using realloc, but this depends on realloc using the
	 * same block if the block shrinks. The question is, wether all
	 * reallocs in the world do this.
	 */
	pmem = alloc(newsize, 0);
	if (oldsize) {
		/*
		 * This test makes re_alloc also work if there was no old block
		 */
		c1 = pmem;
		c2 = ptr;
		if (newsize > oldsize) {
			newsize = oldsize;
		}
		while (newsize--) {
			*c1++ = *c2++;
		}
		free(ptr);
	}
	return pmem;
}

/*
 * Append a block to the linked list of blockheaders of blocks that are
 * in core.
 */

STATIC VOID
addtolist(pblock) register struct block *pblock; {
	register struct block *bllist = blocklist;

	pblock->b_next = 0;
	(bllist + b_head)->b_next = pblock - bllist;
	b_head = pblock - bllist;
	if (!b_tail) {
		/*
		 * The list was empty, initialize
		 */
		b_tail = b_head;
	}
}

static char *saved;
static long filldegree;

/*
 * Try to read the block indicated by pblock
 */

STATIC VOID
nextblock(pblock) register struct block *pblock; {
	register char *c,	/* Run through pblock->b_info */
		      *c1;	/* indicate end of pblock->b_info */
	register int *poff;	/* pointer in line-offset list */
	register int cnt;	/* # of characters read */
	register unsigned siz;	/* Size of allocated line-offset list */
	static unsigned savedsiz;	/* saved "siz" */
	static int *savedpoff;		/* saved "poff" */
	static char *savedc1;		/* saved "c1" */

	if (pblock->b_flags & PARTLY) {
		/*
		 * The block was already partly filled. Initialize locals
		 * accordingly
		 */
		poff = savedpoff;
		siz = savedsiz;
		pblock->b_flags = 0;
		c1 = savedc1;
		if (c1 == pblock->b_info || *(c1 - 1)) {
			/*
			 * We had incremented "lastreadline" temporarily,
			 * because the last line could not be completely read