Subversion Repositories Kolibri OS

Rev

Blame | Last modification | View Log | RSS feed

  1. // Profiling list implementation -*- C++ -*-
  2.  
  3. // Copyright (C) 2009-2015 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.   template<typename _List>
  41.     class _List_profile
  42.     {
  43.       _List&
  44.       _M_conjure()
  45.       { return *static_cast<_List*>(this); }
  46.  
  47.     public:
  48.       __gnu_profile::__list2slist_info* _M_list2slist_info;
  49.       __gnu_profile::__list2vector_info* _M_list2vector_info;
  50.  
  51.       _List_profile() _GLIBCXX_NOEXCEPT
  52.       { _M_profile_construct(); }
  53.  
  54.       void
  55.       _M_profile_construct() _GLIBCXX_NOEXCEPT
  56.       {
  57.         _M_list2slist_info = __profcxx_list2slist_construct();
  58.         _M_list2vector_info = __profcxx_list2vector_construct();
  59.       }
  60.  
  61.       void
  62.       _M_profile_destruct() _GLIBCXX_NOEXCEPT
  63.       {
  64.         __profcxx_list2vector_destruct(_M_list2vector_info);
  65.         _M_list2vector_info = 0;
  66.         __profcxx_list2slist_destruct(_M_list2slist_info);
  67.         _M_list2slist_info = 0;
  68.       }
  69.  
  70.       void
  71.       _M_swap(_List_profile& __other)
  72.       {
  73.         std::swap(_M_list2slist_info, __other._M_list2slist_info);
  74.         std::swap(_M_list2vector_info, __other._M_list2vector_info);
  75.       }
  76.  
  77. #if __cplusplus >= 201103L
  78.       _List_profile(const _List_profile&) noexcept
  79.       : _List_profile() { }
  80.       _List_profile(_List_profile&& __other) noexcept
  81.       : _List_profile()
  82.       { _M_swap(__other); }
  83.  
  84.       _List_profile&
  85.       operator=(const _List_profile&) noexcept
  86.       {
  87.         _M_profile_destruct();
  88.         _M_profile_construct();
  89.       }
  90.  
  91.       _List_profile&
  92.       operator=(_List_profile&& __other) noexcept
  93.       {
  94.         _M_swap(__other);
  95.         __other._M_profile_destruct();
  96.         __other._M_profile_construct();
  97.       }
  98. #endif
  99.  
  100.       ~_List_profile()
  101.       { _M_profile_destruct(); }
  102.     };
  103.  
  104.   /** @brief List wrapper with performance instrumentation.  */
  105.   template<typename _Tp, typename _Allocator = std::allocator<_Tp> >
  106.     class list
  107.     : public _GLIBCXX_STD_C::list<_Tp, _Allocator>,
  108.       public _List_profile<list<_Tp, _Allocator> >
  109.     {
  110.       typedef _GLIBCXX_STD_C::list<_Tp, _Allocator>     _Base;
  111.  
  112.     public:
  113.       typedef typename _Base::reference                 reference;
  114.       typedef typename _Base::const_reference           const_reference;
  115.  
  116.       typedef __iterator_tracker<typename _Base::iterator, list>
  117.                                                         iterator;
  118.       typedef __iterator_tracker<typename _Base::const_iterator, list>
  119.                                                         const_iterator;
  120.  
  121.       typedef typename _Base::size_type                 size_type;
  122.       typedef typename _Base::difference_type           difference_type;
  123.  
  124.       typedef _Tp                                       value_type;
  125.       typedef _Allocator                                allocator_type;
  126.       typedef typename _Base::pointer                   pointer;
  127.       typedef typename _Base::const_pointer             const_pointer;
  128.       typedef std::reverse_iterator<iterator>           reverse_iterator;
  129.       typedef std::reverse_iterator<const_iterator>     const_reverse_iterator;
  130.  
  131.       // 23.2.2.1 construct/copy/destroy:
  132.  
  133. #if __cplusplus < 201103L
  134.       list() { }
  135.       list(const list& __x)
  136.       : _Base(__x) { }
  137.  
  138.       ~list() { }
  139. #else
  140.       list() = default;
  141.       list(const list&) = default;
  142.       list(list&&) = default;
  143.       ~list() = default;
  144.  
  145.       list(initializer_list<value_type> __l,
  146.            const allocator_type& __a = allocator_type())
  147.       : _Base(__l, __a) { }
  148. #endif
  149.  
  150.       explicit
  151.       list(const _Allocator& __a) _GLIBCXX_NOEXCEPT
  152.       : _Base(__a) { }
  153.  
  154. #if __cplusplus >= 201103L
  155.       explicit
  156.       list(size_type __n)
  157.       : _Base(__n) { }
  158.  
  159.       list(size_type __n, const _Tp& __value,
  160.            const _Allocator& __a = _Allocator())
  161.       : _Base(__n, __value, __a) { }
  162. #else
  163.       explicit
  164.       list(size_type __n, const _Tp& __value = _Tp(),
  165.            const _Allocator& __a = _Allocator())
  166.       : _Base(__n, __value, __a) { }
  167. #endif
  168.  
  169. #if __cplusplus >= 201103L
  170.       template<typename _InputIterator,
  171.                typename = std::_RequireInputIter<_InputIterator>>
  172. #else
  173.       template<class _InputIterator>
  174. #endif
  175.       list(_InputIterator __first, _InputIterator __last,
  176.            const _Allocator& __a = _Allocator())
  177.       : _Base(__first, __last, __a) { }
  178.  
  179.       list(const _Base& __x)
  180.       : _Base(__x) { }
  181.  
  182. #if __cplusplus < 201103L
  183.       list&
  184.       operator=(const list& __x)
  185.       {
  186.         this->_M_profile_destruct();
  187.         _M_base() = __x;
  188.         this->_M_profile_construct();
  189.         return *this;
  190.       }
  191. #else
  192.       list&
  193.       operator=(const list&) = default;
  194.  
  195.       list&
  196.       operator=(list&&) = default;
  197.  
  198.       list&
  199.       operator=(initializer_list<value_type> __l)
  200.       {
  201.         this->_M_profile_destruct();
  202.         _M_base() = __l;
  203.         this->_M_profile_construct();
  204.         return *this;
  205.       }
  206. #endif
  207.  
  208.       // iterators:
  209.       iterator
  210.       begin() _GLIBCXX_NOEXCEPT
  211.       { return iterator(_Base::begin(), this); }
  212.  
  213.       const_iterator
  214.       begin() const _GLIBCXX_NOEXCEPT
  215.       { return const_iterator(_Base::begin(), this); }
  216.  
  217.       iterator
  218.       end() _GLIBCXX_NOEXCEPT
  219.       {
  220.         __profcxx_list2slist_rewind(this->_M_list2slist_info);
  221.         return iterator(_Base::end(), this);
  222.       }
  223.  
  224.       const_iterator
  225.       end() const _GLIBCXX_NOEXCEPT
  226.       {
  227.         __profcxx_list2slist_rewind(this->_M_list2slist_info);
  228.         return const_iterator(_Base::end(), this);
  229.       }
  230.  
  231.       reverse_iterator
  232.       rbegin() _GLIBCXX_NOEXCEPT
  233.       {
  234.         __profcxx_list2slist_rewind(this->_M_list2slist_info);
  235.         return reverse_iterator(end());
  236.       }
  237.  
  238.       const_reverse_iterator
  239.       rbegin() const _GLIBCXX_NOEXCEPT
  240.       {
  241.         __profcxx_list2slist_rewind(this->_M_list2slist_info);
  242.         return const_reverse_iterator(end());
  243.       }
  244.  
  245.       reverse_iterator
  246.       rend() _GLIBCXX_NOEXCEPT
  247.       { return reverse_iterator(begin()); }
  248.  
  249.       const_reverse_iterator
  250.       rend() const _GLIBCXX_NOEXCEPT
  251.       { return const_reverse_iterator(begin()); }
  252.  
  253. #if __cplusplus >= 201103L
  254.       const_iterator
  255.       cbegin() const noexcept
  256.       { return const_iterator(_Base::cbegin(), this); }
  257.  
  258.       const_iterator
  259.       cend() const noexcept
  260.       { return const_iterator(_Base::cend(), this); }
  261.  
  262.       const_reverse_iterator
  263.       crbegin() const noexcept
  264.       { return const_reverse_iterator(end()); }
  265.  
  266.       const_reverse_iterator
  267.       crend() const noexcept
  268.       { return const_reverse_iterator(begin()); }
  269. #endif
  270.  
  271.       // 23.2.2.2 capacity:
  272.       reference
  273.       back() _GLIBCXX_NOEXCEPT
  274.       {
  275.         __profcxx_list2slist_rewind(this->_M_list2slist_info);
  276.         return _Base::back();
  277.       }
  278.  
  279.       const_reference
  280.       back() const _GLIBCXX_NOEXCEPT
  281.       {
  282.         __profcxx_list2slist_rewind(this->_M_list2slist_info);
  283.         return _Base::back();
  284.       }
  285.  
  286.       // 23.2.2.3 modifiers:
  287.       void
  288.       push_front(const value_type& __x)
  289.       {
  290.         __profcxx_list2vector_invalid_operator(this->_M_list2vector_info);
  291.         __profcxx_list2slist_operation(this->_M_list2slist_info);
  292.         _Base::push_front(__x);
  293.       }
  294.  
  295.       void
  296.       pop_front() _GLIBCXX_NOEXCEPT
  297.       {
  298.         __profcxx_list2slist_operation(this->_M_list2slist_info);
  299.         _Base::pop_front();
  300.       }
  301.  
  302.       void
  303.       pop_back() _GLIBCXX_NOEXCEPT
  304.       {
  305.         _Base::pop_back();
  306.         __profcxx_list2slist_rewind(this->_M_list2slist_info);
  307.       }
  308.  
  309. #if __cplusplus >= 201103L
  310.       template<typename... _Args>
  311.         iterator
  312.         emplace(const_iterator __position, _Args&&... __args)
  313.         {
  314.           return iterator(_Base::emplace(__position.base(),
  315.                                          std::forward<_Args>(__args)...),
  316.                           this);
  317.         }
  318. #endif
  319.  
  320.       iterator
  321. #if __cplusplus >= 201103L
  322.       insert(const_iterator __pos, const _Tp& __x)
  323. #else
  324.       insert(iterator __pos, const _Tp& __x)
  325. #endif
  326.       {
  327.         _M_profile_insert(__pos, this->size());
  328.         return iterator(_Base::insert(__pos.base(), __x), this);
  329.       }
  330.  
  331. #if __cplusplus >= 201103L
  332.       iterator
  333.       insert(const_iterator __pos, _Tp&& __x)
  334.       {
  335.         _M_profile_insert(__pos, this->size());
  336.         return iterator(_Base::emplace(__pos.base(), std::move(__x)),
  337.                         this);
  338.       }
  339.  
  340.       iterator
  341.       insert(const_iterator __pos, initializer_list<value_type> __l)
  342.       {
  343.         _M_profile_insert(__pos, this->size());
  344.         return iterator(_Base::insert(__pos.base(), __l), this);
  345.       }
  346. #endif
  347.  
  348. #if __cplusplus >= 201103L
  349.       iterator
  350.       insert(const_iterator __pos, size_type __n, const _Tp& __x)
  351.       {
  352.         _M_profile_insert(__pos, this->size());
  353.         return iterator(_Base::insert(__pos.base(), __n, __x), this);
  354.       }
  355. #else
  356.       void
  357.       insert(iterator __pos, size_type __n, const _Tp& __x)
  358.       {
  359.         _M_profile_insert(__pos, this->size());
  360.         _Base::insert(__pos.base(), __n, __x);
  361.       }
  362. #endif
  363.  
  364. #if __cplusplus >= 201103L
  365.       template<typename _InputIterator,
  366.                typename = std::_RequireInputIter<_InputIterator>>
  367.         iterator
  368.         insert(const_iterator __pos, _InputIterator __first,
  369.                _InputIterator __last)
  370.         {
  371.           _M_profile_insert(__pos, this->size());
  372.           return iterator(_Base::insert(__pos.base(), __first, __last),
  373.                           this);
  374.         }
  375. #else
  376.       template<class _InputIterator>
  377.         void
  378.         insert(iterator __pos, _InputIterator __first,
  379.                _InputIterator __last)
  380.         {
  381.           _M_profile_insert(__pos, this->size());
  382.           _Base::insert(__pos.base(), __first, __last);
  383.         }
  384. #endif
  385.  
  386.       iterator
  387. #if __cplusplus >= 201103L
  388.       erase(const_iterator __pos) noexcept
  389. #else
  390.       erase(iterator __pos)
  391. #endif
  392.       { return iterator(_Base::erase(__pos.base()), this); }
  393.  
  394.       iterator
  395. #if __cplusplus >= 201103L
  396.       erase(const_iterator __pos, const_iterator __last) noexcept
  397. #else
  398.       erase(iterator __pos, iterator __last)
  399. #endif
  400.       {
  401.         // _GLIBCXX_RESOLVE_LIB_DEFECTS
  402.         // 151. can't currently clear() empty container
  403.         return iterator(_Base::erase(__pos.base(), __last.base()), this);
  404.       }
  405.  
  406.       void
  407.       swap(list& __x)
  408. #if __cplusplus >= 201103L
  409.         noexcept( noexcept(declval<_Base>().swap(__x)) )
  410. #endif
  411.       {
  412.         _Base::swap(__x);
  413.         this->_M_swap(__x);
  414.       }
  415.  
  416.       void
  417.       clear() _GLIBCXX_NOEXCEPT
  418.       {
  419.         this->_M_profile_destruct();
  420.         _Base::clear();
  421.         this->_M_profile_construct();
  422.       }
  423.  
  424.       // 23.2.2.4 list operations:
  425.       void
  426. #if __cplusplus >= 201103L
  427.       splice(const_iterator __pos, list&& __x) noexcept
  428. #else
  429.       splice(iterator __pos, list& __x)
  430. #endif
  431.       { this->splice(__pos, _GLIBCXX_MOVE(__x), __x.begin(), __x.end()); }
  432.  
  433. #if __cplusplus >= 201103L
  434.       void
  435.       splice(const_iterator __pos, list& __x) noexcept
  436.       { this->splice(__pos, std::move(__x)); }
  437.  
  438.       void
  439.       splice(const_iterator __pos, list& __x, const_iterator __i)
  440.       { this->splice(__pos, std::move(__x), __i); }
  441. #endif
  442.  
  443.       void
  444. #if __cplusplus >= 201103L
  445.       splice(const_iterator __pos, list&& __x, const_iterator __i) noexcept
  446. #else
  447.       splice(iterator __pos, list& __x, iterator __i)
  448. #endif
  449.       {
  450.         // We used to perform the splice_alloc check:  not anymore, redundant
  451.         // after implementing the relevant bits of N1599.
  452.  
  453.         // _GLIBCXX_RESOLVE_LIB_DEFECTS
  454.         _Base::splice(__pos.base(), _GLIBCXX_MOVE(__x._M_base()),
  455.                       __i.base());
  456.       }
  457.  
  458.       void
  459. #if __cplusplus >= 201103L
  460.       splice(const_iterator __pos, list&& __x, const_iterator __first,
  461.              const_iterator __last) noexcept
  462. #else
  463.       splice(iterator __pos, list& __x, iterator __first,
  464.              iterator __last)
  465. #endif
  466.       {
  467.         _Base::splice(__pos.base(), _GLIBCXX_MOVE(__x._M_base()),
  468.                       __first.base(), __last.base());
  469.       }
  470.  
  471. #if __cplusplus >= 201103L
  472.       void
  473.       splice(const_iterator __pos, list& __x,
  474.              const_iterator __first, const_iterator __last) noexcept
  475.       { this->splice(__pos, std::move(__x), __first, __last); }
  476. #endif
  477.  
  478.       void
  479.       remove(const _Tp& __value)
  480.       {
  481.         for (iterator __x = begin(); __x != end(); )
  482.           {
  483.             if (*__x == __value)
  484.               __x = erase(__x);
  485.             else
  486.               ++__x;
  487.           }
  488.       }
  489.  
  490.       template<class _Predicate>
  491.         void
  492.         remove_if(_Predicate __pred)
  493.         {
  494.           for (iterator __x = begin(); __x != end(); )
  495.             {
  496.               __profcxx_list2slist_operation(this->_M_list2slist_info);
  497.               if (__pred(*__x))
  498.                 __x = erase(__x);
  499.               else
  500.                 ++__x;
  501.             }
  502.         }
  503.  
  504.       void
  505.       unique()
  506.       {
  507.         iterator __first = begin();
  508.         iterator __last = end();
  509.         if (__first == __last)
  510.           return;
  511.         iterator __next = __first;
  512.         while (++__next != __last)
  513.           {
  514.             __profcxx_list2slist_operation(this->_M_list2slist_info);
  515.             if (*__first == *__next)
  516.               erase(__next);
  517.             else
  518.               __first = __next;
  519.             __next = __first;
  520.           }
  521.       }
  522.  
  523.       template<class _BinaryPredicate>
  524.         void
  525.         unique(_BinaryPredicate __binary_pred)
  526.         {
  527.           iterator __first = begin();
  528.           iterator __last = end();
  529.           if (__first == __last)
  530.             return;
  531.           iterator __next = __first;
  532.           while (++__next != __last)
  533.             {
  534.               __profcxx_list2slist_operation(this->_M_list2slist_info);
  535.               if (__binary_pred(*__first, *__next))
  536.                 erase(__next);
  537.               else
  538.                 __first = __next;
  539.               __next = __first;
  540.             }
  541.         }
  542.  
  543.       void
  544. #if __cplusplus >= 201103L
  545.       merge(list&& __x)
  546. #else
  547.       merge(list& __x)
  548. #endif
  549.       { _Base::merge(_GLIBCXX_MOVE(__x._M_base())); }
  550.  
  551. #if __cplusplus >= 201103L
  552.       void
  553.       merge(list& __x)
  554.       { this->merge(std::move(__x)); }
  555. #endif
  556.  
  557.       template<class _Compare>
  558.         void
  559. #if __cplusplus >= 201103L
  560.         merge(list&& __x, _Compare __comp)
  561. #else
  562.         merge(list& __x, _Compare __comp)
  563. #endif
  564.         { _Base::merge(_GLIBCXX_MOVE(__x._M_base()), __comp); }
  565.  
  566. #if __cplusplus >= 201103L
  567.       template<typename _Compare>
  568.         void
  569.         merge(list& __x, _Compare __comp)
  570.         { this->merge(std::move(__x), __comp); }
  571. #endif
  572.  
  573.       _Base&
  574.       _M_base() _GLIBCXX_NOEXCEPT       { return *this; }
  575.  
  576.       const _Base&
  577.       _M_base() const _GLIBCXX_NOEXCEPT { return *this; }
  578.  
  579.       void _M_profile_iterate(int __rewind = 0) const
  580.       {
  581.         __profcxx_list2slist_operation(this->_M_list2slist_info);
  582.         __profcxx_list2vector_iterate(this->_M_list2vector_info, __rewind);
  583.         if (__rewind)
  584.           __profcxx_list2slist_rewind(this->_M_list2slist_info);
  585.       }
  586.  
  587.     private:
  588.       size_type
  589.       _M_profile_insert(const_iterator __pos, size_type __size)
  590.       {
  591.         size_type __shift = 0;
  592.         typename _Base::const_iterator __it = __pos.base();
  593.         for (; __it != _Base::end(); ++__it)
  594.           __shift++;
  595.         __profcxx_list2slist_rewind(this->_M_list2slist_info);
  596.         __profcxx_list2slist_operation(this->_M_list2slist_info);
  597.         __profcxx_list2vector_insert(this->_M_list2vector_info, __shift, __size);
  598.       }
  599.     };
  600.  
  601.   template<typename _Tp, typename _Alloc>
  602.     inline bool
  603.     operator==(const list<_Tp, _Alloc>& __lhs,
  604.                const list<_Tp, _Alloc>& __rhs)
  605.     { return __lhs._M_base() == __rhs._M_base(); }
  606.  
  607.   template<typename _Tp, typename _Alloc>
  608.     inline bool
  609.     operator!=(const list<_Tp, _Alloc>& __lhs,
  610.                const list<_Tp, _Alloc>& __rhs)
  611.     { return __lhs._M_base() != __rhs._M_base(); }
  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 void
  639.     swap(list<_Tp, _Alloc>& __lhs, list<_Tp, _Alloc>& __rhs)
  640.     { __lhs.swap(__rhs); }
  641.  
  642. } // namespace __profile
  643. } // namespace std
  644.  
  645. #endif
  646.