sort5.c

<B>Digital的Unix操作系统VAX 4.2源码</B>

		do
		{
			i = (*tp)->rn;
			if (getline(tfile[i], (*tp)->rp, maxrec, 1, tag) == 0)
			{
				doclose(tfile[i], setfil(i + a));

				if (--nf <= 0)
					break;
				++tp;
				bonus = cmpsave(nf);
			}
			else
				insert(tp, nf);
		} while (j && (*compare)((*tp)->rp, save) == 0);
	}

	for (i = a; i < b; i++)
	{
		if (i >= eargc)
			(void) unlink(setfil(i));
	}

	doclose(os, catgets(_m_catd, NL_SETN, 13, "merging"));

	free(fbuffer);
	free(buffer);
	free(save);
}

/*======================== comparison routines ==============================*/

/*
 * cmpa -- compare two whole lines
 */
cmpa(pa, pb)
register unsigned char *pa;
register unsigned char *pb;
{
	while(*pa == *pb++)
		if(*pa++ == '\n')
			return(0);
	return(
		*pa == '\n' ? fields[0].rflg:
		*--pb == '\n' ?-fields[0].rflg:
		*pb > *pa   ? fields[0].rflg:
		-fields[0].rflg
	);
}

/*
 * cmp -- compare two lines using fields
 */
int
cmp(line1, line2)
char *line1;	/* pointer to a line */
char *line2;	/* pointer to the other line */
{
	int result;		/* to retain result of comparison */
	int fieldno;		/* index of field under consideration */
	char *sfield1;		/* start of field in line1 */
	char *efield1;		/* end of field in line1 */
	char *sfield2;		/* start of field in line2 */
	char *efield2;		/* end of field in line2 */

	for (fieldno = (nfields > 0); fieldno <= nfields; fieldno++)
	{
		register struct field *fp; /* pointer to field description */

		fp = &fields[fieldno];

		/*
		 * position to start and end of fields
		 */
		if (fieldno != 0)
		{
			efield1 = skip(line1, fp, 1);
			sfield1 = skip(line1, fp, 0);
			efield2 = skip(line2, fp, 1);
			sfield2 = skip(line2, fp, 0);
		}
		else
		{
			efield1 = eol(line1);
			sfield1 = line1;
			efield2 = eol(line2);
			sfield2 = line2;
		}

		/*
		 * Do the comparison for the field that starts including
		 * sfield[12] and ends including efield[12] in lines[12].
		 */
		if (result=(*fp->fcmp)(fp, sfield1, efield1, sfield2, efield2))
			return fp->rflg * result;
	}

	/*
	 * up to now all fields have compared equal, try to compare the
	 * whole line to break the tie if not discarding duplicates anyway
	 */
	if (uflg)
		return(0);

	return(cmpa(line1, line2));
}

/*
 * tagcmp -- compare two tagged records.
 */

tagcmp(r1, r2)
register char *r1, *r2;
{	int result;
	register struct field *fp;
	int fieldno;
	int offset;		/* offset of record pointer */

	for (fieldno = (nfields > 0);  fieldno <= nfields; fieldno++) {
		fp = &fields[fieldno];
		offset = fieldno + 1 - (nfields > 0);
		
		if (result = strcmp(r1 + ((short *)r1)[offset], r2 + ((short *)r2)[offset]))
			return fp->rflg * -result;
	}
	return 0;
}

#define qsexc(p,q)	t = *p; *p = *q; *q = t
#define qstexc(p,q,r)	t = *p; *p = *r; *r = *q; *q = t

qksort(a, l)
char **a;
char **l;
{
	register char **i;
	register char **j;
	register char **lp;
	register char **hp;
	char **k;
	int c;
	int delta;
	char *t;
	unsigned n;


start:
	if ((n = l - a) <= 1)
		return;

	n /= 2;

	if (n >= MTHRESH)
	{
		lp = a + n;
		i = lp - 1;
		j = lp + 1;
		delta = 0;

		c = (*compare)(*lp, *i);
		if (c < 0)
			--delta;
		else if (c > 0)
			++delta;

		c = (*compare)(*lp, *j);
		if (c < 0)
			--delta;
		else if (c > 0)
			++delta;

		if ((delta /= 2) && (c = (*compare)(*i, *j)))
			if (c > 0)
				n -= delta;
			else
				n += delta;
	}

	hp = lp = a + n;
	i = a;
	j = l - 1;

	for (;;)
	{
		if (i < lp)
		{
			if ((c = (*compare)(*i, *lp)) == 0)
			{
				--lp;
				qsexc(i, lp);
				continue;
			}

			if (c < 0)
			{
				++i;
				continue;
			}
		}

loop:
		if (j > hp)
		{
			if ((c = (*compare)(*hp, *j)) == 0)
			{
				++hp;
				qsexc(hp, j);
				goto loop;
			}

			if (c > 0)
			{
				if (i == lp)
				{
					++hp;
					qstexc(i, hp, j);
					i = ++lp;
					goto loop;
				}
				qsexc(i, j);
				--j;
				++i;
				continue;
			}
			--j;
			goto loop;
		}

		if (i == lp)
		{
			if (uflg)
				for (k = lp; k < hp;)
					**k++ = '\0';
			if (lp - a >= l - hp)
			{
				qksort(hp + 1, l);
				l = lp;
			}
			else
			{
				qksort(a, lp);
				a = hp + 1;
			}
			goto start;
		}

		--lp;
		qstexc(j, lp, i);
		j = --hp;
	}
}

/*===================== help functions for comparisons ======================*/

/*
 * skip -- skip in a record according to field specifications
 */
char *
skip(p, fp, j)
register char *p;	/* line to work on */
struct field *fp;	/* field to isolate */
int j;			/* 1 means get the end of the field, 0 means start */
{
	register i;
	register char tbc;

	if ((i = fp->m[j]) < 0)		/* can only happen for j = 1! */
		return(eol(p));

	/*
	 * get to correct field, handling tabchar or spaces
	 */
	if ((tbc = tabchar) != 0)
		while (--i >= 0)
		{
			while (*p != tbc)
				if (*p != '\n')
					p++;
				else
					goto ret;

			if (i > 0 || j == 0)
				p++;
		}
	else
		while (--i >= 0)
		{
			while (blank(*p))
				p++;
			while (!blank(*p))
				if (*p != '\n')
					p++;
				else
					goto ret;
		}

	/*
	 * skip blanks
	 */
	if (fp->bflg[j])
	{
		if (j == 1 && fp->m[j] > 0)
			p++;

		while (blank(*p))
			p++;
	}

	/*
	 * get to byte position within field
	 */
	i = fp->n[j];

	while((i-- > 0) && (*p != '\n'))
		p++;

ret:
	return(p);
}

/* 
 * settag -- setup the tag fields for a record
 */

char *
settag(tp, start, end, amount)
short *tp;		/* pointer to tag area */
char  *start;		/* pointer to record area */
char  *end;		
int    amount;	
{	char *save = (char *)tp;
	int fieldno;
	char charsave;
	char *ep;
	struct field *fp;
	int len;

	for (fieldno = (nfields > 0) ; fieldno <= nfields; fieldno++) {
		fp = &fields[fieldno];
		/*
		 * set offset to start of field in pointer area
		 */
		*end++ = '\0';
		amount--;
		*++tp  = (short)(end - save);

		ep     = skip(start, fp, 1);
		/*
		 * nul terminate for strxfrm
		 */
		charsave = *ep;		
		*ep      = '\0';

		if ((len = strxfrm(end, skip(start, fp, 0), amount)) > amount) {
			*ep = charsave;
			return (char *)0;
		}

		/*
		 * restore character and bump pointers
		 */
		*ep     = charsave;
		end    += len;
		amount -= len;
	}
	if (amount > 0)
		*end++ = '\0';
	else
		return (char *)0;
	/*
	 * first field is the length of the entire record 
	 */
	*(short *)save = end - save;	

	return end;
}

/*
 * cmpsave -- save result of comparison for later use
 */
cmpsave(n)
register int n;
{
	register int award;

	if (n < 2)
		return (0);

	for (n++, award = 0; (n >>= 1) > 0; award++)
	;

	return (award);
}

/*
 * asciicmp -- compare ascii strings
 */
int
asciicmp(fp, s1, e1, s2, e2)
struct field *fp;		/* pointer to field description */
register char *s1;		/* beginning of first field */
char *e1;			/* end of first field */
register char *s2;		/* beginning of second field */
char *e2;			/* end of second field */
{
	register char *ignore;	/* ptr to ignore table */
	register char *code;	/* ptr to code conversion */
	int a;

	code = fp->code;
	ignore = fp->ignore;

	for (;;)
	{
		/*
		 * skip ignore characters
		 */
		while (ignore[*s1])
			s1++;
		while (ignore[*s2])
			s2++;

		if (s1 >= e1 || *s1 == '\n')
			if (s2 < e2 && *s2 != '\n')
				return 1;
			else
				break;

		if (s2 >= e2 || *s2 == '\n')
			return -1;

		if (a = ((int)code[*s2++] & 0xFF) - ((int)code[*s1++] & 0xFF))
			return a;
	}

	/*
	 * the two fields compare equal
	 */
	return 0;
}

/*
 * intlcmp -- international collation
 */
int
intlcmp(fp, s1, e1, s2, e2)
struct field *fp;		/* pointer to field description */
char *s1;			/* beginning of first field */
char *e1;			/* end of first field */
char *s2;			/* beginning of second field */
char *e2;			/* end of second field */
{
	int result;		/* result of collation */
	char save1, save2;	/* save characters to allow nul terminarion */

	/*
	 * "ignore" is specified in the collation itself
	 * NOT_YET: "fold" is done by converting codes to upper case
	 */

	/*
	 * as e1/e2 are to be compared too:
	 */
	save1 = *++e1;
	save2 = *++e2;
	*e1 = *e2 = '\0';

	result = strcoll(s2, s1);

	*e1 = save1;
	*e2 = save2;

	return result;
}

/*
 * numcmp -- numerical comparison of two fields
 *	bytewise comparison of two numbers of the
 *	form [-][0-9]*\.[0-9]*
 */
int
numcmp(fp, s1, e1, s2, e2)
struct field *fp;		/* pointer to field description */
char *s1;			/* beginning of first field */
char *e1;			/* end of first field */
char *s2;			/* beginning of second field */
char *e2;			/* end of second field */
{
	static char radix;	/* radix char to use, initially zero */
	int sa;			/* sign of number in first line */
	int sb;			/* sign of number in second line */
	register char *ipa;	/* tmp ptr into first number */
	register char *ipb;	/* tmp ptr into second number */
	char *jpa;		/* save tmp ptr into first number */
	char *jpb;		/* save tmp ptr into second number */
	int result = 0;		/* result of comparison */

	/*
	 * set radix character
	 */
	if (radix == '\0')
	{
		if ((radix = *nl_langinfo(RADIXCHAR)) == '\0')
			radix = '.';
	}

	/*
	 * evaluate sign
	 */
	sa = sb = 1;
	if (*s1 == '-')
	{
		s1++;
		sa = -sa;
	}

	if (*s2 == '-')
	{
		s2++;
		sb = -sb;
	}

	/*
	 * skip to end of number before the decimal point
	 */
	for (ipa = s1; ipa < e1 && isdigit(*ipa); ipa++)
	;

	for (ipb = s2; ipb < e2 && isdigit(*ipb); ipb++)
	;

	/*
	 * save pointers for scan after decimal point
	 */
	jpa = ipa;
	jpb = ipb;

	if (sa == sb)
		while (ipa > s1 && ipb > s2)
			if (*--ipb - *--ipa != 0)
				result = *ipb - *ipa;

	while (ipa > s1)
		if (*--ipa != '0')
			return(-sa);
	while (ipb > s2)
		if (*--ipb != '0')
			return(sb);

	if (result)
		return (result * sa);

	if (*(s1 = jpa) == radix)
		s1++;

	if (*(s2 = jpb) == radix)
		s2++;

	if (sa == sb)
		while (s1 < e1 && isdigit(*s1)
		   && s2 < e2 && isdigit(*s2))
			if ((result = *s2++ - *s1++) != 0)
				return(result*sa);

	while (s1 < e1 && isdigit(*s1))
		if (*s1++ != '0')
			return(-sa);

	while (s2 < e2 && isdigit(*s2))
		if (*s2++ != '0')
			return(sb);

	return 0;
}

int
monthcmp(fp, s1, e1, s2, e2)
struct field *fp;		/* pointer to field description */
char *s1;			/* beginning of first field */
char *e1;			/* end of first field */
char *s2;			/* beginning of second field */
char *e2;			/* end of second field */
{
	return (month(s1) - month(s2));
}

/*
 * month -- return numerical match value for a month
 */
month(s)
char *s;
{
	static char *months[] = { "jan", "feb", "mar", "apr", "may", "jun",
				  "jul", "aug", "sep", "oct", "nov", "dec" };
	register char *t;
	register char *u;
	register i;
	register char *f = fold + 128;

	for (i = 0; i < sizeof(months) / sizeof(*months); i++)
	{
		for (t = s, u = months[i]; f[*t++] == f[*u++]; )
			if (*u == 0)
				return(i);
	}
	return(-1);
}

/*====================== file handling routines =============================*/