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 
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::
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 
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 
1226  if (__former_buckets)
1227  _M_deallocate_buckets(__former_buckets, __former_bucket_count);
1228  __ht.clear();
1229  }
1230  __catch(...)
1231  {
1232  if (__former_buckets)
1233  {
1234  _M_deallocate_buckets();
1235  _M_rehash_policy._M_reset(__former_state);
1236  _M_buckets = __former_buckets;
1237  _M_bucket_count = __former_bucket_count;
1238  }
1239  __builtin_memset(_M_buckets, 0,
1240  _M_bucket_count * sizeof(__bucket_type));
1241  __throw_exception_again;
1242  }
1243  }
1244  }
1245 
1246  template<typename _Key, typename _Value,
1247  typename _Alloc, typename _ExtractKey, typename _Equal,
1248  typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
1249  typename _Traits>
1250  _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1251  _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1252  _Hashtable(const _Hashtable& __ht)
1253  : __hashtable_base(__ht),
1254  __map_base(__ht),
1255  __rehash_base(__ht),
1256  __hashtable_alloc(
1257  __node_alloc_traits::_S_select_on_copy(__ht._M_node_allocator())),
1258  _M_buckets(nullptr),
1259  _M_bucket_count(__ht._M_bucket_count),
1260  _M_element_count(__ht._M_element_count),
1261  _M_rehash_policy(__ht._M_rehash_policy)
1262  {
1263  _M_assign(__ht,
1264  [this](const __node_type* __n)
1265  { return this->_M_allocate_node(__n->_M_v()); });
1266  }
1267 
1268  template<typename _Key, typename _Value,
1269  typename _Alloc, typename _ExtractKey, typename _Equal,
1270  typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
1271  typename _Traits>
1272  _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1273  _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1274  _Hashtable(_Hashtable&& __ht) noexcept
1275  : __hashtable_base(__ht),
1276  __map_base(__ht),
1277  __rehash_base(__ht),
1278  __hashtable_alloc(std::move(__ht._M_base_alloc())),
1279  _M_buckets(__ht._M_buckets),
1280  _M_bucket_count(__ht._M_bucket_count),
1281  _M_before_begin(__ht._M_before_begin._M_nxt),
1282  _M_element_count(__ht._M_element_count),
1283  _M_rehash_policy(__ht._M_rehash_policy)
1284  {
1285  // Update, if necessary, buckets if __ht is using its single bucket.
1286  if (__ht._M_uses_single_bucket())
1287  {
1288  _M_buckets = &_M_single_bucket;
1289  _M_single_bucket = __ht._M_single_bucket;
1290  }
1291 
1292  // Update, if necessary, bucket pointing to before begin that hasn't
1293  // moved.
1294  if (_M_begin())
1295  _M_buckets[_M_bucket_index(_M_begin())] = &_M_before_begin;
1296 
1297  __ht._M_reset();
1298  }
1299 
1300  template<typename _Key, typename _Value,
1301  typename _Alloc, typename _ExtractKey, typename _Equal,
1302  typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
1303  typename _Traits>
1304  _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1305  _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1306  _Hashtable(const _Hashtable& __ht, const allocator_type& __a)
1307  : __hashtable_base(__ht),
1308  __map_base(__ht),
1309  __rehash_base(__ht),
1310  __hashtable_alloc(__node_alloc_type(__a)),
1311  _M_buckets(),
1312  _M_bucket_count(__ht._M_bucket_count),
1313  _M_element_count(__ht._M_element_count),
1314  _M_rehash_policy(__ht._M_rehash_policy)
1315  {
1316  _M_assign(__ht,
1317  [this](const __node_type* __n)
1318  { return this->_M_allocate_node(__n->_M_v()); });
1319  }
1320 
1321  template<typename _Key, typename _Value,
1322  typename _Alloc, typename _ExtractKey, typename _Equal,
1323  typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
1324  typename _Traits>
1325  _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1326  _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1327  _Hashtable(_Hashtable&& __ht, const allocator_type& __a)
1328  : __hashtable_base(__ht),
1329  __map_base(__ht),
1330  __rehash_base(__ht),
1331  __hashtable_alloc(__node_alloc_type(__a)),
1332  _M_buckets(nullptr),
1333  _M_bucket_count(__ht._M_bucket_count),
1334  _M_element_count(__ht._M_element_count),
1335  _M_rehash_policy(__ht._M_rehash_policy)
1336  {
1337  if (__ht._M_node_allocator() == this->_M_node_allocator())
1338  {
1339  if (__ht._M_uses_single_bucket())
1340  {
1341  _M_buckets = &_M_single_bucket;
1342  _M_single_bucket = __ht._M_single_bucket;
1343  }
1344  else
1345  _M_buckets = __ht._M_buckets;
1346 
1347  _M_before_begin._M_nxt = __ht._M_before_begin._M_nxt;
1348  // Update, if necessary, bucket pointing to before begin that hasn't
1349  // moved.
1350  if (_M_begin())
1351  _M_buckets[_M_bucket_index(_M_begin())] = &_M_before_begin;
1352  __ht._M_reset();
1353  }
1354  else
1355  {
1356  _M_assign(__ht,
1357  [this](__node_type* __n)
1358  {
1359  return this->_M_allocate_node(
1360  std::move_if_noexcept(__n->_M_v()));
1361  });
1362  __ht.clear();
1363  }
1364  }
1365 
1366  template<typename _Key, typename _Value,
1367  typename _Alloc, typename _ExtractKey, typename _Equal,
1368  typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
1369  typename _Traits>
1370  _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1371  _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1372  ~_Hashtable() noexcept
1373  {
1374  clear();
1375  _M_deallocate_buckets();
1376  }
1377 
1378  template<typename _Key, typename _Value,
1379  typename _Alloc, typename _ExtractKey, typename _Equal,
1380  typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
1381  typename _Traits>
1382  void
1383  _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1384  _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1385  swap(_Hashtable& __x)
1386  noexcept(__and_<__is_nothrow_swappable<_H1>,
1387  __is_nothrow_swappable<_Equal>>::value)
1388  {
1389  // The only base class with member variables is hash_code_base.
1390  // We define _Hash_code_base::_M_swap because different
1391  // specializations have different members.
1392  this->_M_swap(__x);
1393 
1394  std::__alloc_on_swap(this->_M_node_allocator(), __x._M_node_allocator());
1395  std::swap(_M_rehash_policy, __x._M_rehash_policy);
1396 
1397  // Deal properly with potentially moved instances.
1398  if (this->_M_uses_single_bucket())
1399  {
1400  if (!__x._M_uses_single_bucket())
1401  {
1402  _M_buckets = __x._M_buckets;
1403  __x._M_buckets = &__x._M_single_bucket;
1404  }
1405  }
1406  else if (__x._M_uses_single_bucket())
1407  {
1408  __x._M_buckets = _M_buckets;
1409  _M_buckets = &_M_single_bucket;
1410  }
1411  else
1412  std::swap(_M_buckets, __x._M_buckets);
1413 
1414  std::swap(_M_bucket_count, __x._M_bucket_count);
1415  std::swap(_M_before_begin._M_nxt, __x._M_before_begin._M_nxt);
1416  std::swap(_M_element_count, __x._M_element_count);
1417  std::swap(_M_single_bucket, __x._M_single_bucket);
1418 
1419  // Fix buckets containing the _M_before_begin pointers that can't be
1420  // swapped.
1421  if (_M_begin())
1422  _M_buckets[_M_bucket_index(_M_begin())] = &_M_before_begin;
1423 
1424  if (__x._M_begin())
1425  __x._M_buckets[__x._M_bucket_index(__x._M_begin())]
1426  = &__x._M_before_begin;
1427  }
1428 
1429  template<typename _Key, typename _Value,
1430  typename _Alloc, typename _ExtractKey, typename _Equal,
1431  typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
1432  typename _Traits>
1433  auto
1434  _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1435  _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1436  find(const key_type& __k)
1437  -> iterator
1438  {
1439  __hash_code __code = this->_M_hash_code(__k);
1440  std::size_t __n = _M_bucket_index(__k, __code);
1441  __node_type* __p = _M_find_node(__n, __k, __code);
1442  return __p ? iterator(__p) : end();
1443  }
1444 
1445  template<typename _Key, typename _Value,
1446  typename _Alloc, typename _ExtractKey, typename _Equal,
1447  typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
1448  typename _Traits>
1449  auto
1450  _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1451  _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1452  find(const key_type& __k) const
1453  -> const_iterator
1454  {
1455  __hash_code __code = this->_M_hash_code(__k);
1456  std::size_t __n = _M_bucket_index(__k, __code);
1457  __node_type* __p = _M_find_node(__n, __k, __code);
1458  return __p ? const_iterator(__p) : end();
1459  }
1460 
1461  template<typename _Key, typename _Value,
1462  typename _Alloc, typename _ExtractKey, typename _Equal,
1463  typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
1464  typename _Traits>
1465  auto
1466  _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1467  _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1468  count(const key_type& __k) const
1469  -> size_type
1470  {
1471  __hash_code __code = this->_M_hash_code(__k);
1472  std::size_t __n = _M_bucket_index(__k, __code);
1473  __node_type* __p = _M_bucket_begin(__n);
1474  if (!__p)
1475  return 0;
1476 
1477  std::size_t __result = 0;
1478  for (;; __p = __p->_M_next())
1479  {
1480  if (this->_M_equals(__k, __code, __p))
1481  ++__result;
1482  else if (__result)
1483  // All equivalent values are next to each other, if we
1484  // found a non-equivalent value after an equivalent one it
1485  // means that we won't find any new equivalent value.
1486  break;
1487  if (!__p->_M_nxt || _M_bucket_index(__p->_M_next()) != __n)
1488  break;
1489  }
1490  return __result;
1491  }
1492 
1493  template<typename _Key, typename _Value,
1494  typename _Alloc, typename _ExtractKey, typename _Equal,
1495  typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
1496  typename _Traits>
1497  auto
1498  _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1499  _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1500  equal_range(const key_type& __k)
1501  -> pair<iterator, iterator>
1502  {
1503  __hash_code __code = this->_M_hash_code(__k);
1504  std::size_t __n = _M_bucket_index(__k, __code);
1505  __node_type* __p = _M_find_node(__n, __k, __code);
1506 
1507  if (__p)
1508  {
1509  __node_type* __p1 = __p->_M_next();
1510  while (__p1 && _M_bucket_index(__p1) == __n
1511  && this->_M_equals(__k, __code, __p1))
1512  __p1 = __p1->_M_next();
1513 
1514  return std::make_pair(iterator(__p), iterator(__p1));
1515  }
1516  else
1517  return std::make_pair(end(), end());
1518  }
1519 
1520  template<typename _Key, typename _Value,
1521  typename _Alloc, typename _ExtractKey, typename _Equal,
1522  typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
1523  typename _Traits>
1524  auto
1525  _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1526  _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1527  equal_range(const key_type& __k) const
1528  -> pair<const_iterator, const_iterator>
1529  {
1530  __hash_code __code = this->_M_hash_code(__k);
1531  std::size_t __n = _M_bucket_index(__k, __code);
1532  __node_type* __p = _M_find_node(__n, __k, __code);
1533 
1534  if (__p)
1535  {
1536  __node_type* __p1 = __p->_M_next();
1537  while (__p1 && _M_bucket_index(__p1) == __n
1538  && this->_M_equals(__k, __code, __p1))
1539  __p1 = __p1->_M_next();
1540 
1541  return std::make_pair(const_iterator(__p), const_iterator(__p1));
1542  }
1543  else
1544  return std::make_pair(end(), end());
1545  }
1546 
1547  // Find the node whose key compares equal to k in the bucket n.
1548  // Return nullptr if no node is found.
1549  template<typename _Key, typename _Value,
1550  typename _Alloc, typename _ExtractKey, typename _Equal,
1551  typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
1552  typename _Traits>
1553  auto
1554  _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1555  _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1556  _M_find_before_node(size_type __n, const key_type& __k,
1557  __hash_code __code) const
1558  -> __node_base*
1559  {
1560  __node_base* __prev_p = _M_buckets[__n];
1561  if (!__prev_p)
1562  return nullptr;
1563 
1564  for (__node_type* __p = static_cast<__node_type*>(__prev_p->_M_nxt);;
1565  __p = __p->_M_next())
1566  {
1567  if (this->_M_equals(__k, __code, __p))
1568  return __prev_p;
1569 
1570  if (!__p->_M_nxt || _M_bucket_index(__p->_M_next()) != __n)
1571  break;
1572  __prev_p = __p;
1573  }
1574  return nullptr;
1575  }
1576 
1577  template<typename _Key, typename _Value,
1578  typename _Alloc, typename _ExtractKey, typename _Equal,
1579  typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
1580  typename _Traits>
1581  void
1582  _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1583  _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1584  _M_insert_bucket_begin(size_type __bkt, __node_type* __node)
1585  {
1586  if (_M_buckets[__bkt])
1587  {
1588  // Bucket is not empty, we just need to insert the new node
1589  // after the bucket before begin.
1590  __node->_M_nxt = _M_buckets[__bkt]->_M_nxt;
1591  _M_buckets[__bkt]->_M_nxt = __node;
1592  }
1593  else
1594  {
1595  // The bucket is empty, the new node is inserted at the
1596  // beginning of the singly-linked list and the bucket will
1597  // contain _M_before_begin pointer.
1598  __node->_M_nxt = _M_before_begin._M_nxt;
1599  _M_before_begin._M_nxt = __node;
1600  if (__node->_M_nxt)
1601  // We must update former begin bucket that is pointing to
1602  // _M_before_begin.
1603  _M_buckets[_M_bucket_index(__node->_M_next())] = __node;
1604  _M_buckets[__bkt] = &_M_before_begin;
1605  }
1606  }
1607 
1608  template<typename _Key, typename _Value,
1609  typename _Alloc, typename _ExtractKey, typename _Equal,
1610  typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
1611  typename _Traits>
1612  void
1613  _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1614  _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1615  _M_remove_bucket_begin(size_type __bkt, __node_type* __next,
1616  size_type __next_bkt)
1617  {
1618  if (!__next || __next_bkt != __bkt)
1619  {
1620  // Bucket is now empty
1621  // First update next bucket if any
1622  if (__next)
1623  _M_buckets[__next_bkt] = _M_buckets[__bkt];
1624 
1625  // Second update before begin node if necessary
1626  if (&_M_before_begin == _M_buckets[__bkt])
1627  _M_before_begin._M_nxt = __next;
1628  _M_buckets[__bkt] = nullptr;
1629  }
1630  }
1631 
1632  template<typename _Key, typename _Value,
1633  typename _Alloc, typename _ExtractKey, typename _Equal,
1634  typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
1635  typename _Traits>
1636  auto
1637  _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1638  _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1639  _M_get_previous_node(size_type __bkt, __node_base* __n)
1640  -> __node_base*
1641  {
1642  __node_base* __prev_n = _M_buckets[__bkt];
1643  while (__prev_n->_M_nxt != __n)
1644  __prev_n = __prev_n->_M_nxt;
1645  return __prev_n;
1646  }
1647 
1648  template<typename _Key, typename _Value,
1649  typename _Alloc, typename _ExtractKey, typename _Equal,
1650  typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
1651  typename _Traits>
1652  template<typename... _Args>
1653  auto
1654  _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1655  _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1656  _M_emplace(std::true_type, _Args&&... __args)
1657  -> pair<iterator, bool>
1658  {
1659  // First build the node to get access to the hash code
1660  __node_type* __node = this->_M_allocate_node(std::forward<_Args>(__args)...);
1661  const key_type& __k = this->_M_extract()(__node->_M_v());
1662  __hash_code __code;
1663  __try
1664  {
1665  __code = this->_M_hash_code(__k);
1666  }
1667  __catch(...)
1668  {
1669  this->_M_deallocate_node(__node);
1670  __throw_exception_again;
1671  }
1672 
1673  size_type __bkt = _M_bucket_index(__k, __code);
1674  if (__node_type* __p = _M_find_node(__bkt, __k, __code))
1675  {
1676  // There is already an equivalent node, no insertion
1677  this->_M_deallocate_node(__node);
1678  return std::make_pair(iterator(__p), false);
1679  }
1680 
1681  // Insert the node
1682  return std::make_pair(_M_insert_unique_node(__bkt, __code, __node),
1683  true);
1684  }
1685 
1686  template<typename _Key, typename _Value,
1687  typename _Alloc, typename _ExtractKey, typename _Equal,
1688  typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
1689  typename _Traits>
1690  template<typename... _Args>
1691  auto
1692  _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1693  _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1694  _M_emplace(const_iterator __hint, std::false_type, _Args&&... __args)
1695  -> iterator
1696  {
1697  // First build the node to get its hash code.
1698  __node_type* __node =
1699  this->_M_allocate_node(std::forward<_Args>(__args)...);
1700 
1701  __hash_code __code;
1702  __try
1703  {
1704  __code = this->_M_hash_code(this->_M_extract()(__node->_M_v()));
1705  }
1706  __catch(...)
1707  {
1708  this->_M_deallocate_node(__node);
1709  __throw_exception_again;
1710  }
1711 
1712  return _M_insert_multi_node(__hint._M_cur, __code, __node);
1713  }
1714 
1715  template<typename _Key, typename _Value,
1716  typename _Alloc, typename _ExtractKey, typename _Equal,
1717  typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
1718  typename _Traits>
1719  auto
1720  _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1721  _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1722  _M_insert_unique_node(size_type __bkt, __hash_code __code,
1723  __node_type* __node, size_type __n_elt)
1724  -> iterator
1725  {
1726  const __rehash_state& __saved_state = _M_rehash_policy._M_state();
1727  std::pair<bool, std::size_t> __do_rehash
1728  = _M_rehash_policy._M_need_rehash(_M_bucket_count, _M_element_count,
1729  __n_elt);
1730 
1731  __try
1732  {
1733  if (__do_rehash.first)
1734  {
1735  _M_rehash(__do_rehash.second, __saved_state);
1736  __bkt = _M_bucket_index(this->_M_extract()(__node->_M_v()), __code);
1737  }
1738 
1739  this->_M_store_code(__node, __code);
1740 
1741  // Always insert at the beginning of the bucket.
1742  _M_insert_bucket_begin(__bkt, __node);
1743  ++_M_element_count;
1744  return iterator(__node);
1745  }
1746  __catch(...)
1747  {
1748  this->_M_deallocate_node(__node);
1749  __throw_exception_again;
1750  }
1751  }
1752 
1753  // Insert node, in bucket bkt if no rehash (assumes no element with its key
1754  // already present). Take ownership of the node, deallocate it on exception.
1755  template<typename _Key, typename _Value,
1756  typename _Alloc, typename _ExtractKey, typename _Equal,
1757  typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
1758  typename _Traits>
1759  auto
1760  _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1761  _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1762  _M_insert_multi_node(__node_type* __hint, __hash_code __code,
1763  __node_type* __node)
1764  -> iterator
1765  {
1766  const __rehash_state& __saved_state = _M_rehash_policy._M_state();
1767  std::pair<bool, std::size_t> __do_rehash
1768  = _M_rehash_policy._M_need_rehash(_M_bucket_count, _M_element_count, 1);
1769 
1770  __try
1771  {
1772  if (__do_rehash.first)
1773  _M_rehash(__do_rehash.second, __saved_state);
1774 
1775  this->_M_store_code(__node, __code);
1776  const key_type& __k = this->_M_extract()(__node->_M_v());
1777  size_type __bkt = _M_bucket_index(__k, __code);
1778 
1779  // Find the node before an equivalent one or use hint if it exists and
1780  // if it is equivalent.
1781  __node_base* __prev
1782  = __builtin_expect(__hint != nullptr, false)
1783  && this->_M_equals(__k, __code, __hint)
1784  ? __hint
1785  : _M_find_before_node(__bkt, __k, __code);
1786  if (__prev)
1787  {
1788  // Insert after the node before the equivalent one.
1789  __node->_M_nxt = __prev->_M_nxt;
1790  __prev->_M_nxt = __node;
1791  if (__builtin_expect(__prev == __hint, false))
1792  // hint might be the last bucket node, in this case we need to
1793  // update next bucket.
1794  if (__node->_M_nxt
1795  && !this->_M_equals(__k, __code, __node->_M_next()))
1796  {
1797  size_type __next_bkt = _M_bucket_index(__node->_M_next());
1798  if (__next_bkt != __bkt)
1799  _M_buckets[__next_bkt] = __node;
1800  }
1801  }
1802  else
1803  // The inserted node has no equivalent in the
1804  // hashtable. We must insert the new node at the
1805  // beginning of the bucket to preserve equivalent
1806  // elements' relative positions.
1807  _M_insert_bucket_begin(__bkt, __node);
1808  ++_M_element_count;
1809  return iterator(__node);
1810  }
1811  __catch(...)
1812  {
1813  this->_M_deallocate_node(__node);
1814  __throw_exception_again;
1815  }
1816  }
1817 
1818  // Insert v if no element with its key is already present.
1819  template<typename _Key, typename _Value,
1820  typename _Alloc, typename _ExtractKey, typename _Equal,
1821  typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
1822  typename _Traits>
1823  template<typename _Arg, typename _NodeGenerator>
1824  auto
1825  _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1826  _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1827  _M_insert(_Arg&& __v, const _NodeGenerator& __node_gen, true_type,
1828  size_type __n_elt)
1829  -> pair<iterator, bool>
1830  {
1831  const key_type& __k = this->_M_extract()(__v);
1832  __hash_code __code = this->_M_hash_code(__k);
1833  size_type __bkt = _M_bucket_index(__k, __code);
1834 
1835  __node_type* __n = _M_find_node(__bkt, __k, __code);
1836  if (__n)
1837  return std::make_pair(iterator(__n), false);
1838 
1839  __n = __node_gen(std::forward<_Arg>(__v));
1840  return { _M_insert_unique_node(__bkt, __code, __n, __n_elt), true };
1841  }
1842 
1843  // Insert v unconditionally.
1844  template<typename _Key, typename _Value,
1845  typename _Alloc, typename _ExtractKey, typename _Equal,
1846  typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
1847  typename _Traits>
1848  template<typename _Arg, typename _NodeGenerator>
1849  auto
1850  _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1851  _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1852  _M_insert(const_iterator __hint, _Arg&& __v,
1853  const _NodeGenerator& __node_gen, false_type)
1854  -> iterator
1855  {
1856  // First compute the hash code so that we don't do anything if it
1857  // throws.
1858  __hash_code __code = this->_M_hash_code(this->_M_extract()(__v));
1859 
1860  // Second allocate new node so that we don't rehash if it throws.
1861  __node_type* __node = __node_gen(std::forward<_Arg>(__v));
1862 
1863  return _M_insert_multi_node(__hint._M_cur, __code, __node);
1864  }
1865 
1866  template<typename _Key, typename _Value,
1867  typename _Alloc, typename _ExtractKey, typename _Equal,
1868  typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
1869  typename _Traits>
1870  auto
1871  _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1872  _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1873  erase(const_iterator __it)
1874  -> iterator
1875  {
1876  __node_type* __n = __it._M_cur;
1877  std::size_t __bkt = _M_bucket_index(__n);
1878 
1879  // Look for previous node to unlink it from the erased one, this
1880  // is why we need buckets to contain the before begin to make
1881  // this search fast.
1882  __node_base* __prev_n = _M_get_previous_node(__bkt, __n);
1883  return _M_erase(__bkt, __prev_n, __n);
1884  }
1885 
1886  template<typename _Key, typename _Value,
1887  typename _Alloc, typename _ExtractKey, typename _Equal,
1888  typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
1889  typename _Traits>
1890  auto
1891  _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1892  _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1893  _M_erase(size_type __bkt, __node_base* __prev_n, __node_type* __n)
1894  -> iterator
1895  {
1896  if (__prev_n == _M_buckets[__bkt])
1897  _M_remove_bucket_begin(__bkt, __n->_M_next(),
1898  __n->_M_nxt ? _M_bucket_index(__n->_M_next()) : 0);
1899  else if (__n->_M_nxt)
1900  {
1901  size_type __next_bkt = _M_bucket_index(__n->_M_next());
1902  if (__next_bkt != __bkt)
1903  _M_buckets[__next_bkt] = __prev_n;
1904  }
1905 
1906  __prev_n->_M_nxt = __n->_M_nxt;
1907  iterator __result(__n->_M_next());
1908  this->_M_deallocate_node(__n);
1909  --_M_element_count;
1910 
1911  return __result;
1912  }
1913 
1914  template<typename _Key, typename _Value,
1915  typename _Alloc, typename _ExtractKey, typename _Equal,
1916  typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
1917  typename _Traits>
1918  auto
1919  _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1920  _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1921  _M_erase(std::true_type, const key_type& __k)
1922  -> size_type
1923  {
1924  __hash_code __code = this->_M_hash_code(__k);
1925  std::size_t __bkt = _M_bucket_index(__k, __code);
1926 
1927  // Look for the node before the first matching node.
1928  __node_base* __prev_n = _M_find_before_node(__bkt, __k, __code);
1929  if (!__prev_n)
1930  return 0;
1931 
1932  // We found a matching node, erase it.
1933  __node_type* __n = static_cast<__node_type*>(__prev_n->_M_nxt);
1934  _M_erase(__bkt, __prev_n, __n);
1935  return 1;
1936  }
1937 
1938  template<typename _Key, typename _Value,
1939  typename _Alloc, typename _ExtractKey, typename _Equal,
1940  typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
1941  typename _Traits>
1942  auto
1943  _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1944  _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1945  _M_erase(std::false_type, const key_type& __k)
1946  -> size_type
1947  {
1948  __hash_code __code = this->_M_hash_code(__k);
1949  std::size_t __bkt = _M_bucket_index(__k, __code);
1950 
1951  // Look for the node before the first matching node.
1952  __node_base* __prev_n = _M_find_before_node(__bkt, __k, __code);
1953  if (!__prev_n)
1954  return 0;
1955 
1956  // _GLIBCXX_RESOLVE_LIB_DEFECTS
1957  // 526. Is it undefined if a function in the standard changes
1958  // in parameters?
1959  // We use one loop to find all matching nodes and another to deallocate
1960  // them so that the key stays valid during the first loop. It might be
1961  // invalidated indirectly when destroying nodes.
1962  __node_type* __n = static_cast<__node_type*>(__prev_n->_M_nxt);
1963  __node_type* __n_last = __n;
1964  std::size_t __n_last_bkt = __bkt;
1965  do
1966  {
1967  __n_last = __n_last->_M_next();
1968  if (!__n_last)
1969  break;
1970  __n_last_bkt = _M_bucket_index(__n_last);
1971  }
1972  while (__n_last_bkt == __bkt && this->_M_equals(__k, __code, __n_last));
1973 
1974  // Deallocate nodes.
1975  size_type __result = 0;
1976  do
1977  {
1978  __node_type* __p = __n->_M_next();
1979  this->_M_deallocate_node(__n);
1980  __n = __p;
1981  ++__result;
1982  --_M_element_count;
1983  }
1984  while (__n != __n_last);
1985 
1986  if (__prev_n == _M_buckets[__bkt])
1987  _M_remove_bucket_begin(__bkt, __n_last, __n_last_bkt);
1988  else if (__n_last && __n_last_bkt != __bkt)
1989  _M_buckets[__n_last_bkt] = __prev_n;
1990  __prev_n->_M_nxt = __n_last;
1991  return __result;
1992  }
1993 
1994  template<typename _Key, typename _Value,
1995  typename _Alloc, typename _ExtractKey, typename _Equal,
1996  typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
1997  typename _Traits>
1998  auto
1999  _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
2000  _H1, _H2, _Hash, _RehashPolicy, _Traits>::
2001  erase(const_iterator __first, const_iterator __last)
2002  -> iterator
2003  {
2004  __node_type* __n = __first._M_cur;
2005  __node_type* __last_n = __last._M_cur;
2006  if (__n == __last_n)
2007  return iterator(__n);
2008 
2009  std::size_t __bkt = _M_bucket_index(__n);
2010 
2011  __node_base* __prev_n = _M_get_previous_node(__bkt, __n);
2012  bool __is_bucket_begin = __n == _M_bucket_begin(__bkt);
2013  std::size_t __n_bkt = __bkt;
2014  for (;;)
2015  {
2016  do
2017  {
2018  __node_type* __tmp = __n;
2019  __n = __n->_M_next();
2020  this->_M_deallocate_node(__tmp);
2021  --_M_element_count;
2022  if (!__n)
2023  break;
2024  __n_bkt = _M_bucket_index(__n);
2025  }
2026  while (__n != __last_n && __n_bkt == __bkt);
2027  if (__is_bucket_begin)
2028  _M_remove_bucket_begin(__bkt, __n, __n_bkt);
2029  if (__n == __last_n)
2030  break;
2031  __is_bucket_begin = true;
2032  __bkt = __n_bkt;
2033  }
2034 
2035  if (__n && (__n_bkt != __bkt || __is_bucket_begin))
2036  _M_buckets[__n_bkt] = __prev_n;
2037  __prev_n->_M_nxt = __n;
2038  return iterator(__n);
2039  }
2040 
2041  template<typename _Key, typename _Value,
2042  typename _Alloc, typename _ExtractKey, typename _Equal,
2043  typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
2044  typename _Traits>
2045  void
2046  _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
2047  _H1, _H2, _Hash, _RehashPolicy, _Traits>::
2048  clear() noexcept
2049  {
2050  this->_M_deallocate_nodes(_M_begin());
2051  __builtin_memset(_M_buckets, 0, _M_bucket_count * sizeof(__bucket_type));
2052  _M_element_count = 0;
2053  _M_before_begin._M_nxt = nullptr;
2054  }
2055 
2056  template<typename _Key, typename _Value,
2057  typename _Alloc, typename _ExtractKey, typename _Equal,
2058  typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
2059  typename _Traits>
2060  void
2061  _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
2062  _H1, _H2, _Hash, _RehashPolicy, _Traits>::
2063  rehash(size_type __n)
2064  {
2065  const __rehash_state& __saved_state = _M_rehash_policy._M_state();
2066  std::size_t __buckets
2067  = std::max(_M_rehash_policy._M_bkt_for_elements(_M_element_count + 1),
2068  __n);
2069  __buckets = _M_rehash_policy._M_next_bkt(__buckets);
2070 
2071  if (__buckets != _M_bucket_count)
2072  _M_rehash(__buckets, __saved_state);
2073  else
2074  // No rehash, restore previous state to keep a consistent state.
2075  _M_rehash_policy._M_reset(__saved_state);
2076  }
2077 
2078  template<typename _Key, typename _Value,
2079  typename _Alloc, typename _ExtractKey, typename _Equal,
2080  typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
2081  typename _Traits>
2082  void
2083  _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
2084  _H1, _H2, _Hash, _RehashPolicy, _Traits>::
2085  _M_rehash(size_type __n, const __rehash_state& __state)
2086  {
2087  __try
2088  {
2089  _M_rehash_aux(__n, __unique_keys());
2090  }
2091  __catch(...)
2092  {
2093  // A failure here means that buckets allocation failed. We only
2094  // have to restore hash policy previous state.
2095  _M_rehash_policy._M_reset(__state);
2096  __throw_exception_again;
2097  }
2098  }
2099 
2100  // Rehash when there is no equivalent elements.
2101  template<typename _Key, typename _Value,
2102  typename _Alloc, typename _ExtractKey, typename _Equal,
2103  typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
2104  typename _Traits>
2105  void
2106  _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
2107  _H1, _H2, _Hash, _RehashPolicy, _Traits>::
2108  _M_rehash_aux(size_type __n, std::true_type)
2109  {
2110  __bucket_type* __new_buckets = _M_allocate_buckets(__n);
2111  __node_type* __p = _M_begin();
2112  _M_before_begin._M_nxt = nullptr;
2113  std::size_t __bbegin_bkt = 0;
2114  while (__p)
2115  {
2116  __node_type* __next = __p->_M_next();
2117  std::size_t __bkt = __hash_code_base::_M_bucket_index(__p, __n);
2118  if (!__new_buckets[__bkt])
2119  {
2120  __p->_M_nxt = _M_before_begin._M_nxt;
2121  _M_before_begin._M_nxt = __p;
2122  __new_buckets[__bkt] = &_M_before_begin;
2123  if (__p->_M_nxt)
2124  __new_buckets[__bbegin_bkt] = __p;
2125  __bbegin_bkt = __bkt;
2126  }
2127  else
2128  {
2129  __p->_M_nxt = __new_buckets[__bkt]->_M_nxt;
2130  __new_buckets[__bkt]->_M_nxt = __p;
2131  }
2132  __p = __next;
2133  }
2134 
2135  _M_deallocate_buckets();
2136  _M_bucket_count = __n;
2137  _M_buckets = __new_buckets;
2138  }
2139 
2140  // Rehash when there can be equivalent elements, preserve their relative
2141  // order.
2142  template<typename _Key, typename _Value,
2143  typename _Alloc, typename _ExtractKey, typename _Equal,
2144  typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
2145  typename _Traits>
2146  void
2147  _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
2148  _H1, _H2, _Hash, _RehashPolicy, _Traits>::
2149  _M_rehash_aux(size_type __n, std::false_type)
2150  {
2151  __bucket_type* __new_buckets = _M_allocate_buckets(__n);
2152 
2153  __node_type* __p = _M_begin();
2154  _M_before_begin._M_nxt = nullptr;
2155  std::size_t __bbegin_bkt = 0;
2156  std::size_t __prev_bkt = 0;
2157  __node_type* __prev_p = nullptr;
2158  bool __check_bucket = false;
2159 
2160  while (__p)
2161  {
2162  __node_type* __next = __p->_M_next();
2163  std::size_t __bkt = __hash_code_base::_M_bucket_index(__p, __n);
2164 
2165  if (__prev_p && __prev_bkt == __bkt)
2166  {
2167  // Previous insert was already in this bucket, we insert after
2168  // the previously inserted one to preserve equivalent elements
2169  // relative order.
2170  __p->_M_nxt = __prev_p->_M_nxt;
2171  __prev_p->_M_nxt = __p;
2172 
2173  // Inserting after a node in a bucket require to check that we
2174  // haven't change the bucket last node, in this case next
2175  // bucket containing its before begin node must be updated. We
2176  // schedule a check as soon as we move out of the sequence of
2177  // equivalent nodes to limit the number of checks.
2178  __check_bucket = true;
2179  }
2180  else
2181  {
2182  if (__check_bucket)
2183  {
2184  // Check if we shall update the next bucket because of
2185  // insertions into __prev_bkt bucket.
2186  if (__prev_p->_M_nxt)
2187  {
2188  std::size_t __next_bkt
2189  = __hash_code_base::_M_bucket_index(__prev_p->_M_next(),
2190  __n);
2191  if (__next_bkt != __prev_bkt)
2192  __new_buckets[__next_bkt] = __prev_p;
2193  }
2194  __check_bucket = false;
2195  }
2196 
2197  if (!__new_buckets[__bkt])
2198  {
2199  __p->_M_nxt = _M_before_begin._M_nxt;
2200  _M_before_begin._M_nxt = __p;
2201  __new_buckets[__bkt] = &_M_before_begin;
2202  if (__p->_M_nxt)
2203  __new_buckets[__bbegin_bkt] = __p;
2204  __bbegin_bkt = __bkt;
2205  }
2206  else
2207  {
2208  __p->_M_nxt = __new_buckets[__bkt]->_M_nxt;
2209  __new_buckets[__bkt]->_M_nxt = __p;
2210  }
2211  }
2212  __prev_p = __p;
2213  __prev_bkt = __bkt;
2214  __p = __next;
2215  }
2216 
2217  if (__check_bucket && __prev_p->_M_nxt)
2218  {
2219  std::size_t __next_bkt
2220  = __hash_code_base::_M_bucket_index(__prev_p->_M_next(), __n);
2221  if (__next_bkt != __prev_bkt)
2222  __new_buckets[__next_bkt] = __prev_p;
2223  }
2224 
2225  _M_deallocate_buckets();
2226  _M_bucket_count = __n;
2227  _M_buckets = __new_buckets;
2228  }
2229 
2230 #if __cplusplus > 201402L
2231  template<typename, typename, typename> class _Hash_merge_helper { };
2232 #endif // C++17
2233 
2234 _GLIBCXX_END_NAMESPACE_VERSION
2235 } // namespace std
2236 
2237 #endif // _HASHTABLE_H
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
_GLIBCXX17_CONSTEXPR iterator_traits< _InputIterator >::difference_type distance(_InputIterator __first, _InputIterator __last)
A generalization of pointer arithmetic.
constexpr const _Tp * end(initializer_list< _Tp > __ils) noexcept
Return an iterator pointing to one past the last element of the initializer_list. ...
Uniform interface to C++98 and C++11 allocators.
Node const_iterators, used to iterate through all the hashtable.
enable_if< ::__array_traits< _Tp, _Nm >::_Is_swappable::value >::type noexcept(noexcept(__one.swap(__two)))
swap
Definition: array:295
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
is_nothrow_move_assignable
Definition: type_traits:1132
integral_constant< bool, false > false_type
The type used as a compile-time boolean with false value.
Definition: type_traits:78
integral_constant< bool, true > true_type
The type used as a compile-time boolean with true value.
Definition: type_traits:75
_T2 second
first is a copy of the first object
Definition: stl_pair.h:215
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
_GLIBCXX14_CONSTEXPR const _Tp & max(const _Tp &, const _Tp &)
This does what you think it does.
Definition: stl_algobase.h:219
is_default_constructible
Definition: type_traits:914
integral_constant
Definition: type_traits:57
constexpr const _Tp * begin(initializer_list< _Tp > __ils) noexcept
Return an iterator pointing to the first element of the initializer_list.
_Tp exchange(_Tp &__obj, _Up &&__new_val)
Assign __new_val to __obj and return its previous value.
Definition: utility:283
is_same
Definition: type_traits:1328
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
_T1 first
second_type is the second bound type
Definition: stl_pair.h:214
Define a member typedef type to one of two argument types.
Definition: type_traits:92
initializer_list
Node iterators, used to iterate through all the hashtable.