1136644Sache// Profiling set implementation -*- C++ -*- 2136644Sache 321308Sache// Copyright (C) 2009-2019 Free Software Foundation, Inc. 421308Sache// 521308Sache// This file is part of the GNU ISO C++ Library. This library is free 621308Sache// software; you can redistribute it and/or modify it under the 721308Sache// terms of the GNU General Public License as published by the 821308Sache// Free Software Foundation; either version 3, or (at your option) 958310Sache// any later version. 1021308Sache 1121308Sache// This library is distributed in the hope that it will be useful, 1221308Sache// but WITHOUT ANY WARRANTY; without even the implied warranty of 1321308Sache// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 1421308Sache// GNU General Public License for more details. 1521308Sache 1621308Sache// Under Section 7 of GPL version 3, you are granted additional 1721308Sache// permissions described in the GCC Runtime Library Exception, version 1821308Sache// 3.1, as published by the Free Software Foundation. 1921308Sache 2058310Sache// You should have received a copy of the GNU General Public License and 2121308Sache// a copy of the GCC Runtime Library Exception along with this program; 2221308Sache// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see 2321308Sache// <http://www.gnu.org/licenses/>. 2421308Sache 2547558Sache/** @file profile/set.h 2647558Sache * This file is a GNU profile extension to the Standard C++ Library. 2747558Sache */ 2847558Sache 29136644Sache#ifndef _GLIBCXX_PROFILE_SET_H 30136644Sache#define _GLIBCXX_PROFILE_SET_H 1 3147558Sache 3247558Sache#include <profile/base.h> 3375406Sache#include <profile/ordered_base.h> 3447558Sache 3547558Sachenamespace std _GLIBCXX_VISIBILITY(default) 3675406Sache{ 3747558Sachenamespace __profile 3847558Sache{ 3947558Sache /// Class std::set wrapper with performance instrumentation. 4047558Sache template<typename _Key, typename _Compare = std::less<_Key>, 4147558Sache typename _Allocator = std::allocator<_Key> > 4247558Sache class set 4347558Sache : public _GLIBCXX_STD_C::set<_Key,_Compare,_Allocator>, 4447558Sache public _Ordered_profile<set<_Key, _Compare, _Allocator> > 4521308Sache { 4621308Sache typedef _GLIBCXX_STD_C::set<_Key, _Compare, _Allocator> _Base; 4721308Sache 48136644Sache typedef typename _Base::iterator _Base_iterator; 4947558Sache typedef typename _Base::const_iterator _Base_const_iterator; 5021308Sache 5121308Sache public: 52136644Sache // types: 53136644Sache typedef _Key key_type; 54136644Sache typedef _Key value_type; 5521308Sache typedef _Compare key_compare; 5621308Sache typedef _Compare value_compare; 5721308Sache typedef typename _Base::reference reference; 5821308Sache typedef typename _Base::const_reference const_reference; 5921308Sache 6021308Sache typedef __iterator_tracker<_Base_iterator, set> iterator; 6121308Sache typedef __iterator_tracker<_Base_const_iterator, 6221308Sache set> const_iterator; 6321308Sache typedef std::reverse_iterator<iterator> reverse_iterator; 6421308Sache typedef std::reverse_iterator<const_iterator> const_reverse_iterator; 6521308Sache 6621308Sache typedef typename _Base::size_type size_type; 6721308Sache typedef typename _Base::difference_type difference_type; 6821308Sache 6921308Sache // 23.3.3.1 construct/copy/destroy: 7021308Sache#if __cplusplus < 201103L 71119610Sache set() 7221308Sache : _Base() { } 7321308Sache set(const set& __x) 74119610Sache : _Base(__x) { } 7521308Sache ~set() { } 7621308Sache#else 77119610Sache set() = default; 7821308Sache set(const set&) = default; 7921308Sache set(set&&) = default; 8021308Sache ~set() = default; 8121308Sache#endif 8221308Sache 83119610Sache explicit set(const _Compare& __comp, 8421308Sache const _Allocator& __a = _Allocator()) 85136644Sache : _Base(__comp, __a) { } 86136644Sache 87136644Sache#if __cplusplus >= 201103L 88136644Sache template<typename _InputIterator, 8921308Sache typename = std::_RequireInputIter<_InputIterator>> 9021308Sache#else 9121308Sache template<typename _InputIterator> 92119610Sache#endif 9321308Sache set(_InputIterator __first, _InputIterator __last, 94136644Sache const _Compare& __comp = _Compare(), 95136644Sache const _Allocator& __a = _Allocator()) 96136644Sache : _Base(__first, __last, __comp, __a) { } 97136644Sache 9821308Sache#if __cplusplus >= 201103L 9921308Sache set(initializer_list<value_type> __l, 10021308Sache const _Compare& __comp = _Compare(), 101119610Sache const _Allocator& __a = _Allocator()) 10221308Sache : _Base(__l, __comp, __a) { } 10321308Sache 104119610Sache explicit 10521308Sache set(const _Allocator& __a) 10621308Sache : _Base(__a) { } 107119610Sache 10821308Sache set(const set& __x, const _Allocator& __a) 10921308Sache : _Base(__x, __a) { } 11021308Sache 11121308Sache set(set&& __x, const _Allocator& __a) 112119610Sache noexcept( noexcept(_Base(std::move(__x), __a)) ) 11321308Sache : _Base(std::move(__x), __a) { } 11421308Sache 115119610Sache set(initializer_list<value_type> __l, const _Allocator& __a) 11621308Sache : _Base(__l, __a) { } 11721308Sache 11821308Sache template<typename _InputIterator> 11921308Sache set(_InputIterator __first, _InputIterator __last, 12021308Sache const _Allocator& __a) 12121308Sache : _Base(__first, __last, __a) { } 122119610Sache#endif 12321308Sache 12421308Sache set(const _Base& __x) 12521308Sache : _Base(__x) { } 126119610Sache 12721308Sache#if __cplusplus < 201103L 12821308Sache set& 12921308Sache operator=(const set& __x) 130119610Sache { 13121308Sache this->_M_profile_destruct(); 13221308Sache _M_base() = __x; 13321308Sache this->_M_profile_construct(); 134119610Sache return *this; 13521308Sache } 136136644Sache#else 137136644Sache set& 138136644Sache operator=(const set&) = default; 139136644Sache 14021308Sache set& 14121308Sache operator=(set&&) = default; 142119610Sache 14321308Sache set& 14421308Sache operator=(initializer_list<value_type> __l) 14521308Sache { 14621308Sache this->_M_profile_destruct(); 147119610Sache _M_base() = __l; 14821308Sache this->_M_profile_construct(); 14921308Sache return *this; 15021308Sache } 15121308Sache#endif 152119610Sache 15321308Sache // iterators 15421308Sache iterator 15521308Sache begin() _GLIBCXX_NOEXCEPT 15621308Sache { return iterator(_Base::begin(), this); } 157119610Sache 15821308Sache const_iterator 15921308Sache begin() const _GLIBCXX_NOEXCEPT 16021308Sache { return const_iterator(_Base::begin(), this); } 16121308Sache 16221308Sache iterator 16321308Sache end() _GLIBCXX_NOEXCEPT 16421308Sache { return iterator(_Base::end(), this); } 16521308Sache 16621308Sache const_iterator 167119610Sache end() const _GLIBCXX_NOEXCEPT 16821308Sache { return const_iterator(_Base::end(), this); } 16921308Sache 17047558Sache#if __cplusplus >= 201103L 17147558Sache const_iterator 172119610Sache cbegin() const noexcept 17321308Sache { return const_iterator(_Base::cbegin(), this); } 17421308Sache 17521308Sache const_iterator 17621308Sache cend() const noexcept 17721308Sache { return const_iterator(_Base::cend(), this); } 17821308Sache#endif 179119610Sache 18021308Sache reverse_iterator 18121308Sache rbegin() _GLIBCXX_NOEXCEPT 18221308Sache { 18321308Sache __profcxx_map2umap_invalidate(this->_M_map2umap_info); 18421308Sache return reverse_iterator(end()); 18521308Sache } 186119610Sache 18721308Sache const_reverse_iterator 18821308Sache rbegin() const _GLIBCXX_NOEXCEPT 18921308Sache { 19021308Sache __profcxx_map2umap_invalidate(this->_M_map2umap_info); 19121308Sache return const_reverse_iterator(end()); 19221308Sache } 193119610Sache 19421308Sache reverse_iterator 19521308Sache rend() _GLIBCXX_NOEXCEPT 19621308Sache { 19721308Sache __profcxx_map2umap_invalidate(this->_M_map2umap_info); 198119610Sache return reverse_iterator(begin()); 19921308Sache } 20021308Sache 20121308Sache const_reverse_iterator 202119610Sache rend() const _GLIBCXX_NOEXCEPT 20321308Sache { 20421308Sache __profcxx_map2umap_invalidate(this->_M_map2umap_info); 205119610Sache return const_reverse_iterator(begin()); 20621308Sache } 20721308Sache 20821308Sache#if __cplusplus >= 201103L 20921308Sache const_reverse_iterator 21021308Sache crbegin() const noexcept 21121308Sache { 21221308Sache __profcxx_map2umap_invalidate(this->_M_map2umap_info); 21321308Sache return const_reverse_iterator(cend()); 21421308Sache } 21521308Sache 21621308Sache const_reverse_iterator 21721308Sache crend() const noexcept 21821308Sache { 21921308Sache __profcxx_map2umap_invalidate(this->_M_map2umap_info); 22021308Sache return const_reverse_iterator(cbegin()); 221119610Sache } 22221308Sache#endif 22321308Sache 22421308Sache void 22521308Sache swap(set& __x) 226119610Sache _GLIBCXX_NOEXCEPT_IF( noexcept(declval<_Base&>().swap(__x)) ) 22721308Sache { 22821308Sache _Base::swap(__x); 22947558Sache this->_M_swap(__x); 23047558Sache } 23147558Sache 23247558Sache // modifiers: 23347558Sache#if __cplusplus >= 201103L 234119610Sache template<typename... _Args> 23521308Sache std::pair<iterator, bool> 23621308Sache emplace(_Args&&... __args) 23721308Sache { 238119610Sache __profcxx_map2umap_insert(this->_M_map2umap_info, this->size(), 1); 23921308Sache auto __base_ret = _Base::emplace(std::forward<_Args>(__args)...); 24021308Sache return std::make_pair(iterator(__base_ret.first, this), 24121308Sache __base_ret.second); 24221308Sache } 24375406Sache 24421308Sache template<typename... _Args> 24521308Sache iterator 24675406Sache emplace_hint(const_iterator __pos, _Args&&... __args) 24721308Sache { 24821308Sache auto size_before = this->size(); 24921308Sache auto __res 25021308Sache = _Base::emplace_hint(__pos.base(), std::forward<_Args>(__args)...); 25121308Sache __profcxx_map2umap_insert(this->_M_map2umap_info, 252136644Sache size_before, _M_hint_used(__pos.base(), __res) ? 0 : 1); 253136644Sache return iterator(__res, this); 25475406Sache } 25575406Sache#endif 25675406Sache 25726497Sache std::pair<iterator, bool> 25826497Sache insert(const value_type& __x) 25926497Sache { 26075406Sache __profcxx_map2umap_insert(this->_M_map2umap_info, this->size(), 1); 26126497Sache std::pair<_Base_iterator, bool> __base_ret = _Base::insert(__x); 26247558Sache return std::make_pair(iterator(__base_ret.first, this), 26347558Sache __base_ret.second); 26447558Sache } 26547558Sache 26621308Sache#if __cplusplus >= 201103L 267 std::pair<iterator, bool> 268 insert(value_type&& __x) 269 { 270 __profcxx_map2umap_insert(this->_M_map2umap_info, this->size(), 1); 271 std::pair<_Base_iterator, bool> __base_ret 272 = _Base::insert(std::move(__x)); 273 return std::make_pair(iterator(__base_ret.first, this), 274 __base_ret.second); 275 } 276#endif 277 278 iterator 279 insert(const_iterator __pos, const value_type& __x) 280 { 281 size_type size_before = this->size(); 282 _Base_iterator __res = _Base::insert(__pos.base(), __x); 283 __profcxx_map2umap_insert(this->_M_map2umap_info, 284 size_before, _M_hint_used(__pos.base(), __res) ? 0 : 1); 285 return iterator(__res, this); 286 } 287 288#if __cplusplus >= 201103L 289 iterator 290 insert(const_iterator __pos, value_type&& __x) 291 { return iterator(_Base::insert(__pos.base(), std::move(__x)), this); } 292#endif 293 294 template<typename _InputIterator> 295 void 296 insert(_InputIterator __first, _InputIterator __last) 297 { 298 for (; __first != __last; ++__first) 299 insert(*__first); 300 } 301 302#if __cplusplus >= 201103L 303 void 304 insert(initializer_list<value_type> __l) 305 { insert(__l.begin(), __l.end()); } 306#endif 307 308#if __cplusplus >= 201103L 309 iterator 310 erase(const_iterator __pos) 311 { 312 __profcxx_map2umap_erase(this->_M_map2umap_info, this->size(), 1); 313 return iterator(_Base::erase(__pos.base()), this); 314 } 315#else 316 void 317 erase(iterator __pos) 318 { 319 __profcxx_map2umap_erase(this->_M_map2umap_info, this->size(), 1); 320 _Base::erase(__pos.base()); 321 } 322#endif 323 324 size_type 325 erase(const key_type& __x) 326 { 327 __profcxx_map2umap_find(this->_M_map2umap_info, this->size()); 328 __profcxx_map2umap_erase(this->_M_map2umap_info, this->size(), 1); 329 return _Base::erase(__x); 330 } 331 332#if __cplusplus >= 201103L 333 iterator 334 erase(const_iterator __first, const_iterator __last) 335 { 336 if (__first != __last) 337 { 338 iterator __ret; 339 for (; __first != __last;) 340 __ret = erase(__first++); 341 return __ret; 342 } 343 344 return iterator(_Base::erase(__first.base(), __last.base()), this); 345 } 346#else 347 void 348 erase(iterator __first, iterator __last) 349 { 350 for (; __first != __last;) 351 erase(__first++); 352 } 353#endif 354 355 void 356 clear() _GLIBCXX_NOEXCEPT 357 { 358 this->_M_profile_destruct(); 359 _Base::clear(); 360 this->_M_profile_construct(); 361 } 362 363 size_type 364 count(const key_type& __x) const 365 { 366 __profcxx_map2umap_find(this->_M_map2umap_info, this->size()); 367 return _Base::count(__x); 368 } 369 370#if __cplusplus > 201103L 371 template<typename _Kt, 372 typename _Req = 373 typename __has_is_transparent<_Compare, _Kt>::type> 374 size_type 375 count(const _Kt& __x) const 376 { 377 __profcxx_map2umap_find(this->_M_map2umap_info, this->size()); 378 return _Base::count(__x); 379 } 380#endif 381 382 // set operations: 383 iterator 384 find(const key_type& __x) 385 { 386 __profcxx_map2umap_find(this->_M_map2umap_info, this->size()); 387 return iterator(_Base::find(__x), this); 388 } 389 390 const_iterator 391 find(const key_type& __x) const 392 { 393 __profcxx_map2umap_find(this->_M_map2umap_info, this->size()); 394 return const_iterator(_Base::find(__x), this); 395 } 396 397#if __cplusplus > 201103L 398 template<typename _Kt, 399 typename _Req = 400 typename __has_is_transparent<_Compare, _Kt>::type> 401 iterator 402 find(const _Kt& __x) 403 { 404 __profcxx_map2umap_find(this->_M_map2umap_info, this->size()); 405 return { _Base::find(__x), this }; 406 } 407 408 template<typename _Kt, 409 typename _Req = 410 typename __has_is_transparent<_Compare, _Kt>::type> 411 const_iterator 412 find(const _Kt& __x) const 413 { 414 __profcxx_map2umap_find(this->_M_map2umap_info, this->size()); 415 return { _Base::find(__x), this }; 416 } 417#endif 418 419 iterator 420 lower_bound(const key_type& __x) 421 { 422 __profcxx_map2umap_find(this->_M_map2umap_info, this->size()); 423 __profcxx_map2umap_invalidate(this->_M_map2umap_info); 424 return iterator(_Base::lower_bound(__x), this); 425 } 426 427 const_iterator 428 lower_bound(const key_type& __x) const 429 { 430 __profcxx_map2umap_find(this->_M_map2umap_info, this->size()); 431 __profcxx_map2umap_invalidate(this->_M_map2umap_info); 432 return const_iterator(_Base::lower_bound(__x), this); 433 } 434 435#if __cplusplus > 201103L 436 template<typename _Kt, 437 typename _Req = 438 typename __has_is_transparent<_Compare, _Kt>::type> 439 iterator 440 lower_bound(const _Kt& __x) 441 { 442 __profcxx_map2umap_find(this->_M_map2umap_info, this->size()); 443 __profcxx_map2umap_invalidate(this->_M_map2umap_info); 444 return { _Base::lower_bound(__x), this }; 445 } 446 447 template<typename _Kt, 448 typename _Req = 449 typename __has_is_transparent<_Compare, _Kt>::type> 450 const_iterator 451 lower_bound(const _Kt& __x) const 452 { 453 __profcxx_map2umap_find(this->_M_map2umap_info, this->size()); 454 __profcxx_map2umap_invalidate(this->_M_map2umap_info); 455 return { _Base::lower_bound(__x), this }; 456 } 457#endif 458 459 iterator 460 upper_bound(const key_type& __x) 461 { 462 __profcxx_map2umap_find(this->_M_map2umap_info, this->size()); 463 __profcxx_map2umap_invalidate(this->_M_map2umap_info); 464 return iterator(_Base::upper_bound(__x), this); 465 } 466 467 const_iterator 468 upper_bound(const key_type& __x) const 469 { 470 __profcxx_map2umap_find(this->_M_map2umap_info, this->size()); 471 __profcxx_map2umap_invalidate(this->_M_map2umap_info); 472 return const_iterator(_Base::upper_bound(__x), this); 473 } 474 475#if __cplusplus > 201103L 476 template<typename _Kt, 477 typename _Req = 478 typename __has_is_transparent<_Compare, _Kt>::type> 479 iterator 480 upper_bound(const _Kt& __x) 481 { 482 __profcxx_map2umap_find(this->_M_map2umap_info, this->size()); 483 __profcxx_map2umap_invalidate(this->_M_map2umap_info); 484 return { _Base::upper_bound(__x), this }; 485 } 486 487 template<typename _Kt, 488 typename _Req = 489 typename __has_is_transparent<_Compare, _Kt>::type> 490 const_iterator 491 upper_bound(const _Kt& __x) const 492 { 493 __profcxx_map2umap_find(this->_M_map2umap_info, this->size()); 494 __profcxx_map2umap_invalidate(this->_M_map2umap_info); 495 return { _Base::upper_bound(__x), this }; 496 } 497#endif 498 499 std::pair<iterator, iterator> 500 equal_range(const key_type& __x) 501 { 502 __profcxx_map2umap_find(this->_M_map2umap_info, this->size()); 503 std::pair<_Base_iterator, _Base_iterator> __base_ret 504 = _Base::equal_range(__x); 505 return std::make_pair(iterator(__base_ret.first, this), 506 iterator(__base_ret.second, this)); 507 } 508 509 std::pair<const_iterator, const_iterator> 510 equal_range(const key_type& __x) const 511 { 512 __profcxx_map2umap_find(this->_M_map2umap_info, this->size()); 513 std::pair<_Base_const_iterator, _Base_const_iterator> __base_ret 514 = _Base::equal_range(__x); 515 return std::make_pair(const_iterator(__base_ret.first, this), 516 const_iterator(__base_ret.second, this)); 517 } 518 519#if __cplusplus > 201103L 520 template<typename _Kt, 521 typename _Req = 522 typename __has_is_transparent<_Compare, _Kt>::type> 523 std::pair<iterator, iterator> 524 equal_range(const _Kt& __x) 525 { 526 __profcxx_map2umap_find(this->_M_map2umap_info, this->size()); 527 auto __res = _Base::equal_range(__x); 528 return { { __res.first, this }, { __res.second, this } }; 529 } 530 531 template<typename _Kt, 532 typename _Req = 533 typename __has_is_transparent<_Compare, _Kt>::type> 534 std::pair<const_iterator, const_iterator> 535 equal_range(const _Kt& __x) const 536 { 537 __profcxx_map2umap_find(this->_M_map2umap_info, this->size()); 538 auto __res = _Base::equal_range(__x); 539 return { { __res.first, this }, { __res.second, this } }; 540 } 541#endif 542 543 _Base& 544 _M_base() _GLIBCXX_NOEXCEPT { return *this; } 545 546 const _Base& 547 _M_base() const _GLIBCXX_NOEXCEPT { return *this; } 548 549 private: 550 /** If hint is used we consider that the map and unordered_map 551 * operations have equivalent insertion cost so we do not update metrics 552 * about it. 553 * Note that to find out if hint has been used is libstdc++ 554 * implementation dependent. 555 */ 556 bool 557 _M_hint_used(_Base_const_iterator __hint, _Base_iterator __res) 558 { 559 return (__hint == __res 560 || (__hint == _M_base().end() && ++__res == _M_base().end()) 561 || (__hint != _M_base().end() && (++__hint == __res 562 || ++__res == --__hint))); 563 } 564 565 template<typename _K1, typename _C1, typename _A1> 566 friend bool 567 operator==(const set<_K1, _C1, _A1>&, const set<_K1, _C1, _A1>&); 568 569 template<typename _K1, typename _C1, typename _A1> 570 friend bool 571 operator<(const set<_K1, _C1, _A1>&, const set<_K1, _C1, _A1>&); 572 }; 573 574 template<typename _Key, typename _Compare, typename _Allocator> 575 inline bool 576 operator==(const set<_Key, _Compare, _Allocator>& __lhs, 577 const set<_Key, _Compare, _Allocator>& __rhs) 578 { 579 __profcxx_map2umap_invalidate(__lhs._M_map2umap_info); 580 __profcxx_map2umap_invalidate(__rhs._M_map2umap_info); 581 return __lhs._M_base() == __rhs._M_base(); 582 } 583 584 template<typename _Key, typename _Compare, typename _Allocator> 585 inline bool 586 operator<(const set<_Key, _Compare, _Allocator>& __lhs, 587 const set<_Key, _Compare, _Allocator>& __rhs) 588 { 589 __profcxx_map2umap_invalidate(__lhs._M_map2umap_info); 590 __profcxx_map2umap_invalidate(__rhs._M_map2umap_info); 591 return __lhs._M_base() < __rhs._M_base(); 592 } 593 594 template<typename _Key, typename _Compare, typename _Allocator> 595 inline bool 596 operator!=(const set<_Key, _Compare, _Allocator>& __lhs, 597 const set<_Key, _Compare, _Allocator>& __rhs) 598 { return !(__lhs == __rhs); } 599 600 template<typename _Key, typename _Compare, typename _Allocator> 601 inline bool 602 operator<=(const set<_Key, _Compare, _Allocator>& __lhs, 603 const set<_Key, _Compare, _Allocator>& __rhs) 604 { return !(__rhs < __lhs); } 605 606 template<typename _Key, typename _Compare, typename _Allocator> 607 inline bool 608 operator>=(const set<_Key, _Compare, _Allocator>& __lhs, 609 const set<_Key, _Compare, _Allocator>& __rhs) 610 { return !(__lhs < __rhs); } 611 612 template<typename _Key, typename _Compare, typename _Allocator> 613 inline bool 614 operator>(const set<_Key, _Compare, _Allocator>& __lhs, 615 const set<_Key, _Compare, _Allocator>& __rhs) 616 { return __rhs < __lhs; } 617 618 template<typename _Key, typename _Compare, typename _Allocator> 619 void 620 swap(set<_Key, _Compare, _Allocator>& __x, 621 set<_Key, _Compare, _Allocator>& __y) 622 _GLIBCXX_NOEXCEPT_IF(noexcept(__x.swap(__y))) 623 { return __x.swap(__y); } 624 625} // namespace __profile 626} // namespace std 627 628#endif 629