From patchwork Fri Aug 26 16:38:47 2022 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Martin Jambor X-Patchwork-Id: 1670940 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@legolas.ozlabs.org Authentication-Results: legolas.ozlabs.org; spf=pass (sender SPF authorized) smtp.mailfrom=gcc.gnu.org (client-ip=8.43.85.97; helo=sourceware.org; envelope-from=gcc-patches-bounces+incoming=patchwork.ozlabs.org@gcc.gnu.org; receiver=) Authentication-Results: legolas.ozlabs.org; dkim=fail reason="signature verification failed" (1024-bit key; unprotected) header.d=suse.cz header.i=@suse.cz header.a=rsa-sha256 header.s=susede2_rsa header.b=JXLqR17P; dkim=fail reason="signature verification failed" header.d=suse.cz header.i=@suse.cz header.a=ed25519-sha256 header.s=susede2_ed25519 header.b=t3MbTCq3; dkim-atps=neutral Received: from sourceware.org (ip-8-43-85-97.sourceware.org [8.43.85.97]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature ECDSA (P-384) server-digest SHA384) (No client certificate requested) by legolas.ozlabs.org (Postfix) with ESMTPS id 4MDlsL40HBz1yhT for ; Sat, 27 Aug 2022 02:39:02 +1000 (AEST) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id DA3E63850860 for ; Fri, 26 Aug 2022 16:38:59 +0000 (GMT) X-Original-To: gcc-patches@gcc.gnu.org Delivered-To: gcc-patches@gcc.gnu.org Received: from smtp-out2.suse.de (smtp-out2.suse.de [195.135.220.29]) by sourceware.org (Postfix) with ESMTPS id BCBE138515FD for ; Fri, 26 Aug 2022 16:38:48 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org BCBE138515FD Authentication-Results: sourceware.org; dmarc=none (p=none dis=none) header.from=suse.cz Authentication-Results: sourceware.org; spf=pass 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-out2.suse.de (Postfix) with ESMTPS id AB96A1F91D; Fri, 26 Aug 2022 16:38:47 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=suse.cz; s=susede2_rsa; t=1661531927; h=from:from:reply-to:date:date:message-id:message-id:to:to:cc:cc: mime-version:mime-version:content-type:content-type; bh=BAzBpaBXTdHxPO/xloCAAdw7KVJWg5vdVhqJ04JHZPA=; b=JXLqR17PzNDq5LSmUIFBx1N6df4D+NyHZYZyjFbJR8zyKpBw4u8wO6tRuQ9e8dX1JkHa0D YJGAM3kQRBLWWy4xgUi/YaGpWaNW+ChaoHKVzXOWiMKl5karICL3zBin6opSoegVCNkGW9 yNaIVP4hnk+2Vl98bnm7GuXfRQXOUb8= DKIM-Signature: v=1; a=ed25519-sha256; c=relaxed/relaxed; d=suse.cz; s=susede2_ed25519; t=1661531927; h=from:from:reply-to:date:date:message-id:message-id:to:to:cc:cc: mime-version:mime-version:content-type:content-type; bh=BAzBpaBXTdHxPO/xloCAAdw7KVJWg5vdVhqJ04JHZPA=; b=t3MbTCq3etJSf9sG7taqiWtHqfJCbPn5fIPbJcO6IvYMZpElxqUB6nyaSd07No6ULLQ1yw wJlw6CHmQI3DEVAQ== 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 9DACB13421; Fri, 26 Aug 2022 16:38:47 +0000 (UTC) Received: from dovecot-director2.suse.de ([192.168.254.65]) by imap2.suse-dmz.suse.de with ESMTPSA id b1FzJhf3CGMtdwAAMHmgww (envelope-from ); Fri, 26 Aug 2022 16:38:47 +0000 From: Martin Jambor To: GCC Patches Subject: [PATCH 1/2] vec: Add array_slice constructors from non-const and gc vectors User-Agent: Notmuch/0.35 (https://notmuchmail.org) Emacs/28.1 (x86_64-suse-linux-gnu) Date: Fri, 26 Aug 2022 18:38:47 +0200 Message-ID: MIME-Version: 1.0 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_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 X-BeenThere: gcc-patches@gcc.gnu.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Gcc-patches mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Cc: Richard Sandiford , Richard Biener Errors-To: gcc-patches-bounces+incoming=patchwork.ozlabs.org@gcc.gnu.org Sender: "Gcc-patches" Hi, This patch adds constructors of array_slice that are required to create them from non-const (heap or auto) vectors or from GC vectors. The use of non-const array_slices is somewhat limited, as creating one from const vec still leads to array_slice, so I eventually also only resorted to having read-only array_slices. But I do need the constructor from the gc vector. Bootstrapped and tested along code that actually uses it on x86_64-linux. OK for trunk? Thanks, Martin gcc/ChangeLog: 2022-08-08 Martin Jambor * vec.h (array_slice): Add constructors for non-const reference to heap vector and pointers to heap vectors. --- gcc/vec.h | 12 ++++++++++++ 1 file changed, 12 insertions(+) diff --git a/gcc/vec.h b/gcc/vec.h index eed075addc9..b0477e1044c 100644 --- a/gcc/vec.h +++ b/gcc/vec.h @@ -2264,6 +2264,18 @@ public: array_slice (const vec &v) : m_base (v.address ()), m_size (v.length ()) {} + template + array_slice (vec &v) + : m_base (v.address ()), m_size (v.length ()) {} + + template + array_slice (const vec *v) + : m_base (v ? v->address () : nullptr), m_size (v ? v->length () : 0) {} + + template + array_slice (vec *v) + : m_base (v ? v->address () : nullptr), m_size (v ? v->length () : 0) {} + iterator begin () { return m_base; } iterator end () { return m_base + m_size; } From patchwork Fri Aug 26 16:39:09 2022 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Martin Jambor X-Patchwork-Id: 1670941 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@legolas.ozlabs.org Authentication-Results: legolas.ozlabs.org; spf=pass (sender SPF authorized) smtp.mailfrom=gcc.gnu.org (client-ip=2620:52:3:1:0:246e:9693:128c; helo=sourceware.org; envelope-from=gcc-patches-bounces+incoming=patchwork.ozlabs.org@gcc.gnu.org; receiver=) Authentication-Results: legolas.ozlabs.org; dkim=fail reason="signature verification failed" (1024-bit key; unprotected) header.d=suse.cz header.i=@suse.cz header.a=rsa-sha256 header.s=susede2_rsa header.b=cahRbb0z; dkim=fail reason="signature verification failed" header.d=suse.cz header.i=@suse.cz header.a=ed25519-sha256 header.s=susede2_ed25519 header.b=ziozW9ay; dkim-atps=neutral Received: from sourceware.org (server2.sourceware.org [IPv6:2620:52:3:1:0:246e:9693:128c]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature ECDSA (P-384) server-digest SHA384) (No client certificate requested) by legolas.ozlabs.org (Postfix) with ESMTPS id 4MDltf1tKSz1yhN for ; Sat, 27 Aug 2022 02:40:08 +1000 (AEST) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 73DB1385116E for ; Fri, 26 Aug 2022 16:40:05 +0000 (GMT) X-Original-To: gcc-patches@gcc.gnu.org Delivered-To: gcc-patches@gcc.gnu.org Received: from smtp-out1.suse.de (smtp-out1.suse.de [IPv6:2001:67c:2178:6::1c]) by sourceware.org (Postfix) with ESMTPS id 061B4385085A for ; Fri, 26 Aug 2022 16:39:11 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 061B4385085A 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 D52C9336B4; Fri, 26 Aug 2022 16:39:09 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=suse.cz; s=susede2_rsa; t=1661531949; h=from:from:reply-to:date:date:message-id:message-id:to:to:cc:cc: mime-version:mime-version:content-type:content-type; bh=8MMuIFKw8HIBHFu3wvmmGEtZFb6+vpH6VStXUmfib5c=; b=cahRbb0zi1l+np8/Eaa2cDEz6YgK6X+KNmBysy5VzvmRGuKymkMnb6GIdiVooO2nxdlfDq v2qaPyEaVJRhQR+/uGDLJtzDAFrCKM/Y7U12P8iMqOvNajgudFv3RgyWh/blILxpVkG63k snl6PTKRgI1vRHR+p9BKLYrcIercs44= DKIM-Signature: v=1; a=ed25519-sha256; c=relaxed/relaxed; d=suse.cz; s=susede2_ed25519; t=1661531949; h=from:from:reply-to:date:date:message-id:message-id:to:to:cc:cc: mime-version:mime-version:content-type:content-type; bh=8MMuIFKw8HIBHFu3wvmmGEtZFb6+vpH6VStXUmfib5c=; b=ziozW9aySuKliJh2cyi9wfzrJmAiWvogX+3fHvNCzbmM8Vez/S6hnR/57vgCVDW4m0hUs8 L+8KyfvfVDjN68CQ== 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 C70D313421; Fri, 26 Aug 2022 16:39:09 +0000 (UTC) Received: from dovecot-director2.suse.de ([192.168.254.65]) by imap2.suse-dmz.suse.de with ESMTPSA id sXV5MC33CGNbdwAAMHmgww (envelope-from ); Fri, 26 Aug 2022 16:39:09 +0000 From: Martin Jambor To: GCC Patches Subject: [PATCH 2/2] vec: Add array_slice::bsearch User-Agent: Notmuch/0.35 (https://notmuchmail.org) Emacs/28.1 (x86_64-suse-linux-gnu) Date: Fri, 26 Aug 2022 18:39:09 +0200 Message-ID: MIME-Version: 1.0 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 X-BeenThere: gcc-patches@gcc.gnu.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Gcc-patches mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Cc: Richard Sandiford , Richard Biener Errors-To: gcc-patches-bounces+incoming=patchwork.ozlabs.org@gcc.gnu.org Sender: "Gcc-patches" Hi, This adds a method to binary search in a sorted array_slice. 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. Bootstrapped and tested along code that actually uses it on x86_64-linux. OK for trunk? Thanks, Martin gcc/ChangeLog: 2022-08-08 Martin Jambor * vec.h (array_slice::bsearch): New methods. --- gcc/vec.h | 94 +++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 94 insertions(+) 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 == 0; } + /* 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 *) const; + 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); } +/* 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 = this->m_base; + size_t nmemb = this->size (); + size_t size = sizeof (T); + /* The following is a copy of glibc stdlib-bsearch.h. */ + size_t l, u, idx; + const void *p; + int comparison; + + l = 0; + u = nmemb; + while (l < u) + { + idx = (l + u) / 2; + p = (const void *) (((const char *) base) + (idx * size)); + comparison = (*compar) (key, p); + if (comparison < 0) + u = idx; + else if (comparison > 0) + l = 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 = this->m_base; + size_t nmemb = this->size (); + size_t size = sizeof (T); + /* The following is a copy of glibc stdlib-bsearch.h. */ + size_t l, u, idx; + const void *p; + int comparison; + + l = 0; + u = nmemb; + while (l < u) + { + idx = (l + u) / 2; + p = (const void *) (((const char *) base) + (idx * size)); + comparison = (*compar) (key, p, data); + if (comparison < 0) + u = idx; + else if (comparison > 0) + l = 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 >= 3000) # pragma GCC poison m_vec m_vecpfx m_vecdata #endif