Re: memcpy-optimized version of qsort.

[Paul Eggert <eggert at CS dot UCLA dot EDU>]

Wolfgang Glas <wolfgang.glas@ev-i.at> writes:

> 3) merge tmp and b+n1 into b.

But the C Standard requires that qsort's comparison function be passed
pointers into the original array, not into a temporary copy like 'tmp'.

This issue has come up before, so it's worth documenting.  Here's a
proposed patch to the glibc documentation that documents the standard
restrictions on qsort and bsearch.  While drafting this patch I
noticed that the documentation's sample comparison function violates
these newly-documented restrictions so I fixed that too.

2004-06-07  Paul Eggert  <eggert@cs.ucla.edu>

	* manual/search.texi (Comparison Functions): Fix bug in example
	code: the comparison function based on 'double' was not a total
	order for IEEE floating point because of NaNs, and this violates
	the C Standard.  Switch to 'int' instead, to keep it simple.  All
	uses changed.
	(Array Search Function): Mention that the first argument to the
	comparison function will be the key and the second an array element.
	(Array Sort Function): Mention that arguments to the comparison
	function will point to array elements.
	(Array Search Function, Array Sort Function): Mention that the
	function must not modify the array, and the function must be consistent.

Index: manual/search.texi
===================================================================
RCS file: /cvs/glibc/libc/manual/search.texi,v
retrieving revision 1.36
diff -p -u -r1.36 search.texi
--- manual/search.texi	11 Oct 2002 10:50:55 -0000	1.36
+++ manual/search.texi	7 Jun 2004 19:25:08 -0000
@@ -35,16 +35,17 @@ second, zero if they are ``equal'', and 
 is ``greater''.
 
 Here is an example of a comparison function which works with an array of
-numbers of type @code{double}:
+numbers of type @code{int}:
 
 @smallexample
 int
-compare_doubles (const void *a, const void *b)
+compare_ints (const void *a, const void *b)
 @{
-  const double *da = (const double *) a;
-  const double *db = (const double *) b;
+  const int *ia = (const int *) a;
+  const int *ib = (const int *) b;
 
-  return (*da > *db) - (*da < *db);
+  /* (*ia - *ib) might overflow, so:  */
+  return (*ia > *ib) - (*ia < *ib);
 @}
 @end smallexample
 
@@ -118,11 +119,16 @@ that is equivalent to @var{key}.  The ar
 each of which is of size @var{size} bytes.
 
 The @var{compare} function is used to perform the comparison.  This
-function is called with two pointer arguments and should return an
+function is called with two pointer arguments
+(@var{key} and a pointer to an array element, respectively)
+and should return an
 integer less than, equal to, or greater than zero corresponding to
 whether its first argument is considered less than, equal to, or greater
 than its second argument.  The elements of the @var{array} must already
 be sorted in ascending order according to this comparison function.
+The comparison function should not modify the contents of the array,
+and should define a consistent ordering so that the same object always
+compares the same way with the key.
 
 The return value is a pointer to the matching array element, or a null
 pointer if no match is found.  If the array contains more than one element
@@ -150,10 +156,13 @@ The @var{qsort} function sorts the array
 @var{count} elements, each of which is of size @var{size}.
 
 The @var{compare} function is used to perform the comparison on the
-array elements.  This function is called with two pointer arguments and
+array elements.  This function is called with two arguments that
+point to elements in the array, and
 should return an integer less than, equal to, or greater than zero
 corresponding to whether its first argument is considered less than,
-equal to, or greater than its second argument.
+equal to, or greater than its second argument.  The comparison
+function should not modify the contents of the array, and should
+define a consistent total ordering on the array elements.
 
 @cindex stable sorting
 @strong{Warning:} If two objects compare as equal, their order after
@@ -168,16 +177,16 @@ distinguish between two elements, it com
 Note that doing this may make the sorting algorithm less efficient, so
 do it only if necessary.
 
-Here is a simple example of sorting an array of doubles in numerical
+Here is a simple example of sorting an array of @code{int}s in numerical
 order, using the comparison function defined above (@pxref{Comparison
 Functions}):
 
 @smallexample
 @{
-  double *array;
+  int *array;
   int size;
   @dots{}
-  qsort (array, size, sizeof (double), compare_doubles);
+  qsort (array, size, sizeof (int), compare_ints);
 @}
 @end smallexample