1// hashtable.h header -*- C++ -*- 
2 
3// Copyright (C) 2007-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.h 
26 * This is an internal header file, included by other library headers. 
27 * Do not attempt to use it directly. @headername{unordered_map, unordered_set} 
28 */ 
29 
30#ifndef _HASHTABLE_H 
31#define _HASHTABLE_H 1 
32 
33#pragma GCC system_header 
34 
35#include <bits/hashtable_policy.h> 
36#if __cplusplus > 201402L 
37# include <bits/node_handle.h> 
38#endif 
39 
40namespace std _GLIBCXX_VISIBILITY(default) 
41{ 
42_GLIBCXX_BEGIN_NAMESPACE_VERSION 
43 
44 template<typename _Tp, typename _Hash> 
45 using __cache_default 
46 = __not_<__and_<// Do not cache for fast hasher. 
47 __is_fast_hash<_Hash>, 
48 // Mandatory to have erase not throwing. 
49 __is_nothrow_invocable<const _Hash&, const _Tp&>>>; 
50 
51 /** 
52 * Primary class template _Hashtable. 
53 * 
54 * @ingroup hashtable-detail 
55 * 
56 * @tparam _Value CopyConstructible type. 
57 * 
58 * @tparam _Key CopyConstructible type. 
59 * 
60 * @tparam _Alloc An allocator type 
61 * ([lib.allocator.requirements]) whose _Alloc::value_type is 
62 * _Value. As a conforming extension, we allow for 
63 * _Alloc::value_type != _Value. 
64 * 
65 * @tparam _ExtractKey Function object that takes an object of type 
66 * _Value and returns a value of type _Key. 
67 * 
68 * @tparam _Equal Function object that takes two objects of type k 
69 * and returns a bool-like value that is true if the two objects 
70 * are considered equal. 
71 * 
72 * @tparam _H1 The hash function. A unary function object with 
73 * argument type _Key and result type size_t. Return values should 
74 * be distributed over the entire range [0, numeric_limits<size_t>:::max()]. 
75 * 
76 * @tparam _H2 The range-hashing function (in the terminology of 
77 * Tavori and Dreizin). A binary function object whose argument 
78 * types and result type are all size_t. Given arguments r and N, 
79 * the return value is in the range [0, N). 
80 * 
81 * @tparam _Hash The ranged hash function (Tavori and Dreizin). A 
82 * binary function whose argument types are _Key and size_t and 
83 * whose result type is size_t. Given arguments k and N, the 
84 * return value is in the range [0, N). Default: hash(k, N) = 
85 * h2(h1(k), N). If _Hash is anything other than the default, _H1 
86 * and _H2 are ignored. 
87 * 
88 * @tparam _RehashPolicy Policy class with three members, all of 
89 * which govern the bucket count. _M_next_bkt(n) returns a bucket 
90 * count no smaller than n. _M_bkt_for_elements(n) returns a 
91 * bucket count appropriate for an element count of n. 
92 * _M_need_rehash(n_bkt, n_elt, n_ins) determines whether, if the 
93 * current bucket count is n_bkt and the current element count is 
94 * n_elt, we need to increase the bucket count. If so, returns 
95 * make_pair(true, n), where n is the new bucket count. If not, 
96 * returns make_pair(false, <anything>) 
97 * 
98 * @tparam _Traits Compile-time class with three boolean 
99 * std::integral_constant members: __cache_hash_code, __constant_iterators, 
100 * __unique_keys. 
101 * 
102 * Each _Hashtable data structure has: 
103 * 
104 * - _Bucket[] _M_buckets 
105 * - _Hash_node_base _M_before_begin 
106 * - size_type _M_bucket_count 
107 * - size_type _M_element_count 
108 * 
109 * with _Bucket being _Hash_node* and _Hash_node containing: 
110 * 
111 * - _Hash_node* _M_next 
112 * - Tp _M_value 
113 * - size_t _M_hash_code if cache_hash_code is true 
114 * 
115 * In terms of Standard containers the hashtable is like the aggregation of: 
116 * 
117 * - std::forward_list<_Node> containing the elements 
118 * - std::vector<std::forward_list<_Node>::iterator> representing the buckets 
119 * 
120 * The non-empty buckets contain the node before the first node in the 
121 * bucket. This design makes it possible to implement something like a 
122 * std::forward_list::insert_after on container insertion and 
123 * std::forward_list::erase_after on container erase 
124 * calls. _M_before_begin is equivalent to 
125 * std::forward_list::before_begin. Empty buckets contain 
126 * nullptr. Note that one of the non-empty buckets contains 
127 * &_M_before_begin which is not a dereferenceable node so the 
128 * node pointer in a bucket shall never be dereferenced, only its 
129 * next node can be. 
130 * 
131 * Walking through a bucket's nodes requires a check on the hash code to 
132 * see if each node is still in the bucket. Such a design assumes a 
133 * quite efficient hash functor and is one of the reasons it is 
134 * highly advisable to set __cache_hash_code to true. 
135 * 
136 * The container iterators are simply built from nodes. This way 
137 * incrementing the iterator is perfectly efficient independent of 
138 * how many empty buckets there are in the container. 
139 * 
140 * On insert we compute the element's hash code and use it to find the 
141 * bucket index. If the element must be inserted in an empty bucket 
142 * we add it at the beginning of the singly linked list and make the 
143 * bucket point to _M_before_begin. The bucket that used to point to 
144 * _M_before_begin, if any, is updated to point to its new before 
145 * begin node. 
146 * 
147 * On erase, the simple iterator design requires using the hash 
148 * functor to get the index of the bucket to update. For this 
149 * reason, when __cache_hash_code is set to false the hash functor must 
150 * not throw and this is enforced by a static assertion. 
151 * 
152 * Functionality is implemented by decomposition into base classes, 
153 * where the derived _Hashtable class is used in _Map_base, 
154 * _Insert, _Rehash_base, and _Equality base classes to access the 
155 * "this" pointer. _Hashtable_base is used in the base classes as a 
156 * non-recursive, fully-completed-type so that detailed nested type 
157 * information, such as iterator type and node type, can be 
158 * used. This is similar to the "Curiously Recurring Template 
159 * Pattern" (CRTP) technique, but uses a reconstructed, not 
160 * explicitly passed, template pattern. 
161 * 
162 * Base class templates are:  
163 * - __detail::_Hashtable_base 
164 * - __detail::_Map_base 
165 * - __detail::_Insert 
166 * - __detail::_Rehash_base 
167 * - __detail::_Equality 
168 */ 
169 template<typename _Key, typename _Value, typename _Alloc, 
170 typename _ExtractKey, typename _Equal, 
171 typename _H1, typename _H2, typename _Hash, 
172 typename _RehashPolicy, typename _Traits> 
173 class _Hashtable 
174 : public __detail::_Hashtable_base<_Key, _Value, _ExtractKey, _Equal, 
175 _H1, _H2, _Hash, _Traits>, 
176 public __detail::_Map_base<_Key, _Value, _Alloc, _ExtractKey, _Equal, 
177 _H1, _H2, _Hash, _RehashPolicy, _Traits>, 
178 public __detail::_Insert<_Key, _Value, _Alloc, _ExtractKey, _Equal, 
179 _H1, _H2, _Hash, _RehashPolicy, _Traits>, 
180 public __detail::_Rehash_base<_Key, _Value, _Alloc, _ExtractKey, _Equal, 
181 _H1, _H2, _Hash, _RehashPolicy, _Traits>, 
182 public __detail::_Equality<_Key, _Value, _Alloc, _ExtractKey, _Equal, 
183 _H1, _H2, _Hash, _RehashPolicy, _Traits>, 
184 private __detail::_Hashtable_alloc< 
185 __alloc_rebind<_Alloc, 
186 __detail::_Hash_node<_Value, 
187 _Traits::__hash_cached::value>>> 
188 { 
189 static_assert(is_same<typename remove_cv<_Value>::type, _Value>::value, 
190 "unordered container must have a non-const, non-volatile value_type"); 
191#ifdef __STRICT_ANSI__ 
192 static_assert(is_same<typename _Alloc::value_type, _Value>{}, 
193 "unordered container must have the same value_type as its allocator"); 
194#endif 
195 
196 using __traits_type = _Traits; 
197 using __hash_cached = typename __traits_type::__hash_cached; 
198 using __node_type = __detail::_Hash_node<_Value, __hash_cached::value>; 
199 using __node_alloc_type = __alloc_rebind<_Alloc, __node_type>; 
200 
201 using __hashtable_alloc = __detail::_Hashtable_alloc<__node_alloc_type>; 
202 
203 using __value_alloc_traits = 
204 typename __hashtable_alloc::__value_alloc_traits; 
205 using __node_alloc_traits = 
206 typename __hashtable_alloc::__node_alloc_traits; 
207 using __node_base = typename __hashtable_alloc::__node_base; 
208 using __bucket_type = typename __hashtable_alloc::__bucket_type; 
209 
210 public: 
211 typedef _Key key_type; 
212 typedef _Value value_type; 
213 typedef _Alloc allocator_type; 
214 typedef _Equal key_equal; 
215 
216 // mapped_type, if present, comes from _Map_base. 
217 // hasher, if present, comes from _Hash_code_base/_Hashtable_base. 
218 typedef typename __value_alloc_traits::pointer pointer; 
219 typedef typename __value_alloc_traits::const_pointer const_pointer; 
220 typedef value_type& reference; 
221 typedef const value_type& const_reference; 
222 
223 private: 
224 using __rehash_type = _RehashPolicy; 
225 using __rehash_state = typename __rehash_type::_State; 
226 
227 using __constant_iterators = typename __traits_type::__constant_iterators; 
228 using __unique_keys = typename __traits_type::__unique_keys; 
229 
230 using __key_extract = typename std::conditional< 
231 __constant_iterators::value, 
232 __detail::_Identity, 
233 __detail::_Select1st>::type; 
234 
235 using __hashtable_base = __detail:: 
236 _Hashtable_base<_Key, _Value, _ExtractKey, 
237 _Equal, _H1, _H2, _Hash, _Traits>; 
238 
239 using __hash_code_base = typename __hashtable_base::__hash_code_base; 
240 using __hash_code = typename __hashtable_base::__hash_code; 
241 using __ireturn_type = typename __hashtable_base::__ireturn_type; 
242 
243 using __map_base = __detail::_Map_base<_Key, _Value, _Alloc, _ExtractKey, 
244 _Equal, _H1, _H2, _Hash, 
245 _RehashPolicy, _Traits>; 
246 
247 using __rehash_base = __detail::_Rehash_base<_Key, _Value, _Alloc, 
248 _ExtractKey, _Equal, 
249 _H1, _H2, _Hash, 
250 _RehashPolicy, _Traits>; 
251 
252 using __eq_base = __detail::_Equality<_Key, _Value, _Alloc, _ExtractKey, 
253 _Equal, _H1, _H2, _Hash, 
254 _RehashPolicy, _Traits>; 
255 
256 using __reuse_or_alloc_node_type = 
257 __detail::_ReuseOrAllocNode<__node_alloc_type>; 
258 
259 // Metaprogramming for picking apart hash caching. 
260 template<typename _Cond> 
261 using __if_hash_cached = __or_<__not_<__hash_cached>, _Cond>; 
262 
263 template<typename _Cond> 
264 using __if_hash_not_cached = __or_<__hash_cached, _Cond>; 
265 
266 // Compile-time diagnostics. 
267 
268 // _Hash_code_base has everything protected, so use this derived type to 
269 // access it. 
270 struct __hash_code_base_access : __hash_code_base 
271 { using __hash_code_base::_M_bucket_index; }; 
272 
273 // Getting a bucket index from a node shall not throw because it is used 
274 // in methods (erase, swap...) that shall not throw. 
275 static_assert(noexcept(declval<const __hash_code_base_access&>() 
276 ._M_bucket_index((const __node_type*)nullptr, 
277 (std::size_t)0)), 
278 "Cache the hash code or qualify your functors involved" 
279 " in hash code and bucket index computation with noexcept"); 
280 
281 // Following two static assertions are necessary to guarantee 
282 // that local_iterator will be default constructible. 
283 
284 // When hash codes are cached local iterator inherits from H2 functor 
285 // which must then be default constructible. 
286 static_assert(__if_hash_cached<is_default_constructible<_H2>>::value, 
287 "Functor used to map hash code to bucket index" 
288 " must be default constructible"); 
289 
290 template<typename _Keya, typename _Valuea, typename _Alloca, 
291 typename _ExtractKeya, typename _Equala, 
292 typename _H1a, typename _H2a, typename _Hasha, 
293 typename _RehashPolicya, typename _Traitsa, 
294 bool _Unique_keysa> 
295 friend struct __detail::_Map_base; 
296 
297 template<typename _Keya, typename _Valuea, typename _Alloca, 
298 typename _ExtractKeya, typename _Equala, 
299 typename _H1a, typename _H2a, typename _Hasha, 
300 typename _RehashPolicya, typename _Traitsa> 
301 friend struct __detail::_Insert_base; 
302 
303 template<typename _Keya, typename _Valuea, typename _Alloca, 
304 typename _ExtractKeya, typename _Equala, 
305 typename _H1a, typename _H2a, typename _Hasha, 
306 typename _RehashPolicya, typename _Traitsa, 
307 bool _Constant_iteratorsa> 
308 friend struct __detail::_Insert; 
309 
310 public: 
311 using size_type = typename __hashtable_base::size_type; 
312 using difference_type = typename __hashtable_base::difference_type; 
313 
314 using iterator = typename __hashtable_base::iterator; 
315 using const_iterator = typename __hashtable_base::const_iterator; 
316 
317 using local_iterator = typename __hashtable_base::local_iterator; 
318 using const_local_iterator = typename __hashtable_base:: 
319 const_local_iterator; 
320 
321#if __cplusplus > 201402L 
322 using node_type = _Node_handle<_Key, _Value, __node_alloc_type>; 
323 using insert_return_type = _Node_insert_return<iterator, node_type>; 
324#endif 
325 
326 private: 
327 __bucket_type* _M_buckets = &_M_single_bucket; 
328 size_type _M_bucket_count = 1; 
329 __node_base _M_before_begin; 
330 size_type _M_element_count = 0; 
331 _RehashPolicy _M_rehash_policy; 
332 
333 // A single bucket used when only need for 1 bucket. Especially 
334 // interesting in move semantic to leave hashtable with only 1 buckets 
335 // which is not allocated so that we can have those operations noexcept 
336 // qualified. 
337 // Note that we can't leave hashtable with 0 bucket without adding 
338 // numerous checks in the code to avoid 0 modulus. 
339 __bucket_type _M_single_bucket = nullptr; 
340 
341 bool 
342 _M_uses_single_bucket(__bucket_type* __bkts) const 
343 { return __builtin_expect(__bkts == &_M_single_bucket, false); } 
344 
345 bool 
346 _M_uses_single_bucket() const 
347 { return _M_uses_single_bucket(_M_buckets); } 
348 
349 __hashtable_alloc& 
350 _M_base_alloc() { return *this; } 
351 
352 __bucket_type* 
353 _M_allocate_buckets(size_type __n) 
354 { 
355 if (__builtin_expect(__n == 1, false)) 
356 { 
357 _M_single_bucket = nullptr; 
358 return &_M_single_bucket; 
359 } 
360 
361 return __hashtable_alloc::_M_allocate_buckets(__n); 
362 } 
363 
364 void 
365 _M_deallocate_buckets(__bucket_type* __bkts, size_type __n) 
366 { 
367 if (_M_uses_single_bucket(__bkts)) 
368 return; 
369 
370 __hashtable_alloc::_M_deallocate_buckets(__bkts, __n); 
371 } 
372 
373 void 
374 _M_deallocate_buckets() 
375 { _M_deallocate_buckets(_M_buckets, _M_bucket_count); } 
376 
377 // Gets bucket begin, deals with the fact that non-empty buckets contain 
378 // their before begin node. 
379 __node_type* 
380 _M_bucket_begin(size_type __bkt) const; 
381 
382 __node_type* 
383 _M_begin() const 
384 { return static_cast<__node_type*>(_M_before_begin._M_nxt); } 
385 
386 // Assign *this using another _Hashtable instance. Either elements 
387 // are copy or move depends on the _NodeGenerator. 
388 template<typename _Ht, typename _NodeGenerator> 
389 void 
390 _M_assign_elements(_Ht&&, const _NodeGenerator&); 
391 
392 template<typename _NodeGenerator> 
393 void 
394 _M_assign(const _Hashtable&, const _NodeGenerator&); 
395 
396 void 
397 _M_move_assign(_Hashtable&&, std::true_type); 
398 
399 void 
400 _M_move_assign(_Hashtable&&, std::false_type); 
401 
402 void 
403 _M_reset() noexcept; 
404 
405 _Hashtable(const _H1& __h1, const _H2& __h2, const _Hash& __h, 
406 const _Equal& __eq, const _ExtractKey& __exk, 
407 const allocator_type& __a) 
408 : __hashtable_base(__exk, __h1, __h2, __h, __eq), 
409 __hashtable_alloc(__node_alloc_type(__a)) 
410 { } 
411 
412 public: 
413 // Constructor, destructor, assignment, swap 
414 _Hashtable() = default; 
415 _Hashtable(size_type __bucket_hint, 
416 const _H1&, const _H2&, const _Hash&, 
417 const _Equal&, const _ExtractKey&, 
418 const allocator_type&); 
419 
420 template<typename _InputIterator> 
421 _Hashtable(_InputIterator __first, _InputIterator __last, 
422 size_type __bucket_hint, 
423 const _H1&, const _H2&, const _Hash&, 
424 const _Equal&, const _ExtractKey&, 
425 const allocator_type&); 
426 
427 _Hashtable(const _Hashtable&); 
428 
429 _Hashtable(_Hashtable&&) noexcept; 
430 
431 _Hashtable(const _Hashtable&, const allocator_type&); 
432 
433 _Hashtable(_Hashtable&&, const allocator_type&); 
434 
435 // Use delegating constructors. 
436 explicit 
437 _Hashtable(const allocator_type& __a) 
438 : __hashtable_alloc(__node_alloc_type(__a)) 
439 { } 
440 
441 explicit 
442 _Hashtable(size_type __n, 
443 const _H1& __hf = _H1(), 
444 const key_equal& __eql = key_equal(), 
445 const allocator_type& __a = allocator_type()) 
446 : _Hashtable(__n, __hf, _H2(), _Hash(), __eql, 
447 __key_extract(), __a) 
448 { } 
449 
450 template<typename _InputIterator> 
451 _Hashtable(_InputIterator __f, _InputIterator __l, 
452 size_type __n = 0, 
453 const _H1& __hf = _H1(), 
454 const key_equal& __eql = key_equal(), 
455 const allocator_type& __a = allocator_type()) 
456 : _Hashtable(__f, __l, __n, __hf, _H2(), _Hash(), __eql, 
457 __key_extract(), __a) 
458 { } 
459 
460 _Hashtable(initializer_list<value_type> __l, 
461 size_type __n = 0, 
462 const _H1& __hf = _H1(), 
463 const key_equal& __eql = key_equal(), 
464 const allocator_type& __a = allocator_type()) 
465 : _Hashtable(__l.begin(), __l.end(), __n, __hf, _H2(), _Hash(), __eql, 
466 __key_extract(), __a) 
467 { } 
468 
469 _Hashtable& 
470 operator=(const _Hashtable& __ht); 
471 
472 _Hashtable& 
473 operator=(_Hashtable&& __ht) 
474 noexcept(__node_alloc_traits::_S_nothrow_move() 
475 && is_nothrow_move_assignable<_H1>::value 
476 && is_nothrow_move_assignable<_Equal>::value) 
477 { 
478 constexpr bool __move_storage = 
479 __node_alloc_traits::_S_propagate_on_move_assign() 
480 || __node_alloc_traits::_S_always_equal(); 
481 _M_move_assign(std::move(__ht), __bool_constant<__move_storage>()); 
482 return *this; 
483 } 
484 
485 _Hashtable& 
486 operator=(initializer_list<value_type> __l) 
487 { 
488 __reuse_or_alloc_node_type __roan(_M_begin(), *this); 
489 _M_before_begin._M_nxt = nullptr; 
490 clear(); 
491 this->_M_insert_range(__l.begin(), __l.end(), __roan, __unique_keys()); 
492 return *this; 
493 } 
494 
495 ~_Hashtable() noexcept; 
496 
497 void 
498 swap(_Hashtable&) 
499 noexcept(__and_<__is_nothrow_swappable<_H1>, 
500 __is_nothrow_swappable<_Equal>>::value); 
501 
502 // Basic container operations 
503 iterator 
504 begin() noexcept 
505 { return iterator(_M_begin()); } 
506 
507 const_iterator 
508 begin() const noexcept 
509 { return const_iterator(_M_begin()); } 
510 
511 iterator 
512 end() noexcept 
513 { return iterator(nullptr); } 
514 
515 const_iterator 
516 end() const noexcept 
517 { return const_iterator(nullptr); } 
518 
519 const_iterator 
520 cbegin() const noexcept 
521 { return const_iterator(_M_begin()); } 
522 
523 const_iterator 
524 cend() const noexcept 
525 { return const_iterator(nullptr); } 
526 
527 size_type 
528 size() const noexcept 
529 { return _M_element_count; } 
530 
531 _GLIBCXX_NODISCARD bool 
532 empty() const noexcept 
533 { return size() == 0; } 
534 
535 allocator_type 
536 get_allocator() const noexcept 
537 { return allocator_type(this->_M_node_allocator()); } 
538 
539 size_type 
540 max_size() const noexcept 
541 { return __node_alloc_traits::max_size(this->_M_node_allocator()); } 
542 
543 // Observers 
544 key_equal 
545 key_eq() const 
546 { return this->_M_eq(); } 
547 
548 // hash_function, if present, comes from _Hash_code_base. 
549 
550 // Bucket operations 
551 size_type 
552 bucket_count() const noexcept 
553 { return _M_bucket_count; } 
554 
555 size_type 
556 max_bucket_count() const noexcept 
557 { return max_size(); } 
558 
559 size_type 
560 bucket_size(size_type __n) const 
561 { return std::distance(begin(__n), end(__n)); } 
562 
563 size_type 
564 bucket(const key_type& __k) const 
565 { return _M_bucket_index(__k, this->_M_hash_code(__k)); } 
566 
567 local_iterator 
568 begin(size_type __n) 
569 { 
570 return local_iterator(*this, _M_bucket_begin(__n), 
571 __n, _M_bucket_count); 
572 } 
573 
574 local_iterator 
575 end(size_type __n) 
576 { return local_iterator(*this, nullptr, __n, _M_bucket_count); } 
577 
578 const_local_iterator 
579 begin(size_type __n) const 
580 { 
581 return const_local_iterator(*this, _M_bucket_begin(__n), 
582 __n, _M_bucket_count); 
583 } 
584 
585 const_local_iterator 
586 end(size_type __n) const 
587 { return const_local_iterator(*this, nullptr, __n, _M_bucket_count); } 
588 
589 // DR 691. 
590 const_local_iterator 
591 cbegin(size_type __n) const 
592 { 
593 return const_local_iterator(*this, _M_bucket_begin(__n), 
594 __n, _M_bucket_count); 
595 } 
596 
597 const_local_iterator 
598 cend(size_type __n) const 
599 { return const_local_iterator(*this, nullptr, __n, _M_bucket_count); } 
600 
601 float 
602 load_factor() const noexcept 
603 { 
604 return static_cast<float>(size()) / static_cast<float>(bucket_count()); 
605 } 
606 
607 // max_load_factor, if present, comes from _Rehash_base. 
608 
609 // Generalization of max_load_factor. Extension, not found in 
610 // TR1. Only useful if _RehashPolicy is something other than 
611 // the default. 
612 const _RehashPolicy& 
613 __rehash_policy() const 
614 { return _M_rehash_policy; } 
615 
616 void 
617 __rehash_policy(const _RehashPolicy& __pol) 
618 { _M_rehash_policy = __pol; } 
619 
620 // Lookup. 
621 iterator 
622 find(const key_type& __k); 
623 
624 const_iterator 
625 find(const key_type& __k) const; 
626 
627 size_type 
628 count(const key_type& __k) const; 
629 
630 std::pair<iterator, iterator> 
631 equal_range(const key_type& __k); 
632 
633 std::pair<const_iterator, const_iterator> 
634 equal_range(const key_type& __k) const; 
635 
636 protected: 
637 // Bucket index computation helpers. 
638 size_type 
639 _M_bucket_index(__node_type* __n) const noexcept 
640 { return __hash_code_base::_M_bucket_index(__n, _M_bucket_count); } 
641 
642 size_type 
643 _M_bucket_index(const key_type& __k, __hash_code __c) const 
644 { return __hash_code_base::_M_bucket_index(__k, __c, _M_bucket_count); } 
645 
646 // Find and insert helper functions and types 
647 // Find the node before the one matching the criteria. 
648 __node_base* 
649 _M_find_before_node(size_type, const key_type&, __hash_code) const; 
650 
651 __node_type* 
652 _M_find_node(size_type __bkt, const key_type& __key, 
653 __hash_code __c) const 
654 { 
655 __node_base* __before_n = _M_find_before_node(__bkt, __key, __c); 
656 if (__before_n) 
657 return static_cast<__node_type*>(__before_n->_M_nxt); 
658 return nullptr; 
659 } 
660 
661 // Insert a node at the beginning of a bucket. 
662 void 
663 _M_insert_bucket_begin(size_type, __node_type*); 
664 
665 // Remove the bucket first node 
666 void 
667 _M_remove_bucket_begin(size_type __bkt, __node_type* __next_n, 
668 size_type __next_bkt); 
669 
670 // Get the node before __n in the bucket __bkt 
671 __node_base* 
672 _M_get_previous_node(size_type __bkt, __node_base* __n); 
673 
674 // Insert node with hash code __code, in bucket bkt if no rehash (assumes 
675 // no element with its key already present). Take ownership of the node, 
676 // deallocate it on exception. 
677 iterator 
678 _M_insert_unique_node(size_type __bkt, __hash_code __code, 
679 __node_type* __n, size_type __n_elt = 1); 
680 
681 // Insert node with hash code __code. Take ownership of the node, 
682 // deallocate it on exception. 
683 iterator 
684 _M_insert_multi_node(__node_type* __hint, 
685 __hash_code __code, __node_type* __n); 
686 
687 template<typename... _Args> 
688 std::pair<iterator, bool> 
689 _M_emplace(std::true_type, _Args&&... __args); 
690 
691 template<typename... _Args> 
692 iterator 
693 _M_emplace(std::false_type __uk, _Args&&... __args) 
694 { return _M_emplace(cend(), __uk, std::forward<_Args>(__args)...); } 
695 
696 // Emplace with hint, useless when keys are unique. 
697 template<typename... _Args> 
698 iterator 
699 _M_emplace(const_iterator, std::true_type __uk, _Args&&... __args) 
700 { return _M_emplace(__uk, std::forward<_Args>(__args)...).first; } 
701 
702 template<typename... _Args> 
703 iterator 
704 _M_emplace(const_iterator, std::false_type, _Args&&... __args); 
705 
706 template<typename _Arg, typename _NodeGenerator> 
707 std::pair<iterator, bool> 
708 _M_insert(_Arg&&, const _NodeGenerator&, true_type, size_type = 1); 
709 
710 template<typename _Arg, typename _NodeGenerator> 
711 iterator 
712 _M_insert(_Arg&& __arg, const _NodeGenerator& __node_gen, 
713 false_type __uk) 
714 { 
715 return _M_insert(cend(), std::forward<_Arg>(__arg), __node_gen, 
716 __uk); 
717 } 
718 
719 // Insert with hint, not used when keys are unique. 
720 template<typename _Arg, typename _NodeGenerator> 
721 iterator 
722 _M_insert(const_iterator, _Arg&& __arg, 
723 const _NodeGenerator& __node_gen, true_type __uk) 
724 { 
725 return 
726 _M_insert(std::forward<_Arg>(__arg), __node_gen, __uk).first; 
727 } 
728 
729 // Insert with hint when keys are not unique. 
730 template<typename _Arg, typename _NodeGenerator> 
731 iterator 
732 _M_insert(const_iterator, _Arg&&, 
733 const _NodeGenerator&, false_type); 
734 
735 size_type 
736 _M_erase(std::true_type, const key_type&); 
737 
738 size_type 
739 _M_erase(std::false_type, const key_type&); 
740 
741 iterator 
742 _M_erase(size_type __bkt, __node_base* __prev_n, __node_type* __n); 
743 
744 public: 
745 // Emplace 
746 template<typename... _Args> 
747 __ireturn_type 
748 emplace(_Args&&... __args) 
749 { return _M_emplace(__unique_keys(), std::forward<_Args>(__args)...); } 
750 
751 template<typename... _Args> 
752 iterator 
753 emplace_hint(const_iterator __hint, _Args&&... __args) 
754 { 
755 return _M_emplace(__hint, __unique_keys(), 
756 std::forward<_Args>(__args)...); 
757 } 
758 
759 // Insert member functions via inheritance. 
760 
761 // Erase 
762 iterator 
763 erase(const_iterator); 
764 
765 // LWG 2059. 
766 iterator 
767 erase(iterator __it) 
768 { return erase(const_iterator(__it)); } 
769 
770 size_type 
771 erase(const key_type& __k) 
772 { return _M_erase(__unique_keys(), __k); } 
773 
774 iterator 
775 erase(const_iterator, const_iterator); 
776 
777 void 
778 clear() noexcept; 
779 
780 // Set number of buckets to be appropriate for container of n element. 
781 void rehash(size_type __n); 
782 
783 // DR 1189. 
784 // reserve, if present, comes from _Rehash_base. 
785 
786#if __cplusplus > 201402L 
787 /// Re-insert an extracted node into a container with unique keys. 
788 insert_return_type 
789 _M_reinsert_node(node_type&& __nh) 
790 { 
791 insert_return_type __ret; 
792 if (__nh.empty()) 
793 __ret.position = end(); 
794 else 
795 { 
796 __glibcxx_assert(get_allocator() == __nh.get_allocator()); 
797 
798 const key_type& __k = __nh._M_key(); 
799 __hash_code __code = this->_M_hash_code(__k); 
800 size_type __bkt = _M_bucket_index(__k, __code); 
801 if (__node_type* __n = _M_find_node(__bkt, __k, __code)) 
802 { 
803 __ret.node = std::move(__nh); 
804 __ret.position = iterator(__n); 
805 __ret.inserted = false; 
806 } 
807 else 
808 { 
809 __ret.position 
810 = _M_insert_unique_node(__bkt, __code, __nh._M_ptr); 
811 __nh._M_ptr = nullptr; 
812 __ret.inserted = true; 
813 } 
814 } 
815 return __ret; 
816 } 
817 
818 /// Re-insert an extracted node into a container with equivalent keys. 
819 iterator 
820 _M_reinsert_node_multi(const_iterator __hint, node_type&& __nh) 
821 { 
822 iterator __ret; 
823 if (__nh.empty()) 
824 __ret = end(); 
825 else 
826 { 
827 __glibcxx_assert(get_allocator() == __nh.get_allocator()); 
828 
829 auto __code = this->_M_hash_code(__nh._M_key()); 
830 auto __node = std::exchange(__nh._M_ptr, nullptr); 
831 // FIXME: this deallocates the node on exception. 
832 __ret = _M_insert_multi_node(__hint._M_cur, __code, __node); 
833 } 
834 return __ret; 
835 } 
836 
837 /// Extract a node. 
838 node_type 
839 extract(const_iterator __pos) 
840 { 
841 __node_type* __n = __pos._M_cur; 
842 size_t __bkt = _M_bucket_index(__n); 
843 
844 // Look for previous node to unlink it from the erased one, this 
845 // is why we need buckets to contain the before begin to make 
846 // this search fast. 
847 __node_base* __prev_n = _M_get_previous_node(__bkt, __n); 
848 
849 if (__prev_n == _M_buckets[__bkt]) 
850 _M_remove_bucket_begin(__bkt, __n->_M_next(), 
851 __n->_M_nxt ? _M_bucket_index(__n->_M_next()) : 0); 
852 else if (__n->_M_nxt) 
853 { 
854 size_type __next_bkt = _M_bucket_index(__n->_M_next()); 
855 if (__next_bkt != __bkt) 
856 _M_buckets[__next_bkt] = __prev_n; 
857 } 
858 
859 __prev_n->_M_nxt = __n->_M_nxt; 
860 __n->_M_nxt = nullptr; 
861 --_M_element_count; 
862 return { __n, this->_M_node_allocator() }; 
863 } 
864 
865 /// Extract a node. 
866 node_type 
867 extract(const _Key& __k) 
868 { 
869 node_type __nh; 
870 auto __pos = find(__k); 
871 if (__pos != end()) 
872 __nh = extract(const_iterator(__pos)); 
873 return __nh; 
874 } 
875 
876 /// Merge from a compatible container into one with unique keys. 
877 template<typename _Compatible_Hashtable> 
878 void 
879 _M_merge_unique(_Compatible_Hashtable& __src) noexcept 
880 { 
881 static_assert(is_same_v<typename _Compatible_Hashtable::node_type, 
882 node_type>, "Node types are compatible"); 
883 __glibcxx_assert(get_allocator() == __src.get_allocator()); 
884 
885 auto __n_elt = __src.size(); 
886 for (auto __i = __src.begin(), __end = __src.end(); __i != __end;) 
887 { 
888 auto __pos = __i++; 
889 const key_type& __k = this->_M_extract()(__pos._M_cur->_M_v()); 
890 __hash_code __code = this->_M_hash_code(__k); 
891 size_type __bkt = _M_bucket_index(__k, __code); 
892 if (_M_find_node(__bkt, __k, __code) == nullptr) 
893 { 
894 auto __nh = __src.extract(__pos); 
895 _M_insert_unique_node(__bkt, __code, __nh._M_ptr, __n_elt); 
896 __nh._M_ptr = nullptr; 
897 __n_elt = 1; 
898 } 
899 else if (__n_elt != 1) 
900 --__n_elt; 
901 } 
902 } 
903 
904 /// Merge from a compatible container into one with equivalent keys. 
905 template<typename _Compatible_Hashtable> 
906 void 
907 _M_merge_multi(_Compatible_Hashtable& __src) noexcept 
908 { 
909 static_assert(is_same_v<typename _Compatible_Hashtable::node_type, 
910 node_type>, "Node types are compatible"); 
911 __glibcxx_assert(get_allocator() == __src.get_allocator()); 
912 
913 this->reserve(size() + __src.size()); 
914 for (auto __i = __src.begin(), __end = __src.end(); __i != __end;) 
915 _M_reinsert_node_multi(cend(), __src.extract(__i++)); 
916 } 
917#endif // C++17 
918 
919 private: 
920 // Helper rehash method used when keys are unique. 
921 void _M_rehash_aux(size_type __n, std::true_type); 
922 
923 // Helper rehash method used when keys can be non-unique. 
924 void _M_rehash_aux(size_type __n, std::false_type); 
925 
926 // Unconditionally change size of bucket array to n, restore 
927 // hash policy state to __state on exception. 
928 void _M_rehash(size_type __n, const __rehash_state& __state); 
929 }; 
930 
931 
932 // Definitions of class template _Hashtable's out-of-line member functions. 
933 template<typename _Key, typename _Value, 
934 typename _Alloc, typename _ExtractKey, typename _Equal, 
935 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 
936 typename _Traits> 
937 auto 
938 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, 
939 _H1, _H2, _Hash, _RehashPolicy, _Traits>:: 
940 _M_bucket_begin(size_type __bkt) const 
941 -> __node_type* 
942 { 
943 __node_base* __n = _M_buckets[__bkt]; 
944 return __n ? static_cast<__node_type*>(__n->_M_nxt) : nullptr; 
945 } 
946 
947 template<typename _Key, typename _Value, 
948 typename _Alloc, typename _ExtractKey, typename _Equal, 
949 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 
950 typename _Traits> 
951 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, 
952 _H1, _H2, _Hash, _RehashPolicy, _Traits>:: 
953 _Hashtable(size_type __bucket_hint, 
954 const _H1& __h1, const _H2& __h2, const _Hash& __h, 
955 const _Equal& __eq, const _ExtractKey& __exk, 
956 const allocator_type& __a) 
957 : _Hashtable(__h1, __h2, __h, __eq, __exk, __a) 
958 { 
959 auto __bkt = _M_rehash_policy._M_next_bkt(__bucket_hint); 
960 if (__bkt > _M_bucket_count) 
961 { 
962 _M_buckets = _M_allocate_buckets(__bkt); 
963 _M_bucket_count = __bkt; 
964 } 
965 } 
966 
967 template<typename _Key, typename _Value, 
968 typename _Alloc, typename _ExtractKey, typename _Equal, 
969 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 
970 typename _Traits> 
971 template<typename _InputIterator> 
972 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, 
973 _H1, _H2, _Hash, _RehashPolicy, _Traits>:: 
974 _Hashtable(_InputIterator __f, _InputIterator __l, 
975 size_type __bucket_hint, 
976 const _H1& __h1, const _H2& __h2, const _Hash& __h, 
977 const _Equal& __eq, const _ExtractKey& __exk, 
978 const allocator_type& __a) 
979 : _Hashtable(__h1, __h2, __h, __eq, __exk, __a) 
980 { 
981 auto __nb_elems = __detail::__distance_fw(__f, __l); 
982 auto __bkt_count = 
983 _M_rehash_policy._M_next_bkt( 
984 std::max(_M_rehash_policy._M_bkt_for_elements(__nb_elems), 
985 __bucket_hint)); 
986 
987 if (__bkt_count > _M_bucket_count) 
988 { 
989 _M_buckets = _M_allocate_buckets(__bkt_count); 
990 _M_bucket_count = __bkt_count; 
991 } 
992 
993 for (; __f != __l; ++__f) 
994 this->insert(*__f); 
995 } 
996 
997 template<typename _Key, typename _Value, 
998 typename _Alloc, typename _ExtractKey, typename _Equal, 
999 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 
1000 typename _Traits> 
1001 auto 
1002 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, 
1003 _H1, _H2, _Hash, _RehashPolicy, _Traits>:: 
1004 operator=(const _Hashtable& __ht) 
1005 -> _Hashtable& 
1006 { 
1007 if (&__ht == this) 
1008 return *this; 
1009 
1010 if (__node_alloc_traits::_S_propagate_on_copy_assign()) 
1011 { 
1012 auto& __this_alloc = this->_M_node_allocator(); 
1013 auto& __that_alloc = __ht._M_node_allocator(); 
1014 if (!__node_alloc_traits::_S_always_equal() 
1015 && __this_alloc != __that_alloc) 
1016 { 
1017 // Replacement allocator cannot free existing storage. 
1018 this->_M_deallocate_nodes(_M_begin()); 
1019 _M_before_begin._M_nxt = nullptr; 
1020 _M_deallocate_buckets(); 
1021 _M_buckets = nullptr; 
1022 std::__alloc_on_copy(__this_alloc, __that_alloc); 
1023 __hashtable_base::operator=(__ht); 
1024 _M_bucket_count = __ht._M_bucket_count; 
1025 _M_element_count = __ht._M_element_count; 
1026 _M_rehash_policy = __ht._M_rehash_policy; 
1027 __try 
1028 { 
1029 _M_assign(__ht, 
1030 [this](const __node_type* __n) 
1031 { return this->_M_allocate_node(__n->_M_v()); }); 
1032 } 
1033 __catch(...) 
1034 { 
1035 // _M_assign took care of deallocating all memory. Now we 
1036 // must make sure this instance remains in a usable state. 
1037 _M_reset(); 
1038 __throw_exception_again; 
1039 } 
1040 return *this; 
1041 } 
1042 std::__alloc_on_copy(__this_alloc, __that_alloc); 
1043 } 
1044 
1045 // Reuse allocated buckets and nodes. 
1046 _M_assign_elements(__ht, 
1047 [](const __reuse_or_alloc_node_type& __roan, const __node_type* __n) 
1048 { return __roan(__n->_M_v()); }); 
1049 return *this; 
1050 } 
1051 
1052 template<typename _Key, typename _Value, 
1053 typename _Alloc, typename _ExtractKey, typename _Equal, 
1054 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 
1055 typename _Traits> 
1056 template<typename _Ht, typename _NodeGenerator> 
1057 void 
1058 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, 
1059 _H1, _H2, _Hash, _RehashPolicy, _Traits>:: 
1060 _M_assign_elements(_Ht&& __ht, const _NodeGenerator& __node_gen) 
1061 { 
1062 __bucket_type* __former_buckets = nullptr; 
1063 std::size_t __former_bucket_count = _M_bucket_count; 
1064 const __rehash_state& __former_state = _M_rehash_policy._M_state(); 
1065 
1066 if (_M_bucket_count != __ht._M_bucket_count) 
1067 { 
1068 __former_buckets = _M_buckets; 
1069 _M_buckets = _M_allocate_buckets(__ht._M_bucket_count); 
1070 _M_bucket_count = __ht._M_bucket_count; 
1071 } 
1072 else 
1073 __builtin_memset(_M_buckets, 0, 
1074 _M_bucket_count * sizeof(__bucket_type)); 
1075 
1076 __try 
1077 { 
1078 __hashtable_base::operator=(std::forward<_Ht>(__ht)); 
1079 _M_element_count = __ht._M_element_count; 
1080 _M_rehash_policy = __ht._M_rehash_policy; 
1081 __reuse_or_alloc_node_type __roan(_M_begin(), *this); 
1082 _M_before_begin._M_nxt = nullptr; 
1083 _M_assign(__ht, 
1084 [&__node_gen, &__roan](__node_type* __n) 
1085 { return __node_gen(__roan, __n); }); 
1086 if (__former_buckets) 
1087 _M_deallocate_buckets(__former_buckets, __former_bucket_count); 
1088 } 
1089 __catch(...) 
1090 { 
1091 if (__former_buckets) 
1092 { 
1093 // Restore previous buckets. 
1094 _M_deallocate_buckets(); 
1095 _M_rehash_policy._M_reset(__former_state); 
1096 _M_buckets = __former_buckets; 
1097 _M_bucket_count = __former_bucket_count; 
1098 } 
1099 __builtin_memset(_M_buckets, 0, 
1100 _M_bucket_count * sizeof(__bucket_type)); 
1101 __throw_exception_again; 
1102 } 
1103 } 
1104 
1105 template<typename _Key, typename _Value, 
1106 typename _Alloc, typename _ExtractKey, typename _Equal, 
1107 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 
1108 typename _Traits> 
1109 template<typename _NodeGenerator> 
1110 void 
1111 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, 
1112 _H1, _H2, _Hash, _RehashPolicy, _Traits>:: 
1113 _M_assign(const _Hashtable& __ht, const _NodeGenerator& __node_gen) 
1114 { 
1115 __bucket_type* __buckets = nullptr; 
1116 if (!_M_buckets) 
1117 _M_buckets = __buckets = _M_allocate_buckets(_M_bucket_count); 
1118 
1119 __try 
1120 { 
1121 if (!__ht._M_before_begin._M_nxt) 
1122 return; 
1123 
1124 // First deal with the special first node pointed to by 
1125 // _M_before_begin. 
1126 __node_type* __ht_n = __ht._M_begin(); 
1127 __node_type* __this_n = __node_gen(__ht_n); 
1128 this->_M_copy_code(__this_n, __ht_n); 
1129 _M_before_begin._M_nxt = __this_n; 
1130 _M_buckets[_M_bucket_index(__this_n)] = &_M_before_begin; 
1131 
1132 // Then deal with other nodes. 
1133 __node_base* __prev_n = __this_n; 
1134 for (__ht_n = __ht_n->_M_next(); __ht_n; __ht_n = __ht_n->_M_next()) 
1135 { 
1136 __this_n = __node_gen(__ht_n); 
1137 __prev_n->_M_nxt = __this_n; 
1138 this->_M_copy_code(__this_n, __ht_n); 
1139 size_type __bkt = _M_bucket_index(__this_n); 
1140 if (!_M_buckets[__bkt]) 
1141 _M_buckets[__bkt] = __prev_n; 
1142 __prev_n = __this_n; 
1143 } 
1144 } 
1145 __catch(...) 
1146 { 
1147 clear(); 
1148 if (__buckets) 
1149 _M_deallocate_buckets(); 
1150 __throw_exception_again; 
1151 } 
1152 } 
1153 
1154 template<typename _Key, typename _Value, 
1155 typename _Alloc, typename _ExtractKey, typename _Equal, 
1156 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 
1157 typename _Traits> 
1158 void 
1159 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, 
1160 _H1, _H2, _Hash, _RehashPolicy, _Traits>:: 
1161 _M_reset() noexcept 
1162 { 
1163 _M_rehash_policy._M_reset(); 
1164 _M_bucket_count = 1; 
1165 _M_single_bucket = nullptr; 
1166 _M_buckets = &_M_single_bucket; 
1167 _M_before_begin._M_nxt = nullptr; 
1168 _M_element_count = 0; 
1169 } 
1170 
1171 template<typename _Key, typename _Value, 
1172 typename _Alloc, typename _ExtractKey, typename _Equal, 
1173 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 
1174 typename _Traits> 
1175 void 
1176 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, 
1177 _H1, _H2, _Hash, _RehashPolicy, _Traits>:: 
1178 _M_move_assign(_Hashtable&& __ht, std::true_type) 
1179 { 
1180 this->_M_deallocate_nodes(_M_begin()); 
1181 _M_deallocate_buckets(); 
1182 __hashtable_base::operator=(std::move(__ht)); 
1183 _M_rehash_policy = __ht._M_rehash_policy; 
1184 if (!__ht._M_uses_single_bucket()) 
1185 _M_buckets = __ht._M_buckets; 
1186 else 
1187 { 
1188 _M_buckets = &_M_single_bucket; 
1189 _M_single_bucket = __ht._M_single_bucket; 
1190 } 
1191 _M_bucket_count = __ht._M_bucket_count; 
1192 _M_before_begin._M_nxt = __ht._M_before_begin._M_nxt; 
1193 _M_element_count = __ht._M_element_count; 
1194 std::__alloc_on_move(this->_M_node_allocator(), __ht._M_node_allocator()); 
1195 
1196 // Fix buckets containing the _M_before_begin pointers that can't be 
1197 // moved. 
1198 if (_M_begin()) 
1199 _M_buckets[_M_bucket_index(_M_begin())] = &_M_before_begin; 
1200 __ht._M_reset(); 
1201 } 
1202 
1203 template<typename _Key, typename _Value, 
1204 typename _Alloc, typename _ExtractKey, typename _Equal, 
1205 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 
1206 typename _Traits> 
1207 void 
1208 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, 
1209 _H1, _H2, _Hash, _RehashPolicy, _Traits>:: 
1210 _M_move_assign(_Hashtable&& __ht, std::false_type) 
1211 { 
1212 if (__ht._M_node_allocator() == this->_M_node_allocator()) 
1213 _M_move_assign(std::move(__ht), std::true_type()); 
1214 else 
1215 { 
1216 // Can't move memory, move elements then. 
1217 _M_assign_elements(std::move(__ht), 
1218 [](const __reuse_or_alloc_node_type& __roan, __node_type* __n) 
1219 { return __roan(std::move_if_noexcept(__n->_M_v())); }); 
1220 __ht.clear(); 
1221 } 
1222 } 
1223 
1224 template<typename _Key, typename _Value, 
1225 typename _Alloc, typename _ExtractKey, typename _Equal, 
1226 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 
1227 typename _Traits> 
1228 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, 
1229 _H1, _H2, _Hash, _RehashPolicy, _Traits>:: 
1230 _Hashtable(const _Hashtable& __ht) 
1231 : __hashtable_base(__ht), 
1232 __map_base(__ht), 
1233 __rehash_base(__ht), 
1234 __hashtable_alloc( 
1235 __node_alloc_traits::_S_select_on_copy(__ht._M_node_allocator())), 
1236 _M_buckets(nullptr), 
1237 _M_bucket_count(__ht._M_bucket_count), 
1238 _M_element_count(__ht._M_element_count), 
1239 _M_rehash_policy(__ht._M_rehash_policy) 
1240 { 
1241 _M_assign(__ht, 
1242 [this](const __node_type* __n) 
1243 { return this->_M_allocate_node(__n->_M_v()); }); 
1244 } 
1245 
1246 template<typename _Key, typename _Value, 
1247 typename _Alloc, typename _ExtractKey, typename _Equal, 
1248 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 
1249 typename _Traits> 
1250 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, 
1251 _H1, _H2, _Hash, _RehashPolicy, _Traits>:: 
1252 _Hashtable(_Hashtable&& __ht) noexcept 
1253 : __hashtable_base(__ht), 
1254 __map_base(__ht), 
1255 __rehash_base(__ht), 
1256 __hashtable_alloc(std::move(__ht._M_base_alloc())), 
1257 _M_buckets(__ht._M_buckets), 
1258 _M_bucket_count(__ht._M_bucket_count), 
1259 _M_before_begin(__ht._M_before_begin._M_nxt), 
1260 _M_element_count(__ht._M_element_count), 
1261 _M_rehash_policy(__ht._M_rehash_policy) 
1262 { 
1263 // Update, if necessary, buckets if __ht is using its single bucket. 
1264 if (__ht._M_uses_single_bucket()) 
1265 { 
1266 _M_buckets = &_M_single_bucket; 
1267 _M_single_bucket = __ht._M_single_bucket; 
1268 } 
1269 
1270 // Update, if necessary, bucket pointing to before begin that hasn't 
1271 // moved. 
1272 if (_M_begin()) 
1273 _M_buckets[_M_bucket_index(_M_begin())] = &_M_before_begin; 
1274 
1275 __ht._M_reset(); 
1276 } 
1277 
1278 template<typename _Key, typename _Value, 
1279 typename _Alloc, typename _ExtractKey, typename _Equal, 
1280 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 
1281 typename _Traits> 
1282 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, 
1283 _H1, _H2, _Hash, _RehashPolicy, _Traits>:: 
1284 _Hashtable(const _Hashtable& __ht, const allocator_type& __a) 
1285 : __hashtable_base(__ht), 
1286 __map_base(__ht), 
1287 __rehash_base(__ht), 
1288 __hashtable_alloc(__node_alloc_type(__a)), 
1289 _M_buckets(), 
1290 _M_bucket_count(__ht._M_bucket_count), 
1291 _M_element_count(__ht._M_element_count), 
1292 _M_rehash_policy(__ht._M_rehash_policy) 
1293 { 
1294 _M_assign(__ht, 
1295 [this](const __node_type* __n) 
1296 { return this->_M_allocate_node(__n->_M_v()); }); 
1297 } 
1298 
1299 template<typename _Key, typename _Value, 
1300 typename _Alloc, typename _ExtractKey, typename _Equal, 
1301 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 
1302 typename _Traits> 
1303 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, 
1304 _H1, _H2, _Hash, _RehashPolicy, _Traits>:: 
1305 _Hashtable(_Hashtable&& __ht, const allocator_type& __a) 
1306 : __hashtable_base(__ht), 
1307 __map_base(__ht), 
1308 __rehash_base(__ht), 
1309 __hashtable_alloc(__node_alloc_type(__a)), 
1310 _M_buckets(nullptr), 
1311 _M_bucket_count(__ht._M_bucket_count), 
1312 _M_element_count(__ht._M_element_count), 
1313 _M_rehash_policy(__ht._M_rehash_policy) 
1314 { 
1315 if (__ht._M_node_allocator() == this->_M_node_allocator()) 
1316 { 
1317 if (__ht._M_uses_single_bucket()) 
1318 { 
1319 _M_buckets = &_M_single_bucket; 
1320 _M_single_bucket = __ht._M_single_bucket; 
1321 } 
1322 else 
1323 _M_buckets = __ht._M_buckets; 
1324 
1325 _M_before_begin._M_nxt = __ht._M_before_begin._M_nxt; 
1326 // Update, if necessary, bucket pointing to before begin that hasn't 
1327 // moved. 
1328 if (_M_begin()) 
1329 _M_buckets[_M_bucket_index(_M_begin())] = &_M_before_begin; 
1330 __ht._M_reset(); 
1331 } 
1332 else 
1333 { 
1334 _M_assign(__ht, 
1335 [this](__node_type* __n) 
1336 { 
1337 return this->_M_allocate_node( 
1338 std::move_if_noexcept(__n->_M_v())); 
1339 }); 
1340 __ht.clear(); 
1341 } 
1342 } 
1343 
1344 template<typename _Key, typename _Value, 
1345 typename _Alloc, typename _ExtractKey, typename _Equal, 
1346 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 
1347 typename _Traits> 
1348 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, 
1349 _H1, _H2, _Hash, _RehashPolicy, _Traits>:: 
1350 ~_Hashtable() noexcept 
1351 { 
1352 clear(); 
1353 _M_deallocate_buckets(); 
1354 } 
1355 
1356 template<typename _Key, typename _Value, 
1357 typename _Alloc, typename _ExtractKey, typename _Equal, 
1358 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 
1359 typename _Traits> 
1360 void 
1361 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, 
1362 _H1, _H2, _Hash, _RehashPolicy, _Traits>:: 
1363 swap(_Hashtable& __x) 
1364 noexcept(__and_<__is_nothrow_swappable<_H1>, 
1365 __is_nothrow_swappable<_Equal>>::value) 
1366 { 
1367 // The only base class with member variables is hash_code_base. 
1368 // We define _Hash_code_base::_M_swap because different 
1369 // specializations have different members. 
1370 this->_M_swap(__x); 
1371 
1372 std::__alloc_on_swap(this->_M_node_allocator(), __x._M_node_allocator()); 
1373 std::swap(_M_rehash_policy, __x._M_rehash_policy); 
1374 
1375 // Deal properly with potentially moved instances. 
1376 if (this->_M_uses_single_bucket()) 
1377 { 
1378 if (!__x._M_uses_single_bucket()) 
1379 { 
1380 _M_buckets = __x._M_buckets; 
1381 __x._M_buckets = &__x._M_single_bucket; 
1382 } 
1383 } 
1384 else if (__x._M_uses_single_bucket()) 
1385 { 
1386 __x._M_buckets = _M_buckets; 
1387 _M_buckets = &_M_single_bucket; 
1388 }  
1389 else 
1390 std::swap(_M_buckets, __x._M_buckets); 
1391 
1392 std::swap(_M_bucket_count, __x._M_bucket_count); 
1393 std::swap(_M_before_begin._M_nxt, __x._M_before_begin._M_nxt); 
1394 std::swap(_M_element_count, __x._M_element_count); 
1395 std::swap(_M_single_bucket, __x._M_single_bucket); 
1396 
1397 // Fix buckets containing the _M_before_begin pointers that can't be 
1398 // swapped. 
1399 if (_M_begin()) 
1400 _M_buckets[_M_bucket_index(_M_begin())] = &_M_before_begin; 
1401 
1402 if (__x._M_begin()) 
1403 __x._M_buckets[__x._M_bucket_index(__x._M_begin())] 
1404 = &__x._M_before_begin; 
1405 } 
1406 
1407 template<typename _Key, typename _Value, 
1408 typename _Alloc, typename _ExtractKey, typename _Equal, 
1409 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 
1410 typename _Traits> 
1411 auto 
1412 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, 
1413 _H1, _H2, _Hash, _RehashPolicy, _Traits>:: 
1414 find(const key_type& __k) 
1415 -> iterator 
1416 { 
1417 __hash_code __code = this->_M_hash_code(__k); 
1418 std::size_t __n = _M_bucket_index(__k, __code); 
1419 __node_type* __p = _M_find_node(__n, __k, __code); 
1420 return __p ? iterator(__p) : end(); 
1421 } 
1422 
1423 template<typename _Key, typename _Value, 
1424 typename _Alloc, typename _ExtractKey, typename _Equal, 
1425 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 
1426 typename _Traits> 
1427 auto 
1428 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, 
1429 _H1, _H2, _Hash, _RehashPolicy, _Traits>:: 
1430 find(const key_type& __k) const 
1431 -> const_iterator 
1432 { 
1433 __hash_code __code = this->_M_hash_code(__k); 
1434 std::size_t __n = _M_bucket_index(__k, __code); 
1435 __node_type* __p = _M_find_node(__n, __k, __code); 
1436 return __p ? const_iterator(__p) : end(); 
1437 } 
1438 
1439 template<typename _Key, typename _Value, 
1440 typename _Alloc, typename _ExtractKey, typename _Equal, 
1441 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 
1442 typename _Traits> 
1443 auto 
1444 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, 
1445 _H1, _H2, _Hash, _RehashPolicy, _Traits>:: 
1446 count(const key_type& __k) const 
1447 -> size_type 
1448 { 
1449 __hash_code __code = this->_M_hash_code(__k); 
1450 std::size_t __n = _M_bucket_index(__k, __code); 
1451 __node_type* __p = _M_bucket_begin(__n); 
1452 if (!__p) 
1453 return 0; 
1454 
1455 std::size_t __result = 0; 
1456 for (;; __p = __p->_M_next()) 
1457 { 
1458 if (this->_M_equals(__k, __code, __p)) 
1459 ++__result; 
1460 else if (__result) 
1461 // All equivalent values are next to each other, if we 
1462 // found a non-equivalent value after an equivalent one it 
1463 // means that we won't find any new equivalent value. 
1464 break; 
1465 if (!__p->_M_nxt || _M_bucket_index(__p->_M_next()) != __n) 
1466 break; 
1467 } 
1468 return __result; 
1469 } 
1470 
1471 template<typename _Key, typename _Value, 
1472 typename _Alloc, typename _ExtractKey, typename _Equal, 
1473 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 
1474 typename _Traits> 
1475 auto 
1476 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, 
1477 _H1, _H2, _Hash, _RehashPolicy, _Traits>:: 
1478 equal_range(const key_type& __k) 
1479 -> pair<iterator, iterator> 
1480 { 
1481 __hash_code __code = this->_M_hash_code(__k); 
1482 std::size_t __n = _M_bucket_index(__k, __code); 
1483 __node_type* __p = _M_find_node(__n, __k, __code); 
1484 
1485 if (__p) 
1486 { 
1487 __node_type* __p1 = __p->_M_next(); 
1488 while (__p1 && _M_bucket_index(__p1) == __n 
1489 && this->_M_equals(__k, __code, __p1)) 
1490 __p1 = __p1->_M_next(); 
1491 
1492 return std::make_pair(iterator(__p), iterator(__p1)); 
1493 } 
1494 else 
1495 return std::make_pair(end(), end()); 
1496 } 
1497 
1498 template<typename _Key, typename _Value, 
1499 typename _Alloc, typename _ExtractKey, typename _Equal, 
1500 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 
1501 typename _Traits> 
1502 auto 
1503 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, 
1504 _H1, _H2, _Hash, _RehashPolicy, _Traits>:: 
1505 equal_range(const key_type& __k) const 
1506 -> pair<const_iterator, const_iterator> 
1507 { 
1508 __hash_code __code = this->_M_hash_code(__k); 
1509 std::size_t __n = _M_bucket_index(__k, __code); 
1510 __node_type* __p = _M_find_node(__n, __k, __code); 
1511 
1512 if (__p) 
1513 { 
1514 __node_type* __p1 = __p->_M_next(); 
1515 while (__p1 && _M_bucket_index(__p1) == __n 
1516 && this->_M_equals(__k, __code, __p1)) 
1517 __p1 = __p1->_M_next(); 
1518 
1519 return std::make_pair(const_iterator(__p), const_iterator(__p1)); 
1520 } 
1521 else 
1522 return std::make_pair(end(), end()); 
1523 } 
1524 
1525 // Find the node whose key compares equal to k in the bucket n. 
1526 // Return nullptr if no node is found. 
1527 template<typename _Key, typename _Value, 
1528 typename _Alloc, typename _ExtractKey, typename _Equal, 
1529 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 
1530 typename _Traits> 
1531 auto 
1532 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, 
1533 _H1, _H2, _Hash, _RehashPolicy, _Traits>:: 
1534 _M_find_before_node(size_type __n, const key_type& __k, 
1535 __hash_code __code) const 
1536 -> __node_base* 
1537 { 
1538 __node_base* __prev_p = _M_buckets[__n]; 
1539 if (!__prev_p) 
1540 return nullptr; 
1541 
1542 for (__node_type* __p = static_cast<__node_type*>(__prev_p->_M_nxt);; 
1543 __p = __p->_M_next()) 
1544 { 
1545 if (this->_M_equals(__k, __code, __p)) 
1546 return __prev_p; 
1547 
1548 if (!__p->_M_nxt || _M_bucket_index(__p->_M_next()) != __n) 
1549 break; 
1550 __prev_p = __p; 
1551 } 
1552 return nullptr; 
1553 } 
1554 
1555 template<typename _Key, typename _Value, 
1556 typename _Alloc, typename _ExtractKey, typename _Equal, 
1557 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 
1558 typename _Traits> 
1559 void 
1560 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, 
1561 _H1, _H2, _Hash, _RehashPolicy, _Traits>:: 
1562 _M_insert_bucket_begin(size_type __bkt, __node_type* __node) 
1563 { 
1564 if (_M_buckets[__bkt]) 
1565 { 
1566 // Bucket is not empty, we just need to insert the new node 
1567 // after the bucket before begin. 
1568 __node->_M_nxt = _M_buckets[__bkt]->_M_nxt; 
1569 _M_buckets[__bkt]->_M_nxt = __node; 
1570 } 
1571 else 
1572 { 
1573 // The bucket is empty, the new node is inserted at the 
1574 // beginning of the singly-linked list and the bucket will 
1575 // contain _M_before_begin pointer. 
1576 __node->_M_nxt = _M_before_begin._M_nxt; 
1577 _M_before_begin._M_nxt = __node; 
1578 if (__node->_M_nxt) 
1579 // We must update former begin bucket that is pointing to 
1580 // _M_before_begin. 
1581 _M_buckets[_M_bucket_index(__node->_M_next())] = __node; 
1582 _M_buckets[__bkt] = &_M_before_begin; 
1583 } 
1584 } 
1585 
1586 template<typename _Key, typename _Value, 
1587 typename _Alloc, typename _ExtractKey, typename _Equal, 
1588 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 
1589 typename _Traits> 
1590 void 
1591 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, 
1592 _H1, _H2, _Hash, _RehashPolicy, _Traits>:: 
1593 _M_remove_bucket_begin(size_type __bkt, __node_type* __next, 
1594 size_type __next_bkt) 
1595 { 
1596 if (!__next || __next_bkt != __bkt) 
1597 { 
1598 // Bucket is now empty 
1599 // First update next bucket if any 
1600 if (__next) 
1601 _M_buckets[__next_bkt] = _M_buckets[__bkt]; 
1602 
1603 // Second update before begin node if necessary 
1604 if (&_M_before_begin == _M_buckets[__bkt]) 
1605 _M_before_begin._M_nxt = __next; 
1606 _M_buckets[__bkt] = nullptr; 
1607 } 
1608 } 
1609 
1610 template<typename _Key, typename _Value, 
1611 typename _Alloc, typename _ExtractKey, typename _Equal, 
1612 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 
1613 typename _Traits> 
1614 auto 
1615 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, 
1616 _H1, _H2, _Hash, _RehashPolicy, _Traits>:: 
1617 _M_get_previous_node(size_type __bkt, __node_base* __n) 
1618 -> __node_base* 
1619 { 
1620 __node_base* __prev_n = _M_buckets[__bkt]; 
1621 while (__prev_n->_M_nxt != __n) 
1622 __prev_n = __prev_n->_M_nxt; 
1623 return __prev_n; 
1624 } 
1625 
1626 template<typename _Key, typename _Value, 
1627 typename _Alloc, typename _ExtractKey, typename _Equal, 
1628 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 
1629 typename _Traits> 
1630 template<typename... _Args> 
1631 auto 
1632 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, 
1633 _H1, _H2, _Hash, _RehashPolicy, _Traits>:: 
1634 _M_emplace(std::true_type, _Args&&... __args) 
1635 -> pair<iterator, bool> 
1636 { 
1637 // First build the node to get access to the hash code 
1638 __node_type* __node = this->_M_allocate_node(std::forward<_Args>(__args)...); 
1639 const key_type& __k = this->_M_extract()(__node->_M_v()); 
1640 __hash_code __code; 
1641 __try 
1642 { 
1643 __code = this->_M_hash_code(__k); 
1644 } 
1645 __catch(...) 
1646 { 
1647 this->_M_deallocate_node(__node); 
1648 __throw_exception_again; 
1649 } 
1650 
1651 size_type __bkt = _M_bucket_index(__k, __code); 
1652 if (__node_type* __p = _M_find_node(__bkt, __k, __code)) 
1653 { 
1654 // There is already an equivalent node, no insertion 
1655 this->_M_deallocate_node(__node); 
1656 return std::make_pair(iterator(__p), false); 
1657 } 
1658 
1659 // Insert the node 
1660 return std::make_pair(_M_insert_unique_node(__bkt, __code, __node), 
1661 true); 
1662 } 
1663 
1664 template<typename _Key, typename _Value, 
1665 typename _Alloc, typename _ExtractKey, typename _Equal, 
1666 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 
1667 typename _Traits> 
1668 template<typename... _Args> 
1669 auto 
1670 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, 
1671 _H1, _H2, _Hash, _RehashPolicy, _Traits>:: 
1672 _M_emplace(const_iterator __hint, std::false_type, _Args&&... __args) 
1673 -> iterator 
1674 { 
1675 // First build the node to get its hash code. 
1676 __node_type* __node = 
1677 this->_M_allocate_node(std::forward<_Args>(__args)...); 
1678 
1679 __hash_code __code; 
1680 __try 
1681 { 
1682 __code = this->_M_hash_code(this->_M_extract()(__node->_M_v())); 
1683 } 
1684 __catch(...) 
1685 { 
1686 this->_M_deallocate_node(__node); 
1687 __throw_exception_again; 
1688 } 
1689 
1690 return _M_insert_multi_node(__hint._M_cur, __code, __node); 
1691 } 
1692 
1693 template<typename _Key, typename _Value, 
1694 typename _Alloc, typename _ExtractKey, typename _Equal, 
1695 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 
1696 typename _Traits> 
1697 auto 
1698 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, 
1699 _H1, _H2, _Hash, _RehashPolicy, _Traits>:: 
1700 _M_insert_unique_node(size_type __bkt, __hash_code __code, 
1701 __node_type* __node, size_type __n_elt) 
1702 -> iterator 
1703 { 
1704 const __rehash_state& __saved_state = _M_rehash_policy._M_state(); 
1705 std::pair<bool, std::size_t> __do_rehash 
1706 = _M_rehash_policy._M_need_rehash(_M_bucket_count, _M_element_count, 
1707 __n_elt); 
1708 
1709 __try 
1710 { 
1711 if (__do_rehash.first) 
1712 { 
1713 _M_rehash(__do_rehash.second, __saved_state); 
1714 __bkt = _M_bucket_index(this->_M_extract()(__node->_M_v()), __code); 
1715 } 
1716 
1717 this->_M_store_code(__node, __code); 
1718 
1719 // Always insert at the beginning of the bucket. 
1720 _M_insert_bucket_begin(__bkt, __node); 
1721 ++_M_element_count; 
1722 return iterator(__node); 
1723 } 
1724 __catch(...) 
1725 { 
1726 this->_M_deallocate_node(__node); 
1727 __throw_exception_again; 
1728 } 
1729 } 
1730 
1731 // Insert node, in bucket bkt if no rehash (assumes no element with its key 
1732 // already present). Take ownership of the node, deallocate it on exception. 
1733 template<typename _Key, typename _Value, 
1734 typename _Alloc, typename _ExtractKey, typename _Equal, 
1735 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 
1736 typename _Traits> 
1737 auto 
1738 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, 
1739 _H1, _H2, _Hash, _RehashPolicy, _Traits>:: 
1740 _M_insert_multi_node(__node_type* __hint, __hash_code __code, 
1741 __node_type* __node) 
1742 -> iterator 
1743 { 
1744 const __rehash_state& __saved_state = _M_rehash_policy._M_state(); 
1745 std::pair<bool, std::size_t> __do_rehash 
1746 = _M_rehash_policy._M_need_rehash(_M_bucket_count, _M_element_count, 1); 
1747 
1748 __try 
1749 { 
1750 if (__do_rehash.first) 
1751 _M_rehash(__do_rehash.second, __saved_state); 
1752 
1753 this->_M_store_code(__node, __code); 
1754 const key_type& __k = this->_M_extract()(__node->_M_v()); 
1755 size_type __bkt = _M_bucket_index(__k, __code); 
1756 
1757 // Find the node before an equivalent one or use hint if it exists and 
1758 // if it is equivalent. 
1759 __node_base* __prev 
1760 = __builtin_expect(__hint != nullptr, false) 
1761 && this->_M_equals(__k, __code, __hint) 
1762 ? __hint 
1763 : _M_find_before_node(__bkt, __k, __code); 
1764 if (__prev) 
1765 { 
1766 // Insert after the node before the equivalent one. 
1767 __node->_M_nxt = __prev->_M_nxt; 
1768 __prev->_M_nxt = __node; 
1769 if (__builtin_expect(__prev == __hint, false)) 
1770 // hint might be the last bucket node, in this case we need to 
1771 // update next bucket. 
1772 if (__node->_M_nxt 
1773 && !this->_M_equals(__k, __code, __node->_M_next())) 
1774 { 
1775 size_type __next_bkt = _M_bucket_index(__node->_M_next()); 
1776 if (__next_bkt != __bkt) 
1777 _M_buckets[__next_bkt] = __node; 
1778 } 
1779 } 
1780 else 
1781 // The inserted node has no equivalent in the 
1782 // hashtable. We must insert the new node at the 
1783 // beginning of the bucket to preserve equivalent 
1784 // elements' relative positions. 
1785 _M_insert_bucket_begin(__bkt, __node); 
1786 ++_M_element_count; 
1787 return iterator(__node); 
1788 } 
1789 __catch(...) 
1790 { 
1791 this->_M_deallocate_node(__node); 
1792 __throw_exception_again; 
1793 } 
1794 } 
1795 
1796 // Insert v if no element with its key is already present. 
1797 template<typename _Key, typename _Value, 
1798 typename _Alloc, typename _ExtractKey, typename _Equal, 
1799 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 
1800 typename _Traits> 
1801 template<typename _Arg, typename _NodeGenerator> 
1802 auto 
1803 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, 
1804 _H1, _H2, _Hash, _RehashPolicy, _Traits>:: 
1805 _M_insert(_Arg&& __v, const _NodeGenerator& __node_gen, true_type, 
1806 size_type __n_elt) 
1807 -> pair<iterator, bool> 
1808 { 
1809 const key_type& __k = this->_M_extract()(__v); 
1810 __hash_code __code = this->_M_hash_code(__k); 
1811 size_type __bkt = _M_bucket_index(__k, __code); 
1812 
1813 __node_type* __n = _M_find_node(__bkt, __k, __code); 
1814 if (__n) 
1815 return std::make_pair(iterator(__n), false); 
1816 
1817 __n = __node_gen(std::forward<_Arg>(__v)); 
1818 return { _M_insert_unique_node(__bkt, __code, __n, __n_elt), true }; 
1819 } 
1820 
1821 // Insert v unconditionally. 
1822 template<typename _Key, typename _Value, 
1823 typename _Alloc, typename _ExtractKey, typename _Equal, 
1824 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 
1825 typename _Traits> 
1826 template<typename _Arg, typename _NodeGenerator> 
1827 auto 
1828 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, 
1829 _H1, _H2, _Hash, _RehashPolicy, _Traits>:: 
1830 _M_insert(const_iterator __hint, _Arg&& __v, 
1831 const _NodeGenerator& __node_gen, false_type) 
1832 -> iterator 
1833 { 
1834 // First compute the hash code so that we don't do anything if it 
1835 // throws. 
1836 __hash_code __code = this->_M_hash_code(this->_M_extract()(__v)); 
1837 
1838 // Second allocate new node so that we don't rehash if it throws. 
1839 __node_type* __node = __node_gen(std::forward<_Arg>(__v)); 
1840 
1841 return _M_insert_multi_node(__hint._M_cur, __code, __node); 
1842 } 
1843 
1844 template<typename _Key, typename _Value, 
1845 typename _Alloc, typename _ExtractKey, typename _Equal, 
1846 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 
1847 typename _Traits> 
1848 auto 
1849 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, 
1850 _H1, _H2, _Hash, _RehashPolicy, _Traits>:: 
1851 erase(const_iterator __it) 
1852 -> iterator 
1853 { 
1854 __node_type* __n = __it._M_cur; 
1855 std::size_t __bkt = _M_bucket_index(__n); 
1856 
1857 // Look for previous node to unlink it from the erased one, this 
1858 // is why we need buckets to contain the before begin to make 
1859 // this search fast. 
1860 __node_base* __prev_n = _M_get_previous_node(__bkt, __n); 
1861 return _M_erase(__bkt, __prev_n, __n); 
1862 } 
1863 
1864 template<typename _Key, typename _Value, 
1865 typename _Alloc, typename _ExtractKey, typename _Equal, 
1866 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 
1867 typename _Traits> 
1868 auto 
1869 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, 
1870 _H1, _H2, _Hash, _RehashPolicy, _Traits>:: 
1871 _M_erase(size_type __bkt, __node_base* __prev_n, __node_type* __n) 
1872 -> iterator 
1873 { 
1874 if (__prev_n == _M_buckets[__bkt]) 
1875 _M_remove_bucket_begin(__bkt, __n->_M_next(), 
1876 __n->_M_nxt ? _M_bucket_index(__n->_M_next()) : 0); 
1877 else if (__n->_M_nxt) 
1878 { 
1879 size_type __next_bkt = _M_bucket_index(__n->_M_next()); 
1880 if (__next_bkt != __bkt) 
1881 _M_buckets[__next_bkt] = __prev_n; 
1882 } 
1883 
1884 __prev_n->_M_nxt = __n->_M_nxt; 
1885 iterator __result(__n->_M_next()); 
1886 this->_M_deallocate_node(__n); 
1887 --_M_element_count; 
1888 
1889 return __result; 
1890 } 
1891 
1892 template<typename _Key, typename _Value, 
1893 typename _Alloc, typename _ExtractKey, typename _Equal, 
1894 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 
1895 typename _Traits> 
1896 auto 
1897 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, 
1898 _H1, _H2, _Hash, _RehashPolicy, _Traits>:: 
1899 _M_erase(std::true_type, const key_type& __k) 
1900 -> size_type 
1901 { 
1902 __hash_code __code = this->_M_hash_code(__k); 
1903 std::size_t __bkt = _M_bucket_index(__k, __code); 
1904 
1905 // Look for the node before the first matching node. 
1906 __node_base* __prev_n = _M_find_before_node(__bkt, __k, __code); 
1907 if (!__prev_n) 
1908 return 0; 
1909 
1910 // We found a matching node, erase it. 
1911 __node_type* __n = static_cast<__node_type*>(__prev_n->_M_nxt); 
1912 _M_erase(__bkt, __prev_n, __n); 
1913 return 1; 
1914 } 
1915 
1916 template<typename _Key, typename _Value, 
1917 typename _Alloc, typename _ExtractKey, typename _Equal, 
1918 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 
1919 typename _Traits> 
1920 auto 
1921 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, 
1922 _H1, _H2, _Hash, _RehashPolicy, _Traits>:: 
1923 _M_erase(std::false_type, const key_type& __k) 
1924 -> size_type 
1925 { 
1926 __hash_code __code = this->_M_hash_code(__k); 
1927 std::size_t __bkt = _M_bucket_index(__k, __code); 
1928 
1929 // Look for the node before the first matching node. 
1930 __node_base* __prev_n = _M_find_before_node(__bkt, __k, __code); 
1931 if (!__prev_n) 
1932 return 0; 
1933 
1934 // _GLIBCXX_RESOLVE_LIB_DEFECTS 
1935 // 526. Is it undefined if a function in the standard changes 
1936 // in parameters? 
1937 // We use one loop to find all matching nodes and another to deallocate 
1938 // them so that the key stays valid during the first loop. It might be 
1939 // invalidated indirectly when destroying nodes. 
1940 __node_type* __n = static_cast<__node_type*>(__prev_n->_M_nxt); 
1941 __node_type* __n_last = __n; 
1942 std::size_t __n_last_bkt = __bkt; 
1943 do 
1944 { 
1945 __n_last = __n_last->_M_next(); 
1946 if (!__n_last) 
1947 break; 
1948 __n_last_bkt = _M_bucket_index(__n_last); 
1949 } 
1950 while (__n_last_bkt == __bkt && this->_M_equals(__k, __code, __n_last)); 
1951 
1952 // Deallocate nodes. 
1953 size_type __result = 0; 
1954 do 
1955 { 
1956 __node_type* __p = __n->_M_next(); 
1957 this->_M_deallocate_node(__n); 
1958 __n = __p; 
1959 ++__result; 
1960 --_M_element_count; 
1961 } 
1962 while (__n != __n_last); 
1963 
1964 if (__prev_n == _M_buckets[__bkt]) 
1965 _M_remove_bucket_begin(__bkt, __n_last, __n_last_bkt); 
1966 else if (__n_last && __n_last_bkt != __bkt) 
1967 _M_buckets[__n_last_bkt] = __prev_n; 
1968 __prev_n->_M_nxt = __n_last; 
1969 return __result; 
1970 } 
1971 
1972 template<typename _Key, typename _Value, 
1973 typename _Alloc, typename _ExtractKey, typename _Equal, 
1974 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 
1975 typename _Traits> 
1976 auto 
1977 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, 
1978 _H1, _H2, _Hash, _RehashPolicy, _Traits>:: 
1979 erase(const_iterator __first, const_iterator __last) 
1980 -> iterator 
1981 { 
1982 __node_type* __n = __first._M_cur; 
1983 __node_type* __last_n = __last._M_cur; 
1984 if (__n == __last_n) 
1985 return iterator(__n); 
1986 
1987 std::size_t __bkt = _M_bucket_index(__n); 
1988 
1989 __node_base* __prev_n = _M_get_previous_node(__bkt, __n); 
1990 bool __is_bucket_begin = __n == _M_bucket_begin(__bkt); 
1991 std::size_t __n_bkt = __bkt; 
1992 for (;;) 
1993 { 
1994 do 
1995 { 
1996 __node_type* __tmp = __n; 
1997 __n = __n->_M_next(); 
1998 this->_M_deallocate_node(__tmp); 
1999 --_M_element_count; 
2000 if (!__n) 
2001 break; 
2002 __n_bkt = _M_bucket_index(__n); 
2003 } 
2004 while (__n != __last_n && __n_bkt == __bkt); 
2005 if (__is_bucket_begin) 
2006 _M_remove_bucket_begin(__bkt, __n, __n_bkt); 
2007 if (__n == __last_n) 
2008 break; 
2009 __is_bucket_begin = true; 
2010 __bkt = __n_bkt; 
2011 } 
2012 
2013 if (__n && (__n_bkt != __bkt || __is_bucket_begin)) 
2014 _M_buckets[__n_bkt] = __prev_n; 
2015 __prev_n->_M_nxt = __n; 
2016 return iterator(__n); 
2017 } 
2018 
2019 template<typename _Key, typename _Value, 
2020 typename _Alloc, typename _ExtractKey, typename _Equal, 
2021 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 
2022 typename _Traits> 
2023 void 
2024 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, 
2025 _H1, _H2, _Hash, _RehashPolicy, _Traits>:: 
2026 clear() noexcept 
2027 { 
2028 this->_M_deallocate_nodes(_M_begin()); 
2029 __builtin_memset(_M_buckets, 0, _M_bucket_count * sizeof(__bucket_type)); 
2030 _M_element_count = 0; 
2031 _M_before_begin._M_nxt = nullptr; 
2032 } 
2033 
2034 template<typename _Key, typename _Value, 
2035 typename _Alloc, typename _ExtractKey, typename _Equal, 
2036 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 
2037 typename _Traits> 
2038 void 
2039 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, 
2040 _H1, _H2, _Hash, _RehashPolicy, _Traits>:: 
2041 rehash(size_type __n) 
2042 { 
2043 const __rehash_state& __saved_state = _M_rehash_policy._M_state(); 
2044 std::size_t __buckets 
2045 = std::max(_M_rehash_policy._M_bkt_for_elements(_M_element_count + 1), 
2046 __n); 
2047 __buckets = _M_rehash_policy._M_next_bkt(__buckets); 
2048 
2049 if (__buckets != _M_bucket_count) 
2050 _M_rehash(__buckets, __saved_state); 
2051 else 
2052 // No rehash, restore previous state to keep a consistent state. 
2053 _M_rehash_policy._M_reset(__saved_state); 
2054 } 
2055 
2056 template<typename _Key, typename _Value, 
2057 typename _Alloc, typename _ExtractKey, typename _Equal, 
2058 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 
2059 typename _Traits> 
2060 void 
2061 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, 
2062 _H1, _H2, _Hash, _RehashPolicy, _Traits>:: 
2063 _M_rehash(size_type __n, const __rehash_state& __state) 
2064 { 
2065 __try 
2066 { 
2067 _M_rehash_aux(__n, __unique_keys()); 
2068 } 
2069 __catch(...) 
2070 { 
2071 // A failure here means that buckets allocation failed. We only 
2072 // have to restore hash policy previous state. 
2073 _M_rehash_policy._M_reset(__state); 
2074 __throw_exception_again; 
2075 } 
2076 } 
2077 
2078 // Rehash when there is no equivalent elements. 
2079 template<typename _Key, typename _Value, 
2080 typename _Alloc, typename _ExtractKey, typename _Equal, 
2081 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 
2082 typename _Traits> 
2083 void 
2084 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, 
2085 _H1, _H2, _Hash, _RehashPolicy, _Traits>:: 
2086 _M_rehash_aux(size_type __n, std::true_type) 
2087 { 
2088 __bucket_type* __new_buckets = _M_allocate_buckets(__n); 
2089 __node_type* __p = _M_begin(); 
2090 _M_before_begin._M_nxt = nullptr; 
2091 std::size_t __bbegin_bkt = 0; 
2092 while (__p) 
2093 { 
2094 __node_type* __next = __p->_M_next(); 
2095 std::size_t __bkt = __hash_code_base::_M_bucket_index(__p, __n); 
2096 if (!__new_buckets[__bkt]) 
2097 { 
2098 __p->_M_nxt = _M_before_begin._M_nxt; 
2099 _M_before_begin._M_nxt = __p; 
2100 __new_buckets[__bkt] = &_M_before_begin; 
2101 if (__p->_M_nxt) 
2102 __new_buckets[__bbegin_bkt] = __p; 
2103 __bbegin_bkt = __bkt; 
2104 } 
2105 else 
2106 { 
2107 __p->_M_nxt = __new_buckets[__bkt]->_M_nxt; 
2108 __new_buckets[__bkt]->_M_nxt = __p; 
2109 } 
2110 __p = __next; 
2111 } 
2112 
2113 _M_deallocate_buckets(); 
2114 _M_bucket_count = __n; 
2115 _M_buckets = __new_buckets; 
2116 } 
2117 
2118 // Rehash when there can be equivalent elements, preserve their relative 
2119 // order. 
2120 template<typename _Key, typename _Value, 
2121 typename _Alloc, typename _ExtractKey, typename _Equal, 
2122 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 
2123 typename _Traits> 
2124 void 
2125 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, 
2126 _H1, _H2, _Hash, _RehashPolicy, _Traits>:: 
2127 _M_rehash_aux(size_type __n, std::false_type) 
2128 { 
2129 __bucket_type* __new_buckets = _M_allocate_buckets(__n); 
2130 
2131 __node_type* __p = _M_begin(); 
2132 _M_before_begin._M_nxt = nullptr; 
2133 std::size_t __bbegin_bkt = 0; 
2134 std::size_t __prev_bkt = 0; 
2135 __node_type* __prev_p = nullptr; 
2136 bool __check_bucket = false; 
2137 
2138 while (__p) 
2139 { 
2140 __node_type* __next = __p->_M_next(); 
2141 std::size_t __bkt = __hash_code_base::_M_bucket_index(__p, __n); 
2142 
2143 if (__prev_p && __prev_bkt == __bkt) 
2144 { 
2145 // Previous insert was already in this bucket, we insert after 
2146 // the previously inserted one to preserve equivalent elements 
2147 // relative order. 
2148 __p->_M_nxt = __prev_p->_M_nxt; 
2149 __prev_p->_M_nxt = __p; 
2150 
2151 // Inserting after a node in a bucket require to check that we 
2152 // haven't change the bucket last node, in this case next 
2153 // bucket containing its before begin node must be updated. We 
2154 // schedule a check as soon as we move out of the sequence of 
2155 // equivalent nodes to limit the number of checks. 
2156 __check_bucket = true; 
2157 } 
2158 else 
2159 { 
2160 if (__check_bucket) 
2161 { 
2162 // Check if we shall update the next bucket because of 
2163 // insertions into __prev_bkt bucket. 
2164 if (__prev_p->_M_nxt) 
2165 { 
2166 std::size_t __next_bkt 
2167 = __hash_code_base::_M_bucket_index(__prev_p->_M_next(), 
2168 __n); 
2169 if (__next_bkt != __prev_bkt) 
2170 __new_buckets[__next_bkt] = __prev_p; 
2171 } 
2172 __check_bucket = false; 
2173 } 
2174 
2175 if (!__new_buckets[__bkt]) 
2176 { 
2177 __p->_M_nxt = _M_before_begin._M_nxt; 
2178 _M_before_begin._M_nxt = __p; 
2179 __new_buckets[__bkt] = &_M_before_begin; 
2180 if (__p->_M_nxt) 
2181 __new_buckets[__bbegin_bkt] = __p; 
2182 __bbegin_bkt = __bkt; 
2183 } 
2184 else 
2185 { 
2186 __p->_M_nxt = __new_buckets[__bkt]->_M_nxt; 
2187 __new_buckets[__bkt]->_M_nxt = __p; 
2188 } 
2189 } 
2190 __prev_p = __p; 
2191 __prev_bkt = __bkt; 
2192 __p = __next; 
2193 } 
2194 
2195 if (__check_bucket && __prev_p->_M_nxt) 
2196 { 
2197 std::size_t __next_bkt 
2198 = __hash_code_base::_M_bucket_index(__prev_p->_M_next(), __n); 
2199 if (__next_bkt != __prev_bkt) 
2200 __new_buckets[__next_bkt] = __prev_p; 
2201 } 
2202 
2203 _M_deallocate_buckets(); 
2204 _M_bucket_count = __n; 
2205 _M_buckets = __new_buckets; 
2206 } 
2207 
2208#if __cplusplus > 201402L 
2209 template<typename, typename, typename> class _Hash_merge_helper { }; 
2210#endif // C++17 
2211 
2212#if __cpp_deduction_guides >= 201606 
2213 // Used to constrain deduction guides 
2214 template<typename _Hash> 
2215 using _RequireNotAllocatorOrIntegral 
2216 = __enable_if_t<!__or_<is_integral<_Hash>, __is_allocator<_Hash>>::value>; 
2217#endif 
2218 
2219_GLIBCXX_END_NAMESPACE_VERSION 
2220} // namespace std 
2221 
2222#endif // _HASHTABLE_H 
2223