1 // Profiling unordered containers implementation details -*- C++ -*-
3 // Copyright (C) 2013-2015 Free Software Foundation, Inc.
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)
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.
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.
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/>.
24 /** @file profile/unordered_base.h
25 * This file is a GNU profile extension to the Standard C++ Library.
28 #ifndef _GLIBCXX_PROFILE_UNORDERED
29 #define _GLIBCXX_PROFILE_UNORDERED 1
31 namespace std
_GLIBCXX_VISIBILITY(default)
35 template<typename _UnorderedCont
,
36 typename _Value
, bool _Cache_hash_code
>
37 struct _Bucket_index_helper
;
39 template<typename _UnorderedCont
, typename _Value
>
40 struct _Bucket_index_helper
<_UnorderedCont
, _Value
, true>
43 bucket(const _UnorderedCont
& __uc
,
44 const __detail::_Hash_node
<_Value
, true>* __node
)
45 { return __node
->_M_hash_code
% __uc
.bucket_count(); }
48 template<typename _UnorderedCont
, typename _Value
>
49 struct _Bucket_index_helper
<_UnorderedCont
, _Value
, false>
52 bucket(const _UnorderedCont
& __uc
,
53 const __detail::_Hash_node
<_Value
, false>* __node
)
54 { return __uc
.bucket(__node
->_M_v()); }
57 template<typename _UnorderedCont
, typename _Key
, typename _Mapped
>
58 struct _Bucket_index_helper
<_UnorderedCont
,
59 std::pair
<const _Key
, _Mapped
>, false>
61 typedef std::pair
<const _Key
, _Mapped
> _Value
;
64 bucket(const _UnorderedCont
& __uc
,
65 const __detail::_Hash_node
<_Value
, false>* __node
)
66 { return __uc
.bucket(__node
->_M_v().first
); }
69 template<typename _UnorderedCont
, typename _Value
, bool _Cache_hash_code
>
71 __get_bucket_index(const _UnorderedCont
& __uc
,
72 const __detail::_Hash_node
<_Value
, _Cache_hash_code
>* __node
)
74 using __bucket_index_helper
75 = _Bucket_index_helper
<_UnorderedCont
, _Value
, _Cache_hash_code
>;
76 return __bucket_index_helper::bucket(__uc
, __node
);
79 template<typename _UnorderedCont
,
80 typename _Value
, bool _Cache_hash_code
>
83 template<typename _UnorderedCont
, typename _Value
>
84 struct _Equal_helper
<_UnorderedCont
, _Value
, true>
87 are_equal(const _UnorderedCont
& __uc
,
88 const __detail::_Hash_node
<_Value
, true>* __lhs
,
89 const __detail::_Hash_node
<_Value
, true>* __rhs
)
91 return __lhs
->_M_hash_code
== __rhs
->_M_hash_code
92 && __uc
.key_eq()(__lhs
->_M_v(), __rhs
->_M_v());
96 template<typename _UnorderedCont
,
98 struct _Equal_helper
<_UnorderedCont
, _Value
, false>
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()); }
107 template<typename _UnorderedCont
,
108 typename _Key
, typename _Mapped
>
109 struct _Equal_helper
<_UnorderedCont
, std::pair
<const _Key
, _Mapped
>, true>
111 typedef std::pair
<const _Key
, _Mapped
> _Value
;
114 are_equal(const _UnorderedCont
& __uc
,
115 const __detail::_Hash_node
<_Value
, true>* __lhs
,
116 const __detail::_Hash_node
<_Value
, true>* __rhs
)
118 return __lhs
->_M_hash_code
== __rhs
->_M_hash_code
119 && __uc
.key_eq()(__lhs
->_M_v().first
, __rhs
->_M_v().first
);
123 template<typename _UnorderedCont
,
124 typename _Key
, typename _Mapped
>
125 struct _Equal_helper
<_UnorderedCont
, std::pair
<const _Key
, _Mapped
>, false>
127 typedef std::pair
<const _Key
, _Mapped
> _Value
;
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
); }
136 template<typename _UnorderedCont
, typename _Value
, bool _Cache_hash_code
>
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
)
143 = _Equal_helper
<_UnorderedCont
, _Value
, _Cache_hash_code
>;
144 return __equal_helper::are_equal(__uc
, __lhs
, __rhs
);
147 template<typename _UnorderedCont
, bool _Unique_keys
>
148 class _Unordered_profile
152 { return *(static_cast<_UnorderedCont
*>(this)); }
154 using __unique_keys
= std::integral_constant
<bool, _Unique_keys
>;
157 _Unordered_profile() noexcept
158 { _M_profile_construct(); }
160 _Unordered_profile(const _Unordered_profile
&) noexcept
161 : _Unordered_profile() { }
163 _Unordered_profile(_Unordered_profile
&& __other
) noexcept
164 : _Unordered_profile()
165 { _M_swap(__other
); }
167 ~_Unordered_profile()
168 { _M_profile_destruct(); }
171 operator=(const _Unordered_profile
&) noexcept
173 // Assignment just reset profiling.
174 _M_profile_destruct();
175 _M_profile_construct();
179 operator=(_Unordered_profile
&& __other
) noexcept
181 // Take profiling of the moved instance...
184 // ...and then reset other instance profiling.
185 __other
._M_profile_destruct();
186 __other
._M_profile_construct();
190 _M_profile_construct() noexcept
192 auto& __uc
= _M_conjure();
193 _M_size_info
= __profcxx_hashtable_size_construct(__uc
.bucket_count());
194 _M_hashfunc_info
= __profcxx_hash_func_construct();
198 _M_profile_destruct() noexcept
200 auto& __uc
= _M_conjure();
201 __profcxx_hashtable_size_destruct(_M_size_info
,
202 __uc
.bucket_count(), __uc
.size());
205 if (!_M_hashfunc_info
)
208 _M_profile_destruct(__unique_keys());
209 _M_hashfunc_info
= 0;
213 _M_swap(_Unordered_profile
& __other
) noexcept
215 std::swap(_M_size_info
, __other
._M_size_info
);
216 std::swap(_M_hashfunc_info
, __other
._M_hashfunc_info
);
220 _M_profile_resize(std::size_t __old_size
)
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
);
227 __gnu_profile::__container_size_info
* _M_size_info
;
228 __gnu_profile::__hashfunc_info
* _M_hashfunc_info
;
232 _M_profile_destruct(std::true_type
);
235 _M_profile_destruct(std::false_type
);
238 template<typename _UnorderedCont
, bool _Unique_keys
>
240 _Unordered_profile
<_UnorderedCont
, _Unique_keys
>::
241 _M_profile_destruct(std::true_type
)
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())
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
)
257 __lc
= __lc
> __chain
? __lc
: __chain
;
258 __hops
+= __chain
* (__chain
- 1) / 2;
263 __profcxx_hash_func_destruct(_M_hashfunc_info
,
264 __lc
, __uc
.size(), __hops
);
267 template<typename _UnorderedCont
, bool _Unique_keys
>
269 _Unordered_profile
<_UnorderedCont
, _Unique_keys
>::
270 _M_profile_destruct(std::false_type
)
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())
277 auto __bkt
= __get_bucket_index(__uc
, __it
._M_cur
);
278 auto __lit
= __uc
.begin(__bkt
);
279 auto __lend
= __uc
.end(__bkt
);
282 for (++__it
, ++__lit
; __lit
!= __lend
; ++__it
, ++__lit
)
284 if (!__are_equal(__uc
, __pit
._M_cur
, __it
._M_cur
))
295 __lc
= __lc
> __chain
? __lc
: __chain
;
296 __hops
+= __chain
* (__chain
- 1) / 2;
301 __profcxx_hash_func_destruct(_M_hashfunc_info
,
302 __lc
, __unique_size
, __hops
);
305 } // namespace __profile