1// Profiling unordered_map/unordered_multimap implementation -*- C++ -*- 2 3// Copyright (C) 2009-2015 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 { __x.swap(__y); } 303 304 template<typename _Key, typename _Tp, typename _Hash, 305 typename _Pred, typename _Alloc> 306 inline bool 307 operator==(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 308 const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 309 { return static_cast<const _GLIBCXX_STD_BASE&>(__x) == __y; } 310 311 template<typename _Key, typename _Tp, typename _Hash, 312 typename _Pred, typename _Alloc> 313 inline bool 314 operator!=(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 315 const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 316 { return !(__x == __y); } 317 318#undef _GLIBCXX_BASE 319#undef _GLIBCXX_STD_BASE 320#define _GLIBCXX_BASE unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc> 321#define _GLIBCXX_STD_BASE _GLIBCXX_STD_C::_GLIBCXX_BASE 322 323 /// Class std::unordered_multimap wrapper with performance instrumentation. 324 template<typename _Key, typename _Tp, 325 typename _Hash = std::hash<_Key>, 326 typename _Pred = std::equal_to<_Key>, 327 typename _Alloc = std::allocator<std::pair<const _Key, _Tp> > > 328 class unordered_multimap 329 : public _GLIBCXX_STD_BASE, 330 public _Unordered_profile<unordered_multimap<_Key, _Tp, 331 _Hash, _Pred, _Alloc>, 332 false> 333 { 334 typedef typename _GLIBCXX_STD_BASE _Base; 335 336 _Base& 337 _M_base() noexcept { return *this; } 338 339 const _Base& 340 _M_base() const noexcept { return *this; } 341 342 public: 343 typedef typename _Base::size_type size_type; 344 typedef typename _Base::hasher hasher; 345 typedef typename _Base::key_equal key_equal; 346 typedef typename _Base::allocator_type allocator_type; 347 typedef typename _Base::key_type key_type; 348 typedef typename _Base::value_type value_type; 349 typedef typename _Base::difference_type difference_type; 350 typedef typename _Base::reference reference; 351 typedef typename _Base::const_reference const_reference; 352 353 typedef typename _Base::iterator iterator; 354 typedef typename _Base::const_iterator const_iterator; 355 356 unordered_multimap() = default; 357 358 explicit 359 unordered_multimap(size_type __n, 360 const hasher& __hf = hasher(), 361 const key_equal& __eql = key_equal(), 362 const allocator_type& __a = allocator_type()) 363 : _Base(__n, __hf, __eql, __a) { } 364 365 template<typename _InputIterator> 366 unordered_multimap(_InputIterator __f, _InputIterator __l, 367 size_type __n = 0, 368 const hasher& __hf = hasher(), 369 const key_equal& __eql = key_equal(), 370 const allocator_type& __a = allocator_type()) 371 : _Base(__f, __l, __n, __hf, __eql, __a) { } 372 373 unordered_multimap(const unordered_multimap&) = default; 374 375 unordered_multimap(const _Base& __x) 376 : _Base(__x) { } 377 378 unordered_multimap(unordered_multimap&&) = default; 379 380 explicit 381 unordered_multimap(const allocator_type& __a) 382 : _Base(__a) { } 383 384 unordered_multimap(const unordered_multimap& __ummap, 385 const allocator_type& __a) 386 : _Base(__ummap._M_base(), __a) { } 387 388 unordered_multimap(unordered_multimap&& __ummap, 389 const allocator_type& __a) 390 : _Base(std::move(__ummap._M_base()), __a) { } 391 392 unordered_multimap(initializer_list<value_type> __l, 393 size_type __n = 0, 394 const hasher& __hf = hasher(), 395 const key_equal& __eql = key_equal(), 396 const allocator_type& __a = allocator_type()) 397 : _Base(__l, __n, __hf, __eql, __a) { } 398 399 unordered_multimap(size_type __n, const allocator_type& __a) 400 : unordered_multimap(__n, hasher(), key_equal(), __a) 401 { } 402 403 unordered_multimap(size_type __n, const hasher& __hf, 404 const allocator_type& __a) 405 : unordered_multimap(__n, __hf, key_equal(), __a) 406 { } 407 408 template<typename _InputIterator> 409 unordered_multimap(_InputIterator __first, _InputIterator __last, 410 size_type __n, 411 const allocator_type& __a) 412 : unordered_multimap(__first, __last, __n, hasher(), key_equal(), __a) 413 { } 414 415 template<typename _InputIterator> 416 unordered_multimap(_InputIterator __first, _InputIterator __last, 417 size_type __n, const hasher& __hf, 418 const allocator_type& __a) 419 : unordered_multimap(__first, __last, __n, __hf, key_equal(), __a) 420 { } 421 422 unordered_multimap(initializer_list<value_type> __l, 423 size_type __n, 424 const allocator_type& __a) 425 : unordered_multimap(__l, __n, hasher(), key_equal(), __a) 426 { } 427 428 unordered_multimap(initializer_list<value_type> __l, 429 size_type __n, const hasher& __hf, 430 const allocator_type& __a) 431 : unordered_multimap(__l, __n, __hf, key_equal(), __a) 432 { } 433 434 unordered_multimap& 435 operator=(const unordered_multimap&) = default; 436 437 unordered_multimap& 438 operator=(unordered_multimap&&) = default; 439 440 unordered_multimap& 441 operator=(initializer_list<value_type> __l) 442 { 443 this->_M_profile_destruct(); 444 _M_base() = __l; 445 this->_M_profile_construct(); 446 return *this; 447 } 448 449 void 450 clear() noexcept 451 { 452 this->_M_profile_destruct(); 453 _Base::clear(); 454 this->_M_profile_construct(); 455 } 456 457 template<typename... _Args> 458 iterator 459 emplace(_Args&&... __args) 460 { 461 size_type __old_size = _Base::bucket_count(); 462 iterator __res 463 = _Base::emplace(std::forward<_Args>(__args)...); 464 this->_M_profile_resize(__old_size); 465 return __res; 466 } 467 468 template<typename... _Args> 469 iterator 470 emplace_hint(const_iterator __it, _Args&&... __args) 471 { 472 size_type __old_size = _Base::bucket_count(); 473 iterator __res 474 = _Base::emplace_hint(__it, std::forward<_Args>(__args)...); 475 this->_M_profile_resize(__old_size); 476 return __res; 477 } 478 479 void 480 insert(std::initializer_list<value_type> __l) 481 { 482 size_type __old_size = _Base::bucket_count(); 483 _Base::insert(__l); 484 this->_M_profile_resize(__old_size); 485 } 486 487 iterator 488 insert(const value_type& __obj) 489 { 490 size_type __old_size = _Base::bucket_count(); 491 iterator __res = _Base::insert(__obj); 492 this->_M_profile_resize(__old_size); 493 return __res; 494 } 495 496 iterator 497 insert(const_iterator __iter, const value_type& __v) 498 { 499 size_type __old_size = _Base::bucket_count(); 500 iterator __res = _Base::insert(__iter, __v); 501 this->_M_profile_resize(__old_size); 502 return __res; 503 } 504 505 template<typename _Pair, typename = typename 506 std::enable_if<std::is_constructible<value_type, 507 _Pair&&>::value>::type> 508 iterator 509 insert(_Pair&& __obj) 510 { 511 size_type __old_size = _Base::bucket_count(); 512 iterator __res = _Base::insert(std::forward<_Pair>(__obj)); 513 this->_M_profile_resize(__old_size); 514 return __res; 515 } 516 517 template<typename _Pair, typename = typename 518 std::enable_if<std::is_constructible<value_type, 519 _Pair&&>::value>::type> 520 iterator 521 insert(const_iterator __iter, _Pair&& __v) 522 { 523 size_type __old_size = _Base::bucket_count(); 524 iterator __res = _Base::insert(__iter, std::forward<_Pair>(__v)); 525 this->_M_profile_resize(__old_size); 526 return __res; 527 } 528 529 template<typename _InputIter> 530 void 531 insert(_InputIter __first, _InputIter __last) 532 { 533 size_type __old_size = _Base::bucket_count(); 534 _Base::insert(__first, __last); 535 this->_M_profile_resize(__old_size); 536 } 537 538 void 539 swap(unordered_multimap& __x) 540 noexcept( noexcept(__x._M_base().swap(__x)) ) 541 { 542 _Base::swap(__x._M_base()); 543 this->_M_swap(__x); 544 } 545 546 void 547 rehash(size_type __n) 548 { 549 size_type __old_size = _Base::bucket_count(); 550 _Base::rehash(__n); 551 this->_M_profile_resize(__old_size); 552 } 553 }; 554 555 template<typename _Key, typename _Tp, typename _Hash, 556 typename _Pred, typename _Alloc> 557 inline void 558 swap(unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 559 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 560 { __x.swap(__y); } 561 562 template<typename _Key, typename _Tp, typename _Hash, 563 typename _Pred, typename _Alloc> 564 inline bool 565 operator==(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 566 const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 567 { return static_cast<const _GLIBCXX_STD_BASE&>(__x) == __y; } 568 569 template<typename _Key, typename _Tp, typename _Hash, 570 typename _Pred, typename _Alloc> 571 inline bool 572 operator!=(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 573 const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 574 { return !(__x == __y); } 575 576} // namespace __profile 577} // namespace std 578 579#undef _GLIBCXX_BASE 580#undef _GLIBCXX_STD_BASE 581 582#endif // C++11 583 584#endif 585