From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 22074 invoked by alias); 11 May 2018 10:29:11 -0000 Mailing-List: contact gcc-patches-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Id: List-Archive: List-Post: List-Help: Sender: gcc-patches-owner@gcc.gnu.org Received: (qmail 21706 invoked by uid 89); 11 May 2018 10:29:10 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-6.6 required=5.0 tests=AWL,BAYES_00,GIT_PATCH_1,RCVD_IN_DNSWL_NONE autolearn=ham version=3.3.2 spammy=Hx-languages-length:1392, contract X-HELO: gate.crashing.org Received: from gate.crashing.org (HELO gate.crashing.org) (63.228.1.57) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with ESMTP; Fri, 11 May 2018 10:29:09 +0000 Received: from gate.crashing.org (localhost.localdomain [127.0.0.1]) by gate.crashing.org (8.14.1/8.14.1) with ESMTP id w4BAT6jr006801; Fri, 11 May 2018 05:29:06 -0500 Received: (from segher@localhost) by gate.crashing.org (8.14.1/8.14.1/Submit) id w4BAT5HQ006797; Fri, 11 May 2018 05:29:05 -0500 Date: Fri, 11 May 2018 10:35:00 -0000 From: Segher Boessenkool To: Richard Biener Cc: gcc-patches@gcc.gnu.org, Alexander Monakov Subject: Re: [PATCH 0/2] Introduce gcc_qsort Message-ID: <20180511102905.GC17342@gate.crashing.org> References: <20180510155641.2950-1-amonakov@ispras.ru> <82E69EBE-92EB-41AB-8E1B-ADBD65516D73@gmail.com> Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <82E69EBE-92EB-41AB-8E1B-ADBD65516D73@gmail.com> User-Agent: Mutt/1.4.2.3i X-IsSubscribed: yes X-SW-Source: 2018-05/txt/msg00546.txt.bz2 On Thu, May 10, 2018 at 07:40:57PM +0200, Richard Biener wrote: > On May 10, 2018 5:56:39 PM GMT+02:00, Alexander Monakov wrote: > >/* This implements a sort function suitable for GCC use cases: > > - signature-compatible to C qsort, but relaxed contract: > > - may apply the comparator to elements in a temporary buffer > > What consequences has this or rather how is this observable and makes comparators behave differently? A comparison function is allowed to compare the addresses of the elements, or compute what should be the index into the array that is sorted from the pointers to the elements, etc. That will not work if the pointers to the elements do not actually point into the original array. For example from reload1.c: static int reload_reg_class_lower (const void *r1p, const void *r2p) { int r1 = *(const short *) r1p, r2 = *(const short *) r2p; // ... return r1 - r2; } (called as static short reload_order[MAX_RELOADS]; // ... qsort (reload_order, n_reloads, sizeof (short), reload_reg_class_lower); ). Such a comparator will still work with temporary arrays if both elements are always in the same temp array (in deterministic order, etc.) array; but it won't work if the comparator did e.g. return (r1 - reload_order) - (r2 - reload_order); (it would be undefined behaviour, to start with). Segher