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: 791 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:adf:ecc5:0:0:0:0:0 with SMTP id s5csp315771wro; Fri, 26 Aug 2022 09:40:20 -0700 (PDT) X-Google-Smtp-Source: AA6agR73ZwWbJMNEtyAsN1W9tPMLDNkE4XgdsrLO2D602pkSv8TgYC655kLVBQveqyehRhRMKPTD X-Received: by 2002:a17:907:7e8e:b0:741:362a:9678 with SMTP id qb14-20020a1709077e8e00b00741362a9678mr1470748ejc.499.1661532020157; Fri, 26 Aug 2022 09:40:20 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1661532020; cv=none; d=google.com; s=arc-20160816; b=GnN3GBzmlJjTP+9Oj451omBV4VuV11pdXmCBHob3vhoeirpEm4bHWcondZb68ww0tP GT6AL0/gX+anQb1EKygHysmhV3YowtMOkGHROaCm7p86PR3Om6HOaRlVUhcnkkaRGyRV Fp1Jgak37HaY6+tsQtN1ts+CWyn13fiawVoVNffZkIlyh+2Lrc93auIrA65yiztN7ofM OyfM+rw1KI39it1oztbqjwOp2PpljBnV+h52740nX8e2ynkiiOaCKv80EJnksRr0+kXO jVuTQSidXuNNwEhFGSR2iDumc7PcBcDnQVyYFAZLlIHpUR7uTFtp/81YgTbpAenxmoBX 9StQ== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=sender:errors-to:cc:list-subscribe:list-help:list-post:list-archive :list-unsubscribe:list-id:precedence:mime-version:message-id:date :user-agent:subject:to:from:dkim-signature:dkim-signature :dmarc-filter:delivered-to; bh=8MMuIFKw8HIBHFu3wvmmGEtZFb6+vpH6VStXUmfib5c=; b=XdDpUMiSU1mE0OlCg9fhU3NKSo2vLMlJykZca0aKeLgOkAO3jQt4uyimtL2DVXspo1 JavPGRaj51G7izDHN8jGNm+pzHSW5Nag52mowdnIwrG5DA7g6HbMK5ngc0eXXhUZ1Mc2 Bp6/2bJdj9fDYTqVODQGxZ4s5F/UtIqEKFXsvg8NL+jRAwmyrZMMTQ/raxdU+2aZNQ8H xAdM1Sa2gKeznvhr8bNBwuGPdNrQgqzGMAsJ1X4M6EszcRS9+61bJWEF8SlBa7TYfsEj 8D5hEOW+tBtWuW1r/EvwhHVq14R3ResRhYWeH28volAtcF9T1EofvH0HvX4a0wyGJvUb HerA== ARC-Authentication-Results: i=1; mx.google.com; dkim=fail header.i=@suse.cz header.s=susede2_rsa header.b=cahRbb0z; dkim=neutral (no key) header.i=@suse.cz header.s=susede2_ed25519 header.b=ziozW9ay; spf=pass (google.com: domain of gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org designates 2620:52:3:1:0:246e:9693:128c as permitted sender) smtp.mailfrom="gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org" Received: from sourceware.org (server2.sourceware.org. [2620:52:3:1:0:246e:9693:128c]) by mx.google.com with ESMTPS id gs38-20020a1709072d2600b0073136f95cccsi1585922ejc.582.2022.08.26.09.40.19 for (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Fri, 26 Aug 2022 09:40:20 -0700 (PDT) Received-SPF: pass (google.com: domain of gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org designates 2620:52:3:1:0:246e:9693:128c as permitted sender) client-ip=2620:52:3:1:0:246e:9693:128c; Authentication-Results: mx.google.com; dkim=fail header.i=@suse.cz header.s=susede2_rsa header.b=cahRbb0z; dkim=neutral (no key) header.i=@suse.cz header.s=susede2_ed25519 header.b=ziozW9ay; spf=pass (google.com: domain of gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org designates 2620:52:3:1:0:246e:9693:128c as permitted sender) smtp.mailfrom="gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org" Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id B08373851153 for ; Fri, 26 Aug 2022 16:40:17 +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+ouuuleilei=gmail.com@gcc.gnu.org Sender: "Gcc-patches" X-getmail-retrieved-from-mailbox: =?utf-8?q?INBOX?= X-GMAIL-THRID: =?utf-8?q?1742242599192608018?= X-GMAIL-MSGID: =?utf-8?q?1742242599192608018?= 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