From patchwork Wed Dec 10 15:49:09 2014 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: =?utf-8?b?T25kxZllaiBCw61sa2E=?= X-Patchwork-Id: 419718 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Received: from sourceware.org (server1.sourceware.org [209.132.180.131]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by ozlabs.org (Postfix) with ESMTPS id 2F4581400EA for ; Thu, 11 Dec 2014 02:49:53 +1100 (AEDT) DomainKey-Signature: a=rsa-sha1; c=nofws; d=sourceware.org; h=list-id :list-unsubscribe:list-subscribe:list-archive:list-post :list-help:sender:date:from:to:cc:subject:message-id:references :mime-version:content-type:content-transfer-encoding :in-reply-to; q=dns; s=default; b=GLD3Ky5sE1kWTXFIsMC56qTaWqGMw2 6sGOLanXbMrs78u4L68TOJsmyr3sz4UFR4JlY+gSxnEETFR3YJTrMJm6Mn6TwspZ Ps9U/6IP9svmTDClTDGzr4xipLN+eMdCocNp6ajjXpYAC5uEIBXoKPVQURd6CXS4 VO2HCcpL7H5js= DKIM-Signature: v=1; a=rsa-sha1; c=relaxed; d=sourceware.org; h=list-id :list-unsubscribe:list-subscribe:list-archive:list-post :list-help:sender:date:from:to:cc:subject:message-id:references :mime-version:content-type:content-transfer-encoding :in-reply-to; s=default; bh=FpC4elhh9nA/9fZ8M6ABCZpp/q0=; b=er9c nwNOPXQYk7ZxQi4uWToypRl15Vv6yIDWIuYTCy14ohd5OESGjYrIM0YAeA0PElt8 NNxcaiU4NAQU+S6PzDpXL18qB4e+jtllRMfintTjpjVrN3p9RT3IlFCNL/zUHL8t rra8YrMVDV8lSF0Kja1mjk7ZcbOABWB5ynOKV64= Received: (qmail 12469 invoked by alias); 10 Dec 2014 15:49:48 -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 12460 invoked by uid 89); 10 Dec 2014 15:49:47 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=0.3 required=5.0 tests=AWL, BAYES_00, CLAIM_SUBJECT, FREEMAIL_FROM, SPF_NEUTRAL autolearn=no version=3.3.2 X-HELO: popelka.ms.mff.cuni.cz Date: Wed, 10 Dec 2014 16:49:09 +0100 From: =?utf-8?B?T25kxZllaiBCw61sa2E=?= To: Anders Kaseorg Cc: Florian Weimer , libc-alpha@sourceware.org Subject: [COMMITED][v2] manual: Remove incorrect claim that qsort() can be stabilized Message-ID: <20141210154909.GA31968@domone> References: MIME-Version: 1.0 Content-Disposition: inline In-Reply-To: User-Agent: Mutt/1.5.20 (2009-06-14) On Wed, Jul 02, 2014 at 09:17:50PM -0400, Anders Kaseorg wrote: > Under certain conditions on the size of the array and its items, > qsort() may fall back to an in-place quicksort if it cannot allocate > memory for a temporary array with malloc(). This algorithm is not a > stable sort even if the comparison function is written in the > described manner. > > Fixes #10672. > > Signed-off-by: Anders Kaseorg > > --- > On Tue, 1 Jul 2014, Florian Weimer wrote: > > I would suggest to remove the entire paragraph instead, or perhaps a warning > > that the pointers with which the comparison function is called do not > > necessarily have to reside within the input array. > > What do you think about this wording, then? (The problem is not actually > about pointers residing outside the input array, because it happens that > the algorithm where that occurs is stable. But I agree it’s worth > mentioning too.) > As it looks ok now I commited it with changelog and NEWS entry. diff --git a/ChangeLog b/ChangeLog index c2d99a0..bf140d3 100644 --- a/ChangeLog +++ b/ChangeLog @@ -1,3 +1,9 @@ +2014-12-10 Anders Kaseorg + + [BZ #10672] + * manual/search.texi: (Array Sort Function): Remove claim how make + qsort stable. + 2014-12-10 Andreas Schwab [BZ #12847] diff --git a/NEWS b/NEWS index 7b32c03..4235d37 100644 --- a/NEWS +++ b/NEWS @@ -9,12 +9,12 @@ Version 2.21 * The following bugs are resolved with this release: - 6652, 12847, 12926, 13862, 14132, 14138, 14171, 14498, 15215, 15884, - 16469, 16619, 16740, 16857, 17192, 17266, 17344, 17363, 17370, 17371, - 17411, 17460, 17475, 17485, 17501, 17506, 17508, 17522, 17555, 17570, - 17571, 17572, 17573, 17574, 17581, 17582, 17583, 17584, 17585, 17589, - 17594, 17601, 17608, 17616, 17625, 17633, 17647, 17653, 17664, 17665, - 17668, 17682. + 6652, 10672, 12847, 12926, 13862, 14132, 14138, 14171, 14498, 15215, + 15884, 16469, 16619, 16740, 16857, 17192, 17266, 17344, 17363, 17370, + 17371, 17411, 17460, 17475, 17485, 17501, 17506, 17508, 17522, 17555, + 17570, 17571, 17572, 17573, 17574, 17581, 17582, 17583, 17584, 17585, + 17589, 17594, 17601, 17608, 17616, 17625, 17633, 17647, 17653, 17664, + 17665, 17668, 17682. * CVE-2104-7817 The wordexp function could ignore the WRDE_NOCMD flag under certain input conditions resulting in the execution of a shell for diff --git a/manual/search.texi b/manual/search.texi index 509a543..8aff574 100644 --- a/manual/search.texi +++ b/manual/search.texi @@ -180,11 +180,10 @@ 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. -If you want the effect of a stable sort, you can get this result by -writing the comparison function so that, lacking other reason -distinguish between two elements, it compares them by their addresses. -Note that doing this may make the sorting algorithm less efficient, so -do it only if necessary. +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. Here is a simple example of sorting an array of doubles in numerical order, using the comparison function defined above (@pxref{Comparison