Subversion Repositories Kolibri OS

Rev

Blame | Last modification | View Log | RSS feed

  1. // Profiling unordered_map/unordered_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 along
  21. // with this library; see the file COPYING3.  If not see
  22. // <http://www.gnu.org/licenses/>.
  23.  
  24. /** @file profile/unordered_map
  25.  *  This file is a GNU profile extension to the Standard C++ Library.
  26.  */
  27.  
  28. #ifndef _GLIBCXX_PROFILE_UNORDERED_MAP
  29. #define _GLIBCXX_PROFILE_UNORDERED_MAP 1
  30.  
  31. #if __cplusplus < 201103L
  32. # include <bits/c++0x_warning.h>
  33. #else
  34. # include <unordered_map>
  35.  
  36. #include <profile/base.h>
  37. #include <profile/unordered_base.h>
  38.  
  39. #define _GLIBCXX_BASE unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>
  40. #define _GLIBCXX_STD_BASE _GLIBCXX_STD_C::_GLIBCXX_BASE
  41.  
  42. namespace std _GLIBCXX_VISIBILITY(default)
  43. {
  44. namespace __profile
  45. {
  46.   /// Class std::unordered_map wrapper with performance instrumentation.
  47.   template<typename _Key, typename _Tp,
  48.            typename _Hash = std::hash<_Key>,
  49.            typename _Pred = std::equal_to<_Key>,
  50.            typename _Alloc = std::allocator<std::pair<const _Key, _Tp> > >
  51.     class unordered_map
  52.     : public _GLIBCXX_STD_BASE,
  53.       public _Unordered_profile<unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>,
  54.                                 true>
  55.     {
  56.       typedef typename _GLIBCXX_STD_BASE _Base;
  57.  
  58.       _Base&
  59.       _M_base() noexcept        { return *this; }
  60.  
  61.       const _Base&
  62.       _M_base() const noexcept  { return *this; }
  63.  
  64.     public:
  65.       typedef typename _Base::size_type         size_type;
  66.       typedef typename _Base::hasher            hasher;
  67.       typedef typename _Base::key_equal         key_equal;
  68.       typedef typename _Base::allocator_type    allocator_type;
  69.       typedef typename _Base::key_type          key_type;
  70.       typedef typename _Base::value_type        value_type;
  71.       typedef typename _Base::difference_type   difference_type;
  72.       typedef typename _Base::reference         reference;
  73.       typedef typename _Base::const_reference   const_reference;
  74.       typedef typename _Base::mapped_type       mapped_type;
  75.  
  76.       typedef typename _Base::iterator          iterator;
  77.       typedef typename _Base::const_iterator    const_iterator;
  78.  
  79.       unordered_map() = default;
  80.  
  81.       explicit
  82.       unordered_map(size_type __n,
  83.                     const hasher& __hf = hasher(),
  84.                     const key_equal& __eql = key_equal(),
  85.                     const allocator_type& __a = allocator_type())
  86.       : _Base(__n, __hf, __eql, __a) { }
  87.  
  88.       template<typename _InputIterator>
  89.         unordered_map(_InputIterator __f, _InputIterator __l,
  90.                       size_type __n = 0,
  91.                       const hasher& __hf = hasher(),
  92.                       const key_equal& __eql = key_equal(),
  93.                       const allocator_type& __a = allocator_type())
  94.         : _Base(__f, __l, __n, __hf, __eql, __a) { }
  95.  
  96.       unordered_map(const unordered_map&) = default;
  97.  
  98.       unordered_map(const _Base& __x)
  99.       : _Base(__x) { }
  100.  
  101.       unordered_map(unordered_map&&) = default;
  102.  
  103.       explicit
  104.       unordered_map(const allocator_type& __a)
  105.       : _Base(__a) { }
  106.  
  107.       unordered_map(const unordered_map& __umap,
  108.                     const allocator_type& __a)
  109.       : _Base(__umap, __a) { }
  110.  
  111.       unordered_map(unordered_map&& __umap,
  112.                     const allocator_type& __a)
  113.       : _Base(std::move(__umap._M_base()), __a) { }
  114.  
  115.       unordered_map(initializer_list<value_type> __l,
  116.                     size_type __n = 0,
  117.                     const hasher& __hf = hasher(),
  118.                     const key_equal& __eql = key_equal(),
  119.                     const allocator_type& __a = allocator_type())
  120.       : _Base(__l, __n, __hf, __eql, __a) { }
  121.  
  122.       unordered_map(size_type __n, const allocator_type& __a)
  123.       : unordered_map(__n, hasher(), key_equal(), __a)
  124.       { }
  125.  
  126.       unordered_map(size_type __n, const hasher& __hf,
  127.                     const allocator_type& __a)
  128.       : unordered_map(__n, __hf, key_equal(), __a)
  129.       { }
  130.  
  131.       template<typename _InputIterator>
  132.         unordered_map(_InputIterator __first, _InputIterator __last,
  133.                       size_type __n,
  134.                       const allocator_type& __a)
  135.           : unordered_map(__first, __last, __n, hasher(), key_equal(), __a)
  136.         { }
  137.  
  138.       template<typename _InputIterator>
  139.         unordered_map(_InputIterator __first, _InputIterator __last,
  140.                       size_type __n, const hasher& __hf,
  141.                       const allocator_type& __a)
  142.           : unordered_map(__first, __last, __n, __hf, key_equal(), __a)
  143.         { }
  144.  
  145.       unordered_map(initializer_list<value_type> __l,
  146.                     size_type __n,
  147.                     const allocator_type& __a)
  148.         : unordered_map(__l, __n, hasher(), key_equal(), __a)
  149.       { }
  150.  
  151.       unordered_map(initializer_list<value_type> __l,
  152.                     size_type __n, const hasher& __hf,
  153.                     const allocator_type& __a)
  154.         : unordered_map(__l, __n, __hf, key_equal(), __a)
  155.       { }
  156.  
  157.       unordered_map&
  158.       operator=(const unordered_map&) = default;
  159.  
  160.       unordered_map&
  161.       operator=(unordered_map&&) = default;
  162.  
  163.       unordered_map&
  164.       operator=(initializer_list<value_type> __l)
  165.       {
  166.         this->_M_profile_destruct();
  167.         _M_base() = __l;
  168.         this->_M_profile_construct();
  169.         return *this;
  170.       }
  171.  
  172.       void
  173.       clear() noexcept
  174.       {
  175.         this->_M_profile_destruct();
  176.         _Base::clear();
  177.         this->_M_profile_construct();
  178.       }
  179.  
  180.       template<typename... _Args>
  181.         std::pair<iterator, bool>
  182.         emplace(_Args&&... __args)
  183.         {
  184.           size_type __old_size = _Base::bucket_count();
  185.           std::pair<iterator, bool> __res
  186.             = _Base::emplace(std::forward<_Args>(__args)...);
  187.           this->_M_profile_resize(__old_size);
  188.           return __res;
  189.         }
  190.  
  191.       template<typename... _Args>
  192.         iterator
  193.         emplace_hint(const_iterator __it, _Args&&... __args)
  194.         {
  195.           size_type __old_size = _Base::bucket_count();
  196.           iterator __res
  197.             = _Base::emplace_hint(__it, std::forward<_Args>(__args)...);
  198.           this->_M_profile_resize(__old_size);
  199.           return __res;
  200.         }
  201.  
  202.       void
  203.       insert(std::initializer_list<value_type> __l)
  204.       {
  205.         size_type __old_size = _Base::bucket_count();
  206.         _Base::insert(__l);
  207.         this->_M_profile_resize(__old_size);
  208.       }
  209.  
  210.       std::pair<iterator, bool>
  211.       insert(const value_type& __obj)
  212.       {
  213.         size_type __old_size = _Base::bucket_count();
  214.         std::pair<iterator, bool> __res = _Base::insert(__obj);
  215.         this->_M_profile_resize(__old_size);
  216.         return __res;
  217.       }
  218.  
  219.       iterator
  220.       insert(const_iterator __iter, const value_type& __v)
  221.       {
  222.         size_type __old_size = _Base::bucket_count();
  223.         iterator __res = _Base::insert(__iter, __v);
  224.         this->_M_profile_resize(__old_size);
  225.         return __res;
  226.       }
  227.  
  228.       template<typename _Pair, typename = typename
  229.                std::enable_if<std::is_constructible<value_type,
  230.                                                     _Pair&&>::value>::type>
  231.         std::pair<iterator, bool>
  232.         insert(_Pair&& __obj)
  233.         {
  234.           size_type __old_size = _Base::bucket_count();
  235.           std::pair<iterator, bool> __res
  236.             = _Base::insert(std::forward<_Pair>(__obj));
  237.           this->_M_profile_resize(__old_size);
  238.           return __res;
  239.         }
  240.  
  241.       template<typename _Pair, typename = typename
  242.                std::enable_if<std::is_constructible<value_type,
  243.                                                     _Pair&&>::value>::type>
  244.         iterator
  245.         insert(const_iterator __iter, _Pair&& __v)
  246.         {
  247.           size_type __old_size = _Base::bucket_count();
  248.           iterator __res = _Base::insert(__iter, std::forward<_Pair>(__v));
  249.           this->_M_profile_resize(__old_size);
  250.           return __res;
  251.         }
  252.  
  253.       template<typename _InputIter>
  254.         void
  255.         insert(_InputIter __first, _InputIter __last)
  256.         {
  257.           size_type __old_size = _Base::bucket_count();
  258.           _Base::insert(__first, __last);
  259.           this->_M_profile_resize(__old_size);
  260.         }
  261.  
  262.       // operator[]
  263.       mapped_type&
  264.       operator[](const _Key& __k)
  265.       {
  266.         size_type __old_size = _Base::bucket_count();
  267.         mapped_type& __res = _M_base()[__k];
  268.         this->_M_profile_resize(__old_size);
  269.         return __res;
  270.       }
  271.  
  272.       mapped_type&
  273.       operator[](_Key&& __k)
  274.       {
  275.         size_type __old_size = _Base::bucket_count();
  276.         mapped_type& __res = _M_base()[std::move(__k)];
  277.         this->_M_profile_resize(__old_size);
  278.         return __res;
  279.       }
  280.  
  281.       void
  282.       swap(unordered_map& __x)
  283.       noexcept( noexcept(__x._M_base().swap(__x)) )
  284.       {
  285.         _Base::swap(__x._M_base());
  286.         this->_M_swap(__x);
  287.       }
  288.  
  289.       void rehash(size_type __n)
  290.       {
  291.         size_type __old_size = _Base::bucket_count();
  292.         _Base::rehash(__n);
  293.         this->_M_profile_resize(__old_size);
  294.       }
  295.   };
  296.  
  297.   template<typename _Key, typename _Tp, typename _Hash,
  298.            typename _Pred, typename _Alloc>
  299.     inline void
  300.     swap(unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
  301.          unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
  302.     { __x.swap(__y); }
  303.  
  304.   template<typename _Key, typename _Tp, typename _Hash,
  305.            typename _Pred, typename _Alloc>
  306.     inline bool
  307.     operator==(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
  308.                const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
  309.     { return static_cast<const _GLIBCXX_STD_BASE&>(__x) == __y; }
  310.  
  311.   template<typename _Key, typename _Tp, typename _Hash,
  312.            typename _Pred, typename _Alloc>
  313.     inline bool
  314.     operator!=(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
  315.                const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
  316.     { return !(__x == __y); }
  317.  
  318. #undef _GLIBCXX_BASE
  319. #undef _GLIBCXX_STD_BASE
  320. #define _GLIBCXX_BASE unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>
  321. #define _GLIBCXX_STD_BASE _GLIBCXX_STD_C::_GLIBCXX_BASE
  322.  
  323.   /// Class std::unordered_multimap wrapper with performance instrumentation.
  324.   template<typename _Key, typename _Tp,
  325.            typename _Hash = std::hash<_Key>,
  326.            typename _Pred = std::equal_to<_Key>,
  327.            typename _Alloc = std::allocator<std::pair<const _Key, _Tp> > >
  328.     class unordered_multimap
  329.     : public _GLIBCXX_STD_BASE,
  330.       public _Unordered_profile<unordered_multimap<_Key, _Tp,
  331.                                                    _Hash, _Pred, _Alloc>,
  332.                                 false>
  333.     {
  334.       typedef typename _GLIBCXX_STD_BASE _Base;
  335.  
  336.       _Base&
  337.       _M_base() noexcept        { return *this; }
  338.  
  339.       const _Base&
  340.       _M_base() const noexcept  { return *this; }
  341.  
  342.     public:
  343.       typedef typename _Base::size_type         size_type;
  344.       typedef typename _Base::hasher            hasher;
  345.       typedef typename _Base::key_equal         key_equal;
  346.       typedef typename _Base::allocator_type    allocator_type;
  347.       typedef typename _Base::key_type          key_type;
  348.       typedef typename _Base::value_type        value_type;
  349.       typedef typename _Base::difference_type   difference_type;
  350.       typedef typename _Base::reference         reference;
  351.       typedef typename _Base::const_reference   const_reference;
  352.  
  353.       typedef typename _Base::iterator          iterator;
  354.       typedef typename _Base::const_iterator    const_iterator;
  355.  
  356.       unordered_multimap() = default;
  357.  
  358.       explicit
  359.       unordered_multimap(size_type __n,
  360.                          const hasher& __hf = hasher(),
  361.                          const key_equal& __eql = key_equal(),
  362.                          const allocator_type& __a = allocator_type())
  363.       : _Base(__n, __hf, __eql, __a) { }
  364.  
  365.       template<typename _InputIterator>
  366.         unordered_multimap(_InputIterator __f, _InputIterator __l,
  367.                            size_type __n = 0,
  368.                            const hasher& __hf = hasher(),
  369.                            const key_equal& __eql = key_equal(),
  370.                            const allocator_type& __a = allocator_type())
  371.         : _Base(__f, __l, __n, __hf, __eql, __a) { }
  372.  
  373.       unordered_multimap(const unordered_multimap&) = default;
  374.  
  375.       unordered_multimap(const _Base& __x)
  376.       : _Base(__x) { }
  377.  
  378.       unordered_multimap(unordered_multimap&&) = default;
  379.  
  380.       explicit
  381.       unordered_multimap(const allocator_type& __a)
  382.       : _Base(__a) { }
  383.  
  384.       unordered_multimap(const unordered_multimap& __ummap,
  385.                          const allocator_type& __a)
  386.       : _Base(__ummap._M_base(), __a) { }
  387.  
  388.       unordered_multimap(unordered_multimap&& __ummap,
  389.                          const allocator_type& __a)
  390.       : _Base(std::move(__ummap._M_base()), __a) { }
  391.  
  392.       unordered_multimap(initializer_list<value_type> __l,
  393.                          size_type __n = 0,
  394.                          const hasher& __hf = hasher(),
  395.                          const key_equal& __eql = key_equal(),
  396.                          const allocator_type& __a = allocator_type())
  397.       : _Base(__l, __n, __hf, __eql, __a) { }
  398.  
  399.       unordered_multimap(size_type __n, const allocator_type& __a)
  400.       : unordered_multimap(__n, hasher(), key_equal(), __a)
  401.       { }
  402.  
  403.       unordered_multimap(size_type __n, const hasher& __hf,
  404.                          const allocator_type& __a)
  405.       : unordered_multimap(__n, __hf, key_equal(), __a)
  406.       { }
  407.  
  408.       template<typename _InputIterator>
  409.         unordered_multimap(_InputIterator __first, _InputIterator __last,
  410.                            size_type __n,
  411.                            const allocator_type& __a)
  412.           : unordered_multimap(__first, __last, __n, hasher(), key_equal(), __a)
  413.         { }
  414.  
  415.       template<typename _InputIterator>
  416.         unordered_multimap(_InputIterator __first, _InputIterator __last,
  417.                            size_type __n, const hasher& __hf,
  418.                            const allocator_type& __a)
  419.           : unordered_multimap(__first, __last, __n, __hf, key_equal(), __a)
  420.         { }
  421.  
  422.       unordered_multimap(initializer_list<value_type> __l,
  423.                          size_type __n,
  424.                          const allocator_type& __a)
  425.         : unordered_multimap(__l, __n, hasher(), key_equal(), __a)
  426.       { }
  427.  
  428.       unordered_multimap(initializer_list<value_type> __l,
  429.                          size_type __n, const hasher& __hf,
  430.                          const allocator_type& __a)
  431.         : unordered_multimap(__l, __n, __hf, key_equal(), __a)
  432.       { }
  433.  
  434.       unordered_multimap&
  435.       operator=(const unordered_multimap&) = default;
  436.  
  437.       unordered_multimap&
  438.       operator=(unordered_multimap&&) = default;
  439.  
  440.       unordered_multimap&
  441.       operator=(initializer_list<value_type> __l)
  442.       {
  443.         this->_M_profile_destruct();
  444.         _M_base() = __l;
  445.         this->_M_profile_construct();
  446.         return *this;
  447.       }
  448.  
  449.       void
  450.       clear() noexcept
  451.       {
  452.         this->_M_profile_destruct();
  453.         _Base::clear();
  454.         this->_M_profile_construct();
  455.       }
  456.  
  457.       template<typename... _Args>
  458.         iterator
  459.         emplace(_Args&&... __args)
  460.         {
  461.           size_type __old_size = _Base::bucket_count();
  462.           iterator __res
  463.             = _Base::emplace(std::forward<_Args>(__args)...);
  464.           this->_M_profile_resize(__old_size);
  465.           return __res;
  466.         }
  467.  
  468.       template<typename... _Args>
  469.         iterator
  470.         emplace_hint(const_iterator __it, _Args&&... __args)
  471.         {
  472.           size_type __old_size = _Base::bucket_count();
  473.           iterator __res
  474.             = _Base::emplace_hint(__it, std::forward<_Args>(__args)...);
  475.           this->_M_profile_resize(__old_size);
  476.           return __res;
  477.         }
  478.  
  479.       void
  480.       insert(std::initializer_list<value_type> __l)
  481.       {
  482.         size_type __old_size = _Base::bucket_count();
  483.         _Base::insert(__l);
  484.         this->_M_profile_resize(__old_size);
  485.       }
  486.  
  487.       iterator
  488.       insert(const value_type& __obj)
  489.       {
  490.         size_type __old_size = _Base::bucket_count();
  491.         iterator __res = _Base::insert(__obj);
  492.         this->_M_profile_resize(__old_size);
  493.         return __res;
  494.       }
  495.  
  496.       iterator
  497.       insert(const_iterator __iter, const value_type& __v)
  498.       {
  499.         size_type __old_size = _Base::bucket_count();
  500.         iterator __res = _Base::insert(__iter, __v);
  501.         this->_M_profile_resize(__old_size);
  502.         return __res;
  503.       }
  504.  
  505.       template<typename _Pair, typename = typename
  506.                std::enable_if<std::is_constructible<value_type,
  507.                                                     _Pair&&>::value>::type>
  508.         iterator
  509.         insert(_Pair&& __obj)
  510.         {
  511.           size_type __old_size = _Base::bucket_count();
  512.           iterator __res = _Base::insert(std::forward<_Pair>(__obj));
  513.           this->_M_profile_resize(__old_size);
  514.           return __res;
  515.         }
  516.  
  517.       template<typename _Pair, typename = typename
  518.                std::enable_if<std::is_constructible<value_type,
  519.                                                     _Pair&&>::value>::type>
  520.         iterator
  521.         insert(const_iterator __iter, _Pair&& __v)
  522.         {
  523.           size_type __old_size = _Base::bucket_count();
  524.           iterator __res = _Base::insert(__iter, std::forward<_Pair>(__v));
  525.           this->_M_profile_resize(__old_size);
  526.           return __res;
  527.         }
  528.  
  529.       template<typename _InputIter>
  530.         void
  531.         insert(_InputIter __first, _InputIter __last)
  532.         {
  533.           size_type __old_size = _Base::bucket_count();
  534.           _Base::insert(__first, __last);
  535.           this->_M_profile_resize(__old_size);
  536.         }
  537.  
  538.       void
  539.       swap(unordered_multimap& __x)
  540.       noexcept( noexcept(__x._M_base().swap(__x)) )
  541.       {
  542.         _Base::swap(__x._M_base());
  543.         this->_M_swap(__x);
  544.       }
  545.  
  546.       void
  547.       rehash(size_type __n)
  548.       {
  549.         size_type __old_size = _Base::bucket_count();
  550.         _Base::rehash(__n);
  551.         this->_M_profile_resize(__old_size);
  552.       }
  553.   };
  554.  
  555.   template<typename _Key, typename _Tp, typename _Hash,
  556.            typename _Pred, typename _Alloc>
  557.     inline void
  558.     swap(unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
  559.          unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
  560.     { __x.swap(__y); }
  561.  
  562.   template<typename _Key, typename _Tp, typename _Hash,
  563.            typename _Pred, typename _Alloc>
  564.     inline bool
  565.     operator==(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
  566.                const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
  567.     { return static_cast<const _GLIBCXX_STD_BASE&>(__x) == __y; }
  568.  
  569.   template<typename _Key, typename _Tp, typename _Hash,
  570.            typename _Pred, typename _Alloc>
  571.     inline bool
  572.     operator!=(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
  573.                const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
  574.     { return !(__x == __y); }
  575.  
  576. } // namespace __profile
  577. } // namespace std
  578.  
  579. #undef _GLIBCXX_BASE
  580. #undef _GLIBCXX_STD_BASE
  581.  
  582. #endif // C++11
  583.  
  584. #endif
  585.