1// Internal policy header for unordered_set and unordered_map -*- C++ -*- 
2 
3// Copyright (C) 2010-2019 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 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. 
27 * Do not attempt to use it directly. 
28 * @headername{unordered_map,unordered_set} 
29 */ 
30 
31#ifndef _HASHTABLE_POLICY_H 
32#define _HASHTABLE_POLICY_H 1 
33 
34#include <tuple> // for std::tuple, std::forward_as_tuple 
35#include <limits> // for std::numeric_limits 
36#include <bits/stl_algobase.h> // for std::min. 
37 
38namespace std _GLIBCXX_VISIBILITY(default) 
39{ 
40_GLIBCXX_BEGIN_NAMESPACE_VERSION 
41 
42 template<typename _Key, typename _Value, typename _Alloc, 
43 typename _ExtractKey, typename _Equal, 
44 typename _H1, typename _H2, typename _Hash, 
45 typename _RehashPolicy, typename _Traits> 
46 class _Hashtable; 
47 
48namespace __detail 
49{ 
50 /** 
51 * @defgroup hashtable-detail Base and Implementation Classes 
52 * @ingroup unordered_associative_containers 
53 * @{ 
54 */ 
55 template<typename _Key, typename _Value, 
56 typename _ExtractKey, typename _Equal, 
57 typename _H1, typename _H2, typename _Hash, typename _Traits> 
58 struct _Hashtable_base; 
59 
60 // Helper function: return distance(first, last) for forward 
61 // iterators, or 0/1 for input iterators. 
62 template<class _Iterator> 
63 inline typename std::iterator_traits<_Iterator>::difference_type 
64 __distance_fw(_Iterator __first, _Iterator __last, 
65 std::input_iterator_tag) 
66 { return __first != __last ? 1 : 0; } 
67 
68 template<class _Iterator> 
69 inline typename std::iterator_traits<_Iterator>::difference_type 
70 __distance_fw(_Iterator __first, _Iterator __last, 
71 std::forward_iterator_tag) 
72 { return std::distance(__first, __last); } 
73 
74 template<class _Iterator> 
75 inline typename std::iterator_traits<_Iterator>::difference_type 
76 __distance_fw(_Iterator __first, _Iterator __last) 
77 { return __distance_fw(__first, __last, 
78 std::__iterator_category(__first)); } 
79 
80 struct _Identity 
81 { 
82 template<typename _Tp> 
83 _Tp&& 
84 operator()(_Tp&& __x) const 
85 { return std::forward<_Tp>(__x); } 
86 }; 
87 
88 struct _Select1st 
89 { 
90 template<typename _Tp> 
91 auto 
92 operator()(_Tp&& __x) const 
93 -> decltype(std::get<0>(std::forward<_Tp>(__x))) 
94 { return std::get<0>(std::forward<_Tp>(__x)); } 
95 }; 
96 
97 template<typename _NodeAlloc> 
98 struct _Hashtable_alloc; 
99 
100 // Functor recycling a pool of nodes and using allocation once the pool is 
101 // empty. 
102 template<typename _NodeAlloc> 
103 struct _ReuseOrAllocNode 
104 { 
105 private: 
106 using __node_alloc_type = _NodeAlloc; 
107 using __hashtable_alloc = _Hashtable_alloc<__node_alloc_type>; 
108 using __node_alloc_traits = 
109 typename __hashtable_alloc::__node_alloc_traits; 
110 using __node_type = typename __hashtable_alloc::__node_type; 
111 
112 public: 
113 _ReuseOrAllocNode(__node_type* __nodes, __hashtable_alloc& __h) 
114 : _M_nodes(__nodes), _M_h(__h) { } 
115 _ReuseOrAllocNode(const _ReuseOrAllocNode&) = delete; 
116 
117 ~_ReuseOrAllocNode() 
118 { _M_h._M_deallocate_nodes(_M_nodes); } 
119 
120 template<typename _Arg> 
121 __node_type* 
122 operator()(_Arg&& __arg) const 
123 { 
124 if (_M_nodes) 
125 { 
126 __node_type* __node = _M_nodes; 
127 _M_nodes = _M_nodes->_M_next(); 
128 __node->_M_nxt = nullptr; 
129 auto& __a = _M_h._M_node_allocator(); 
130 __node_alloc_traits::destroy(__a, __node->_M_valptr()); 
131 __try 
132 { 
133 __node_alloc_traits::construct(__a, __node->_M_valptr(), 
134 std::forward<_Arg>(__arg)); 
135 } 
136 __catch(...) 
137 { 
138 _M_h._M_deallocate_node_ptr(__node); 
139 __throw_exception_again; 
140 } 
141 return __node; 
142 } 
143 return _M_h._M_allocate_node(std::forward<_Arg>(__arg)); 
144 } 
145 
146 private: 
147 mutable __node_type* _M_nodes; 
148 __hashtable_alloc& _M_h; 
149 }; 
150 
151 // Functor similar to the previous one but without any pool of nodes to 
152 // recycle. 
153 template<typename _NodeAlloc> 
154 struct _AllocNode 
155 { 
156 private: 
157 using __hashtable_alloc = _Hashtable_alloc<_NodeAlloc>; 
158 using __node_type = typename __hashtable_alloc::__node_type; 
159 
160 public: 
161 _AllocNode(__hashtable_alloc& __h) 
162 : _M_h(__h) { } 
163 
164 template<typename _Arg> 
165 __node_type* 
166 operator()(_Arg&& __arg) const 
167 { return _M_h._M_allocate_node(std::forward<_Arg>(__arg)); } 
168 
169 private: 
170 __hashtable_alloc& _M_h; 
171 }; 
172 
173 // Auxiliary types used for all instantiations of _Hashtable nodes 
174 // and iterators. 
175 
176 /** 
177 * struct _Hashtable_traits 
178 * 
179 * Important traits for hash tables. 
180 * 
181 * @tparam _Cache_hash_code Boolean value. True if the value of 
182 * the hash function is stored along with the value. This is a 
183 * time-space tradeoff. Storing it may improve lookup speed by 
184 * reducing the number of times we need to call the _Equal 
185 * function. 
186 * 
187 * @tparam _Constant_iterators Boolean value. True if iterator and 
188 * const_iterator are both constant iterator types. This is true 
189 * for unordered_set and unordered_multiset, false for 
190 * unordered_map and unordered_multimap. 
191 * 
192 * @tparam _Unique_keys Boolean value. True if the return value 
193 * of _Hashtable::count(k) is always at most one, false if it may 
194 * be an arbitrary number. This is true for unordered_set and 
195 * unordered_map, false for unordered_multiset and 
196 * unordered_multimap. 
197 */ 
198 template<bool _Cache_hash_code, bool _Constant_iterators, bool _Unique_keys> 
199 struct _Hashtable_traits 
200 { 
201 using __hash_cached = __bool_constant<_Cache_hash_code>; 
202 using __constant_iterators = __bool_constant<_Constant_iterators>; 
203 using __unique_keys = __bool_constant<_Unique_keys>; 
204 }; 
205 
206 /** 
207 * struct _Hash_node_base 
208 * 
209 * Nodes, used to wrap elements stored in the hash table. A policy 
210 * template parameter of class template _Hashtable controls whether 
211 * nodes also store a hash code. In some cases (e.g. strings) this 
212 * may be a performance win. 
213 */ 
214 struct _Hash_node_base 
215 { 
216 _Hash_node_base* _M_nxt; 
217 
218 _Hash_node_base() noexcept : _M_nxt() { } 
219 
220 _Hash_node_base(_Hash_node_base* __next) noexcept : _M_nxt(__next) { } 
221 }; 
222 
223 /** 
224 * struct _Hash_node_value_base 
225 * 
226 * Node type with the value to store. 
227 */ 
228 template<typename _Value> 
229 struct _Hash_node_value_base : _Hash_node_base 
230 { 
231 typedef _Value value_type; 
232 
233 __gnu_cxx::__aligned_buffer<_Value> _M_storage; 
234 
235 _Value* 
236 _M_valptr() noexcept 
237 { return _M_storage._M_ptr(); } 
238 
239 const _Value* 
240 _M_valptr() const noexcept 
241 { return _M_storage._M_ptr(); } 
242 
243 _Value& 
244 _M_v() noexcept 
245 { return *_M_valptr(); } 
246 
247 const _Value& 
248 _M_v() const noexcept 
249 { return *_M_valptr(); } 
250 }; 
251 
252 /** 
253 * Primary template struct _Hash_node. 
254 */ 
255 template<typename _Value, bool _Cache_hash_code> 
256 struct _Hash_node; 
257 
258 /** 
259 * Specialization for nodes with caches, struct _Hash_node. 
260 * 
261 * Base class is __detail::_Hash_node_value_base. 
262 */ 
263 template<typename _Value> 
264 struct _Hash_node<_Value, true> : _Hash_node_value_base<_Value> 
265 { 
266 std::size_t _M_hash_code; 
267 
268 _Hash_node* 
269 _M_next() const noexcept 
270 { return static_cast<_Hash_node*>(this->_M_nxt); } 
271 }; 
272 
273 /** 
274 * Specialization for nodes without caches, struct _Hash_node. 
275 * 
276 * Base class is __detail::_Hash_node_value_base. 
277 */ 
278 template<typename _Value> 
279 struct _Hash_node<_Value, false> : _Hash_node_value_base<_Value> 
280 { 
281 _Hash_node* 
282 _M_next() const noexcept 
283 { return static_cast<_Hash_node*>(this->_M_nxt); } 
284 }; 
285 
286 /// Base class for node iterators. 
287 template<typename _Value, bool _Cache_hash_code> 
288 struct _Node_iterator_base 
289 { 
290 using __node_type = _Hash_node<_Value, _Cache_hash_code>; 
291 
292 __node_type* _M_cur; 
293 
294 _Node_iterator_base(__node_type* __p) noexcept 
295 : _M_cur(__p) { } 
296 
297 void 
298 _M_incr() noexcept 
299 { _M_cur = _M_cur->_M_next(); } 
300 }; 
301 
302 template<typename _Value, bool _Cache_hash_code> 
303 inline bool 
304 operator==(const _Node_iterator_base<_Value, _Cache_hash_code>& __x, 
305 const _Node_iterator_base<_Value, _Cache_hash_code >& __y) 
306 noexcept 
307 { return __x._M_cur == __y._M_cur; } 
308 
309 template<typename _Value, bool _Cache_hash_code> 
310 inline bool 
311 operator!=(const _Node_iterator_base<_Value, _Cache_hash_code>& __x, 
312 const _Node_iterator_base<_Value, _Cache_hash_code>& __y) 
313 noexcept 
314 { return __x._M_cur != __y._M_cur; } 
315 
316 /// Node iterators, used to iterate through all the hashtable. 
317 template<typename _Value, bool __constant_iterators, bool __cache> 
318 struct _Node_iterator 
319 : public _Node_iterator_base<_Value, __cache> 
320 { 
321 private: 
322 using __base_type = _Node_iterator_base<_Value, __cache>; 
323 using __node_type = typename __base_type::__node_type; 
324 
325 public: 
326 typedef _Value value_type; 
327 typedef std::ptrdiff_t difference_type; 
328 typedef std::forward_iterator_tag iterator_category; 
329 
330 using pointer = typename std::conditional<__constant_iterators, 
331 const _Value*, _Value*>::type; 
332 
333 using reference = typename std::conditional<__constant_iterators, 
334 const _Value&, _Value&>::type; 
335 
336 _Node_iterator() noexcept 
337 : __base_type(0) { } 
338 
339 explicit 
340 _Node_iterator(__node_type* __p) noexcept 
341 : __base_type(__p) { } 
342 
343 reference 
344 operator*() const noexcept 
345 { return this->_M_cur->_M_v(); } 
346 
347 pointer 
348 operator->() const noexcept 
349 { return this->_M_cur->_M_valptr(); } 
350 
351 _Node_iterator& 
352 operator++() noexcept 
353 { 
354 this->_M_incr(); 
355 return *this; 
356 } 
357 
358 _Node_iterator 
359 operator++(int) noexcept 
360 { 
361 _Node_iterator __tmp(*this); 
362 this->_M_incr(); 
363 return __tmp; 
364 } 
365 }; 
366 
367 /// Node const_iterators, used to iterate through all the hashtable. 
368 template<typename _Value, bool __constant_iterators, bool __cache> 
369 struct _Node_const_iterator 
370 : public _Node_iterator_base<_Value, __cache> 
371 { 
372 private: 
373 using __base_type = _Node_iterator_base<_Value, __cache>; 
374 using __node_type = typename __base_type::__node_type; 
375 
376 public: 
377 typedef _Value value_type; 
378 typedef std::ptrdiff_t difference_type; 
379 typedef std::forward_iterator_tag iterator_category; 
380 
381 typedef const _Value* pointer; 
382 typedef const _Value& reference; 
383 
384 _Node_const_iterator() noexcept 
385 : __base_type(0) { } 
386 
387 explicit 
388 _Node_const_iterator(__node_type* __p) noexcept 
389 : __base_type(__p) { } 
390 
391 _Node_const_iterator(const _Node_iterator<_Value, __constant_iterators, 
392 __cache>& __x) noexcept 
393 : __base_type(__x._M_cur) { } 
394 
395 reference 
396 operator*() const noexcept 
397 { return this->_M_cur->_M_v(); } 
398 
399 pointer 
400 operator->() const noexcept 
401 { return this->_M_cur->_M_valptr(); } 
402 
403 _Node_const_iterator& 
404 operator++() noexcept 
405 { 
406 this->_M_incr(); 
407 return *this; 
408 } 
409 
410 _Node_const_iterator 
411 operator++(int) noexcept 
412 { 
413 _Node_const_iterator __tmp(*this); 
414 this->_M_incr(); 
415 return __tmp; 
416 } 
417 }; 
418 
419 // Many of class template _Hashtable's template parameters are policy 
420 // classes. These are defaults for the policies. 
421 
422 /// Default range hashing function: use division to fold a large number 
423 /// into the range [0, N). 
424 struct _Mod_range_hashing 
425 { 
426 typedef std::size_t first_argument_type; 
427 typedef std::size_t second_argument_type; 
428 typedef std::size_t result_type; 
429 
430 result_type 
431 operator()(first_argument_type __num, 
432 second_argument_type __den) const noexcept 
433 { return __num % __den; } 
434 }; 
435 
436 /// Default ranged hash function H. In principle it should be a 
437 /// function object composed from objects of type H1 and H2 such that 
438 /// h(k, N) = h2(h1(k), N), but that would mean making extra copies of 
439 /// h1 and h2. So instead we'll just use a tag to tell class template 
440 /// hashtable to do that composition. 
441 struct _Default_ranged_hash { }; 
442 
443 /// Default value for rehash policy. Bucket size is (usually) the 
444 /// smallest prime that keeps the load factor small enough. 
445 struct _Prime_rehash_policy 
446 { 
447 using __has_load_factor = std::true_type; 
448 
449 _Prime_rehash_policy(float __z = 1.0) noexcept 
450 : _M_max_load_factor(__z), _M_next_resize(0) { } 
451 
452 float 
453 max_load_factor() const noexcept 
454 { return _M_max_load_factor; } 
455 
456 // Return a bucket size no smaller than n. 
457 std::size_t 
458 _M_next_bkt(std::size_t __n) const; 
459 
460 // Return a bucket count appropriate for n elements 
461 std::size_t 
462 _M_bkt_for_elements(std::size_t __n) const 
463 { return __builtin_ceil(__n / (long double)_M_max_load_factor); } 
464 
465 // __n_bkt is current bucket count, __n_elt is current element count, 
466 // and __n_ins is number of elements to be inserted. Do we need to 
467 // increase bucket count? If so, return make_pair(true, n), where n 
468 // is the new bucket count. If not, return make_pair(false, 0). 
469 std::pair<bool, std::size_t> 
470 _M_need_rehash(std::size_t __n_bkt, std::size_t __n_elt, 
471 std::size_t __n_ins) const; 
472 
473 typedef std::size_t _State; 
474 
475 _State 
476 _M_state() const 
477 { return _M_next_resize; } 
478 
479 void 
480 _M_reset() noexcept 
481 { _M_next_resize = 0; } 
482 
483 void 
484 _M_reset(_State __state) 
485 { _M_next_resize = __state; } 
486 
487 static const std::size_t _S_growth_factor = 2; 
488 
489 float _M_max_load_factor; 
490 mutable std::size_t _M_next_resize; 
491 }; 
492 
493 /// Range hashing function assuming that second arg is a power of 2. 
494 struct _Mask_range_hashing 
495 { 
496 typedef std::size_t first_argument_type; 
497 typedef std::size_t second_argument_type; 
498 typedef std::size_t result_type; 
499 
500 result_type 
501 operator()(first_argument_type __num, 
502 second_argument_type __den) const noexcept 
503 { return __num & (__den - 1); } 
504 }; 
505 
506 /// Compute closest power of 2 not less than __n 
507 inline std::size_t 
508 __clp2(std::size_t __n) noexcept 
509 { 
510 // Equivalent to return __n ? std::ceil2(__n) : 0; 
511 if (__n < 2) 
512 return __n; 
513 const unsigned __lz = sizeof(size_t) > sizeof(long) 
514 ? __builtin_clzll(__n - 1ull) 
515 : __builtin_clzl(__n - 1ul); 
516 // Doing two shifts avoids undefined behaviour when __lz == 0. 
517 return (size_t(1) << (numeric_limits<size_t>::digits - __lz - 1)) << 1; 
518 } 
519 
520 /// Rehash policy providing power of 2 bucket numbers. Avoids modulo 
521 /// operations. 
522 struct _Power2_rehash_policy 
523 { 
524 using __has_load_factor = std::true_type; 
525 
526 _Power2_rehash_policy(float __z = 1.0) noexcept 
527 : _M_max_load_factor(__z), _M_next_resize(0) { } 
528 
529 float 
530 max_load_factor() const noexcept 
531 { return _M_max_load_factor; } 
532 
533 // Return a bucket size no smaller than n (as long as n is not above the 
534 // highest power of 2). 
535 std::size_t 
536 _M_next_bkt(std::size_t __n) noexcept 
537 { 
538 const auto __max_width = std::min<size_t>(sizeof(size_t), 8); 
539 const auto __max_bkt = size_t(1) << (__max_width * __CHAR_BIT__ - 1); 
540 std::size_t __res = __clp2(__n); 
541 
542 if (__res == __n) 
543 __res <<= 1; 
544 
545 if (__res == 0) 
546 __res = __max_bkt; 
547 
548 if (__res == __max_bkt) 
549 // Set next resize to the max value so that we never try to rehash again 
550 // as we already reach the biggest possible bucket number. 
551 // Note that it might result in max_load_factor not being respected. 
552 _M_next_resize = std::size_t(-1); 
553 else 
554 _M_next_resize 
555 = __builtin_ceil(__res * (long double)_M_max_load_factor); 
556 
557 return __res; 
558 } 
559 
560 // Return a bucket count appropriate for n elements 
561 std::size_t 
562 _M_bkt_for_elements(std::size_t __n) const noexcept 
563 { return __builtin_ceil(__n / (long double)_M_max_load_factor); } 
564 
565 // __n_bkt is current bucket count, __n_elt is current element count, 
566 // and __n_ins is number of elements to be inserted. Do we need to 
567 // increase bucket count? If so, return make_pair(true, n), where n 
568 // is the new bucket count. If not, return make_pair(false, 0). 
569 std::pair<bool, std::size_t> 
570 _M_need_rehash(std::size_t __n_bkt, std::size_t __n_elt, 
571 std::size_t __n_ins) noexcept 
572 { 
573 if (__n_elt + __n_ins >= _M_next_resize) 
574 { 
575 long double __min_bkts = (__n_elt + __n_ins) 
576 / (long double)_M_max_load_factor; 
577 if (__min_bkts >= __n_bkt) 
578 return std::make_pair(true, 
579 _M_next_bkt(std::max<std::size_t>(__builtin_floor(__min_bkts) + 1, 
580 __n_bkt * _S_growth_factor))); 
581 
582 _M_next_resize 
583 = __builtin_floor(__n_bkt * (long double)_M_max_load_factor); 
584 return std::make_pair(false, 0); 
585 } 
586 else 
587 return std::make_pair(false, 0); 
588 } 
589 
590 typedef std::size_t _State; 
591 
592 _State 
593 _M_state() const noexcept 
594 { return _M_next_resize; } 
595 
596 void 
597 _M_reset() noexcept 
598 { _M_next_resize = 0; } 
599 
600 void 
601 _M_reset(_State __state) noexcept 
602 { _M_next_resize = __state; } 
603 
604 static const std::size_t _S_growth_factor = 2; 
605 
606 float _M_max_load_factor; 
607 std::size_t _M_next_resize; 
608 }; 
609 
610 // Base classes for std::_Hashtable. We define these base classes 
611 // because in some cases we want to do different things depending on 
612 // the value of a policy class. In some cases the policy class 
613 // affects which member functions and nested typedefs are defined; 
614 // we handle that by specializing base class templates. Several of 
615 // the base class templates need to access other members of class 
616 // template _Hashtable, so we use a variant of the "Curiously 
617 // Recurring Template Pattern" (CRTP) technique. 
618 
619 /** 
620 * Primary class template _Map_base. 
621 * 
622 * If the hashtable has a value type of the form pair<T1, T2> and a 
623 * key extraction policy (_ExtractKey) that returns the first part 
624 * of the pair, the hashtable gets a mapped_type typedef. If it 
625 * satisfies those criteria and also has unique keys, then it also 
626 * gets an operator[]. 
627 */ 
628 template<typename _Key, typename _Value, typename _Alloc, 
629 typename _ExtractKey, typename _Equal, 
630 typename _H1, typename _H2, typename _Hash, 
631 typename _RehashPolicy, typename _Traits, 
632 bool _Unique_keys = _Traits::__unique_keys::value> 
633 struct _Map_base { }; 
634 
635 /// Partial specialization, __unique_keys set to false. 
636 template<typename _Key, typename _Pair, typename _Alloc, typename _Equal, 
637 typename _H1, typename _H2, typename _Hash, 
638 typename _RehashPolicy, typename _Traits> 
639 struct _Map_base<_Key, _Pair, _Alloc, _Select1st, _Equal, 
640 _H1, _H2, _Hash, _RehashPolicy, _Traits, false> 
641 { 
642 using mapped_type = typename std::tuple_element<1, _Pair>::type; 
643 }; 
644 
645 /// Partial specialization, __unique_keys set to true. 
646 template<typename _Key, typename _Pair, typename _Alloc, typename _Equal, 
647 typename _H1, typename _H2, typename _Hash, 
648 typename _RehashPolicy, typename _Traits> 
649 struct _Map_base<_Key, _Pair, _Alloc, _Select1st, _Equal, 
650 _H1, _H2, _Hash, _RehashPolicy, _Traits, true> 
651 { 
652 private: 
653 using __hashtable_base = __detail::_Hashtable_base<_Key, _Pair, 
654 _Select1st, 
655 _Equal, _H1, _H2, _Hash, 
656 _Traits>; 
657 
658 using __hashtable = _Hashtable<_Key, _Pair, _Alloc, 
659 _Select1st, _Equal, 
660 _H1, _H2, _Hash, _RehashPolicy, _Traits>; 
661 
662 using __hash_code = typename __hashtable_base::__hash_code; 
663 using __node_type = typename __hashtable_base::__node_type; 
664 
665 public: 
666 using key_type = typename __hashtable_base::key_type; 
667 using iterator = typename __hashtable_base::iterator; 
668 using mapped_type = typename std::tuple_element<1, _Pair>::type; 
669 
670 mapped_type& 
671 operator[](const key_type& __k); 
672 
673 mapped_type& 
674 operator[](key_type&& __k); 
675 
676 // _GLIBCXX_RESOLVE_LIB_DEFECTS 
677 // DR 761. unordered_map needs an at() member function. 
678 mapped_type& 
679 at(const key_type& __k); 
680 
681 const mapped_type& 
682 at(const key_type& __k) const; 
683 }; 
684 
685 template<typename _Key, typename _Pair, typename _Alloc, typename _Equal, 
686 typename _H1, typename _H2, typename _Hash, 
687 typename _RehashPolicy, typename _Traits> 
688 auto 
689 _Map_base<_Key, _Pair, _Alloc, _Select1st, _Equal, 
690 _H1, _H2, _Hash, _RehashPolicy, _Traits, true>:: 
691 operator[](const key_type& __k) 
692 -> mapped_type& 
693 { 
694 __hashtable* __h = static_cast<__hashtable*>(this); 
695 __hash_code __code = __h->_M_hash_code(__k); 
696 std::size_t __n = __h->_M_bucket_index(__k, __code); 
697 __node_type* __p = __h->_M_find_node(__n, __k, __code); 
698 
699 if (!__p) 
700 { 
701 __p = __h->_M_allocate_node(std::piecewise_construct, 
702 std::tuple<const key_type&>(__k), 
703 std::tuple<>()); 
704 return __h->_M_insert_unique_node(__n, __code, __p)->second; 
705 } 
706 
707 return __p->_M_v().second; 
708 } 
709 
710 template<typename _Key, typename _Pair, typename _Alloc, typename _Equal, 
711 typename _H1, typename _H2, typename _Hash, 
712 typename _RehashPolicy, typename _Traits> 
713 auto 
714 _Map_base<_Key, _Pair, _Alloc, _Select1st, _Equal, 
715 _H1, _H2, _Hash, _RehashPolicy, _Traits, true>:: 
716 operator[](key_type&& __k) 
717 -> mapped_type& 
718 { 
719 __hashtable* __h = static_cast<__hashtable*>(this); 
720 __hash_code __code = __h->_M_hash_code(__k); 
721 std::size_t __n = __h->_M_bucket_index(__k, __code); 
722 __node_type* __p = __h->_M_find_node(__n, __k, __code); 
723 
724 if (!__p) 
725 { 
726 __p = __h->_M_allocate_node(std::piecewise_construct, 
727 std::forward_as_tuple(std::move(__k)), 
728 std::tuple<>()); 
729 return __h->_M_insert_unique_node(__n, __code, __p)->second; 
730 } 
731 
732 return __p->_M_v().second; 
733 } 
734 
735 template<typename _Key, typename _Pair, typename _Alloc, typename _Equal, 
736 typename _H1, typename _H2, typename _Hash, 
737 typename _RehashPolicy, typename _Traits> 
738 auto 
739 _Map_base<_Key, _Pair, _Alloc, _Select1st, _Equal, 
740 _H1, _H2, _Hash, _RehashPolicy, _Traits, true>:: 
741 at(const key_type& __k) 
742 -> mapped_type& 
743 { 
744 __hashtable* __h = static_cast<__hashtable*>(this); 
745 __hash_code __code = __h->_M_hash_code(__k); 
746 std::size_t __n = __h->_M_bucket_index(__k, __code); 
747 __node_type* __p = __h->_M_find_node(__n, __k, __code); 
748 
749 if (!__p) 
750 __throw_out_of_range(__N("_Map_base::at")); 
751 return __p->_M_v().second; 
752 } 
753 
754 template<typename _Key, typename _Pair, typename _Alloc, typename _Equal, 
755 typename _H1, typename _H2, typename _Hash, 
756 typename _RehashPolicy, typename _Traits> 
757 auto 
758 _Map_base<_Key, _Pair, _Alloc, _Select1st, _Equal, 
759 _H1, _H2, _Hash, _RehashPolicy, _Traits, true>:: 
760 at(const key_type& __k) const 
761 -> const mapped_type& 
762 { 
763 const __hashtable* __h = static_cast<const __hashtable*>(this); 
764 __hash_code __code = __h->_M_hash_code(__k); 
765 std::size_t __n = __h->_M_bucket_index(__k, __code); 
766 __node_type* __p = __h->_M_find_node(__n, __k, __code); 
767 
768 if (!__p) 
769 __throw_out_of_range(__N("_Map_base::at")); 
770 return __p->_M_v().second; 
771 } 
772 
773 /** 
774 * Primary class template _Insert_base. 
775 * 
776 * Defines @c insert member functions appropriate to all _Hashtables. 
777 */ 
778 template<typename _Key, typename _Value, typename _Alloc, 
779 typename _ExtractKey, typename _Equal, 
780 typename _H1, typename _H2, typename _Hash, 
781 typename _RehashPolicy, typename _Traits> 
782 struct _Insert_base 
783 { 
784 protected: 
785 using __hashtable = _Hashtable<_Key, _Value, _Alloc, _ExtractKey, 
786 _Equal, _H1, _H2, _Hash, 
787 _RehashPolicy, _Traits>; 
788 
789 using __hashtable_base = _Hashtable_base<_Key, _Value, _ExtractKey, 
790 _Equal, _H1, _H2, _Hash, 
791 _Traits>; 
792 
793 using value_type = typename __hashtable_base::value_type; 
794 using iterator = typename __hashtable_base::iterator; 
795 using const_iterator = typename __hashtable_base::const_iterator; 
796 using size_type = typename __hashtable_base::size_type; 
797 
798 using __unique_keys = typename __hashtable_base::__unique_keys; 
799 using __ireturn_type = typename __hashtable_base::__ireturn_type; 
800 using __node_type = _Hash_node<_Value, _Traits::__hash_cached::value>; 
801 using __node_alloc_type = __alloc_rebind<_Alloc, __node_type>; 
802 using __node_gen_type = _AllocNode<__node_alloc_type>; 
803 
804 __hashtable& 
805 _M_conjure_hashtable() 
806 { return *(static_cast<__hashtable*>(this)); } 
807 
808 template<typename _InputIterator, typename _NodeGetter> 
809 void 
810 _M_insert_range(_InputIterator __first, _InputIterator __last, 
811 const _NodeGetter&, true_type); 
812 
813 template<typename _InputIterator, typename _NodeGetter> 
814 void 
815 _M_insert_range(_InputIterator __first, _InputIterator __last, 
816 const _NodeGetter&, false_type); 
817 
818 public: 
819 __ireturn_type 
820 insert(const value_type& __v) 
821 { 
822 __hashtable& __h = _M_conjure_hashtable(); 
823 __node_gen_type __node_gen(__h); 
824 return __h._M_insert(__v, __node_gen, __unique_keys()); 
825 } 
826 
827 iterator 
828 insert(const_iterator __hint, const value_type& __v) 
829 { 
830 __hashtable& __h = _M_conjure_hashtable(); 
831 __node_gen_type __node_gen(__h);  
832 return __h._M_insert(__hint, __v, __node_gen, __unique_keys()); 
833 } 
834 
835 void 
836 insert(initializer_list<value_type> __l) 
837 { this->insert(__l.begin(), __l.end()); } 
838 
839 template<typename _InputIterator> 
840 void 
841 insert(_InputIterator __first, _InputIterator __last) 
842 { 
843 __hashtable& __h = _M_conjure_hashtable(); 
844 __node_gen_type __node_gen(__h); 
845 return _M_insert_range(__first, __last, __node_gen, __unique_keys()); 
846 } 
847 }; 
848 
849 template<typename _Key, typename _Value, typename _Alloc, 
850 typename _ExtractKey, typename _Equal, 
851 typename _H1, typename _H2, typename _Hash, 
852 typename _RehashPolicy, typename _Traits> 
853 template<typename _InputIterator, typename _NodeGetter> 
854 void 
855 _Insert_base<_Key, _Value, _Alloc, _ExtractKey, _Equal, _H1, _H2, _Hash, 
856 _RehashPolicy, _Traits>:: 
857 _M_insert_range(_InputIterator __first, _InputIterator __last, 
858 const _NodeGetter& __node_gen, true_type) 
859 { 
860 size_type __n_elt = __detail::__distance_fw(__first, __last); 
861 if (__n_elt == 0) 
862 return; 
863 
864 __hashtable& __h = _M_conjure_hashtable(); 
865 for (; __first != __last; ++__first) 
866 { 
867 if (__h._M_insert(*__first, __node_gen, __unique_keys(), 
868 __n_elt).second) 
869 __n_elt = 1; 
870 else if (__n_elt != 1) 
871 --__n_elt; 
872 } 
873 } 
874 
875 template<typename _Key, typename _Value, typename _Alloc, 
876 typename _ExtractKey, typename _Equal, 
877 typename _H1, typename _H2, typename _Hash, 
878 typename _RehashPolicy, typename _Traits> 
879 template<typename _InputIterator, typename _NodeGetter> 
880 void 
881 _Insert_base<_Key, _Value, _Alloc, _ExtractKey, _Equal, _H1, _H2, _Hash, 
882 _RehashPolicy, _Traits>:: 
883 _M_insert_range(_InputIterator __first, _InputIterator __last, 
884 const _NodeGetter& __node_gen, false_type) 
885 { 
886 using __rehash_type = typename __hashtable::__rehash_type; 
887 using __rehash_state = typename __hashtable::__rehash_state; 
888 using pair_type = std::pair<bool, std::size_t>; 
889 
890 size_type __n_elt = __detail::__distance_fw(__first, __last); 
891 if (__n_elt == 0) 
892 return; 
893 
894 __hashtable& __h = _M_conjure_hashtable(); 
895 __rehash_type& __rehash = __h._M_rehash_policy; 
896 const __rehash_state& __saved_state = __rehash._M_state(); 
897 pair_type __do_rehash = __rehash._M_need_rehash(__h._M_bucket_count, 
898 __h._M_element_count, 
899 __n_elt); 
900 
901 if (__do_rehash.first) 
902 __h._M_rehash(__do_rehash.second, __saved_state); 
903 
904 for (; __first != __last; ++__first) 
905 __h._M_insert(*__first, __node_gen, __unique_keys()); 
906 } 
907 
908 /** 
909 * Primary class template _Insert. 
910 * 
911 * Defines @c insert member functions that depend on _Hashtable policies, 
912 * via partial specializations. 
913 */ 
914 template<typename _Key, typename _Value, typename _Alloc, 
915 typename _ExtractKey, typename _Equal, 
916 typename _H1, typename _H2, typename _Hash, 
917 typename _RehashPolicy, typename _Traits, 
918 bool _Constant_iterators = _Traits::__constant_iterators::value> 
919 struct _Insert; 
920 
921 /// Specialization. 
922 template<typename _Key, typename _Value, typename _Alloc, 
923 typename _ExtractKey, typename _Equal, 
924 typename _H1, typename _H2, typename _Hash, 
925 typename _RehashPolicy, typename _Traits> 
926 struct _Insert<_Key, _Value, _Alloc, _ExtractKey, _Equal, _H1, _H2, _Hash, 
927 _RehashPolicy, _Traits, true> 
928 : public _Insert_base<_Key, _Value, _Alloc, _ExtractKey, _Equal, 
929 _H1, _H2, _Hash, _RehashPolicy, _Traits> 
930 { 
931 using __base_type = _Insert_base<_Key, _Value, _Alloc, _ExtractKey, 
932 _Equal, _H1, _H2, _Hash, 
933 _RehashPolicy, _Traits>; 
934 
935 using __hashtable_base = _Hashtable_base<_Key, _Value, _ExtractKey, 
936 _Equal, _H1, _H2, _Hash, 
937 _Traits>; 
938 
939 using value_type = typename __base_type::value_type; 
940 using iterator = typename __base_type::iterator; 
941 using const_iterator = typename __base_type::const_iterator; 
942 
943 using __unique_keys = typename __base_type::__unique_keys; 
944 using __ireturn_type = typename __hashtable_base::__ireturn_type; 
945 using __hashtable = typename __base_type::__hashtable; 
946 using __node_gen_type = typename __base_type::__node_gen_type; 
947 
948 using __base_type::insert; 
949 
950 __ireturn_type 
951 insert(value_type&& __v) 
952 { 
953 __hashtable& __h = this->_M_conjure_hashtable(); 
954 __node_gen_type __node_gen(__h); 
955 return __h._M_insert(std::move(__v), __node_gen, __unique_keys()); 
956 } 
957 
958 iterator 
959 insert(const_iterator __hint, value_type&& __v) 
960 { 
961 __hashtable& __h = this->_M_conjure_hashtable(); 
962 __node_gen_type __node_gen(__h); 
963 return __h._M_insert(__hint, std::move(__v), __node_gen, 
964 __unique_keys()); 
965 } 
966 }; 
967 
968 /// Specialization. 
969 template<typename _Key, typename _Value, typename _Alloc, 
970 typename _ExtractKey, typename _Equal, 
971 typename _H1, typename _H2, typename _Hash, 
972 typename _RehashPolicy, typename _Traits> 
973 struct _Insert<_Key, _Value, _Alloc, _ExtractKey, _Equal, _H1, _H2, _Hash, 
974 _RehashPolicy, _Traits, false> 
975 : public _Insert_base<_Key, _Value, _Alloc, _ExtractKey, _Equal, 
976 _H1, _H2, _Hash, _RehashPolicy, _Traits> 
977 { 
978 using __base_type = _Insert_base<_Key, _Value, _Alloc, _ExtractKey, 
979 _Equal, _H1, _H2, _Hash, 
980 _RehashPolicy, _Traits>; 
981 using value_type = typename __base_type::value_type; 
982 using iterator = typename __base_type::iterator; 
983 using const_iterator = typename __base_type::const_iterator; 
984 
985 using __unique_keys = typename __base_type::__unique_keys; 
986 using __hashtable = typename __base_type::__hashtable; 
987 using __ireturn_type = typename __base_type::__ireturn_type; 
988 
989 using __base_type::insert; 
990 
991 template<typename _Pair> 
992 using __is_cons = std::is_constructible<value_type, _Pair&&>; 
993 
994 template<typename _Pair> 
995 using _IFcons = std::enable_if<__is_cons<_Pair>::value>; 
996 
997 template<typename _Pair> 
998 using _IFconsp = typename _IFcons<_Pair>::type; 
999 
1000 template<typename _Pair, typename = _IFconsp<_Pair>> 
1001 __ireturn_type 
1002 insert(_Pair&& __v) 
1003 { 
1004 __hashtable& __h = this->_M_conjure_hashtable(); 
1005 return __h._M_emplace(__unique_keys(), std::forward<_Pair>(__v)); 
1006 } 
1007 
1008 template<typename _Pair, typename = _IFconsp<_Pair>> 
1009 iterator 
1010 insert(const_iterator __hint, _Pair&& __v) 
1011 { 
1012 __hashtable& __h = this->_M_conjure_hashtable(); 
1013 return __h._M_emplace(__hint, __unique_keys(), 
1014 std::forward<_Pair>(__v)); 
1015 } 
1016 }; 
1017 
1018 template<typename _Policy> 
1019 using __has_load_factor = typename _Policy::__has_load_factor; 
1020 
1021 /** 
1022 * Primary class template _Rehash_base. 
1023 * 
1024 * Give hashtable the max_load_factor functions and reserve iff the 
1025 * rehash policy supports it. 
1026 */ 
1027 template<typename _Key, typename _Value, typename _Alloc, 
1028 typename _ExtractKey, typename _Equal, 
1029 typename _H1, typename _H2, typename _Hash, 
1030 typename _RehashPolicy, typename _Traits, 
1031 typename = 
1032 __detected_or_t<std::false_type, __has_load_factor, _RehashPolicy>> 
1033 struct _Rehash_base; 
1034 
1035 /// Specialization when rehash policy doesn't provide load factor management. 
1036 template<typename _Key, typename _Value, typename _Alloc, 
1037 typename _ExtractKey, typename _Equal, 
1038 typename _H1, typename _H2, typename _Hash, 
1039 typename _RehashPolicy, typename _Traits> 
1040 struct _Rehash_base<_Key, _Value, _Alloc, _ExtractKey, _Equal, 
1041 _H1, _H2, _Hash, _RehashPolicy, _Traits, 
1042 std::false_type> 
1043 { 
1044 }; 
1045 
1046 /// Specialization when rehash policy provide load factor management. 
1047 template<typename _Key, typename _Value, typename _Alloc, 
1048 typename _ExtractKey, typename _Equal, 
1049 typename _H1, typename _H2, typename _Hash, 
1050 typename _RehashPolicy, typename _Traits> 
1051 struct _Rehash_base<_Key, _Value, _Alloc, _ExtractKey, _Equal, 
1052 _H1, _H2, _Hash, _RehashPolicy, _Traits, 
1053 std::true_type> 
1054 { 
1055 using __hashtable = _Hashtable<_Key, _Value, _Alloc, _ExtractKey, 
1056 _Equal, _H1, _H2, _Hash, 
1057 _RehashPolicy, _Traits>; 
1058 
1059 float 
1060 max_load_factor() const noexcept 
1061 { 
1062 const __hashtable* __this = static_cast<const __hashtable*>(this); 
1063 return __this->__rehash_policy().max_load_factor(); 
1064 } 
1065 
1066 void 
1067 max_load_factor(float __z) 
1068 { 
1069 __hashtable* __this = static_cast<__hashtable*>(this); 
1070 __this->__rehash_policy(_RehashPolicy(__z)); 
1071 } 
1072 
1073 void 
1074 reserve(std::size_t __n) 
1075 { 
1076 __hashtable* __this = static_cast<__hashtable*>(this); 
1077 __this->rehash(__builtin_ceil(__n / max_load_factor())); 
1078 } 
1079 }; 
1080 
1081 /** 
1082 * Primary class template _Hashtable_ebo_helper. 
1083 * 
1084 * Helper class using EBO when it is not forbidden (the type is not 
1085 * final) and when it is worth it (the type is empty.) 
1086 */ 
1087 template<int _Nm, typename _Tp, 
1088 bool __use_ebo = !__is_final(_Tp) && __is_empty(_Tp)> 
1089 struct _Hashtable_ebo_helper; 
1090 
1091 /// Specialization using EBO. 
1092 template<int _Nm, typename _Tp> 
1093 struct _Hashtable_ebo_helper<_Nm, _Tp, true> 
1094 : private _Tp 
1095 { 
1096 _Hashtable_ebo_helper() = default; 
1097 
1098 template<typename _OtherTp> 
1099 _Hashtable_ebo_helper(_OtherTp&& __tp) 
1100 : _Tp(std::forward<_OtherTp>(__tp)) 
1101 { } 
1102 
1103 static const _Tp& 
1104 _S_cget(const _Hashtable_ebo_helper& __eboh) 
1105 { return static_cast<const _Tp&>(__eboh); } 
1106 
1107 static _Tp& 
1108 _S_get(_Hashtable_ebo_helper& __eboh) 
1109 { return static_cast<_Tp&>(__eboh); } 
1110 }; 
1111 
1112 /// Specialization not using EBO. 
1113 template<int _Nm, typename _Tp> 
1114 struct _Hashtable_ebo_helper<_Nm, _Tp, false> 
1115 { 
1116 _Hashtable_ebo_helper() = default; 
1117 
1118 template<typename _OtherTp> 
1119 _Hashtable_ebo_helper(_OtherTp&& __tp) 
1120 : _M_tp(std::forward<_OtherTp>(__tp)) 
1121 { } 
1122 
1123 static const _Tp& 
1124 _S_cget(const _Hashtable_ebo_helper& __eboh) 
1125 { return __eboh._M_tp; } 
1126 
1127 static _Tp& 
1128 _S_get(_Hashtable_ebo_helper& __eboh) 
1129 { return __eboh._M_tp; } 
1130 
1131 private: 
1132 _Tp _M_tp; 
1133 }; 
1134 
1135 /** 
1136 * Primary class template _Local_iterator_base. 
1137 * 
1138 * Base class for local iterators, used to iterate within a bucket 
1139 * but not between buckets. 
1140 */ 
1141 template<typename _Key, typename _Value, typename _ExtractKey, 
1142 typename _H1, typename _H2, typename _Hash, 
1143 bool __cache_hash_code> 
1144 struct _Local_iterator_base; 
1145 
1146 /** 
1147 * Primary class template _Hash_code_base. 
1148 * 
1149 * Encapsulates two policy issues that aren't quite orthogonal. 
1150 * (1) the difference between using a ranged hash function and using 
1151 * the combination of a hash function and a range-hashing function. 
1152 * In the former case we don't have such things as hash codes, so 
1153 * we have a dummy type as placeholder. 
1154 * (2) Whether or not we cache hash codes. Caching hash codes is 
1155 * meaningless if we have a ranged hash function. 
1156 * 
1157 * We also put the key extraction objects here, for convenience. 
1158 * Each specialization derives from one or more of the template 
1159 * parameters to benefit from Ebo. This is important as this type 
1160 * is inherited in some cases by the _Local_iterator_base type used 
1161 * to implement local_iterator and const_local_iterator. As with 
1162 * any iterator type we prefer to make it as small as possible. 
1163 * 
1164 * Primary template is unused except as a hook for specializations. 
1165 */ 
1166 template<typename _Key, typename _Value, typename _ExtractKey, 
1167 typename _H1, typename _H2, typename _Hash, 
1168 bool __cache_hash_code> 
1169 struct _Hash_code_base; 
1170 
1171 /// Specialization: ranged hash function, no caching hash codes. H1 
1172 /// and H2 are provided but ignored. We define a dummy hash code type. 
1173 template<typename _Key, typename _Value, typename _ExtractKey, 
1174 typename _H1, typename _H2, typename _Hash> 
1175 struct _Hash_code_base<_Key, _Value, _ExtractKey, _H1, _H2, _Hash, false> 
1176 : private _Hashtable_ebo_helper<0, _ExtractKey>, 
1177 private _Hashtable_ebo_helper<1, _Hash> 
1178 { 
1179 private: 
1180 using __ebo_extract_key = _Hashtable_ebo_helper<0, _ExtractKey>; 
1181 using __ebo_hash = _Hashtable_ebo_helper<1, _Hash>; 
1182 
1183 protected: 
1184 typedef void* __hash_code; 
1185 typedef _Hash_node<_Value, false> __node_type; 
1186 
1187 // We need the default constructor for the local iterators and _Hashtable 
1188 // default constructor. 
1189 _Hash_code_base() = default; 
1190 
1191 _Hash_code_base(const _ExtractKey& __ex, const _H1&, const _H2&, 
1192 const _Hash& __h) 
1193 : __ebo_extract_key(__ex), __ebo_hash(__h) { } 
1194 
1195 __hash_code 
1196 _M_hash_code(const _Key& __key) const 
1197 { return 0; } 
1198 
1199 std::size_t 
1200 _M_bucket_index(const _Key& __k, __hash_code, std::size_t __n) const 
1201 { return _M_ranged_hash()(__k, __n); } 
1202 
1203 std::size_t 
1204 _M_bucket_index(const __node_type* __p, std::size_t __n) const 
1205 noexcept( noexcept(declval<const _Hash&>()(declval<const _Key&>(), 
1206 (std::size_t)0)) ) 
1207 { return _M_ranged_hash()(_M_extract()(__p->_M_v()), __n); } 
1208 
1209 void 
1210 _M_store_code(__node_type*, __hash_code) const 
1211 { } 
1212 
1213 void 
1214 _M_copy_code(__node_type*, const __node_type*) const 
1215 { } 
1216 
1217 void 
1218 _M_swap(_Hash_code_base& __x) 
1219 { 
1220 std::swap(_M_extract(), __x._M_extract()); 
1221 std::swap(_M_ranged_hash(), __x._M_ranged_hash()); 
1222 } 
1223 
1224 const _ExtractKey& 
1225 _M_extract() const { return __ebo_extract_key::_S_cget(*this); } 
1226 
1227 _ExtractKey& 
1228 _M_extract() { return __ebo_extract_key::_S_get(*this); } 
1229 
1230 const _Hash& 
1231 _M_ranged_hash() const { return __ebo_hash::_S_cget(*this); } 
1232 
1233 _Hash& 
1234 _M_ranged_hash() { return __ebo_hash::_S_get(*this); } 
1235 }; 
1236 
1237 // No specialization for ranged hash function while caching hash codes. 
1238 // That combination is meaningless, and trying to do it is an error. 
1239 
1240 /// Specialization: ranged hash function, cache hash codes. This 
1241 /// combination is meaningless, so we provide only a declaration 
1242 /// and no definition. 
1243 template<typename _Key, typename _Value, typename _ExtractKey, 
1244 typename _H1, typename _H2, typename _Hash> 
1245 struct _Hash_code_base<_Key, _Value, _ExtractKey, _H1, _H2, _Hash, true>; 
1246 
1247 /// Specialization: hash function and range-hashing function, no 
1248 /// caching of hash codes. 
1249 /// Provides typedef and accessor required by C++ 11. 
1250 template<typename _Key, typename _Value, typename _ExtractKey, 
1251 typename _H1, typename _H2> 
1252 struct _Hash_code_base<_Key, _Value, _ExtractKey, _H1, _H2, 
1253 _Default_ranged_hash, false> 
1254 : private _Hashtable_ebo_helper<0, _ExtractKey>, 
1255 private _Hashtable_ebo_helper<1, _H1>, 
1256 private _Hashtable_ebo_helper<2, _H2> 
1257 { 
1258 private: 
1259 using __ebo_extract_key = _Hashtable_ebo_helper<0, _ExtractKey>; 
1260 using __ebo_h1 = _Hashtable_ebo_helper<1, _H1>; 
1261 using __ebo_h2 = _Hashtable_ebo_helper<2, _H2>; 
1262 
1263 // Gives the local iterator implementation access to _M_bucket_index(). 
1264 friend struct _Local_iterator_base<_Key, _Value, _ExtractKey, _H1, _H2, 
1265 _Default_ranged_hash, false>; 
1266 
1267 public: 
1268 typedef _H1 hasher; 
1269 
1270 hasher 
1271 hash_function() const 
1272 { return _M_h1(); } 
1273 
1274 protected: 
1275 typedef std::size_t __hash_code; 
1276 typedef _Hash_node<_Value, false> __node_type; 
1277 
1278 // We need the default constructor for the local iterators and _Hashtable 
1279 // default constructor. 
1280 _Hash_code_base() = default; 
1281 
1282 _Hash_code_base(const _ExtractKey& __ex, 
1283 const _H1& __h1, const _H2& __h2, 
1284 const _Default_ranged_hash&) 
1285 : __ebo_extract_key(__ex), __ebo_h1(__h1), __ebo_h2(__h2) { } 
1286 
1287 __hash_code 
1288 _M_hash_code(const _Key& __k) const 
1289 { 
1290 static_assert(__is_invocable<const _H1&, const _Key&>{}, 
1291 "hash function must be invocable with an argument of key type"); 
1292 return _M_h1()(__k); 
1293 } 
1294 
1295 std::size_t 
1296 _M_bucket_index(const _Key&, __hash_code __c, std::size_t __n) const 
1297 { return _M_h2()(__c, __n); } 
1298 
1299 std::size_t 
1300 _M_bucket_index(const __node_type* __p, std::size_t __n) const 
1301 noexcept( noexcept(declval<const _H1&>()(declval<const _Key&>())) 
1302 && noexcept(declval<const _H2&>()((__hash_code)0, 
1303 (std::size_t)0)) ) 
1304 { return _M_h2()(_M_h1()(_M_extract()(__p->_M_v())), __n); } 
1305 
1306 void 
1307 _M_store_code(__node_type*, __hash_code) const 
1308 { } 
1309 
1310 void 
1311 _M_copy_code(__node_type*, const __node_type*) const 
1312 { } 
1313 
1314 void 
1315 _M_swap(_Hash_code_base& __x) 
1316 { 
1317 std::swap(_M_extract(), __x._M_extract()); 
1318 std::swap(_M_h1(), __x._M_h1()); 
1319 std::swap(_M_h2(), __x._M_h2()); 
1320 } 
1321 
1322 const _ExtractKey& 
1323 _M_extract() const { return __ebo_extract_key::_S_cget(*this); } 
1324 
1325 _ExtractKey& 
1326 _M_extract() { return __ebo_extract_key::_S_get(*this); } 
1327 
1328 const _H1& 
1329 _M_h1() const { return __ebo_h1::_S_cget(*this); } 
1330 
1331 _H1& 
1332 _M_h1() { return __ebo_h1::_S_get(*this); } 
1333 
1334 const _H2& 
1335 _M_h2() const { return __ebo_h2::_S_cget(*this); } 
1336 
1337 _H2& 
1338 _M_h2() { return __ebo_h2::_S_get(*this); } 
1339 }; 
1340 
1341 /// Specialization: hash function and range-hashing function, 
1342 /// caching hash codes. H is provided but ignored. Provides 
1343 /// typedef and accessor required by C++ 11. 
1344 template<typename _Key, typename _Value, typename _ExtractKey, 
1345 typename _H1, typename _H2> 
1346 struct _Hash_code_base<_Key, _Value, _ExtractKey, _H1, _H2, 
1347 _Default_ranged_hash, true> 
1348 : private _Hashtable_ebo_helper<0, _ExtractKey>, 
1349 private _Hashtable_ebo_helper<1, _H1>, 
1350 private _Hashtable_ebo_helper<2, _H2> 
1351 { 
1352 private: 
1353 // Gives the local iterator implementation access to _M_h2(). 
1354 friend struct _Local_iterator_base<_Key, _Value, _ExtractKey, _H1, _H2, 
1355 _Default_ranged_hash, true>; 
1356 
1357 using __ebo_extract_key = _Hashtable_ebo_helper<0, _ExtractKey>; 
1358 using __ebo_h1 = _Hashtable_ebo_helper<1, _H1>; 
1359 using __ebo_h2 = _Hashtable_ebo_helper<2, _H2>; 
1360 
1361 public: 
1362 typedef _H1 hasher; 
1363 
1364 hasher 
1365 hash_function() const 
1366 { return _M_h1(); } 
1367 
1368 protected: 
1369 typedef std::size_t __hash_code; 
1370 typedef _Hash_node<_Value, true> __node_type; 
1371 
1372 // We need the default constructor for _Hashtable default constructor. 
1373 _Hash_code_base() = default; 
1374 _Hash_code_base(const _ExtractKey& __ex, 
1375 const _H1& __h1, const _H2& __h2, 
1376 const _Default_ranged_hash&) 
1377 : __ebo_extract_key(__ex), __ebo_h1(__h1), __ebo_h2(__h2) { } 
1378 
1379 __hash_code 
1380 _M_hash_code(const _Key& __k) const 
1381 { 
1382 static_assert(__is_invocable<const _H1&, const _Key&>{}, 
1383 "hash function must be invocable with an argument of key type"); 
1384 return _M_h1()(__k); 
1385 } 
1386 
1387 std::size_t 
1388 _M_bucket_index(const _Key&, __hash_code __c, 
1389 std::size_t __n) const 
1390 { return _M_h2()(__c, __n); } 
1391 
1392 std::size_t 
1393 _M_bucket_index(const __node_type* __p, std::size_t __n) const 
1394 noexcept( noexcept(declval<const _H2&>()((__hash_code)0, 
1395 (std::size_t)0)) ) 
1396 { return _M_h2()(__p->_M_hash_code, __n); } 
1397 
1398 void 
1399 _M_store_code(__node_type* __n, __hash_code __c) const 
1400 { __n->_M_hash_code = __c; } 
1401 
1402 void 
1403 _M_copy_code(__node_type* __to, const __node_type* __from) const 
1404 { __to->_M_hash_code = __from->_M_hash_code; } 
1405 
1406 void 
1407 _M_swap(_Hash_code_base& __x) 
1408 { 
1409 std::swap(_M_extract(), __x._M_extract()); 
1410 std::swap(_M_h1(), __x._M_h1()); 
1411 std::swap(_M_h2(), __x._M_h2()); 
1412 } 
1413 
1414 const _ExtractKey& 
1415 _M_extract() const { return __ebo_extract_key::_S_cget(*this); } 
1416 
1417 _ExtractKey& 
1418 _M_extract() { return __ebo_extract_key::_S_get(*this); } 
1419 
1420 const _H1& 
1421 _M_h1() const { return __ebo_h1::_S_cget(*this); } 
1422 
1423 _H1& 
1424 _M_h1() { return __ebo_h1::_S_get(*this); } 
1425 
1426 const _H2& 
1427 _M_h2() const { return __ebo_h2::_S_cget(*this); } 
1428 
1429 _H2& 
1430 _M_h2() { return __ebo_h2::_S_get(*this); } 
1431 }; 
1432 
1433 /** 
1434 * Primary class template _Equal_helper. 
1435 * 
1436 */ 
1437 template <typename _Key, typename _Value, typename _ExtractKey, 
1438 typename _Equal, typename _HashCodeType, 
1439 bool __cache_hash_code> 
1440 struct _Equal_helper; 
1441 
1442 /// Specialization. 
1443 template<typename _Key, typename _Value, typename _ExtractKey, 
1444 typename _Equal, typename _HashCodeType> 
1445 struct _Equal_helper<_Key, _Value, _ExtractKey, _Equal, _HashCodeType, true> 
1446 { 
1447 static bool 
1448 _S_equals(const _Equal& __eq, const _ExtractKey& __extract, 
1449 const _Key& __k, _HashCodeType __c, _Hash_node<_Value, true>* __n) 
1450 { return __c == __n->_M_hash_code && __eq(__k, __extract(__n->_M_v())); } 
1451 }; 
1452 
1453 /// Specialization. 
1454 template<typename _Key, typename _Value, typename _ExtractKey, 
1455 typename _Equal, typename _HashCodeType> 
1456 struct _Equal_helper<_Key, _Value, _ExtractKey, _Equal, _HashCodeType, false> 
1457 { 
1458 static bool 
1459 _S_equals(const _Equal& __eq, const _ExtractKey& __extract, 
1460 const _Key& __k, _HashCodeType, _Hash_node<_Value, false>* __n) 
1461 { return __eq(__k, __extract(__n->_M_v())); } 
1462 }; 
1463 
1464 
1465 /// Partial specialization used when nodes contain a cached hash code. 
1466 template<typename _Key, typename _Value, typename _ExtractKey, 
1467 typename _H1, typename _H2, typename _Hash> 
1468 struct _Local_iterator_base<_Key, _Value, _ExtractKey, 
1469 _H1, _H2, _Hash, true> 
1470 : private _Hashtable_ebo_helper<0, _H2> 
1471 { 
1472 protected: 
1473 using __base_type = _Hashtable_ebo_helper<0, _H2>; 
1474 using __hash_code_base = _Hash_code_base<_Key, _Value, _ExtractKey, 
1475 _H1, _H2, _Hash, true>; 
1476 
1477 _Local_iterator_base() = default; 
1478 _Local_iterator_base(const __hash_code_base& __base, 
1479 _Hash_node<_Value, true>* __p, 
1480 std::size_t __bkt, std::size_t __bkt_count) 
1481 : __base_type(__base._M_h2()), 
1482 _M_cur(__p), _M_bucket(__bkt), _M_bucket_count(__bkt_count) { } 
1483 
1484 void 
1485 _M_incr() 
1486 { 
1487 _M_cur = _M_cur->_M_next(); 
1488 if (_M_cur) 
1489 { 
1490 std::size_t __bkt 
1491 = __base_type::_S_get(*this)(_M_cur->_M_hash_code, 
1492 _M_bucket_count); 
1493 if (__bkt != _M_bucket) 
1494 _M_cur = nullptr; 
1495 } 
1496 } 
1497 
1498 _Hash_node<_Value, true>* _M_cur; 
1499 std::size_t _M_bucket; 
1500 std::size_t _M_bucket_count; 
1501 
1502 public: 
1503 const void* 
1504 _M_curr() const { return _M_cur; } // for equality ops 
1505 
1506 std::size_t 
1507 _M_get_bucket() const { return _M_bucket; } // for debug mode 
1508 }; 
1509 
1510 // Uninitialized storage for a _Hash_code_base. 
1511 // This type is DefaultConstructible and Assignable even if the 
1512 // _Hash_code_base type isn't, so that _Local_iterator_base<..., false> 
1513 // can be DefaultConstructible and Assignable. 
1514 template<typename _Tp, bool _IsEmpty = std::is_empty<_Tp>::value> 
1515 struct _Hash_code_storage 
1516 { 
1517 __gnu_cxx::__aligned_buffer<_Tp> _M_storage; 
1518 
1519 _Tp* 
1520 _M_h() { return _M_storage._M_ptr(); } 
1521 
1522 const _Tp* 
1523 _M_h() const { return _M_storage._M_ptr(); } 
1524 }; 
1525 
1526 // Empty partial specialization for empty _Hash_code_base types. 
1527 template<typename _Tp> 
1528 struct _Hash_code_storage<_Tp, true> 
1529 { 
1530 static_assert( std::is_empty<_Tp>::value, "Type must be empty" ); 
1531 
1532 // As _Tp is an empty type there will be no bytes written/read through 
1533 // the cast pointer, so no strict-aliasing violation. 
1534 _Tp* 
1535 _M_h() { return reinterpret_cast<_Tp*>(this); } 
1536 
1537 const _Tp* 
1538 _M_h() const { return reinterpret_cast<const _Tp*>(this); } 
1539 }; 
1540 
1541 template<typename _Key, typename _Value, typename _ExtractKey, 
1542 typename _H1, typename _H2, typename _Hash> 
1543 using __hash_code_for_local_iter 
1544 = _Hash_code_storage<_Hash_code_base<_Key, _Value, _ExtractKey, 
1545 _H1, _H2, _Hash, false>>; 
1546 
1547 // Partial specialization used when hash codes are not cached 
1548 template<typename _Key, typename _Value, typename _ExtractKey, 
1549 typename _H1, typename _H2, typename _Hash> 
1550 struct _Local_iterator_base<_Key, _Value, _ExtractKey, 
1551 _H1, _H2, _Hash, false> 
1552 : __hash_code_for_local_iter<_Key, _Value, _ExtractKey, _H1, _H2, _Hash> 
1553 { 
1554 protected: 
1555 using __hash_code_base = _Hash_code_base<_Key, _Value, _ExtractKey, 
1556 _H1, _H2, _Hash, false>; 
1557 
1558 _Local_iterator_base() : _M_bucket_count(-1) { } 
1559 
1560 _Local_iterator_base(const __hash_code_base& __base, 
1561 _Hash_node<_Value, false>* __p, 
1562 std::size_t __bkt, std::size_t __bkt_count) 
1563 : _M_cur(__p), _M_bucket(__bkt), _M_bucket_count(__bkt_count) 
1564 { _M_init(__base); } 
1565 
1566 ~_Local_iterator_base() 
1567 { 
1568 if (_M_bucket_count != -1) 
1569 _M_destroy(); 
1570 } 
1571 
1572 _Local_iterator_base(const _Local_iterator_base& __iter) 
1573 : _M_cur(__iter._M_cur), _M_bucket(__iter._M_bucket), 
1574 _M_bucket_count(__iter._M_bucket_count) 
1575 { 
1576 if (_M_bucket_count != -1) 
1577 _M_init(*__iter._M_h()); 
1578 } 
1579 
1580 _Local_iterator_base& 
1581 operator=(const _Local_iterator_base& __iter) 
1582 { 
1583 if (_M_bucket_count != -1) 
1584 _M_destroy(); 
1585 _M_cur = __iter._M_cur; 
1586 _M_bucket = __iter._M_bucket; 
1587 _M_bucket_count = __iter._M_bucket_count; 
1588 if (_M_bucket_count != -1) 
1589 _M_init(*__iter._M_h()); 
1590 return *this; 
1591 } 
1592 
1593 void 
1594 _M_incr() 
1595 { 
1596 _M_cur = _M_cur->_M_next(); 
1597 if (_M_cur) 
1598 { 
1599 std::size_t __bkt = this->_M_h()->_M_bucket_index(_M_cur, 
1600 _M_bucket_count); 
1601 if (__bkt != _M_bucket) 
1602 _M_cur = nullptr; 
1603 } 
1604 } 
1605 
1606 _Hash_node<_Value, false>* _M_cur; 
1607 std::size_t _M_bucket; 
1608 std::size_t _M_bucket_count; 
1609 
1610 void 
1611 _M_init(const __hash_code_base& __base) 
1612 { ::new(this->_M_h()) __hash_code_base(__base); } 
1613 
1614 void 
1615 _M_destroy() { this->_M_h()->~__hash_code_base(); } 
1616 
1617 public: 
1618 const void* 
1619 _M_curr() const { return _M_cur; } // for equality ops and debug mode 
1620 
1621 std::size_t 
1622 _M_get_bucket() const { return _M_bucket; } // for debug mode 
1623 }; 
1624 
1625 template<typename _Key, typename _Value, typename _ExtractKey, 
1626 typename _H1, typename _H2, typename _Hash, bool __cache> 
1627 inline bool 
1628 operator==(const _Local_iterator_base<_Key, _Value, _ExtractKey, 
1629 _H1, _H2, _Hash, __cache>& __x, 
1630 const _Local_iterator_base<_Key, _Value, _ExtractKey, 
1631 _H1, _H2, _Hash, __cache>& __y) 
1632 { return __x._M_curr() == __y._M_curr(); } 
1633 
1634 template<typename _Key, typename _Value, typename _ExtractKey, 
1635 typename _H1, typename _H2, typename _Hash, bool __cache> 
1636 inline bool 
1637 operator!=(const _Local_iterator_base<_Key, _Value, _ExtractKey, 
1638 _H1, _H2, _Hash, __cache>& __x, 
1639 const _Local_iterator_base<_Key, _Value, _ExtractKey, 
1640 _H1, _H2, _Hash, __cache>& __y) 
1641 { return __x._M_curr() != __y._M_curr(); } 
1642 
1643 /// local iterators 
1644 template<typename _Key, typename _Value, typename _ExtractKey, 
1645 typename _H1, typename _H2, typename _Hash, 
1646 bool __constant_iterators, bool __cache> 
1647 struct _Local_iterator 
1648 : public _Local_iterator_base<_Key, _Value, _ExtractKey, 
1649 _H1, _H2, _Hash, __cache> 
1650 { 
1651 private: 
1652 using __base_type = _Local_iterator_base<_Key, _Value, _ExtractKey, 
1653 _H1, _H2, _Hash, __cache>; 
1654 using __hash_code_base = typename __base_type::__hash_code_base; 
1655 public: 
1656 typedef _Value value_type; 
1657 typedef typename std::conditional<__constant_iterators, 
1658 const _Value*, _Value*>::type 
1659 pointer; 
1660 typedef typename std::conditional<__constant_iterators, 
1661 const _Value&, _Value&>::type 
1662 reference; 
1663 typedef std::ptrdiff_t difference_type; 
1664 typedef std::forward_iterator_tag iterator_category; 
1665 
1666 _Local_iterator() = default; 
1667 
1668 _Local_iterator(const __hash_code_base& __base, 
1669 _Hash_node<_Value, __cache>* __p, 
1670 std::size_t __bkt, std::size_t __bkt_count) 
1671 : __base_type(__base, __p, __bkt, __bkt_count) 
1672 { } 
1673 
1674 reference 
1675 operator*() const 
1676 { return this->_M_cur->_M_v(); } 
1677 
1678 pointer 
1679 operator->() const 
1680 { return this->_M_cur->_M_valptr(); } 
1681 
1682 _Local_iterator& 
1683 operator++() 
1684 { 
1685 this->_M_incr(); 
1686 return *this; 
1687 } 
1688 
1689 _Local_iterator 
1690 operator++(int) 
1691 { 
1692 _Local_iterator __tmp(*this); 
1693 this->_M_incr(); 
1694 return __tmp; 
1695 } 
1696 }; 
1697 
1698 /// local const_iterators 
1699 template<typename _Key, typename _Value, typename _ExtractKey, 
1700 typename _H1, typename _H2, typename _Hash, 
1701 bool __constant_iterators, bool __cache> 
1702 struct _Local_const_iterator 
1703 : public _Local_iterator_base<_Key, _Value, _ExtractKey, 
1704 _H1, _H2, _Hash, __cache> 
1705 { 
1706 private: 
1707 using __base_type = _Local_iterator_base<_Key, _Value, _ExtractKey, 
1708 _H1, _H2, _Hash, __cache>; 
1709 using __hash_code_base = typename __base_type::__hash_code_base; 
1710 
1711 public: 
1712 typedef _Value value_type; 
1713 typedef const _Value* pointer; 
1714 typedef const _Value& reference; 
1715 typedef std::ptrdiff_t difference_type; 
1716 typedef std::forward_iterator_tag iterator_category; 
1717 
1718 _Local_const_iterator() = default; 
1719 
1720 _Local_const_iterator(const __hash_code_base& __base, 
1721 _Hash_node<_Value, __cache>* __p, 
1722 std::size_t __bkt, std::size_t __bkt_count) 
1723 : __base_type(__base, __p, __bkt, __bkt_count) 
1724 { } 
1725 
1726 _Local_const_iterator(const _Local_iterator<_Key, _Value, _ExtractKey, 
1727 _H1, _H2, _Hash, 
1728 __constant_iterators, 
1729 __cache>& __x) 
1730 : __base_type(__x) 
1731 { } 
1732 
1733 reference 
1734 operator*() const 
1735 { return this->_M_cur->_M_v(); } 
1736 
1737 pointer 
1738 operator->() const 
1739 { return this->_M_cur->_M_valptr(); } 
1740 
1741 _Local_const_iterator& 
1742 operator++() 
1743 { 
1744 this->_M_incr(); 
1745 return *this; 
1746 } 
1747 
1748 _Local_const_iterator 
1749 operator++(int) 
1750 { 
1751 _Local_const_iterator __tmp(*this); 
1752 this->_M_incr(); 
1753 return __tmp; 
1754 } 
1755 }; 
1756 
1757 /** 
1758 * Primary class template _Hashtable_base. 
1759 * 
1760 * Helper class adding management of _Equal functor to 
1761 * _Hash_code_base type. 
1762 * 
1763 * Base class templates are: 
1764 * - __detail::_Hash_code_base 
1765 * - __detail::_Hashtable_ebo_helper 
1766 */ 
1767 template<typename _Key, typename _Value, 
1768 typename _ExtractKey, typename _Equal, 
1769 typename _H1, typename _H2, typename _Hash, typename _Traits> 
1770 struct _Hashtable_base 
1771 : public _Hash_code_base<_Key, _Value, _ExtractKey, _H1, _H2, _Hash, 
1772 _Traits::__hash_cached::value>, 
1773 private _Hashtable_ebo_helper<0, _Equal> 
1774 { 
1775 public: 
1776 typedef _Key key_type; 
1777 typedef _Value value_type; 
1778 typedef _Equal key_equal; 
1779 typedef std::size_t size_type; 
1780 typedef std::ptrdiff_t difference_type; 
1781 
1782 using __traits_type = _Traits; 
1783 using __hash_cached = typename __traits_type::__hash_cached; 
1784 using __constant_iterators = typename __traits_type::__constant_iterators; 
1785 using __unique_keys = typename __traits_type::__unique_keys; 
1786 
1787 using __hash_code_base = _Hash_code_base<_Key, _Value, _ExtractKey, 
1788 _H1, _H2, _Hash, 
1789 __hash_cached::value>; 
1790 
1791 using __hash_code = typename __hash_code_base::__hash_code; 
1792 using __node_type = typename __hash_code_base::__node_type; 
1793 
1794 using iterator = __detail::_Node_iterator<value_type, 
1795 __constant_iterators::value, 
1796 __hash_cached::value>; 
1797 
1798 using const_iterator = __detail::_Node_const_iterator<value_type, 
1799 __constant_iterators::value, 
1800 __hash_cached::value>; 
1801 
1802 using local_iterator = __detail::_Local_iterator<key_type, value_type, 
1803 _ExtractKey, _H1, _H2, _Hash, 
1804 __constant_iterators::value, 
1805 __hash_cached::value>; 
1806 
1807 using const_local_iterator = __detail::_Local_const_iterator<key_type, 
1808 value_type, 
1809 _ExtractKey, _H1, _H2, _Hash, 
1810 __constant_iterators::value, 
1811 __hash_cached::value>; 
1812 
1813 using __ireturn_type = typename std::conditional<__unique_keys::value, 
1814 std::pair<iterator, bool>, 
1815 iterator>::type; 
1816 private: 
1817 using _EqualEBO = _Hashtable_ebo_helper<0, _Equal>; 
1818 using _EqualHelper = _Equal_helper<_Key, _Value, _ExtractKey, _Equal, 
1819 __hash_code, __hash_cached::value>; 
1820 
1821 protected: 
1822 _Hashtable_base() = default; 
1823 _Hashtable_base(const _ExtractKey& __ex, const _H1& __h1, const _H2& __h2, 
1824 const _Hash& __hash, const _Equal& __eq) 
1825 : __hash_code_base(__ex, __h1, __h2, __hash), _EqualEBO(__eq) 
1826 { } 
1827 
1828 bool 
1829 _M_equals(const _Key& __k, __hash_code __c, __node_type* __n) const 
1830 { 
1831 static_assert(__is_invocable<const _Equal&, const _Key&, const _Key&>{}, 
1832 "key equality predicate must be invocable with two arguments of " 
1833 "key type"); 
1834 return _EqualHelper::_S_equals(_M_eq(), this->_M_extract(), 
1835 __k, __c, __n); 
1836 } 
1837 
1838 void 
1839 _M_swap(_Hashtable_base& __x) 
1840 { 
1841 __hash_code_base::_M_swap(__x); 
1842 std::swap(_M_eq(), __x._M_eq()); 
1843 } 
1844 
1845 const _Equal& 
1846 _M_eq() const { return _EqualEBO::_S_cget(*this); } 
1847 
1848 _Equal& 
1849 _M_eq() { return _EqualEBO::_S_get(*this); } 
1850 }; 
1851 
1852 /** 
1853 * struct _Equality_base. 
1854 * 
1855 * Common types and functions for class _Equality. 
1856 */ 
1857 struct _Equality_base 
1858 { 
1859 protected: 
1860 template<typename _Uiterator> 
1861 static bool 
1862 _S_is_permutation(_Uiterator, _Uiterator, _Uiterator); 
1863 }; 
1864 
1865 // See std::is_permutation in N3068. 
1866 template<typename _Uiterator> 
1867 bool 
1868 _Equality_base:: 
1869 _S_is_permutation(_Uiterator __first1, _Uiterator __last1, 
1870 _Uiterator __first2) 
1871 { 
1872 for (; __first1 != __last1; ++__first1, ++__first2) 
1873 if (!(*__first1 == *__first2)) 
1874 break; 
1875 
1876 if (__first1 == __last1) 
1877 return true; 
1878 
1879 _Uiterator __last2 = __first2; 
1880 std::advance(__last2, std::distance(__first1, __last1)); 
1881 
1882 for (_Uiterator __it1 = __first1; __it1 != __last1; ++__it1) 
1883 { 
1884 _Uiterator __tmp = __first1; 
1885 while (__tmp != __it1 && !bool(*__tmp == *__it1)) 
1886 ++__tmp; 
1887 
1888 // We've seen this one before. 
1889 if (__tmp != __it1) 
1890 continue; 
1891 
1892 std::ptrdiff_t __n2 = 0; 
1893 for (__tmp = __first2; __tmp != __last2; ++__tmp) 
1894 if (*__tmp == *__it1) 
1895 ++__n2; 
1896 
1897 if (!__n2) 
1898 return false; 
1899 
1900 std::ptrdiff_t __n1 = 0; 
1901 for (__tmp = __it1; __tmp != __last1; ++__tmp) 
1902 if (*__tmp == *__it1) 
1903 ++__n1; 
1904 
1905 if (__n1 != __n2) 
1906 return false; 
1907 } 
1908 return true; 
1909 } 
1910 
1911 /** 
1912 * Primary class template _Equality. 
1913 * 
1914 * This is for implementing equality comparison for unordered 
1915 * containers, per N3068, by John Lakos and Pablo Halpern. 
1916 * Algorithmically, we follow closely the reference implementations 
1917 * therein. 
1918 */ 
1919 template<typename _Key, typename _Value, typename _Alloc, 
1920 typename _ExtractKey, typename _Equal, 
1921 typename _H1, typename _H2, typename _Hash, 
1922 typename _RehashPolicy, typename _Traits, 
1923 bool _Unique_keys = _Traits::__unique_keys::value> 
1924 struct _Equality; 
1925 
1926 /// Specialization. 
1927 template<typename _Key, typename _Value, typename _Alloc, 
1928 typename _ExtractKey, typename _Equal, 
1929 typename _H1, typename _H2, typename _Hash, 
1930 typename _RehashPolicy, typename _Traits> 
1931 struct _Equality<_Key, _Value, _Alloc, _ExtractKey, _Equal, 
1932 _H1, _H2, _Hash, _RehashPolicy, _Traits, true> 
1933 { 
1934 using __hashtable = _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, 
1935 _H1, _H2, _Hash, _RehashPolicy, _Traits>; 
1936 
1937 bool 
1938 _M_equal(const __hashtable&) const; 
1939 }; 
1940 
1941 template<typename _Key, typename _Value, typename _Alloc, 
1942 typename _ExtractKey, typename _Equal, 
1943 typename _H1, typename _H2, typename _Hash, 
1944 typename _RehashPolicy, typename _Traits> 
1945 bool 
1946 _Equality<_Key, _Value, _Alloc, _ExtractKey, _Equal, 
1947 _H1, _H2, _Hash, _RehashPolicy, _Traits, true>:: 
1948 _M_equal(const __hashtable& __other) const 
1949 { 
1950 const __hashtable* __this = static_cast<const __hashtable*>(this); 
1951 
1952 if (__this->size() != __other.size()) 
1953 return false; 
1954 
1955 for (auto __itx = __this->begin(); __itx != __this->end(); ++__itx) 
1956 { 
1957 const auto __ity = __other.find(_ExtractKey()(*__itx)); 
1958 if (__ity == __other.end() || !bool(*__ity == *__itx)) 
1959 return false; 
1960 } 
1961 return true; 
1962 } 
1963 
1964 /// Specialization. 
1965 template<typename _Key, typename _Value, typename _Alloc, 
1966 typename _ExtractKey, typename _Equal, 
1967 typename _H1, typename _H2, typename _Hash, 
1968 typename _RehashPolicy, typename _Traits> 
1969 struct _Equality<_Key, _Value, _Alloc, _ExtractKey, _Equal, 
1970 _H1, _H2, _Hash, _RehashPolicy, _Traits, false> 
1971 : public _Equality_base 
1972 { 
1973 using __hashtable = _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, 
1974 _H1, _H2, _Hash, _RehashPolicy, _Traits>; 
1975 
1976 bool 
1977 _M_equal(const __hashtable&) const; 
1978 }; 
1979 
1980 template<typename _Key, typename _Value, typename _Alloc, 
1981 typename _ExtractKey, typename _Equal, 
1982 typename _H1, typename _H2, typename _Hash, 
1983 typename _RehashPolicy, typename _Traits> 
1984 bool 
1985 _Equality<_Key, _Value, _Alloc, _ExtractKey, _Equal, 
1986 _H1, _H2, _Hash, _RehashPolicy, _Traits, false>:: 
1987 _M_equal(const __hashtable& __other) const 
1988 { 
1989 const __hashtable* __this = static_cast<const __hashtable*>(this); 
1990 
1991 if (__this->size() != __other.size()) 
1992 return false; 
1993 
1994 for (auto __itx = __this->begin(); __itx != __this->end();) 
1995 { 
1996 const auto __xrange = __this->equal_range(_ExtractKey()(*__itx)); 
1997 const auto __yrange = __other.equal_range(_ExtractKey()(*__itx)); 
1998 
1999 if (std::distance(__xrange.first, __xrange.second) 
2000 != std::distance(__yrange.first, __yrange.second)) 
2001 return false; 
2002 
2003 if (!_S_is_permutation(__xrange.first, __xrange.second, 
2004 __yrange.first)) 
2005 return false; 
2006 
2007 __itx = __xrange.second; 
2008 } 
2009 return true; 
2010 } 
2011 
2012 /** 
2013 * This type deals with all allocation and keeps an allocator instance through 
2014 * inheritance to benefit from EBO when possible. 
2015 */ 
2016 template<typename _NodeAlloc> 
2017 struct _Hashtable_alloc : private _Hashtable_ebo_helper<0, _NodeAlloc> 
2018 { 
2019 private: 
2020 using __ebo_node_alloc = _Hashtable_ebo_helper<0, _NodeAlloc>; 
2021 public: 
2022 using __node_type = typename _NodeAlloc::value_type; 
2023 using __node_alloc_type = _NodeAlloc; 
2024 // Use __gnu_cxx to benefit from _S_always_equal and al. 
2025 using __node_alloc_traits = __gnu_cxx::__alloc_traits<__node_alloc_type>; 
2026 
2027 using __value_alloc_traits = typename __node_alloc_traits::template 
2028 rebind_traits<typename __node_type::value_type>; 
2029 
2030 using __node_base = __detail::_Hash_node_base; 
2031 using __bucket_type = __node_base*;  
2032 using __bucket_alloc_type = 
2033 __alloc_rebind<__node_alloc_type, __bucket_type>; 
2034 using __bucket_alloc_traits = std::allocator_traits<__bucket_alloc_type>; 
2035 
2036 _Hashtable_alloc() = default; 
2037 _Hashtable_alloc(const _Hashtable_alloc&) = default; 
2038 _Hashtable_alloc(_Hashtable_alloc&&) = default; 
2039 
2040 template<typename _Alloc> 
2041 _Hashtable_alloc(_Alloc&& __a) 
2042 : __ebo_node_alloc(std::forward<_Alloc>(__a)) 
2043 { } 
2044 
2045 __node_alloc_type& 
2046 _M_node_allocator() 
2047 { return __ebo_node_alloc::_S_get(*this); } 
2048 
2049 const __node_alloc_type& 
2050 _M_node_allocator() const 
2051 { return __ebo_node_alloc::_S_cget(*this); } 
2052 
2053 template<typename... _Args> 
2054 __node_type* 
2055 _M_allocate_node(_Args&&... __args); 
2056 
2057 void 
2058 _M_deallocate_node(__node_type* __n); 
2059 
2060 void 
2061 _M_deallocate_node_ptr(__node_type* __n); 
2062 
2063 // Deallocate the linked list of nodes pointed to by __n 
2064 void 
2065 _M_deallocate_nodes(__node_type* __n); 
2066 
2067 __bucket_type* 
2068 _M_allocate_buckets(std::size_t __n); 
2069 
2070 void 
2071 _M_deallocate_buckets(__bucket_type*, std::size_t __n); 
2072 }; 
2073 
2074 // Definitions of class template _Hashtable_alloc's out-of-line member 
2075 // functions. 
2076 template<typename _NodeAlloc> 
2077 template<typename... _Args> 
2078 typename _Hashtable_alloc<_NodeAlloc>::__node_type* 
2079 _Hashtable_alloc<_NodeAlloc>::_M_allocate_node(_Args&&... __args) 
2080 { 
2081 auto __nptr = __node_alloc_traits::allocate(_M_node_allocator(), 1); 
2082 __node_type* __n = std::__to_address(__nptr); 
2083 __try 
2084 { 
2085 ::new ((void*)__n) __node_type; 
2086 __node_alloc_traits::construct(_M_node_allocator(), 
2087 __n->_M_valptr(), 
2088 std::forward<_Args>(__args)...); 
2089 return __n; 
2090 } 
2091 __catch(...) 
2092 { 
2093 __node_alloc_traits::deallocate(_M_node_allocator(), __nptr, 1); 
2094 __throw_exception_again; 
2095 } 
2096 } 
2097 
2098 template<typename _NodeAlloc> 
2099 void 
2100 _Hashtable_alloc<_NodeAlloc>::_M_deallocate_node(__node_type* __n) 
2101 { 
2102 __node_alloc_traits::destroy(_M_node_allocator(), __n->_M_valptr()); 
2103 _M_deallocate_node_ptr(__n); 
2104 } 
2105 
2106 template<typename _NodeAlloc> 
2107 void 
2108 _Hashtable_alloc<_NodeAlloc>::_M_deallocate_node_ptr(__node_type* __n) 
2109 { 
2110 typedef typename __node_alloc_traits::pointer _Ptr; 
2111 auto __ptr = std::pointer_traits<_Ptr>::pointer_to(*__n); 
2112 __n->~__node_type(); 
2113 __node_alloc_traits::deallocate(_M_node_allocator(), __ptr, 1); 
2114 } 
2115 
2116 template<typename _NodeAlloc> 
2117 void 
2118 _Hashtable_alloc<_NodeAlloc>::_M_deallocate_nodes(__node_type* __n) 
2119 { 
2120 while (__n) 
2121 { 
2122 __node_type* __tmp = __n; 
2123 __n = __n->_M_next(); 
2124 _M_deallocate_node(__tmp); 
2125 } 
2126 } 
2127 
2128 template<typename _NodeAlloc> 
2129 typename _Hashtable_alloc<_NodeAlloc>::__bucket_type* 
2130 _Hashtable_alloc<_NodeAlloc>::_M_allocate_buckets(std::size_t __n) 
2131 { 
2132 __bucket_alloc_type __alloc(_M_node_allocator()); 
2133 
2134 auto __ptr = __bucket_alloc_traits::allocate(__alloc, __n); 
2135 __bucket_type* __p = std::__to_address(__ptr); 
2136 __builtin_memset(__p, 0, __n * sizeof(__bucket_type)); 
2137 return __p; 
2138 } 
2139 
2140 template<typename _NodeAlloc> 
2141 void 
2142 _Hashtable_alloc<_NodeAlloc>::_M_deallocate_buckets(__bucket_type* __bkts, 
2143 std::size_t __n) 
2144 { 
2145 typedef typename __bucket_alloc_traits::pointer _Ptr; 
2146 auto __ptr = std::pointer_traits<_Ptr>::pointer_to(*__bkts); 
2147 __bucket_alloc_type __alloc(_M_node_allocator()); 
2148 __bucket_alloc_traits::deallocate(__alloc, __ptr, __n); 
2149 } 
2150 
2151 //@} hashtable-detail 
2152} // namespace __detail 
2153_GLIBCXX_END_NAMESPACE_VERSION 
2154} // namespace std 
2155 
2156#endif // _HASHTABLE_POLICY_H 
2157