libstdc++-v3/include/profile/unordered_base.h

   1 // Profiling unordered containers implementation details -*- C++ -*-
   2
   3 // Copyright (C) 2013-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_base.h
  25  *  This file is a GNU profile extension to the Standard C++ Library.
  26  */
  27
  28 #ifndef _GLIBCXX_PROFILE_UNORDERED
  29 #define _GLIBCXX_PROFILE_UNORDERED 1
  30
  31 namespace std _GLIBCXX_VISIBILITY(default)
  32 {
  33 namespace __profile
  34 {
  35   template<typename _UnorderedCont,
  36            typename _Value, bool _Cache_hash_code>
  37     struct _Bucket_index_helper;
  38
  39   template<typename _UnorderedCont, typename _Value>
  40     struct _Bucket_index_helper<_UnorderedCont, _Value, true>
  41     {
  42       static std::size_t
  43       bucket(const _UnorderedCont& __uc,
  44              const __detail::_Hash_node<_Value, true>* __node)
  45       { return __node->_M_hash_code % __uc.bucket_count(); }
  46     };
  47
  48   template<typename _UnorderedCont, typename _Value>
  49     struct _Bucket_index_helper<_UnorderedCont, _Value, false>
  50     {
  51       static std::size_t
  52       bucket(const _UnorderedCont& __uc,
  53              const __detail::_Hash_node<_Value, false>* __node)
  54       { return __uc.bucket(__node->_M_v()); }
  55     };
  56
  57   template<typename _UnorderedCont, typename _Key, typename _Mapped>
  58     struct _Bucket_index_helper<_UnorderedCont,
  59                                 std::pair<const _Key, _Mapped>, false>
  60     {
  61       typedef std::pair<const _Key, _Mapped> _Value;
  62
  63       static std::size_t
  64       bucket(const _UnorderedCont& __uc,
  65              const __detail::_Hash_node<_Value, false>* __node)
  66       { return __uc.bucket(__node->_M_v().first); }
  67     };
  68
  69   template<typename _UnorderedCont, typename _Value, bool _Cache_hash_code>
  70     std::size_t
  71     __get_bucket_index(const _UnorderedCont& __uc,
  72                        const __detail::_Hash_node<_Value, _Cache_hash_code>* __node)
  73     {
  74       using __bucket_index_helper
  75         = _Bucket_index_helper<_UnorderedCont, _Value, _Cache_hash_code>;
  76       return __bucket_index_helper::bucket(__uc, __node);
  77     }
  78
  79   template<typename _UnorderedCont,
  80            typename _Value, bool _Cache_hash_code>
  81     struct _Equal_helper;
  82
  83   template<typename _UnorderedCont, typename _Value>
  84     struct _Equal_helper<_UnorderedCont, _Value, true>
  85     {
  86       static std::size_t
  87       are_equal(const _UnorderedCont& __uc,
  88                 const __detail::_Hash_node<_Value, true>* __lhs,
  89                 const __detail::_Hash_node<_Value, true>* __rhs)
  90       {
  91         return __lhs->_M_hash_code == __rhs->_M_hash_code
  92           && __uc.key_eq()(__lhs->_M_v(), __rhs->_M_v());
  93       }
  94     };
  95
  96   template<typename _UnorderedCont,
  97            typename _Value>
  98     struct _Equal_helper<_UnorderedCont, _Value, false>
  99     {
 100       static std::size_t
 101       are_equal(const _UnorderedCont& __uc,
 102                 const __detail::_Hash_node<_Value, false>* __lhs,
 103                 const __detail::_Hash_node<_Value, false>* __rhs)
 104       { return __uc.key_eq()(__lhs->_M_v(), __rhs->_M_v()); }
 105     };
 106
 107   template<typename _UnorderedCont,
 108            typename _Key, typename _Mapped>
 109     struct _Equal_helper<_UnorderedCont, std::pair<const _Key, _Mapped>, true>
 110     {
 111       typedef std::pair<const _Key, _Mapped> _Value;
 112
 113       static std::size_t
 114       are_equal(const _UnorderedCont& __uc,
 115                 const __detail::_Hash_node<_Value, true>* __lhs,
 116                 const __detail::_Hash_node<_Value, true>* __rhs)
 117       {
 118         return __lhs->_M_hash_code == __rhs->_M_hash_code
 119           && __uc.key_eq()(__lhs->_M_v().first, __rhs->_M_v().first);
 120       }
 121     };
 122
 123   template<typename _UnorderedCont,
 124            typename _Key, typename _Mapped>
 125     struct _Equal_helper<_UnorderedCont, std::pair<const _Key, _Mapped>, false>
 126     {
 127       typedef std::pair<const _Key, _Mapped> _Value;
 128
 129       static std::size_t
 130       are_equal(const _UnorderedCont& __uc,
 131                 const __detail::_Hash_node<_Value, false>* __lhs,
 132                 const __detail::_Hash_node<_Value, false>* __rhs)
 133       { return __uc.key_eq()(__lhs->_M_v().first, __rhs->_M_v().first); }
 134     };
 135
 136   template<typename _UnorderedCont, typename _Value, bool _Cache_hash_code>
 137     bool
 138     __are_equal(const _UnorderedCont& __uc,
 139                 const __detail::_Hash_node<_Value, _Cache_hash_code>* __lhs,
 140                 const __detail::_Hash_node<_Value, _Cache_hash_code>* __rhs)
 141   {
 142     using __equal_helper
 143       = _Equal_helper<_UnorderedCont, _Value, _Cache_hash_code>;
 144     return __equal_helper::are_equal(__uc, __lhs, __rhs);
 145   }
 146
 147   template<typename _UnorderedCont, bool _Unique_keys>
 148     class _Unordered_profile
 149     {
 150       _UnorderedCont&
 151       _M_conjure()
 152       { return *(static_cast<_UnorderedCont*>(this)); }
 153
 154       using __unique_keys = std::integral_constant<bool, _Unique_keys>;
 155
 156     protected:
 157       _Unordered_profile() noexcept
 158       { _M_profile_construct(); }
 159
 160       _Unordered_profile(const _Unordered_profile&) noexcept
 161         : _Unordered_profile() { }
 162
 163       _Unordered_profile(_Unordered_profile&& __other) noexcept
 164         : _Unordered_profile()
 165       { _M_swap(__other); }
 166
 167       ~_Unordered_profile()
 168       { _M_profile_destruct(); }
 169
 170       _Unordered_profile&
 171       operator=(const _Unordered_profile&) noexcept
 172       {
 173         // Assignment just reset profiling.
 174         _M_profile_destruct();
 175         _M_profile_construct();
 176       }
 177
 178       _Unordered_profile&
 179       operator=(_Unordered_profile&& __other) noexcept
 180       {
 181         // Take profiling of the moved instance...
 182         _M_swap(__other);
 183
 184         // ...and then reset other instance profiling.
 185         __other._M_profile_destruct();
 186         __other._M_profile_construct();
 187       }
 188
 189       void
 190       _M_profile_construct() noexcept
 191       {
 192         auto& __uc = _M_conjure();
 193         _M_size_info = __profcxx_hashtable_size_construct(__uc.bucket_count());
 194         _M_hashfunc_info = __profcxx_hash_func_construct();
 195       }
 196
 197       void
 198       _M_profile_destruct() noexcept
 199       {
 200         auto& __uc = _M_conjure();
 201         __profcxx_hashtable_size_destruct(_M_size_info,
 202                                           __uc.bucket_count(), __uc.size());
 203         _M_size_info = 0;
 204
 205         if (!_M_hashfunc_info)
 206           return;
 207
 208         _M_profile_destruct(__unique_keys());
 209         _M_hashfunc_info = 0;
 210       }
 211
 212       void
 213       _M_swap(_Unordered_profile& __other) noexcept
 214       {
 215         std::swap(_M_size_info, __other._M_size_info);
 216         std::swap(_M_hashfunc_info, __other._M_hashfunc_info);
 217       }
 218
 219       void
 220       _M_profile_resize(std::size_t __old_size)
 221       {
 222         auto __new_size = _M_conjure().bucket_count();
 223         if (__old_size != __new_size)
 224           __profcxx_hashtable_size_resize(_M_size_info, __old_size, __new_size);
 225       }
 226
 227       __gnu_profile::__container_size_info* _M_size_info;
 228       __gnu_profile::__hashfunc_info* _M_hashfunc_info;
 229
 230     private:
 231       void
 232       _M_profile_destruct(std::true_type);
 233
 234       void
 235       _M_profile_destruct(std::false_type);
 236     };
 237
 238   template<typename _UnorderedCont, bool _Unique_keys>
 239     void
 240     _Unordered_profile<_UnorderedCont, _Unique_keys>::
 241     _M_profile_destruct(std::true_type)
 242     {
 243       auto& __uc = _M_conjure();
 244       std::size_t __hops = 0, __lc = 0, __chain = 0;
 245       auto __it = __uc.begin();
 246       while (__it != __uc.end())
 247         {
 248           auto __bkt = __get_bucket_index(__uc, __it._M_cur);
 249           auto __lit = __uc.begin(__bkt);
 250           auto __lend = __uc.end(__bkt);
 251           for (++__it, ++__lit; __lit != __lend; ++__it, ++__lit)
 252             ++__chain;
 253
 254           if (__chain)
 255             {
 256               ++__chain;
 257               __lc = __lc > __chain ? __lc : __chain;
 258               __hops += __chain * (__chain - 1) / 2;
 259               __chain = 0;
 260             }
 261         }
 262
 263       __profcxx_hash_func_destruct(_M_hashfunc_info,
 264                                    __lc, __uc.size(), __hops);
 265     }
 266
 267   template<typename _UnorderedCont, bool _Unique_keys>
 268     void
 269     _Unordered_profile<_UnorderedCont, _Unique_keys>::
 270     _M_profile_destruct(std::false_type)
 271     {
 272       auto& __uc = _M_conjure();
 273       std::size_t __hops = 0, __lc = 0, __chain = 0, __unique_size = 0;
 274       auto __it = __uc.begin();
 275       while (__it != __uc.end())
 276         {
 277           auto __bkt = __get_bucket_index(__uc, __it._M_cur);
 278           auto __lit = __uc.begin(__bkt);
 279           auto __lend = __uc.end(__bkt);
 280           auto __pit = __it;
 281           ++__unique_size;
 282           for (++__it, ++__lit; __lit != __lend; ++__it, ++__lit)
 283             {
 284               if (!__are_equal(__uc, __pit._M_cur, __it._M_cur))
 285                 {
 286                   ++__chain;
 287                   ++__unique_size;
 288                   __pit = __it;
 289                 }
 290             }
 291
 292           if (__chain)
 293             {
 294               ++__chain;
 295               __lc = __lc > __chain ? __lc : __chain;
 296               __hops += __chain * (__chain - 1) / 2;
 297               __chain = 0;
 298             }
 299         }
 300
 301       __profcxx_hash_func_destruct(_M_hashfunc_info,
 302                                    __lc, __unique_size, __hops);
 303     }
 304
 305 } // namespace __profile
 306 } // namespace std
 307
 308 #endif