libstdc++
|
00001 // Profiling unordered containers implementation details -*- C++ -*- 00002 00003 // Copyright (C) 2013 Free Software Foundation, Inc. 00004 // 00005 // This file is part of the GNU ISO C++ Library. This library is free 00006 // software; you can redistribute it and/or modify it under the 00007 // terms of the GNU General Public License as published by the 00008 // Free Software Foundation; either version 3, or (at your option) 00009 // any later version. 00010 // 00011 // This library is distributed in the hope that it will be useful, 00012 // but WITHOUT ANY WARRANTY; without even the implied warranty of 00013 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 00014 // GNU General Public License for more details. 00015 00016 // Under Section 7 of GPL version 3, you are granted additional 00017 // permissions described in the GCC Runtime Library Exception, version 00018 // 3.1, as published by the Free Software Foundation. 00019 00020 // You should have received a copy of the GNU General Public License along 00021 // with this library; see the file COPYING3. If not see 00022 // <http://www.gnu.org/licenses/>. 00023 00024 /** @file profile/unordered_base.h 00025 * This file is a GNU profile extension to the Standard C++ Library. 00026 */ 00027 00028 #ifndef _GLIBCXX_PROFILE_UNORDERED 00029 #define _GLIBCXX_PROFILE_UNORDERED 1 00030 00031 namespace std _GLIBCXX_VISIBILITY(default) 00032 { 00033 namespace __profile 00034 { 00035 template<typename _UnorderedCont, 00036 typename _Value, bool _Cache_hash_code> 00037 struct _Bucket_index_helper; 00038 00039 template<typename _UnorderedCont, typename _Value> 00040 struct _Bucket_index_helper<_UnorderedCont, _Value, true> 00041 { 00042 static std::size_t 00043 bucket(const _UnorderedCont& __uc, 00044 const __detail::_Hash_node<_Value, true>* __node) 00045 { return __node->_M_hash_code % __uc.bucket_count(); } 00046 }; 00047 00048 template<typename _UnorderedCont, typename _Value> 00049 struct _Bucket_index_helper<_UnorderedCont, _Value, false> 00050 { 00051 static std::size_t 00052 bucket(const _UnorderedCont& __uc, 00053 const __detail::_Hash_node<_Value, false>* __node) 00054 { return __uc.bucket(__node->_M_v); } 00055 }; 00056 00057 template<typename _UnorderedCont, typename _Key, typename _Mapped> 00058 struct _Bucket_index_helper<_UnorderedCont, 00059 std::pair<const _Key, _Mapped>, false> 00060 { 00061 typedef std::pair<const _Key, _Mapped> _Value; 00062 00063 static std::size_t 00064 bucket(const _UnorderedCont& __uc, 00065 const __detail::_Hash_node<_Value, false>* __node) 00066 { return __uc.bucket(__node->_M_v.first); } 00067 }; 00068 00069 template<typename _UnorderedCont, typename _Value, bool _Cache_hash_code> 00070 std::size_t 00071 __get_bucket_index(const _UnorderedCont& __uc, 00072 const __detail::_Hash_node<_Value, _Cache_hash_code>* __node) 00073 { 00074 using __bucket_index_helper 00075 = _Bucket_index_helper<_UnorderedCont, _Value, _Cache_hash_code>; 00076 return __bucket_index_helper::bucket(__uc, __node); 00077 } 00078 00079 template<typename _UnorderedCont, 00080 typename _Value, bool _Cache_hash_code> 00081 struct _Equal_helper; 00082 00083 template<typename _UnorderedCont, typename _Value> 00084 struct _Equal_helper<_UnorderedCont, _Value, true> 00085 { 00086 static std::size_t 00087 are_equal(const _UnorderedCont& __uc, 00088 const __detail::_Hash_node<_Value, true>* __lhs, 00089 const __detail::_Hash_node<_Value, true>* __rhs) 00090 { 00091 return __lhs->_M_hash_code == __rhs->_M_hash_code 00092 && __uc.key_eq()(__lhs->_M_v, __rhs->_M_v); 00093 } 00094 }; 00095 00096 template<typename _UnorderedCont, 00097 typename _Value> 00098 struct _Equal_helper<_UnorderedCont, _Value, false> 00099 { 00100 static std::size_t 00101 are_equal(const _UnorderedCont& __uc, 00102 const __detail::_Hash_node<_Value, false>* __lhs, 00103 const __detail::_Hash_node<_Value, false>* __rhs) 00104 { return __uc.key_eq()(__lhs->_M_v, __rhs->_M_v); } 00105 }; 00106 00107 template<typename _UnorderedCont, 00108 typename _Key, typename _Mapped> 00109 struct _Equal_helper<_UnorderedCont, std::pair<const _Key, _Mapped>, true> 00110 { 00111 typedef std::pair<const _Key, _Mapped> _Value; 00112 00113 static std::size_t 00114 are_equal(const _UnorderedCont& __uc, 00115 const __detail::_Hash_node<_Value, true>* __lhs, 00116 const __detail::_Hash_node<_Value, true>* __rhs) 00117 { 00118 return __lhs->_M_hash_code == __rhs->_M_hash_code 00119 && __uc.key_eq()(__lhs->_M_v.first, __rhs->_M_v.first); 00120 } 00121 }; 00122 00123 template<typename _UnorderedCont, 00124 typename _Key, typename _Mapped> 00125 struct _Equal_helper<_UnorderedCont, std::pair<const _Key, _Mapped>, false> 00126 { 00127 typedef std::pair<const _Key, _Mapped> _Value; 00128 00129 static std::size_t 00130 are_equal(const _UnorderedCont& __uc, 00131 const __detail::_Hash_node<_Value, false>* __lhs, 00132 const __detail::_Hash_node<_Value, false>* __rhs) 00133 { return __uc.key_eq()(__lhs->_M_v.first, __rhs->_M_v.first); } 00134 }; 00135 00136 template<typename _UnorderedCont, typename _Value, bool _Cache_hash_code> 00137 bool 00138 __are_equal(const _UnorderedCont& __uc, 00139 const __detail::_Hash_node<_Value, _Cache_hash_code>* __lhs, 00140 const __detail::_Hash_node<_Value, _Cache_hash_code>* __rhs) 00141 { 00142 using __equal_helper 00143 = _Equal_helper<_UnorderedCont, _Value, _Cache_hash_code>; 00144 return __equal_helper::are_equal(__uc, __lhs, __rhs); 00145 } 00146 00147 template<typename _UnorderedCont, bool _Unique_keys> 00148 class _Unordered_profile 00149 { 00150 _UnorderedCont& 00151 _M_conjure() 00152 { return *(static_cast<_UnorderedCont*>(this)); } 00153 00154 using __unique_keys = std::integral_constant<bool, _Unique_keys>; 00155 00156 protected: 00157 _Unordered_profile() 00158 { 00159 auto& __uc = _M_conjure(); 00160 __profcxx_hashtable_construct(&__uc, __uc.bucket_count()); 00161 __profcxx_hashtable_construct2(&__uc); 00162 } 00163 _Unordered_profile(const _Unordered_profile&) 00164 : _Unordered_profile() { } 00165 _Unordered_profile(_Unordered_profile&&) 00166 : _Unordered_profile() { } 00167 00168 ~_Unordered_profile() noexcept 00169 { 00170 auto& __uc = _M_conjure(); 00171 __profcxx_hashtable_destruct(&__uc, __uc.bucket_count(), __uc.size()); 00172 _M_profile_destruct(); 00173 } 00174 00175 _Unordered_profile& 00176 operator=(const _Unordered_profile&) = default; 00177 00178 _Unordered_profile& 00179 operator=(_Unordered_profile&&) = default; 00180 00181 void 00182 _M_profile_destruct() 00183 { 00184 if (!__profcxx_inefficient_hash_is_on()) 00185 return; 00186 00187 _M_profile_destruct(__unique_keys()); 00188 } 00189 00190 private: 00191 void 00192 _M_profile_destruct(std::true_type); 00193 00194 void 00195 _M_profile_destruct(std::false_type); 00196 }; 00197 00198 template<typename _UnorderedCont, bool _Unique_keys> 00199 void 00200 _Unordered_profile<_UnorderedCont, _Unique_keys>:: 00201 _M_profile_destruct(std::true_type) 00202 { 00203 auto& __uc = _M_conjure(); 00204 std::size_t __hops = 0, __lc = 0, __chain = 0; 00205 auto __it = __uc.begin(); 00206 while (__it != __uc.end()) 00207 { 00208 auto __bkt = __get_bucket_index(__uc, __it._M_cur); 00209 auto __lit = __uc.begin(__bkt); 00210 auto __lend = __uc.end(__bkt); 00211 for (++__it, ++__lit; __lit != __lend; ++__it, ++__lit) 00212 ++__chain; 00213 if (__chain) 00214 { 00215 ++__chain; 00216 __lc = __lc > __chain ? __lc : __chain; 00217 __hops += __chain * (__chain - 1) / 2; 00218 __chain = 0; 00219 } 00220 } 00221 __profcxx_hashtable_destruct2(&__uc, __lc, __uc.size(), __hops); 00222 } 00223 00224 template<typename _UnorderedCont, bool _Unique_keys> 00225 void 00226 _Unordered_profile<_UnorderedCont, _Unique_keys>:: 00227 _M_profile_destruct(std::false_type) 00228 { 00229 auto& __uc = _M_conjure(); 00230 std::size_t __hops = 0, __lc = 0, __chain = 0, __unique_size = 0; 00231 auto __it = __uc.begin(); 00232 while (__it != __uc.end()) 00233 { 00234 auto __bkt = __get_bucket_index(__uc, __it._M_cur); 00235 auto __lit = __uc.begin(__bkt); 00236 auto __lend = __uc.end(__bkt); 00237 auto __pit = __it; 00238 ++__unique_size; 00239 for (++__it, ++__lit; __lit != __lend; ++__it, ++__lit) 00240 { 00241 if (!__are_equal(__uc, __pit._M_cur, __it._M_cur)) 00242 { 00243 ++__chain; 00244 ++__unique_size; 00245 __pit = __it; 00246 } 00247 } 00248 if (__chain) 00249 { 00250 ++__chain; 00251 __lc = __lc > __chain ? __lc : __chain; 00252 __hops += __chain * (__chain - 1) / 2; 00253 __chain = 0; 00254 } 00255 } 00256 __profcxx_hashtable_destruct2(&__uc, __lc, __unique_size, __hops); 00257 } 00258 00259 } // namespace __profile 00260 } // namespace std 00261 00262 #endif