libstdc++-v3/include/profile/list

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