1 // Profiling unordered_map/unordered_multimap implementation -*- C++ -*- 2 3 // Copyright (C) 2009, 2010 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 2, 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 // You should have received a copy of the GNU General Public License along 17 // with this library; see the file COPYING. If not, write to the Free 18 // Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, 19 // USA. 20 21 // As a special exception, you may use this file as part of a free software 22 // library without restriction. Specifically, if other files instantiate 23 // templates or use macros or inline functions from this file, or you compile 24 // this file and link it with other files to produce an executable, this 25 // file does not by itself cause the resulting executable to be covered by 26 // the GNU General Public License. This exception does not however 27 // invalidate any other reasons why the executable file might be covered by 28 // the GNU General Public License. 29 30 /** @file profile/unordered_map 31 * This file is a GNU profile extension to the Standard C++ Library. 32 */ 33 34 #ifndef _GLIBCXX_PROFILE_UNORDERED_MAP 35 #define _GLIBCXX_PROFILE_UNORDERED_MAP 1 36 37 #ifndef __GXX_EXPERIMENTAL_CXX0X__ 38 # include <bits/c++0x_warning.h> 39 #else 40 # include <unordered_map> 41 42 #include <profile/base.h> 43 44 #define _GLIBCXX_BASE unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc> 45 #define _GLIBCXX_STD_BASE _GLIBCXX_STD_C::_GLIBCXX_BASE 46 47 namespace std _GLIBCXX_VISIBILITY(default) 48 { 49 namespace __profile 50 { 51 /// Class std::unordered_map wrapper with performance instrumentation. 52 template<typename _Key, typename _Tp, 53 typename _Hash = std::hash<_Key>, 54 typename _Pred = std::equal_to<_Key>, 55 typename _Alloc = std::allocator<_Key> > 56 class unordered_map 57 : public _GLIBCXX_STD_BASE 58 { 59 typedef typename _GLIBCXX_STD_BASE _Base; 60 61 public: 62 typedef typename _Base::size_type size_type; 63 typedef typename _Base::hasher hasher; 64 typedef typename _Base::key_equal key_equal; 65 typedef typename _Base::allocator_type allocator_type; 66 typedef typename _Base::key_type key_type; 67 typedef typename _Base::value_type value_type; 68 typedef typename _Base::difference_type difference_type; 69 typedef typename _Base::reference reference; 70 typedef typename _Base::const_reference const_reference; 71 typedef typename _Base::mapped_type mapped_type; 72 73 typedef typename _Base::iterator iterator; 74 typedef typename _Base::const_iterator const_iterator; 75 76 explicit 77 unordered_map(size_type __n = 10, 78 const hasher& __hf = hasher(), 79 const key_equal& __eql = key_equal(), 80 const allocator_type& __a = allocator_type()) 81 : _Base(__n, __hf, __eql, __a) 82 { 83 __profcxx_hashtable_construct(this, _Base::bucket_count()); 84 __profcxx_hashtable_construct2(this); 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 __profcxx_hashtable_construct(this, _Base::bucket_count()); 96 __profcxx_hashtable_construct2(this); 97 } 98 99 unordered_map(const _Base& __x) 100 : _Base(__x) 101 { 102 __profcxx_hashtable_construct(this, _Base::bucket_count()); 103 __profcxx_hashtable_construct2(this); 104 } 105 106 unordered_map(unordered_map&& __x) 107 : _Base(std::move(__x)) 108 { 109 __profcxx_hashtable_construct(this, _Base::bucket_count()); 110 __profcxx_hashtable_construct2(this); 111 } 112 113 unordered_map(initializer_list<value_type> __l, 114 size_type __n = 0, 115 const hasher& __hf = hasher(), 116 const key_equal& __eql = key_equal(), 117 const allocator_type& __a = allocator_type()) 118 : _Base(__l, __n, __hf, __eql, __a) { } 119 120 unordered_map& 121 operator=(const unordered_map& __x) 122 { 123 *static_cast<_Base*>(this) = __x; 124 return *this; 125 } 126 127 unordered_map& 128 operator=(unordered_map&& __x) 129 { 130 // NB: DR 1204. 131 // NB: DR 675. 132 this->clear(); 133 this->swap(__x); 134 return *this; 135 } 136 137 unordered_map& 138 operator=(initializer_list<value_type> __l) 139 { 140 this->clear(); 141 this->insert(__l); 142 return *this; 143 } 144 145 ~unordered_map() 146 { 147 __profcxx_hashtable_destruct(this, _Base::bucket_count(), 148 _Base::size()); 149 _M_profile_destruct(); 150 } 151 152 _Base& 153 _M_base() { return *this; } 154 155 const _Base& 156 _M_base() const { return *this; } 157 158 159 void 160 clear() 161 { 162 __profcxx_hashtable_destruct(this, _Base::bucket_count(), 163 _Base::size()); 164 _M_profile_destruct(); 165 _Base::clear(); 166 } 167 168 void 169 insert(std::initializer_list<value_type> __l) 170 { 171 size_type __old_size = _Base::bucket_count(); 172 _Base::insert(__l); 173 _M_profile_resize(__old_size); 174 } 175 176 std::pair<iterator, bool> 177 insert(const value_type& __obj) 178 { 179 size_type __old_size = _Base::bucket_count(); 180 std::pair<iterator, bool> __res = _Base::insert(__obj); 181 _M_profile_resize(__old_size); 182 return __res; 183 } 184 185 iterator 186 insert(const_iterator __iter, const value_type& __v) 187 { 188 size_type __old_size = _Base::bucket_count(); 189 iterator __res = _Base::insert(__iter, __v); 190 _M_profile_resize(__old_size); 191 return __res; 192 } 193 194 template<typename _Pair, typename = typename 195 std::enable_if<std::is_convertible<_Pair, 196 value_type>::value>::type> 197 std::pair<iterator, bool> 198 insert(_Pair&& __obj) 199 { 200 size_type __old_size = _Base::bucket_count(); 201 std::pair<iterator, bool> __res 202 = _Base::insert(std::forward<_Pair>(__obj)); 203 _M_profile_resize(__old_size); 204 return __res; 205 } 206 207 template<typename _Pair, typename = typename 208 std::enable_if<std::is_convertible<_Pair, 209 value_type>::value>::type> 210 iterator 211 insert(const_iterator __iter, _Pair&& __v) 212 { 213 size_type __old_size = _Base::bucket_count(); 214 iterator __res = _Base::insert(__iter, std::forward<_Pair>(__v)); 215 _M_profile_resize(__old_size); 216 return __res; 217 } 218 219 template<typename _InputIter> 220 void 221 insert(_InputIter __first, _InputIter __last) 222 { 223 size_type __old_size = _Base::bucket_count(); 224 _Base::insert(__first, __last); 225 _M_profile_resize(__old_size); 226 } 227 228 void 229 insert(const value_type* __first, const value_type* __last) 230 { 231 size_type __old_size = _Base::bucket_count(); 232 _Base::insert(__first, __last); 233 _M_profile_resize(__old_size); 234 } 235 236 // operator[] 237 mapped_type& 238 operator[](const _Key& __k) 239 { 240 size_type __old_size = _Base::bucket_count(); 241 mapped_type& __res = _M_base()[__k]; 242 _M_profile_resize(__old_size); 243 return __res; 244 } 245 246 mapped_type& 247 operator[](_Key&& __k) 248 { 249 size_type __old_size = _Base::bucket_count(); 250 mapped_type& __res = _M_base()[std::move(__k)]; 251 _M_profile_resize(__old_size); 252 return __res; 253 } 254 255 void 256 swap(unordered_map& __x) 257 { _Base::swap(__x); } 258 259 void rehash(size_type __n) 260 { 261 size_type __old_size = _Base::bucket_count(); 262 _Base::rehash(__n); 263 _M_profile_resize(__old_size); 264 } 265 266 private: 267 void 268 _M_profile_resize(size_type __old_size) 269 { 270 size_type __new_size = _Base::bucket_count(); 271 if (__old_size != __new_size) 272 __profcxx_hashtable_resize(this, __old_size, __new_size); 273 } 274 275 void 276 _M_profile_destruct() 277 { 278 size_type __hops = 0, __lc = 0, __chain = 0; 279 for (iterator __it = _M_base().begin(); __it != _M_base().end(); 280 ++__it) 281 { 282 while (__it._M_cur_node->_M_next) 283 { 284 ++__chain; 285 ++__it; 286 } 287 if (__chain) 288 { 289 ++__chain; 290 __lc = __lc > __chain ? __lc : __chain; 291 __hops += __chain * (__chain - 1) / 2; 292 __chain = 0; 293 } 294 } 295 __profcxx_hashtable_destruct2(this, __lc, _Base::size(), __hops); 296 } 297 }; 298 299 template<typename _Key, typename _Tp, typename _Hash, 300 typename _Pred, typename _Alloc> 301 inline void 302 swap(unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 303 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 304 { __x.swap(__y); } 305 306 template<typename _Key, typename _Tp, typename _Hash, 307 typename _Pred, typename _Alloc> 308 inline bool 309 operator==(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 310 const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 311 { return __x._M_equal(__y); } 312 313 template<typename _Key, typename _Tp, typename _Hash, 314 typename _Pred, typename _Alloc> 315 inline bool 316 operator!=(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 317 const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 318 { return !(__x == __y); } 319 320 #undef _GLIBCXX_BASE 321 #undef _GLIBCXX_STD_BASE 322 #define _GLIBCXX_BASE unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc> 323 #define _GLIBCXX_STD_BASE _GLIBCXX_STD_C::_GLIBCXX_BASE 324 325 /// Class std::unordered_multimap wrapper with performance instrumentation. 326 template<typename _Key, typename _Tp, 327 typename _Hash = std::hash<_Key>, 328 typename _Pred = std::equal_to<_Key>, 329 typename _Alloc = std::allocator<_Key> > 330 class unordered_multimap 331 : public _GLIBCXX_STD_BASE 332 { 333 typedef typename _GLIBCXX_STD_BASE _Base; 334 335 public: 336 typedef typename _Base::size_type size_type; 337 typedef typename _Base::hasher hasher; 338 typedef typename _Base::key_equal key_equal; 339 typedef typename _Base::allocator_type allocator_type; 340 typedef typename _Base::key_type key_type; 341 typedef typename _Base::value_type value_type; 342 typedef typename _Base::difference_type difference_type; 343 typedef typename _Base::reference reference; 344 typedef typename _Base::const_reference const_reference; 345 346 typedef typename _Base::iterator iterator; 347 typedef typename _Base::const_iterator const_iterator; 348 349 explicit 350 unordered_multimap(size_type __n = 10, 351 const hasher& __hf = hasher(), 352 const key_equal& __eql = key_equal(), 353 const allocator_type& __a = allocator_type()) 354 : _Base(__n, __hf, __eql, __a) 355 { 356 __profcxx_hashtable_construct(this, _Base::bucket_count()); 357 } 358 template<typename _InputIterator> 359 unordered_multimap(_InputIterator __f, _InputIterator __l, 360 size_type __n = 0, 361 const hasher& __hf = hasher(), 362 const key_equal& __eql = key_equal(), 363 const allocator_type& __a = allocator_type()) 364 : _Base(__f, __l, __n, __hf, __eql, __a) 365 { 366 __profcxx_hashtable_construct(this, _Base::bucket_count()); 367 } 368 369 unordered_multimap(const _Base& __x) 370 : _Base(__x) 371 { 372 __profcxx_hashtable_construct(this, _Base::bucket_count()); 373 } 374 375 unordered_multimap(unordered_multimap&& __x) 376 : _Base(std::move(__x)) 377 { 378 __profcxx_hashtable_construct(this, _Base::bucket_count()); 379 } 380 381 unordered_multimap(initializer_list<value_type> __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(__l, __n, __hf, __eql, __a) { } 387 388 unordered_multimap& 389 operator=(const unordered_multimap& __x) 390 { 391 *static_cast<_Base*>(this) = __x; 392 return *this; 393 } 394 395 unordered_multimap& 396 operator=(unordered_multimap&& __x) 397 { 398 // NB: DR 1204. 399 // NB: DR 675. 400 this->clear(); 401 this->swap(__x); 402 return *this; 403 } 404 405 unordered_multimap& 406 operator=(initializer_list<value_type> __l) 407 { 408 this->clear(); 409 this->insert(__l); 410 return *this; 411 } 412 413 ~unordered_multimap() 414 { 415 __profcxx_hashtable_destruct(this, _Base::bucket_count(), 416 _Base::size()); 417 _M_profile_destruct(); 418 } 419 420 _Base& 421 _M_base() { return *this; } 422 423 const _Base& 424 _M_base() const { return *this; } 425 426 427 void 428 clear() 429 { 430 __profcxx_hashtable_destruct(this, _Base::bucket_count(), 431 _Base::size()); 432 _M_profile_destruct(); 433 _Base::clear(); 434 } 435 436 void 437 insert(std::initializer_list<value_type> __l) 438 { 439 size_type __old_size = _Base::bucket_count(); 440 _Base::insert(__l); 441 _M_profile_resize(__old_size, _Base::bucket_count()); 442 } 443 444 iterator 445 insert(const value_type& __obj) 446 { 447 size_type __old_size = _Base::bucket_count(); 448 iterator __res = _Base::insert(__obj); 449 _M_profile_resize(__old_size, _Base::bucket_count()); 450 return __res; 451 } 452 453 iterator 454 insert(const_iterator __iter, const value_type& __v) 455 { 456 size_type __old_size = _Base::bucket_count(); 457 iterator __res = _Base::insert(__iter, __v); 458 _M_profile_resize(__old_size, _Base::bucket_count()); 459 return __res; 460 } 461 462 template<typename _Pair, typename = typename 463 std::enable_if<std::is_convertible<_Pair, 464 value_type>::value>::type> 465 iterator 466 insert(_Pair&& __obj) 467 { 468 size_type __old_size = _Base::bucket_count(); 469 iterator __res = _Base::insert(std::forward<_Pair>(__obj)); 470 _M_profile_resize(__old_size, _Base::bucket_count()); 471 return __res; 472 } 473 474 template<typename _Pair, typename = typename 475 std::enable_if<std::is_convertible<_Pair, 476 value_type>::value>::type> 477 iterator 478 insert(const_iterator __iter, _Pair&& __v) 479 { 480 size_type __old_size = _Base::bucket_count(); 481 iterator __res = _Base::insert(__iter, std::forward<_Pair>(__v)); 482 _M_profile_resize(__old_size, _Base::bucket_count()); 483 return __res; 484 } 485 486 template<typename _InputIter> 487 void 488 insert(_InputIter __first, _InputIter __last) 489 { 490 size_type __old_size = _Base::bucket_count(); 491 _Base::insert(__first, __last); 492 _M_profile_resize(__old_size, _Base::bucket_count()); 493 } 494 495 void 496 insert(const value_type* __first, const value_type* __last) 497 { 498 size_type __old_size = _Base::bucket_count(); 499 _Base::insert(__first, __last); 500 _M_profile_resize(__old_size, _Base::bucket_count()); 501 } 502 503 void 504 swap(unordered_multimap& __x) 505 { _Base::swap(__x); } 506 507 void rehash(size_type __n) 508 { 509 size_type __old_size = _Base::bucket_count(); 510 _Base::rehash(__n); 511 _M_profile_resize(__old_size, _Base::bucket_count()); 512 } 513 514 private: 515 void 516 _M_profile_resize(size_type __old_size, size_type __new_size) 517 { 518 if (__old_size != __new_size) 519 __profcxx_hashtable_resize(this, __old_size, __new_size); 520 } 521 522 void 523 _M_profile_destruct() 524 { 525 size_type __hops = 0, __lc = 0, __chain = 0; 526 for (iterator __it = _M_base().begin(); __it != _M_base().end(); 527 ++__it) 528 { 529 while (__it._M_cur_node->_M_next) 530 { 531 ++__chain; 532 ++__it; 533 } 534 if (__chain) 535 { 536 ++__chain; 537 __lc = __lc > __chain ? __lc : __chain; 538 __hops += __chain * (__chain - 1) / 2; 539 __chain = 0; 540 } 541 } 542 __profcxx_hashtable_destruct2(this, __lc, _Base::size(), __hops); 543 } 544 545 }; 546 547 template<typename _Key, typename _Tp, typename _Hash, 548 typename _Pred, typename _Alloc> 549 inline void 550 swap(unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 551 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 552 { __x.swap(__y); } 553 554 template<typename _Key, typename _Tp, typename _Hash, 555 typename _Pred, typename _Alloc> 556 inline bool 557 operator==(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 558 const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 559 { return __x._M_equal(__y); } 560 561 template<typename _Key, typename _Tp, typename _Hash, 562 typename _Pred, typename _Alloc> 563 inline bool 564 operator!=(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 565 const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 566 { return !(__x == __y); } 567 568 } // namespace __profile 569 } // namespace std 570 571 #undef _GLIBCXX_BASE 572 #undef _GLIBCXX_STD_BASE 573 574 #endif // __GXX_EXPERIMENTAL_CXX0X__ 575 576 #endif 577
