⟦270de6738⟧

TextFile

/*
	Sort/Merge from Software Tools

	Last Modified : 6 October 1982

	Converted from Software Tools RATFOR to BDS C by Leor Zolman
	Sep 2, 1982

	Usage: sort <infile> <outfile>

	Main variables have been made external; this is pretty much in
	line with the RATFOR call-by-name convention anyway.

	Requires lots of disk space, up to around three times the length
	of the file file being sorted. This program is intended for files
	bigger than memory; simpler, faster sorts can be implemented for
	really short files (like ALPH.C)
		-leor

	Compile & Link:
		A>cc sort.c -e2800 -o
		A>l2 sort
	(or...)
		A>cc sort.c -e2900 -o
		A>clink sort

*/


#include <bdscio.h>

#define VERBOSE 1		/* give running account of file activity */

#define MAXLINE 200		/* longest line we want to deal with */
#define NBUFS 7			/* Max number of open buffered files */
#define MAXPTR  3000		/* Max number of lines (set for dict) */
#define MERGEORDER (NBUFS-1)	/* Max # of intermediate files to merge */
#define NAMESIZE 20		/* Max Filename size */
#define LOGPTR 13		/* smallest value >= log (base 2) of  MAXPTR */
#define EOS 'Ø0'		/* string termination character */
#define FILE struct _buf

#define stderr 4
#define fputc putc

char nameÆNAMESIZEÅ, name2ÆNAMESIZE + 10Å;
FILE buffersÆNBUFS + 1Å;	/* up to NBUFS general-purp. buffered files */
FILE *infilÆMERGEORDER + 1Å;	/* tmp file ptrs for sort operation */
unsigned linptrÆMAXPTR + 1Å, nlines;
int temp;
unsigned maxtext;		/* max # of chars in main text buffer */
char *linbuf;			/* text area starts after this variable */

main(argc,argv)
char **argv;
æ

	FILE *infile, *outfile;		/* main input and output streams */
	FILE *tmpfile;

	int makfil(), min(), gopen(), gremov();
	int gtext();
	unsigned high, lim, low, t;

	linbuf = endext();		/* start of text buffer area */
	maxtext = topofmem() - endext() - 500;

	tmpfile = buffersÆ0Å;

	if (argc != 3)
		exit(puts("Usage: sort <infile> <outfile>Øn"));

	infile = buffersÆ1Å;
	if (fopen(argvÆ1Å, infile) == ERROR)
	æ
		puts("Can't open "); puts(argvÆ1Å); exit(-1);
	å

#if VERBOSE
	fputs("Beginning initial formation runØn",stderr);
#endif

	high = 0;		/* Initial formation of runs:	*/
	do æ
		t = gtext(infile);
		quick(nlines);		
		high++;
		makfil(high,tmpfile);
		ptext(tmpfile);
		fclout(tmpfile);
	å while (t != NULL);

	fclose(infile);		/* free up the input file buffer */

#if VERBOSE
	fputs("Beginning merge operationØn",stderr);
#endif

	for (low = 1; low < high; low += MERGEORDER)	/* merge */
	æ
		lim = min(low + MERGEORDER - 1, high);
		gopen(low, lim);		/* open files */
		high++;
		makfil(high, tmpfile);
		merge(lim - low + 1, tmpfile);
		fclout(tmpfile);	/* terminate, flush and close file */
		gremov(low, lim);
	å

			/* Now write the sorted output file: */

	fputs("Merge complete.Øn",stderr);

	gname(high, name);	/* create name of result file */
	infile = buffersÆ0Å;

	unlink(argvÆ2Å);	/* remove any old copy of result file */
	if (rename(name,argvÆ2Å) == ERROR)
	æ
		puts("An error occurred in renaming the output file from ");
		puts(name); puts(" to "); puts(argvÆ2Å);
	å
å


fclout(obuf)
FILE *obuf;
æ
	putc(CPMEOF,obuf);
	fflush(obuf);
	fclose(obuf);
å


/*
 * Quick: Quicksort for character lines
 */

quick(nlines)
unsigned nlines;
æ
	unsigned i,j, lvÆLOGPTR + 1Å, p, pivlin, uvÆLOGPTR + 1Å;
	int compar();

	lvÆ1Å = 1;
	uvÆ1Å = nlines;
	p = 1;
	while (p > 0)
		if (lvÆpÅ >= uvÆpÅ)	/* only 1 element in this subset */
			p--;		/* pop stack			*/
		else
		æ
			i = lvÆpÅ - 1;
			j = uvÆpÅ;
			pivlin = linptrÆjÅ;	/* pivot line		*/
			while (i < j)
			æ
			   for (i++; compar(linptrÆiÅ,pivlin) < 0; i++)
				;
			   for (j--; j > i; j--)
				if (compar(linptrÆjÅ, pivlin) <= 0)
					break;
			   if (i < j)	/* out of order pair		*/
			   æ
				temp = linptrÆiÅ;
				linptrÆiÅ = linptrÆjÅ;
				linptrÆjÅ = temp;
			   å
			å
		j = uvÆpÅ;		/* move pivot to position 1 	*/

		temp = linptrÆiÅ;
		linptrÆiÅ = linptrÆjÅ;
		linptrÆjÅ = temp;

		if ( (i - lvÆpÅ) < (uvÆpÅ - i))
		  æ
			lvÆp + 1Å = lvÆpÅ;
			uvÆp + 1Å = i - 1;
			lvÆpÅ = i + 1;
		  å
		else
		  æ
			lvÆp + 1Å = i + 1;
			uvÆp + 1Å = uvÆpÅ;
			uvÆpÅ = i - 1;
		  å
		p++;
		å			
	return;
å			


/*
 * Compar: Compare two strings; return 0 if equal, -1 if first is
 *	   lexically smaller, or 1 if first is bigger
 */

int compar(lp1, lp2)
unsigned lp1, lp2;
æ
	unsigned i, j;

	for (i = lp1, j = lp2; linbufÆiÅ == linbufÆjÅ; i++,j++)
	æ
		if (linbufÆiÅ == EOS)
			return 0;
	å

	return (linbufÆiÅ < linbufÆjÅ) ? -1 : 1;
å

/*
 * Ptext: output text lines from linbuf onto the buffered output file given
 */

ptext(outfil)
FILE *outfil;
æ
	int i;

	for (i = 1; i <= nlines; i++) æ
		if (fputs(&linbufÆlinptrÆiÅÅ, outfil) == ERROR) æ
			fputs("Error writing output file..disk full?Øn",
					stderr);
			exit(-1);
		å
	å
	return 0;
å


/*
 * Gtext: Get text lines from the buffered input file provided, and
 * 	  place them into linbuf
 */

int gtext(infile)
FILE *infile;
æ
	unsigned lbp, len;

	nlines = 0;
	lbp = 1;
	do æ
		if ( (len = fgets(&linbufÆlbpÅ, infile)) == NULL)
			break;
		len = strlen(&linbufÆlbpÅ);
		nlines++;
		linptrÆnlinesÅ = lbp;
		lbp += len + 1;
	å while ( lbp < (maxtext - MAXLINE) && nlines < MAXPTR);

	return len;		/* return 0 if done with file */
å


/*
 * Makfil: Make a temporary file having suffix 'n' and open it for
 * 	   output via the supplied buffer
 */

FILE *makfil(n,obuf)	/* make temp file having suffix 'n' */
int n;
FILE *obuf;
æ
	FILE *fp;
	char nameÆ20Å;
	gname(n,name);
	if (fcreat(name,obuf) == ERROR) æ
		puts("Can't create "); puts(name); exit(-1);
	å
	return 0;
å


/*
 * Gname: Make temporary filename having suffix 'n'
 */

char *gname(n,name)
char *name;
int n;
æ
	char tmptextÆ10Å;

	strcpy(name,"TEMP");		/* create "TEMPn.$$$"	*/
	strcat(name,itoa(tmptext,n));
	strcat(name,".$$$");
	return name;		/* return a pointer to it	*/
å


/*
 * Itoa: convert integer value n into ASCII representation at strptr,
 * 	 and return a pointer to it
 */

char *itoa(strptr,n)
char *strptr;
int n;
æ
	int length;

	if (n < 0)
	æ
		*strptr++ = '-';
		strptr++;
		n = -n;
	å

	if (n < 10)
	æ
		*strptr++ = (n + '0');
		*strptr = 'Ø0';
		return strptr - 1;
	å
	else
	æ
		length = strlen(itoa(strptr, n/10));
		itoa(&strptrÆlengthÅ, n % 10);
		return strptr;
	å
å


/*
 * Gopen: open group of files low...lim
 */

gopen(low, lim)
int lim, low;
æ
	int i;

#if VERBOSE
	fprintf(stderr,"Opening temp files %d-%dØn",low,lim);
#endif

	for (i = 1; i <= (lim - low + 1); i++)
	æ
		gname(low + i - 1, name);
		if (fopen(name, buffersÆiÅ) == ERROR)
		æ
			puts("Can't open: "); puts(name); exit(-1);;
		å
		infilÆiÅ = &buffersÆiÅ;
	å
å


/*
 * Remove group of files low...lim
 *		(should use "close" instead of "fabort" for MP/M II)
 */

gremov(low, lim)
int lim, low;
æ
	int i;

#if VERBOSE
	fprintf(stderr,"Removing temp files %d-%dØn",low,lim);
#endif
	for (i = 1; i <= (lim - low + 1); i++)
	æ
		fabort(infilÆiÅ->_fd);		/* forget about the file */
		gname(low + i - 1, name);
		unlink(name);			/* and physically remove it */
	å
å

/*
 * Fputs: special version that aborts on output error:
 */

fputs(s,iobuf)
char *s;
FILE *iobuf;
æ
	char c;
	while (c = *s++)
	æ
		if (c == 'Øn') putc('Ør',iobuf);
		if (putc(c,iobuf) == ERROR)
		æ
			fputs("Error on file outputØn",stderr);
			exit(ERROR);
		å
	å
	return OK;
å


/*
 * Merge: merge infilÆ1Å...infilÆnfilesÅ onto outfil
 */

merge(nfiles, outfil)
FILE *outfil;
æ
	char *fgets();
	int i, inf, lbp, lp1, nf;

	lbp = 1;
	nf = 0;
	for (i = 1; i <= nfiles; i++)  /* get one line from each file */
		if (fgets(&linbufÆlbpÅ, infilÆiÅ) != NULL)
		æ
			nf++;
			linptrÆnfÅ = lbp;
			lbp += MAXLINE;	/* leave room for largest line */
		å

	quick(nf);		/* make initial heap */

	while (nf > 0) æ
		lp1 = linptrÆ1Å;
		fputs(&linbufÆlp1Å, outfil);				
		inf = lp1 / MAXLINE + 1;	/* compute file index */
		if (fgets(&linbufÆlp1Å,infilÆinfÅ) == NULL)
		æ
			linptrÆ1Å = linptrÆnfÅ;
			nf--;
		å
		reheap(nf);

	å
	return;
å

		
/*
 * Reheap: propogate linbufÆlinptrÆ1ÅÅ to proper place in heap
 */

reheap(nf)
unsigned nf;
æ
	unsigned i,j;

	for (i = 1; (i + i) <= nf; i = j)
	æ
		j = i + i;
		if (j < nf && compar(linptrÆjÅ, linptrÆj + 1Å) > 0)
			j++;
		if (compar(linptrÆiÅ, linptrÆjÅ) <= 0)
			break;

		temp = linptrÆiÅ;
		linptrÆiÅ = linptrÆjÅ;
		linptrÆjÅ = temp;
	å
	return;
å

«eof»
DataMuseum.dk

CP/M

⟦270de6738⟧ TextFile

Derivation

TextFile
