libstdc++
|
00001 // Profiling unordered containers implementation details -*- C++ -*- 00002 00003 // Copyright (C) 2013-2015 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() noexcept 00158 { _M_profile_construct(); } 00159 00160 _Unordered_profile(const _Unordered_profile&) noexcept 00161 : _Unordered_profile() { } 00162 00163 _Unordered_profile(_Unordered_profile&& __other) noexcept 00164 : _Unordered_profile() 00165 { _M_swap(__other); } 00166 00167 ~_Unordered_profile() 00168 { _M_profile_destruct(); } 00169 00170 _Unordered_profile& 00171 operator=(const _Unordered_profile&) noexcept 00172 { 00173 // Assignment just reset profiling. 00174 _M_profile_destruct(); 00175 _M_profile_construct(); 00176 } 00177 00178 _Unordered_profile& 00179 operator=(_Unordered_profile&& __other) noexcept 00180 { 00181 // Take profiling of the moved instance... 00182 _M_swap(__other); 00183 00184 // ...and then reset other instance profiling. 00185 __other._M_profile_destruct(); 00186 __other._M_profile_construct(); 00187 } 00188 00189 void 00190 _M_profile_construct() noexcept 00191 { 00192 auto& __uc = _M_conjure(); 00193 _M_size_info = __profcxx_hashtable_size_construct(__uc.bucket_count()); 00194 _M_hashfunc_info = __profcxx_hash_func_construct(); 00195 } 00196 00197 void 00198 _M_profile_destruct() noexcept 00199 { 00200 auto& __uc = _M_conjure(); 00201 __profcxx_hashtable_size_destruct(_M_size_info, 00202 __uc.bucket_count(), __uc.size()); 00203 _M_size_info = 0; 00204 00205 if (!_M_hashfunc_info) 00206 return; 00207 00208 _M_profile_destruct(__unique_keys()); 00209 _M_hashfunc_info = 0; 00210 } 00211 00212 void 00213 _M_swap(_Unordered_profile& __other) noexcept 00214 { 00215 std::swap(_M_size_info, __other._M_size_info); 00216 std::swap(_M_hashfunc_info, __other._M_hashfunc_info); 00217 } 00218 00219 void 00220 _M_profile_resize(std::size_t __old_size) 00221 { 00222 auto __new_size = _M_conjure().bucket_count(); 00223 if (__old_size != __new_size) 00224 __profcxx_hashtable_size_resize(_M_size_info, __old_size, __new_size); 00225 } 00226 00227 __gnu_profile::__container_size_info* _M_size_info; 00228 __gnu_profile::__hashfunc_info* _M_hashfunc_info; 00229 00230 private: 00231 void 00232 _M_profile_destruct(std::true_type); 00233 00234 void 00235 _M_profile_destruct(std::false_type); 00236 }; 00237 00238 template<typename _UnorderedCont, bool _Unique_keys> 00239 void 00240 _Unordered_profile<_UnorderedCont, _Unique_keys>:: 00241 _M_profile_destruct(std::true_type) 00242 { 00243 auto& __uc = _M_conjure(); 00244 std::size_t __hops = 0, __lc = 0, __chain = 0; 00245 auto __it = __uc.begin(); 00246 while (__it != __uc.end()) 00247 { 00248 auto __bkt = __get_bucket_index(__uc, __it._M_cur); 00249 auto __lit = __uc.begin(__bkt); 00250 auto __lend = __uc.end(__bkt); 00251 for (++__it, ++__lit; __lit != __lend; ++__it, ++__lit) 00252 ++__chain; 00253 00254 if (__chain) 00255 { 00256 ++__chain; 00257 __lc = __lc > __chain ? __lc : __chain; 00258 __hops += __chain * (__chain - 1) / 2; 00259 __chain = 0; 00260 } 00261 } 00262 00263 __profcxx_hash_func_destruct(_M_hashfunc_info, 00264 __lc, __uc.size(), __hops); 00265 } 00266 00267 template<typename _UnorderedCont, bool _Unique_keys> 00268 void 00269 _Unordered_profile<_UnorderedCont, _Unique_keys>:: 00270 _M_profile_destruct(std::false_type) 00271 { 00272 auto& __uc = _M_conjure(); 00273 std::size_t __hops = 0, __lc = 0, __chain = 0, __unique_size = 0; 00274 auto __it = __uc.begin(); 00275 while (__it != __uc.end()) 00276 { 00277 auto __bkt = __get_bucket_index(__uc, __it._M_cur); 00278 auto __lit = __uc.begin(__bkt); 00279 auto __lend = __uc.end(__bkt); 00280 auto __pit = __it; 00281 ++__unique_size; 00282 for (++__it, ++__lit; __lit != __lend; ++__it, ++__lit) 00283 { 00284 if (!__are_equal(__uc, __pit._M_cur, __it._M_cur)) 00285 { 00286 ++__chain; 00287 ++__unique_size; 00288 __pit = __it; 00289 } 00290 } 00291 00292 if (__chain) 00293 { 00294 ++__chain; 00295 __lc = __lc > __chain ? __lc : __chain; 00296 __hops += __chain * (__chain - 1) / 2; 00297 __chain = 0; 00298 } 00299 } 00300 00301 __profcxx_hash_func_destruct(_M_hashfunc_info, 00302 __lc, __unique_size, __hops); 00303 } 00304 00305 } // namespace __profile 00306 } // namespace std 00307 00308 #endif