From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from smtp-out2.suse.de (smtp-out2.suse.de [IPv6:2001:67c:2178:6::1d]) by sourceware.org (Postfix) with ESMTPS id 48169385115F for ; Fri, 26 Aug 2022 18:24:09 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 48169385115F Authentication-Results: sourceware.org; dmarc=pass (p=none dis=none) header.from=suse.de Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=suse.de Received: from imap2.suse-dmz.suse.de (imap2.suse-dmz.suse.de [192.168.254.74]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature ECDSA (P-521) server-digest SHA512) (No client certificate requested) by smtp-out2.suse.de (Postfix) with ESMTPS id 6F9A01F385; Fri, 26 Aug 2022 18:24:08 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=suse.de; s=susede2_rsa; t=1661538248; h=from:from:reply-to:date:date:message-id:message-id:to:to:cc:cc: mime-version:mime-version:content-type:content-type: content-transfer-encoding:content-transfer-encoding: in-reply-to:in-reply-to:references:references; bh=3ki2VRsfS7l4wMC/p+8BTgObuTbKxa+kqXmZe5C3Tf8=; b=QC2LRwQ0QDa1UZUKqD5tdxeZK4PnEkSu/Pb+AdGP/eZFKpllprcafXi0Md8QL5LOJIuZNV FFVGSGpEmTWaVcQ99OfKK+P8KmsUcXlzb7koM0QCpUVZxzF2WF3GBnpflQ9JUIGoM1rEVP EsO3GnbAsZknvdjZCn3uxlgzcaEKAX0= DKIM-Signature: v=1; a=ed25519-sha256; c=relaxed/relaxed; d=suse.de; s=susede2_ed25519; t=1661538248; h=from:from:reply-to:date:date:message-id:message-id:to:to:cc:cc: mime-version:mime-version:content-type:content-type: content-transfer-encoding:content-transfer-encoding: in-reply-to:in-reply-to:references:references; bh=3ki2VRsfS7l4wMC/p+8BTgObuTbKxa+kqXmZe5C3Tf8=; b=4O6syeDsnNiZkou4E9GSWFgapmSVEVnR1Jd8CFM6+1yhLHHGAxvKgtO4Nw6N8Ei4pWyBpX GbAB9RFZxcgDYdAA== Received: from imap2.suse-dmz.suse.de (imap2.suse-dmz.suse.de [192.168.254.74]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature ECDSA (P-521) server-digest SHA512) (No client certificate requested) by imap2.suse-dmz.suse.de (Postfix) with ESMTPS id 6333513421; Fri, 26 Aug 2022 18:24:08 +0000 (UTC) Received: from dovecot-director2.suse.de ([192.168.254.65]) by imap2.suse-dmz.suse.de with ESMTPSA id yREzGMgPCWONGwAAMHmgww (envelope-from ); Fri, 26 Aug 2022 18:24:08 +0000 Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: quoted-printable From: Richard Biener Mime-Version: 1.0 (1.0) Subject: Re: [PATCH 2/2] vec: Add array_slice::bsearch Date: Fri, 26 Aug 2022 20:24:07 +0200 Message-Id: <97EB95B8-B901-4290-AA80-3116209F9EBC@suse.de> References: Cc: GCC Patches , Richard Sandiford In-Reply-To: To: Martin Jambor X-Mailer: iPhone Mail (19G82) X-Spam-Status: No, score=-11.7 required=5.0 tests=BAYES_00,DKIM_SIGNED,DKIM_VALID,DKIM_VALID_AU,DKIM_VALID_EF,GIT_PATCH_0,SPF_HELO_NONE,SPF_PASS,TXREP,T_SCC_BODY_TEXT_LINE autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on server2.sourceware.org List-Id: > Am 26.08.2022 um 18:40 schrieb Martin Jambor : >=20 > =EF=BB=BFHi, >=20 > This adds a method to binary search in a sorted array_slice. >=20 > The implementation is direct copy of vec:bsearch. Moreover, to only > copy it once and not twice, I used const_cast in the non-const > variants to be able to use the const variants. I hope that is > acceptable abuse of const_cast but I'll be happy to change that if > not. >=20 > Bootstrapped and tested along code that actually uses it on > x86_64-linux. OK for trunk? Can you avoid the copying by using array slice bsearch from the vec<> bsearc= h? > Thanks, >=20 > Martin >=20 >=20 > gcc/ChangeLog: >=20 > 2022-08-08 Martin Jambor >=20 > * vec.h (array_slice::bsearch): New methods. > --- > gcc/vec.h | 94 +++++++++++++++++++++++++++++++++++++++++++++++++++++++ > 1 file changed, 94 insertions(+) >=20 > diff --git a/gcc/vec.h b/gcc/vec.h > index b0477e1044c..61ebdc4ca13 100644 > --- a/gcc/vec.h > +++ b/gcc/vec.h > @@ -2301,6 +2301,14 @@ public: > // True if the array is valid, false if it is an array like INVALID. > bool is_valid () const { return m_base || m_size =3D=3D 0; } >=20 > + /* Methods for binary search in sorted array_slice. */ > + const T *bsearch (const void *key, int (*compar)(const void *, > + const void *)) const; > + T *bsearch (const void *key, int (*compar)(const void *, const void *))= ; > + const T *bsearch (const void *key, > + int (*compar)(const void *, const void *, void *), void *) cons= t; > + T *bsearch (const void *key, > + int (*compar)(const void *, const void *, void *), void *); > private: > iterator m_base; > unsigned int m_size; > @@ -2361,6 +2369,92 @@ make_array_slice (T *base, unsigned int size) > return array_slice (base, size); > } >=20 > +/* Search the contents of the sorted array_slice with a binary search. C= MP is > + the comparison function to pass to bsearch. */ > + > +template > +inline const T * > +array_slice::bsearch (const void *key, > + int (*compar) (const void *, const void *)) const > +{ > + const void *base =3D this->m_base; > + size_t nmemb =3D this->size (); > + size_t size =3D sizeof (T); > + /* The following is a copy of glibc stdlib-bsearch.h. */ > + size_t l, u, idx; > + const void *p; > + int comparison; > + > + l =3D 0; > + u =3D nmemb; > + while (l < u) > + { > + idx =3D (l + u) / 2; > + p =3D (const void *) (((const char *) base) + (idx * size)); > + comparison =3D (*compar) (key, p); > + if (comparison < 0) > + u =3D idx; > + else if (comparison > 0) > + l =3D idx + 1; > + else > + return (T *)const_cast(p); > + } > + > + return NULL; > +} > + > +template > +inline T * > +array_slice::bsearch (const void *key, > + int (*compar) (const void *, const void *)) > +{ > + return const_cast(bsearch (key, compar)); > +} > + > +/* Search the contents of the sorted array_slice with a binary search. C= MP is > + the comparison function to pass to bsearch. */ > + > +template > +inline const T * > +array_slice::bsearch (const void *key, > + int (*compar) (const void *, const void *, void *), > + void *data) const > +{ > + const void *base =3D this->m_base; > + size_t nmemb =3D this->size (); > + size_t size =3D sizeof (T); > + /* The following is a copy of glibc stdlib-bsearch.h. */ > + size_t l, u, idx; > + const void *p; > + int comparison; > + > + l =3D 0; > + u =3D nmemb; > + while (l < u) > + { > + idx =3D (l + u) / 2; > + p =3D (const void *) (((const char *) base) + (idx * size)); > + comparison =3D (*compar) (key, p, data); > + if (comparison < 0) > + u =3D idx; > + else if (comparison > 0) > + l =3D idx + 1; > + else > + return (T *)const_cast(p); > + } > + > + return NULL; > +} > + > +template > +inline T * > +array_slice::bsearch (const void *key, > + int (*compar) (const void *, const void *, void *), > + void *data) > +{ > + return const_cast (bsearch (key, compar, data)); > +} > + > #if (GCC_VERSION >=3D 3000) > # pragma GCC poison m_vec m_vecpfx m_vecdata > #endif > --=20 > 2.37.2 >=20