From patchwork Sun Nov 17 21:03:08 2019 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: 1196451 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Authentication-Results: ozlabs.org; spf=pass (sender SPF authorized) smtp.mailfrom=gcc.gnu.org (client-ip=209.132.180.131; helo=sourceware.org; envelope-from=gcc-patches-return-513855-incoming=patchwork.ozlabs.org@gcc.gnu.org; receiver=) Authentication-Results: ozlabs.org; dmarc=fail (p=none dis=none) header.from=gmail.com Authentication-Results: ozlabs.org; dkim=pass (1024-bit key; unprotected) header.d=gcc.gnu.org header.i=@gcc.gnu.org header.b="e9doxDi8"; dkim=fail reason="signature verification failed" (2048-bit key; unprotected) header.d=gmail.com header.i=@gmail.com header.b="ZfUf6xZc"; dkim-atps=neutral Received: from sourceware.org (server1.sourceware.org [209.132.180.131]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by ozlabs.org (Postfix) with ESMTPS id 47GPh32kVgz9sP4 for ; Mon, 18 Nov 2019 08:03:30 +1100 (AEDT) DomainKey-Signature: a=rsa-sha1; c=nofws; d=gcc.gnu.org; h=list-id :list-unsubscribe:list-archive:list-post:list-help:sender:to :from:subject:message-id:date:mime-version:content-type; q=dns; s=default; b=IkES+9GYZE/fO4r/KDa9QIDftkPz02iCA2uIvKlK7HzmwHvICb z9s39iU03b9zE8shFKeuCTqyPiAXdT9Wd8iN7BsHC0Q73AZiGeIMiwL0oiI6A1vG k1d7k6BLh8fozlTMBEfm5fwxwrYB5yTm0QUYPN2kW6HTtYWyx4D8BKV6U= DKIM-Signature: v=1; a=rsa-sha1; c=relaxed; d=gcc.gnu.org; h=list-id :list-unsubscribe:list-archive:list-post:list-help:sender:to :from:subject:message-id:date:mime-version:content-type; s= default; bh=Vv+reiZy0TNLvyhjqx4b4ooMiwY=; b=e9doxDi8C5BV5F1/C/5P 9bj329xMnsRV5Y+t1IxLPovauU+TVxHdu4mnC4rNSEh7dOf1nBEzi4aNGEhLZoYt IFJ/WpKn/krM5Gle7X4g/ZC72ouue3JvXPIws9k91Ukm7rhA4j9RpSPsIrvmzL1X QEAbrT0qVkhEHTFYZoID1sc= Received: (qmail 67254 invoked by alias); 17 Nov 2019 21:03:15 -0000 Mailing-List: contact gcc-patches-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Id: List-Unsubscribe: List-Archive: List-Post: List-Help: Sender: gcc-patches-owner@gcc.gnu.org Delivered-To: mailing list gcc-patches@gcc.gnu.org Received: (qmail 67237 invoked by uid 89); 17 Nov 2019 21:03:15 -0000 Authentication-Results: sourceware.org; auth=none X-Spam-SWARE-Status: No, score=-26.9 required=5.0 tests=BAYES_00, FREEMAIL_FROM, GIT_PATCH_0, GIT_PATCH_1, GIT_PATCH_2, GIT_PATCH_3, RCVD_IN_DNSWL_NONE, SPF_PASS autolearn=ham version=3.3.1 spammy=HX-Received:21c4, HX-Received:sk:h187mr1, 157210, 1572, 10 X-HELO: mail-wm1-f44.google.com Received: from mail-wm1-f44.google.com (HELO mail-wm1-f44.google.com) (209.85.128.44) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with ESMTP; Sun, 17 Nov 2019 21:03:12 +0000 Received: by mail-wm1-f44.google.com with SMTP id t26so16565098wmi.4; Sun, 17 Nov 2019 13:03:12 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=to:from:subject:message-id:date:user-agent:mime-version :content-language; bh=QwKgHlhKw8MaF2WFvBGaKFODjohXwVpT/VHap6yuQV8=; b=ZfUf6xZc36OojbMeX17ID+Kr72yJ9PJL/OmCsmYHz7zy0k6NGAYfzMTb0ATgBMoPkn CLBtF3F6s3RfUeKaAWE2f1ZEuWwItf/t5DPk2npG0JgdPXHc96eREwnYTS4ocxo/NJ7o 5cUgVaDMlUjYE+B2vVUT1ISChDD6T611dPFB5Hjs+w4bf8iQMTUDcgHbKp8TsOMFCdJW oqDHHix8EXyyrIIz4je3BmVMZeheyjmACkE1N4stM/2utF1KLqbO6+nNDZsl9VyoK0bC JkHvUHjIAW6dsMldNbvwB1v6RbNHOjLxeHCz+25Sq5yY+fyeGfrxghzUg6a22JobPBHe SL0A== Received: from ?IPv6:2a01:e0a:1dc:b1c0:2de3:6b55:97a4:2396? ([2a01:e0a:1dc:b1c0:2de3:6b55:97a4:2396]) by smtp.googlemail.com with ESMTPSA id y6sm20701654wrn.21.2019.11.17.13.03.09 (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Sun, 17 Nov 2019 13:03:09 -0800 (PST) To: "libstdc++@gcc.gnu.org" , gcc-patches From: =?utf-8?q?Fran=C3=A7ois_Dumont?= Subject: [PATCH][Hashtable 4/6] Clean local_iterator implementation Message-ID: Date: Sun, 17 Nov 2019 22:03:08 +0100 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:60.0) Gecko/20100101 Thunderbird/60.9.0 MIME-Version: 1.0 Simplify local_iterator implementation. It makes local_iterator and iterator comparable which is used in debug containers.     * include/bits/hashtable_policy.h (_Node_iterator_base()): New.     (operator==(const _Node_iterator_base&, const _Node_iterator_base&)):     Make hidden friend.     (operator!=(const _Node_iterator_base&, const _Node_iterator_base&)):     Make hidden friend.     (_Local_iterator_base<>): Inherits _Node_iterator_base.     (_Local_iterator_base<>::_M_cur): Remove.     (_Local_iterator_base<>::_M_curr()): Remove.     (operator==(const _Local_iterator_base&, const _Local_iterator_base&)):     Remove.     (operator!=(const _Local_iterator_base&, const _Local_iterator_base&)):     Remove.     * include/debug/unordered_map (unordered_map<>::_M_invalidate): Adapt.     (unordered_multimap<>::_M_invalidate): Adapt.     * include/debug/unordered_set (unordered_set<>::_M_invalidate): Adapt.     (unordered_multiset<>::_M_invalidate): Adapt. Tested under Linux x86_64. François diff --git a/libstdc++-v3/include/bits/hashtable_policy.h b/libstdc++-v3/include/bits/hashtable_policy.h index f330f7f811b..5cc943b3d22 100644 --- a/libstdc++-v3/include/bits/hashtable_policy.h +++ b/libstdc++-v3/include/bits/hashtable_policy.h @@ -301,27 +301,24 @@ namespace __detail __node_type* _M_cur; + _Node_iterator_base() = default; _Node_iterator_base(__node_type* __p) noexcept : _M_cur(__p) { } void _M_incr() noexcept { _M_cur = _M_cur->_M_next(); } - }; - template - inline bool - operator==(const _Node_iterator_base<_Value, _Cache_hash_code>& __x, - const _Node_iterator_base<_Value, _Cache_hash_code >& __y) - noexcept - { return __x._M_cur == __y._M_cur; } + friend bool + operator==(const _Node_iterator_base& __x, const _Node_iterator_base& __y) + noexcept + { return __x._M_cur == __y._M_cur; } - template - inline bool - operator!=(const _Node_iterator_base<_Value, _Cache_hash_code>& __x, - const _Node_iterator_base<_Value, _Cache_hash_code>& __y) - noexcept - { return __x._M_cur != __y._M_cur; } + friend bool + operator!=(const _Node_iterator_base& __x, const _Node_iterator_base& __y) + noexcept + { return __x._M_cur != __y._M_cur; } + }; /// Node iterators, used to iterate through all the hashtable. template::type; _Node_iterator() noexcept - : __base_type(0) { } + : __base_type(nullptr) { } explicit _Node_iterator(__node_type* __p) noexcept @@ -394,7 +391,7 @@ namespace __detail typedef const _Value& reference; _Node_const_iterator() noexcept - : __base_type(0) { } + : __base_type(nullptr) { } explicit _Node_const_iterator(__node_type* __p) noexcept @@ -1426,9 +1423,11 @@ namespace __detail struct _Local_iterator_base<_Key, _Value, _ExtractKey, _H1, _H2, _Hash, __hash_cached_t> : private _Hashtable_ebo_helper<0, _H2> + , _Node_iterator_base<_Value, __hash_cached_t> { protected: using __base_type = _Hashtable_ebo_helper<0, _H2>; + using __base_node_iter = _Node_iterator_base<_Value, __hash_cached_t>; using __hash_code_base = _Hash_code_base<_Key, _Value, _ExtractKey, _H1, _H2, _Hash, __hash_cached_t>; @@ -1437,31 +1436,27 @@ namespace __detail _Local_iterator_base(const __hash_code_base& __base, _Hash_node<_Value, __hash_cached_t>* __p, std::size_t __bkt, std::size_t __bkt_count) - : __base_type(__base._M_h2()), - _M_cur(__p), _M_bucket(__bkt), _M_bucket_count(__bkt_count) { } + : __base_type(__base._M_h2()), __base_node_iter(__p) + , _M_bucket(__bkt), _M_bucket_count(__bkt_count) { } void _M_incr() { - _M_cur = _M_cur->_M_next(); - if (_M_cur) + __base_node_iter::_M_incr(); + if (this->_M_cur) { std::size_t __bkt - = __base_type::_M_get()(_M_cur->_M_hash_code, - _M_bucket_count); + = __base_type::_M_get()(this->_M_cur->_M_hash_code, + _M_bucket_count); if (__bkt != _M_bucket) - _M_cur = nullptr; + this->_M_cur = nullptr; } } - _Hash_node<_Value, __hash_cached_t>* _M_cur; std::size_t _M_bucket; std::size_t _M_bucket_count; public: - const void* - _M_curr() const { return _M_cur; } // for equality ops - std::size_t _M_get_bucket() const { return _M_bucket; } // for debug mode }; @@ -1510,18 +1505,20 @@ namespace __detail struct _Local_iterator_base<_Key, _Value, _ExtractKey, _H1, _H2, _Hash, __hash_not_cached_t> : __hash_code_for_local_iter<_Key, _Value, _ExtractKey, _H1, _H2, _Hash> + , _Node_iterator_base<_Value, __hash_not_cached_t> { protected: using __hash_code_base = _Hash_code_base<_Key, _Value, _ExtractKey, _H1, _H2, _Hash, __hash_not_cached_t>; + using __node_iter_base = _Node_iterator_base<_Value, __hash_not_cached_t>; _Local_iterator_base() : _M_bucket_count(-1) { } _Local_iterator_base(const __hash_code_base& __base, _Hash_node<_Value, __hash_not_cached_t>* __p, std::size_t __bkt, std::size_t __bkt_count) - : _M_cur(__p), _M_bucket(__bkt), _M_bucket_count(__bkt_count) + : __node_iter_base(__p), _M_bucket(__bkt), _M_bucket_count(__bkt_count) { _M_init(__base); } ~_Local_iterator_base() @@ -1531,8 +1528,8 @@ namespace __detail } _Local_iterator_base(const _Local_iterator_base& __iter) - : _M_cur(__iter._M_cur), _M_bucket(__iter._M_bucket), - _M_bucket_count(__iter._M_bucket_count) + : __node_iter_base(__iter), _M_bucket(__iter._M_bucket) + , _M_bucket_count(__iter._M_bucket_count) { if (_M_bucket_count != -1) _M_init(*__iter._M_h()); @@ -1543,7 +1540,7 @@ namespace __detail { if (_M_bucket_count != -1) _M_destroy(); - _M_cur = __iter._M_cur; + this->_M_cur = __iter._M_cur; _M_bucket = __iter._M_bucket; _M_bucket_count = __iter._M_bucket_count; if (_M_bucket_count != -1) @@ -1554,17 +1551,16 @@ namespace __detail void _M_incr() { - _M_cur = _M_cur->_M_next(); - if (_M_cur) + __node_iter_base::_M_incr(); + if (this->_M_cur) { - std::size_t __bkt = this->_M_h()->_M_bucket_index(_M_cur, + std::size_t __bkt = this->_M_h()->_M_bucket_index(this->_M_cur, _M_bucket_count); if (__bkt != _M_bucket) - _M_cur = nullptr; + this->_M_cur = nullptr; } } - _Hash_node<_Value, __hash_not_cached_t>* _M_cur; std::size_t _M_bucket; std::size_t _M_bucket_count; @@ -1576,33 +1572,10 @@ namespace __detail _M_destroy() { this->_M_h()->~__hash_code_base(); } public: - const void* - _M_curr() const { return _M_cur; } // for equality ops and debug mode - std::size_t _M_get_bucket() const { return _M_bucket; } // for debug mode }; - template - inline bool - operator==(const _Local_iterator_base<_Key, _Value, _ExtractKey, - _H1, _H2, _Hash, _Cache_hash_code>& __x, - const _Local_iterator_base<_Key, _Value, _ExtractKey, - _H1, _H2, _Hash, _Cache_hash_code>& __y) - { return __x._M_curr() == __y._M_curr(); } - - template - inline bool - operator!=(const _Local_iterator_base<_Key, _Value, _ExtractKey, - _H1, _H2, _Hash, _Cache_hash_code>& __x, - const _Local_iterator_base<_Key, _Value, _ExtractKey, - _H1, _H2, _Hash, _Cache_hash_code>& __y) - { return __x._M_curr() != __y._M_curr(); } - /// local iterators template; using __hash_code_base = typename __base_type::__hash_code_base; + public: typedef _Value value_type; typedef typename std::conditional<_Constant_iterators::value, diff --git a/libstdc++-v3/include/debug/unordered_map b/libstdc++-v3/include/debug/unordered_map index d844ee9fa0e..157349ea4f9 100644 --- a/libstdc++-v3/include/debug/unordered_map +++ b/libstdc++-v3/include/debug/unordered_map @@ -621,7 +621,7 @@ namespace __debug [__victim](_Base_const_iterator __it) { return __it == __victim; }); this->_M_invalidate_local_if( [__victim](_Base_const_local_iterator __it) - { return __it._M_curr() == __victim._M_cur; }); + { return __it == __victim; }); } _Base_iterator @@ -1227,7 +1227,7 @@ namespace __debug [__victim](_Base_const_iterator __it) { return __it == __victim; }); this->_M_invalidate_local_if( [__victim](_Base_const_local_iterator __it) - { return __it._M_curr() == __victim._M_cur; }); + { return __it == __victim; }); } _Base_iterator diff --git a/libstdc++-v3/include/debug/unordered_set b/libstdc++-v3/include/debug/unordered_set index ecc084e3846..924ff7671ee 100644 --- a/libstdc++-v3/include/debug/unordered_set +++ b/libstdc++-v3/include/debug/unordered_set @@ -506,7 +506,7 @@ namespace __debug [__victim](_Base_const_iterator __it) { return __it == __victim; }); this->_M_invalidate_local_if( [__victim](_Base_const_local_iterator __it) - { return __it._M_curr() == __victim._M_cur; }); + { return __it == __victim; }); } _Base_iterator @@ -1066,7 +1066,7 @@ namespace __debug [__victim](_Base_const_iterator __it) { return __it == __victim; }); this->_M_invalidate_local_if( [__victim](_Base_const_local_iterator __it) - { return __it._M_curr() == __victim._M_cur; }); + { return __it == __victim; }); } _Base_iterator