Subversion Repositories Kolibri OS

Rev

Blame | Last modification | View Log | RSS feed

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