]>
Commit | Line | Data |
---|---|---|
3b2524b1 PC |
1 | // Internal policy header for unordered_set and unordered_map -*- C++ -*- |
2 | ||
346afd84 | 3 | // Copyright (C) 2010, 2011, 2012 Free Software Foundation, Inc. |
3b2524b1 PC |
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 and | |
21 | // a copy of the GCC Runtime Library Exception along with this program; | |
22 | // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see | |
23 | // <http://www.gnu.org/licenses/>. | |
24 | ||
25 | /** @file bits/hashtable_policy.h | |
26 | * This is an internal header file, included by other library headers. | |
7c3e9502 | 27 | * Do not attempt to use it directly. |
f910786b | 28 | * @headername{unordered_map,unordered_set} |
3b2524b1 PC |
29 | */ |
30 | ||
31 | #ifndef _HASHTABLE_POLICY_H | |
32 | #define _HASHTABLE_POLICY_H 1 | |
33 | ||
12ffa228 BK |
34 | namespace std _GLIBCXX_VISIBILITY(default) |
35 | { | |
4dad8b49 BK |
36 | template<typename _Key, typename _Value, typename _Alloc, |
37 | typename _ExtractKey, typename _Equal, | |
38 | typename _H1, typename _H2, typename _Hash, | |
39 | typename _RehashPolicy, typename _Traits> | |
40 | class _Hashtable; | |
41 | ||
3b2524b1 PC |
42 | namespace __detail |
43 | { | |
12ffa228 BK |
44 | _GLIBCXX_BEGIN_NAMESPACE_VERSION |
45 | ||
4dad8b49 BK |
46 | /** |
47 | * @defgroup hashtable-detail Base and Implementation Classes | |
48 | * @ingroup unordered_associative_containers | |
49 | * @{ | |
50 | */ | |
51 | template<typename _Key, typename _Value, | |
52 | typename _ExtractKey, typename _Equal, | |
53 | typename _H1, typename _H2, typename _Hash, typename _Traits> | |
54 | struct _Hashtable_base; | |
55 | ||
3b2524b1 PC |
56 | // Helper function: return distance(first, last) for forward |
57 | // iterators, or 0 for input iterators. | |
58 | template<class _Iterator> | |
59 | inline typename std::iterator_traits<_Iterator>::difference_type | |
60 | __distance_fw(_Iterator __first, _Iterator __last, | |
61 | std::input_iterator_tag) | |
62 | { return 0; } | |
63 | ||
64 | template<class _Iterator> | |
65 | inline typename std::iterator_traits<_Iterator>::difference_type | |
66 | __distance_fw(_Iterator __first, _Iterator __last, | |
67 | std::forward_iterator_tag) | |
68 | { return std::distance(__first, __last); } | |
69 | ||
70 | template<class _Iterator> | |
71 | inline typename std::iterator_traits<_Iterator>::difference_type | |
72 | __distance_fw(_Iterator __first, _Iterator __last) | |
73 | { | |
74 | typedef typename std::iterator_traits<_Iterator>::iterator_category _Tag; | |
75 | return __distance_fw(__first, __last, _Tag()); | |
76 | } | |
77 | ||
da29608a FD |
78 | // Helper type used to detect when the hash functor is noexcept qualified or |
79 | // not | |
80 | template <typename _Key, typename _Hash> | |
81 | struct __is_noexcept_hash : std::integral_constant<bool, | |
82 | noexcept(declval<const _Hash&>()(declval<const _Key&>()))> | |
4dad8b49 | 83 | { }; |
da29608a | 84 | |
4dad8b49 | 85 | // Auxiliary types used for all instantiations of _Hashtable nodes |
3b2524b1 | 86 | // and iterators. |
7c3e9502 | 87 | |
4dad8b49 BK |
88 | /** |
89 | * struct _Hashtable_traits | |
90 | * | |
91 | * Important traits for hash tables. | |
92 | * | |
93 | * @tparam __cache_hash_code Boolean value. True if the value of | |
94 | * the hash function is stored along with the value. This is a | |
95 | * time-space tradeoff. Storing it may improve lookup speed by | |
96 | * reducing the number of times we need to call the _Equal | |
97 | * function. | |
98 | * | |
99 | * @tparam __constant_iterators Boolean value. True if iterator and | |
100 | * const_iterator are both constant iterator types. This is true | |
101 | * for unordered_set and unordered_multiset, false for | |
102 | * unordered_map and unordered_multimap. | |
103 | * | |
104 | * @tparam __unique_keys Boolean value. True if the return value | |
105 | * of _Hashtable::count(k) is always at most one, false if it may | |
106 | * be an arbitrary number. This true for unordered_set and | |
107 | * unordered_map, false for unordered_multiset and | |
108 | * unordered_multimap. | |
109 | */ | |
110 | template<bool _Cache_hash_code, bool _Constant_iterators, bool _Unique_keys> | |
111 | struct _Hashtable_traits | |
112 | { | |
113 | template<bool _Cond> | |
114 | using __bool_constant = integral_constant<bool, _Cond>; | |
115 | ||
116 | using __hash_cached = __bool_constant<_Cache_hash_code>; | |
117 | using __constant_iterators = __bool_constant<_Constant_iterators>; | |
118 | using __unique_keys = __bool_constant<_Unique_keys>; | |
119 | }; | |
120 | ||
121 | /** | |
122 | * struct _Hash_node_base | |
123 | * | |
124 | * Nodes, used to wrap elements stored in the hash table. A policy | |
125 | * template parameter of class template _Hashtable controls whether | |
126 | * nodes also store a hash code. In some cases (e.g. strings) this | |
127 | * may be a performance win. | |
128 | */ | |
f86b266c FD |
129 | struct _Hash_node_base |
130 | { | |
131 | _Hash_node_base* _M_nxt; | |
132 | ||
4dad8b49 BK |
133 | _Hash_node_base() : _M_nxt() { } |
134 | ||
135 | _Hash_node_base(_Hash_node_base* __next) : _M_nxt(__next) { } | |
f86b266c FD |
136 | }; |
137 | ||
4dad8b49 BK |
138 | /** |
139 | * Primary template struct _Hash_node. | |
140 | */ | |
141 | template<typename _Value, bool _Cache_hash_code> | |
3b2524b1 PC |
142 | struct _Hash_node; |
143 | ||
4dad8b49 | 144 | /// Specialization. |
3b2524b1 | 145 | template<typename _Value> |
f86b266c | 146 | struct _Hash_node<_Value, true> : _Hash_node_base |
3b2524b1 PC |
147 | { |
148 | _Value _M_v; | |
149 | std::size_t _M_hash_code; | |
3b2524b1 PC |
150 | |
151 | template<typename... _Args> | |
7c3e9502 | 152 | _Hash_node(_Args&&... __args) |
f86b266c FD |
153 | : _M_v(std::forward<_Args>(__args)...), _M_hash_code() { } |
154 | ||
4dad8b49 BK |
155 | _Hash_node* |
156 | _M_next() const { return static_cast<_Hash_node*>(_M_nxt); } | |
3b2524b1 PC |
157 | }; |
158 | ||
4dad8b49 | 159 | /// Specialization. |
3b2524b1 | 160 | template<typename _Value> |
f86b266c | 161 | struct _Hash_node<_Value, false> : _Hash_node_base |
3b2524b1 PC |
162 | { |
163 | _Value _M_v; | |
3b2524b1 PC |
164 | |
165 | template<typename... _Args> | |
7c3e9502 | 166 | _Hash_node(_Args&&... __args) |
f86b266c FD |
167 | : _M_v(std::forward<_Args>(__args)...) { } |
168 | ||
4dad8b49 BK |
169 | _Hash_node* |
170 | _M_next() const { return static_cast<_Hash_node*>(_M_nxt); } | |
3b2524b1 PC |
171 | }; |
172 | ||
4dad8b49 BK |
173 | /// Base class for node iterators. |
174 | template<typename _Value, bool _Cache_hash_code> | |
3b2524b1 PC |
175 | struct _Node_iterator_base |
176 | { | |
4dad8b49 BK |
177 | typedef _Hash_node<_Value, _Cache_hash_code> __node_type; |
178 | ||
179 | __node_type* _M_cur; | |
180 | ||
181 | _Node_iterator_base(__node_type* __p) | |
3b2524b1 | 182 | : _M_cur(__p) { } |
7c3e9502 | 183 | |
3b2524b1 PC |
184 | void |
185 | _M_incr() | |
f86b266c | 186 | { _M_cur = _M_cur->_M_next(); } |
3b2524b1 PC |
187 | }; |
188 | ||
4dad8b49 | 189 | template<typename _Value, bool _Cache_hash_code> |
3b2524b1 | 190 | inline bool |
4dad8b49 BK |
191 | operator==(const _Node_iterator_base<_Value, _Cache_hash_code>& __x, |
192 | const _Node_iterator_base<_Value, _Cache_hash_code >& __y) | |
3b2524b1 PC |
193 | { return __x._M_cur == __y._M_cur; } |
194 | ||
4dad8b49 | 195 | template<typename _Value, bool _Cache_hash_code> |
3b2524b1 | 196 | inline bool |
4dad8b49 BK |
197 | operator!=(const _Node_iterator_base<_Value, _Cache_hash_code>& __x, |
198 | const _Node_iterator_base<_Value, _Cache_hash_code>& __y) | |
3b2524b1 PC |
199 | { return __x._M_cur != __y._M_cur; } |
200 | ||
4dad8b49 | 201 | /// Node iterators, used to iterate through all the hashtable. |
3b2524b1 PC |
202 | template<typename _Value, bool __constant_iterators, bool __cache> |
203 | struct _Node_iterator | |
204 | : public _Node_iterator_base<_Value, __cache> | |
205 | { | |
4dad8b49 BK |
206 | private: |
207 | using __base_type = _Node_iterator_base<_Value, __cache>; | |
208 | using __node_type = typename __base_type::__node_type; | |
209 | ||
210 | public: | |
3b2524b1 | 211 | typedef _Value value_type; |
3b2524b1 PC |
212 | typedef std::ptrdiff_t difference_type; |
213 | typedef std::forward_iterator_tag iterator_category; | |
214 | ||
4dad8b49 BK |
215 | using pointer = typename std::conditional<__constant_iterators, |
216 | const _Value*, _Value*>::type; | |
217 | ||
218 | using reference = typename std::conditional<__constant_iterators, | |
219 | const _Value&, _Value&>::type; | |
220 | ||
3b2524b1 | 221 | _Node_iterator() |
4dad8b49 | 222 | : __base_type(0) { } |
3b2524b1 PC |
223 | |
224 | explicit | |
4dad8b49 BK |
225 | _Node_iterator(__node_type* __p) |
226 | : __base_type(__p) { } | |
3b2524b1 PC |
227 | |
228 | reference | |
229 | operator*() const | |
230 | { return this->_M_cur->_M_v; } | |
7c3e9502 | 231 | |
3b2524b1 PC |
232 | pointer |
233 | operator->() const | |
882b3d5c | 234 | { return std::__addressof(this->_M_cur->_M_v); } |
3b2524b1 PC |
235 | |
236 | _Node_iterator& | |
237 | operator++() | |
7c3e9502 | 238 | { |
3b2524b1 | 239 | this->_M_incr(); |
7c3e9502 | 240 | return *this; |
3b2524b1 | 241 | } |
7c3e9502 | 242 | |
3b2524b1 PC |
243 | _Node_iterator |
244 | operator++(int) | |
7c3e9502 | 245 | { |
3b2524b1 PC |
246 | _Node_iterator __tmp(*this); |
247 | this->_M_incr(); | |
248 | return __tmp; | |
249 | } | |
250 | }; | |
251 | ||
4dad8b49 | 252 | /// Node const_iterators, used to iterate through all the hashtable. |
3b2524b1 PC |
253 | template<typename _Value, bool __constant_iterators, bool __cache> |
254 | struct _Node_const_iterator | |
255 | : public _Node_iterator_base<_Value, __cache> | |
256 | { | |
4dad8b49 BK |
257 | private: |
258 | using __base_type = _Node_iterator_base<_Value, __cache>; | |
259 | using __node_type = typename __base_type::__node_type; | |
260 | ||
261 | public: | |
3b2524b1 | 262 | typedef _Value value_type; |
3b2524b1 PC |
263 | typedef std::ptrdiff_t difference_type; |
264 | typedef std::forward_iterator_tag iterator_category; | |
265 | ||
4dad8b49 BK |
266 | typedef const _Value* pointer; |
267 | typedef const _Value& reference; | |
268 | ||
3b2524b1 | 269 | _Node_const_iterator() |
4dad8b49 | 270 | : __base_type(0) { } |
3b2524b1 PC |
271 | |
272 | explicit | |
4dad8b49 BK |
273 | _Node_const_iterator(__node_type* __p) |
274 | : __base_type(__p) { } | |
3b2524b1 PC |
275 | |
276 | _Node_const_iterator(const _Node_iterator<_Value, __constant_iterators, | |
277 | __cache>& __x) | |
4dad8b49 | 278 | : __base_type(__x._M_cur) { } |
3b2524b1 PC |
279 | |
280 | reference | |
281 | operator*() const | |
282 | { return this->_M_cur->_M_v; } | |
7c3e9502 | 283 | |
3b2524b1 PC |
284 | pointer |
285 | operator->() const | |
882b3d5c | 286 | { return std::__addressof(this->_M_cur->_M_v); } |
3b2524b1 PC |
287 | |
288 | _Node_const_iterator& | |
289 | operator++() | |
7c3e9502 | 290 | { |
3b2524b1 | 291 | this->_M_incr(); |
7c3e9502 | 292 | return *this; |
3b2524b1 | 293 | } |
7c3e9502 | 294 | |
3b2524b1 PC |
295 | _Node_const_iterator |
296 | operator++(int) | |
7c3e9502 | 297 | { |
3b2524b1 PC |
298 | _Node_const_iterator __tmp(*this); |
299 | this->_M_incr(); | |
300 | return __tmp; | |
301 | } | |
302 | }; | |
303 | ||
3b2524b1 PC |
304 | // Many of class template _Hashtable's template parameters are policy |
305 | // classes. These are defaults for the policies. | |
306 | ||
4dad8b49 BK |
307 | /// Default range hashing function: use division to fold a large number |
308 | /// into the range [0, N). | |
3b2524b1 PC |
309 | struct _Mod_range_hashing |
310 | { | |
311 | typedef std::size_t first_argument_type; | |
312 | typedef std::size_t second_argument_type; | |
313 | typedef std::size_t result_type; | |
314 | ||
315 | result_type | |
316 | operator()(first_argument_type __num, second_argument_type __den) const | |
317 | { return __num % __den; } | |
318 | }; | |
319 | ||
4dad8b49 BK |
320 | /// Default ranged hash function H. In principle it should be a |
321 | /// function object composed from objects of type H1 and H2 such that | |
322 | /// h(k, N) = h2(h1(k), N), but that would mean making extra copies of | |
323 | /// h1 and h2. So instead we'll just use a tag to tell class template | |
324 | /// hashtable to do that composition. | |
3b2524b1 PC |
325 | struct _Default_ranged_hash { }; |
326 | ||
4dad8b49 BK |
327 | /// Default value for rehash policy. Bucket size is (usually) the |
328 | /// smallest prime that keeps the load factor small enough. | |
3b2524b1 PC |
329 | struct _Prime_rehash_policy |
330 | { | |
331 | _Prime_rehash_policy(float __z = 1.0) | |
da29608a | 332 | : _M_max_load_factor(__z), _M_prev_resize(0), _M_next_resize(0) { } |
3b2524b1 PC |
333 | |
334 | float | |
d3677132 | 335 | max_load_factor() const noexcept |
7c3e9502 | 336 | { return _M_max_load_factor; } |
3b2524b1 PC |
337 | |
338 | // Return a bucket size no smaller than n. | |
339 | std::size_t | |
340 | _M_next_bkt(std::size_t __n) const; | |
7c3e9502 | 341 | |
3b2524b1 PC |
342 | // Return a bucket count appropriate for n elements |
343 | std::size_t | |
344 | _M_bkt_for_elements(std::size_t __n) const; | |
7c3e9502 | 345 | |
3b2524b1 PC |
346 | // __n_bkt is current bucket count, __n_elt is current element count, |
347 | // and __n_ins is number of elements to be inserted. Do we need to | |
348 | // increase bucket count? If so, return make_pair(true, n), where n | |
349 | // is the new bucket count. If not, return make_pair(false, 0). | |
350 | std::pair<bool, std::size_t> | |
351 | _M_need_rehash(std::size_t __n_bkt, std::size_t __n_elt, | |
352 | std::size_t __n_ins) const; | |
353 | ||
da29608a FD |
354 | typedef std::pair<std::size_t, std::size_t> _State; |
355 | ||
356 | _State | |
357 | _M_state() const | |
358 | { return std::make_pair(_M_prev_resize, _M_next_resize); } | |
359 | ||
360 | void | |
361 | _M_reset(const _State& __state) | |
362 | { | |
363 | _M_prev_resize = __state.first; | |
364 | _M_next_resize = __state.second; | |
365 | } | |
366 | ||
3b2524b1 PC |
367 | enum { _S_n_primes = sizeof(unsigned long) != 8 ? 256 : 256 + 48 }; |
368 | ||
369 | float _M_max_load_factor; | |
da29608a | 370 | mutable std::size_t _M_prev_resize; |
3b2524b1 PC |
371 | mutable std::size_t _M_next_resize; |
372 | }; | |
373 | ||
374 | extern const unsigned long __prime_list[]; | |
375 | ||
376 | // XXX This is a hack. There's no good reason for any of | |
7c3e9502 | 377 | // _Prime_rehash_policy's member functions to be inline. |
3b2524b1 PC |
378 | |
379 | // Return a prime no smaller than n. | |
380 | inline std::size_t | |
381 | _Prime_rehash_policy:: | |
382 | _M_next_bkt(std::size_t __n) const | |
383 | { | |
4cdccf26 PC |
384 | // Optimize lookups involving the first elements of __prime_list. |
385 | // (useful to speed-up, eg, constructors) | |
95c0a8a7 | 386 | static const unsigned char __fast_bkt[12] |
4cdccf26 PC |
387 | = { 2, 2, 2, 3, 5, 5, 7, 7, 11, 11, 11, 11 }; |
388 | ||
95c0a8a7 FD |
389 | if (__n <= 11) |
390 | { | |
391 | _M_prev_resize = 0; | |
392 | _M_next_resize | |
393 | = __builtin_ceil(__fast_bkt[__n] * (long double)_M_max_load_factor); | |
394 | return __fast_bkt[__n]; | |
395 | } | |
396 | ||
da29608a | 397 | const unsigned long* __p |
95c0a8a7 FD |
398 | = std::lower_bound(__prime_list + 5, __prime_list + _S_n_primes, __n); |
399 | ||
400 | // Shrink will take place only if the number of elements is small enough | |
401 | // so that the prime number 2 steps before __p is large enough to still | |
402 | // conform to the max load factor: | |
403 | _M_prev_resize | |
404 | = __builtin_floor(*(__p - 2) * (long double)_M_max_load_factor); | |
405 | ||
406 | // Let's guaranty that a minimal grow step of 11 is used | |
da29608a | 407 | if (*__p - __n < 11) |
95c0a8a7 FD |
408 | __p = std::lower_bound(__p, __prime_list + _S_n_primes, __n + 11); |
409 | _M_next_resize = __builtin_ceil(*__p * (long double)_M_max_load_factor); | |
da29608a | 410 | return *__p; |
3b2524b1 PC |
411 | } |
412 | ||
413 | // Return the smallest prime p such that alpha p >= n, where alpha | |
414 | // is the load factor. | |
415 | inline std::size_t | |
416 | _Prime_rehash_policy:: | |
417 | _M_bkt_for_elements(std::size_t __n) const | |
e25fc78f | 418 | { return _M_next_bkt(__builtin_ceil(__n / (long double)_M_max_load_factor)); } |
3b2524b1 PC |
419 | |
420 | // Finds the smallest prime p such that alpha p > __n_elt + __n_ins. | |
421 | // If p > __n_bkt, return make_pair(true, p); otherwise return | |
7c3e9502 | 422 | // make_pair(false, 0). In principle this isn't very different from |
3b2524b1 PC |
423 | // _M_bkt_for_elements. |
424 | ||
425 | // The only tricky part is that we're caching the element count at | |
426 | // which we need to rehash, so we don't have to do a floating-point | |
427 | // multiply for every insertion. | |
428 | ||
429 | inline std::pair<bool, std::size_t> | |
430 | _Prime_rehash_policy:: | |
431 | _M_need_rehash(std::size_t __n_bkt, std::size_t __n_elt, | |
432 | std::size_t __n_ins) const | |
433 | { | |
da29608a | 434 | if (__n_elt + __n_ins >= _M_next_resize) |
3b2524b1 | 435 | { |
da29608a FD |
436 | long double __min_bkts = (__n_elt + __n_ins) |
437 | / (long double)_M_max_load_factor; | |
438 | if (__min_bkts >= __n_bkt) | |
439 | return std::make_pair(true, | |
440 | _M_next_bkt(__builtin_floor(__min_bkts) + 1)); | |
7c3e9502 | 441 | else |
3b2524b1 | 442 | { |
e25fc78f FD |
443 | _M_next_resize |
444 | = __builtin_floor(__n_bkt * (long double)_M_max_load_factor); | |
3b2524b1 PC |
445 | return std::make_pair(false, 0); |
446 | } | |
447 | } | |
da29608a FD |
448 | else if (__n_elt + __n_ins < _M_prev_resize) |
449 | { | |
450 | long double __min_bkts = (__n_elt + __n_ins) | |
451 | / (long double)_M_max_load_factor; | |
452 | return std::make_pair(true, | |
453 | _M_next_bkt(__builtin_floor(__min_bkts) + 1)); | |
454 | } | |
3b2524b1 PC |
455 | else |
456 | return std::make_pair(false, 0); | |
457 | } | |
458 | ||
5dc22714 | 459 | // Base classes for std::_Hashtable. We define these base classes |
4dad8b49 BK |
460 | // because in some cases we want to do different things depending on |
461 | // the value of a policy class. In some cases the policy class | |
5dc22714 PC |
462 | // affects which member functions and nested typedefs are defined; |
463 | // we handle that by specializing base class templates. Several of | |
464 | // the base class templates need to access other members of class | |
4dad8b49 BK |
465 | // template _Hashtable, so we use a variant of the "Curiously |
466 | // Recurring Template Pattern" (CRTP) technique. | |
467 | ||
468 | /** | |
469 | * Primary class template _Map_base. | |
470 | * | |
471 | * If the hashtable has a value type of the form pair<T1, T2> and a | |
472 | * key extraction policy (_ExtractKey) that returns the first part | |
473 | * of the pair, the hashtable gets a mapped_type typedef. If it | |
474 | * satisfies those criteria and also has unique keys, then it also | |
475 | * gets an operator[]. | |
476 | */ | |
477 | template<typename _Key, typename _Value, typename _Alloc, | |
478 | typename _ExtractKey, typename _Equal, | |
479 | typename _H1, typename _H2, typename _Hash, | |
480 | typename _RehashPolicy, typename _Traits, | |
481 | bool _Unique_keys = _Traits::__unique_keys::value> | |
3b2524b1 | 482 | struct _Map_base { }; |
5dc22714 | 483 | |
4dad8b49 BK |
484 | /// Partial specialization, __unique_keys set to false. |
485 | template<typename _Key, typename _Pair, typename _Alloc, typename _Equal, | |
486 | typename _H1, typename _H2, typename _Hash, | |
487 | typename _RehashPolicy, typename _Traits> | |
488 | struct _Map_base<_Key, _Pair, _Alloc, std::_Select1st<_Pair>, _Equal, | |
489 | _H1, _H2, _Hash, _RehashPolicy, _Traits, false> | |
3b2524b1 | 490 | { |
4dad8b49 | 491 | using mapped_type = typename _Pair::second_type; |
3b2524b1 PC |
492 | }; |
493 | ||
4dad8b49 BK |
494 | /// Partial specialization, __unique_keys set to true. |
495 | template<typename _Key, typename _Pair, typename _Alloc, typename _Equal, | |
496 | typename _H1, typename _H2, typename _Hash, | |
497 | typename _RehashPolicy, typename _Traits> | |
498 | struct _Map_base<_Key, _Pair, _Alloc, std::_Select1st<_Pair>, _Equal, | |
499 | _H1, _H2, _Hash, _RehashPolicy, _Traits, true> | |
3b2524b1 | 500 | { |
4dad8b49 BK |
501 | private: |
502 | using __hashtable_base = __detail::_Hashtable_base<_Key, _Pair, | |
503 | std::_Select1st<_Pair>, | |
504 | _Equal, _H1, _H2, _Hash, | |
505 | _Traits>; | |
506 | ||
507 | using __hashtable = _Hashtable<_Key, _Pair, _Alloc, | |
508 | std::_Select1st<_Pair>, _Equal, | |
509 | _H1, _H2, _Hash, _RehashPolicy, _Traits>; | |
510 | ||
511 | using __hash_code = typename __hashtable_base::__hash_code; | |
512 | using __node_type = typename __hashtable_base::__node_type; | |
513 | ||
514 | public: | |
515 | using key_type = typename __hashtable_base::key_type; | |
516 | using iterator = typename __hashtable_base::iterator; | |
517 | using mapped_type = typename _Pair::second_type; | |
5dc22714 | 518 | |
3b2524b1 | 519 | mapped_type& |
4dad8b49 | 520 | operator[](const key_type& __k); |
3b2524b1 | 521 | |
fb7342fd | 522 | mapped_type& |
4dad8b49 | 523 | operator[](key_type&& __k); |
fb7342fd | 524 | |
3b2524b1 PC |
525 | // _GLIBCXX_RESOLVE_LIB_DEFECTS |
526 | // DR 761. unordered_map needs an at() member function. | |
527 | mapped_type& | |
4dad8b49 | 528 | at(const key_type& __k); |
3b2524b1 PC |
529 | |
530 | const mapped_type& | |
4dad8b49 | 531 | at(const key_type& __k) const; |
3b2524b1 PC |
532 | }; |
533 | ||
4dad8b49 BK |
534 | template<typename _Key, typename _Pair, typename _Alloc, typename _Equal, |
535 | typename _H1, typename _H2, typename _Hash, | |
536 | typename _RehashPolicy, typename _Traits> | |
537 | typename _Map_base<_Key, _Pair, _Alloc, std::_Select1st<_Pair>, _Equal, | |
538 | _H1, _H2, _Hash, _RehashPolicy, _Traits, true> | |
539 | ::mapped_type& | |
540 | _Map_base<_Key, _Pair, _Alloc, std::_Select1st<_Pair>, _Equal, | |
541 | _H1, _H2, _Hash, _RehashPolicy, _Traits, true>:: | |
542 | operator[](const key_type& __k) | |
3b2524b1 | 543 | { |
4dad8b49 BK |
544 | __hashtable* __h = static_cast<__hashtable*>(this); |
545 | __hash_code __code = __h->_M_hash_code(__k); | |
a188284c | 546 | std::size_t __n = __h->_M_bucket_index(__k, __code); |
4dad8b49 | 547 | __node_type* __p = __h->_M_find_node(__n, __k, __code); |
3b2524b1 | 548 | |
3b2524b1 PC |
549 | if (!__p) |
550 | return __h->_M_insert_bucket(std::make_pair(__k, mapped_type()), | |
551 | __n, __code)->second; | |
552 | return (__p->_M_v).second; | |
553 | } | |
554 | ||
4dad8b49 BK |
555 | template<typename _Key, typename _Pair, typename _Alloc, typename _Equal, |
556 | typename _H1, typename _H2, typename _Hash, | |
557 | typename _RehashPolicy, typename _Traits> | |
558 | typename _Map_base<_Key, _Pair, _Alloc, std::_Select1st<_Pair>, _Equal, | |
559 | _H1, _H2, _Hash, _RehashPolicy, _Traits, true> | |
560 | ::mapped_type& | |
561 | _Map_base<_Key, _Pair, _Alloc, std::_Select1st<_Pair>, _Equal, | |
562 | _H1, _H2, _Hash, _RehashPolicy, _Traits, true>:: | |
563 | operator[](key_type&& __k) | |
fb7342fd | 564 | { |
4dad8b49 BK |
565 | __hashtable* __h = static_cast<__hashtable*>(this); |
566 | __hash_code __code = __h->_M_hash_code(__k); | |
a188284c | 567 | std::size_t __n = __h->_M_bucket_index(__k, __code); |
4dad8b49 | 568 | __node_type* __p = __h->_M_find_node(__n, __k, __code); |
fb7342fd | 569 | |
fb7342fd PC |
570 | if (!__p) |
571 | return __h->_M_insert_bucket(std::make_pair(std::move(__k), | |
572 | mapped_type()), | |
573 | __n, __code)->second; | |
574 | return (__p->_M_v).second; | |
575 | } | |
576 | ||
4dad8b49 BK |
577 | template<typename _Key, typename _Pair, typename _Alloc, typename _Equal, |
578 | typename _H1, typename _H2, typename _Hash, | |
579 | typename _RehashPolicy, typename _Traits> | |
580 | typename _Map_base<_Key, _Pair, _Alloc, std::_Select1st<_Pair>, _Equal, | |
581 | _H1, _H2, _Hash, _RehashPolicy, _Traits, true> | |
582 | ::mapped_type& | |
583 | _Map_base<_Key, _Pair, _Alloc, std::_Select1st<_Pair>, _Equal, | |
584 | _H1, _H2, _Hash, _RehashPolicy, _Traits, true>:: | |
585 | at(const key_type& __k) | |
3b2524b1 | 586 | { |
4dad8b49 BK |
587 | __hashtable* __h = static_cast<__hashtable*>(this); |
588 | __hash_code __code = __h->_M_hash_code(__k); | |
a188284c | 589 | std::size_t __n = __h->_M_bucket_index(__k, __code); |
4dad8b49 | 590 | __node_type* __p = __h->_M_find_node(__n, __k, __code); |
3b2524b1 | 591 | |
3b2524b1 PC |
592 | if (!__p) |
593 | __throw_out_of_range(__N("_Map_base::at")); | |
594 | return (__p->_M_v).second; | |
595 | } | |
596 | ||
4dad8b49 BK |
597 | template<typename _Key, typename _Pair, typename _Alloc, typename _Equal, |
598 | typename _H1, typename _H2, typename _Hash, | |
599 | typename _RehashPolicy, typename _Traits> | |
600 | const typename _Map_base<_Key, _Pair, _Alloc, std::_Select1st<_Pair>, | |
601 | _Equal, | |
602 | _H1, _H2, _Hash, _RehashPolicy, _Traits, true> | |
603 | ::mapped_type& | |
604 | _Map_base<_Key, _Pair, _Alloc, std::_Select1st<_Pair>, _Equal, | |
605 | _H1, _H2, _Hash, _RehashPolicy, _Traits, true>:: | |
606 | at(const key_type& __k) const | |
3b2524b1 | 607 | { |
4dad8b49 BK |
608 | const __hashtable* __h = static_cast<const __hashtable*>(this); |
609 | __hash_code __code = __h->_M_hash_code(__k); | |
a188284c | 610 | std::size_t __n = __h->_M_bucket_index(__k, __code); |
4dad8b49 | 611 | __node_type* __p = __h->_M_find_node(__n, __k, __code); |
3b2524b1 | 612 | |
3b2524b1 PC |
613 | if (!__p) |
614 | __throw_out_of_range(__N("_Map_base::at")); | |
615 | return (__p->_M_v).second; | |
616 | } | |
617 | ||
4dad8b49 BK |
618 | /** |
619 | * Primary class template _Insert_base. | |
620 | * | |
621 | * insert member functions appropriate to all _Hashtables. | |
622 | */ | |
623 | template<typename _Key, typename _Value, typename _Alloc, | |
624 | typename _ExtractKey, typename _Equal, | |
625 | typename _H1, typename _H2, typename _Hash, | |
626 | typename _RehashPolicy, typename _Traits> | |
627 | struct _Insert_base | |
628 | { | |
629 | using __hashtable = _Hashtable<_Key, _Value, _Alloc, _ExtractKey, | |
630 | _Equal, _H1, _H2, _Hash, | |
631 | _RehashPolicy, _Traits>; | |
632 | ||
633 | using __hashtable_base = _Hashtable_base<_Key, _Value, _ExtractKey, | |
634 | _Equal, _H1, _H2, _Hash, | |
635 | _Traits>; | |
636 | ||
637 | using value_type = typename __hashtable_base::value_type; | |
638 | using iterator = typename __hashtable_base::iterator; | |
639 | using const_iterator = typename __hashtable_base::const_iterator; | |
640 | using size_type = typename __hashtable_base::size_type; | |
641 | ||
642 | using __unique_keys = typename __hashtable_base::__unique_keys; | |
643 | using __ireturn_type = typename __hashtable_base::__ireturn_type; | |
644 | using __iconv_type = typename __hashtable_base::__iconv_type; | |
645 | ||
646 | __hashtable& | |
647 | _M_conjure_hashtable() | |
648 | { return *(static_cast<__hashtable*>(this)); } | |
649 | ||
650 | __ireturn_type | |
651 | insert(const value_type& __v) | |
652 | { | |
653 | __hashtable& __h = _M_conjure_hashtable(); | |
654 | return __h._M_insert(__v, __unique_keys()); | |
655 | } | |
656 | ||
657 | iterator | |
658 | insert(const_iterator, const value_type& __v) | |
659 | { return __iconv_type()(insert(__v)); } | |
3b2524b1 | 660 | |
4dad8b49 BK |
661 | void |
662 | insert(initializer_list<value_type> __l) | |
663 | { this->insert(__l.begin(), __l.end()); } | |
664 | ||
665 | template<typename _InputIterator> | |
666 | void | |
667 | insert(_InputIterator __first, _InputIterator __last); | |
668 | }; | |
669 | ||
670 | template<typename _Key, typename _Value, typename _Alloc, | |
671 | typename _ExtractKey, typename _Equal, | |
672 | typename _H1, typename _H2, typename _Hash, | |
673 | typename _RehashPolicy, typename _Traits> | |
674 | template<typename _InputIterator> | |
675 | void | |
676 | _Insert_base<_Key, _Value, _Alloc, _ExtractKey, _Equal, _H1, _H2, _Hash, | |
677 | _RehashPolicy, _Traits>:: | |
678 | insert(_InputIterator __first, _InputIterator __last) | |
679 | { | |
680 | using __rehash_type = typename __hashtable::__rehash_type; | |
681 | using __rehash_state = typename __hashtable::__rehash_state; | |
682 | using pair_type = std::pair<bool, std::size_t>; | |
683 | ||
684 | size_type __n_elt = __detail::__distance_fw(__first, __last); | |
685 | ||
686 | __hashtable& __h = _M_conjure_hashtable(); | |
687 | __rehash_type& __rehash = __h._M_rehash_policy; | |
688 | const __rehash_state& __saved_state = __rehash._M_state(); | |
689 | pair_type __do_rehash = __rehash._M_need_rehash(__h._M_bucket_count, | |
690 | __h._M_element_count, | |
691 | __n_elt); | |
692 | ||
693 | if (__do_rehash.first) | |
694 | __h._M_rehash(__do_rehash.second, __saved_state); | |
695 | ||
696 | for (; __first != __last; ++__first) | |
697 | this->insert(*__first); | |
698 | } | |
699 | ||
700 | /** | |
701 | * Primary class template _Insert. | |
702 | * | |
703 | * Select insert member functions appropriate to _Hashtable policy choices. | |
704 | */ | |
705 | template<typename _Key, typename _Value, typename _Alloc, | |
706 | typename _ExtractKey, typename _Equal, | |
707 | typename _H1, typename _H2, typename _Hash, | |
708 | typename _RehashPolicy, typename _Traits, | |
709 | bool _Constant_iterators = _Traits::__constant_iterators::value, | |
710 | bool _Unique_keys = _Traits::__unique_keys::value> | |
711 | struct _Insert; | |
712 | ||
713 | /// Specialization. | |
714 | template<typename _Key, typename _Value, typename _Alloc, | |
715 | typename _ExtractKey, typename _Equal, | |
716 | typename _H1, typename _H2, typename _Hash, | |
717 | typename _RehashPolicy, typename _Traits> | |
718 | struct _Insert<_Key, _Value, _Alloc, _ExtractKey, _Equal, _H1, _H2, _Hash, | |
719 | _RehashPolicy, _Traits, true, true> | |
720 | : public _Insert_base<_Key, _Value, _Alloc, _ExtractKey, _Equal, | |
721 | _H1, _H2, _Hash, _RehashPolicy, _Traits> | |
722 | { | |
723 | using __base_type = _Insert_base<_Key, _Value, _Alloc, _ExtractKey, | |
724 | _Equal, _H1, _H2, _Hash, | |
725 | _RehashPolicy, _Traits>; | |
726 | using value_type = typename __base_type::value_type; | |
727 | using iterator = typename __base_type::iterator; | |
728 | using const_iterator = typename __base_type::const_iterator; | |
729 | ||
730 | using __unique_keys = typename __base_type::__unique_keys; | |
731 | using __hashtable = typename __base_type::__hashtable; | |
732 | ||
733 | using __base_type::insert; | |
734 | ||
735 | std::pair<iterator, bool> | |
736 | insert(value_type&& __v) | |
737 | { | |
738 | __hashtable& __h = this->_M_conjure_hashtable(); | |
739 | return __h._M_insert(std::move(__v), __unique_keys()); | |
740 | } | |
741 | ||
742 | iterator | |
743 | insert(const_iterator, value_type&& __v) | |
744 | { return insert(std::move(__v)).first; } | |
745 | }; | |
746 | ||
747 | /// Specialization. | |
748 | template<typename _Key, typename _Value, typename _Alloc, | |
749 | typename _ExtractKey, typename _Equal, | |
750 | typename _H1, typename _H2, typename _Hash, | |
751 | typename _RehashPolicy, typename _Traits> | |
752 | struct _Insert<_Key, _Value, _Alloc, _ExtractKey, _Equal, _H1, _H2, _Hash, | |
753 | _RehashPolicy, _Traits, true, false> | |
754 | : public _Insert_base<_Key, _Value, _Alloc, _ExtractKey, _Equal, | |
755 | _H1, _H2, _Hash, _RehashPolicy, _Traits> | |
756 | { | |
757 | using __base_type = _Insert_base<_Key, _Value, _Alloc, _ExtractKey, | |
758 | _Equal, _H1, _H2, _Hash, | |
759 | _RehashPolicy, _Traits>; | |
760 | using value_type = typename __base_type::value_type; | |
761 | using iterator = typename __base_type::iterator; | |
762 | using const_iterator = typename __base_type::const_iterator; | |
763 | ||
764 | using __unique_keys = typename __base_type::__unique_keys; | |
765 | using __hashtable = typename __base_type::__hashtable; | |
766 | ||
767 | using __base_type::insert; | |
768 | ||
769 | iterator | |
770 | insert(value_type&& __v) | |
771 | { | |
772 | __hashtable& __h = this->_M_conjure_hashtable(); | |
773 | return __h._M_insert(std::move(__v), __unique_keys()); | |
774 | } | |
775 | ||
776 | iterator | |
777 | insert(const_iterator, value_type&& __v) | |
778 | { return insert(std::move(__v)); } | |
779 | }; | |
780 | ||
781 | /// Specialization. | |
782 | template<typename _Key, typename _Value, typename _Alloc, | |
783 | typename _ExtractKey, typename _Equal, | |
784 | typename _H1, typename _H2, typename _Hash, | |
785 | typename _RehashPolicy, typename _Traits, bool _Unique_keys> | |
786 | struct _Insert<_Key, _Value, _Alloc, _ExtractKey, _Equal, _H1, _H2, _Hash, | |
787 | _RehashPolicy, _Traits, false, _Unique_keys> | |
788 | : public _Insert_base<_Key, _Value, _Alloc, _ExtractKey, _Equal, | |
789 | _H1, _H2, _Hash, _RehashPolicy, _Traits> | |
3b2524b1 | 790 | { |
4dad8b49 BK |
791 | using __base_type = _Insert_base<_Key, _Value, _Alloc, _ExtractKey, |
792 | _Equal, _H1, _H2, _Hash, | |
793 | _RehashPolicy, _Traits>; | |
794 | using value_type = typename __base_type::value_type; | |
795 | using iterator = typename __base_type::iterator; | |
796 | using const_iterator = typename __base_type::const_iterator; | |
797 | ||
798 | using __unique_keys = typename __base_type::__unique_keys; | |
799 | using __hashtable = typename __base_type::__hashtable; | |
800 | using __ireturn_type = typename __base_type::__ireturn_type; | |
801 | using __iconv_type = typename __base_type::__iconv_type; | |
802 | ||
803 | using __base_type::insert; | |
804 | ||
805 | template<typename _Pair> | |
806 | using __is_convertible = std::is_convertible<_Pair, value_type>; | |
807 | ||
808 | template<typename _Pair> | |
809 | using _IFconv = std::enable_if<__is_convertible<_Pair>::value>; | |
810 | ||
811 | template<typename _Pair> | |
812 | using _IFconvp = typename _IFconv<_Pair>::type; | |
813 | ||
814 | template<typename _Pair, typename = _IFconvp<_Pair>> | |
815 | __ireturn_type | |
816 | insert(_Pair&& __v) | |
817 | { | |
818 | __hashtable& __h = this->_M_conjure_hashtable(); | |
819 | return __h._M_insert(std::forward<_Pair>(__v), __unique_keys()); | |
820 | } | |
821 | ||
822 | template<typename _Pair, typename = _IFconvp<_Pair>> | |
823 | iterator | |
824 | insert(const_iterator, _Pair&& __v) | |
825 | { return __iconv_type()(insert(std::forward<_Pair>(__v))); } | |
826 | }; | |
827 | ||
828 | /** | |
829 | * Primary class template _Rehash_base. | |
830 | * | |
831 | * Give hashtable the max_load_factor functions and reserve iff the | |
832 | * rehash policy is _Prime_rehash_policy. | |
833 | */ | |
834 | template<typename _Key, typename _Value, typename _Alloc, | |
835 | typename _ExtractKey, typename _Equal, | |
836 | typename _H1, typename _H2, typename _Hash, | |
837 | typename _RehashPolicy, typename _Traits> | |
838 | struct _Rehash_base; | |
839 | ||
840 | /// Specialization. | |
841 | template<typename _Key, typename _Value, typename _Alloc, | |
842 | typename _ExtractKey, typename _Equal, | |
843 | typename _H1, typename _H2, typename _Hash, typename _Traits> | |
844 | struct _Rehash_base<_Key, _Value, _Alloc, _ExtractKey, _Equal, | |
845 | _H1, _H2, _Hash, _Prime_rehash_policy, _Traits> | |
846 | { | |
847 | using __hashtable = _Hashtable<_Key, _Value, _Alloc, _ExtractKey, | |
848 | _Equal, _H1, _H2, _Hash, | |
849 | _Prime_rehash_policy, _Traits>; | |
850 | ||
3b2524b1 | 851 | float |
d3677132 | 852 | max_load_factor() const noexcept |
3b2524b1 | 853 | { |
4dad8b49 | 854 | const __hashtable* __this = static_cast<const __hashtable*>(this); |
3b2524b1 PC |
855 | return __this->__rehash_policy().max_load_factor(); |
856 | } | |
857 | ||
858 | void | |
859 | max_load_factor(float __z) | |
860 | { | |
4dad8b49 | 861 | __hashtable* __this = static_cast<__hashtable*>(this); |
3b2524b1 PC |
862 | __this->__rehash_policy(_Prime_rehash_policy(__z)); |
863 | } | |
9155c0e3 PC |
864 | |
865 | void | |
866 | reserve(std::size_t __n) | |
867 | { | |
4dad8b49 | 868 | __hashtable* __this = static_cast<__hashtable*>(this); |
9155c0e3 PC |
869 | __this->rehash(__builtin_ceil(__n / max_load_factor())); |
870 | } | |
3b2524b1 PC |
871 | }; |
872 | ||
4dad8b49 BK |
873 | /** |
874 | * Primary class template _Hashtable_ebo_helper. | |
875 | * | |
876 | * Helper class using EBO when it is not forbidden, type is not | |
877 | * final, and when it worth it, type is empty. | |
878 | */ | |
cc74ac5d | 879 | template<int _Nm, typename _Tp, |
a188284c | 880 | bool __use_ebo = !__is_final(_Tp) && __is_empty(_Tp)> |
346afd84 | 881 | struct _Hashtable_ebo_helper; |
a188284c | 882 | |
4dad8b49 | 883 | /// Specialization using EBO. |
cc74ac5d | 884 | template<int _Nm, typename _Tp> |
346afd84 | 885 | struct _Hashtable_ebo_helper<_Nm, _Tp, true> : private _Tp |
a188284c | 886 | { |
346afd84 | 887 | _Hashtable_ebo_helper() = default; |
4dad8b49 | 888 | |
346afd84 | 889 | _Hashtable_ebo_helper(const _Tp& __tp) : _Tp(__tp) |
a188284c FD |
890 | { } |
891 | ||
892 | static const _Tp& | |
346afd84 | 893 | _S_cget(const _Hashtable_ebo_helper& __eboh) |
a188284c FD |
894 | { return static_cast<const _Tp&>(__eboh); } |
895 | ||
896 | static _Tp& | |
346afd84 | 897 | _S_get(_Hashtable_ebo_helper& __eboh) |
a188284c FD |
898 | { return static_cast<_Tp&>(__eboh); } |
899 | }; | |
900 | ||
4dad8b49 | 901 | /// Specialization not using EBO. |
cc74ac5d | 902 | template<int _Nm, typename _Tp> |
346afd84 | 903 | struct _Hashtable_ebo_helper<_Nm, _Tp, false> |
a188284c | 904 | { |
346afd84 | 905 | _Hashtable_ebo_helper() = default; |
4dad8b49 | 906 | |
346afd84 | 907 | _Hashtable_ebo_helper(const _Tp& __tp) : _M_tp(__tp) |
a188284c FD |
908 | { } |
909 | ||
910 | static const _Tp& | |
346afd84 FD |
911 | _S_cget(const _Hashtable_ebo_helper& __eboh) |
912 | { return __eboh._M_tp; } | |
a188284c FD |
913 | |
914 | static _Tp& | |
346afd84 FD |
915 | _S_get(_Hashtable_ebo_helper& __eboh) |
916 | { return __eboh._M_tp; } | |
a188284c FD |
917 | |
918 | private: | |
346afd84 | 919 | _Tp _M_tp; |
a188284c FD |
920 | }; |
921 | ||
4dad8b49 BK |
922 | /** |
923 | * Primary class template _Hash_code_base. | |
924 | * | |
925 | * Encapsulates two policy issues that aren't quite orthogonal. | |
926 | * (1) the difference between using a ranged hash function and using | |
927 | * the combination of a hash function and a range-hashing function. | |
928 | * In the former case we don't have such things as hash codes, so | |
929 | * we have a dummy type as placeholder. | |
930 | * (2) Whether or not we cache hash codes. Caching hash codes is | |
931 | * meaningless if we have a ranged hash function. | |
932 | * | |
933 | * We also put the key extraction objects here, for convenience. | |
934 | * Each specialization derives from one or more of the template | |
935 | * parameters to benefit from Ebo. This is important as this type | |
936 | * is inherited in some cases by the _Local_iterator_base type used | |
937 | * to implement local_iterator and const_local_iterator. As with | |
938 | * any iterator type we prefer to make it as small as possible. | |
939 | * | |
940 | * Primary template is unused except as a hook for specializations. | |
941 | */ | |
a188284c | 942 | template<typename _Key, typename _Value, typename _ExtractKey, |
3b2524b1 PC |
943 | typename _H1, typename _H2, typename _Hash, |
944 | bool __cache_hash_code> | |
945 | struct _Hash_code_base; | |
946 | ||
4dad8b49 BK |
947 | /// Specialization: ranged hash function, no caching hash codes. H1 |
948 | /// and H2 are provided but ignored. We define a dummy hash code type. | |
949 | template<typename _Key, typename _Value, typename _ExtractKey, | |
3b2524b1 | 950 | typename _H1, typename _H2, typename _Hash> |
a188284c | 951 | struct _Hash_code_base<_Key, _Value, _ExtractKey, _H1, _H2, _Hash, false> |
346afd84 FD |
952 | : private _Hashtable_ebo_helper<0, _ExtractKey>, |
953 | private _Hashtable_ebo_helper<1, _Hash> | |
3b2524b1 | 954 | { |
a188284c | 955 | private: |
4dad8b49 BK |
956 | typedef _Hashtable_ebo_helper<0, _ExtractKey> _EboExtractKey; |
957 | typedef _Hashtable_ebo_helper<1, _Hash> _EboHash; | |
346afd84 | 958 | |
3b2524b1 | 959 | protected: |
4dad8b49 BK |
960 | typedef void* __hash_code; |
961 | typedef _Hash_node<_Value, false> __node_type; | |
962 | ||
a188284c FD |
963 | // We need the default constructor for the local iterators. |
964 | _Hash_code_base() = default; | |
3b2524b1 | 965 | |
4dad8b49 BK |
966 | _Hash_code_base(const _ExtractKey& __ex, const _H1&, const _H2&, |
967 | const _Hash& __h) | |
968 | : _EboExtractKey(__ex), _EboHash(__h) { } | |
7c3e9502 | 969 | |
4dad8b49 | 970 | __hash_code |
3b2524b1 PC |
971 | _M_hash_code(const _Key& __key) const |
972 | { return 0; } | |
7c3e9502 | 973 | |
3b2524b1 | 974 | std::size_t |
4dad8b49 | 975 | _M_bucket_index(const _Key& __k, __hash_code, std::size_t __n) const |
a188284c | 976 | { return _M_ranged_hash()(__k, __n); } |
3b2524b1 PC |
977 | |
978 | std::size_t | |
4dad8b49 | 979 | _M_bucket_index(const __node_type* __p, std::size_t __n) const |
a188284c | 980 | { return _M_ranged_hash()(_M_extract()(__p->_M_v), __n); } |
3b2524b1 PC |
981 | |
982 | void | |
4dad8b49 | 983 | _M_store_code(__node_type*, __hash_code) const |
3b2524b1 PC |
984 | { } |
985 | ||
986 | void | |
4dad8b49 | 987 | _M_copy_code(__node_type*, const __node_type*) const |
3b2524b1 | 988 | { } |
7c3e9502 | 989 | |
3b2524b1 PC |
990 | void |
991 | _M_swap(_Hash_code_base& __x) | |
992 | { | |
a188284c FD |
993 | std::swap(_M_extract(), __x._M_extract()); |
994 | std::swap(_M_ranged_hash(), __x._M_ranged_hash()); | |
3b2524b1 PC |
995 | } |
996 | ||
997 | protected: | |
a188284c FD |
998 | const _ExtractKey& |
999 | _M_extract() const { return _EboExtractKey::_S_cget(*this); } | |
4dad8b49 | 1000 | |
a188284c FD |
1001 | _ExtractKey& |
1002 | _M_extract() { return _EboExtractKey::_S_get(*this); } | |
4dad8b49 | 1003 | |
a188284c FD |
1004 | const _Hash& |
1005 | _M_ranged_hash() const { return _EboHash::_S_cget(*this); } | |
4dad8b49 | 1006 | |
a188284c FD |
1007 | _Hash& |
1008 | _M_ranged_hash() { return _EboHash::_S_get(*this); } | |
3b2524b1 PC |
1009 | }; |
1010 | ||
3b2524b1 PC |
1011 | // No specialization for ranged hash function while caching hash codes. |
1012 | // That combination is meaningless, and trying to do it is an error. | |
7c3e9502 | 1013 | |
4dad8b49 BK |
1014 | /// Specialization: ranged hash function, cache hash codes. This |
1015 | /// combination is meaningless, so we provide only a declaration | |
1016 | /// and no definition. | |
a188284c | 1017 | template<typename _Key, typename _Value, typename _ExtractKey, |
3b2524b1 | 1018 | typename _H1, typename _H2, typename _Hash> |
a188284c | 1019 | struct _Hash_code_base<_Key, _Value, _ExtractKey, _H1, _H2, _Hash, true>; |
3b2524b1 | 1020 | |
4dad8b49 BK |
1021 | /// Specialization: hash function and range-hashing function, no |
1022 | /// caching of hash codes. | |
1023 | /// Provides typedef and accessor required by TR1. | |
a188284c | 1024 | template<typename _Key, typename _Value, typename _ExtractKey, |
3b2524b1 | 1025 | typename _H1, typename _H2> |
a188284c | 1026 | struct _Hash_code_base<_Key, _Value, _ExtractKey, _H1, _H2, |
3b2524b1 | 1027 | _Default_ranged_hash, false> |
346afd84 FD |
1028 | : private _Hashtable_ebo_helper<0, _ExtractKey>, |
1029 | private _Hashtable_ebo_helper<1, _H1>, | |
1030 | private _Hashtable_ebo_helper<2, _H2> | |
3b2524b1 | 1031 | { |
a188284c | 1032 | private: |
4dad8b49 BK |
1033 | typedef _Hashtable_ebo_helper<0, _ExtractKey> _EboExtractKey; |
1034 | typedef _Hashtable_ebo_helper<1, _H1> _EboH1; | |
1035 | typedef _Hashtable_ebo_helper<2, _H2> _EboH2; | |
a188284c FD |
1036 | |
1037 | public: | |
4dad8b49 | 1038 | typedef _H1 hasher; |
3b2524b1 PC |
1039 | |
1040 | hasher | |
1041 | hash_function() const | |
a188284c | 1042 | { return _M_h1(); } |
3b2524b1 | 1043 | |
4dad8b49 BK |
1044 | typedef std::size_t __hash_code; |
1045 | typedef _Hash_node<_Value, false> __node_type; | |
1046 | ||
3b2524b1 | 1047 | protected: |
a188284c FD |
1048 | // We need the default constructor for the local iterators. |
1049 | _Hash_code_base() = default; | |
4dad8b49 | 1050 | |
a188284c | 1051 | _Hash_code_base(const _ExtractKey& __ex, |
3b2524b1 PC |
1052 | const _H1& __h1, const _H2& __h2, |
1053 | const _Default_ranged_hash&) | |
a188284c | 1054 | : _EboExtractKey(__ex), _EboH1(__h1), _EboH2(__h2) { } |
3b2524b1 | 1055 | |
4dad8b49 | 1056 | __hash_code |
3b2524b1 | 1057 | _M_hash_code(const _Key& __k) const |
a188284c | 1058 | { return _M_h1()(__k); } |
7c3e9502 | 1059 | |
3b2524b1 | 1060 | std::size_t |
4dad8b49 | 1061 | _M_bucket_index(const _Key&, __hash_code __c, std::size_t __n) const |
a188284c | 1062 | { return _M_h2()(__c, __n); } |
3b2524b1 PC |
1063 | |
1064 | std::size_t | |
4dad8b49 | 1065 | _M_bucket_index(const __node_type* __p, |
3b2524b1 | 1066 | std::size_t __n) const |
a188284c | 1067 | { return _M_h2()(_M_h1()(_M_extract()(__p->_M_v)), __n); } |
3b2524b1 PC |
1068 | |
1069 | void | |
4dad8b49 | 1070 | _M_store_code(__node_type*, __hash_code) const |
3b2524b1 PC |
1071 | { } |
1072 | ||
1073 | void | |
4dad8b49 | 1074 | _M_copy_code(__node_type*, const __node_type*) const |
3b2524b1 PC |
1075 | { } |
1076 | ||
1077 | void | |
1078 | _M_swap(_Hash_code_base& __x) | |
1079 | { | |
a188284c FD |
1080 | std::swap(_M_extract(), __x._M_extract()); |
1081 | std::swap(_M_h1(), __x._M_h1()); | |
1082 | std::swap(_M_h2(), __x._M_h2()); | |
3b2524b1 PC |
1083 | } |
1084 | ||
a188284c FD |
1085 | const _ExtractKey& |
1086 | _M_extract() const { return _EboExtractKey::_S_cget(*this); } | |
4dad8b49 | 1087 | |
a188284c FD |
1088 | _ExtractKey& |
1089 | _M_extract() { return _EboExtractKey::_S_get(*this); } | |
4dad8b49 | 1090 | |
a188284c FD |
1091 | const _H1& |
1092 | _M_h1() const { return _EboH1::_S_cget(*this); } | |
4dad8b49 | 1093 | |
a188284c FD |
1094 | _H1& |
1095 | _M_h1() { return _EboH1::_S_get(*this); } | |
4dad8b49 | 1096 | |
a188284c FD |
1097 | const _H2& |
1098 | _M_h2() const { return _EboH2::_S_cget(*this); } | |
4dad8b49 | 1099 | |
a188284c FD |
1100 | _H2& |
1101 | _M_h2() { return _EboH2::_S_get(*this); } | |
3b2524b1 PC |
1102 | }; |
1103 | ||
4dad8b49 BK |
1104 | /// Specialization: hash function and range-hashing function, |
1105 | /// caching hash codes. H is provided but ignored. Provides | |
1106 | /// typedef and accessor required by TR1. | |
a188284c | 1107 | template<typename _Key, typename _Value, typename _ExtractKey, |
3b2524b1 | 1108 | typename _H1, typename _H2> |
a188284c | 1109 | struct _Hash_code_base<_Key, _Value, _ExtractKey, _H1, _H2, |
3b2524b1 | 1110 | _Default_ranged_hash, true> |
346afd84 FD |
1111 | : private _Hashtable_ebo_helper<0, _ExtractKey>, |
1112 | private _Hashtable_ebo_helper<1, _H1>, | |
1113 | private _Hashtable_ebo_helper<2, _H2> | |
3b2524b1 | 1114 | { |
a188284c | 1115 | private: |
4dad8b49 BK |
1116 | typedef _Hashtable_ebo_helper<0, _ExtractKey> _EboExtractKey; |
1117 | typedef _Hashtable_ebo_helper<1, _H1> _EboH1; | |
1118 | typedef _Hashtable_ebo_helper<2, _H2> _EboH2; | |
a188284c FD |
1119 | |
1120 | public: | |
4dad8b49 | 1121 | typedef _H1 hasher; |
7c3e9502 | 1122 | |
3b2524b1 PC |
1123 | hasher |
1124 | hash_function() const | |
a188284c | 1125 | { return _M_h1(); } |
3b2524b1 | 1126 | |
4dad8b49 BK |
1127 | typedef std::size_t __hash_code; |
1128 | typedef _Hash_node<_Value, true> __node_type; | |
1129 | ||
3b2524b1 | 1130 | protected: |
a188284c | 1131 | _Hash_code_base(const _ExtractKey& __ex, |
3b2524b1 PC |
1132 | const _H1& __h1, const _H2& __h2, |
1133 | const _Default_ranged_hash&) | |
a188284c | 1134 | : _EboExtractKey(__ex), _EboH1(__h1), _EboH2(__h2) { } |
3b2524b1 | 1135 | |
4dad8b49 | 1136 | __hash_code |
3b2524b1 | 1137 | _M_hash_code(const _Key& __k) const |
a188284c | 1138 | { return _M_h1()(__k); } |
7c3e9502 | 1139 | |
3b2524b1 | 1140 | std::size_t |
4dad8b49 | 1141 | _M_bucket_index(const _Key&, __hash_code __c, |
3b2524b1 | 1142 | std::size_t __n) const |
a188284c | 1143 | { return _M_h2()(__c, __n); } |
3b2524b1 PC |
1144 | |
1145 | std::size_t | |
4dad8b49 | 1146 | _M_bucket_index(const __node_type* __p, std::size_t __n) const |
a188284c | 1147 | { return _M_h2()(__p->_M_hash_code, __n); } |
3b2524b1 PC |
1148 | |
1149 | void | |
4dad8b49 | 1150 | _M_store_code(__node_type* __n, __hash_code __c) const |
3b2524b1 PC |
1151 | { __n->_M_hash_code = __c; } |
1152 | ||
1153 | void | |
4dad8b49 | 1154 | _M_copy_code(__node_type* __to, const __node_type* __from) const |
3b2524b1 PC |
1155 | { __to->_M_hash_code = __from->_M_hash_code; } |
1156 | ||
1157 | void | |
1158 | _M_swap(_Hash_code_base& __x) | |
1159 | { | |
a188284c FD |
1160 | std::swap(_M_extract(), __x._M_extract()); |
1161 | std::swap(_M_h1(), __x._M_h1()); | |
1162 | std::swap(_M_h2(), __x._M_h2()); | |
3b2524b1 | 1163 | } |
7c3e9502 | 1164 | |
a188284c FD |
1165 | const _ExtractKey& |
1166 | _M_extract() const { return _EboExtractKey::_S_cget(*this); } | |
4dad8b49 | 1167 | |
a188284c FD |
1168 | _ExtractKey& |
1169 | _M_extract() { return _EboExtractKey::_S_get(*this); } | |
4dad8b49 | 1170 | |
a188284c FD |
1171 | const _H1& |
1172 | _M_h1() const { return _EboH1::_S_cget(*this); } | |
4dad8b49 | 1173 | |
a188284c FD |
1174 | _H1& |
1175 | _M_h1() { return _EboH1::_S_get(*this); } | |
4dad8b49 | 1176 | |
a188284c FD |
1177 | const _H2& |
1178 | _M_h2() const { return _EboH2::_S_cget(*this); } | |
4dad8b49 | 1179 | |
a188284c FD |
1180 | _H2& |
1181 | _M_h2() { return _EboH2::_S_get(*this); } | |
1182 | }; | |
1183 | ||
4dad8b49 BK |
1184 | /** |
1185 | * Primary class template _Equal_helper. | |
1186 | * | |
1187 | */ | |
a188284c FD |
1188 | template <typename _Key, typename _Value, typename _ExtractKey, |
1189 | typename _Equal, typename _HashCodeType, | |
1190 | bool __cache_hash_code> | |
1191 | struct _Equal_helper; | |
1192 | ||
4dad8b49 | 1193 | /// Specialization. |
a188284c FD |
1194 | template<typename _Key, typename _Value, typename _ExtractKey, |
1195 | typename _Equal, typename _HashCodeType> | |
1196 | struct _Equal_helper<_Key, _Value, _ExtractKey, _Equal, _HashCodeType, true> | |
1197 | { | |
1198 | static bool | |
1199 | _S_equals(const _Equal& __eq, const _ExtractKey& __extract, | |
4dad8b49 BK |
1200 | const _Key& __k, _HashCodeType __c, _Hash_node<_Value, true>* __n) |
1201 | { return __c == __n->_M_hash_code && __eq(__k, __extract(__n->_M_v)); } | |
a188284c FD |
1202 | }; |
1203 | ||
4dad8b49 | 1204 | /// Specialization. |
a188284c FD |
1205 | template<typename _Key, typename _Value, typename _ExtractKey, |
1206 | typename _Equal, typename _HashCodeType> | |
1207 | struct _Equal_helper<_Key, _Value, _ExtractKey, _Equal, _HashCodeType, false> | |
1208 | { | |
1209 | static bool | |
1210 | _S_equals(const _Equal& __eq, const _ExtractKey& __extract, | |
4dad8b49 | 1211 | const _Key& __k, _HashCodeType, _Hash_node<_Value, false>* __n) |
a188284c FD |
1212 | { return __eq(__k, __extract(__n->_M_v)); } |
1213 | }; | |
1214 | ||
a188284c | 1215 | |
4dad8b49 BK |
1216 | /** |
1217 | * Primary class template _Local_iterator_base. | |
1218 | * | |
1219 | * Base class for local iterators, used to iterate within a bucket | |
1220 | * but not between buckets. | |
1221 | */ | |
a188284c FD |
1222 | template<typename _Key, typename _Value, typename _ExtractKey, |
1223 | typename _H1, typename _H2, typename _Hash, | |
1224 | bool __cache_hash_code> | |
1225 | struct _Local_iterator_base; | |
1226 | ||
4dad8b49 | 1227 | /// Specialization. |
a188284c FD |
1228 | template<typename _Key, typename _Value, typename _ExtractKey, |
1229 | typename _H1, typename _H2, typename _Hash> | |
1230 | struct _Local_iterator_base<_Key, _Value, _ExtractKey, | |
1231 | _H1, _H2, _Hash, true> | |
346afd84 | 1232 | : private _H2 |
a188284c FD |
1233 | { |
1234 | _Local_iterator_base() = default; | |
1235 | _Local_iterator_base(_Hash_node<_Value, true>* __p, | |
1236 | std::size_t __bkt, std::size_t __bkt_count) | |
1237 | : _M_cur(__p), _M_bucket(__bkt), _M_bucket_count(__bkt_count) { } | |
1238 | ||
1239 | void | |
1240 | _M_incr() | |
1241 | { | |
f86b266c | 1242 | _M_cur = _M_cur->_M_next(); |
a188284c FD |
1243 | if (_M_cur) |
1244 | { | |
1245 | std::size_t __bkt = _M_h2()(_M_cur->_M_hash_code, _M_bucket_count); | |
1246 | if (__bkt != _M_bucket) | |
1247 | _M_cur = nullptr; | |
1248 | } | |
1249 | } | |
1250 | ||
1251 | const _H2& _M_h2() const | |
1252 | { return *this; } | |
1253 | ||
1254 | _Hash_node<_Value, true>* _M_cur; | |
1255 | std::size_t _M_bucket; | |
1256 | std::size_t _M_bucket_count; | |
1257 | }; | |
1258 | ||
4dad8b49 | 1259 | /// Specialization. |
a188284c FD |
1260 | template<typename _Key, typename _Value, typename _ExtractKey, |
1261 | typename _H1, typename _H2, typename _Hash> | |
1262 | struct _Local_iterator_base<_Key, _Value, _ExtractKey, | |
1263 | _H1, _H2, _Hash, false> | |
346afd84 FD |
1264 | : private _Hash_code_base<_Key, _Value, _ExtractKey, |
1265 | _H1, _H2, _Hash, false> | |
a188284c FD |
1266 | { |
1267 | _Local_iterator_base() = default; | |
1268 | _Local_iterator_base(_Hash_node<_Value, false>* __p, | |
1269 | std::size_t __bkt, std::size_t __bkt_count) | |
1270 | : _M_cur(__p), _M_bucket(__bkt), _M_bucket_count(__bkt_count) { } | |
1271 | ||
1272 | void | |
1273 | _M_incr() | |
1274 | { | |
f86b266c | 1275 | _M_cur = _M_cur->_M_next(); |
a188284c FD |
1276 | if (_M_cur) |
1277 | { | |
1278 | std::size_t __bkt = this->_M_bucket_index(_M_cur, _M_bucket_count); | |
1279 | if (__bkt != _M_bucket) | |
1280 | _M_cur = nullptr; | |
1281 | } | |
1282 | } | |
1283 | ||
1284 | _Hash_node<_Value, false>* _M_cur; | |
1285 | std::size_t _M_bucket; | |
1286 | std::size_t _M_bucket_count; | |
1287 | }; | |
1288 | ||
1289 | template<typename _Key, typename _Value, typename _ExtractKey, | |
1290 | typename _H1, typename _H2, typename _Hash, bool __cache> | |
1291 | inline bool | |
1292 | operator==(const _Local_iterator_base<_Key, _Value, _ExtractKey, | |
1293 | _H1, _H2, _Hash, __cache>& __x, | |
1294 | const _Local_iterator_base<_Key, _Value, _ExtractKey, | |
1295 | _H1, _H2, _Hash, __cache>& __y) | |
1296 | { return __x._M_cur == __y._M_cur; } | |
1297 | ||
1298 | template<typename _Key, typename _Value, typename _ExtractKey, | |
1299 | typename _H1, typename _H2, typename _Hash, bool __cache> | |
1300 | inline bool | |
1301 | operator!=(const _Local_iterator_base<_Key, _Value, _ExtractKey, | |
1302 | _H1, _H2, _Hash, __cache>& __x, | |
1303 | const _Local_iterator_base<_Key, _Value, _ExtractKey, | |
1304 | _H1, _H2, _Hash, __cache>& __y) | |
1305 | { return __x._M_cur != __y._M_cur; } | |
1306 | ||
4dad8b49 | 1307 | /// local iterators |
a188284c FD |
1308 | template<typename _Key, typename _Value, typename _ExtractKey, |
1309 | typename _H1, typename _H2, typename _Hash, | |
1310 | bool __constant_iterators, bool __cache> | |
1311 | struct _Local_iterator | |
1312 | : public _Local_iterator_base<_Key, _Value, _ExtractKey, | |
1313 | _H1, _H2, _Hash, __cache> | |
1314 | { | |
1315 | typedef _Value value_type; | |
1316 | typedef typename std::conditional<__constant_iterators, | |
1317 | const _Value*, _Value*>::type | |
1318 | pointer; | |
1319 | typedef typename std::conditional<__constant_iterators, | |
1320 | const _Value&, _Value&>::type | |
1321 | reference; | |
1322 | typedef std::ptrdiff_t difference_type; | |
1323 | typedef std::forward_iterator_tag iterator_category; | |
1324 | ||
1325 | _Local_iterator() = default; | |
1326 | ||
1327 | explicit | |
1328 | _Local_iterator(_Hash_node<_Value, __cache>* __p, | |
1329 | std::size_t __bkt, std::size_t __bkt_count) | |
1330 | : _Local_iterator_base<_Key, _Value, _ExtractKey, _H1, _H2, _Hash, | |
1331 | __cache>(__p, __bkt, __bkt_count) | |
1332 | { } | |
1333 | ||
1334 | reference | |
1335 | operator*() const | |
1336 | { return this->_M_cur->_M_v; } | |
1337 | ||
1338 | pointer | |
1339 | operator->() const | |
1340 | { return std::__addressof(this->_M_cur->_M_v); } | |
1341 | ||
1342 | _Local_iterator& | |
1343 | operator++() | |
1344 | { | |
1345 | this->_M_incr(); | |
1346 | return *this; | |
1347 | } | |
1348 | ||
1349 | _Local_iterator | |
1350 | operator++(int) | |
1351 | { | |
1352 | _Local_iterator __tmp(*this); | |
1353 | this->_M_incr(); | |
1354 | return __tmp; | |
1355 | } | |
1356 | }; | |
1357 | ||
4dad8b49 | 1358 | /// local const_iterators |
a188284c FD |
1359 | template<typename _Key, typename _Value, typename _ExtractKey, |
1360 | typename _H1, typename _H2, typename _Hash, | |
1361 | bool __constant_iterators, bool __cache> | |
1362 | struct _Local_const_iterator | |
1363 | : public _Local_iterator_base<_Key, _Value, _ExtractKey, | |
1364 | _H1, _H2, _Hash, __cache> | |
1365 | { | |
1366 | typedef _Value value_type; | |
1367 | typedef const _Value* pointer; | |
1368 | typedef const _Value& reference; | |
1369 | typedef std::ptrdiff_t difference_type; | |
1370 | typedef std::forward_iterator_tag iterator_category; | |
1371 | ||
1372 | _Local_const_iterator() = default; | |
1373 | ||
1374 | explicit | |
1375 | _Local_const_iterator(_Hash_node<_Value, __cache>* __p, | |
1376 | std::size_t __bkt, std::size_t __bkt_count) | |
1377 | : _Local_iterator_base<_Key, _Value, _ExtractKey, _H1, _H2, _Hash, | |
1378 | __cache>(__p, __bkt, __bkt_count) | |
1379 | { } | |
1380 | ||
1381 | _Local_const_iterator(const _Local_iterator<_Key, _Value, _ExtractKey, | |
1382 | _H1, _H2, _Hash, | |
1383 | __constant_iterators, | |
1384 | __cache>& __x) | |
1385 | : _Local_iterator_base<_Key, _Value, _ExtractKey, _H1, _H2, _Hash, | |
1386 | __cache>(__x._M_cur, __x._M_bucket, | |
1387 | __x._M_bucket_count) | |
1388 | { } | |
1389 | ||
1390 | reference | |
1391 | operator*() const | |
1392 | { return this->_M_cur->_M_v; } | |
1393 | ||
1394 | pointer | |
1395 | operator->() const | |
1396 | { return std::__addressof(this->_M_cur->_M_v); } | |
1397 | ||
1398 | _Local_const_iterator& | |
1399 | operator++() | |
1400 | { | |
1401 | this->_M_incr(); | |
1402 | return *this; | |
1403 | } | |
1404 | ||
1405 | _Local_const_iterator | |
1406 | operator++(int) | |
1407 | { | |
1408 | _Local_const_iterator __tmp(*this); | |
1409 | this->_M_incr(); | |
1410 | return __tmp; | |
1411 | } | |
3b2524b1 | 1412 | }; |
5dc22714 | 1413 | |
4dad8b49 BK |
1414 | /** |
1415 | * Primary class template _Hashtable_base. | |
1416 | * | |
1417 | * Base class for _Hashtable. Helper class adding management of | |
1418 | * _Equal functor to _Hash_code_base type. | |
1419 | */ | |
1420 | template<typename _Key, typename _Value, | |
1421 | typename _ExtractKey, typename _Equal, | |
1422 | typename _H1, typename _H2, typename _Hash, typename _Traits> | |
1423 | struct _Hashtable_base | |
1424 | : public _Hash_code_base<_Key, _Value, _ExtractKey, _H1, _H2, _Hash, | |
1425 | _Traits::__hash_cached::value>, | |
1426 | private _Hashtable_ebo_helper<0, _Equal> | |
1427 | { | |
1428 | public: | |
1429 | typedef _Key key_type; | |
1430 | typedef _Value value_type; | |
1431 | typedef _Equal key_equal; | |
1432 | typedef std::size_t size_type; | |
1433 | typedef std::ptrdiff_t difference_type; | |
1434 | ||
1435 | using __traits_type = _Traits; | |
1436 | using __hash_cached = typename __traits_type::__hash_cached; | |
1437 | using __constant_iterators = typename __traits_type::__constant_iterators; | |
1438 | using __unique_keys = typename __traits_type::__unique_keys; | |
1439 | ||
1440 | using __hash_code_base = _Hash_code_base<_Key, _Value, _ExtractKey, | |
1441 | _H1, _H2, _Hash, | |
1442 | __hash_cached::value>; | |
1443 | ||
1444 | using __hash_code = typename __hash_code_base::__hash_code; | |
1445 | using __node_type = typename __hash_code_base::__node_type; | |
1446 | ||
1447 | using iterator = __detail::_Node_iterator<value_type, | |
1448 | __constant_iterators::value, | |
1449 | __hash_cached::value>; | |
1450 | ||
1451 | using const_iterator = __detail::_Node_const_iterator<value_type, | |
1452 | __constant_iterators::value, | |
1453 | __hash_cached::value>; | |
1454 | ||
1455 | using local_iterator = __detail::_Local_iterator<key_type, value_type, | |
1456 | _ExtractKey, _H1, _H2, _Hash, | |
1457 | __constant_iterators::value, | |
1458 | __hash_cached::value>; | |
1459 | ||
1460 | using const_local_iterator = __detail::_Local_const_iterator<key_type, | |
1461 | value_type, | |
1462 | _ExtractKey, _H1, _H2, _Hash, | |
1463 | __constant_iterators::value, | |
1464 | __hash_cached::value>; | |
1465 | ||
1466 | using __ireturn_type = typename std::conditional<__unique_keys::value, | |
1467 | std::pair<iterator, bool>, | |
1468 | iterator>::type; | |
1469 | ||
1470 | using __iconv_type = typename std::conditional<__unique_keys::value, | |
1471 | std::_Select1st<__ireturn_type>, | |
1472 | std::_Identity<__ireturn_type> | |
1473 | >::type; | |
1474 | private: | |
1475 | using _EqualEBO = _Hashtable_ebo_helper<0, _Equal>; | |
1476 | using _EqualHelper = _Equal_helper<_Key, _Value, _ExtractKey, _Equal, | |
1477 | __hash_code, __hash_cached::value>; | |
1478 | ||
1479 | protected: | |
1480 | using __node_base = __detail::_Hash_node_base; | |
1481 | using __bucket_type = __node_base*; | |
1482 | ||
1483 | _Hashtable_base(const _ExtractKey& __ex, const _H1& __h1, const _H2& __h2, | |
1484 | const _Hash& __hash, const _Equal& __eq) | |
1485 | : __hash_code_base(__ex, __h1, __h2, __hash), _EqualEBO(__eq) | |
1486 | { } | |
1487 | ||
1488 | bool | |
1489 | _M_equals(const _Key& __k, __hash_code __c, __node_type* __n) const | |
1490 | { | |
1491 | return _EqualHelper::_S_equals(_M_eq(), this->_M_extract(), | |
1492 | __k, __c, __n); | |
1493 | } | |
1494 | ||
1495 | void | |
1496 | _M_swap(_Hashtable_base& __x) | |
1497 | { | |
1498 | __hash_code_base::_M_swap(__x); | |
1499 | std::swap(_M_eq(), __x._M_eq()); | |
1500 | } | |
1501 | ||
1502 | const _Equal& | |
1503 | _M_eq() const { return _EqualEBO::_S_cget(*this); } | |
1504 | ||
1505 | _Equal& | |
1506 | _M_eq() { return _EqualEBO::_S_get(*this); } | |
1507 | }; | |
5dc22714 | 1508 | |
4dad8b49 BK |
1509 | /** |
1510 | * struct _Equality_base. | |
1511 | * | |
1512 | * Common types and functions for class _Equality. | |
1513 | */ | |
1514 | struct _Equality_base | |
1515 | { | |
1516 | protected: | |
1517 | template<typename _Uiterator> | |
1518 | static bool | |
1519 | _S_is_permutation(_Uiterator, _Uiterator, _Uiterator); | |
1520 | }; | |
5dc22714 | 1521 | |
4dad8b49 BK |
1522 | // See std::is_permutation in N3068. |
1523 | template<typename _Uiterator> | |
1524 | bool | |
1525 | _Equality_base:: | |
1526 | _S_is_permutation(_Uiterator __first1, _Uiterator __last1, | |
1527 | _Uiterator __first2) | |
5dc22714 | 1528 | { |
4dad8b49 BK |
1529 | for (; __first1 != __last1; ++__first1, ++__first2) |
1530 | if (!(*__first1 == *__first2)) | |
1531 | break; | |
1532 | ||
1533 | if (__first1 == __last1) | |
1534 | return true; | |
1535 | ||
1536 | _Uiterator __last2 = __first2; | |
1537 | std::advance(__last2, std::distance(__first1, __last1)); | |
1538 | ||
1539 | for (_Uiterator __it1 = __first1; __it1 != __last1; ++__it1) | |
1540 | { | |
1541 | _Uiterator __tmp = __first1; | |
1542 | while (__tmp != __it1 && !bool(*__tmp == *__it1)) | |
1543 | ++__tmp; | |
1544 | ||
1545 | // We've seen this one before. | |
1546 | if (__tmp != __it1) | |
1547 | continue; | |
1548 | ||
1549 | std::ptrdiff_t __n2 = 0; | |
1550 | for (__tmp = __first2; __tmp != __last2; ++__tmp) | |
1551 | if (*__tmp == *__it1) | |
1552 | ++__n2; | |
1553 | ||
1554 | if (!__n2) | |
1555 | return false; | |
1556 | ||
1557 | std::ptrdiff_t __n1 = 0; | |
1558 | for (__tmp = __it1; __tmp != __last1; ++__tmp) | |
1559 | if (*__tmp == *__it1) | |
1560 | ++__n1; | |
1561 | ||
1562 | if (__n1 != __n2) | |
1563 | return false; | |
1564 | } | |
1565 | return true; | |
1566 | } | |
1567 | ||
1568 | /** | |
1569 | * Primary class template _Equality. | |
1570 | * | |
1571 | * This is for implementing equality comparison for unordered | |
1572 | * containers, per N3068, by John Lakos and Pablo Halpern. | |
1573 | * Algorithmically, we follow closely the reference implementations | |
1574 | * therein. | |
1575 | */ | |
1576 | template<typename _Key, typename _Value, typename _Alloc, | |
1577 | typename _ExtractKey, typename _Equal, | |
1578 | typename _H1, typename _H2, typename _Hash, | |
1579 | typename _RehashPolicy, typename _Traits, | |
1580 | bool _Unique_keys = _Traits::__unique_keys::value> | |
1581 | struct _Equality; | |
1582 | ||
1583 | /// Specialization. | |
1584 | template<typename _Key, typename _Value, typename _Alloc, | |
1585 | typename _ExtractKey, typename _Equal, | |
1586 | typename _H1, typename _H2, typename _Hash, | |
1587 | typename _RehashPolicy, typename _Traits> | |
1588 | struct _Equality<_Key, _Value, _Alloc, _ExtractKey, _Equal, | |
1589 | _H1, _H2, _Hash, _RehashPolicy, _Traits, true> | |
1590 | { | |
1591 | using __hashtable = _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, | |
1592 | _H1, _H2, _Hash, _RehashPolicy, _Traits>; | |
1593 | ||
1594 | bool | |
1595 | _M_equal(const __hashtable&) const; | |
5dc22714 PC |
1596 | }; |
1597 | ||
4dad8b49 BK |
1598 | template<typename _Key, typename _Value, typename _Alloc, |
1599 | typename _ExtractKey, typename _Equal, | |
1600 | typename _H1, typename _H2, typename _Hash, | |
1601 | typename _RehashPolicy, typename _Traits> | |
5dc22714 | 1602 | bool |
4dad8b49 BK |
1603 | _Equality<_Key, _Value, _Alloc, _ExtractKey, _Equal, |
1604 | _H1, _H2, _Hash, _RehashPolicy, _Traits, true>:: | |
1605 | _M_equal(const __hashtable& __other) const | |
5dc22714 | 1606 | { |
4dad8b49 | 1607 | const __hashtable* __this = static_cast<const __hashtable*>(this); |
5dc22714 PC |
1608 | |
1609 | if (__this->size() != __other.size()) | |
1610 | return false; | |
1611 | ||
1612 | for (auto __itx = __this->begin(); __itx != __this->end(); ++__itx) | |
1613 | { | |
1614 | const auto __ity = __other.find(_ExtractKey()(*__itx)); | |
d1503908 | 1615 | if (__ity == __other.end() || !bool(*__ity == *__itx)) |
5dc22714 PC |
1616 | return false; |
1617 | } | |
1618 | return true; | |
1619 | } | |
1620 | ||
4dad8b49 BK |
1621 | /// Specialization. |
1622 | template<typename _Key, typename _Value, typename _Alloc, | |
1623 | typename _ExtractKey, typename _Equal, | |
1624 | typename _H1, typename _H2, typename _Hash, | |
1625 | typename _RehashPolicy, typename _Traits> | |
1626 | struct _Equality<_Key, _Value, _Alloc, _ExtractKey, _Equal, | |
1627 | _H1, _H2, _Hash, _RehashPolicy, _Traits, false> | |
1628 | : public _Equality_base | |
5dc22714 | 1629 | { |
4dad8b49 BK |
1630 | using __hashtable = _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, |
1631 | _H1, _H2, _Hash, _RehashPolicy, _Traits>; | |
5dc22714 | 1632 | |
5dc22714 | 1633 | bool |
4dad8b49 BK |
1634 | _M_equal(const __hashtable&) const; |
1635 | }; | |
5dc22714 | 1636 | |
4dad8b49 BK |
1637 | template<typename _Key, typename _Value, typename _Alloc, |
1638 | typename _ExtractKey, typename _Equal, | |
1639 | typename _H1, typename _H2, typename _Hash, | |
1640 | typename _RehashPolicy, typename _Traits> | |
5dc22714 | 1641 | bool |
4dad8b49 BK |
1642 | _Equality<_Key, _Value, _Alloc, _ExtractKey, _Equal, |
1643 | _H1, _H2, _Hash, _RehashPolicy, _Traits, false>:: | |
1644 | _M_equal(const __hashtable& __other) const | |
5dc22714 | 1645 | { |
4dad8b49 | 1646 | const __hashtable* __this = static_cast<const __hashtable*>(this); |
5dc22714 PC |
1647 | |
1648 | if (__this->size() != __other.size()) | |
1649 | return false; | |
1650 | ||
1651 | for (auto __itx = __this->begin(); __itx != __this->end();) | |
1652 | { | |
1653 | const auto __xrange = __this->equal_range(_ExtractKey()(*__itx)); | |
1654 | const auto __yrange = __other.equal_range(_ExtractKey()(*__itx)); | |
1655 | ||
1656 | if (std::distance(__xrange.first, __xrange.second) | |
1657 | != std::distance(__yrange.first, __yrange.second)) | |
1658 | return false; | |
1659 | ||
4dad8b49 | 1660 | if (!_S_is_permutation(__xrange.first, __xrange.second, |
5dc22714 PC |
1661 | __yrange.first)) |
1662 | return false; | |
1663 | ||
1664 | __itx = __xrange.second; | |
1665 | } | |
1666 | return true; | |
1667 | } | |
7c3e9502 | 1668 | |
4dad8b49 | 1669 | //@} hashtable-detail |
12ffa228 BK |
1670 | _GLIBCXX_END_NAMESPACE_VERSION |
1671 | } // namespace __detail | |
1672 | } // namespace std | |
3b2524b1 PC |
1673 | |
1674 | #endif // _HASHTABLE_POLICY_H |