Subversion Repositories Kolibri OS

Rev

Blame | Last modification | View Log | RSS feed

  1. // Profiling multiset 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/multiset.h
  26.  *  This file is a GNU profile extension to the Standard C++ Library.
  27.  */
  28.  
  29. #ifndef _GLIBCXX_PROFILE_MULTISET_H
  30. #define _GLIBCXX_PROFILE_MULTISET_H 1
  31.  
  32. #include <profile/base.h>
  33. #include <profile/ordered_base.h>
  34.  
  35. namespace std _GLIBCXX_VISIBILITY(default)
  36. {
  37. namespace __profile
  38. {
  39.   /// Class std::multiset wrapper with performance instrumentation.
  40.   template<typename _Key, typename _Compare = std::less<_Key>,
  41.            typename _Allocator = std::allocator<_Key> >
  42.     class multiset
  43.     : public _GLIBCXX_STD_C::multiset<_Key, _Compare, _Allocator>,
  44.       public _Ordered_profile<multiset<_Key, _Compare, _Allocator> >
  45.     {
  46.       typedef _GLIBCXX_STD_C::multiset<_Key, _Compare, _Allocator> _Base;
  47.  
  48.       typedef typename _Base::iterator                  _Base_iterator;
  49.       typedef typename _Base::const_iterator            _Base_const_iterator;
  50.  
  51.     public:
  52.       // types:
  53.       typedef _Key                                      key_type;
  54.       typedef _Key                                      value_type;
  55.       typedef _Compare                                  key_compare;
  56.       typedef _Compare                                  value_compare;
  57.       typedef _Allocator                                allocator_type;
  58.       typedef typename _Base::reference                 reference;
  59.       typedef typename _Base::const_reference           const_reference;
  60.  
  61.       typedef __iterator_tracker<_Base_iterator,
  62.                                  multiset>              iterator;
  63.       typedef __iterator_tracker<_Base_const_iterator,
  64.                                  multiset>              const_iterator;
  65.       typedef std::reverse_iterator<iterator>           reverse_iterator;
  66.       typedef std::reverse_iterator<const_iterator>     const_reverse_iterator;
  67.  
  68.       typedef typename _Base::size_type                 size_type;
  69.       typedef typename _Base::difference_type           difference_type;
  70.  
  71.       // 23.3.3.1 construct/copy/destroy:
  72.  
  73. #if __cplusplus < 201103L
  74.       multiset()
  75.       : _Base() { }
  76.       multiset(const multiset& __x)
  77.       : _Base(__x) { }
  78.       ~multiset() { }
  79. #else
  80.       multiset() = default;
  81.       multiset(const multiset&) = default;
  82.       multiset(multiset&&) = default;
  83.       ~multiset() = default;
  84. #endif
  85.  
  86.       explicit multiset(const _Compare& __comp,
  87.                         const _Allocator& __a = _Allocator())
  88.       : _Base(__comp, __a) { }
  89.  
  90. #if __cplusplus >= 201103L
  91.       template<typename _InputIterator,
  92.                typename = std::_RequireInputIter<_InputIterator>>
  93. #else
  94.       template<typename _InputIterator>
  95. #endif
  96.         multiset(_InputIterator __first, _InputIterator __last,
  97.                  const _Compare& __comp = _Compare(),
  98.                  const _Allocator& __a = _Allocator())
  99.         : _Base(__first, __last, __comp, __a) { }
  100.  
  101. #if __cplusplus >= 201103L
  102.       multiset(initializer_list<value_type> __l,
  103.                const _Compare& __comp = _Compare(),
  104.                const allocator_type& __a = allocator_type())
  105.       : _Base(__l, __comp, __a) { }
  106.  
  107.       explicit
  108.       multiset(const allocator_type& __a)
  109.       : _Base(__a) { }
  110.  
  111.       multiset(const multiset& __x, const allocator_type& __a)
  112.       : _Base(__x, __a) { }
  113.  
  114.       multiset(multiset&& __x, const allocator_type& __a)
  115.       noexcept( noexcept(_Base(std::move(__x), __a)) )
  116.       : _Base(std::move(__x), __a) { }
  117.  
  118.       multiset(initializer_list<value_type> __l, const allocator_type& __a)
  119.       : _Base(__l, __a) { }
  120.  
  121.       template<typename _InputIterator>
  122.         multiset(_InputIterator __first, _InputIterator __last,
  123.                  const allocator_type& __a)
  124.         : _Base(__first, __last, __a) { }
  125. #endif
  126.  
  127.       multiset(const _Base& __x)
  128.       : _Base(__x) { }
  129.  
  130. #if __cplusplus < 201103L
  131.       multiset&
  132.       operator=(const multiset& __x)
  133.       {
  134.         this->_M_profile_destruct();
  135.         _M_base() = __x;
  136.         this->_M_profile_construct();
  137.         return *this;
  138.       }
  139. #else
  140.       multiset&
  141.       operator=(const multiset&) = default;
  142.  
  143.       multiset&
  144.       operator=(multiset&&) = default;
  145.  
  146.       multiset&
  147.       operator=(initializer_list<value_type> __l)
  148.       {
  149.         this->_M_profile_destruct();
  150.         _M_base() = __l;
  151.         this->_M_profile_construct();
  152.         return *this;
  153.       }
  154. #endif
  155.  
  156.       // iterators
  157.       iterator
  158.       begin() _GLIBCXX_NOEXCEPT
  159.       { return iterator(_Base::begin(), this); }
  160.  
  161.       const_iterator
  162.       begin() const _GLIBCXX_NOEXCEPT
  163.       { return const_iterator(_Base::begin(), this); }
  164.  
  165.       iterator
  166.       end() _GLIBCXX_NOEXCEPT
  167.       { return iterator(_Base::end(), this); }
  168.  
  169.       const_iterator
  170.       end() const _GLIBCXX_NOEXCEPT
  171.       { return const_iterator(_Base::end(), this); }
  172.  
  173. #if __cplusplus >= 201103L
  174.       const_iterator
  175.       cbegin() const noexcept
  176.       { return const_iterator(_Base::cbegin(), this); }
  177.  
  178.       const_iterator
  179.       cend() const noexcept
  180.       { return const_iterator(_Base::cend(), this); }
  181. #endif
  182.  
  183.       reverse_iterator
  184.       rbegin() _GLIBCXX_NOEXCEPT
  185.       {
  186.         __profcxx_map2umap_invalidate(this->_M_map2umap_info);
  187.         return reverse_iterator(end());
  188.       }
  189.  
  190.       const_reverse_iterator
  191.       rbegin() const _GLIBCXX_NOEXCEPT
  192.       {
  193.         __profcxx_map2umap_invalidate(this->_M_map2umap_info);
  194.         return const_reverse_iterator(end());
  195.       }
  196.  
  197.       reverse_iterator
  198.       rend() _GLIBCXX_NOEXCEPT
  199.       {
  200.         __profcxx_map2umap_invalidate(this->_M_map2umap_info);
  201.         return reverse_iterator(begin());
  202.       }
  203.  
  204.       const_reverse_iterator
  205.       rend() const _GLIBCXX_NOEXCEPT
  206.       {
  207.         __profcxx_map2umap_invalidate(this->_M_map2umap_info);
  208.         return const_reverse_iterator(begin());
  209.       }
  210.  
  211. #if __cplusplus >= 201103L
  212.       const_reverse_iterator
  213.       crbegin() const noexcept
  214.       {
  215.         __profcxx_map2umap_invalidate(this->_M_map2umap_info);
  216.         return const_reverse_iterator(cend());
  217.       }
  218.  
  219.       const_reverse_iterator
  220.       crend() const noexcept
  221.       {
  222.         __profcxx_map2umap_invalidate(this->_M_map2umap_info);
  223.         return const_reverse_iterator(cbegin());
  224.       }
  225. #endif
  226.  
  227.       void
  228.       swap(multiset& __x)
  229. #if __cplusplus >= 201103L
  230.         noexcept( noexcept(declval<_Base>().swap(__x)) )
  231. #endif
  232.       {
  233.         _Base::swap(__x);
  234.         this->_M_swap(__x);
  235.       }
  236.  
  237.       // modifiers:
  238. #if __cplusplus >= 201103L
  239.       template<typename... _Args>
  240.         iterator
  241.         emplace(_Args&&... __args)
  242.         {
  243.           // The cost is the same whether or not the element is inserted so we
  244.           // always report insertion of 1 element.
  245.           __profcxx_map2umap_insert(this->_M_map2umap_info, this->size(), 1);
  246.           return iterator(_Base::emplace(std::forward<_Args>(__args)...), this);
  247.         }
  248.  
  249.       template<typename... _Args>
  250.         iterator
  251.         emplace_hint(const_iterator __pos, _Args&&... __args)
  252.         {
  253.           auto size_before = this->size();
  254.           auto __res
  255.             = _Base::emplace_hint(__pos.base(), std::forward<_Args>(__args)...);
  256.           __profcxx_map2umap_insert(this->_M_map2umap_info,
  257.                 size_before, _M_hint_used(__pos.base(), __res) ? 0 : 1);
  258.           return iterator(__res, this);
  259.         }
  260. #endif
  261.  
  262.       iterator
  263.       insert(const value_type& __x)
  264.       {
  265.         __profcxx_map2umap_insert(this->_M_map2umap_info, this->size(), 1);
  266.         return iterator(_Base::insert(__x), this);
  267.       }
  268.  
  269. #if __cplusplus >= 201103L
  270.       iterator
  271.       insert(value_type&& __x)
  272.       {
  273.         __profcxx_map2umap_insert(this->_M_map2umap_info, this->size(), 1);
  274.         return iterator(_Base::insert(std::move(__x)), this);
  275.       }
  276. #endif
  277.  
  278.       iterator
  279.       insert(const_iterator __pos, const value_type& __x)
  280.       {
  281.         size_type size_before = this->size();
  282.         _Base_iterator __res = _Base::insert(__pos.base(), __x);
  283.        
  284.         __profcxx_map2umap_insert(this->_M_map2umap_info,
  285.                 size_before, _M_hint_used(__pos.base(), __res) ? 0 : 1);
  286.         return iterator(__res, this);
  287.       }
  288.  
  289. #if __cplusplus >= 201103L
  290.       iterator
  291.       insert(const_iterator __pos, value_type&& __x)
  292.       {
  293.         auto size_before = this->size();
  294.         auto __res = _Base::insert(__pos.base(), std::move(__x));
  295.         __profcxx_map2umap_insert(this->_M_map2umap_info,
  296.                 size_before, _M_hint_used(__pos.base(), __res) ? 0 : 1);
  297.         return iterator(__res, this);
  298.       }
  299. #endif
  300.  
  301. #if __cplusplus >= 201103L
  302.       template<typename _InputIterator,
  303.                typename = std::_RequireInputIter<_InputIterator>>
  304. #else
  305.       template<typename _InputIterator>
  306. #endif
  307.         void
  308.         insert(_InputIterator __first, _InputIterator __last)
  309.         {
  310.           for (; __first != __last; ++__first)
  311.             insert(*__first);
  312.         }
  313.  
  314. #if __cplusplus >= 201103L
  315.       void
  316.       insert(initializer_list<value_type> __l)
  317.       { insert(__l.begin(), __l.end()); }
  318. #endif
  319.  
  320. #if __cplusplus >= 201103L
  321.       iterator
  322.       erase(const_iterator __pos)
  323.       {
  324.         __profcxx_map2umap_erase(this->_M_map2umap_info, this->size(), 1);
  325.         return iterator(_Base::erase(__pos.base()), this);
  326.       }
  327. #else
  328.       void
  329.       erase(iterator __pos)
  330.       {
  331.         __profcxx_map2umap_erase(this->_M_map2umap_info, this->size(), 1);
  332.         _Base::erase(__pos.base());
  333.       }
  334. #endif
  335.  
  336.       size_type
  337.       erase(const key_type& __x)
  338.       {
  339.         __profcxx_map2umap_find(this->_M_map2umap_info, this->size());
  340.         __profcxx_map2umap_erase(this->_M_map2umap_info, this->size(), 1);
  341.         return _Base::erase(__x);
  342.       }
  343.  
  344. #if __cplusplus >= 201103L
  345.       iterator
  346.       erase(const_iterator __first, const_iterator __last)
  347.       {
  348.         if (__first != __last)
  349.           {
  350.             iterator __ret;
  351.             for (; __first != __last;)
  352.               __ret = erase(__first++);
  353.             return __ret;
  354.           }
  355.         else
  356.           return iterator(_Base::erase(__first.base(), __last.base()), this);
  357.       }
  358. #else
  359.       void
  360.       erase(iterator __first, iterator __last)
  361.       {
  362.         for (; __first != __last;)
  363.           erase(__first++);
  364.       }
  365. #endif
  366.  
  367.       void
  368.       clear() _GLIBCXX_NOEXCEPT
  369.       {
  370.         this->_M_profile_destruct();
  371.         _Base::clear();
  372.         this->_M_profile_construct();
  373.       }
  374.  
  375.       size_type
  376.       count(const key_type& __x) const
  377.       {
  378.         __profcxx_map2umap_find(this->_M_map2umap_info, this->size());
  379.         return _Base::count(__x);
  380.       }
  381.  
  382.       // multiset operations:
  383.       iterator
  384.       find(const key_type& __x)
  385.       {
  386.         __profcxx_map2umap_find(this->_M_map2umap_info, this->size());
  387.         return iterator(_Base::find(__x), this);
  388.       }
  389.  
  390.       // _GLIBCXX_RESOLVE_LIB_DEFECTS
  391.       // 214. set::find() missing const overload
  392.       const_iterator
  393.       find(const key_type& __x) const
  394.       {
  395.         __profcxx_map2umap_find(this->_M_map2umap_info, this->size());
  396.         return const_iterator(_Base::find(__x), this);
  397.       }
  398.  
  399.       iterator
  400.       lower_bound(const key_type& __x)
  401.       {
  402.         __profcxx_map2umap_find(this->_M_map2umap_info, this->size());
  403.         return iterator(_Base::lower_bound(__x), this);
  404.       }
  405.  
  406.       // _GLIBCXX_RESOLVE_LIB_DEFECTS
  407.       // 214. set::find() missing const overload
  408.       const_iterator
  409.       lower_bound(const key_type& __x) const
  410.       {
  411.         __profcxx_map2umap_find(this->_M_map2umap_info, this->size());
  412.         __profcxx_map2umap_invalidate(this->_M_map2umap_info);
  413.         return const_iterator(_Base::lower_bound(__x), this);
  414.       }
  415.  
  416.       iterator
  417.       upper_bound(const key_type& __x)
  418.       {
  419.         __profcxx_map2umap_find(this->_M_map2umap_info, this->size());
  420.         __profcxx_map2umap_invalidate(this->_M_map2umap_info);
  421.         return iterator(_Base::upper_bound(__x), this);
  422.       }
  423.  
  424.       // _GLIBCXX_RESOLVE_LIB_DEFECTS
  425.       // 214. set::find() missing const overload
  426.       const_iterator
  427.       upper_bound(const key_type& __x) const
  428.       {
  429.         __profcxx_map2umap_find(this->_M_map2umap_info, this->size());
  430.         __profcxx_map2umap_invalidate(this->_M_map2umap_info);
  431.         return const_iterator(_Base::upper_bound(__x), this);
  432.       }
  433.  
  434.       std::pair<iterator,iterator>
  435.       equal_range(const key_type& __x)
  436.       {
  437.         __profcxx_map2umap_find(this->_M_map2umap_info, this->size());
  438.         std::pair<_Base_iterator, _Base_iterator> __base_ret
  439.           = _Base::equal_range(__x);
  440.         return std::make_pair(iterator(__base_ret.first, this),
  441.                               iterator(__base_ret.second, this));
  442.       }
  443.  
  444.       // _GLIBCXX_RESOLVE_LIB_DEFECTS
  445.       // 214. set::find() missing const overload
  446.       std::pair<const_iterator,const_iterator>
  447.       equal_range(const key_type& __x) const
  448.       {
  449.         __profcxx_map2umap_find(this->_M_map2umap_info, this->size());
  450.         std::pair<_Base_const_iterator, _Base_const_iterator> __base_ret
  451.           = _Base::equal_range(__x);
  452.         return std::make_pair(const_iterator(__base_ret.first, this),
  453.                               const_iterator(__base_ret.second, this));
  454.       }
  455.  
  456.       _Base&
  457.       _M_base() _GLIBCXX_NOEXCEPT       { return *this; }
  458.  
  459.       const _Base&
  460.       _M_base() const _GLIBCXX_NOEXCEPT { return *this; }
  461.  
  462.     private:
  463.       /** If hint is used we consider that the map and unordered_map
  464.        * operations have equivalent insertion cost so we do not update metrics
  465.        * about it.
  466.        * Note that to find out if hint has been used is libstdc++
  467.        * implementation dependent.
  468.        */
  469.       bool
  470.       _M_hint_used(_Base_const_iterator __hint, _Base_iterator __res)
  471.       {
  472.         return (__hint == __res
  473.                 || (__hint == _M_base().end() && ++__res == _M_base().end())
  474.                 || (__hint != _M_base().end() && (++__hint == __res
  475.                                                   || ++__res == --__hint)));
  476.       }
  477.  
  478.       template<typename _K1, typename _C1, typename _A1>
  479.         friend bool
  480.         operator==(const multiset<_K1, _C1, _A1>&,
  481.                    const multiset<_K1, _C1, _A1>&);
  482.  
  483.       template<typename _K1, typename _C1, typename _A1>
  484.         friend bool
  485.         operator< (const multiset<_K1, _C1, _A1>&,
  486.                    const multiset<_K1, _C1, _A1>&);
  487.     };
  488.  
  489.   template<typename _Key, typename _Compare, typename _Allocator>
  490.     inline bool
  491.     operator==(const multiset<_Key, _Compare, _Allocator>& __lhs,
  492.                const multiset<_Key, _Compare, _Allocator>& __rhs)
  493.     {
  494.       __profcxx_map2umap_invalidate(__lhs._M_map2umap_info);
  495.       __profcxx_map2umap_invalidate(__rhs._M_map2umap_info);
  496.       return __lhs._M_base() == __rhs._M_base();
  497.     }
  498.  
  499.   template<typename _Key, typename _Compare, typename _Allocator>
  500.     inline bool
  501.     operator<(const multiset<_Key, _Compare, _Allocator>& __lhs,
  502.               const multiset<_Key, _Compare, _Allocator>& __rhs)
  503.     {
  504.       __profcxx_map2umap_invalidate(__lhs._M_map2umap_info);
  505.       __profcxx_map2umap_invalidate(__rhs._M_map2umap_info);
  506.       return __lhs._M_base() < __rhs._M_base();
  507.     }
  508.  
  509.   template<typename _Key, typename _Compare, typename _Allocator>
  510.     inline bool
  511.     operator!=(const multiset<_Key, _Compare, _Allocator>& __lhs,
  512.                const multiset<_Key, _Compare, _Allocator>& __rhs)
  513.     { return !(__lhs == __rhs); }
  514.  
  515.   template<typename _Key, typename _Compare, typename _Allocator>
  516.     inline bool
  517.     operator<=(const multiset<_Key, _Compare, _Allocator>& __lhs,
  518.                const multiset<_Key, _Compare, _Allocator>& __rhs)
  519.     { return !(__rhs < __lhs); }
  520.  
  521.   template<typename _Key, typename _Compare, typename _Allocator>
  522.     inline bool
  523.     operator>=(const multiset<_Key, _Compare, _Allocator>& __lhs,
  524.                const multiset<_Key, _Compare, _Allocator>& __rhs)
  525.     { return !(__lhs < __rhs); }
  526.  
  527.   template<typename _Key, typename _Compare, typename _Allocator>
  528.     inline bool
  529.     operator>(const multiset<_Key, _Compare, _Allocator>& __lhs,
  530.               const multiset<_Key, _Compare, _Allocator>& __rhs)
  531.     { return __rhs < __lhs; }
  532.  
  533.   template<typename _Key, typename _Compare, typename _Allocator>
  534.     void
  535.     swap(multiset<_Key, _Compare, _Allocator>& __x,
  536.          multiset<_Key, _Compare, _Allocator>& __y)
  537.     { return __x.swap(__y); }
  538.  
  539. } // namespace __profile
  540. } // namespace std
  541.  
  542. #endif
  543.