Subversion Repositories Kolibri OS

Rev

Go to most recent revision | Blame | Last modification | View Log | RSS feed

  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
  658.