From patchwork Thu Nov 23 21:58:40 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: =?utf-8?q?Fran=C3=A7ois_Dumont?= X-Patchwork-Id: 1867984 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@legolas.ozlabs.org Authentication-Results: legolas.ozlabs.org; dkim=pass (2048-bit key; unprotected) header.d=gmail.com header.i=@gmail.com header.a=rsa-sha256 header.s=20230601 header.b=lpaxfHlo; dkim-atps=neutral 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=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 [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 (secp384r1) server-digest SHA384) (No client certificate requested) by legolas.ozlabs.org (Postfix) with ESMTPS id 4SbsT13x4Bz1yS0 for ; Fri, 24 Nov 2023 08:59:01 +1100 (AEDT) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 1FCC53857C60 for ; Thu, 23 Nov 2023 21:58:59 +0000 (GMT) X-Original-To: gcc-patches@gcc.gnu.org Delivered-To: gcc-patches@gcc.gnu.org Received: from mail-wm1-x335.google.com (mail-wm1-x335.google.com [IPv6:2a00:1450:4864:20::335]) by sourceware.org (Postfix) with ESMTPS id BD62A38582A5; Thu, 23 Nov 2023 21:58:43 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org BD62A38582A5 Authentication-Results: sourceware.org; dmarc=pass (p=none dis=none) header.from=gmail.com Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=gmail.com ARC-Filter: OpenARC Filter v1.0.0 sourceware.org BD62A38582A5 Authentication-Results: server2.sourceware.org; arc=none smtp.remote-ip=2a00:1450:4864:20::335 ARC-Seal: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1700776726; cv=none; b=c19XefIksEyIgXFoXS3RWYm3tVA3UD7bN9v+Y5sf6iDU2166K+E/G7F8IFLXZrZU6ykSidr/nvuXjmCzq6+Voz8G9z3k78MSqTAwu93NzpGk82sxZzamovdNrPL82uHsJeYMBIJS5UQXxkOJVnWTefZQkFADHLm6HI1VyJ5/q5I= ARC-Message-Signature: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1700776726; c=relaxed/simple; bh=Chw4+PBM/6T90QUTMv2lKNKcHp+0vC3aI0kbEQNhi7Y=; h=DKIM-Signature:Message-ID:Date:MIME-Version:From:Subject:To; b=VwAkcEfWi6LxLoQCsFTPaKgEoUPkOL2CVR38TuzXWg78Tdz6LInEr4IWzDug+hhkEf5W+AD2sTsh/lbt4i7dhSrmMUckwcfFH+M2XbcGmYljdeVqchHu042zCjGZk1LOCRenV6PIVqmyOYjIXJfjESVnW9Xl4SqLTbeyiaoJUu8= ARC-Authentication-Results: i=1; server2.sourceware.org Received: by mail-wm1-x335.google.com with SMTP id 5b1f17b1804b1-40790b0a224so8683935e9.0; Thu, 23 Nov 2023 13:58:43 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1700776721; x=1701381521; darn=gcc.gnu.org; h=content-language:cc:to:subject:from:user-agent:mime-version:date :message-id:from:to:cc:subject:date:message-id:reply-to; bh=d1bZAoN21BhFLqrDdrtHn2KjnFkKSSuSu9ElmYnJc0w=; b=lpaxfHloLXMhYcCTtoB1bf05XJEz7IqRImmUEGu2SbFSrn+MBcTnn1q4E4RytT5fU/ KxrqmSjftw3MR5P4nYp7y+ExJC0w7FiqevF0z+wJ18kgF7CIPT53xzzdHPdAxH22upXR FBwNMi6moHdlx7C6Qx/YH8fBWJGkWHhYXUgyjRifeVL1Crq5ZzAyf3kjZSjXxU9/KKun X3HJ+00/IIU8ALdC7iBHI+B7vePR3DrzR32OHffhdFI7p6EY4kdVAAOIcbTCOJX9Ua/e HlhUlnycjGw4k0R1mKscUEr6aINZepcoHxOitqyv/FLdgh1Fxu21OXpmRzVNc+u4/Lve g+9w== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1700776721; x=1701381521; h=content-language:cc:to:subject:from:user-agent:mime-version:date :message-id:x-gm-message-state:from:to:cc:subject:date:message-id :reply-to; bh=d1bZAoN21BhFLqrDdrtHn2KjnFkKSSuSu9ElmYnJc0w=; b=AcR4GBwyTNnTfVWIZYatcFxxVlRTKiGnSt3LsTsYWuG93aDqQLal1Ifxay41yLH+Eg 2hKbzYF/yZ87c90XzodBuPtfhjhJLHArotZPyBEOl65TmiImCHAGT/AWCZchsGy5frqc GPawlfF1+lTzs6tYcsU34QamPzpctnLuLqWrsZMX/xuojzIaIYQDYEtxqT54DyniHuYU +CR3tEqB7vxlhrh3sjJL7EQfEigxEyi6LKFVYXcD+G7lErzzA+r3boENOLEGtqsvD/6b jNRPAky6hzJZE456wWdJX6xV/6qnREim71D4x8UbJh/MMUQ7lDwU0v9loWgyh4MdqFel cqmA== X-Gm-Message-State: AOJu0Ywq1OF/gfoeWR9bYX8uh6A4YkRkwkJux/31TUt6c9g3RrqEUIoh d8q+flXRtY8dhVhNw3DNe2cp0QT2kqc= X-Google-Smtp-Source: AGHT+IECKX34si0iUaGsIi84PVdxK4PYj6F8nGmGoMNL8/4aaEjkG/p1HUxPV6NAooIofC7ENlQxiA== X-Received: by 2002:a05:6000:b03:b0:332:cada:84a with SMTP id dj3-20020a0560000b0300b00332cada084amr534240wrb.61.1700776721265; Thu, 23 Nov 2023 13:58:41 -0800 (PST) Received: from ?IPV6:2a01:e0a:1dc:b1c0:fc8d:30b8:64d5:2ae8? ([2a01:e0a:1dc:b1c0:fc8d:30b8:64d5:2ae8]) by smtp.gmail.com with ESMTPSA id o7-20020a05600c510700b0040b36ad5413sm2995518wms.46.2023.11.23.13.58.40 (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Thu, 23 Nov 2023 13:58:40 -0800 (PST) Message-ID: <1e319e88-62ae-476f-bae0-afa8ba126310@gmail.com> Date: Thu, 23 Nov 2023 22:58:40 +0100 MIME-Version: 1.0 User-Agent: Mozilla Thunderbird From: =?utf-8?q?Fran=C3=A7ois_Dumont?= Subject: [PATCH 2/5][_Hashtable] Fix implementation inconsistencies To: libstdc++ Cc: gcc-patches Content-Language: en-US X-Spam-Status: No, score=-9.1 required=5.0 tests=BAYES_00, BODY_8BITS, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, FREEMAIL_FROM, GIT_PATCH_0, RCVD_IN_DNSWL_NONE, 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.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 libstdc++: [_Hashtable] Fix some implementation inconsistencies     Get rid of the different usages of the mutable keyword. For     _Prime_rehash_policy methods are exported from the library, we need to     keep their const qualifier, so adapt implementation to update previously     mutable member.     Remove useless noexcept qualification on _Hashtable _M_bucket_index overload.     Fix comment to explain that we need the computation of bucket index to be     noexcept to be able to rehash the container when needed. For Standard     instantiations through std::unordered_xxx containers we already force     usage of hash code cache when hash functor is not noexcep so it is guarantied.     The static_assert purpose in _Hashtable on _M_bucket_index is thus limited     to usages of _Hashtable with exotic _Hashtable_traits.     libstdc++-v3/ChangeLog:             * include/bits/hashtable_policy.h (_NodeBuilder<>::_S_build): Remove             const qualification on _NodeGenerator instance. (_ReuseOrAllocNode<>::operator()(_Args&&...)): Remove const qualification.             (_ReuseOrAllocNode<>::_M_nodes): Remove mutable.             (_Prime_rehash_policy::max_load_factor()): Remove noexcept.             (_Prime_rehash_policy::_M_reset()): Remove noexcept.             (_Prime_rehash_policy::_M_next_resize): Remove mutable.             (_Power2_rehash_policy::_M_next_bkt(size_t)): Remove noexcept.             (_Power2_rehash_policy::_M_bkt_for_elements(size_t)): Remove noexcept.             (_Power2_rehash_policy::_M_neeed_rehash): Remove noexcept.             (_Power2_rehash_policy::_M_reset): Remove noexcept.             (_Insert_base<>::_M_insert_range): Remove _NodeGetter const qualification.             (_Hash_code_base<>::_M_bucket_index(const _Hash_node_value<>&, size_t)):             Simplify noexcept declaration, we already static_assert that _RangeHash functor             is noexcept.             * include/bits/hashtable.h: Rework comments. Remove const qualifier on             _NodeGenerator& arguments.             (_Hashtable<>::_M_bucket_index(const __node_value_type&)): Remove useless             noexcept qualification.             * src/c++11/hashtable_c++0x.cc (_Prime_rehash_policy): Workaround             _M_next_resize not being mutable anymore. Tested under Linux x86_64, ok to commit ? François diff --git a/libstdc++-v3/include/bits/hashtable.h b/libstdc++-v3/include/bits/hashtable.h index 9ff9104a2ab..8329d32e68e 100644 --- a/libstdc++-v3/include/bits/hashtable.h +++ b/libstdc++-v3/include/bits/hashtable.h @@ -48,7 +48,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION using __cache_default = __not_<__and_, - // Mandatory to have erase not throwing. + // Mandatory for the rehash process. __is_nothrow_invocable>>; // Helper to conditionally delete the default constructor. @@ -477,7 +477,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION template void - _M_assign(_Ht&&, const _NodeGenerator&); + _M_assign(_Ht&&, _NodeGenerator&); void _M_move_assign(_Hashtable&&, true_type); @@ -792,7 +792,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION private: // Bucket index computation helpers. size_type - _M_bucket_index(const __node_value_type& __n) const noexcept + _M_bucket_index(const __node_value_type& __n) const { return __hash_code_base::_M_bucket_index(__n, _M_bucket_count); } size_type @@ -920,7 +920,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION template std::pair - _M_insert_unique(_Kt&&, _Arg&&, const _NodeGenerator&); + _M_insert_unique(_Kt&&, _Arg&&, _NodeGenerator&); template static __conditional_t< @@ -940,7 +940,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION template std::pair - _M_insert_unique_aux(_Arg&& __arg, const _NodeGenerator& __node_gen) + _M_insert_unique_aux(_Arg&& __arg, _NodeGenerator& __node_gen) { return _M_insert_unique( _S_forward_key(_ExtractKey{}(std::forward<_Arg>(__arg))), @@ -949,7 +949,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION template std::pair - _M_insert(_Arg&& __arg, const _NodeGenerator& __node_gen, + _M_insert(_Arg&& __arg, _NodeGenerator& __node_gen, true_type /* __uks */) { using __to_value @@ -960,7 +960,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION template iterator - _M_insert(_Arg&& __arg, const _NodeGenerator& __node_gen, + _M_insert(_Arg&& __arg, _NodeGenerator& __node_gen, false_type __uks) { using __to_value @@ -973,7 +973,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION template iterator _M_insert(const_iterator, _Arg&& __arg, - const _NodeGenerator& __node_gen, true_type __uks) + _NodeGenerator& __node_gen, true_type __uks) { return _M_insert(std::forward<_Arg>(__arg), __node_gen, __uks).first; @@ -983,7 +983,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION template iterator _M_insert(const_iterator, _Arg&&, - const _NodeGenerator&, false_type __uks); + _NodeGenerator&, false_type __uks); size_type _M_erase(true_type __uks, const key_type&); @@ -1378,7 +1378,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION void _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>:: - _M_assign(_Ht&& __ht, const _NodeGenerator& __node_gen) + _M_assign(_Ht&& __ht, _NodeGenerator& __node_gen) { __buckets_ptr __buckets = nullptr; if (!_M_buckets) @@ -1620,8 +1620,10 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION ~_Hashtable() noexcept { // Getting a bucket index from a node shall not throw because it is used - // in methods (erase, swap...) that shall not throw. Need a complete - // type to check this, so do it in the destructor not at class scope. + // during the rehash process. This static_assert purpose is limited to usage + // of _Hashtable with _Hashtable_traits requesting non-cached hash code. + // Need a complete type to check this, so do it in the destructor not at + // class scope. static_assert(noexcept(declval() ._M_bucket_index(declval(), (std::size_t)0)), @@ -2222,7 +2224,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>:: _M_insert_unique(_Kt&& __k, _Arg&& __v, - const _NodeGenerator& __node_gen) + _NodeGenerator& __node_gen) -> pair { if (size() <= __small_size_threshold()) @@ -2259,7 +2261,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>:: _M_insert(const_iterator __hint, _Arg&& __v, - const _NodeGenerator& __node_gen, + _NodeGenerator& __node_gen, false_type /* __uks */) -> iterator { diff --git a/libstdc++-v3/include/bits/hashtable_policy.h b/libstdc++-v3/include/bits/hashtable_policy.h index c67eebd3b2b..5c40be2cb72 100644 --- a/libstdc++-v3/include/bits/hashtable_policy.h +++ b/libstdc++-v3/include/bits/hashtable_policy.h @@ -155,7 +155,7 @@ namespace __detail { template static auto - _S_build(_Kt&& __k, _Arg&& __arg, const _NodeGenerator& __node_gen) + _S_build(_Kt&& __k, _Arg&& __arg, _NodeGenerator& __node_gen) -> typename _NodeGenerator::__node_ptr { return __node_gen(std::forward<_Kt>(__k), @@ -168,7 +168,7 @@ namespace __detail { template static auto - _S_build(_Kt&& __k, _Arg&&, const _NodeGenerator& __node_gen) + _S_build(_Kt&& __k, _Arg&&, _NodeGenerator& __node_gen) -> typename _NodeGenerator::__node_ptr { return __node_gen(std::forward<_Kt>(__k)); } }; @@ -212,7 +212,7 @@ namespace __detail template __node_ptr - operator()(_Args&&... __args) const + operator()(_Args&&... __args) { if (!_M_nodes) return _M_h._M_allocate_node(std::forward<_Args>(__args)...); @@ -230,7 +230,7 @@ namespace __detail } private: - mutable __node_ptr _M_nodes; + __node_ptr _M_nodes; __hashtable_alloc& _M_h; }; @@ -551,10 +551,11 @@ namespace __detail : _M_max_load_factor(__z), _M_next_resize(0) { } float - max_load_factor() const noexcept + max_load_factor() const { return _M_max_load_factor; } // Return a bucket size no smaller than n. + // TODO: 'const' qualifier is kept for abi compatibility reason. std::size_t _M_next_bkt(std::size_t __n) const; @@ -567,6 +568,7 @@ namespace __detail // and __n_ins is number of elements to be inserted. Do we need to // increase bucket count? If so, return make_pair(true, n), where n // is the new bucket count. If not, return make_pair(false, 0). + // TODO: 'const' qualifier is kept for abi compatibility reason. std::pair _M_need_rehash(std::size_t __n_bkt, std::size_t __n_elt, std::size_t __n_ins) const; @@ -578,7 +580,7 @@ namespace __detail { return _M_next_resize; } void - _M_reset() noexcept + _M_reset() { _M_next_resize = 0; } void @@ -588,7 +590,7 @@ namespace __detail static const std::size_t _S_growth_factor = 2; float _M_max_load_factor; - mutable std::size_t _M_next_resize; + std::size_t _M_next_resize; }; /// Range hashing function assuming that second arg is a power of 2. @@ -629,13 +631,13 @@ namespace __detail : _M_max_load_factor(__z), _M_next_resize(0) { } float - max_load_factor() const noexcept + max_load_factor() const { return _M_max_load_factor; } // Return a bucket size no smaller than n (as long as n is not above the // highest power of 2). std::size_t - _M_next_bkt(std::size_t __n) noexcept + _M_next_bkt(std::size_t __n) { if (__n == 0) // Special case on container 1st initialization with 0 bucket count @@ -669,7 +671,7 @@ namespace __detail // Return a bucket count appropriate for n elements std::size_t - _M_bkt_for_elements(std::size_t __n) const noexcept + _M_bkt_for_elements(std::size_t __n) const { return __builtin_ceil(__n / (double)_M_max_load_factor); } // __n_bkt is current bucket count, __n_elt is current element count, @@ -678,7 +680,7 @@ namespace __detail // is the new bucket count. If not, return make_pair(false, 0). std::pair _M_need_rehash(std::size_t __n_bkt, std::size_t __n_elt, - std::size_t __n_ins) noexcept + std::size_t __n_ins) { if (__n_elt + __n_ins > _M_next_resize) { @@ -708,11 +710,11 @@ namespace __detail { return _M_next_resize; } void - _M_reset() noexcept + _M_reset() { _M_next_resize = 0; } void - _M_reset(_State __state) noexcept + _M_reset(_State __state) { _M_next_resize = __state; } static const std::size_t _S_growth_factor = 2; @@ -931,12 +933,12 @@ namespace __detail template void _M_insert_range(_InputIterator __first, _InputIterator __last, - const _NodeGetter&, true_type __uks); + _NodeGetter&, true_type __uks); template void _M_insert_range(_InputIterator __first, _InputIterator __last, - const _NodeGetter&, false_type __uks); + _NodeGetter&, false_type __uks); public: using iterator = _Node_iterator<_Value, __constant_iterators::value, @@ -1012,7 +1014,7 @@ namespace __detail _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>:: _M_insert_range(_InputIterator __first, _InputIterator __last, - const _NodeGetter& __node_gen, true_type __uks) + _NodeGetter& __node_gen, true_type __uks) { __hashtable& __h = _M_conjure_hashtable(); for (; __first != __last; ++__first) @@ -1029,7 +1031,7 @@ namespace __detail _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>:: _M_insert_range(_InputIterator __first, _InputIterator __last, - const _NodeGetter& __node_gen, false_type __uks) + _NodeGetter& __node_gen, false_type __uks) { using __rehash_guard_t = typename __hashtable::__rehash_guard_t; using __pair_type = std::pair; @@ -1359,9 +1361,7 @@ namespace __detail std::size_t _M_bucket_index(const _Hash_node_value<_Value, false>& __n, std::size_t __bkt_count) const - noexcept( noexcept(declval()(declval())) - && noexcept(declval()((__hash_code)0, - (std::size_t)0)) ) + noexcept( noexcept(declval()(declval())) ) { return _RangeHash{}(_M_hash_code(_ExtractKey{}(__n._M_v())), __bkt_count); @@ -1369,9 +1369,7 @@ namespace __detail std::size_t _M_bucket_index(const _Hash_node_value<_Value, true>& __n, - std::size_t __bkt_count) const - noexcept( noexcept(declval()((__hash_code)0, - (std::size_t)0)) ) + std::size_t __bkt_count) const noexcept { return _RangeHash{}(__n._M_hash_code, __bkt_count); } void diff --git a/libstdc++-v3/src/c++11/hashtable_c++0x.cc b/libstdc++-v3/src/c++11/hashtable_c++0x.cc index 9673d867402..e75b09a31bb 100644 --- a/libstdc++-v3/src/c++11/hashtable_c++0x.cc +++ b/libstdc++-v3/src/c++11/hashtable_c++0x.cc @@ -45,6 +45,7 @@ namespace __detail std::size_t _Prime_rehash_policy::_M_next_bkt(std::size_t __n) const { + auto __mutable_this = const_cast<_Prime_rehash_policy*>(this); // Optimize lookups involving the first elements of __prime_list. // (useful to speed-up, eg, constructors) static const unsigned char __fast_bkt[] @@ -58,7 +59,7 @@ namespace __detail // want to add an element allocation will take place. return 1; - _M_next_resize = + __mutable_this->_M_next_resize = __builtin_floor(__fast_bkt[__n] * (double)_M_max_load_factor); return __fast_bkt[__n]; } @@ -79,9 +80,9 @@ namespace __detail // Set next resize to the max value so that we never try to rehash again // as we already reach the biggest possible bucket number. // Note that it might result in max_load_factor not being respected. - _M_next_resize = size_t(-1); + __mutable_this->_M_next_resize = size_t(-1); else - _M_next_resize = + __mutable_this->_M_next_resize = __builtin_floor(*__next_bkt * (double)_M_max_load_factor); return *__next_bkt; @@ -101,6 +102,7 @@ namespace __detail _M_need_rehash(std::size_t __n_bkt, std::size_t __n_elt, std::size_t __n_ins) const { + auto __mutable_this = const_cast<_Prime_rehash_policy*>(this); if (__n_elt + __n_ins > _M_next_resize) { // If _M_next_resize is 0 it means that we have nothing allocated so @@ -114,7 +116,7 @@ namespace __detail _M_next_bkt(std::max(__builtin_floor(__min_bkts) + 1, __n_bkt * _S_growth_factor)) }; - _M_next_resize + __mutable_this->_M_next_resize = __builtin_floor(__n_bkt * (double)_M_max_load_factor); return { false, 0 }; }