1// Profiling unordered_map/unordered_multimap implementation -*- C++ -*- 2 3// Copyright (C) 2009-2018 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 42namespace std _GLIBCXX_VISIBILITY(default) 43{ 44namespace __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 unordered_map() = default; 80 81 explicit 82 unordered_map(size_type __n, 83 const hasher& __hf = hasher(), 84 const key_equal& __eql = key_equal(), 85 const allocator_type& __a = allocator_type()) 86 : _Base(__n, __hf, __eql, __a) { } 87 88 template<typename _InputIterator> 89 unordered_map(_InputIterator __f, _InputIterator __l, 90 size_type __n = 0, 91 const hasher& __hf = hasher(), 92 const key_equal& __eql = key_equal(), 93 const allocator_type& __a = allocator_type()) 94 : _Base(__f, __l, __n, __hf, __eql, __a) { } 95 96 unordered_map(const unordered_map&) = default; 97 98 unordered_map(const _Base& __x) 99 : _Base(__x) { } 100 101 unordered_map(unordered_map&&) = default; 102 103 explicit 104 unordered_map(const allocator_type& __a) 105 : _Base(__a) { } 106 107 unordered_map(const unordered_map& __umap, 108 const allocator_type& __a) 109 : _Base(__umap, __a) { } 110 111 unordered_map(unordered_map&& __umap, 112 const allocator_type& __a) 113 : _Base(std::move(__umap._M_base()), __a) { } 114 115 unordered_map(initializer_list<value_type> __l, 116 size_type __n = 0, 117 const hasher& __hf = hasher(), 118 const key_equal& __eql = key_equal(), 119 const allocator_type& __a = allocator_type()) 120 : _Base(__l, __n, __hf, __eql, __a) { } 121 122 unordered_map(size_type __n, const allocator_type& __a) 123 : unordered_map(__n, hasher(), key_equal(), __a) 124 { } 125 126 unordered_map(size_type __n, const hasher& __hf, 127 const allocator_type& __a) 128 : unordered_map(__n, __hf, key_equal(), __a) 129 { } 130 131 template<typename _InputIterator> 132 unordered_map(_InputIterator __first, _InputIterator __last, 133 size_type __n, 134 const allocator_type& __a) 135 : unordered_map(__first, __last, __n, hasher(), key_equal(), __a) 136 { } 137 138 template<typename _InputIterator> 139 unordered_map(_InputIterator __first, _InputIterator __last, 140 size_type __n, const hasher& __hf, 141 const allocator_type& __a) 142 : unordered_map(__first, __last, __n, __hf, key_equal(), __a) 143 { } 144 145 unordered_map(initializer_list<value_type> __l, 146 size_type __n, 147 const allocator_type& __a) 148 : unordered_map(__l, __n, hasher(), key_equal(), __a) 149 { } 150 151 unordered_map(initializer_list<value_type> __l, 152 size_type __n, const hasher& __hf, 153 const allocator_type& __a) 154 : unordered_map(__l, __n, __hf, key_equal(), __a) 155 { } 156 157 unordered_map& 158 operator=(const unordered_map&) = default; 159 160 unordered_map& 161 operator=(unordered_map&&) = default; 162 163 unordered_map& 164 operator=(initializer_list<value_type> __l) 165 { 166 this->_M_profile_destruct(); 167 _M_base() = __l; 168 this->_M_profile_construct(); 169 return *this; 170 } 171 172 void 173 clear() noexcept 174 { 175 this->_M_profile_destruct(); 176 _Base::clear(); 177 this->_M_profile_construct(); 178 } 179 180 template<typename... _Args> 181 std::pair<iterator, bool> 182 emplace(_Args&&... __args) 183 { 184 size_type __old_size = _Base::bucket_count(); 185 std::pair<iterator, bool> __res 186 = _Base::emplace(std::forward<_Args>(__args)...); 187 this->_M_profile_resize(__old_size); 188 return __res; 189 } 190 191 template<typename... _Args> 192 iterator 193 emplace_hint(const_iterator __it, _Args&&... __args) 194 { 195 size_type __old_size = _Base::bucket_count(); 196 iterator __res 197 = _Base::emplace_hint(__it, std::forward<_Args>(__args)...); 198 this->_M_profile_resize(__old_size); 199 return __res; 200 } 201 202 void 203 insert(std::initializer_list<value_type> __l) 204 { 205 size_type __old_size = _Base::bucket_count(); 206 _Base::insert(__l); 207 this->_M_profile_resize(__old_size); 208 } 209 210 std::pair<iterator, bool> 211 insert(const value_type& __obj) 212 { 213 size_type __old_size = _Base::bucket_count(); 214 std::pair<iterator, bool> __res = _Base::insert(__obj); 215 this->_M_profile_resize(__old_size); 216 return __res; 217 } 218 219 iterator 220 insert(const_iterator __iter, const value_type& __v) 221 { 222 size_type __old_size = _Base::bucket_count(); 223 iterator __res = _Base::insert(__iter, __v); 224 this->_M_profile_resize(__old_size); 225 return __res; 226 } 227 228 template<typename _Pair, typename = typename 229 std::enable_if<std::is_constructible<value_type, 230 _Pair&&>::value>::type> 231 std::pair<iterator, bool> 232 insert(_Pair&& __obj) 233 { 234 size_type __old_size = _Base::bucket_count(); 235 std::pair<iterator, bool> __res 236 = _Base::insert(std::forward<_Pair>(__obj)); 237 this->_M_profile_resize(__old_size); 238 return __res; 239 } 240 241 template<typename _Pair, typename = typename 242 std::enable_if<std::is_constructible<value_type, 243 _Pair&&>::value>::type> 244 iterator 245 insert(const_iterator __iter, _Pair&& __v) 246 { 247 size_type __old_size = _Base::bucket_count(); 248 iterator __res = _Base::insert(__iter, std::forward<_Pair>(__v)); 249 this->_M_profile_resize(__old_size); 250 return __res; 251 } 252 253 template<typename _InputIter> 254 void 255 insert(_InputIter __first, _InputIter __last) 256 { 257 size_type __old_size = _Base::bucket_count(); 258 _Base::insert(__first, __last); 259 this->_M_profile_resize(__old_size); 260 } 261 262 // operator[] 263 mapped_type& 264 operator[](const _Key& __k) 265 { 266 size_type __old_size = _Base::bucket_count(); 267 mapped_type& __res = _M_base()[__k]; 268 this->_M_profile_resize(__old_size); 269 return __res; 270 } 271 272 mapped_type& 273 operator[](_Key&& __k) 274 { 275 size_type __old_size = _Base::bucket_count(); 276 mapped_type& __res = _M_base()[std::move(__k)]; 277 this->_M_profile_resize(__old_size); 278 return __res; 279 } 280 281 void 282 swap(unordered_map& __x) 283 noexcept( noexcept(__x._M_base().swap(__x)) ) 284 { 285 _Base::swap(__x._M_base()); 286 this->_M_swap(__x); 287 } 288 289 void rehash(size_type __n) 290 { 291 size_type __old_size = _Base::bucket_count(); 292 _Base::rehash(__n); 293 this->_M_profile_resize(__old_size); 294 } 295 }; 296 297 template<typename _Key, typename _Tp, typename _Hash, 298 typename _Pred, typename _Alloc> 299 inline void 300 swap(unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 301 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 302 noexcept(noexcept(__x.swap(__y))) 303 { __x.swap(__y); } 304 305 template<typename _Key, typename _Tp, typename _Hash, 306 typename _Pred, typename _Alloc> 307 inline bool 308 operator==(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 309 const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 310 { return static_cast<const _GLIBCXX_STD_BASE&>(__x) == __y; } 311 312 template<typename _Key, typename _Tp, typename _Hash, 313 typename _Pred, typename _Alloc> 314 inline bool 315 operator!=(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 316 const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 317 { return !(__x == __y); } 318 319#undef _GLIBCXX_BASE 320#undef _GLIBCXX_STD_BASE 321#define _GLIBCXX_BASE unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc> 322#define _GLIBCXX_STD_BASE _GLIBCXX_STD_C::_GLIBCXX_BASE 323 324 /// Class std::unordered_multimap wrapper with performance instrumentation. 325 template<typename _Key, typename _Tp, 326 typename _Hash = std::hash<_Key>, 327 typename _Pred = std::equal_to<_Key>, 328 typename _Alloc = std::allocator<std::pair<const _Key, _Tp> > > 329 class unordered_multimap 330 : public _GLIBCXX_STD_BASE, 331 public _Unordered_profile<unordered_multimap<_Key, _Tp, 332 _Hash, _Pred, _Alloc>, 333 false> 334 { 335 typedef typename _GLIBCXX_STD_BASE _Base; 336 337 _Base& 338 _M_base() noexcept { return *this; } 339 340 const _Base& 341 _M_base() const noexcept { return *this; } 342 343 public: 344 typedef typename _Base::size_type size_type; 345 typedef typename _Base::hasher hasher; 346 typedef typename _Base::key_equal key_equal; 347 typedef typename _Base::allocator_type allocator_type; 348 typedef typename _Base::key_type key_type; 349 typedef typename _Base::value_type value_type; 350 typedef typename _Base::difference_type difference_type; 351 typedef typename _Base::reference reference; 352 typedef typename _Base::const_reference const_reference; 353 354 typedef typename _Base::iterator iterator; 355 typedef typename _Base::const_iterator const_iterator; 356 357 unordered_multimap() = default; 358 359 explicit 360 unordered_multimap(size_type __n, 361 const hasher& __hf = hasher(), 362 const key_equal& __eql = key_equal(), 363 const allocator_type& __a = allocator_type()) 364 : _Base(__n, __hf, __eql, __a) { } 365 366 template<typename _InputIterator> 367 unordered_multimap(_InputIterator __f, _InputIterator __l, 368 size_type __n = 0, 369 const hasher& __hf = hasher(), 370 const key_equal& __eql = key_equal(), 371 const allocator_type& __a = allocator_type()) 372 : _Base(__f, __l, __n, __hf, __eql, __a) { } 373 374 unordered_multimap(const unordered_multimap&) = default; 375 376 unordered_multimap(const _Base& __x) 377 : _Base(__x) { } 378 379 unordered_multimap(unordered_multimap&&) = default; 380 381 explicit 382 unordered_multimap(const allocator_type& __a) 383 : _Base(__a) { } 384 385 unordered_multimap(const unordered_multimap& __ummap, 386 const allocator_type& __a) 387 : _Base(__ummap._M_base(), __a) { } 388 389 unordered_multimap(unordered_multimap&& __ummap, 390 const allocator_type& __a) 391 : _Base(std::move(__ummap._M_base()), __a) { } 392 393 unordered_multimap(initializer_list<value_type> __l, 394 size_type __n = 0, 395 const hasher& __hf = hasher(), 396 const key_equal& __eql = key_equal(), 397 const allocator_type& __a = allocator_type()) 398 : _Base(__l, __n, __hf, __eql, __a) { } 399 400 unordered_multimap(size_type __n, const allocator_type& __a) 401 : unordered_multimap(__n, hasher(), key_equal(), __a) 402 { } 403 404 unordered_multimap(size_type __n, const hasher& __hf, 405 const allocator_type& __a) 406 : unordered_multimap(__n, __hf, key_equal(), __a) 407 { } 408 409 template<typename _InputIterator> 410 unordered_multimap(_InputIterator __first, _InputIterator __last, 411 size_type __n, 412 const allocator_type& __a) 413 : unordered_multimap(__first, __last, __n, hasher(), key_equal(), __a) 414 { } 415 416 template<typename _InputIterator> 417 unordered_multimap(_InputIterator __first, _InputIterator __last, 418 size_type __n, const hasher& __hf, 419 const allocator_type& __a) 420 : unordered_multimap(__first, __last, __n, __hf, key_equal(), __a) 421 { } 422 423 unordered_multimap(initializer_list<value_type> __l, 424 size_type __n, 425 const allocator_type& __a) 426 : unordered_multimap(__l, __n, hasher(), key_equal(), __a) 427 { } 428 429 unordered_multimap(initializer_list<value_type> __l, 430 size_type __n, const hasher& __hf, 431 const allocator_type& __a) 432 : unordered_multimap(__l, __n, __hf, key_equal(), __a) 433 { } 434 435 unordered_multimap& 436 operator=(const unordered_multimap&) = default; 437 438 unordered_multimap& 439 operator=(unordered_multimap&&) = default; 440 441 unordered_multimap& 442 operator=(initializer_list<value_type> __l) 443 { 444 this->_M_profile_destruct(); 445 _M_base() = __l; 446 this->_M_profile_construct(); 447 return *this; 448 } 449 450 void 451 clear() noexcept 452 { 453 this->_M_profile_destruct(); 454 _Base::clear(); 455 this->_M_profile_construct(); 456 } 457 458 template<typename... _Args> 459 iterator 460 emplace(_Args&&... __args) 461 { 462 size_type __old_size = _Base::bucket_count(); 463 iterator __res 464 = _Base::emplace(std::forward<_Args>(__args)...); 465 this->_M_profile_resize(__old_size); 466 return __res; 467 } 468 469 template<typename... _Args> 470 iterator 471 emplace_hint(const_iterator __it, _Args&&... __args) 472 { 473 size_type __old_size = _Base::bucket_count(); 474 iterator __res 475 = _Base::emplace_hint(__it, std::forward<_Args>(__args)...); 476 this->_M_profile_resize(__old_size); 477 return __res; 478 } 479 480 void 481 insert(std::initializer_list<value_type> __l) 482 { 483 size_type __old_size = _Base::bucket_count(); 484 _Base::insert(__l); 485 this->_M_profile_resize(__old_size); 486 } 487 488 iterator 489 insert(const value_type& __obj) 490 { 491 size_type __old_size = _Base::bucket_count(); 492 iterator __res = _Base::insert(__obj); 493 this->_M_profile_resize(__old_size); 494 return __res; 495 } 496 497 iterator 498 insert(const_iterator __iter, const value_type& __v) 499 { 500 size_type __old_size = _Base::bucket_count(); 501 iterator __res = _Base::insert(__iter, __v); 502 this->_M_profile_resize(__old_size); 503 return __res; 504 } 505 506 template<typename _Pair, typename = typename 507 std::enable_if<std::is_constructible<value_type, 508 _Pair&&>::value>::type> 509 iterator 510 insert(_Pair&& __obj) 511 { 512 size_type __old_size = _Base::bucket_count(); 513 iterator __res = _Base::insert(std::forward<_Pair>(__obj)); 514 this->_M_profile_resize(__old_size); 515 return __res; 516 } 517 518 template<typename _Pair, typename = typename 519 std::enable_if<std::is_constructible<value_type, 520 _Pair&&>::value>::type> 521 iterator 522 insert(const_iterator __iter, _Pair&& __v) 523 { 524 size_type __old_size = _Base::bucket_count(); 525 iterator __res = _Base::insert(__iter, std::forward<_Pair>(__v)); 526 this->_M_profile_resize(__old_size); 527 return __res; 528 } 529 530 template<typename _InputIter> 531 void 532 insert(_InputIter __first, _InputIter __last) 533 { 534 size_type __old_size = _Base::bucket_count(); 535 _Base::insert(__first, __last); 536 this->_M_profile_resize(__old_size); 537 } 538 539 void 540 swap(unordered_multimap& __x) 541 noexcept( noexcept(__x._M_base().swap(__x)) ) 542 { 543 _Base::swap(__x._M_base()); 544 this->_M_swap(__x); 545 } 546 547 void 548 rehash(size_type __n) 549 { 550 size_type __old_size = _Base::bucket_count(); 551 _Base::rehash(__n); 552 this->_M_profile_resize(__old_size); 553 } 554 }; 555 556 template<typename _Key, typename _Tp, typename _Hash, 557 typename _Pred, typename _Alloc> 558 inline void 559 swap(unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 560 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 561 noexcept(noexcept(__x.swap(__y))) 562 { __x.swap(__y); } 563 564 template<typename _Key, typename _Tp, typename _Hash, 565 typename _Pred, typename _Alloc> 566 inline bool 567 operator==(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 568 const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 569 { return static_cast<const _GLIBCXX_STD_BASE&>(__x) == __y; } 570 571 template<typename _Key, typename _Tp, typename _Hash, 572 typename _Pred, typename _Alloc> 573 inline bool 574 operator!=(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 575 const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 576 { return !(__x == __y); } 577 578} // namespace __profile 579} // namespace std 580 581#undef _GLIBCXX_BASE 582#undef _GLIBCXX_STD_BASE 583 584#endif // C++11 585 586#endif 587