]>
Commit | Line | Data |
---|---|---|
c50ff294 | 1 | // Profiling unordered containers implementation details -*- C++ -*- |
2 | ||
f1717362 | 3 | // Copyright (C) 2013-2016 Free Software Foundation, Inc. |
c50ff294 | 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: | |
1675d1be | 157 | _Unordered_profile() noexcept |
158 | { _M_profile_construct(); } | |
159 | ||
160 | _Unordered_profile(const _Unordered_profile&) noexcept | |
c50ff294 | 161 | : _Unordered_profile() { } |
162 | ||
1675d1be | 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 | |
c50ff294 | 172 | { |
1675d1be | 173 | // Assignment just reset profiling. |
5f70fed5 | 174 | _M_profile_destruct(); |
1675d1be | 175 | _M_profile_construct(); |
c50ff294 | 176 | } |
177 | ||
178 | _Unordered_profile& | |
1675d1be | 179 | operator=(_Unordered_profile&& __other) noexcept |
180 | { | |
181 | // Take profiling of the moved instance... | |
182 | _M_swap(__other); | |
c50ff294 | 183 | |
1675d1be | 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 | } | |
c50ff294 | 196 | |
197 | void | |
1675d1be | 198 | _M_profile_destruct() noexcept |
c50ff294 | 199 | { |
1675d1be | 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) | |
c50ff294 | 206 | return; |
207 | ||
208 | _M_profile_destruct(__unique_keys()); | |
1675d1be | 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); | |
c50ff294 | 217 | } |
218 | ||
1675d1be | 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 | ||
c50ff294 | 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; | |
5f70fed5 | 253 | |
c50ff294 | 254 | if (__chain) |
255 | { | |
256 | ++__chain; | |
257 | __lc = __lc > __chain ? __lc : __chain; | |
258 | __hops += __chain * (__chain - 1) / 2; | |
259 | __chain = 0; | |
260 | } | |
261 | } | |
1675d1be | 262 | |
263 | __profcxx_hash_func_destruct(_M_hashfunc_info, | |
264 | __lc, __uc.size(), __hops); | |
c50ff294 | 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 | } | |
5f70fed5 | 291 | |
c50ff294 | 292 | if (__chain) |
293 | { | |
294 | ++__chain; | |
295 | __lc = __lc > __chain ? __lc : __chain; | |
296 | __hops += __chain * (__chain - 1) / 2; | |
297 | __chain = 0; | |
298 | } | |
299 | } | |
1675d1be | 300 | |
301 | __profcxx_hash_func_destruct(_M_hashfunc_info, | |
302 | __lc, __unique_size, __hops); | |
c50ff294 | 303 | } |
304 | ||
305 | } // namespace __profile | |
306 | } // namespace std | |
307 | ||
308 | #endif |