1 // Profiling unordered containers implementation details -*- C++ -*-
2
3 // Copyright (C) 2013-2018 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
_GLIBCXX_VISIBILITY(default)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
309