sort.c

这是一个同样来自贝尔实验室的和UNIX有着渊源的操作系统, 其简洁的设计和实现易于我们学习和理解

		case Gflag:
		case Nflag:
		case Gflag|Nflag:
		case Gflag|Rflag:
		case Nflag|Rflag:
		case Gflag|Nflag|Rflag:
			f->dokey = dokey_gn;
			break;
		case Mflag:
		case Mflag|Rflag:
			f->dokey = dokey_m;
			makemapm(f);
			break;
		case Dflag:
		case Dflag|Fflag:
		case Dflag|Fflag|Iflag:
		case Dflag|Fflag|Iflag|Rflag:
		case Dflag|Fflag|Iflag|Rflag|Wflag:
		case Dflag|Fflag|Iflag|Wflag:
		case Dflag|Fflag|Rflag:
		case Dflag|Fflag|Rflag|Wflag:
		case Dflag|Fflag|Wflag:
		case Dflag|Iflag:
		case Dflag|Iflag|Rflag:
		case Dflag|Iflag|Rflag|Wflag:
		case Dflag|Iflag|Wflag:
		case Dflag|Rflag:
		case Dflag|Rflag|Wflag:
		case Dflag|Wflag:
		case Fflag:
		case Fflag|Iflag:
		case Fflag|Iflag|Rflag:
		case Fflag|Iflag|Rflag|Wflag:
		case Fflag|Iflag|Wflag:
		case Fflag|Rflag:
		case Fflag|Rflag|Wflag:
		case Fflag|Wflag:
		case Iflag:
		case Iflag|Rflag:
		case Iflag|Rflag|Wflag:
		case Iflag|Wflag:
		case Wflag:
			f->dokey = dokey_dfi;
			makemapd(f);
			break;
		}
	}

	/*
	 * random spot checks
	 */
	if(args.nfile > 1 && args.cflag) {
		fprint(2, "sort: -c can have at most one input file\n");
		done("option");
	}
	return;
}

uchar*
skip(uchar *l, int n1, int n2, int bflag, int endfield)
{
	int i, c, tc;
	Rune r;

	if(endfield && n1 < 0)
		return 0;

	c = *l++;
	tc = args.tabchar;
	if(tc) {
		if(tc < Runeself) {
			for(i=n1; i>0; i--) {
				while(c != tc) {
					if(c == '\n')
						return 0;
					c = *l++;
				}
				if(!(endfield && i == 1))
					c = *l++;
			}
		} else {
			l--;
			l += chartorune(&r, (char*)l);
			for(i=n1; i>0; i--) {
				while(r != tc) {
					if(r == '\n')
						return 0;
					l += chartorune(&r, (char*)l);
				}
				if(!(endfield && i == 1))
					l += chartorune(&r, (char*)l);
			}
			c = r;
		}
	} else {
		for(i=n1; i>0; i--) {
			while(c == ' ' || c == '\t')
				c = *l++;
			while(c != ' ' && c != '\t') {
				if(c == '\n')
					return 0;
				c = *l++;
			}
		}
	}

	if(bflag)
		while(c == ' ' || c == '\t')
			c = *l++;

	l--;
	for(i=n2; i>0; i--) {
		c = *l;
		if(c < Runeself) {
			if(c == '\n')
				return 0;
			l++;
			continue;
		}
		l += chartorune(&r, (char*)l);
	}
	return l;
}

void
dokey_gn(Key *k, uchar *lp, uchar *lpe, Field *f)
{
	uchar *kp;
	int c, cl, dp;
	int state, nzero, exp, expsign, rflag;

	cl = k->klen + 3;
	kp = k->key + cl;	/* skip place for sign, exponent[2] */

	nzero = 0;		/* number of trailing zeros */
	exp = 0;		/* value of the exponent */
	expsign = 0;		/* sign of the exponent */
	dp = 0x4040;		/* location of decimal point */
	rflag = f->flags&Rflag;	/* xor of rflag and - sign */
	state = NSstart;

	for(;; lp++) {
		if(lp >= lpe)
			break;
		c = *lp;

		if(c == ' ' || c == '\t') {
			switch(state) {
			case NSstart:
			case NSsign:
				continue;
			}
			break;
		}
		if(c == '+' || c == '-') {
			switch(state) {
			case NSstart:
				state = NSsign;
				if(c == '-')
					rflag = !rflag;
				continue;
			case NSexp:
				state = NSexpsign;
				if(c == '-')
					expsign = 1;
				continue;
			}
			break;
		}
		if(c == '0') {
			switch(state) {
			case NSdigit:
				if(rflag)
					c = ~c;
				*kp++ = c;
				cl++;
				nzero++;
				dp++;
				state = NSdigit;
				continue;
			case NSfract:
				if(rflag)
					c = ~c;
				*kp++ = c;
				cl++;
				nzero++;
				state = NSfract;
				continue;
			case NSstart:
			case NSsign:
			case NSzero:
				state = NSzero;
				continue;
			case NSzerofract:
			case NSpoint:
				dp--;
				state = NSzerofract;
				continue;
			case NSexpsign:
			case NSexp:
			case NSexpdigit:
				exp = exp*10 + (c - '0');
				state = NSexpdigit;
				continue;
			}
			break;
		}
		if(c >= '1' && c <= '9') {
			switch(state) {
			case NSzero:
			case NSstart:
			case NSsign:
			case NSdigit:
				if(rflag)
					c = ~c;
				*kp++ = c;
				cl++;
				nzero = 0;
				dp++;
				state = NSdigit;
				continue;
			case NSzerofract:
			case NSpoint:
			case NSfract:
				if(rflag)
					c = ~c;
				*kp++ = c;
				cl++;
				nzero = 0;
				state = NSfract;
				continue;
			case NSexpsign:
			case NSexp:
			case NSexpdigit:
				exp = exp*10 + (c - '0');
				state = NSexpdigit;
				continue;
			}
			break;
		}
		if(c == '.') {
			switch(state) {
			case NSstart:
			case NSsign:
				state = NSpoint;
				continue;
			case NSzero:
				state = NSzerofract;
				continue;
			case NSdigit:
				state = NSfract;
				continue;
			}
			break;
		}
		if((f->flags & Gflag) && (c == 'e' || c == 'E')) {
			switch(state) {
			case NSdigit:
			case NSfract:
				state = NSexp;
				continue;
			}
			break;
		}
		break;
	}

	switch(state) {
	/*
	 * result is zero
	 */
	case NSstart:
	case NSsign:
	case NSzero:
	case NSzerofract:
	case NSpoint:
		kp = k->key + k->klen;
		k->klen += 2;
		kp[0] = 0x20;	/* between + and - */
		kp[1] = 0;
		return;
	/*
	 * result has exponent
	 */
	case NSexpsign:
	case NSexp:
	case NSexpdigit:
		if(expsign)
			exp = -exp;
		dp += exp;

	/*
	 * result is fixed point number
	 */
	case NSdigit:
	case NSfract:
		kp -= nzero;
		cl -= nzero;
		break;
	}

	/*
	 * end of number
	 */
	c = 0;
	if(rflag)
		c = ~c;
	*kp = c;

	/*
	 * sign and exponent
	 */
	c = 0x30;
	if(rflag) {
		c = 0x10;
		dp = ~dp;
	}
	kp = k->key + k->klen;
	kp[0] = c;
	kp[1] = (dp >> 8);
	kp[2] = dp;
	k->klen = cl+1;
}

void
dokey_m(Key *k, uchar *lp, uchar *lpe, Field *f)
{
	uchar *kp;
	Rune r, place[3];
	int c, cl, pc;
	int rflag;

	rflag = f->flags&Rflag;
	pc = 0;

	cl = k->klen;
	kp = k->key + cl;

	for(;;) {
		/*
		 * get the character
		 */
		if(lp >= lpe)
			break;
		c = *lp;
		if(c >= Runeself) {
			lp += chartorune(&r, (char*)lp);
			c = r;
		} else
			lp++;

		if(c < nelem(f->mapto)) {
			c = f->mapto[c];
			if(c == 0)
				continue;
		}
		place[pc++] = c;
		if(pc < 3)
			continue;
		for(c=11; c>=0; c--)
			if(memcmp(month[c], place, sizeof(place)) == 0)
				break;
		c += 10;
		if(rflag)
			c = ~c;
		*kp++ = c;
		cl++;
		break;
	}

	c = 0;
	if(rflag)
		c = ~c;
	*kp = c;
	k->klen = cl+1;
}

void
dokey_dfi(Key *k, uchar *lp, uchar *lpe, Field *f)
{
	uchar *kp;
	Rune r;
	int c, cl, n, rflag;

	cl = k->klen;
	kp = k->key + cl;
	rflag = f->flags & Rflag;

	for(;;) {
		/*
		 * get the character
		 */
		if(lp >= lpe)
			break;
		c = *lp;
		if(c >= Runeself) {
			lp += chartorune(&r, (char*)lp);
			c = r;
		} else
			lp++;

		/*
		 * do the various mappings.
		 * the common case is handled
		 * completely by the table.
		 */
		if(c != 0 && c < Runeself) {
			c = f->mapto[c];
			if(c) {
				*kp++ = c;
				cl++;
			}
			continue;
		}

		/*
		 * for characters out of range,
		 * the table does not do Rflag.
		 * ignore is based on mapto[255]
		 */
		if(c != 0 && c < nelem(f->mapto)) {
			c = f->mapto[c];
			if(c == 0)
				continue;
		} else
			if(f->mapto[nelem(f->mapto)-1] == 0)
				continue;

		/*
		 * put it in the key
		 */
		r = c;
		n = runetochar((char*)kp, &r);
		kp += n;
		cl += n;
		if(rflag)
			while(n > 0) {
				kp[-n] = ~kp[-n];
				n--;
			}
	}

	/*
	 * end of key
	 */
	k->klen = cl+1;
	if(rflag) {
		*kp = ~0;
		return;
	}
	*kp = 0;
}

void
dokey_r(Key *k, uchar *lp, uchar *lpe, Field*)
{
	int cl, n;
	uchar *kp;

	n = lpe - lp;
	if(n < 0)
		n = 0;
	cl = k->klen;
	kp = k->key + cl;
	k->klen = cl+n+1;

	lpe -= 3;
	while(lp < lpe) {
		kp[0] = ~lp[0];
		kp[1] = ~lp[1];
		kp[2] = ~lp[2];
		kp[3] = ~lp[3];
		kp += 4;
		lp += 4;
	}

	lpe += 3;
	while(lp < lpe)
		*kp++ = ~*lp++;
	*kp = ~0;
}

void
dokey_(Key *k, uchar *lp, uchar *lpe, Field*)
{
	int n, cl;
	uchar *kp;

	n = lpe - lp;
	if(n < 0)
		n = 0;
	cl = k->klen;
	kp = k->key + cl;
	k->klen = cl+n+1;
	memmove(kp, lp, n);
	kp[n] = 0;
}

void
buildkey(Line *l)
{
	Key *k;
	uchar *lp, *lpe;
	int ll, kl, cl, i, n;
	Field *f;

	ll = l->llen - 1;
	kl = 0;			/* allocated length */
	cl = 0;			/* current length */
	k = 0;

	for(i=1; i<=args.nfield; i++) {
		f = &args.field[i];
		lp = skip(l->line, f->beg1, f->beg2, f->flags&B1flag, 0);
		if(lp == 0)
			lp = l->line + ll;
		lpe = skip(l->line, f->end1, f->end2, f->flags&Bflag, 1);
		if(lpe == 0)
			lpe = l->line + ll;
		n = (lpe - lp) + 1;
		if(n <= 0)
			n = 1;
		if(cl+(n+4) > kl) {
			kl = cl+(n+4);
			k = realloc(k, sizeof(Key) +
				(kl-1)*sizeof(k->key[0]));
			if(k == 0)
				nomem();
		}
		k->klen = cl;
		(*f->dokey)(k, lp, lpe, f);
		cl = k->klen;
	}

	/*
	 * global comparisons
	 */
	if(!(args.uflag && cl > 0)) {
		f = &args.field[0];
		if(cl+(ll+4) > kl) {
			kl = cl+(ll+4);
			k = realloc(k, sizeof(Key) +
				(kl-1)*sizeof(k->key[0]));
			if(k == 0)
				nomem();
		}
		k->klen = cl;
		(*f->dokey)(k, l->line, l->line+ll, f);
		cl = k->klen;
	}

	l->key = k;
	k->klen = cl;

	if(args.vflag) {
		write(2, l->line, l->llen);
		for(i=0; i<k->klen; i++) {
			fprint(2, " %.2x", k->key[i]);
			if(k->key[i] == 0x00 || k->key[i] == 0xff)
				fprint(2, "\n");
		}
	}
}

void
makemapm(Field *f)
{
	int i, c;

	for(i=0; i<nelem(f->mapto); i++) {
		c = 1;
		if(i == ' ' || i == '\t')
			c = 0;
		if(i >= 'a' && i <= 'z')
			c = i + ('A' - 'a');
		if(i >= 'A' && i <= 'Z')
			c = i;
		f->mapto[i] = c;
		if(args.vflag) {
			if((i & 15) == 0)
				fprint(2, "	");
			fprint(2, " %.2x", c);
			if((i & 15) == 15)
				fprint(2, "\n");
		}
	}
}

void
makemapd(Field *f)
{
	int i, j, c;

	for(i=0; i<nelem(f->mapto); i++) {
		c = i;
		if(f->flags & Iflag)
			if(c < 040 || c > 0176)
				c = -1;
		if((f->flags & Wflag) && c >= 0)
			if(c == ' ' || c == '\t')
				c = -1;
		if((f->flags & Dflag) && c >= 0)
			if(!(c == ' ' || c == '\t' ||
			    (c >= 'a' && c <= 'z') ||
			    (c >= 'A' && c <= 'Z') ||
			    (c >= '0' && c <= '9'))) {
				for(j=0; latinmap[j]; j+=3)
					if(c == latinmap[j+0] ||
					   c == latinmap[j+1])
						break;
				if(latinmap[j] == 0)
					c = -1;
			}
		if((f->flags & Fflag) && c >= 0) {
			if(c >= 'a' && c <= 'z')
				c += 'A' - 'a';
			for(j=0; latinmap[j]; j+=3)
				if(c == latinmap[j+0] ||
				   c == latinmap[j+1]) {
					c = latinmap[j+2];
					break;
				}
		}
		if((f->flags & Rflag) && c >= 0 && i > 0 && i < Runeself)
			c = ~c & 0xff;
		if(c < 0)
			c = 0;
		f->mapto[i] = c;
		if(args.vflag) {
			if((i & 15) == 0)
				fprint(2, "	");
			fprint(2, " %.2x", c);
			if((i & 15) == 15)
				fprint(2, "\n");
		}
	}
}

int	latinmap[] =
{
/*	lcase	ucase	fold	*/
	L'à',	L'À',	L'A',	
	L'á',	L'Á',	L'A',	
	L'â',	L'Â',	L'A',	
	L'ä',	L'Ä',	L'A',	
	L'ã',	L'Ã',	L'A',	
	L'å',	L'Å',	L'A',	
	L'è',	L'È',	L'E',	
	L'é',	L'É',	L'E',	
	L'ê',	L'Ê',	L'E',	
	L'ë',	L'Ë',	L'E',	
	L'ì',	L'Ì',	L'I',	
	L'í',	L'Í',	L'I',	
	L'î',	L'Î',	L'I',	
	L'ï',	L'Ï',	L'I',	
	L'ò',	L'Ò',	L'O',	
	L'ó',	L'Ó',	L'O',	
	L'ô',	L'Ô',	L'O',	
	L'ö',	L'Ö',	L'O',	
	L'õ',	L'Õ',	L'O',	
	L'ø',	L'Ø',	L'O',	
	L'ù',	L'Ù',	L'U',	
	L'ú',	L'Ú',	L'U',	
	L'û',	L'Û',	L'U',	
	L'ü',	L'Ü',	L'U',	
	L'æ',	L'Æ',	L'A',	
	L'ð',	L'Ð',	L'D',	
	L'ñ',	L'Ñ',	L'N',	
	L'ý',	L'Ý',	L'Y',	
	L'ç',	L'Ç',	L'C',	
	0,
};

Rune*	month[12] =
{
	L"JAN",
	L"FEB",
	L"MAR",
	L"APR",
	L"MAY",
	L"JUN",
	L"JUL",
	L"AUG",
	L"SEP",
	L"OCT",
	L"NOV",
	L"DEC",
};

/************** radix sort ***********/

enum
{
	Threshold	= 14,
};

void	rsort4(Key***, ulong, int);
void	bsort4(Key***, ulong, int);

void
sort4(void *a, ulong n)
{
	if(n > Threshold)
		rsort4((Key***)a, n, 0);
	else
		bsort4((Key***)a, n, 0);
}

void
rsort4(Key ***a, ulong n, int b)
{
	Key ***ea, ***t, ***u, **t1, **u1, *k;
	Key ***part[257];
	static long count[257];
	long clist[257+257], *cp, *cp1;
	int c, lowc, higc;

	/*
	 * pass 1 over all keys,
	 * count the number of each key[b].
	 * find low count and high count.
	 */
	lowc = 256;
	higc = 0;
	ea = a+n;
	for(t=a; t<ea; t++) {
		k = **t;
		n = k->klen;
		if(b >= n) {
			count[256]++;
			continue;
		}
		c = k->key[b];
		n = count[c]++;
		if(n == 0) {
			if(c < lowc)
				lowc = c;
			if(c > higc)
				higc = c;
		}
	}

	/*
	 * pass 2 over all counts,
	 * put partition pointers in part[c].
	 * save compacted indexes and counts
	 * in clist[].
	 */
	t = a;
	n = count[256];
	clist[0] = n;
	part[256] = t;
	t += n;

	cp1 = clist+1;
	cp = count+lowc;
	for(c=lowc; c<=higc; c++,cp++) {
		n = *cp;
		if(n) {
			cp1[0] = n;
			cp1[1] = c;
			cp1 += 2;
			part[c] = t;
			t += n;
		}
	}
	*cp1 = 0;

	/*
	 * pass 3 over all counts.
	 * chase lowest pointer in each partition
	 * around a permutation until it comes
	 * back and is stored where it started.
	 * static array, count[], should be
	 * reduced to zero entries except maybe
	 * count[256].
	 */
	for(cp1=clist+1; cp1[0]; cp1+=2) {
		c = cp1[1];
		cp = count+c;
		while(*cp) {
			t1 = *part[c];
			for(;;) {
				k = *t1;
				n = 256;
				if(b < k->klen)
					n = k->key[b];
				u = part[n]++;
				count[n]--;
				u1 = *u;
				*u = t1;
				if(n == c)
					break;
				t1 = u1;
			}
		}
	}

	/*
	 * pass 4 over all partitions.
	 * call recursively.
	 */
	b++;
	t = a + clist[0];
	count[256] = 0;
	for(cp1=clist+1; n=cp1[0]; cp1+=2) {
		if(n > Threshold)
			rsort4(t, n, b);
		else
		if(n > 1)
			bsort4(t, n, b);
		t += n;
	}
}

/*
 * bubble sort to pick up
 * the pieces.
 */
void
bsort4(Key ***a, ulong n, int b)
{
	Key ***i, ***j, ***k, ***l, **t;
	Key *ka, *kb;
	int n1, n2;

	l = a+n;
	j = a;

loop:
	i = j;
	j++;
	if(j >= l)
		return;

	ka = **i;
	kb = **j;
	n1 = ka->klen - b;
	n2 = kb->klen - b;
	if(n1 > n2)
		n1 = n2;
	if(n1 <= 0)
		goto loop;
	n2 = ka->key[b] - kb->key[b];
	if(n2 == 0)
		n2 = memcmp(ka->key+b, kb->key+b, n1);
	if(n2 <= 0)
		goto loop;

	for(;;) {
		k = i+1;

		t = *k;
		*k = *i;
		*i = t;

		if(i <= a)
			goto loop;

		i--;
		ka = **i;
		kb = *t;
		n1 = ka->klen - b;
		n2 = kb->klen - b;
		if(n1 > n2)
			n1 = n2;
		if(n1 <= 0)
			goto loop;
		n2 = ka->key[b] - kb->key[b];
		if(n2 == 0)
			n2 = memcmp(ka->key+b, kb->key+b, n1);
		if(n2 <= 0)
			goto loop;
	}
}