1// Profiling unordered_map/unordered_multimap implementation -*- C++ -*- 2 3// Copyright (C) 2009, 2010, 2011, 2012 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#ifndef __GXX_EXPERIMENTAL_CXX0X__ 32# include <bits/c++0x_warning.h> 33#else 34# include <unordered_map> 35 36#include <profile/base.h> 37 38#define _GLIBCXX_BASE unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc> 39#define _GLIBCXX_STD_BASE _GLIBCXX_STD_C::_GLIBCXX_BASE 40 41namespace std _GLIBCXX_VISIBILITY(default) 42{ 43namespace __profile 44{ 45 /// Class std::unordered_map wrapper with performance instrumentation. 46 template<typename _Key, typename _Tp, 47 typename _Hash = std::hash<_Key>, 48 typename _Pred = std::equal_to<_Key>, 49 typename _Alloc = std::allocator<_Key> > 50 class unordered_map 51 : public _GLIBCXX_STD_BASE 52 { 53 typedef typename _GLIBCXX_STD_BASE _Base; 54 55 public: 56 typedef typename _Base::size_type size_type; 57 typedef typename _Base::hasher hasher; 58 typedef typename _Base::key_equal key_equal; 59 typedef typename _Base::allocator_type allocator_type; 60 typedef typename _Base::key_type key_type; 61 typedef typename _Base::value_type value_type; 62 typedef typename _Base::difference_type difference_type; 63 typedef typename _Base::reference reference; 64 typedef typename _Base::const_reference const_reference; 65 typedef typename _Base::mapped_type mapped_type; 66 67 typedef typename _Base::iterator iterator; 68 typedef typename _Base::const_iterator const_iterator; 69 70 explicit 71 unordered_map(size_type __n = 10, 72 const hasher& __hf = hasher(), 73 const key_equal& __eql = key_equal(), 74 const allocator_type& __a = allocator_type()) 75 : _Base(__n, __hf, __eql, __a) 76 { 77 __profcxx_hashtable_construct(this, _Base::bucket_count()); 78 __profcxx_hashtable_construct2(this); 79 } 80 81 template<typename _InputIterator> 82 unordered_map(_InputIterator __f, _InputIterator __l, 83 size_type __n = 0, 84 const hasher& __hf = hasher(), 85 const key_equal& __eql = key_equal(), 86 const allocator_type& __a = allocator_type()) 87 : _Base(__f, __l, __n, __hf, __eql, __a) 88 { 89 __profcxx_hashtable_construct(this, _Base::bucket_count()); 90 __profcxx_hashtable_construct2(this); 91 } 92 93 unordered_map(const unordered_map& __x) 94 : _Base(__x) 95 { 96 __profcxx_hashtable_construct(this, _Base::bucket_count()); 97 __profcxx_hashtable_construct2(this); 98 } 99 100 unordered_map(const _Base& __x) 101 : _Base(__x) 102 { 103 __profcxx_hashtable_construct(this, _Base::bucket_count()); 104 __profcxx_hashtable_construct2(this); 105 } 106 107 unordered_map(unordered_map&& __x) 108 : _Base(std::move(__x)) 109 { 110 __profcxx_hashtable_construct(this, _Base::bucket_count()); 111 __profcxx_hashtable_construct2(this); 112 } 113 114 unordered_map(initializer_list<value_type> __l, 115 size_type __n = 0, 116 const hasher& __hf = hasher(), 117 const key_equal& __eql = key_equal(), 118 const allocator_type& __a = allocator_type()) 119 : _Base(__l, __n, __hf, __eql, __a) { } 120 121 unordered_map& 122 operator=(const unordered_map& __x) 123 { 124 *static_cast<_Base*>(this) = __x; 125 return *this; 126 } 127 128 unordered_map& 129 operator=(unordered_map&& __x) 130 { 131 // NB: DR 1204. 132 // NB: DR 675. 133 this->clear(); 134 this->swap(__x); 135 return *this; 136 } 137 138 unordered_map& 139 operator=(initializer_list<value_type> __l) 140 { 141 this->clear(); 142 this->insert(__l); 143 return *this; 144 } 145 146 ~unordered_map() noexcept 147 { 148 __profcxx_hashtable_destruct(this, _Base::bucket_count(), 149 _Base::size()); 150 _M_profile_destruct(); 151 } 152 153 _Base& 154 _M_base() noexcept { return *this; } 155 156 const _Base& 157 _M_base() const noexcept { return *this; } 158 159 void 160 clear() noexcept 161 { 162 __profcxx_hashtable_destruct(this, _Base::bucket_count(), 163 _Base::size()); 164 _M_profile_destruct(); 165 _Base::clear(); 166 } 167 168 template<typename... _Args> 169 std::pair<iterator, bool> 170 emplace(_Args&&... __args) 171 { 172 size_type __old_size = _Base::bucket_count(); 173 std::pair<iterator, bool> __res 174 = _Base::emplace(std::forward<_Args>(__args)...); 175 _M_profile_resize(__old_size); 176 return __res; 177 } 178 179 template<typename... _Args> 180 iterator 181 emplace_hint(const_iterator __it, _Args&&... __args) 182 { 183 size_type __old_size = _Base::bucket_count(); 184 iterator __res 185 = _Base::emplace_hint(__it, std::forward<_Args>(__args)...); 186 _M_profile_resize(__old_size); 187 return __res; 188 } 189 190 void 191 insert(std::initializer_list<value_type> __l) 192 { 193 size_type __old_size = _Base::bucket_count(); 194 _Base::insert(__l); 195 _M_profile_resize(__old_size); 196 } 197 198 std::pair<iterator, bool> 199 insert(const value_type& __obj) 200 { 201 size_type __old_size = _Base::bucket_count(); 202 std::pair<iterator, bool> __res = _Base::insert(__obj); 203 _M_profile_resize(__old_size); 204 return __res; 205 } 206 207 iterator 208 insert(const_iterator __iter, const value_type& __v) 209 { 210 size_type __old_size = _Base::bucket_count(); 211 iterator __res = _Base::insert(__iter, __v); 212 _M_profile_resize(__old_size); 213 return __res; 214 } 215 216 template<typename _Pair, typename = typename 217 std::enable_if<std::is_constructible<value_type, 218 _Pair&&>::value>::type> 219 std::pair<iterator, bool> 220 insert(_Pair&& __obj) 221 { 222 size_type __old_size = _Base::bucket_count(); 223 std::pair<iterator, bool> __res 224 = _Base::insert(std::forward<_Pair>(__obj)); 225 _M_profile_resize(__old_size); 226 return __res; 227 } 228 229 template<typename _Pair, typename = typename 230 std::enable_if<std::is_constructible<value_type, 231 _Pair&&>::value>::type> 232 iterator 233 insert(const_iterator __iter, _Pair&& __v) 234 { 235 size_type __old_size = _Base::bucket_count(); 236 iterator __res = _Base::insert(__iter, std::forward<_Pair>(__v)); 237 _M_profile_resize(__old_size); 238 return __res; 239 } 240 241 template<typename _InputIter> 242 void 243 insert(_InputIter __first, _InputIter __last) 244 { 245 size_type __old_size = _Base::bucket_count(); 246 _Base::insert(__first, __last); 247 _M_profile_resize(__old_size); 248 } 249 250 void 251 insert(const value_type* __first, const value_type* __last) 252 { 253 size_type __old_size = _Base::bucket_count(); 254 _Base::insert(__first, __last); 255 _M_profile_resize(__old_size); 256 } 257 258 // operator[] 259 mapped_type& 260 operator[](const _Key& __k) 261 { 262 size_type __old_size = _Base::bucket_count(); 263 mapped_type& __res = _M_base()[__k]; 264 _M_profile_resize(__old_size); 265 return __res; 266 } 267 268 mapped_type& 269 operator[](_Key&& __k) 270 { 271 size_type __old_size = _Base::bucket_count(); 272 mapped_type& __res = _M_base()[std::move(__k)]; 273 _M_profile_resize(__old_size); 274 return __res; 275 } 276 277 void 278 swap(unordered_map& __x) 279 { _Base::swap(__x); } 280 281 void rehash(size_type __n) 282 { 283 size_type __old_size = _Base::bucket_count(); 284 _Base::rehash(__n); 285 _M_profile_resize(__old_size); 286 } 287 288 private: 289 void 290 _M_profile_resize(size_type __old_size) 291 { 292 size_type __new_size = _Base::bucket_count(); 293 if (__old_size != __new_size) 294 __profcxx_hashtable_resize(this, __old_size, __new_size); 295 } 296 297 void 298 _M_profile_destruct() 299 { 300 size_type __hops = 0, __lc = 0, __chain = 0; 301 iterator __it = this->begin(); 302 while (__it != this->end()) 303 { 304 size_type __bkt = this->bucket(__it->first); 305 auto __lit = this->begin(__bkt); 306 auto __lend = this->end(__bkt); 307 for (++__it, ++__lit; __lit != __lend; ++__it, ++__lit) 308 ++__chain; 309 if (__chain) 310 { 311 ++__chain; 312 __lc = __lc > __chain ? __lc : __chain; 313 __hops += __chain * (__chain - 1) / 2; 314 __chain = 0; 315 } 316 } 317 __profcxx_hashtable_destruct2(this, __lc, _Base::size(), __hops); 318 } 319 }; 320 321 template<typename _Key, typename _Tp, typename _Hash, 322 typename _Pred, typename _Alloc> 323 inline void 324 swap(unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 325 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 326 { __x.swap(__y); } 327 328 template<typename _Key, typename _Tp, typename _Hash, 329 typename _Pred, typename _Alloc> 330 inline bool 331 operator==(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 332 const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 333 { return __x._M_equal(__y); } 334 335 template<typename _Key, typename _Tp, typename _Hash, 336 typename _Pred, typename _Alloc> 337 inline bool 338 operator!=(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 339 const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 340 { return !(__x == __y); } 341 342#undef _GLIBCXX_BASE 343#undef _GLIBCXX_STD_BASE 344#define _GLIBCXX_BASE unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc> 345#define _GLIBCXX_STD_BASE _GLIBCXX_STD_C::_GLIBCXX_BASE 346 347 /// Class std::unordered_multimap wrapper with performance instrumentation. 348 template<typename _Key, typename _Tp, 349 typename _Hash = std::hash<_Key>, 350 typename _Pred = std::equal_to<_Key>, 351 typename _Alloc = std::allocator<_Key> > 352 class unordered_multimap 353 : public _GLIBCXX_STD_BASE 354 { 355 typedef typename _GLIBCXX_STD_BASE _Base; 356 357 public: 358 typedef typename _Base::size_type size_type; 359 typedef typename _Base::hasher hasher; 360 typedef typename _Base::key_equal key_equal; 361 typedef typename _Base::allocator_type allocator_type; 362 typedef typename _Base::key_type key_type; 363 typedef typename _Base::value_type value_type; 364 typedef typename _Base::difference_type difference_type; 365 typedef typename _Base::reference reference; 366 typedef typename _Base::const_reference const_reference; 367 368 typedef typename _Base::iterator iterator; 369 typedef typename _Base::const_iterator const_iterator; 370 371 explicit 372 unordered_multimap(size_type __n = 10, 373 const hasher& __hf = hasher(), 374 const key_equal& __eql = key_equal(), 375 const allocator_type& __a = allocator_type()) 376 : _Base(__n, __hf, __eql, __a) 377 { 378 __profcxx_hashtable_construct(this, _Base::bucket_count()); 379 } 380 template<typename _InputIterator> 381 unordered_multimap(_InputIterator __f, _InputIterator __l, 382 size_type __n = 0, 383 const hasher& __hf = hasher(), 384 const key_equal& __eql = key_equal(), 385 const allocator_type& __a = allocator_type()) 386 : _Base(__f, __l, __n, __hf, __eql, __a) 387 { 388 __profcxx_hashtable_construct(this, _Base::bucket_count()); 389 } 390 391 unordered_multimap(const unordered_multimap& __x) 392 : _Base(__x) 393 { 394 __profcxx_hashtable_construct(this, _Base::bucket_count()); 395 } 396 397 unordered_multimap(const _Base& __x) 398 : _Base(__x) 399 { 400 __profcxx_hashtable_construct(this, _Base::bucket_count()); 401 } 402 403 unordered_multimap(unordered_multimap&& __x) 404 : _Base(std::move(__x)) 405 { 406 __profcxx_hashtable_construct(this, _Base::bucket_count()); 407 } 408 409 unordered_multimap(initializer_list<value_type> __l, 410 size_type __n = 0, 411 const hasher& __hf = hasher(), 412 const key_equal& __eql = key_equal(), 413 const allocator_type& __a = allocator_type()) 414 : _Base(__l, __n, __hf, __eql, __a) { } 415 416 unordered_multimap& 417 operator=(const unordered_multimap& __x) 418 { 419 *static_cast<_Base*>(this) = __x; 420 return *this; 421 } 422 423 unordered_multimap& 424 operator=(unordered_multimap&& __x) 425 { 426 // NB: DR 1204. 427 // NB: DR 675. 428 this->clear(); 429 this->swap(__x); 430 return *this; 431 } 432 433 unordered_multimap& 434 operator=(initializer_list<value_type> __l) 435 { 436 this->clear(); 437 this->insert(__l); 438 return *this; 439 } 440 441 ~unordered_multimap() noexcept 442 { 443 __profcxx_hashtable_destruct(this, _Base::bucket_count(), 444 _Base::size()); 445 _M_profile_destruct(); 446 } 447 448 void 449 clear() noexcept 450 { 451 __profcxx_hashtable_destruct(this, _Base::bucket_count(), 452 _Base::size()); 453 _M_profile_destruct(); 454 _Base::clear(); 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 _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 _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 _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 _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 _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 _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 _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 _M_profile_resize(__old_size); 536 } 537 538 void 539 insert(const value_type* __first, const value_type* __last) 540 { 541 size_type __old_size = _Base::bucket_count(); 542 _Base::insert(__first, __last); 543 _M_profile_resize(__old_size); 544 } 545 546 void 547 swap(unordered_multimap& __x) 548 { _Base::swap(__x); } 549 550 void rehash(size_type __n) 551 { 552 size_type __old_size = _Base::bucket_count(); 553 _Base::rehash(__n); 554 _M_profile_resize(__old_size); 555 } 556 557 private: 558 void 559 _M_profile_resize(size_type __old_size) 560 { 561 size_type __new_size = _Base::bucket_count(); 562 if (__old_size != __new_size) 563 __profcxx_hashtable_resize(this, __old_size, __new_size); 564 } 565 566 void 567 _M_profile_destruct() 568 { 569 size_type __hops = 0, __lc = 0, __chain = 0; 570 iterator __it = this->begin(); 571 while (__it != this->end()) 572 { 573 size_type __bkt = this->bucket(__it->first); 574 auto __lit = this->begin(__bkt); 575 auto __lend = this->end(__bkt); 576 for (++__it, ++__lit; __lit != __lend; ++__it, ++__lit) 577 ++__chain; 578 if (__chain) 579 { 580 ++__chain; 581 __lc = __lc > __chain ? __lc : __chain; 582 __hops += __chain * (__chain - 1) / 2; 583 __chain = 0; 584 } 585 } 586 __profcxx_hashtable_destruct2(this, __lc, _Base::size(), __hops); 587 } 588 }; 589 590 template<typename _Key, typename _Tp, typename _Hash, 591 typename _Pred, typename _Alloc> 592 inline void 593 swap(unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 594 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 595 { __x.swap(__y); } 596 597 template<typename _Key, typename _Tp, typename _Hash, 598 typename _Pred, typename _Alloc> 599 inline bool 600 operator==(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 601 const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 602 { return __x._M_equal(__y); } 603 604 template<typename _Key, typename _Tp, typename _Hash, 605 typename _Pred, typename _Alloc> 606 inline bool 607 operator!=(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 608 const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 609 { return !(__x == __y); } 610 611} // namespace __profile 612} // namespace std 613 614#undef _GLIBCXX_BASE 615#undef _GLIBCXX_STD_BASE 616 617#endif // __GXX_EXPERIMENTAL_CXX0X__ 618 619#endif 620