NetBSD Problem Report #22182

Received: (qmail 3728 invoked by uid 605); 18 Jul 2003 16:51:51 -0000
Message-Id: <20030718165149.830264852@calamity.sis.pasteur.fr>
Date: Fri, 18 Jul 2003 18:51:49 +0200 (CEST)
From: njoly@pasteur.fr
Sender: gnats-bugs-owner@NetBSD.org
Reply-To: njoly@pasteur.fr
To: gnats-bugs@gnats.netbsd.org
Subject: sort(1) fields `rn' options may give incorrect results
X-Send-Pr-Version: 3.95

>Number:         22182
>Category:       bin
>Synopsis:       sort(1) fields options give incorrect results: -rn -k1 <> -k 1rn
>Confidential:   no
>Severity:       serious
>Priority:       low
>Responsible:    jdolecek
>State:          closed
>Class:          sw-bug
>Submitter-Id:   net
>Arrival-Date:   Fri Jul 18 16:52:00 +0000 2003
>Closed-Date:    Sat Aug 22 11:14:59 +0000 2009
>Last-Modified:  Wed Oct 14 20:45:06 +0000 2009
>Originator:     Nicolas Joly
>Release:        NetBSD 1.6U (Thu Jul 17 14:25:58 CEST 2003)
>Organization:
	Pasteur Institute, Paris.
>Environment:
System: NetBSD calamity.sis.pasteur.fr 1.6U NetBSD 1.6U (CALAMITY) #7: Wed Jul 9 23:44:31 CEST 2003 njoly@calamity.sis.pasteur.fr:/local/src/NetBSD/src/sys/arch/i386/compile/CALAMITY i386
Architecture: i386
Machine: i386
>Description:
	Using fields options may leads to incorrect results on sorting numbers
	By example (see below), sort -rn -k 1 and sort -k 1rn give different
	results.
>How-To-Repeat:
njoly@hal [~]> cat > xx 
1599
1501
1500
1499
1401
1400
njoly@hal [~]> sort -rn -k 1 xx
1599
1501
1500
1499
1401
1400
njoly@hal [~]> sort -k 1rn xx  
1500
1599
1501
1400
1499
1401
>Fix:
	N/A
>Release-Note:
>Audit-Trail:
Responsible-Changed-From-To: bin-bug-people->jdolecek 
Responsible-Changed-By: jdolecek 
Responsible-Changed-When: Fri Jul 18 18:08:59 UTC 2003 
Responsible-Changed-Why:  
sort(1) is mine 

From: Giles Lean <giles@nemeton.com.au>
To: njoly@pasteur.fr
Cc: gnats-bugs@gnats.netbsd.org
Subject: Re: bin/22182: sort(1) fields `rn' options may give incorrect results 
Date: Sat, 19 Jul 2003 14:20:27 +1000

 > Subject: bin/22182: sort(1) fields `rn' options may give incorrect results

 See also bin/20259 and ensuing discussion.  Peter Seebach made some
 progress troubleshooting that one.

 Giles

From: David Laight <dsl@netbsd.org>
To: gnats-bugs@gnats.NetBSD.org
Cc: 
Subject: PR/22182 CVS commit: src/usr.bin/sort
Date: Sat, 22 Aug 2009 10:53:29 +0000

 Module Name:	src
 Committed By:	dsl
 Date:		Sat Aug 22 10:53:28 UTC 2009

 Modified Files:
 	src/usr.bin/sort: append.c fields.c files.c fsort.c init.c msort.c
 	    sort.c sort.h

 Log Message:
 Rework the way sort generates sort keys:
 - If we generate a key, it is always sortable using memcmp()
 - If we are sorting the whole record, then a weight-table must be used
   during compares.
 - Major surgery to encoding of numbers to ensure unique keys for equal
   numeric values.  Reverse numerics are handled by inverting the sign.
 - Case folding (-f) is handled when the sort keys are generated. No other
   code has to care at all.
 - Key uniqueness (-u) is done during merge for large datasets. It only
   has to be done when writing the output file for small files.
   Since the file is in key order this is simple!
 Probably fixes all of: PR/27257 PR/25551 PR/22182 PR/31095 PR/30504
 PR/36816 PR/37860 PR/39308
 Also PR/18614 should no longer die, but a little more work needs to be
 done on the merging for very large files.


 To generate a diff of this commit:
 cvs rdiff -u -r1.19 -r1.20 src/usr.bin/sort/append.c src/usr.bin/sort/init.c
 cvs rdiff -u -r1.24 -r1.25 src/usr.bin/sort/fields.c src/usr.bin/sort/sort.h
 cvs rdiff -u -r1.34 -r1.35 src/usr.bin/sort/files.c
 cvs rdiff -u -r1.38 -r1.39 src/usr.bin/sort/fsort.c
 cvs rdiff -u -r1.22 -r1.23 src/usr.bin/sort/msort.c
 cvs rdiff -u -r1.51 -r1.52 src/usr.bin/sort/sort.c

 Please note that diffs are not public domain; they are subject to the
 copyright notices on the relevant files.

State-Changed-From-To: open->closed
State-Changed-By: dsl@NetBSD.org
State-Changed-When: Sat, 22 Aug 2009 11:14:59 +0000
State-Changed-Why:
fixed - see above


From: Stephen Borrill <sborrill@netbsd.org>
To: gnats-bugs@gnats.NetBSD.org
Cc: 
Subject: PR/22182 CVS commit: [netbsd-5] src/usr.bin/sort
Date: Wed, 14 Oct 2009 20:41:53 +0000

 Module Name:	src
 Committed By:	sborrill
 Date:		Wed Oct 14 20:41:53 UTC 2009

 Modified Files:
 	src/usr.bin/sort [netbsd-5]: Makefile append.c fields.c files.c fsort.c
 	    fsort.h init.c msort.c sort.1 sort.c sort.h tmp.c
 Added Files:
 	src/usr.bin/sort [netbsd-5]: radix_sort.c

 Log Message:
 Pull up the following revisions(s) (requested by dsl in ticket #1084):
 	usr.bin/sort/Makefile:	revision 1.6-1.8
 	usr.bin/sort/append.c:	revision 1.15-1.22
 	usr.bin/sort/fields.c:	revision 1.20-1.30
 	usr.bin/sort/files.c:	revision 1.27-1.40
 	usr.bin/sort/fsort.c:	revision 1.33-1.45
 	usr.bin/sort/fsort.h:	revision 1.14-1.17
 	usr.bin/sort/init.c:	revision 1.19-1.23
 	usr.bin/sort/msort.c:	revision 1.19-1.28
 	usr.bin/sort/radix_sort.c:	revision 1.1-1.4
 	usr.bin/sort/sort.1:	revision 1.27-1.29
 	usr.bin/sort/sort.c:	revision 1.47-1.56
 	usr.bin/sort/sort.h:	revision 1.20-1.30
 	usr.bin/sort/tmp.c:	revision 1.14-1.15

 Only use radix sort for in-memory sort, always merge temporary files.
 Use a local radixsort() function so we can pass record length.
 Avoid use of weight tables for key compares.
 Fix generation of keys for numbers, negate value for reverse sort.
 Write file in reverse-key order for 'sort -n'.
 'sort -S' now does a posix sort (sort matching keys by record data).
 Ensure merge sort doesn't have too many temporary files open.
 Fixes: PR#18614 PR#27257 PR#25551 PR#22182 PR#31095 PR#30504 PR#36816
 PR#37860 PR#39308 PR#42094


 To generate a diff of this commit:
 cvs rdiff -u -r1.5 -r1.5.40.1 src/usr.bin/sort/Makefile
 cvs rdiff -u -r1.14 -r1.14.6.1 src/usr.bin/sort/append.c
 cvs rdiff -u -r1.19 -r1.19.6.1 src/usr.bin/sort/fields.c \
     src/usr.bin/sort/sort.h
 cvs rdiff -u -r1.26 -r1.26.6.1 src/usr.bin/sort/files.c \
     src/usr.bin/sort/sort.1
 cvs rdiff -u -r1.32 -r1.32.6.1 src/usr.bin/sort/fsort.c
 cvs rdiff -u -r1.13 -r1.13.6.1 src/usr.bin/sort/fsort.h \
     src/usr.bin/sort/tmp.c
 cvs rdiff -u -r1.18 -r1.18.6.1 src/usr.bin/sort/init.c \
     src/usr.bin/sort/msort.c
 cvs rdiff -u -r0 -r1.4.2.2 src/usr.bin/sort/radix_sort.c
 cvs rdiff -u -r1.46 -r1.46.4.1 src/usr.bin/sort/sort.c

 Please note that diffs are not public domain; they are subject to the
 copyright notices on the relevant files.

>Unformatted:

Home	PR Database Search