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