Subversion Repositories Kolibri OS

Rev

Blame | Last modification | View Log | RSS feed

  1. // Profiling map 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 along
  21. // with this library; see the file COPYING3.  If not see
  22. // <http://www.gnu.org/licenses/>.
  23.  
  24. /** @file profile/map.h
  25.  *  This file is a GNU profile extension to the Standard C++ Library.
  26.  */
  27.  
  28. #ifndef _GLIBCXX_PROFILE_MAP_H
  29. #define _GLIBCXX_PROFILE_MAP_H 1
  30.  
  31. #include <profile/base.h>
  32. #include <profile/ordered_base.h>
  33.  
  34. namespace std _GLIBCXX_VISIBILITY(default)
  35. {
  36. namespace __profile
  37. {
  38.   /// Class std::map wrapper with performance instrumentation.
  39.   template<typename _Key, typename _Tp, typename _Compare = std::less<_Key>,
  40.            typename _Allocator = std::allocator<std::pair<const _Key, _Tp> > >
  41.     class map
  42.     : public _GLIBCXX_STD_C::map<_Key, _Tp, _Compare, _Allocator>,
  43.       public _Ordered_profile<map<_Key, _Tp, _Compare, _Allocator> >
  44.     {
  45.       typedef _GLIBCXX_STD_C::map<_Key, _Tp, _Compare, _Allocator> _Base;
  46.  
  47.       typedef typename _Base::iterator                  _Base_iterator;
  48.       typedef typename _Base::const_iterator            _Base_const_iterator;
  49.  
  50.     public:
  51.       // types:
  52.       typedef _Key                                      key_type;
  53.       typedef _Tp                                       mapped_type;
  54.       typedef typename _Base::value_type                value_type;
  55.       typedef _Compare                                  key_compare;
  56.       typedef typename _Base::reference                 reference;
  57.       typedef typename _Base::const_reference           const_reference;
  58.  
  59.       typedef __iterator_tracker<_Base_iterator, map>   iterator;
  60.       typedef __iterator_tracker<_Base_const_iterator,
  61.                                  map>                   const_iterator;
  62.       typedef std::reverse_iterator<iterator>           reverse_iterator;
  63.       typedef std::reverse_iterator<const_iterator>     const_reverse_iterator;
  64.  
  65.       typedef typename _Base::size_type                 size_type;
  66.       typedef typename _Base::difference_type           difference_type;
  67.  
  68.       // 23.3.1.1 construct/copy/destroy:
  69.  
  70. #if __cplusplus < 201103L
  71.       map()
  72.       : _Base() { }
  73.       map(const map& __x)
  74.         : _Base(__x) { }
  75.       ~map()
  76.       { }
  77. #else
  78.       map() = default;
  79.       map(const map&) = default;
  80.       map(map&&) = default;
  81.       ~map() = default;
  82. #endif
  83.  
  84.       explicit
  85.       map(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.         map(_InputIterator __first, _InputIterator __last,
  96.             const _Compare& __comp = _Compare(),
  97.             const _Allocator& __a = _Allocator())
  98.         : _Base(__first, __last, __comp, __a) { }
  99.  
  100.       map(const _Base& __x)
  101.       : _Base(__x) { }
  102.  
  103. #if __cplusplus >= 201103L
  104.       map(initializer_list<value_type> __l,
  105.           const _Compare& __c = _Compare(),
  106.           const _Allocator& __a = _Allocator())
  107.       : _Base(__l, __c, __a) { }
  108.  
  109.       explicit
  110.       map(const _Allocator& __a)
  111.       : _Base(__a) { }
  112.  
  113.       map(const map& __x, const _Allocator& __a)
  114.       : _Base(__x, __a) { }
  115.  
  116.       map(map&& __x, const _Allocator& __a)
  117.       noexcept( noexcept(_Base(std::move(__x), __a)) )
  118.       : _Base(std::move(__x), __a) { }
  119.  
  120.       map(initializer_list<value_type> __l, const _Allocator& __a)
  121.       : _Base(__l, __a) { }
  122.  
  123.       template<typename _InputIterator>
  124.         map(_InputIterator __first, _InputIterator __last,
  125.             const _Allocator& __a)
  126.         : _Base(__first, __last, __a) { }
  127. #endif
  128.  
  129. #if __cplusplus < 201103L
  130.       map&
  131.       operator=(const map& __x)
  132.       {
  133.         this->_M_profile_destruct();
  134.         _M_base() = __x;
  135.         this->_M_profile_construct();
  136.         return *this;
  137.       }
  138. #else
  139.       map&
  140.       operator=(const map&) = default;
  141.  
  142.       map&
  143.       operator=(map&&) = default;
  144.  
  145.       map&
  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.       // 23.3.1.2 element access:
  227.       mapped_type&
  228.       operator[](const key_type& __k)
  229.       {
  230.         __profcxx_map2umap_find(this->_M_map2umap_info, this->size());
  231.         return _Base::operator[](__k);
  232.       }
  233.  
  234. #if __cplusplus >= 201103L
  235.       mapped_type&
  236.       operator[](key_type&& __k)
  237.       {
  238.         __profcxx_map2umap_find(this->_M_map2umap_info, this->size());
  239.         return _Base::operator[](std::move(__k));
  240.       }
  241. #endif
  242.  
  243.       mapped_type&
  244.       at(const key_type& __k)
  245.       {
  246.         __profcxx_map2umap_find(this->_M_map2umap_info, this->size());
  247.         return _Base::at(__k);
  248.       }
  249.  
  250.       const mapped_type&
  251.       at(const key_type& __k) const
  252.       {
  253.         __profcxx_map2umap_find(this->_M_map2umap_info, this->size());
  254.         return _Base::at(__k);
  255.       }
  256.  
  257.       // modifiers:
  258. #if __cplusplus >= 201103L
  259.       template<typename... _Args>
  260.         std::pair<iterator, bool>
  261.         emplace(_Args&&... __args)
  262.         {
  263.           // The cost is the same whether or not the element is inserted so we
  264.           // always report insertion of 1 element.
  265.           __profcxx_map2umap_insert(this->_M_map2umap_info, this->size(), 1);
  266.           auto __base_ret = _Base::emplace(std::forward<_Args>(__args)...);
  267.           return std::make_pair(iterator(__base_ret.first, this),
  268.                                 __base_ret.second);
  269.         }
  270.  
  271.       template<typename... _Args>
  272.         iterator
  273.         emplace_hint(const_iterator __pos, _Args&&... __args)
  274.         {
  275.           auto size_before = this->size();
  276.           auto __res
  277.             = _Base::emplace_hint(__pos.base(), std::forward<_Args>(__args)...);
  278.           __profcxx_map2umap_insert(this->_M_map2umap_info,
  279.                 size_before, _M_hint_used(__pos.base(), __res) ? 0 : 1);
  280.           return iterator(__res, this);
  281.         }
  282. #endif
  283.  
  284.       std::pair<iterator, bool>
  285.       insert(const value_type& __x)
  286.       {
  287.         __profcxx_map2umap_insert(this->_M_map2umap_info, this->size(), 1);
  288.         std::pair<_Base_iterator, bool> __base_ret = _Base::insert(__x);
  289.         return std::make_pair(iterator(__base_ret.first, this),
  290.                               __base_ret.second);
  291.       }
  292.  
  293. #if __cplusplus >= 201103L
  294.       template<typename _Pair, typename = typename
  295.                std::enable_if<std::is_constructible<value_type,
  296.                                                     _Pair&&>::value>::type>
  297.         std::pair<iterator, bool>
  298.         insert(_Pair&& __x)
  299.         {
  300.           __profcxx_map2umap_insert(this->_M_map2umap_info, this->size(), 1);
  301.           auto __base_ret= _Base::insert(std::forward<_Pair>(__x));
  302.           return std::make_pair(iterator(__base_ret.first, this),
  303.                                 __base_ret.second);
  304.         }
  305. #endif
  306.  
  307. #if __cplusplus >= 201103L
  308.       void
  309.       insert(std::initializer_list<value_type> __list)
  310.       { insert(__list.begin(), __list.end()); }
  311. #endif
  312.  
  313.       iterator
  314. #if __cplusplus >= 201103L
  315.       insert(const_iterator __pos, const value_type& __x)
  316. #else
  317.       insert(iterator __pos, const value_type& __x)
  318. #endif
  319.       {
  320.         size_type size_before = this->size();
  321.         _Base_iterator __res = _Base::insert(__pos.base(), __x);
  322.        
  323.         __profcxx_map2umap_insert(this->_M_map2umap_info,
  324.                 size_before, _M_hint_used(__pos.base(), __res) ? 0 : 1);
  325.         return iterator(__res, this);
  326.       }
  327.  
  328. #if __cplusplus >= 201103L
  329.       template<typename _Pair, typename = typename
  330.                std::enable_if<std::is_constructible<value_type,
  331.                                                     _Pair&&>::value>::type>
  332.         iterator
  333.         insert(const_iterator __pos, _Pair&& __x)
  334.         {
  335.           size_type size_before = this->size();
  336.           auto __res = _Base::insert(__pos.base(), std::forward<_Pair>(__x));
  337.        
  338.           __profcxx_map2umap_insert(this->_M_map2umap_info,
  339.                 size_before, _M_hint_used(__pos.base(), __res) ? 0 : 1);
  340.           return iterator(__res, this);
  341.       }
  342. #endif
  343.  
  344.       template<typename _InputIterator>
  345.         void
  346.         insert(_InputIterator __first, _InputIterator __last)
  347.         {
  348.           for (; __first != __last; ++__first)
  349.             insert(*__first);
  350.         }
  351.  
  352. #if __cplusplus >= 201103L
  353.       iterator
  354.       erase(const_iterator __pos)
  355.       {
  356.         __profcxx_map2umap_erase(this->_M_map2umap_info, this->size(), 1);
  357.         return iterator(_Base::erase(__pos.base()), this);
  358.       }
  359.  
  360.       iterator
  361.       erase(iterator __pos)
  362.       {
  363.         __profcxx_map2umap_erase(this->_M_map2umap_info, this->size(), 1);
  364.         return iterator(_Base::erase(__pos.base()), this);
  365.       }
  366. #else
  367.       void
  368.       erase(iterator __pos)
  369.       {
  370.         __profcxx_map2umap_erase(this->_M_map2umap_info, this->size(), 1);
  371.         _Base::erase(__pos.base());
  372.       }
  373. #endif
  374.  
  375.       size_type
  376.       erase(const key_type& __x)
  377.       {
  378.         __profcxx_map2umap_find(this->_M_map2umap_info, this->size());
  379.         __profcxx_map2umap_erase(this->_M_map2umap_info, this->size(), 1);
  380.         return _Base::erase(__x);
  381.       }
  382.  
  383. #if __cplusplus >= 201103L
  384.       iterator
  385.       erase(const_iterator __first, const_iterator __last)
  386.       {
  387.         if (__first != __last)
  388.           {
  389.             iterator __ret;
  390.             for (; __first != __last;)
  391.               __ret = erase(__first++);
  392.             return __ret;
  393.           }
  394.         else
  395.           return iterator(_Base::erase(__first.base(), __last.base()), this);
  396.       }
  397. #else
  398.       void
  399.       erase(iterator __first, iterator __last)
  400.       {
  401.         for (; __first != __last;)
  402.           erase(__first++);
  403.       }
  404. #endif
  405.  
  406.       void
  407.       swap(map& __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.3.1.3 map operations:
  425.       iterator
  426.       find(const key_type& __x)
  427.       {
  428.         __profcxx_map2umap_find(this->_M_map2umap_info, this->size());
  429.         return iterator(_Base::find(__x), this);
  430.       }
  431.  
  432.       const_iterator
  433.       find(const key_type& __x) const
  434.       {
  435.         __profcxx_map2umap_find(this->_M_map2umap_info, this->size());
  436.         return const_iterator(_Base::find(__x), this);
  437.       }
  438.  
  439.       size_type
  440.       count(const key_type& __x) const
  441.       {
  442.         __profcxx_map2umap_find(this->_M_map2umap_info, this->size());
  443.         return _Base::count(__x);
  444.       }
  445.  
  446.       iterator
  447.       lower_bound(const key_type& __x)
  448.       {
  449.         __profcxx_map2umap_find(this->_M_map2umap_info, this->size());
  450.         __profcxx_map2umap_invalidate(this->_M_map2umap_info);
  451.         return iterator(_Base::lower_bound(__x), this);
  452.       }
  453.  
  454.       const_iterator
  455.       lower_bound(const key_type& __x) const
  456.       {
  457.         __profcxx_map2umap_find(this->_M_map2umap_info, this->size());
  458.         __profcxx_map2umap_invalidate(this->_M_map2umap_info);
  459.         return const_iterator(_Base::lower_bound(__x), this);
  460.       }
  461.  
  462.       iterator
  463.       upper_bound(const key_type& __x)
  464.       {
  465.         __profcxx_map2umap_find(this->_M_map2umap_info, this->size());
  466.         __profcxx_map2umap_invalidate(this->_M_map2umap_info);
  467.         return iterator(_Base::upper_bound(__x), this);
  468.       }
  469.  
  470.       const_iterator
  471.       upper_bound(const key_type& __x) const
  472.       {
  473.         __profcxx_map2umap_find(this->_M_map2umap_info, this->size());
  474.         __profcxx_map2umap_invalidate(this->_M_map2umap_info);
  475.         return const_iterator(_Base::upper_bound(__x), this);
  476.       }
  477.  
  478.       std::pair<iterator,iterator>
  479.       equal_range(const key_type& __x)
  480.       {
  481.         __profcxx_map2umap_find(this->_M_map2umap_info, this->size());
  482.         std::pair<_Base_iterator, _Base_iterator> __base_ret
  483.           = _Base::equal_range(__x);
  484.         return std::make_pair(iterator(__base_ret.first, this),
  485.                               iterator(__base_ret.second, this));
  486.       }
  487.  
  488.       std::pair<const_iterator,const_iterator>
  489.       equal_range(const key_type& __x) const
  490.       {
  491.         __profcxx_map2umap_find(this->_M_map2umap_info, this->size());
  492.         std::pair<_Base_const_iterator, _Base_const_iterator> __base_ret
  493.           = _Base::equal_range(__x);
  494.         return std::make_pair(const_iterator(__base_ret.first, this),
  495.                               const_iterator(__base_ret.second, this));
  496.       }
  497.  
  498.       _Base&
  499.       _M_base() _GLIBCXX_NOEXCEPT       { return *this; }
  500.  
  501.       const _Base&
  502.       _M_base() const _GLIBCXX_NOEXCEPT { return *this; }
  503.  
  504.     private:
  505.       /** If hint is used we consider that the map and unordered_map
  506.        * operations have equivalent insertion cost so we do not update metrics
  507.        * about it.
  508.        * Note that to find out if hint has been used is libstdc++
  509.        * implementation dependent.
  510.        */
  511.       bool
  512.       _M_hint_used(_Base_const_iterator __hint, _Base_iterator __res)
  513.       {
  514.         return (__hint == __res
  515.                 || (__hint == _M_base().end() && ++__res == _M_base().end())
  516.                 || (__hint != _M_base().end() && (++__hint == __res
  517.                                                   || ++__res == --__hint)));
  518.       }
  519.  
  520.  
  521.       template<typename _K1, typename _T1, typename _C1, typename _A1>
  522.         friend bool
  523.         operator==(const map<_K1, _T1, _C1, _A1>&,
  524.                    const map<_K1, _T1, _C1, _A1>&);
  525.  
  526.       template<typename _K1, typename _T1, typename _C1, typename _A1>
  527.         friend bool
  528.         operator<(const map<_K1, _T1, _C1, _A1>&,
  529.                   const map<_K1, _T1, _C1, _A1>&);      
  530.     };
  531.  
  532.   template<typename _Key, typename _Tp,
  533.            typename _Compare, typename _Allocator>
  534.     inline bool
  535.     operator==(const map<_Key, _Tp, _Compare, _Allocator>& __lhs,
  536.                const map<_Key, _Tp, _Compare, _Allocator>& __rhs)
  537.     {
  538.       __profcxx_map2umap_invalidate(__lhs._M_map2umap_info);
  539.       __profcxx_map2umap_invalidate(__rhs._M_map2umap_info);
  540.       return __lhs._M_base() == __rhs._M_base();
  541.     }
  542.  
  543.   template<typename _Key, typename _Tp,
  544.            typename _Compare, typename _Allocator>
  545.     inline bool
  546.     operator<(const map<_Key, _Tp, _Compare, _Allocator>& __lhs,
  547.               const map<_Key, _Tp, _Compare, _Allocator>& __rhs)
  548.     {
  549.       __profcxx_map2umap_invalidate(__lhs._M_map2umap_info);
  550.       __profcxx_map2umap_invalidate(__rhs._M_map2umap_info);
  551.       return __lhs._M_base() < __rhs._M_base();
  552.     }
  553.  
  554.   template<typename _Key, typename _Tp,
  555.            typename _Compare, typename _Allocator>
  556.     inline bool
  557.     operator!=(const map<_Key, _Tp, _Compare, _Allocator>& __lhs,
  558.                const map<_Key, _Tp, _Compare, _Allocator>& __rhs)
  559.     { return !(__lhs == __rhs); }
  560.  
  561.   template<typename _Key, typename _Tp,
  562.            typename _Compare, typename _Allocator>
  563.     inline bool
  564.     operator<=(const map<_Key, _Tp, _Compare, _Allocator>& __lhs,
  565.                const map<_Key, _Tp, _Compare, _Allocator>& __rhs)
  566.     { return !(__rhs < __lhs); }
  567.  
  568.   template<typename _Key, typename _Tp,
  569.            typename _Compare, typename _Allocator>
  570.     inline bool
  571.     operator>=(const map<_Key, _Tp, _Compare, _Allocator>& __lhs,
  572.                const map<_Key, _Tp, _Compare, _Allocator>& __rhs)
  573.     { return !(__lhs < __rhs); }
  574.  
  575.   template<typename _Key, typename _Tp,
  576.            typename _Compare, typename _Allocator>
  577.     inline bool
  578.     operator>(const map<_Key, _Tp, _Compare, _Allocator>& __lhs,
  579.               const map<_Key, _Tp, _Compare, _Allocator>& __rhs)
  580.     { return __rhs < __lhs; }
  581.  
  582.   template<typename _Key, typename _Tp,
  583.            typename _Compare, typename _Allocator>
  584.     inline void
  585.     swap(map<_Key, _Tp, _Compare, _Allocator>& __lhs,
  586.          map<_Key, _Tp, _Compare, _Allocator>& __rhs)
  587.     { __lhs.swap(__rhs); }
  588.  
  589. } // namespace __profile
  590. } // namespace std
  591.  
  592. #endif
  593.