1 // Profiling unordered containers implementation details -*- C++ -*-
3 // Copyright (C) 2013 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
>;
159 auto& __uc
= _M_conjure();
160 __profcxx_hashtable_construct(&__uc
, __uc
.bucket_count());
161 __profcxx_hashtable_construct2(&__uc
);
163 _Unordered_profile(const _Unordered_profile
&)
164 : _Unordered_profile() { }
165 _Unordered_profile(_Unordered_profile
&&)
166 : _Unordered_profile() { }
168 ~_Unordered_profile() noexcept
170 auto& __uc
= _M_conjure();
171 __profcxx_hashtable_destruct(&__uc
, __uc
.bucket_count(), __uc
.size());
172 _M_profile_destruct();
176 operator=(const _Unordered_profile
&) = default;
179 operator=(_Unordered_profile
&&) = default;
182 _M_profile_destruct()
184 if (!__profcxx_inefficient_hash_is_on())
187 _M_profile_destruct(__unique_keys());
192 _M_profile_destruct(std::true_type
);
195 _M_profile_destruct(std::false_type
);
198 template<typename _UnorderedCont
, bool _Unique_keys
>
200 _Unordered_profile
<_UnorderedCont
, _Unique_keys
>::
201 _M_profile_destruct(std::true_type
)
203 auto& __uc
= _M_conjure();
204 std::size_t __hops
= 0, __lc
= 0, __chain
= 0;
205 auto __it
= __uc
.begin();
206 while (__it
!= __uc
.end())
208 auto __bkt
= __get_bucket_index(__uc
, __it
._M_cur
);
209 auto __lit
= __uc
.begin(__bkt
);
210 auto __lend
= __uc
.end(__bkt
);
211 for (++__it
, ++__lit
; __lit
!= __lend
; ++__it
, ++__lit
)
216 __lc
= __lc
> __chain
? __lc
: __chain
;
217 __hops
+= __chain
* (__chain
- 1) / 2;
221 __profcxx_hashtable_destruct2(&__uc
, __lc
, __uc
.size(), __hops
);
224 template<typename _UnorderedCont
, bool _Unique_keys
>
226 _Unordered_profile
<_UnorderedCont
, _Unique_keys
>::
227 _M_profile_destruct(std::false_type
)
229 auto& __uc
= _M_conjure();
230 std::size_t __hops
= 0, __lc
= 0, __chain
= 0, __unique_size
= 0;
231 auto __it
= __uc
.begin();
232 while (__it
!= __uc
.end())
234 auto __bkt
= __get_bucket_index(__uc
, __it
._M_cur
);
235 auto __lit
= __uc
.begin(__bkt
);
236 auto __lend
= __uc
.end(__bkt
);
239 for (++__it
, ++__lit
; __lit
!= __lend
; ++__it
, ++__lit
)
241 if (!__are_equal(__uc
, __pit
._M_cur
, __it
._M_cur
))
251 __lc
= __lc
> __chain
? __lc
: __chain
;
252 __hops
+= __chain
* (__chain
- 1) / 2;
256 __profcxx_hashtable_destruct2(&__uc
, __lc
, __unique_size
, __hops
);
259 } // namespace __profile