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