contrib/gcc-4.7/libstdc++-v3/include/profile/list

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