Add a -s option to make the radix sort be a stable sort. Based on

a diff from Eric Gouyer.  Closes PR 5553.  OK deraadt@

6 files changed, 35 insertions, 22 deletions

diff --git a/usr.bin/sort/fields.c b/usr.bin/sort/fields.c
index a6093e34e71..67303a9b368 100644
--- a/usr.bin/sort/fields.c
+++ b/usr.bin/sort/fields.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: fields.c,v 1.11 2006/02/14 14:45:36 jmc Exp $	*/
+/*	$OpenBSD: fields.c,v 1.12 2007/08/21 20:29:25 millert Exp $	*/
 
 /*-
  * Copyright (c) 1993
@@ -36,7 +36,7 @@
 #if 0
 static char sccsid[] = "@(#)fields.c	8.1 (Berkeley) 6/6/93";
 #else
-static char rcsid[] = "$OpenBSD: fields.c,v 1.11 2006/02/14 14:45:36 jmc Exp $";
+static char rcsid[] = "$OpenBSD: fields.c,v 1.12 2007/08/21 20:29:25 millert Exp $";
 #endif
 #endif /* not lint */
 
@@ -118,7 +118,7 @@ enterkey(RECHEADER *keybuf,	/* pointer to start of key */
 		    fieldtable->flags)) == NULL)
 			return (1);
 
-	if (UNIQUE)
+	if (UNIQUE || STABLE)
 		*(keypos-1) = REC_D;
 	keybuf->offset = keypos - keybuf->data;
 	keybuf->length = keybuf->offset + line->size;
@@ -196,7 +196,7 @@ enterfield(u_char *tablepos, u_char *endkey, struct field *cur_fld, int gflags)
  * To avoid confusing the exponent and the mantissa, use a field delimiter
  * if the exponent is exactly 61, 61+252, etc--this is ok, since it's the
  * only time a field delimiter can come in that position.
- * Reverse order is done analagously.
+ * Reverse order is done analogously.
  */
 
 u_char *
diff --git a/usr.bin/sort/fsort.c b/usr.bin/sort/fsort.c
index d706dd44ab5..e9811471088 100644
--- a/usr.bin/sort/fsort.c
+++ b/usr.bin/sort/fsort.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: fsort.c,v 1.18 2007/03/13 17:33:58 millert Exp $	*/
+/*	$OpenBSD: fsort.c,v 1.19 2007/08/21 20:29:25 millert Exp $	*/
 
 /*-
  * Copyright (c) 1993
@@ -36,7 +36,7 @@
 #if 0
 static char sccsid[] = "@(#)fsort.c	8.1 (Berkeley) 6/6/93";
 #else
-static char rcsid[] = "$OpenBSD: fsort.c,v 1.18 2007/03/13 17:33:58 millert Exp $";
+static char rcsid[] = "$OpenBSD: fsort.c,v 1.19 2007/08/21 20:29:25 millert Exp $";
 #endif
 #endif /* not lint */
 
@@ -173,9 +173,17 @@ fsort(int binno, int depth, union f_handle infiles, int nfiles, FILE *outfp,
 		}
 		get = getnext;
 		if (!ntfiles && !mfct) {	/* everything in memory--pop */
-			if (nelem > 1 && radixsort((const u_char **)keylist,
-			    nelem, weights, REC_D))
-				err(2, NULL);
+			if (nelem > 1) {
+				if (STABLE) {
+					i = sradixsort((const u_char **)keylist,
+					    nelem, weights, REC_D);
+				} else {
+					i = radixsort((const u_char **)keylist,
+					    nelem, weights, REC_D);
+				}
+				if (i)
+					err(2, NULL);
+			}
 			append(keylist, nelem, depth, outfp, putline, ftbl);
 			break;					/* pop */
 		}
diff --git a/usr.bin/sort/msort.c b/usr.bin/sort/msort.c
index cfd223c4570..342f8e37aea 100644
--- a/usr.bin/sort/msort.c
+++ b/usr.bin/sort/msort.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: msort.c,v 1.20 2007/03/13 17:33:58 millert Exp $	*/
+/*	$OpenBSD: msort.c,v 1.21 2007/08/21 20:29:25 millert Exp $	*/
 
 /*-
  * Copyright (c) 1993
@@ -36,7 +36,7 @@
 #if 0
 static char sccsid[] = "@(#)msort.c	8.1 (Berkeley) 6/6/93";
 #else
-static char rcsid[] = "$OpenBSD: msort.c,v 1.20 2007/03/13 17:33:58 millert Exp $";
+static char rcsid[] = "$OpenBSD: msort.c,v 1.21 2007/08/21 20:29:25 millert Exp $";
 #endif
 #endif /* not lint */
 
@@ -295,7 +295,7 @@ cmp(RECHEADER *rec1, RECHEADER *rec2)
 	for (cwts = wts; cwts; cwts = (cwts == wts1 ? 0 : wts1)) {
 		pos1 = rec1->data;
 		pos2 = rec2->data;
-		if (!SINGL_FLD && UNIQUE)
+		if (!SINGL_FLD && (UNIQUE || STABLE))
 			end = pos1 + min(rec1->offset, rec2->offset);
 		else
 			end = pos1 + min(rec1->length, rec2->length);
diff --git a/usr.bin/sort/sort.1 b/usr.bin/sort/sort.1
index aab96e293a1..c208019981b 100644
--- a/usr.bin/sort/sort.1
+++ b/usr.bin/sort/sort.1
@@ -1,4 +1,4 @@
-.\"	$OpenBSD: sort.1,v 1.29 2007/05/31 19:20:16 jmc Exp $
+.\"	$OpenBSD: sort.1,v 1.30 2007/08/21 20:29:25 millert Exp $
 .\"
 .\" Copyright (c) 1991, 1993
 .\"	The Regents of the University of California.  All rights reserved.
@@ -32,7 +32,7 @@
 .\"
 .\"     @(#)sort.1	8.1 (Berkeley) 6/6/93
 .\"
-.Dd $Mdocdate: May 31 2007 $
+.Dd $Mdocdate: August 21 2007 $
 .Dt SORT 1
 .Os
 .Sh NAME
@@ -40,7 +40,7 @@
 .Nd sort or merge text files
 .Sh SYNOPSIS
 .Nm sort
-.Op Fl bcdfHimnruz
+.Op Fl bcdfHimnrsuz
 .Sm off
 .Op Fl k\ \& Ar field1 Op , Ar field2
 .Sm on
@@ -136,6 +136,8 @@ option no longer implies the
 option.)
 .It Fl r
 Reverse the sense of comparisons.
+.It Fl s
+Enable stable sort. Use additional resources (see sradixsort(3)).
 .El
 .Pp
 The treatment of field separators can be altered using these options:
diff --git a/usr.bin/sort/sort.c b/usr.bin/sort/sort.c
index 5205c2304d7..14eb496e524 100644
--- a/usr.bin/sort/sort.c
+++ b/usr.bin/sort/sort.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: sort.c,v 1.34 2007/03/13 17:33:58 millert Exp $	*/
+/*	$OpenBSD: sort.c,v 1.35 2007/08/21 20:29:25 millert Exp $	*/
 
 /*-
  * Copyright (c) 1993
@@ -42,7 +42,7 @@ static char copyright[] =
 #if 0
 static char sccsid[] = "@(#)sort.c	8.1 (Berkeley) 6/6/93";
 #else
-static char rcsid[] = "$OpenBSD: sort.c,v 1.34 2007/03/13 17:33:58 millert Exp $";
+static char rcsid[] = "$OpenBSD: sort.c,v 1.35 2007/08/21 20:29:25 millert Exp $";
 #endif
 #endif /* not lint */
 
@@ -80,7 +80,7 @@ u_char ascii[NBINS], Rascii[NBINS], RFtable[NBINS], Ftable[NBINS];
  * masks of ignored characters.  Alltable is 256 ones
  */
 u_char dtable[NBINS], itable[NBINS], alltable[NBINS];
-int SINGL_FLD = 0, SEP_FLAG = 0, UNIQUE = 0;
+int SINGL_FLD = 0, SEP_FLAG = 0, UNIQUE = 0, STABLE = 0;
 struct coldesc *clist;
 int ncols = 0;
 int ND = 10;			/* limit on number of -k options. */
@@ -125,7 +125,7 @@ main(int argc, char *argv[])
 	fixit(&argc, argv);
 	if (!issetugid() && (outfile = getenv("TMPDIR")))
 		tmpdir = outfile;
-	while ((ch = getopt(argc, argv, "bcdfik:mHno:rR:t:T:uy:z")) != -1) {
+	while ((ch = getopt(argc, argv, "bcdfik:mHno:rR:t:T:uy:zs")) != -1) {
 		switch (ch) {
 		case 'b': fldtab->flags |= BI | BT;
 			break;
@@ -192,6 +192,9 @@ main(int argc, char *argv[])
 			d_mask['\n'] = d_mask[' '];
 			d_mask[REC_D] = REC_D_F;
 			break;
+		case 's':
+			STABLE = 1;
+			break;
 		case '?':
 		default:
 			usage(NULL);
@@ -340,7 +343,7 @@ usage(char *msg)
 
 	if (msg != NULL)
 		warnx("%s", msg);
-	(void)fprintf(stderr, "usage: %s [-bcdfHimnruz] "
+	(void)fprintf(stderr, "usage: %s [-bcdfHimnruzs] "
 	    "[-k field1[,field2]] [-o output] [-R char]\n"
 	    "\t[-T dir] [-t char] [file ...]\n", __progname);
 	exit(2);
diff --git a/usr.bin/sort/sort.h b/usr.bin/sort/sort.h
index 7664ce627a6..59baea59d50 100644
--- a/usr.bin/sort/sort.h
+++ b/usr.bin/sort/sort.h
@@ -1,4 +1,4 @@
-/*	$OpenBSD: sort.h,v 1.6 2003/06/03 02:56:16 millert Exp $	*/
+/*	$OpenBSD: sort.h,v 1.7 2007/08/21 20:29:25 millert Exp $	*/
 
 /*-
  * Copyright (c) 1993
@@ -133,7 +133,7 @@ extern int PANIC;	/* maximum depth of fsort before fmerge is called */
 extern u_char ascii[NBINS], Rascii[NBINS], Ftable[NBINS], RFtable[NBINS];
 extern u_char alltable[NBINS], dtable[NBINS], itable[NBINS];
 extern u_char d_mask[NBINS];
-extern int SINGL_FLD, SEP_FLAG, UNIQUE;
+extern int SINGL_FLD, SEP_FLAG, UNIQUE, STABLE;
 extern int REC_D;
 extern char *tmpdir;
 extern int ND;		/* limit on number of -k options. */