libstdc++-v3/include/profile/list

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