Subversion Repositories Kolibri OS

Rev

Blame | Last modification | View Log | RSS feed

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