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