111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// Profiling unordered containers implementation details -*- C++ -*- 211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// Copyright (C) 2013-2014 Free Software Foundation, Inc. 411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// 511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// This file is part of the GNU ISO C++ Library. This library is free 611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// software; you can redistribute it and/or modify it under the 711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// terms of the GNU General Public License as published by the 811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// Free Software Foundation; either version 3, or (at your option) 911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// any later version. 1011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// 1111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// This library is distributed in the hope that it will be useful, 1211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// but WITHOUT ANY WARRANTY; without even the implied warranty of 1311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 1411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// GNU General Public License for more details. 1511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 1611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// Under Section 7 of GPL version 3, you are granted additional 1711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// permissions described in the GCC Runtime Library Exception, version 1811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// 3.1, as published by the Free Software Foundation. 1911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 2011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// You should have received a copy of the GNU General Public License along 2111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// with this library; see the file COPYING3. If not see 2211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// <http://www.gnu.org/licenses/>. 2311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 2411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert/** @file profile/unordered_base.h 2511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * This file is a GNU profile extension to the Standard C++ Library. 2611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert */ 2711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 2811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#ifndef _GLIBCXX_PROFILE_UNORDERED 2911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#define _GLIBCXX_PROFILE_UNORDERED 1 3011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 3111cd02dfb91661c65134cac258cf5924270e9d2Dan Albertnamespace std _GLIBCXX_VISIBILITY(default) 3211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert{ 3311cd02dfb91661c65134cac258cf5924270e9d2Dan Albertnamespace __profile 3411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert{ 3511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert template<typename _UnorderedCont, 3611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typename _Value, bool _Cache_hash_code> 3711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert struct _Bucket_index_helper; 3811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 3911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert template<typename _UnorderedCont, typename _Value> 4011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert struct _Bucket_index_helper<_UnorderedCont, _Value, true> 4111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 4211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert static std::size_t 4311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert bucket(const _UnorderedCont& __uc, 4411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert const __detail::_Hash_node<_Value, true>* __node) 4511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { return __node->_M_hash_code % __uc.bucket_count(); } 4611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert }; 4711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 4811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert template<typename _UnorderedCont, typename _Value> 4911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert struct _Bucket_index_helper<_UnorderedCont, _Value, false> 5011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 5111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert static std::size_t 5211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert bucket(const _UnorderedCont& __uc, 5311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert const __detail::_Hash_node<_Value, false>* __node) 5411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { return __uc.bucket(__node->_M_v()); } 5511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert }; 5611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 5711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert template<typename _UnorderedCont, typename _Key, typename _Mapped> 5811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert struct _Bucket_index_helper<_UnorderedCont, 5911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert std::pair<const _Key, _Mapped>, false> 6011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 6111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef std::pair<const _Key, _Mapped> _Value; 6211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 6311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert static std::size_t 6411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert bucket(const _UnorderedCont& __uc, 6511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert const __detail::_Hash_node<_Value, false>* __node) 6611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { return __uc.bucket(__node->_M_v().first); } 6711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert }; 6811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 6911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert template<typename _UnorderedCont, typename _Value, bool _Cache_hash_code> 7011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert std::size_t 7111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __get_bucket_index(const _UnorderedCont& __uc, 7211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert const __detail::_Hash_node<_Value, _Cache_hash_code>* __node) 7311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 7411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert using __bucket_index_helper 7511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert = _Bucket_index_helper<_UnorderedCont, _Value, _Cache_hash_code>; 7611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert return __bucket_index_helper::bucket(__uc, __node); 7711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 7811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 7911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert template<typename _UnorderedCont, 8011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typename _Value, bool _Cache_hash_code> 8111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert struct _Equal_helper; 8211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 8311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert template<typename _UnorderedCont, typename _Value> 8411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert struct _Equal_helper<_UnorderedCont, _Value, true> 8511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 8611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert static std::size_t 8711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert are_equal(const _UnorderedCont& __uc, 8811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert const __detail::_Hash_node<_Value, true>* __lhs, 8911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert const __detail::_Hash_node<_Value, true>* __rhs) 9011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 9111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert return __lhs->_M_hash_code == __rhs->_M_hash_code 9211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert && __uc.key_eq()(__lhs->_M_v(), __rhs->_M_v()); 9311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 9411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert }; 9511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 9611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert template<typename _UnorderedCont, 9711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typename _Value> 9811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert struct _Equal_helper<_UnorderedCont, _Value, false> 9911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 10011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert static std::size_t 10111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert are_equal(const _UnorderedCont& __uc, 10211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert const __detail::_Hash_node<_Value, false>* __lhs, 10311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert const __detail::_Hash_node<_Value, false>* __rhs) 10411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { return __uc.key_eq()(__lhs->_M_v(), __rhs->_M_v()); } 10511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert }; 10611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 10711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert template<typename _UnorderedCont, 10811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typename _Key, typename _Mapped> 10911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert struct _Equal_helper<_UnorderedCont, std::pair<const _Key, _Mapped>, true> 11011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 11111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef std::pair<const _Key, _Mapped> _Value; 11211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 11311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert static std::size_t 11411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert are_equal(const _UnorderedCont& __uc, 11511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert const __detail::_Hash_node<_Value, true>* __lhs, 11611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert const __detail::_Hash_node<_Value, true>* __rhs) 11711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 11811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert return __lhs->_M_hash_code == __rhs->_M_hash_code 11911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert && __uc.key_eq()(__lhs->_M_v().first, __rhs->_M_v().first); 12011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 12111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert }; 12211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 12311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert template<typename _UnorderedCont, 12411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typename _Key, typename _Mapped> 12511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert struct _Equal_helper<_UnorderedCont, std::pair<const _Key, _Mapped>, false> 12611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 12711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef std::pair<const _Key, _Mapped> _Value; 12811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 12911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert static std::size_t 13011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert are_equal(const _UnorderedCont& __uc, 13111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert const __detail::_Hash_node<_Value, false>* __lhs, 13211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert const __detail::_Hash_node<_Value, false>* __rhs) 13311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { return __uc.key_eq()(__lhs->_M_v().first, __rhs->_M_v().first); } 13411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert }; 13511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 13611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert template<typename _UnorderedCont, typename _Value, bool _Cache_hash_code> 13711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert bool 13811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __are_equal(const _UnorderedCont& __uc, 13911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert const __detail::_Hash_node<_Value, _Cache_hash_code>* __lhs, 14011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert const __detail::_Hash_node<_Value, _Cache_hash_code>* __rhs) 14111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 14211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert using __equal_helper 14311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert = _Equal_helper<_UnorderedCont, _Value, _Cache_hash_code>; 14411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert return __equal_helper::are_equal(__uc, __lhs, __rhs); 14511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 14611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 14711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert template<typename _UnorderedCont, bool _Unique_keys> 14811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert class _Unordered_profile 14911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 15011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _UnorderedCont& 15111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _M_conjure() 15211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { return *(static_cast<_UnorderedCont*>(this)); } 15311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 15411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert using __unique_keys = std::integral_constant<bool, _Unique_keys>; 15511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 15611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert protected: 15711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _Unordered_profile() 15811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 15911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert auto& __uc = _M_conjure(); 16011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __profcxx_hashtable_construct(&__uc, __uc.bucket_count()); 16111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __profcxx_hashtable_construct2(&__uc); 16211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 16311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _Unordered_profile(const _Unordered_profile&) 16411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert : _Unordered_profile() { } 16511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _Unordered_profile(_Unordered_profile&&) 16611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert : _Unordered_profile() { } 16711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 16811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert ~_Unordered_profile() noexcept 16911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 17011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert auto& __uc = _M_conjure(); 17111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __profcxx_hashtable_destruct(&__uc, __uc.bucket_count(), __uc.size()); 17211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _M_profile_destruct(); 17311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 17411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 17511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _Unordered_profile& 17611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert operator=(const _Unordered_profile&) = default; 17711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 17811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _Unordered_profile& 17911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert operator=(_Unordered_profile&&) = default; 18011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 18111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert void 18211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _M_profile_destruct() 18311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 18411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert if (!__profcxx_inefficient_hash_is_on()) 18511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert return; 18611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 18711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _M_profile_destruct(__unique_keys()); 18811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 18911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 19011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert private: 19111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert void 19211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _M_profile_destruct(std::true_type); 19311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 19411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert void 19511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _M_profile_destruct(std::false_type); 19611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert }; 19711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 19811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert template<typename _UnorderedCont, bool _Unique_keys> 19911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert void 20011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _Unordered_profile<_UnorderedCont, _Unique_keys>:: 20111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _M_profile_destruct(std::true_type) 20211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 20311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert auto& __uc = _M_conjure(); 20411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert std::size_t __hops = 0, __lc = 0, __chain = 0; 20511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert auto __it = __uc.begin(); 20611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert while (__it != __uc.end()) 20711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 20811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert auto __bkt = __get_bucket_index(__uc, __it._M_cur); 20911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert auto __lit = __uc.begin(__bkt); 21011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert auto __lend = __uc.end(__bkt); 21111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert for (++__it, ++__lit; __lit != __lend; ++__it, ++__lit) 21211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert ++__chain; 21311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert if (__chain) 21411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 21511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert ++__chain; 21611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __lc = __lc > __chain ? __lc : __chain; 21711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __hops += __chain * (__chain - 1) / 2; 21811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __chain = 0; 21911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 22011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 22111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __profcxx_hashtable_destruct2(&__uc, __lc, __uc.size(), __hops); 22211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 22311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 22411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert template<typename _UnorderedCont, bool _Unique_keys> 22511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert void 22611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _Unordered_profile<_UnorderedCont, _Unique_keys>:: 22711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _M_profile_destruct(std::false_type) 22811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 22911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert auto& __uc = _M_conjure(); 23011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert std::size_t __hops = 0, __lc = 0, __chain = 0, __unique_size = 0; 23111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert auto __it = __uc.begin(); 23211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert while (__it != __uc.end()) 23311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 23411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert auto __bkt = __get_bucket_index(__uc, __it._M_cur); 23511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert auto __lit = __uc.begin(__bkt); 23611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert auto __lend = __uc.end(__bkt); 23711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert auto __pit = __it; 23811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert ++__unique_size; 23911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert for (++__it, ++__lit; __lit != __lend; ++__it, ++__lit) 24011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 24111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert if (!__are_equal(__uc, __pit._M_cur, __it._M_cur)) 24211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 24311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert ++__chain; 24411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert ++__unique_size; 24511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __pit = __it; 24611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 24711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 24811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert if (__chain) 24911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 25011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert ++__chain; 25111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __lc = __lc > __chain ? __lc : __chain; 25211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __hops += __chain * (__chain - 1) / 2; 25311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __chain = 0; 25411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 25511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 25611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __profcxx_hashtable_destruct2(&__uc, __lc, __unique_size, __hops); 25711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 25811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 25911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert} // namespace __profile 26011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert} // namespace std 26111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 26211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#endif 263