From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from smtp-out1.suse.de (smtp-out1.suse.de [IPv6:2001:67c:2178:6::1c]) by sourceware.org (Postfix) with ESMTPS id 50AF2384F015 for ; Fri, 26 Aug 2022 20:32:41 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 50AF2384F015 Authentication-Results: sourceware.org; dmarc=none (p=none dis=none) header.from=suse.cz Authentication-Results: sourceware.org; spf=fail smtp.mailfrom=suse.cz 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-out1.suse.de (Postfix) with ESMTPS id A8EF5336AD; Fri, 26 Aug 2022 20:32:39 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=suse.cz; s=susede2_rsa; t=1661545959; 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=KZsHFUmCCAqSublwKTO2+KwVR0ERtqaqBt8Oo0HMYPo=; b=yzLsWGn8HP/gxvvs7UZacrchOgHMbmM2e5FBBXVmmcN3E6cOu+JawbmEsKF6+u/XrUz3l6 Z9GvG8vDofKnW//dddIp7ME2RAMfru9I+/od/cAmSNjz9OYuhqwSUZ24Sy1fRZp2BMArMQ u5uMqXlehuFFIatwbz3CR4LzqFYdqSo= DKIM-Signature: v=1; a=ed25519-sha256; c=relaxed/relaxed; d=suse.cz; s=susede2_ed25519; t=1661545959; 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=KZsHFUmCCAqSublwKTO2+KwVR0ERtqaqBt8Oo0HMYPo=; b=uzqKprYcK6mtN6Q4XeG2U5yM6t4T53eI8ifDUiW/tn17PLMueeT96UDlSGg59KR2TkGKxE iPxliQKnhi7YKiAA== 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 96D0913421; Fri, 26 Aug 2022 20:32:39 +0000 (UTC) Received: from dovecot-director2.suse.de ([192.168.254.65]) by imap2.suse-dmz.suse.de with ESMTPSA id 8SaMJOctCWPoQQAAMHmgww (envelope-from ); Fri, 26 Aug 2022 20:32:39 +0000 From: Martin Jambor To: Richard Biener Cc: GCC Patches , Richard Sandiford Subject: Re: [PATCH 2/2] vec: Add array_slice::bsearch In-Reply-To: <97EB95B8-B901-4290-AA80-3116209F9EBC@suse.de> References: <97EB95B8-B901-4290-AA80-3116209F9EBC@suse.de> User-Agent: Notmuch/0.35 (https://notmuchmail.org) Emacs/28.1 (x86_64-suse-linux-gnu) Date: Fri, 26 Aug 2022 22:32:39 +0200 Message-ID: MIME-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: quoted-printable X-Spam-Status: No, score=-11.6 required=5.0 tests=BAYES_00,DKIM_SIGNED,DKIM_VALID,DKIM_VALID_AU,DKIM_VALID_EF,GIT_PATCH_0,SPF_HELO_NONE,SPF_SOFTFAIL,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: Hi, On Fri, Aug 26 2022, Richard Biener wrote: >> 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<> bse= arch? I would be easy to just move the implementation to array_slice and then implement vec<...>::bsearch by calling into that. But I still think I need more constructors for that ;-) 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 *) co= nst; >> + 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. = CMP 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. = CMP 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