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