libstdc++-v3/include/profile/list

   1 // Profiling list 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 and
  21 // a copy of the GCC Runtime Library Exception along with this program;
  22 // see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
  23 // <http://www.gnu.org/licenses/>.
  24
  25 /** @file profile/list
  26  *  This file is a GNU profile extension to the Standard C++ Library.
  27  */
  28
  29 #ifndef _GLIBCXX_PROFILE_LIST
  30 #define _GLIBCXX_PROFILE_LIST 1
  31
  32 #include <list>
  33 #include <profile/base.h>
  34 #include <profile/iterator_tracker.h>
  35
  36 namespace std _GLIBCXX_VISIBILITY(default)
  37 {
  38 namespace __profile
  39 {
  40   /** @brief List wrapper with performance instrumentation.  */
  41 template<typename _Tp, typename _Allocator = std::allocator<_Tp> >
  42     class list
  43     : public _GLIBCXX_STD_C::list<_Tp, _Allocator>
  44     {
  45       typedef _GLIBCXX_STD_C::list<_Tp, _Allocator> _Base;
  46
  47     public:
  48       typedef typename _Base::reference             reference;
  49       typedef typename _Base::const_reference       const_reference;
  50
  51       typedef __iterator_tracker<typename _Base::iterator, list>
  52                                                     iterator;
  53       typedef __iterator_tracker<typename _Base::const_iterator, list>
  54                                                     const_iterator;
  55
  56       typedef typename _Base::size_type             size_type;
  57       typedef typename _Base::difference_type       difference_type;
  58
  59       typedef _Tp                                   value_type;
  60       typedef _Allocator                            allocator_type;
  61       typedef typename _Base::pointer               pointer;
  62       typedef typename _Base::const_pointer         const_pointer;
  63       typedef std::reverse_iterator<iterator>       reverse_iterator;
  64       typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
  65
  66       // 23.2.2.1 construct/copy/destroy:
  67       explicit
  68       list(const _Allocator& __a = _Allocator()) _GLIBCXX_NOEXCEPT
  69       : _Base(__a)
  70       {
  71         __profcxx_list_construct(this);         // list2slist
  72         __profcxx_list_construct2(this);        // list2vector
  73       }
  74
  75 #if __cplusplus >= 201103L
  76       explicit
  77       list(size_type __n)
  78       : _Base(__n)
  79       {
  80         __profcxx_list_construct(this);
  81         __profcxx_list_construct2(this);
  82       }
  83
  84       list(size_type __n, const _Tp& __value,
  85            const _Allocator& __a = _Allocator())
  86       : _Base(__n, __value, __a)
  87       {
  88         __profcxx_list_construct(this);
  89         __profcxx_list_construct2(this);
  90       }
  91 #else
  92       explicit
  93       list(size_type __n, const _Tp& __value = _Tp(),
  94            const _Allocator& __a = _Allocator())
  95       : _Base(__n, __value, __a)
  96       {
  97         __profcxx_list_construct(this);
  98         __profcxx_list_construct2(this);
  99       }
 100 #endif
 101
 102 #if __cplusplus >= 201103L
 103       template<typename _InputIterator,
 104                typename = std::_RequireInputIter<_InputIterator>>
 105 #else
 106       template<class _InputIterator>
 107 #endif
 108       list(_InputIterator __first, _InputIterator __last,
 109            const _Allocator& __a = _Allocator())
 110       : _Base(__first, __last, __a)
 111       {
 112         __profcxx_list_construct(this);
 113         __profcxx_list_construct2(this);
 114       }
 115
 116       list(const list& __x)
 117       : _Base(__x)
 118       {
 119         __profcxx_list_construct(this);
 120         __profcxx_list_construct2(this);
 121       }
 122
 123       list(const _Base& __x)
 124       : _Base(__x)
 125       {
 126         __profcxx_list_construct(this);
 127         __profcxx_list_construct2(this);
 128       }
 129
 130 #if __cplusplus >= 201103L
 131       list(list&& __x) noexcept
 132       : _Base(std::move(__x))
 133       {
 134         __profcxx_list_construct(this);
 135         __profcxx_list_construct2(this);
 136       }
 137
 138       list(initializer_list<value_type> __l,
 139            const allocator_type& __a = allocator_type())
 140         : _Base(__l, __a) { }
 141 #endif
 142
 143       ~list() _GLIBCXX_NOEXCEPT
 144       {
 145         __profcxx_list_destruct(this);
 146         __profcxx_list_destruct2(this);
 147       }
 148
 149       list&
 150       operator=(const list& __x)
 151       {
 152         static_cast<_Base&>(*this) = __x;
 153         return *this;
 154       }
 155
 156 #if __cplusplus >= 201103L
 157       list&
 158       operator=(list&& __x)
 159       {
 160         // NB: DR 1204.
 161         // NB: DR 675.
 162         this->clear();
 163         this->swap(__x);
 164         return *this;
 165       }
 166
 167       list&
 168       operator=(initializer_list<value_type> __l)
 169       {
 170         static_cast<_Base&>(*this) = __l;
 171         return *this;
 172       }
 173
 174       void
 175       assign(initializer_list<value_type> __l)
 176       { _Base::assign(__l); }
 177 #endif
 178
 179 #if __cplusplus >= 201103L
 180       template<typename _InputIterator,
 181                typename = std::_RequireInputIter<_InputIterator>>
 182 #else
 183       template<class _InputIterator>
 184 #endif
 185         void
 186         assign(_InputIterator __first, _InputIterator __last)
 187         { _Base::assign(__first, __last); }
 188
 189       void
 190       assign(size_type __n, const _Tp& __t)
 191       { _Base::assign(__n, __t); }
 192
 193       using _Base::get_allocator;
 194
 195       // iterators:
 196       iterator
 197       begin() _GLIBCXX_NOEXCEPT
 198       { return iterator(_Base::begin(), this); }
 199
 200       const_iterator
 201       begin() const _GLIBCXX_NOEXCEPT
 202       { return const_iterator(_Base::begin(), this); }
 203
 204       iterator
 205       end() _GLIBCXX_NOEXCEPT
 206       {
 207         __profcxx_list_rewind(this);
 208         return iterator(_Base::end(), this);
 209       }
 210
 211       const_iterator
 212       end() const _GLIBCXX_NOEXCEPT
 213       {
 214         __profcxx_list_rewind(this);
 215         return const_iterator(_Base::end(), this);
 216       }
 217
 218       reverse_iterator
 219       rbegin() _GLIBCXX_NOEXCEPT
 220       {
 221         __profcxx_list_rewind(this);
 222         return reverse_iterator(end());
 223       }
 224
 225       const_reverse_iterator
 226       rbegin() const _GLIBCXX_NOEXCEPT
 227       {
 228         __profcxx_list_rewind(this);
 229         return const_reverse_iterator(end());
 230       }
 231
 232       reverse_iterator
 233       rend() _GLIBCXX_NOEXCEPT
 234       { return reverse_iterator(begin()); }
 235
 236       const_reverse_iterator
 237       rend() const _GLIBCXX_NOEXCEPT
 238       { return const_reverse_iterator(begin()); }
 239
 240 #if __cplusplus >= 201103L
 241       const_iterator
 242       cbegin() const noexcept
 243       { return const_iterator(_Base::begin(), this); }
 244
 245       const_iterator
 246       cend() const noexcept
 247       { return const_iterator(_Base::end(), this); }
 248
 249       const_reverse_iterator
 250       crbegin() const noexcept
 251       { return const_reverse_iterator(end()); }
 252
 253       const_reverse_iterator
 254       crend() const noexcept
 255       { return const_reverse_iterator(begin()); }
 256 #endif
 257
 258       // 23.2.2.2 capacity:
 259       using _Base::empty;
 260       using _Base::size;
 261       using _Base::max_size;
 262
 263 #if __cplusplus >= 201103L
 264       void
 265       resize(size_type __sz)
 266       { _Base::resize(__sz); }
 267
 268       void
 269       resize(size_type __sz, const _Tp& __c)
 270       { _Base::resize(__sz, __c); }
 271 #else
 272       void
 273       resize(size_type __sz, _Tp __c = _Tp())
 274       { _Base::resize(__sz, __c); }
 275 #endif
 276
 277       // element access:
 278       reference
 279       front() _GLIBCXX_NOEXCEPT
 280       { return _Base::front(); }
 281
 282       const_reference
 283       front() const _GLIBCXX_NOEXCEPT
 284       { return _Base::front(); }
 285
 286       reference
 287       back() _GLIBCXX_NOEXCEPT
 288       {
 289         __profcxx_list_rewind(this);
 290         return _Base::back();
 291       }
 292
 293       const_reference
 294       back() const _GLIBCXX_NOEXCEPT
 295       {
 296         __profcxx_list_rewind(this);
 297         return _Base::back();
 298       }
 299
 300       // 23.2.2.3 modifiers:
 301       void
 302       push_front(const value_type& __x)
 303       {
 304         __profcxx_list_invalid_operator(this);
 305         __profcxx_list_operation(this);
 306         _Base::push_front(__x);
 307       }
 308
 309 #if __cplusplus >= 201103L
 310       using _Base::emplace_front;
 311 #endif
 312
 313       void
 314       pop_front() _GLIBCXX_NOEXCEPT
 315       {
 316         __profcxx_list_operation(this);
 317         _Base::pop_front();
 318       }
 319
 320       using _Base::push_back;
 321
 322 #if __cplusplus >= 201103L
 323       using _Base::emplace_back;
 324 #endif
 325
 326       void
 327       pop_back() _GLIBCXX_NOEXCEPT
 328       {
 329         iterator __victim = end();
 330         --__victim;
 331         _Base::pop_back();
 332         __profcxx_list_rewind(this);
 333       }
 334
 335 #if __cplusplus >= 201103L
 336       template<typename... _Args>
 337         iterator
 338         emplace(const_iterator __position, _Args&&... __args)
 339         {
 340           return iterator(_Base::emplace(__position.base(),
 341                                          std::forward<_Args>(__args)...),
 342                           this);
 343         }
 344 #endif
 345
 346       iterator
 347 #if __cplusplus >= 201103L
 348       insert(const_iterator __position, const _Tp& __x)
 349 #else
 350       insert(iterator __position, const _Tp& __x)
 351 #endif
 352       {
 353         _M_profile_insert(this, __position, size());
 354         return iterator(_Base::insert(__position.base(), __x), this);
 355       }
 356
 357 #if __cplusplus >= 201103L
 358       iterator
 359       insert(const_iterator __position, _Tp&& __x)
 360       {
 361         _M_profile_insert(this, __position, size());
 362         return iterator(_Base::emplace(__position.base(), std::move(__x)),
 363                         this);
 364       }
 365
 366       iterator
 367       insert(const_iterator __position, initializer_list<value_type> __l)
 368       {
 369         _M_profile_insert(this, __position, size());
 370         return iterator(_Base::insert(__position.base(), __l), this);
 371       }
 372 #endif
 373
 374 #if __cplusplus >= 201103L
 375       iterator
 376       insert(const_iterator __position, size_type __n, const _Tp& __x)
 377       {
 378         _M_profile_insert(this, __position, size());
 379         return iterator(_Base::insert(__position.base(), __n, __x), this);
 380       }
 381 #else
 382       void
 383       insert(iterator __position, size_type __n, const _Tp& __x)
 384       {
 385         _M_profile_insert(this, __position, size());
 386         _Base::insert(__position.base(), __n, __x);
 387       }
 388 #endif
 389
 390 #if __cplusplus >= 201103L
 391       template<typename _InputIterator,
 392                typename = std::_RequireInputIter<_InputIterator>>
 393         iterator
 394         insert(const_iterator __position, _InputIterator __first,
 395                _InputIterator __last)
 396         {
 397           _M_profile_insert(this, __position, size());
 398           return iterator(_Base::insert(__position.base(), __first, __last),
 399                           this);
 400         }
 401 #else
 402       template<class _InputIterator>
 403         void
 404         insert(iterator __position, _InputIterator __first,
 405                _InputIterator __last)
 406         {
 407           _M_profile_insert(this, __position, size());
 408           _Base::insert(__position.base(), __first, __last);
 409         }
 410 #endif
 411
 412       iterator
 413 #if __cplusplus >= 201103L
 414       erase(const_iterator __position) noexcept
 415 #else
 416       erase(iterator __position)
 417 #endif
 418       { return iterator(_Base::erase(__position.base()), this); }
 419
 420       iterator
 421 #if __cplusplus >= 201103L
 422       erase(const_iterator __position, const_iterator __last) noexcept
 423 #else
 424       erase(iterator __position, iterator __last)
 425 #endif
 426       {
 427         // _GLIBCXX_RESOLVE_LIB_DEFECTS
 428         // 151. can't currently clear() empty container
 429         return iterator(_Base::erase(__position.base(), __last.base()), this);
 430       }
 431
 432       void
 433       swap(list& __x)
 434       { _Base::swap(__x); }
 435
 436       void
 437       clear() _GLIBCXX_NOEXCEPT
 438       { _Base::clear(); }
 439
 440       // 23.2.2.4 list operations:
 441       void
 442 #if __cplusplus >= 201103L
 443       splice(const_iterator __position, list&& __x)
 444 #else
 445       splice(iterator __position, list& __x)
 446 #endif
 447       { this->splice(__position, _GLIBCXX_MOVE(__x), __x.begin(), __x.end()); }
 448
 449 #if __cplusplus >= 201103L
 450       void
 451       splice(const_iterator __position, list& __x)
 452       { this->splice(__position, std::move(__x)); }
 453
 454       void
 455       splice(const_iterator __position, list& __x, const_iterator __i)
 456       { this->splice(__position, std::move(__x), __i); }
 457 #endif
 458
 459       void
 460 #if __cplusplus >= 201103L
 461       splice(const_iterator __position, list&& __x, const_iterator __i)
 462 #else
 463       splice(iterator __position, list& __x, iterator __i)
 464 #endif
 465       {
 466         // We used to perform the splice_alloc check:  not anymore, redundant
 467         // after implementing the relevant bits of N1599.
 468
 469         // _GLIBCXX_RESOLVE_LIB_DEFECTS
 470         _Base::splice(__position.base(), _GLIBCXX_MOVE(__x._M_base()),
 471                       __i.base());
 472       }
 473
 474       void
 475 #if __cplusplus >= 201103L
 476       splice(const_iterator __position, list&& __x, const_iterator __first,
 477              const_iterator __last)
 478 #else
 479       splice(iterator __position, list& __x, iterator __first,
 480              iterator __last)
 481 #endif
 482       {
 483         // We used to perform the splice_alloc check:  not anymore, redundant
 484         // after implementing the relevant bits of N1599.
 485
 486         _Base::splice(__position.base(), _GLIBCXX_MOVE(__x._M_base()),
 487                       __first.base(), __last.base());
 488       }
 489
 490 #if __cplusplus >= 201103L
 491       void
 492       splice(const_iterator __position, list& __x,
 493              const_iterator __first, const_iterator __last)
 494       { this->splice(__position, std::move(__x), __first, __last); }
 495 #endif
 496
 497       void
 498       remove(const _Tp& __value)
 499       {
 500         for (iterator __x = begin(); __x != end(); )
 501           {
 502             if (*__x == __value)
 503               __x = erase(__x);
 504             else
 505               ++__x;
 506           }
 507       }
 508
 509       template<class _Predicate>
 510         void
 511         remove_if(_Predicate __pred)
 512         {
 513           for (iterator __x = begin(); __x != end(); )
 514             {
 515               __profcxx_list_operation(this);
 516               if (__pred(*__x))
 517                 __x = erase(__x);
 518               else
 519                 ++__x;
 520             }
 521         }
 522
 523       void
 524       unique()
 525       {
 526         iterator __first = begin();
 527         iterator __last = end();
 528         if (__first == __last)
 529           return;
 530         iterator __next = __first;
 531         while (++__next != __last)
 532           {
 533             __profcxx_list_operation(this);
 534             if (*__first == *__next)
 535               erase(__next);
 536             else
 537               __first = __next;
 538             __next = __first;
 539           }
 540       }
 541
 542       template<class _BinaryPredicate>
 543         void
 544         unique(_BinaryPredicate __binary_pred)
 545         {
 546           iterator __first = begin();
 547           iterator __last = end();
 548           if (__first == __last)
 549             return;
 550           iterator __next = __first;
 551           while (++__next != __last)
 552             {
 553               __profcxx_list_operation(this);
 554               if (__binary_pred(*__first, *__next))
 555                 erase(__next);
 556               else
 557                 __first = __next;
 558               __next = __first;
 559             }
 560         }
 561
 562       void
 563 #if __cplusplus >= 201103L
 564       merge(list&& __x)
 565 #else
 566       merge(list& __x)
 567 #endif
 568       {
 569         // _GLIBCXX_RESOLVE_LIB_DEFECTS
 570         // 300. list::merge() specification incomplete
 571         if (this != &__x)
 572           { _Base::merge(_GLIBCXX_MOVE(__x._M_base())); }
 573       }
 574
 575 #if __cplusplus >= 201103L
 576       void
 577       merge(list& __x)
 578       { this->merge(std::move(__x)); }
 579 #endif
 580
 581       template<class _Compare>
 582         void
 583 #if __cplusplus >= 201103L
 584         merge(list&& __x, _Compare __comp)
 585 #else
 586         merge(list& __x, _Compare __comp)
 587 #endif
 588         {
 589           // _GLIBCXX_RESOLVE_LIB_DEFECTS
 590           // 300. list::merge() specification incomplete
 591           if (this != &__x)
 592             { _Base::merge(_GLIBCXX_MOVE(__x._M_base()), __comp); }
 593         }
 594
 595 #if __cplusplus >= 201103L
 596       template<typename _Compare>
 597         void
 598         merge(list& __x, _Compare __comp)
 599         { this->merge(std::move(__x), __comp); }
 600 #endif
 601
 602       void
 603       sort() { _Base::sort(); }
 604
 605       template<typename _StrictWeakOrdering>
 606         void
 607         sort(_StrictWeakOrdering __pred) { _Base::sort(__pred); }
 608
 609       using _Base::reverse;
 610
 611       _Base&
 612       _M_base() _GLIBCXX_NOEXCEPT       { return *this; }
 613
 614       const _Base&
 615       _M_base() const _GLIBCXX_NOEXCEPT { return *this; }
 616
 617       void _M_profile_find() const
 618       { }
 619
 620       void _M_profile_iterate(int __rewind = 0) const
 621       {
 622         __profcxx_list_operation(this);
 623         __profcxx_list_iterate(this);
 624         if (__rewind)
 625           __profcxx_list_rewind(this);
 626       }
 627
 628     private:
 629       size_type
 630       _M_profile_insert(void* obj, const_iterator __pos, size_type __size)
 631       {
 632         size_type __shift = 0;
 633         typename _Base::const_iterator __it = __pos.base();
 634         for (; __it != _Base::end(); ++__it)
 635           __shift++;
 636         __profcxx_list_rewind(this);
 637         __profcxx_list_operation(this);
 638         __profcxx_list_insert(this, __shift, __size);
 639       }
 640     };
 641
 642   template<typename _Tp, typename _Alloc>
 643     inline bool
 644     operator==(const list<_Tp, _Alloc>& __lhs,
 645                const list<_Tp, _Alloc>& __rhs)
 646     { return __lhs._M_base() == __rhs._M_base(); }
 647
 648   template<typename _Tp, typename _Alloc>
 649     inline bool
 650     operator!=(const list<_Tp, _Alloc>& __lhs,
 651                const list<_Tp, _Alloc>& __rhs)
 652     { return __lhs._M_base() != __rhs._M_base(); }
 653
 654   template<typename _Tp, typename _Alloc>
 655     inline bool
 656     operator<(const list<_Tp, _Alloc>& __lhs,
 657               const list<_Tp, _Alloc>& __rhs)
 658     { return __lhs._M_base() < __rhs._M_base(); }
 659
 660   template<typename _Tp, typename _Alloc>
 661     inline bool
 662     operator<=(const list<_Tp, _Alloc>& __lhs,
 663                const list<_Tp, _Alloc>& __rhs)
 664     { return __lhs._M_base() <= __rhs._M_base(); }
 665
 666   template<typename _Tp, typename _Alloc>
 667     inline bool
 668     operator>=(const list<_Tp, _Alloc>& __lhs,
 669                const list<_Tp, _Alloc>& __rhs)
 670     { return __lhs._M_base() >= __rhs._M_base(); }
 671
 672   template<typename _Tp, typename _Alloc>
 673     inline bool
 674     operator>(const list<_Tp, _Alloc>& __lhs,
 675               const list<_Tp, _Alloc>& __rhs)
 676     { return __lhs._M_base() > __rhs._M_base(); }
 677
 678   template<typename _Tp, typename _Alloc>
 679     inline void
 680     swap(list<_Tp, _Alloc>& __lhs, list<_Tp, _Alloc>& __rhs)
 681     { __lhs.swap(__rhs); }
 682
 683 } // namespace __profile
 684 } // namespace std
 685
 686 #endif