l4/pkg/libstdc++-v3/contrib/libstdc++-v3-4.9/include/profile/list

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