From mboxrd@z Thu Jan 1 00:00:00 1970 X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on inbox.vuxu.org X-Spam-Level: X-Spam-Status: No, score=-3.4 required=5.0 tests=DKIM_SIGNED,DKIM_VALID, DKIM_VALID_AU,MAILING_LIST_MULTI,RCVD_IN_DNSWL_MED,RCVD_IN_MSPIKE_H3, RCVD_IN_MSPIKE_WL autolearn=ham autolearn_force=no version=3.4.4 Received: (qmail 20316 invoked from network); 8 Aug 2021 20:39:25 -0000 Received: from mother.openwall.net (195.42.179.200) by inbox.vuxu.org with ESMTPUTF8; 8 Aug 2021 20:39:25 -0000 Received: (qmail 9882 invoked by uid 550); 8 Aug 2021 20:39:24 -0000 Mailing-List: contact musl-help@lists.openwall.com; run by ezmlm Precedence: bulk List-Post: List-Help: List-Unsubscribe: List-Subscribe: List-ID: Reply-To: musl@lists.openwall.com Received: (qmail 9864 invoked from network); 8 Aug 2021 20:39:23 -0000 X-Virus-Scanned: Debian amavisd-new at disroot.org Mime-Version: 1.0 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=disroot.org; s=mail; t=1628455151; bh=boarhR7vrow6IQsdTYXi/0Ff+eTyT8QbxxTJMPLRBmM=; h=Cc:Subject:From:To:Date:In-Reply-To; b=K28zcfvulEchCtF2IEsh6N4ejKdGF4+sK/u2islQmdxFznC3eciBsUd6/RvEDil8f Q5CgcwgWfZ2gpXJ+JERP4nULkvfSYr2tkqhNmFuNVUbrqujTCFpi+GDhGMijuNn+cl Jfw4buqaLMl37WckYR4YHfp1uLmhFDf/osUNi9uBUMVq51I6UeswcUBBNqt+Qq58rS fr4SqlsrUikapncjPcsKCo2BedUO0X9K96fJTGoXz0/t+NBnlsI4PbD3gEKNHTC9F4 geZE00M+YiWl9ltJY6f3BaF0vpdHKwP1Cg4CEm2BHWAOe/9+j8r9nZLGWFEJeA9E97 GiXDd2sHE5/mQ== Content-Transfer-Encoding: quoted-printable Content-Type: text/plain; charset=UTF-8 Cc: "Olivier Galibert" From: =?utf-8?q?=C3=89rico_Nogueira?= To: Date: Sun, 08 Aug 2021 17:35:51 -0300 Message-Id: In-Reply-To: Subject: Re: [musl] [PATCH] stdlib: implement qsort_r On Sun Aug 8, 2021 at 9:42 AM -03, Jon Chesterfield wrote: > On Sun, Aug 8, 2021 at 12:29 PM Olivier Galibert > wrote: > > > The extension qsort_r allows calling qsort on a list of indices > > without having a global variable to hold the data to sort. > > > > qsort_r is a strong improvement on qsort. I think it's available outside > of > glibc. > > I remember doing something similar locally. Just looked it up and I > renamed & mutated qsort to pass the context along. Therefore typed into > email, I think something like this would provide an implementation of > qsort in terms of qsort_r. > > // declare qsort_r > typedef int (*cmp_r_t)(const void *, const void *, void * context); > > > void qsort_r(void *base, size_t nel, size_t width, cmp_r_t cmp, void* > context); > > > // pass it a function that extracts the comparator for qsort from the > // context > typedef int (*cmp_t)(const void *, const void *); > > > static int compare_adapter(const void *l, const void *r, void * context) > { > cmpt_t c =3D (cmpt_t) context; > > > return c(l,r); > > > } > > // tail call > void qsort(void *base, size_t nel, size_t width, cmp_t c) > { > return qsort_r(base, nel, width, compare_adapter, (cmp_t_t)c); > > > } > > Given optimism about inlining or an always inline annotation > it should turn into the same machine code as the macro > instantiation approach. Alternatively it's a tail call into qsort_r, so > a couple of indirections in exchange for minimal code size growth. > > I haven't compiled or tested that (or looked up the coding conventions > for musl) so this is a drive by suggestion, written in pseudocode > instead of prose for clarity. This is the favored approach, from what I understood of the discussions surrounding it. It's implemented with musl's namespacing rules and such in [1]. It is badly optimized for some archs, unfortunately, as explained in the thread from [2]. I believe that's what's holding it up. [1] https://inbox.vuxu.org/musl/20210309210213.29539-1-ericonr@disroot.org/ [2] https://inbox.vuxu.org/musl/20210309150320.GU32655@brightrain.aerifal.c= x/ > > Thanks all! > > Jon