libstdc++-v3/include/profile/list

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