1 // Profiling unordered_map/unordered_multimap implementation -*- C++ -*- 2 3 // Copyright (C) 2009-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_map 25 * This file is a GNU profile extension to the Standard C++ Library. 26 */ 27 28 #ifndef _GLIBCXX_PROFILE_UNORDERED_MAP 29 #define _GLIBCXX_PROFILE_UNORDERED_MAP 1 30 31 #if __cplusplus < 201103L 32 # include <bits/c++0x_warning.h> 33 #else 34 # include <unordered_map> 35 36 #include <profile/base.h> 37 #include <profile/unordered_base.h> 38 39 #define _GLIBCXX_BASE unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc> 40 #define _GLIBCXX_STD_BASE _GLIBCXX_STD_C::_GLIBCXX_BASE 41 42 namespace std _GLIBCXX_VISIBILITY(default) 43 { 44 namespace __profile 45 { 46 /// Class std::unordered_map wrapper with performance instrumentation. 47 template<typename _Key, typename _Tp, 48 typename _Hash = std::hash<_Key>, 49 typename _Pred = std::equal_to<_Key>, 50 typename _Alloc = std::allocator<std::pair<const _Key, _Tp> > > 51 class unordered_map 52 : public _GLIBCXX_STD_BASE, 53 public _Unordered_profile<unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>, 54 true> 55 { 56 typedef typename _GLIBCXX_STD_BASE _Base; 57 58 _Base& 59 _M_base() noexcept { return *this; } 60 61 const _Base& 62 _M_base() const noexcept { return *this; } 63 64 public: 65 typedef typename _Base::size_type size_type; 66 typedef typename _Base::hasher hasher; 67 typedef typename _Base::key_equal key_equal; 68 typedef typename _Base::allocator_type allocator_type; 69 typedef typename _Base::key_type key_type; 70 typedef typename _Base::value_type value_type; 71 typedef typename _Base::difference_type difference_type; 72 typedef typename _Base::reference reference; 73 typedef typename _Base::const_reference const_reference; 74 typedef typename _Base::mapped_type mapped_type; 75 76 typedef typename _Base::iterator iterator; 77 typedef typename _Base::const_iterator const_iterator; 78 79 explicit 80 unordered_map(size_type __n = 10, 81 const hasher& __hf = hasher(), 82 const key_equal& __eql = key_equal(), 83 const allocator_type& __a = allocator_type()) 84 : _Base(__n, __hf, __eql, __a) 85 { } 86 87 template<typename _InputIterator> 88 unordered_map(_InputIterator __f, _InputIterator __l, 89 size_type __n = 0, 90 const hasher& __hf = hasher(), 91 const key_equal& __eql = key_equal(), 92 const allocator_type& __a = allocator_type()) 93 : _Base(__f, __l, __n, __hf, __eql, __a) 94 { } 95 96 unordered_map(const unordered_map&) = default; 97 98 unordered_map(const _Base& __x) 99 : _Base(__x) 100 { } 101 102 unordered_map(unordered_map&&) = default; 103 104 unordered_map(initializer_list<value_type> __l, 105 size_type __n = 0, 106 const hasher& __hf = hasher(), 107 const key_equal& __eql = key_equal(), 108 const allocator_type& __a = allocator_type()) 109 : _Base(__l, __n, __hf, __eql, __a) 110 { } 111 112 unordered_map& 113 operator=(const unordered_map&) = default; 114 115 unordered_map& 116 operator=(unordered_map&&) = default; 117 118 unordered_map& 119 operator=(initializer_list<value_type> __l) 120 { 121 _M_base() = __l; 122 return *this; 123 } 124 125 void 126 clear() noexcept 127 { 128 __profcxx_hashtable_destruct(this, _Base::bucket_count(), 129 _Base::size()); 130 this->_M_profile_destruct(); 131 _Base::clear(); 132 } 133 134 template<typename... _Args> 135 std::pair<iterator, bool> 136 emplace(_Args&&... __args) 137 { 138 size_type __old_size = _Base::bucket_count(); 139 std::pair<iterator, bool> __res 140 = _Base::emplace(std::forward<_Args>(__args)...); 141 _M_profile_resize(__old_size); 142 return __res; 143 } 144 145 template<typename... _Args> 146 iterator 147 emplace_hint(const_iterator __it, _Args&&... __args) 148 { 149 size_type __old_size = _Base::bucket_count(); 150 iterator __res 151 = _Base::emplace_hint(__it, std::forward<_Args>(__args)...); 152 _M_profile_resize(__old_size); 153 return __res; 154 } 155 156 void 157 insert(std::initializer_list<value_type> __l) 158 { 159 size_type __old_size = _Base::bucket_count(); 160 _Base::insert(__l); 161 _M_profile_resize(__old_size); 162 } 163 164 std::pair<iterator, bool> 165 insert(const value_type& __obj) 166 { 167 size_type __old_size = _Base::bucket_count(); 168 std::pair<iterator, bool> __res = _Base::insert(__obj); 169 _M_profile_resize(__old_size); 170 return __res; 171 } 172 173 iterator 174 insert(const_iterator __iter, const value_type& __v) 175 { 176 size_type __old_size = _Base::bucket_count(); 177 iterator __res = _Base::insert(__iter, __v); 178 _M_profile_resize(__old_size); 179 return __res; 180 } 181 182 template<typename _Pair, typename = typename 183 std::enable_if<std::is_constructible<value_type, 184 _Pair&&>::value>::type> 185 std::pair<iterator, bool> 186 insert(_Pair&& __obj) 187 { 188 size_type __old_size = _Base::bucket_count(); 189 std::pair<iterator, bool> __res 190 = _Base::insert(std::forward<_Pair>(__obj)); 191 _M_profile_resize(__old_size); 192 return __res; 193 } 194 195 template<typename _Pair, typename = typename 196 std::enable_if<std::is_constructible<value_type, 197 _Pair&&>::value>::type> 198 iterator 199 insert(const_iterator __iter, _Pair&& __v) 200 { 201 size_type __old_size = _Base::bucket_count(); 202 iterator __res = _Base::insert(__iter, std::forward<_Pair>(__v)); 203 _M_profile_resize(__old_size); 204 return __res; 205 } 206 207 template<typename _InputIter> 208 void 209 insert(_InputIter __first, _InputIter __last) 210 { 211 size_type __old_size = _Base::bucket_count(); 212 _Base::insert(__first, __last); 213 _M_profile_resize(__old_size); 214 } 215 216 // operator[] 217 mapped_type& 218 operator[](const _Key& __k) 219 { 220 size_type __old_size = _Base::bucket_count(); 221 mapped_type& __res = _M_base()[__k]; 222 _M_profile_resize(__old_size); 223 return __res; 224 } 225 226 mapped_type& 227 operator[](_Key&& __k) 228 { 229 size_type __old_size = _Base::bucket_count(); 230 mapped_type& __res = _M_base()[std::move(__k)]; 231 _M_profile_resize(__old_size); 232 return __res; 233 } 234 235 void 236 swap(unordered_map& __x) 237 { _Base::swap(__x._M_base()); } 238 239 void rehash(size_type __n) 240 { 241 size_type __old_size = _Base::bucket_count(); 242 _Base::rehash(__n); 243 _M_profile_resize(__old_size); 244 } 245 246 private: 247 void 248 _M_profile_resize(size_type __old_size) 249 { 250 size_type __new_size = _Base::bucket_count(); 251 if (__old_size != __new_size) 252 __profcxx_hashtable_resize(this, __old_size, __new_size); 253 } 254 }; 255 256 template<typename _Key, typename _Tp, typename _Hash, 257 typename _Pred, typename _Alloc> 258 inline void 259 swap(unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 260 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 261 { __x.swap(__y); } 262 263 template<typename _Key, typename _Tp, typename _Hash, 264 typename _Pred, typename _Alloc> 265 inline bool 266 operator==(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 267 const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 268 { return static_cast<const _GLIBCXX_STD_BASE&>(__x) == __y; } 269 270 template<typename _Key, typename _Tp, typename _Hash, 271 typename _Pred, typename _Alloc> 272 inline bool 273 operator!=(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 274 const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 275 { return !(__x == __y); } 276 277 #undef _GLIBCXX_BASE 278 #undef _GLIBCXX_STD_BASE 279 #define _GLIBCXX_BASE unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc> 280 #define _GLIBCXX_STD_BASE _GLIBCXX_STD_C::_GLIBCXX_BASE 281 282 /// Class std::unordered_multimap wrapper with performance instrumentation. 283 template<typename _Key, typename _Tp, 284 typename _Hash = std::hash<_Key>, 285 typename _Pred = std::equal_to<_Key>, 286 typename _Alloc = std::allocator<std::pair<const _Key, _Tp> > > 287 class unordered_multimap 288 : public _GLIBCXX_STD_BASE, 289 public _Unordered_profile<unordered_multimap<_Key, _Tp, 290 _Hash, _Pred, _Alloc>, 291 false> 292 { 293 typedef typename _GLIBCXX_STD_BASE _Base; 294 295 _Base& 296 _M_base() noexcept { return *this; } 297 298 const _Base& 299 _M_base() const noexcept { return *this; } 300 301 public: 302 typedef typename _Base::size_type size_type; 303 typedef typename _Base::hasher hasher; 304 typedef typename _Base::key_equal key_equal; 305 typedef typename _Base::allocator_type allocator_type; 306 typedef typename _Base::key_type key_type; 307 typedef typename _Base::value_type value_type; 308 typedef typename _Base::difference_type difference_type; 309 typedef typename _Base::reference reference; 310 typedef typename _Base::const_reference const_reference; 311 312 typedef typename _Base::iterator iterator; 313 typedef typename _Base::const_iterator const_iterator; 314 315 explicit 316 unordered_multimap(size_type __n = 10, 317 const hasher& __hf = hasher(), 318 const key_equal& __eql = key_equal(), 319 const allocator_type& __a = allocator_type()) 320 : _Base(__n, __hf, __eql, __a) 321 { } 322 323 template<typename _InputIterator> 324 unordered_multimap(_InputIterator __f, _InputIterator __l, 325 size_type __n = 0, 326 const hasher& __hf = hasher(), 327 const key_equal& __eql = key_equal(), 328 const allocator_type& __a = allocator_type()) 329 : _Base(__f, __l, __n, __hf, __eql, __a) 330 { } 331 332 unordered_multimap(const unordered_multimap&) = default; 333 334 unordered_multimap(const _Base& __x) 335 : _Base(__x) 336 { } 337 338 unordered_multimap(unordered_multimap&&) = default; 339 340 unordered_multimap(initializer_list<value_type> __l, 341 size_type __n = 0, 342 const hasher& __hf = hasher(), 343 const key_equal& __eql = key_equal(), 344 const allocator_type& __a = allocator_type()) 345 : _Base(__l, __n, __hf, __eql, __a) 346 { } 347 348 unordered_multimap& 349 operator=(const unordered_multimap&) = default; 350 351 unordered_multimap& 352 operator=(unordered_multimap&&) = default; 353 354 unordered_multimap& 355 operator=(initializer_list<value_type> __l) 356 { 357 _M_base() = __l; 358 return *this; 359 } 360 361 void 362 clear() noexcept 363 { 364 __profcxx_hashtable_destruct(this, _Base::bucket_count(), 365 _Base::size()); 366 this->_M_profile_destruct(); 367 _Base::clear(); 368 } 369 370 template<typename... _Args> 371 iterator 372 emplace(_Args&&... __args) 373 { 374 size_type __old_size = _Base::bucket_count(); 375 iterator __res 376 = _Base::emplace(std::forward<_Args>(__args)...); 377 _M_profile_resize(__old_size); 378 return __res; 379 } 380 381 template<typename... _Args> 382 iterator 383 emplace_hint(const_iterator __it, _Args&&... __args) 384 { 385 size_type __old_size = _Base::bucket_count(); 386 iterator __res 387 = _Base::emplace_hint(__it, std::forward<_Args>(__args)...); 388 _M_profile_resize(__old_size); 389 return __res; 390 } 391 392 void 393 insert(std::initializer_list<value_type> __l) 394 { 395 size_type __old_size = _Base::bucket_count(); 396 _Base::insert(__l); 397 _M_profile_resize(__old_size); 398 } 399 400 iterator 401 insert(const value_type& __obj) 402 { 403 size_type __old_size = _Base::bucket_count(); 404 iterator __res = _Base::insert(__obj); 405 _M_profile_resize(__old_size); 406 return __res; 407 } 408 409 iterator 410 insert(const_iterator __iter, const value_type& __v) 411 { 412 size_type __old_size = _Base::bucket_count(); 413 iterator __res = _Base::insert(__iter, __v); 414 _M_profile_resize(__old_size); 415 return __res; 416 } 417 418 template<typename _Pair, typename = typename 419 std::enable_if<std::is_constructible<value_type, 420 _Pair&&>::value>::type> 421 iterator 422 insert(_Pair&& __obj) 423 { 424 size_type __old_size = _Base::bucket_count(); 425 iterator __res = _Base::insert(std::forward<_Pair>(__obj)); 426 _M_profile_resize(__old_size); 427 return __res; 428 } 429 430 template<typename _Pair, typename = typename 431 std::enable_if<std::is_constructible<value_type, 432 _Pair&&>::value>::type> 433 iterator 434 insert(const_iterator __iter, _Pair&& __v) 435 { 436 size_type __old_size = _Base::bucket_count(); 437 iterator __res = _Base::insert(__iter, std::forward<_Pair>(__v)); 438 _M_profile_resize(__old_size); 439 return __res; 440 } 441 442 template<typename _InputIter> 443 void 444 insert(_InputIter __first, _InputIter __last) 445 { 446 size_type __old_size = _Base::bucket_count(); 447 _Base::insert(__first, __last); 448 _M_profile_resize(__old_size); 449 } 450 451 void 452 swap(unordered_multimap& __x) 453 { _Base::swap(__x._M_base()); } 454 455 void 456 rehash(size_type __n) 457 { 458 size_type __old_size = _Base::bucket_count(); 459 _Base::rehash(__n); 460 _M_profile_resize(__old_size); 461 } 462 463 private: 464 void 465 _M_profile_resize(size_type __old_size) 466 { 467 size_type __new_size = _Base::bucket_count(); 468 if (__old_size != __new_size) 469 __profcxx_hashtable_resize(this, __old_size, __new_size); 470 } 471 }; 472 473 template<typename _Key, typename _Tp, typename _Hash, 474 typename _Pred, typename _Alloc> 475 inline void 476 swap(unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 477 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 478 { __x.swap(__y); } 479 480 template<typename _Key, typename _Tp, typename _Hash, 481 typename _Pred, typename _Alloc> 482 inline bool 483 operator==(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 484 const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 485 { return static_cast<const _GLIBCXX_STD_BASE&>(__x) == __y; } 486 487 template<typename _Key, typename _Tp, typename _Hash, 488 typename _Pred, typename _Alloc> 489 inline bool 490 operator!=(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 491 const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 492 { return !(__x == __y); } 493 494 } // namespace __profile 495 } // namespace std 496 497 #undef _GLIBCXX_BASE 498 #undef _GLIBCXX_STD_BASE 499 500 #endif // C++11 501 502 #endif 503
