l4/pkg/l4re-core/libstdc++-v3/contrib/libstdc++-v3-4.8/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())
  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()
 280       { return _Base::front(); }
 281
 282       const_reference
 283       front() const
 284       { return _Base::front(); }
 285
 286       reference
 287       back()
 288       {
 289         __profcxx_list_rewind(this);
 290         return _Base::back();
 291       }
 292
 293       const_reference
 294       back() const
 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()
 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()
 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(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       insert(iterator __position, const _Tp& __x)
 348       {
 349         _M_profile_insert(this, __position, size());
 350         return iterator(_Base::insert(__position.base(), __x), this);
 351       }
 352
 353 #if __cplusplus >= 201103L
 354       iterator
 355       insert(iterator __position, _Tp&& __x)
 356       {
 357         _M_profile_insert(this, __position, size());
 358         return iterator(_Base::emplace(__position.base(), std::move(__x)),
 359                         this);
 360       }
 361
 362       void
 363       insert(iterator __position, initializer_list<value_type> __l)
 364       {
 365         _M_profile_insert(this, __position, size());
 366         _Base::insert(__position.base(), __l);
 367       }
 368 #endif
 369
 370       void
 371       insert(iterator __position, size_type __n, const _Tp& __x)
 372       {
 373         _M_profile_insert(this, __position, size());
 374         _Base::insert(__position.base(), __n, __x);
 375       }
 376
 377 #if __cplusplus >= 201103L
 378       template<typename _InputIterator,
 379                typename = std::_RequireInputIter<_InputIterator>>
 380 #else
 381       template<class _InputIterator>
 382 #endif
 383         void
 384         insert(iterator __position, _InputIterator __first,
 385                _InputIterator __last)
 386         {
 387           _M_profile_insert(this, __position, size());
 388           _Base::insert(__position.base(), __first, __last);
 389         }
 390
 391       iterator
 392       erase(iterator __position)
 393       { return iterator(_Base::erase(__position.base()), this); }
 394
 395       iterator
 396       erase(iterator __position, iterator __last)
 397       {
 398         // _GLIBCXX_RESOLVE_LIB_DEFECTS
 399         // 151. can't currently clear() empty container
 400         return iterator(_Base::erase(__position.base(), __last.base()), this);
 401       }
 402
 403       void
 404       swap(list& __x)
 405       { _Base::swap(__x); }
 406
 407       void
 408       clear() _GLIBCXX_NOEXCEPT
 409       { _Base::clear(); }
 410
 411       // 23.2.2.4 list operations:
 412       void
 413 #if __cplusplus >= 201103L
 414       splice(iterator __position, list&& __x)
 415 #else
 416       splice(iterator __position, list& __x)
 417 #endif
 418       { this->splice(__position, _GLIBCXX_MOVE(__x), __x.begin(), __x.end()); }
 419
 420 #if __cplusplus >= 201103L
 421       void
 422       splice(iterator __position, list& __x)
 423       { this->splice(__position, std::move(__x)); }
 424 #endif
 425
 426 #if __cplusplus >= 201103L
 427       void
 428       splice(iterator __position, list& __x, iterator __i)
 429       { this->splice(__position, std::move(__x), __i); }
 430 #endif
 431
 432       void
 433 #if __cplusplus >= 201103L
 434       splice(iterator __position, list&& __x, iterator __i)
 435 #else
 436       splice(iterator __position, list& __x, iterator __i)
 437 #endif
 438       {
 439         // We used to perform the splice_alloc check:  not anymore, redundant
 440         // after implementing the relevant bits of N1599.
 441
 442         // _GLIBCXX_RESOLVE_LIB_DEFECTS
 443         _Base::splice(__position.base(), _GLIBCXX_MOVE(__x._M_base()),
 444                       __i.base());
 445       }
 446
 447       void
 448 #if __cplusplus >= 201103L
 449       splice(iterator __position, list&& __x, iterator __first,
 450              iterator __last)
 451 #else
 452       splice(iterator __position, list& __x, iterator __first,
 453              iterator __last)
 454 #endif
 455       {
 456         // We used to perform the splice_alloc check:  not anymore, redundant
 457         // after implementing the relevant bits of N1599.
 458
 459         _Base::splice(__position.base(), _GLIBCXX_MOVE(__x._M_base()),
 460                       __first.base(), __last.base());
 461       }
 462
 463 #if __cplusplus >= 201103L
 464       void
 465       splice(iterator __position, list& __x, iterator __first, iterator __last)
 466       { this->splice(__position, std::move(__x), __first, __last); }
 467 #endif
 468
 469       void
 470       remove(const _Tp& __value)
 471       {
 472         for (iterator __x = begin(); __x != end(); )
 473           {
 474             if (*__x == __value)
 475               __x = erase(__x);
 476             else
 477               ++__x;
 478           }
 479       }
 480
 481       template<class _Predicate>
 482         void
 483         remove_if(_Predicate __pred)
 484         {
 485           for (iterator __x = begin(); __x != end(); )
 486             {
 487               __profcxx_list_operation(this);
 488               if (__pred(*__x))
 489                 __x = erase(__x);
 490               else
 491                 ++__x;
 492             }
 493         }
 494
 495       void
 496       unique()
 497       {
 498         iterator __first = begin();
 499         iterator __last = end();
 500         if (__first == __last)
 501           return;
 502         iterator __next = __first;
 503         while (++__next != __last)
 504           {
 505             __profcxx_list_operation(this);
 506             if (*__first == *__next)
 507               erase(__next);
 508             else
 509               __first = __next;
 510             __next = __first;
 511           }
 512       }
 513
 514       template<class _BinaryPredicate>
 515         void
 516         unique(_BinaryPredicate __binary_pred)
 517         {
 518           iterator __first = begin();
 519           iterator __last = end();
 520           if (__first == __last)
 521             return;
 522           iterator __next = __first;
 523           while (++__next != __last)
 524             {
 525               __profcxx_list_operation(this);
 526               if (__binary_pred(*__first, *__next))
 527                 erase(__next);
 528               else
 529                 __first = __next;
 530               __next = __first;
 531             }
 532         }
 533
 534       void
 535 #if __cplusplus >= 201103L
 536       merge(list&& __x)
 537 #else
 538       merge(list& __x)
 539 #endif
 540       {
 541         // _GLIBCXX_RESOLVE_LIB_DEFECTS
 542         // 300. list::merge() specification incomplete
 543         if (this != &__x)
 544           { _Base::merge(_GLIBCXX_MOVE(__x._M_base())); }
 545       }
 546
 547 #if __cplusplus >= 201103L
 548       void
 549       merge(list& __x)
 550       { this->merge(std::move(__x)); }
 551 #endif
 552
 553       template<class _Compare>
 554         void
 555 #if __cplusplus >= 201103L
 556         merge(list&& __x, _Compare __comp)
 557 #else
 558         merge(list& __x, _Compare __comp)
 559 #endif
 560         {
 561           // _GLIBCXX_RESOLVE_LIB_DEFECTS
 562           // 300. list::merge() specification incomplete
 563           if (this != &__x)
 564             { _Base::merge(_GLIBCXX_MOVE(__x._M_base()), __comp); }
 565         }
 566
 567 #if __cplusplus >= 201103L
 568       template<typename _Compare>
 569         void
 570         merge(list& __x, _Compare __comp)
 571         { this->merge(std::move(__x), __comp); }
 572 #endif
 573
 574       void
 575       sort() { _Base::sort(); }
 576
 577       template<typename _StrictWeakOrdering>
 578         void
 579         sort(_StrictWeakOrdering __pred) { _Base::sort(__pred); }
 580
 581       using _Base::reverse;
 582
 583       _Base&
 584       _M_base() _GLIBCXX_NOEXCEPT       { return *this; }
 585
 586       const _Base&
 587       _M_base() const _GLIBCXX_NOEXCEPT { return *this; }
 588
 589       void _M_profile_find() const
 590       { }
 591
 592       void _M_profile_iterate(int __rewind = 0) const
 593       {
 594         __profcxx_list_operation(this);
 595         __profcxx_list_iterate(this);
 596         if (__rewind)
 597           __profcxx_list_rewind(this);
 598       }
 599
 600     private:
 601       size_type _M_profile_insert(void* obj, iterator __pos, size_type __size)
 602       {
 603         size_type __shift = 0;
 604         typename _Base::iterator __it = __pos.base();
 605         for ( ; __it!=_Base::end(); __it++)
 606           __shift++;
 607         __profcxx_list_rewind(this);
 608         __profcxx_list_operation(this);
 609         __profcxx_list_insert(this, __shift, __size);
 610       }
 611     };
 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 bool
 639     operator>=(const list<_Tp, _Alloc>& __lhs,
 640                const list<_Tp, _Alloc>& __rhs)
 641     { return __lhs._M_base() >= __rhs._M_base(); }
 642
 643   template<typename _Tp, typename _Alloc>
 644     inline bool
 645     operator>(const list<_Tp, _Alloc>& __lhs,
 646               const list<_Tp, _Alloc>& __rhs)
 647     { return __lhs._M_base() > __rhs._M_base(); }
 648
 649   template<typename _Tp, typename _Alloc>
 650     inline void
 651     swap(list<_Tp, _Alloc>& __lhs, list<_Tp, _Alloc>& __rhs)
 652     { __lhs.swap(__rhs); }
 653
 654 } // namespace __profile
 655 } // namespace std
 656
 657 #endif