Subversion Repositories Kolibri OS

Rev

Blame | Last modification | View Log | RSS feed

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