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