libstdc++
unordered_base.h
Go to the documentation of this file.
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 
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
A hash performance instrumentation line in the object table.
integral_constant
Definition: type_traits:69
A container size instrumentation line in the object table.
Struct holding two objects of arbitrary type.
Definition: stl_pair.h:96
ISO C++ entities toplevel namespace is std.