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 
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