libstdc++
unordered_base.h
Go to the documentation of this file.
00001 // Profiling unordered containers implementation details -*- C++ -*-
00002 
00003 // Copyright (C) 2013-2015 Free Software Foundation, Inc.
00004 //
00005 // This file is part of the GNU ISO C++ Library.  This library is free
00006 // software; you can redistribute it and/or modify it under the
00007 // terms of the GNU General Public License as published by the
00008 // Free Software Foundation; either version 3, or (at your option)
00009 // any later version.
00010 //
00011 // This library is distributed in the hope that it will be useful,
00012 // but WITHOUT ANY WARRANTY; without even the implied warranty of
00013 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00014 // GNU General Public License for more details.
00015 
00016 // Under Section 7 of GPL version 3, you are granted additional
00017 // permissions described in the GCC Runtime Library Exception, version
00018 // 3.1, as published by the Free Software Foundation.
00019 
00020 // You should have received a copy of the GNU General Public License along
00021 // with this library; see the file COPYING3.  If not see
00022 // <http://www.gnu.org/licenses/>.
00023 
00024 /** @file profile/unordered_base.h
00025  *  This file is a GNU profile extension to the Standard C++ Library.
00026  */
00027 
00028 #ifndef _GLIBCXX_PROFILE_UNORDERED
00029 #define _GLIBCXX_PROFILE_UNORDERED 1
00030 
00031 namespace std _GLIBCXX_VISIBILITY(default)
00032 {
00033 namespace __profile
00034 {
00035   template<typename _UnorderedCont,
00036            typename _Value, bool _Cache_hash_code>
00037     struct _Bucket_index_helper;
00038 
00039   template<typename _UnorderedCont, typename _Value>
00040     struct _Bucket_index_helper<_UnorderedCont, _Value, true>
00041     {
00042       static std::size_t
00043       bucket(const _UnorderedCont& __uc,
00044              const __detail::_Hash_node<_Value, true>* __node)
00045       { return __node->_M_hash_code % __uc.bucket_count(); }
00046     };
00047 
00048   template<typename _UnorderedCont, typename _Value>
00049     struct _Bucket_index_helper<_UnorderedCont, _Value, false>
00050     {
00051       static std::size_t
00052       bucket(const _UnorderedCont& __uc,
00053              const __detail::_Hash_node<_Value, false>* __node)
00054       { return __uc.bucket(__node->_M_v()); }
00055     };
00056 
00057   template<typename _UnorderedCont, typename _Key, typename _Mapped>
00058     struct _Bucket_index_helper<_UnorderedCont,
00059                                 std::pair<const _Key, _Mapped>, false>
00060     {
00061       typedef std::pair<const _Key, _Mapped> _Value;
00062 
00063       static std::size_t
00064       bucket(const _UnorderedCont& __uc,
00065              const __detail::_Hash_node<_Value, false>* __node)
00066       { return __uc.bucket(__node->_M_v().first); }
00067     };
00068 
00069   template<typename _UnorderedCont, typename _Value, bool _Cache_hash_code>
00070     std::size_t
00071     __get_bucket_index(const _UnorderedCont& __uc,
00072                        const __detail::_Hash_node<_Value, _Cache_hash_code>* __node)
00073     {
00074       using __bucket_index_helper
00075         = _Bucket_index_helper<_UnorderedCont, _Value, _Cache_hash_code>;
00076       return __bucket_index_helper::bucket(__uc, __node);
00077     }
00078 
00079   template<typename _UnorderedCont,
00080            typename _Value, bool _Cache_hash_code>
00081     struct _Equal_helper;
00082 
00083   template<typename _UnorderedCont, typename _Value>
00084     struct _Equal_helper<_UnorderedCont, _Value, true>
00085     {
00086       static std::size_t
00087       are_equal(const _UnorderedCont& __uc,
00088                 const __detail::_Hash_node<_Value, true>* __lhs,
00089                 const __detail::_Hash_node<_Value, true>* __rhs)
00090       {
00091         return __lhs->_M_hash_code == __rhs->_M_hash_code
00092           && __uc.key_eq()(__lhs->_M_v(), __rhs->_M_v());
00093       }
00094     };
00095 
00096   template<typename _UnorderedCont,
00097            typename _Value>
00098     struct _Equal_helper<_UnorderedCont, _Value, false>
00099     {
00100       static std::size_t
00101       are_equal(const _UnorderedCont& __uc,
00102                 const __detail::_Hash_node<_Value, false>* __lhs,
00103                 const __detail::_Hash_node<_Value, false>* __rhs)
00104       { return __uc.key_eq()(__lhs->_M_v(), __rhs->_M_v()); }
00105     };
00106 
00107   template<typename _UnorderedCont,
00108            typename _Key, typename _Mapped>
00109     struct _Equal_helper<_UnorderedCont, std::pair<const _Key, _Mapped>, true>
00110     {
00111       typedef std::pair<const _Key, _Mapped> _Value;
00112 
00113       static std::size_t
00114       are_equal(const _UnorderedCont& __uc,
00115                 const __detail::_Hash_node<_Value, true>* __lhs,
00116                 const __detail::_Hash_node<_Value, true>* __rhs)
00117       {
00118         return __lhs->_M_hash_code == __rhs->_M_hash_code
00119           && __uc.key_eq()(__lhs->_M_v().first, __rhs->_M_v().first);
00120       }
00121     };
00122 
00123   template<typename _UnorderedCont,
00124            typename _Key, typename _Mapped>
00125     struct _Equal_helper<_UnorderedCont, std::pair<const _Key, _Mapped>, false>
00126     {
00127       typedef std::pair<const _Key, _Mapped> _Value;
00128 
00129       static std::size_t
00130       are_equal(const _UnorderedCont& __uc,
00131                 const __detail::_Hash_node<_Value, false>* __lhs,
00132                 const __detail::_Hash_node<_Value, false>* __rhs)
00133       { return __uc.key_eq()(__lhs->_M_v().first, __rhs->_M_v().first); }
00134     };
00135 
00136   template<typename _UnorderedCont, typename _Value, bool _Cache_hash_code>
00137     bool
00138     __are_equal(const _UnorderedCont& __uc,
00139                 const __detail::_Hash_node<_Value, _Cache_hash_code>* __lhs,
00140                 const __detail::_Hash_node<_Value, _Cache_hash_code>* __rhs)
00141   {
00142     using __equal_helper
00143       = _Equal_helper<_UnorderedCont, _Value, _Cache_hash_code>;
00144     return __equal_helper::are_equal(__uc, __lhs, __rhs);
00145   }
00146 
00147   template<typename _UnorderedCont, bool _Unique_keys>
00148     class _Unordered_profile
00149     {
00150       _UnorderedCont&
00151       _M_conjure()
00152       { return *(static_cast<_UnorderedCont*>(this)); }
00153 
00154       using __unique_keys = std::integral_constant<bool, _Unique_keys>;
00155 
00156     protected:
00157       _Unordered_profile() noexcept
00158       { _M_profile_construct(); }
00159 
00160       _Unordered_profile(const _Unordered_profile&) noexcept
00161         : _Unordered_profile() { }
00162 
00163       _Unordered_profile(_Unordered_profile&& __other) noexcept
00164         : _Unordered_profile()
00165       { _M_swap(__other); }
00166 
00167       ~_Unordered_profile()
00168       { _M_profile_destruct(); }
00169 
00170       _Unordered_profile&
00171       operator=(const _Unordered_profile&) noexcept
00172       {
00173         // Assignment just reset profiling.
00174         _M_profile_destruct();
00175         _M_profile_construct();
00176       }
00177 
00178       _Unordered_profile&
00179       operator=(_Unordered_profile&& __other) noexcept
00180       {
00181         // Take profiling of the moved instance...
00182         _M_swap(__other);
00183 
00184         // ...and then reset other instance profiling.
00185         __other._M_profile_destruct();
00186         __other._M_profile_construct();
00187       }
00188 
00189       void
00190       _M_profile_construct() noexcept
00191       {
00192         auto& __uc = _M_conjure();
00193         _M_size_info = __profcxx_hashtable_size_construct(__uc.bucket_count());
00194         _M_hashfunc_info = __profcxx_hash_func_construct();
00195       }
00196 
00197       void
00198       _M_profile_destruct() noexcept
00199       {
00200         auto& __uc = _M_conjure();
00201         __profcxx_hashtable_size_destruct(_M_size_info,
00202                                           __uc.bucket_count(), __uc.size());
00203         _M_size_info = 0;
00204 
00205         if (!_M_hashfunc_info)
00206           return;
00207 
00208         _M_profile_destruct(__unique_keys());
00209         _M_hashfunc_info = 0;
00210       }
00211 
00212       void
00213       _M_swap(_Unordered_profile& __other) noexcept
00214       {
00215         std::swap(_M_size_info, __other._M_size_info);
00216         std::swap(_M_hashfunc_info, __other._M_hashfunc_info);
00217       }
00218 
00219       void
00220       _M_profile_resize(std::size_t __old_size)
00221       {
00222         auto __new_size = _M_conjure().bucket_count();
00223         if (__old_size != __new_size)
00224           __profcxx_hashtable_size_resize(_M_size_info, __old_size, __new_size);
00225       }
00226 
00227       __gnu_profile::__container_size_info* _M_size_info;
00228       __gnu_profile::__hashfunc_info* _M_hashfunc_info;
00229 
00230     private:
00231       void
00232       _M_profile_destruct(std::true_type);
00233 
00234       void
00235       _M_profile_destruct(std::false_type);
00236     };
00237 
00238   template<typename _UnorderedCont, bool _Unique_keys>
00239     void
00240     _Unordered_profile<_UnorderedCont, _Unique_keys>::
00241     _M_profile_destruct(std::true_type)
00242     {
00243       auto& __uc = _M_conjure();
00244       std::size_t __hops = 0, __lc = 0, __chain = 0;
00245       auto __it = __uc.begin();
00246       while (__it != __uc.end())
00247         {
00248           auto __bkt = __get_bucket_index(__uc, __it._M_cur);
00249           auto __lit = __uc.begin(__bkt);
00250           auto __lend = __uc.end(__bkt);
00251           for (++__it, ++__lit; __lit != __lend; ++__it, ++__lit)
00252             ++__chain;
00253 
00254           if (__chain)
00255             {
00256               ++__chain;
00257               __lc = __lc > __chain ? __lc : __chain;
00258               __hops += __chain * (__chain - 1) / 2;
00259               __chain = 0;
00260             }
00261         }
00262 
00263       __profcxx_hash_func_destruct(_M_hashfunc_info,
00264                                    __lc, __uc.size(), __hops);
00265     }
00266 
00267   template<typename _UnorderedCont, bool _Unique_keys>
00268     void
00269     _Unordered_profile<_UnorderedCont, _Unique_keys>::
00270     _M_profile_destruct(std::false_type)
00271     {
00272       auto& __uc = _M_conjure();
00273       std::size_t __hops = 0, __lc = 0, __chain = 0, __unique_size = 0;
00274       auto __it = __uc.begin();
00275       while (__it != __uc.end())
00276         {
00277           auto __bkt = __get_bucket_index(__uc, __it._M_cur);
00278           auto __lit = __uc.begin(__bkt);
00279           auto __lend = __uc.end(__bkt);
00280           auto __pit = __it;
00281           ++__unique_size;
00282           for (++__it, ++__lit; __lit != __lend; ++__it, ++__lit)
00283             {
00284               if (!__are_equal(__uc, __pit._M_cur, __it._M_cur))
00285                 {
00286                   ++__chain;
00287                   ++__unique_size;
00288                   __pit = __it;
00289                 }
00290             }
00291 
00292           if (__chain)
00293             {
00294               ++__chain;
00295               __lc = __lc > __chain ? __lc : __chain;
00296               __hops += __chain * (__chain - 1) / 2;
00297               __chain = 0;
00298             }
00299         }
00300 
00301       __profcxx_hash_func_destruct(_M_hashfunc_info,
00302                                    __lc, __unique_size, __hops);
00303     }
00304 
00305 } // namespace __profile
00306 } // namespace std
00307 
00308 #endif