1 // Profiling unordered containers implementation details -*- C++ -*- 2 3 // Copyright (C) 2013-2019 Free Software Foundation, Inc. 4 // 5 // This file is part of the GNU ISO C++ Library. This library is free 6 // software; you can redistribute it and/or modify it under the 7 // terms of the GNU General Public License as published by the 8 // Free Software Foundation; either version 3, or (at your option) 9 // any later version. 10 // 11 // This library is distributed in the hope that it will be useful, 12 // but WITHOUT ANY WARRANTY; without even the implied warranty of 13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 14 // GNU General Public License for more details. 15 16 // Under Section 7 of GPL version 3, you are granted additional 17 // permissions described in the GCC Runtime Library Exception, version 18 // 3.1, as published by the Free Software Foundation. 19 20 // You should have received a copy of the GNU General Public License along 21 // with this library; see the file COPYING3. If not see 22 // <http://www.gnu.org/licenses/>. 23 24 /** @file profile/unordered_base.h 25 * This file is a GNU profile extension to the Standard C++ Library. 26 */ 27 28 #ifndef _GLIBCXX_PROFILE_UNORDERED 29 #define _GLIBCXX_PROFILE_UNORDERED 1 30 31 namespace std _GLIBCXX_VISIBILITY(default) 32 { 33 namespace __profile 34 { 35 template<typename _UnorderedCont, 36 typename _Value, bool _Cache_hash_code> 37 struct _Bucket_index_helper; 38 39 template<typename _UnorderedCont, typename _Value> 40 struct _Bucket_index_helper<_UnorderedCont, _Value, true> 41 { 42 static std::size_t 43 bucket(const _UnorderedCont& __uc, 44 const __detail::_Hash_node<_Value, true>* __node) 45 { return __node->_M_hash_code % __uc.bucket_count(); } 46 }; 47 48 template<typename _UnorderedCont, typename _Value> 49 struct _Bucket_index_helper<_UnorderedCont, _Value, false> 50 { 51 static std::size_t 52 bucket(const _UnorderedCont& __uc, 53 const __detail::_Hash_node<_Value, false>* __node) 54 { return __uc.bucket(__node->_M_v()); } 55 }; 56 57 template<typename _UnorderedCont, typename _Key, typename _Mapped> 58 struct _Bucket_index_helper<_UnorderedCont, 59 std::pair<const _Key, _Mapped>, false> 60 { 61 typedef std::pair<const _Key, _Mapped> _Value; 62 63 static std::size_t 64 bucket(const _UnorderedCont& __uc, 65 const __detail::_Hash_node<_Value, false>* __node) 66 { return __uc.bucket(__node->_M_v().first); } 67 }; 68 69 template<typename _UnorderedCont, typename _Value, bool _Cache_hash_code> 70 std::size_t 71 __get_bucket_index(const _UnorderedCont& __uc, 72 const __detail::_Hash_node<_Value, _Cache_hash_code>* __node) 73 { 74 using __bucket_index_helper 75 = _Bucket_index_helper<_UnorderedCont, _Value, _Cache_hash_code>; 76 return __bucket_index_helper::bucket(__uc, __node); 77 } 78 79 template<typename _UnorderedCont, 80 typename _Value, bool _Cache_hash_code> 81 struct _Equal_helper; 82 83 template<typename _UnorderedCont, typename _Value> 84 struct _Equal_helper<_UnorderedCont, _Value, true> 85 { 86 static std::size_t 87 are_equal(const _UnorderedCont& __uc, 88 const __detail::_Hash_node<_Value, true>* __lhs, 89 const __detail::_Hash_node<_Value, true>* __rhs) 90 { 91 return __lhs->_M_hash_code == __rhs->_M_hash_code 92 && __uc.key_eq()(__lhs->_M_v(), __rhs->_M_v()); 93 } 94 }; 95 96 template<typename _UnorderedCont, 97 typename _Value> 98 struct _Equal_helper<_UnorderedCont, _Value, false> 99 { 100 static std::size_t 101 are_equal(const _UnorderedCont& __uc, 102 const __detail::_Hash_node<_Value, false>* __lhs, 103 const __detail::_Hash_node<_Value, false>* __rhs) 104 { return __uc.key_eq()(__lhs->_M_v(), __rhs->_M_v()); } 105 }; 106 107 template<typename _UnorderedCont, 108 typename _Key, typename _Mapped> 109 struct _Equal_helper<_UnorderedCont, std::pair<const _Key, _Mapped>, true> 110 { 111 typedef std::pair<const _Key, _Mapped> _Value; 112 113 static std::size_t 114 are_equal(const _UnorderedCont& __uc, 115 const __detail::_Hash_node<_Value, true>* __lhs, 116 const __detail::_Hash_node<_Value, true>* __rhs) 117 { 118 return __lhs->_M_hash_code == __rhs->_M_hash_code 119 && __uc.key_eq()(__lhs->_M_v().first, __rhs->_M_v().first); 120 } 121 }; 122 123 template<typename _UnorderedCont, 124 typename _Key, typename _Mapped> 125 struct _Equal_helper<_UnorderedCont, std::pair<const _Key, _Mapped>, false> 126 { 127 typedef std::pair<const _Key, _Mapped> _Value; 128 129 static std::size_t 130 are_equal(const _UnorderedCont& __uc, 131 const __detail::_Hash_node<_Value, false>* __lhs, 132 const __detail::_Hash_node<_Value, false>* __rhs) 133 { return __uc.key_eq()(__lhs->_M_v().first, __rhs->_M_v().first); } 134 }; 135 136 template<typename _UnorderedCont, typename _Value, bool _Cache_hash_code> 137 bool 138 __are_equal(const _UnorderedCont& __uc, 139 const __detail::_Hash_node<_Value, _Cache_hash_code>* __lhs, 140 const __detail::_Hash_node<_Value, _Cache_hash_code>* __rhs) 141 { 142 using __equal_helper 143 = _Equal_helper<_UnorderedCont, _Value, _Cache_hash_code>; 144 return __equal_helper::are_equal(__uc, __lhs, __rhs); 145 } 146 147 template<typename _UnorderedCont, bool _Unique_keys> 148 class _Unordered_profile 149 { 150 _UnorderedCont& 151 _M_conjure() 152 { return *(static_cast<_UnorderedCont*>(this)); } 153 154 using __unique_keys = std::integral_constant<bool, _Unique_keys>; 155 156 protected: 157 _Unordered_profile() noexcept 158 { _M_profile_construct(); } 159 160 _Unordered_profile(const _Unordered_profile&) noexcept 161 : _Unordered_profile() { } 162 163 _Unordered_profile(_Unordered_profile&& __other) noexcept 164 : _Unordered_profile() 165 { _M_swap(__other); } 166 167 ~_Unordered_profile() 168 { _M_profile_destruct(); } 169 170 _Unordered_profile& 171 operator=(const _Unordered_profile&) noexcept 172 { 173 // Assignment just reset profiling. 174 _M_profile_destruct(); 175 _M_profile_construct(); 176 } 177 178 _Unordered_profile& 179 operator=(_Unordered_profile&& __other) noexcept 180 { 181 // Take profiling of the moved instance... 182 _M_swap(__other); 183 184 // ...and then reset other instance profiling. 185 __other._M_profile_destruct(); 186 __other._M_profile_construct(); 187 } 188 189 void 190 _M_profile_construct() noexcept 191 { 192 auto& __uc = _M_conjure(); 193 _M_size_info = __profcxx_hashtable_size_construct(__uc.bucket_count()); 194 _M_hashfunc_info = __profcxx_hash_func_construct(); 195 } 196 197 void 198 _M_profile_destruct() noexcept 199 { 200 auto& __uc = _M_conjure(); 201 __profcxx_hashtable_size_destruct(_M_size_info, 202 __uc.bucket_count(), __uc.size()); 203 _M_size_info = 0; 204 205 if (!_M_hashfunc_info) 206 return; 207 208 _M_profile_destruct(__unique_keys()); 209 _M_hashfunc_info = 0; 210 } 211 212 void 213 _M_swap(_Unordered_profile& __other) noexcept 214 { 215 std::swap(_M_size_info, __other._M_size_info); 216 std::swap(_M_hashfunc_info, __other._M_hashfunc_info); 217 } 218 219 void 220 _M_profile_resize(std::size_t __old_size) 221 { 222 auto __new_size = _M_conjure().bucket_count(); 223 if (__old_size != __new_size) 224 __profcxx_hashtable_size_resize(_M_size_info, __old_size, __new_size); 225 } 226 227 __gnu_profile::__container_size_info* _M_size_info; 228 __gnu_profile::__hashfunc_info* _M_hashfunc_info; 229 230 private: 231 void 232 _M_profile_destruct(std::true_type); 233 234 void 235 _M_profile_destruct(std::false_type); 236 }; 237 238 template<typename _UnorderedCont, bool _Unique_keys> 239 void 240 _Unordered_profile<_UnorderedCont, _Unique_keys>:: 241 _M_profile_destruct(std::true_type) 242 { 243 auto& __uc = _M_conjure(); 244 std::size_t __hops = 0, __lc = 0, __chain = 0; 245 auto __it = __uc.begin(); 246 while (__it != __uc.end()) 247 { 248 auto __bkt = __get_bucket_index(__uc, __it._M_cur); 249 auto __lit = __uc.begin(__bkt); 250 auto __lend = __uc.end(__bkt); 251 for (++__it, ++__lit; __lit != __lend; ++__it, ++__lit) 252 ++__chain; 253 254 if (__chain) 255 { 256 ++__chain; 257 __lc = __lc > __chain ? __lc : __chain; 258 __hops += __chain * (__chain - 1) / 2; 259 __chain = 0; 260 } 261 } 262 263 __profcxx_hash_func_destruct(_M_hashfunc_info, 264 __lc, __uc.size(), __hops); 265 } 266 267 template<typename _UnorderedCont, bool _Unique_keys> 268 void 269 _Unordered_profile<_UnorderedCont, _Unique_keys>:: 270 _M_profile_destruct(std::false_type) 271 { 272 auto& __uc = _M_conjure(); 273 std::size_t __hops = 0, __lc = 0, __chain = 0, __unique_size = 0; 274 auto __it = __uc.begin(); 275 while (__it != __uc.end()) 276 { 277 auto __bkt = __get_bucket_index(__uc, __it._M_cur); 278 auto __lit = __uc.begin(__bkt); 279 auto __lend = __uc.end(__bkt); 280 auto __pit = __it; 281 ++__unique_size; 282 for (++__it, ++__lit; __lit != __lend; ++__it, ++__lit) 283 { 284 if (!__are_equal(__uc, __pit._M_cur, __it._M_cur)) 285 { 286 ++__chain; 287 ++__unique_size; 288 __pit = __it; 289 } 290 } 291 292 if (__chain) 293 { 294 ++__chain; 295 __lc = __lc > __chain ? __lc : __chain; 296 __hops += __chain * (__chain - 1) / 2; 297 __chain = 0; 298 } 299 } 300 301 __profcxx_hash_func_destruct(_M_hashfunc_info, 302 __lc, __unique_size, __hops); 303 } 304 305 } // namespace __profile 306 } // namespace std 307 308 #endif 309
Indexes created Thu Sep 17 00:24:55 UTC 2026