1 // Profiling unordered containers implementation details -*- C++ -*- 2 3 // Copyright (C) 2013 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() 158 { 159 auto& __uc = _M_conjure(); 160 __profcxx_hashtable_construct(&__uc, __uc.bucket_count()); 161 __profcxx_hashtable_construct2(&__uc); 162 } 163 _Unordered_profile(const _Unordered_profile&) 164 : _Unordered_profile() { } 165 _Unordered_profile(_Unordered_profile&&) 166 : _Unordered_profile() { } 167 168 ~_Unordered_profile() noexcept 169 { 170 auto& __uc = _M_conjure(); 171 __profcxx_hashtable_destruct(&__uc, __uc.bucket_count(), __uc.size()); 172 _M_profile_destruct(); 173 } 174 175 _Unordered_profile& 176 operator=(const _Unordered_profile&) = default; 177 178 _Unordered_profile& 179 operator=(_Unordered_profile&&) = default; 180 181 void 182 _M_profile_destruct() 183 { 184 if (!__profcxx_inefficient_hash_is_on()) 185 return; 186 187 _M_profile_destruct(__unique_keys()); 188 } 189 190 private: 191 void 192 _M_profile_destruct(std::true_type); 193 194 void 195 _M_profile_destruct(std::false_type); 196 }; 197 198 template<typename _UnorderedCont, bool _Unique_keys> 199 void 200 _Unordered_profile<_UnorderedCont, _Unique_keys>:: 201 _M_profile_destruct(std::true_type) 202 { 203 auto& __uc = _M_conjure(); 204 std::size_t __hops = 0, __lc = 0, __chain = 0; 205 auto __it = __uc.begin(); 206 while (__it != __uc.end()) 207 { 208 auto __bkt = __get_bucket_index(__uc, __it._M_cur); 209 auto __lit = __uc.begin(__bkt); 210 auto __lend = __uc.end(__bkt); 211 for (++__it, ++__lit; __lit != __lend; ++__it, ++__lit) 212 ++__chain; 213 if (__chain) 214 { 215 ++__chain; 216 __lc = __lc > __chain ? __lc : __chain; 217 __hops += __chain * (__chain - 1) / 2; 218 __chain = 0; 219 } 220 } 221 __profcxx_hashtable_destruct2(&__uc, __lc, __uc.size(), __hops); 222 } 223 224 template<typename _UnorderedCont, bool _Unique_keys> 225 void 226 _Unordered_profile<_UnorderedCont, _Unique_keys>:: 227 _M_profile_destruct(std::false_type) 228 { 229 auto& __uc = _M_conjure(); 230 std::size_t __hops = 0, __lc = 0, __chain = 0, __unique_size = 0; 231 auto __it = __uc.begin(); 232 while (__it != __uc.end()) 233 { 234 auto __bkt = __get_bucket_index(__uc, __it._M_cur); 235 auto __lit = __uc.begin(__bkt); 236 auto __lend = __uc.end(__bkt); 237 auto __pit = __it; 238 ++__unique_size; 239 for (++__it, ++__lit; __lit != __lend; ++__it, ++__lit) 240 { 241 if (!__are_equal(__uc, __pit._M_cur, __it._M_cur)) 242 { 243 ++__chain; 244 ++__unique_size; 245 __pit = __it; 246 } 247 } 248 if (__chain) 249 { 250 ++__chain; 251 __lc = __lc > __chain ? __lc : __chain; 252 __hops += __chain * (__chain - 1) / 2; 253 __chain = 0; 254 } 255 } 256 __profcxx_hashtable_destruct2(&__uc, __lc, __unique_size, __hops); 257 } 258 259 } // namespace __profile 260 } // namespace std 261 262 #endif 263