From patchwork Thu Dec 11 10:33:22 2014 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Anders Kaseorg X-Patchwork-Id: 4172 Received: (qmail 32090 invoked by alias); 11 Dec 2014 10:33:30 -0000 Mailing-List: contact libc-alpha-help@sourceware.org; run by ezmlm Precedence: bulk List-Id: List-Unsubscribe: List-Subscribe: List-Archive: List-Post: List-Help: , Sender: libc-alpha-owner@sourceware.org Delivered-To: mailing list libc-alpha@sourceware.org Received: (qmail 32017 invoked by uid 89); 11 Dec 2014 10:33:30 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-1.1 required=5.0 tests=AWL, BAYES_00, SPF_PASS, T_RP_MATCHES_RCVD autolearn=ham version=3.3.2 X-HELO: dmz-mailsec-scanner-8.mit.edu Date: Thu, 11 Dec 2014 05:33:22 -0500 (EST) From: Anders Kaseorg To: Florian Weimer cc: Andreas Schwab , Paul Eggert , =?UTF-8?Q?Ond=C5=99ej_B=C3=ADlka?= , libc-alpha@sourceware.org Subject: [PATCH v2] manual: Correct guarantee about pointers compared by qsort() Message-ID: User-Agent: Alpine 2.10 (DEB 1266 2009-07-14) MIME-Version: 1.0 C99, C11, POSIX, and the glibc implementation do guarantee that the pointers passed to the qsort comparison function lie within the array. (Also, fix a small typographical mistake: @var{qsort} should be @code{qsort}.) Signed-off-by: Anders Kaseorg Reviewed-by: Jonathan Nieder --- manual/search.texi | 14 ++++++++------ 1 file changed, 8 insertions(+), 6 deletions(-) diff --git a/manual/search.texi b/manual/search.texi index 8aff574..662527f 100644 --- a/manual/search.texi +++ b/manual/search.texi @@ -164,8 +164,8 @@ To sort an array using an arbitrary comparison function, use the @comment ISO @deftypefun void qsort (void *@var{array}, size_t @var{count}, size_t @var{size}, comparison_fn_t @var{compare}) @safety{@prelim{}@mtsafe{}@assafe{}@acunsafe{@acucorrupt{}}} -The @var{qsort} function sorts the array @var{array}. The array contains -@var{count} elements, each of which is of size @var{size}. +The @code{qsort} function sorts the array @var{array}. The array +contains @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 @@ -180,10 +180,12 @@ This can make a difference when the comparison considers only part of the elements. Two elements with the same sort key may differ in other respects. -The addresses passed to the comparison function need not correspond with -the original location of the objects, and need not even lie within the -original array. The only way to perform a stable sort with @var{qsort} -is to first augment the objects with a monotonic counter of some kind. +Although the object addresses passed to the comparison function lie +within the array, they need not correspond with the original locations +of those objects because the sorting algorithm may swap around objects +in the array before making some comparisons. The only way to perform +a stable sort with @code{qsort} is to first augment the objects with a +monotonic counter of some kind. Here is a simple example of sorting an array of doubles in numerical order, using the comparison function defined above (@pxref{Comparison