From patchwork Fri Nov 8 15:30:11 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: Jonathan Wakely X-Patchwork-Id: 2008580 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@legolas.ozlabs.org Authentication-Results: legolas.ozlabs.org; dkim=pass (1024-bit key; unprotected) header.d=redhat.com header.i=@redhat.com header.a=rsa-sha256 header.s=mimecast20190719 header.b=HigOL8EQ; dkim-atps=neutral Authentication-Results: legolas.ozlabs.org; spf=pass (sender SPF authorized) smtp.mailfrom=gcc.gnu.org (client-ip=8.43.85.97; helo=server2.sourceware.org; envelope-from=gcc-patches-bounces~incoming=patchwork.ozlabs.org@gcc.gnu.org; receiver=patchwork.ozlabs.org) Received: from server2.sourceware.org (server2.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 (secp384r1) server-digest SHA384) (No client certificate requested) by legolas.ozlabs.org (Postfix) with ESMTPS id 4XlNcc0ddJz1xy0 for ; Sat, 9 Nov 2024 02:47:44 +1100 (AEDT) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 47AD23857BA7 for ; Fri, 8 Nov 2024 15:47:42 +0000 (GMT) X-Original-To: gcc-patches@gcc.gnu.org Delivered-To: gcc-patches@gcc.gnu.org Received: from us-smtp-delivery-124.mimecast.com (us-smtp-delivery-124.mimecast.com [170.10.133.124]) by sourceware.org (Postfix) with ESMTP id 16BCA3858D3C for ; Fri, 8 Nov 2024 15:46:03 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org 16BCA3858D3C Authentication-Results: sourceware.org; dmarc=pass (p=none dis=none) header.from=redhat.com Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=redhat.com ARC-Filter: OpenARC Filter v1.0.0 sourceware.org 16BCA3858D3C Authentication-Results: server2.sourceware.org; arc=none smtp.remote-ip=170.10.133.124 ARC-Seal: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1731080770; cv=none; b=Ee//ZmnyHzsKMQKQManU6hzPujfATgKMJa3DDcSe/yFe/PJ7ILzpum21nVUSybAdjMZb2nbsr9rtz5cFs1BU+f/qQOZk0V+K+c2LS31FJ66Fqyk7/2m81wawy05RWuyGR1bm1CyrSvpMjk1IdHBkk91w7BX01MpnKWjmVpFMLXM= ARC-Message-Signature: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1731080770; c=relaxed/simple; bh=62ljSzcizjnB4H9ikK5+2w8nBPDD8U36kSX8LI9jzwY=; h=DKIM-Signature:From:To:Subject:Date:Message-ID:MIME-Version; b=MTSjumgR22KMU2LaLIe1Xl9kQNoWq2x0KgAAKitVPkHLqsO7fo6nX3YE6yNJifXGSG4xxBwZUkz0W+3qTWp3DsZQsj62rfJkgRVD7BZEWo/2wr+8fHt/qurlMhEmTDki9D8t+JfUUFISk+Ve1XrMaylsD8DDMmJml/bgtPKsnn0= ARC-Authentication-Results: i=1; server2.sourceware.org DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=redhat.com; s=mimecast20190719; t=1731080762; h=from:from:reply-to:subject:subject: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=XEuLJ+7/wZnlffUlHQgKtS/0tBPAPbUSJBO2im5ZXkk=; b=HigOL8EQoT7xtZS2xlIKF5M85LF3YjCoJYhiTNSXcSBDYXmb3Ja7s4yvjtTgJ6sBzsEkHf SDfHVT3+RycmO2Cxk7f4xelqjY7ZjR8ggoJthpS0pyt5wwb+dpUDjf8nEDvLkN1WFLpoaz B3BWC3a6ih/LQldtm3j3gJtkSzhdJvI= Received: from mx-prod-mc-04.mail-002.prod.us-west-2.aws.redhat.com (ec2-54-186-198-63.us-west-2.compute.amazonaws.com [54.186.198.63]) by relay.mimecast.com with ESMTP with STARTTLS (version=TLSv1.3, cipher=TLS_AES_256_GCM_SHA384) id us-mta-126-JOaoS7tjNkiwvBeYZSPtKg-1; Fri, 08 Nov 2024 10:46:01 -0500 X-MC-Unique: JOaoS7tjNkiwvBeYZSPtKg-1 X-Mimecast-MFC-AGG-ID: JOaoS7tjNkiwvBeYZSPtKg Received: from mx-prod-int-02.mail-002.prod.us-west-2.aws.redhat.com (mx-prod-int-02.mail-002.prod.us-west-2.aws.redhat.com [10.30.177.15]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature RSA-PSS (2048 bits) server-digest SHA256) (No client certificate requested) by mx-prod-mc-04.mail-002.prod.us-west-2.aws.redhat.com (Postfix) with ESMTPS id 7CE301955DC1; Fri, 8 Nov 2024 15:46:00 +0000 (UTC) Received: from localhost (unknown [10.22.64.104]) by mx-prod-int-02.mail-002.prod.us-west-2.aws.redhat.com (Postfix) with ESMTP id B6886195607C; Fri, 8 Nov 2024 15:45:59 +0000 (UTC) From: Jonathan Wakely To: libstdc++@gcc.gnu.org, gcc-patches@gcc.gnu.org Cc: =?utf-8?q?Fran=C3=A7ois_Dumont?= Subject: [PATCH 01/12] libstdc++: Refactor _Hashtable::operator=(initializer_list) Date: Fri, 8 Nov 2024 15:30:11 +0000 Message-ID: <20241108154548.813315-2-jwakely@redhat.com> In-Reply-To: <20241108154548.813315-1-jwakely@redhat.com> References: <20241108154548.813315-1-jwakely@redhat.com> MIME-Version: 1.0 X-Scanned-By: MIMEDefang 3.0 on 10.30.177.15 X-Mimecast-Spam-Score: 0 X-Mimecast-MFC-PROC-ID: aKPCtyvhlwpklpB31ZSgvnqUyvYHQK7pAsEcsEJCjb4_1731080760 X-Mimecast-Originator: redhat.com X-BeenThere: gcc-patches@gcc.gnu.org X-Mailman-Version: 2.1.30 Precedence: list List-Id: Gcc-patches mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: gcc-patches-bounces~incoming=patchwork.ozlabs.org@gcc.gnu.org This replaces a call to _M_insert_range with open coding the loop. This will allow removing the node generator parameter from _M_insert_range in a later commit. libstdc++-v3/ChangeLog: * include/bits/hashtable.h (operator=(initializer_list)): Refactor to not use _M_insert_range. Reviewed-by: François Dumont --- libstdc++-v3/include/bits/hashtable.h | 35 ++++++++++++++++++++++++--- 1 file changed, 32 insertions(+), 3 deletions(-) diff --git a/libstdc++-v3/include/bits/hashtable.h b/libstdc++-v3/include/bits/hashtable.h index b36142b358a..872fcac22d0 100644 --- a/libstdc++-v3/include/bits/hashtable.h +++ b/libstdc++-v3/include/bits/hashtable.h @@ -610,6 +610,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION return *this; } +#pragma GCC diagnostic push +#pragma GCC diagnostic ignored "-Wc++17-extensions" // if constexpr _Hashtable& operator=(initializer_list __l) { @@ -617,16 +619,43 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION _M_before_begin._M_nxt = nullptr; clear(); - // We consider that all elements of __l are going to be inserted. + // We assume that all elements of __l are likely to be inserted. auto __l_bkt_count = _M_rehash_policy._M_bkt_for_elements(__l.size()); - // Do not shrink to keep potential user reservation. + // Excess buckets might have been intentionally reserved by the user, + // so rehash if we need to grow, but don't shrink. if (_M_bucket_count < __l_bkt_count) rehash(__l_bkt_count); - this->_M_insert_range(__l.begin(), __l.end(), __roan, __unique_keys{}); + _ExtractKey __ex; + for (auto& __e : __l) + { + const key_type& __k = __ex(__e); + + if constexpr (__unique_keys::value) + if (this->size() <= __small_size_threshold()) + { + auto __it = _M_begin(); + for (; __it; __it = __it->_M_next()) + if (this->_M_key_equals(__k, *__it)) + break; + if (__it) + continue; // Found existing element with equivalent key + } + + __hash_code __code = this->_M_hash_code(__k); + size_type __bkt = _M_bucket_index(__code); + + if constexpr (__unique_keys::value) + if (_M_find_node(__bkt, __k, __code)) + continue; // Found existing element with equivalent key + + _M_insert_unique_node(__bkt, __code, __roan(__e)); + } + return *this; } +#pragma GCC diagnostic pop ~_Hashtable() noexcept;