libstdc++
hashtable_policy.h
Go to the documentation of this file.
1 // Internal policy header for unordered_set and unordered_map -*- C++ -*-
2 
3 // Copyright (C) 2010-2023 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_policy.h
26  * This is an internal header file, included by other library headers.
27  * Do not attempt to use it directly.
28  * @headername{unordered_map,unordered_set}
29  */
30 
31 #ifndef _HASHTABLE_POLICY_H
32 #define _HASHTABLE_POLICY_H 1
33 
34 #include <tuple> // for std::tuple, std::forward_as_tuple
35 #include <bits/functional_hash.h> // for __is_fast_hash
36 #include <bits/stl_algobase.h> // for std::min, std::is_permutation.
37 #include <bits/stl_pair.h> // for std::pair
38 #include <ext/aligned_buffer.h> // for __gnu_cxx::__aligned_buffer
39 #include <ext/alloc_traits.h> // for std::__alloc_rebind
40 #include <ext/numeric_traits.h> // for __gnu_cxx::__int_traits
41 
42 namespace std _GLIBCXX_VISIBILITY(default)
43 {
44 _GLIBCXX_BEGIN_NAMESPACE_VERSION
45 /// @cond undocumented
46 
47  template<typename _Key, typename _Value, typename _Alloc,
48  typename _ExtractKey, typename _Equal,
49  typename _Hash, typename _RangeHash, typename _Unused,
50  typename _RehashPolicy, typename _Traits>
51  class _Hashtable;
52 
53 namespace __detail
54 {
55  /**
56  * @defgroup hashtable-detail Base and Implementation Classes
57  * @ingroup unordered_associative_containers
58  * @{
59  */
60  template<typename _Key, typename _Value, typename _ExtractKey,
61  typename _Equal, typename _Hash, typename _RangeHash,
62  typename _Unused, typename _Traits>
63  struct _Hashtable_base;
64 
65  // Helper function: return distance(first, last) for forward
66  // iterators, or 0/1 for input iterators.
67  template<typename _Iterator>
69  __distance_fw(_Iterator __first, _Iterator __last,
71  { return __first != __last ? 1 : 0; }
72 
73  template<typename _Iterator>
75  __distance_fw(_Iterator __first, _Iterator __last,
77  { return std::distance(__first, __last); }
78 
79  template<typename _Iterator>
81  __distance_fw(_Iterator __first, _Iterator __last)
82  { return __distance_fw(__first, __last,
83  std::__iterator_category(__first)); }
84 
85  struct _Identity
86  {
87  template<typename _Tp>
88  _Tp&&
89  operator()(_Tp&& __x) const noexcept
90  { return std::forward<_Tp>(__x); }
91  };
92 
93  struct _Select1st
94  {
95  template<typename _Pair>
96  struct __1st_type;
97 
98  template<typename _Tp, typename _Up>
99  struct __1st_type<pair<_Tp, _Up>>
100  { using type = _Tp; };
101 
102  template<typename _Tp, typename _Up>
103  struct __1st_type<const pair<_Tp, _Up>>
104  { using type = const _Tp; };
105 
106  template<typename _Pair>
107  struct __1st_type<_Pair&>
108  { using type = typename __1st_type<_Pair>::type&; };
109 
110  template<typename _Tp>
111  typename __1st_type<_Tp>::type&&
112  operator()(_Tp&& __x) const noexcept
113  { return std::forward<_Tp>(__x).first; }
114  };
115 
116  template<typename _ExKey, typename _Value>
117  struct _ConvertToValueType;
118 
119  template<typename _Value>
120  struct _ConvertToValueType<_Identity, _Value>
121  {
122  template<typename _Kt>
123  constexpr _Kt&&
124  operator()(_Kt&& __k) const noexcept
125  { return std::forward<_Kt>(__k); }
126  };
127 
128  template<typename _Value>
129  struct _ConvertToValueType<_Select1st, _Value>
130  {
131  constexpr _Value&&
132  operator()(_Value&& __x) const noexcept
133  { return std::move(__x); }
134 
135  constexpr const _Value&
136  operator()(const _Value& __x) const noexcept
137  { return __x; }
138 
139  template<typename _Kt, typename _Val>
140  constexpr std::pair<_Kt, _Val>&&
141  operator()(std::pair<_Kt, _Val>&& __x) const noexcept
142  { return std::move(__x); }
143 
144  template<typename _Kt, typename _Val>
145  constexpr const std::pair<_Kt, _Val>&
146  operator()(const std::pair<_Kt, _Val>& __x) const noexcept
147  { return __x; }
148  };
149 
150  template<typename _ExKey>
151  struct _NodeBuilder;
152 
153  template<>
154  struct _NodeBuilder<_Select1st>
155  {
156  template<typename _Kt, typename _Arg, typename _NodeGenerator>
157  static auto
158  _S_build(_Kt&& __k, _Arg&& __arg, const _NodeGenerator& __node_gen)
159  -> typename _NodeGenerator::__node_type*
160  {
161  return __node_gen(std::forward<_Kt>(__k),
162  std::forward<_Arg>(__arg).second);
163  }
164  };
165 
166  template<>
167  struct _NodeBuilder<_Identity>
168  {
169  template<typename _Kt, typename _Arg, typename _NodeGenerator>
170  static auto
171  _S_build(_Kt&& __k, _Arg&&, const _NodeGenerator& __node_gen)
172  -> typename _NodeGenerator::__node_type*
173  { return __node_gen(std::forward<_Kt>(__k)); }
174  };
175 
176  template<typename _NodeAlloc>
177  struct _Hashtable_alloc;
178 
179  // Functor recycling a pool of nodes and using allocation once the pool is
180  // empty.
181  template<typename _NodeAlloc>
182  struct _ReuseOrAllocNode
183  {
184  private:
185  using __node_alloc_type = _NodeAlloc;
186  using __hashtable_alloc = _Hashtable_alloc<__node_alloc_type>;
187  using __node_alloc_traits =
188  typename __hashtable_alloc::__node_alloc_traits;
189 
190  public:
191  using __node_type = typename __hashtable_alloc::__node_type;
192 
193  _ReuseOrAllocNode(__node_type* __nodes, __hashtable_alloc& __h)
194  : _M_nodes(__nodes), _M_h(__h) { }
195  _ReuseOrAllocNode(const _ReuseOrAllocNode&) = delete;
196 
197  ~_ReuseOrAllocNode()
198  { _M_h._M_deallocate_nodes(_M_nodes); }
199 
200  template<typename... _Args>
201  __node_type*
202  operator()(_Args&&... __args) const
203  {
204  if (_M_nodes)
205  {
206  __node_type* __node = _M_nodes;
207  _M_nodes = _M_nodes->_M_next();
208  __node->_M_nxt = nullptr;
209  auto& __a = _M_h._M_node_allocator();
210  __node_alloc_traits::destroy(__a, __node->_M_valptr());
211  __try
212  {
213  __node_alloc_traits::construct(__a, __node->_M_valptr(),
214  std::forward<_Args>(__args)...);
215  }
216  __catch(...)
217  {
218  _M_h._M_deallocate_node_ptr(__node);
219  __throw_exception_again;
220  }
221  return __node;
222  }
223  return _M_h._M_allocate_node(std::forward<_Args>(__args)...);
224  }
225 
226  private:
227  mutable __node_type* _M_nodes;
228  __hashtable_alloc& _M_h;
229  };
230 
231  // Functor similar to the previous one but without any pool of nodes to
232  // recycle.
233  template<typename _NodeAlloc>
234  struct _AllocNode
235  {
236  private:
237  using __hashtable_alloc = _Hashtable_alloc<_NodeAlloc>;
238 
239  public:
240  using __node_type = typename __hashtable_alloc::__node_type;
241 
242  _AllocNode(__hashtable_alloc& __h)
243  : _M_h(__h) { }
244 
245  template<typename... _Args>
246  __node_type*
247  operator()(_Args&&... __args) const
248  { return _M_h._M_allocate_node(std::forward<_Args>(__args)...); }
249 
250  private:
251  __hashtable_alloc& _M_h;
252  };
253 
254  // Auxiliary types used for all instantiations of _Hashtable nodes
255  // and iterators.
256 
257  /**
258  * struct _Hashtable_traits
259  *
260  * Important traits for hash tables.
261  *
262  * @tparam _Cache_hash_code Boolean value. True if the value of
263  * the hash function is stored along with the value. This is a
264  * time-space tradeoff. Storing it may improve lookup speed by
265  * reducing the number of times we need to call the _Hash or _Equal
266  * functors.
267  *
268  * @tparam _Constant_iterators Boolean value. True if iterator and
269  * const_iterator are both constant iterator types. This is true
270  * for unordered_set and unordered_multiset, false for
271  * unordered_map and unordered_multimap.
272  *
273  * @tparam _Unique_keys Boolean value. True if the return value
274  * of _Hashtable::count(k) is always at most one, false if it may
275  * be an arbitrary number. This is true for unordered_set and
276  * unordered_map, false for unordered_multiset and
277  * unordered_multimap.
278  */
279  template<bool _Cache_hash_code, bool _Constant_iterators, bool _Unique_keys>
280  struct _Hashtable_traits
281  {
282  using __hash_cached = __bool_constant<_Cache_hash_code>;
283  using __constant_iterators = __bool_constant<_Constant_iterators>;
284  using __unique_keys = __bool_constant<_Unique_keys>;
285  };
286 
287  /**
288  * struct _Hashtable_hash_traits
289  *
290  * Important traits for hash tables depending on associated hasher.
291  *
292  */
293  template<typename _Hash>
294  struct _Hashtable_hash_traits
295  {
296  static constexpr std::size_t
297  __small_size_threshold() noexcept
298  { return std::__is_fast_hash<_Hash>::value ? 0 : 20; }
299  };
300 
301  /**
302  * struct _Hash_node_base
303  *
304  * Nodes, used to wrap elements stored in the hash table. A policy
305  * template parameter of class template _Hashtable controls whether
306  * nodes also store a hash code. In some cases (e.g. strings) this
307  * may be a performance win.
308  */
309  struct _Hash_node_base
310  {
311  _Hash_node_base* _M_nxt;
312 
313  _Hash_node_base() noexcept : _M_nxt() { }
314 
315  _Hash_node_base(_Hash_node_base* __next) noexcept : _M_nxt(__next) { }
316  };
317 
318  /**
319  * struct _Hash_node_value_base
320  *
321  * Node type with the value to store.
322  */
323  template<typename _Value>
324  struct _Hash_node_value_base
325  {
326  typedef _Value value_type;
327 
328  __gnu_cxx::__aligned_buffer<_Value> _M_storage;
329 
330  [[__gnu__::__always_inline__]]
331  _Value*
332  _M_valptr() noexcept
333  { return _M_storage._M_ptr(); }
334 
335  [[__gnu__::__always_inline__]]
336  const _Value*
337  _M_valptr() const noexcept
338  { return _M_storage._M_ptr(); }
339 
340  [[__gnu__::__always_inline__]]
341  _Value&
342  _M_v() noexcept
343  { return *_M_valptr(); }
344 
345  [[__gnu__::__always_inline__]]
346  const _Value&
347  _M_v() const noexcept
348  { return *_M_valptr(); }
349  };
350 
351  /**
352  * Primary template struct _Hash_node_code_cache.
353  */
354  template<bool _Cache_hash_code>
355  struct _Hash_node_code_cache
356  { };
357 
358  /**
359  * Specialization for node with cache, struct _Hash_node_code_cache.
360  */
361  template<>
362  struct _Hash_node_code_cache<true>
363  { std::size_t _M_hash_code; };
364 
365  template<typename _Value, bool _Cache_hash_code>
366  struct _Hash_node_value
367  : _Hash_node_value_base<_Value>
368  , _Hash_node_code_cache<_Cache_hash_code>
369  { };
370 
371  /**
372  * Primary template struct _Hash_node.
373  */
374  template<typename _Value, bool _Cache_hash_code>
375  struct _Hash_node
376  : _Hash_node_base
377  , _Hash_node_value<_Value, _Cache_hash_code>
378  {
379  _Hash_node*
380  _M_next() const noexcept
381  { return static_cast<_Hash_node*>(this->_M_nxt); }
382  };
383 
384  /// Base class for node iterators.
385  template<typename _Value, bool _Cache_hash_code>
386  struct _Node_iterator_base
387  {
388  using __node_type = _Hash_node<_Value, _Cache_hash_code>;
389 
390  __node_type* _M_cur;
391 
392  _Node_iterator_base() : _M_cur(nullptr) { }
393  _Node_iterator_base(__node_type* __p) noexcept
394  : _M_cur(__p) { }
395 
396  void
397  _M_incr() noexcept
398  { _M_cur = _M_cur->_M_next(); }
399 
400  friend bool
401  operator==(const _Node_iterator_base& __x, const _Node_iterator_base& __y)
402  noexcept
403  { return __x._M_cur == __y._M_cur; }
404 
405 #if __cpp_impl_three_way_comparison < 201907L
406  friend bool
407  operator!=(const _Node_iterator_base& __x, const _Node_iterator_base& __y)
408  noexcept
409  { return __x._M_cur != __y._M_cur; }
410 #endif
411  };
412 
413  /// Node iterators, used to iterate through all the hashtable.
414  template<typename _Value, bool __constant_iterators, bool __cache>
415  struct _Node_iterator
416  : public _Node_iterator_base<_Value, __cache>
417  {
418  private:
419  using __base_type = _Node_iterator_base<_Value, __cache>;
420  using __node_type = typename __base_type::__node_type;
421 
422  public:
423  using value_type = _Value;
424  using difference_type = std::ptrdiff_t;
425  using iterator_category = std::forward_iterator_tag;
426 
427  using pointer = __conditional_t<__constant_iterators,
428  const value_type*, value_type*>;
429 
430  using reference = __conditional_t<__constant_iterators,
431  const value_type&, value_type&>;
432 
433  _Node_iterator() = default;
434 
435  explicit
436  _Node_iterator(__node_type* __p) noexcept
437  : __base_type(__p) { }
438 
439  reference
440  operator*() const noexcept
441  { return this->_M_cur->_M_v(); }
442 
443  pointer
444  operator->() const noexcept
445  { return this->_M_cur->_M_valptr(); }
446 
447  _Node_iterator&
448  operator++() noexcept
449  {
450  this->_M_incr();
451  return *this;
452  }
453 
454  _Node_iterator
455  operator++(int) noexcept
456  {
457  _Node_iterator __tmp(*this);
458  this->_M_incr();
459  return __tmp;
460  }
461  };
462 
463  /// Node const_iterators, used to iterate through all the hashtable.
464  template<typename _Value, bool __constant_iterators, bool __cache>
465  struct _Node_const_iterator
466  : public _Node_iterator_base<_Value, __cache>
467  {
468  private:
469  using __base_type = _Node_iterator_base<_Value, __cache>;
470  using __node_type = typename __base_type::__node_type;
471 
472  public:
473  typedef _Value value_type;
474  typedef std::ptrdiff_t difference_type;
475  typedef std::forward_iterator_tag iterator_category;
476 
477  typedef const value_type* pointer;
478  typedef const value_type& reference;
479 
480  _Node_const_iterator() = default;
481 
482  explicit
483  _Node_const_iterator(__node_type* __p) noexcept
484  : __base_type(__p) { }
485 
486  _Node_const_iterator(const _Node_iterator<_Value, __constant_iterators,
487  __cache>& __x) noexcept
488  : __base_type(__x._M_cur) { }
489 
490  reference
491  operator*() const noexcept
492  { return this->_M_cur->_M_v(); }
493 
494  pointer
495  operator->() const noexcept
496  { return this->_M_cur->_M_valptr(); }
497 
498  _Node_const_iterator&
499  operator++() noexcept
500  {
501  this->_M_incr();
502  return *this;
503  }
504 
505  _Node_const_iterator
506  operator++(int) noexcept
507  {
508  _Node_const_iterator __tmp(*this);
509  this->_M_incr();
510  return __tmp;
511  }
512  };
513 
514  // Many of class template _Hashtable's template parameters are policy
515  // classes. These are defaults for the policies.
516 
517  /// Default range hashing function: use division to fold a large number
518  /// into the range [0, N).
519  struct _Mod_range_hashing
520  {
521  typedef std::size_t first_argument_type;
522  typedef std::size_t second_argument_type;
523  typedef std::size_t result_type;
524 
525  result_type
526  operator()(first_argument_type __num,
527  second_argument_type __den) const noexcept
528  { return __num % __den; }
529  };
530 
531  /// Default ranged hash function H. In principle it should be a
532  /// function object composed from objects of type H1 and H2 such that
533  /// h(k, N) = h2(h1(k), N), but that would mean making extra copies of
534  /// h1 and h2. So instead we'll just use a tag to tell class template
535  /// hashtable to do that composition.
536  struct _Default_ranged_hash { };
537 
538  /// Default value for rehash policy. Bucket size is (usually) the
539  /// smallest prime that keeps the load factor small enough.
540  struct _Prime_rehash_policy
541  {
542  using __has_load_factor = true_type;
543 
544  _Prime_rehash_policy(float __z = 1.0) noexcept
545  : _M_max_load_factor(__z), _M_next_resize(0) { }
546 
547  float
548  max_load_factor() const noexcept
549  { return _M_max_load_factor; }
550 
551  // Return a bucket size no smaller than n.
552  std::size_t
553  _M_next_bkt(std::size_t __n) const;
554 
555  // Return a bucket count appropriate for n elements
556  std::size_t
557  _M_bkt_for_elements(std::size_t __n) const
558  { return __builtin_ceil(__n / (double)_M_max_load_factor); }
559 
560  // __n_bkt is current bucket count, __n_elt is current element count,
561  // and __n_ins is number of elements to be inserted. Do we need to
562  // increase bucket count? If so, return make_pair(true, n), where n
563  // is the new bucket count. If not, return make_pair(false, 0).
565  _M_need_rehash(std::size_t __n_bkt, std::size_t __n_elt,
566  std::size_t __n_ins) const;
567 
568  typedef std::size_t _State;
569 
570  _State
571  _M_state() const
572  { return _M_next_resize; }
573 
574  void
575  _M_reset() noexcept
576  { _M_next_resize = 0; }
577 
578  void
579  _M_reset(_State __state)
580  { _M_next_resize = __state; }
581 
582  static const std::size_t _S_growth_factor = 2;
583 
584  float _M_max_load_factor;
585  mutable std::size_t _M_next_resize;
586  };
587 
588  /// Range hashing function assuming that second arg is a power of 2.
589  struct _Mask_range_hashing
590  {
591  typedef std::size_t first_argument_type;
592  typedef std::size_t second_argument_type;
593  typedef std::size_t result_type;
594 
595  result_type
596  operator()(first_argument_type __num,
597  second_argument_type __den) const noexcept
598  { return __num & (__den - 1); }
599  };
600 
601  /// Compute closest power of 2 not less than __n
602  inline std::size_t
603  __clp2(std::size_t __n) noexcept
604  {
606  // Equivalent to return __n ? std::bit_ceil(__n) : 0;
607  if (__n < 2)
608  return __n;
609  const unsigned __lz = sizeof(size_t) > sizeof(long)
610  ? __builtin_clzll(__n - 1ull)
611  : __builtin_clzl(__n - 1ul);
612  // Doing two shifts avoids undefined behaviour when __lz == 0.
613  return (size_t(1) << (__int_traits<size_t>::__digits - __lz - 1)) << 1;
614  }
615 
616  /// Rehash policy providing power of 2 bucket numbers. Avoids modulo
617  /// operations.
618  struct _Power2_rehash_policy
619  {
620  using __has_load_factor = true_type;
621 
622  _Power2_rehash_policy(float __z = 1.0) noexcept
623  : _M_max_load_factor(__z), _M_next_resize(0) { }
624 
625  float
626  max_load_factor() const noexcept
627  { return _M_max_load_factor; }
628 
629  // Return a bucket size no smaller than n (as long as n is not above the
630  // highest power of 2).
631  std::size_t
632  _M_next_bkt(std::size_t __n) noexcept
633  {
634  if (__n == 0)
635  // Special case on container 1st initialization with 0 bucket count
636  // hint. We keep _M_next_resize to 0 to make sure that next time we
637  // want to add an element allocation will take place.
638  return 1;
639 
640  const auto __max_width = std::min<size_t>(sizeof(size_t), 8);
641  const auto __max_bkt = size_t(1) << (__max_width * __CHAR_BIT__ - 1);
642  std::size_t __res = __clp2(__n);
643 
644  if (__res == 0)
645  __res = __max_bkt;
646  else if (__res == 1)
647  // If __res is 1 we force it to 2 to make sure there will be an
648  // allocation so that nothing need to be stored in the initial
649  // single bucket
650  __res = 2;
651 
652  if (__res == __max_bkt)
653  // Set next resize to the max value so that we never try to rehash again
654  // as we already reach the biggest possible bucket number.
655  // Note that it might result in max_load_factor not being respected.
656  _M_next_resize = size_t(-1);
657  else
658  _M_next_resize
659  = __builtin_floor(__res * (double)_M_max_load_factor);
660 
661  return __res;
662  }
663 
664  // Return a bucket count appropriate for n elements
665  std::size_t
666  _M_bkt_for_elements(std::size_t __n) const noexcept
667  { return __builtin_ceil(__n / (double)_M_max_load_factor); }
668 
669  // __n_bkt is current bucket count, __n_elt is current element count,
670  // and __n_ins is number of elements to be inserted. Do we need to
671  // increase bucket count? If so, return make_pair(true, n), where n
672  // is the new bucket count. If not, return make_pair(false, 0).
674  _M_need_rehash(std::size_t __n_bkt, std::size_t __n_elt,
675  std::size_t __n_ins) noexcept
676  {
677  if (__n_elt + __n_ins > _M_next_resize)
678  {
679  // If _M_next_resize is 0 it means that we have nothing allocated so
680  // far and that we start inserting elements. In this case we start
681  // with an initial bucket size of 11.
682  double __min_bkts
683  = std::max<std::size_t>(__n_elt + __n_ins, _M_next_resize ? 0 : 11)
684  / (double)_M_max_load_factor;
685  if (__min_bkts >= __n_bkt)
686  return { true,
687  _M_next_bkt(std::max<std::size_t>(__builtin_floor(__min_bkts) + 1,
688  __n_bkt * _S_growth_factor)) };
689 
690  _M_next_resize
691  = __builtin_floor(__n_bkt * (double)_M_max_load_factor);
692  return { false, 0 };
693  }
694  else
695  return { false, 0 };
696  }
697 
698  typedef std::size_t _State;
699 
700  _State
701  _M_state() const noexcept
702  { return _M_next_resize; }
703 
704  void
705  _M_reset() noexcept
706  { _M_next_resize = 0; }
707 
708  void
709  _M_reset(_State __state) noexcept
710  { _M_next_resize = __state; }
711 
712  static const std::size_t _S_growth_factor = 2;
713 
714  float _M_max_load_factor;
715  std::size_t _M_next_resize;
716  };
717 
718  // Base classes for std::_Hashtable. We define these base classes
719  // because in some cases we want to do different things depending on
720  // the value of a policy class. In some cases the policy class
721  // affects which member functions and nested typedefs are defined;
722  // we handle that by specializing base class templates. Several of
723  // the base class templates need to access other members of class
724  // template _Hashtable, so we use a variant of the "Curiously
725  // Recurring Template Pattern" (CRTP) technique.
726 
727  /**
728  * Primary class template _Map_base.
729  *
730  * If the hashtable has a value type of the form pair<const T1, T2> and
731  * a key extraction policy (_ExtractKey) that returns the first part
732  * of the pair, the hashtable gets a mapped_type typedef. If it
733  * satisfies those criteria and also has unique keys, then it also
734  * gets an operator[].
735  */
736  template<typename _Key, typename _Value, typename _Alloc,
737  typename _ExtractKey, typename _Equal,
738  typename _Hash, typename _RangeHash, typename _Unused,
739  typename _RehashPolicy, typename _Traits,
740  bool _Unique_keys = _Traits::__unique_keys::value>
741  struct _Map_base { };
742 
743  /// Partial specialization, __unique_keys set to false, std::pair value type.
744  template<typename _Key, typename _Val, typename _Alloc, typename _Equal,
745  typename _Hash, typename _RangeHash, typename _Unused,
746  typename _RehashPolicy, typename _Traits>
747  struct _Map_base<_Key, pair<const _Key, _Val>, _Alloc, _Select1st, _Equal,
748  _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits, false>
749  {
750  using mapped_type = _Val;
751  };
752 
753  /// Partial specialization, __unique_keys set to true.
754  template<typename _Key, typename _Val, typename _Alloc, typename _Equal,
755  typename _Hash, typename _RangeHash, typename _Unused,
756  typename _RehashPolicy, typename _Traits>
757  struct _Map_base<_Key, pair<const _Key, _Val>, _Alloc, _Select1st, _Equal,
758  _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits, true>
759  {
760  private:
761  using __hashtable_base = _Hashtable_base<_Key, pair<const _Key, _Val>,
762  _Select1st, _Equal, _Hash,
763  _RangeHash, _Unused,
764  _Traits>;
765 
766  using __hashtable = _Hashtable<_Key, pair<const _Key, _Val>, _Alloc,
767  _Select1st, _Equal, _Hash, _RangeHash,
768  _Unused, _RehashPolicy, _Traits>;
769 
770  using __hash_code = typename __hashtable_base::__hash_code;
771 
772  public:
773  using key_type = typename __hashtable_base::key_type;
774  using mapped_type = _Val;
775 
776  mapped_type&
777  operator[](const key_type& __k);
778 
779  mapped_type&
780  operator[](key_type&& __k);
781 
782  // _GLIBCXX_RESOLVE_LIB_DEFECTS
783  // DR 761. unordered_map needs an at() member function.
784  mapped_type&
785  at(const key_type& __k)
786  {
787  auto __ite = static_cast<__hashtable*>(this)->find(__k);
788  if (!__ite._M_cur)
789  __throw_out_of_range(__N("unordered_map::at"));
790  return __ite->second;
791  }
792 
793  const mapped_type&
794  at(const key_type& __k) const
795  {
796  auto __ite = static_cast<const __hashtable*>(this)->find(__k);
797  if (!__ite._M_cur)
798  __throw_out_of_range(__N("unordered_map::at"));
799  return __ite->second;
800  }
801  };
802 
803  template<typename _Key, typename _Val, typename _Alloc, typename _Equal,
804  typename _Hash, typename _RangeHash, typename _Unused,
805  typename _RehashPolicy, typename _Traits>
806  auto
807  _Map_base<_Key, pair<const _Key, _Val>, _Alloc, _Select1st, _Equal,
808  _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits, true>::
809  operator[](const key_type& __k)
810  -> mapped_type&
811  {
812  __hashtable* __h = static_cast<__hashtable*>(this);
813  __hash_code __code = __h->_M_hash_code(__k);
814  std::size_t __bkt = __h->_M_bucket_index(__code);
815  if (auto __node = __h->_M_find_node(__bkt, __k, __code))
816  return __node->_M_v().second;
817 
818  typename __hashtable::_Scoped_node __node {
819  __h,
822  std::tuple<>()
823  };
824  auto __pos
825  = __h->_M_insert_unique_node(__bkt, __code, __node._M_node);
826  __node._M_node = nullptr;
827  return __pos->second;
828  }
829 
830  template<typename _Key, typename _Val, typename _Alloc, typename _Equal,
831  typename _Hash, typename _RangeHash, typename _Unused,
832  typename _RehashPolicy, typename _Traits>
833  auto
834  _Map_base<_Key, pair<const _Key, _Val>, _Alloc, _Select1st, _Equal,
835  _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits, true>::
836  operator[](key_type&& __k)
837  -> mapped_type&
838  {
839  __hashtable* __h = static_cast<__hashtable*>(this);
840  __hash_code __code = __h->_M_hash_code(__k);
841  std::size_t __bkt = __h->_M_bucket_index(__code);
842  if (auto __node = __h->_M_find_node(__bkt, __k, __code))
843  return __node->_M_v().second;
844 
845  typename __hashtable::_Scoped_node __node {
846  __h,
849  std::tuple<>()
850  };
851  auto __pos
852  = __h->_M_insert_unique_node(__bkt, __code, __node._M_node);
853  __node._M_node = nullptr;
854  return __pos->second;
855  }
856 
857  // Partial specialization for unordered_map<const T, U>, see PR 104174.
858  template<typename _Key, typename _Val, typename _Alloc, typename _Equal,
859  typename _Hash, typename _RangeHash, typename _Unused,
860  typename _RehashPolicy, typename _Traits, bool __uniq>
861  struct _Map_base<const _Key, pair<const _Key, _Val>,
862  _Alloc, _Select1st, _Equal, _Hash,
863  _RangeHash, _Unused, _RehashPolicy, _Traits, __uniq>
864  : _Map_base<_Key, pair<const _Key, _Val>, _Alloc, _Select1st, _Equal, _Hash,
865  _RangeHash, _Unused, _RehashPolicy, _Traits, __uniq>
866  { };
867 
868  /**
869  * Primary class template _Insert_base.
870  *
871  * Defines @c insert member functions appropriate to all _Hashtables.
872  */
873  template<typename _Key, typename _Value, typename _Alloc,
874  typename _ExtractKey, typename _Equal,
875  typename _Hash, typename _RangeHash, typename _Unused,
876  typename _RehashPolicy, typename _Traits>
877  struct _Insert_base
878  {
879  protected:
880  using __hashtable_base = _Hashtable_base<_Key, _Value, _ExtractKey,
881  _Equal, _Hash, _RangeHash,
882  _Unused, _Traits>;
883 
884  using __hashtable = _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
885  _Hash, _RangeHash,
886  _Unused, _RehashPolicy, _Traits>;
887 
888  using __hash_cached = typename _Traits::__hash_cached;
889  using __constant_iterators = typename _Traits::__constant_iterators;
890 
891  using __hashtable_alloc = _Hashtable_alloc<
892  __alloc_rebind<_Alloc, _Hash_node<_Value,
893  __hash_cached::value>>>;
894 
895  using value_type = typename __hashtable_base::value_type;
896  using size_type = typename __hashtable_base::size_type;
897 
898  using __unique_keys = typename _Traits::__unique_keys;
899  using __node_alloc_type = typename __hashtable_alloc::__node_alloc_type;
900  using __node_gen_type = _AllocNode<__node_alloc_type>;
901 
902  __hashtable&
903  _M_conjure_hashtable()
904  { return *(static_cast<__hashtable*>(this)); }
905 
906  template<typename _InputIterator, typename _NodeGetter>
907  void
908  _M_insert_range(_InputIterator __first, _InputIterator __last,
909  const _NodeGetter&, true_type __uks);
910 
911  template<typename _InputIterator, typename _NodeGetter>
912  void
913  _M_insert_range(_InputIterator __first, _InputIterator __last,
914  const _NodeGetter&, false_type __uks);
915 
916  public:
917  using iterator = _Node_iterator<_Value, __constant_iterators::value,
918  __hash_cached::value>;
919 
920  using const_iterator = _Node_const_iterator<_Value,
921  __constant_iterators::value,
922  __hash_cached::value>;
923 
924  using __ireturn_type = __conditional_t<__unique_keys::value,
926  iterator>;
927 
928  __ireturn_type
929  insert(const value_type& __v)
930  {
931  __hashtable& __h = _M_conjure_hashtable();
932  __node_gen_type __node_gen(__h);
933  return __h._M_insert(__v, __node_gen, __unique_keys{});
934  }
935 
936  iterator
937  insert(const_iterator __hint, const value_type& __v)
938  {
939  __hashtable& __h = _M_conjure_hashtable();
940  __node_gen_type __node_gen(__h);
941  return __h._M_insert(__hint, __v, __node_gen, __unique_keys{});
942  }
943 
944  template<typename _KType, typename... _Args>
946  try_emplace(const_iterator, _KType&& __k, _Args&&... __args)
947  {
948  __hashtable& __h = _M_conjure_hashtable();
949  auto __code = __h._M_hash_code(__k);
950  std::size_t __bkt = __h._M_bucket_index(__code);
951  if (auto __node = __h._M_find_node(__bkt, __k, __code))
952  return { iterator(__node), false };
953 
954  typename __hashtable::_Scoped_node __node {
955  &__h,
957  std::forward_as_tuple(std::forward<_KType>(__k)),
958  std::forward_as_tuple(std::forward<_Args>(__args)...)
959  };
960  auto __it
961  = __h._M_insert_unique_node(__bkt, __code, __node._M_node);
962  __node._M_node = nullptr;
963  return { __it, true };
964  }
965 
966  void
967  insert(initializer_list<value_type> __l)
968  { this->insert(__l.begin(), __l.end()); }
969 
970  template<typename _InputIterator>
971  void
972  insert(_InputIterator __first, _InputIterator __last)
973  {
974  __hashtable& __h = _M_conjure_hashtable();
975  __node_gen_type __node_gen(__h);
976  return _M_insert_range(__first, __last, __node_gen, __unique_keys{});
977  }
978  };
979 
980  template<typename _Key, typename _Value, typename _Alloc,
981  typename _ExtractKey, typename _Equal,
982  typename _Hash, typename _RangeHash, typename _Unused,
983  typename _RehashPolicy, typename _Traits>
984  template<typename _InputIterator, typename _NodeGetter>
985  void
986  _Insert_base<_Key, _Value, _Alloc, _ExtractKey, _Equal,
987  _Hash, _RangeHash, _Unused,
988  _RehashPolicy, _Traits>::
989  _M_insert_range(_InputIterator __first, _InputIterator __last,
990  const _NodeGetter& __node_gen, true_type __uks)
991  {
992  __hashtable& __h = _M_conjure_hashtable();
993  for (; __first != __last; ++__first)
994  __h._M_insert(*__first, __node_gen, __uks);
995  }
996 
997  template<typename _Key, typename _Value, typename _Alloc,
998  typename _ExtractKey, typename _Equal,
999  typename _Hash, typename _RangeHash, typename _Unused,
1000  typename _RehashPolicy, typename _Traits>
1001  template<typename _InputIterator, typename _NodeGetter>
1002  void
1003  _Insert_base<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1004  _Hash, _RangeHash, _Unused,
1005  _RehashPolicy, _Traits>::
1006  _M_insert_range(_InputIterator __first, _InputIterator __last,
1007  const _NodeGetter& __node_gen, false_type __uks)
1008  {
1009  using __rehash_type = typename __hashtable::__rehash_type;
1010  using __rehash_state = typename __hashtable::__rehash_state;
1011  using pair_type = std::pair<bool, std::size_t>;
1012 
1013  size_type __n_elt = __detail::__distance_fw(__first, __last);
1014  if (__n_elt == 0)
1015  return;
1016 
1017  __hashtable& __h = _M_conjure_hashtable();
1018  __rehash_type& __rehash = __h._M_rehash_policy;
1019  const __rehash_state& __saved_state = __rehash._M_state();
1020  pair_type __do_rehash = __rehash._M_need_rehash(__h._M_bucket_count,
1021  __h._M_element_count,
1022  __n_elt);
1023 
1024  if (__do_rehash.first)
1025  __h._M_rehash(__do_rehash.second, __saved_state);
1026 
1027  for (; __first != __last; ++__first)
1028  __h._M_insert(*__first, __node_gen, __uks);
1029  }
1030 
1031  /**
1032  * Primary class template _Insert.
1033  *
1034  * Defines @c insert member functions that depend on _Hashtable policies,
1035  * via partial specializations.
1036  */
1037  template<typename _Key, typename _Value, typename _Alloc,
1038  typename _ExtractKey, typename _Equal,
1039  typename _Hash, typename _RangeHash, typename _Unused,
1040  typename _RehashPolicy, typename _Traits,
1041  bool _Constant_iterators = _Traits::__constant_iterators::value>
1042  struct _Insert;
1043 
1044  /// Specialization.
1045  template<typename _Key, typename _Value, typename _Alloc,
1046  typename _ExtractKey, typename _Equal,
1047  typename _Hash, typename _RangeHash, typename _Unused,
1048  typename _RehashPolicy, typename _Traits>
1049  struct _Insert<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1050  _Hash, _RangeHash, _Unused,
1051  _RehashPolicy, _Traits, true>
1052  : public _Insert_base<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1053  _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>
1054  {
1055  using __base_type = _Insert_base<_Key, _Value, _Alloc, _ExtractKey,
1056  _Equal, _Hash, _RangeHash, _Unused,
1057  _RehashPolicy, _Traits>;
1058 
1059  using value_type = typename __base_type::value_type;
1060  using iterator = typename __base_type::iterator;
1061  using const_iterator = typename __base_type::const_iterator;
1062  using __ireturn_type = typename __base_type::__ireturn_type;
1063 
1064  using __unique_keys = typename __base_type::__unique_keys;
1065  using __hashtable = typename __base_type::__hashtable;
1066  using __node_gen_type = typename __base_type::__node_gen_type;
1067 
1068  using __base_type::insert;
1069 
1070  __ireturn_type
1071  insert(value_type&& __v)
1072  {
1073  __hashtable& __h = this->_M_conjure_hashtable();
1074  __node_gen_type __node_gen(__h);
1075  return __h._M_insert(std::move(__v), __node_gen, __unique_keys{});
1076  }
1077 
1078  iterator
1079  insert(const_iterator __hint, value_type&& __v)
1080  {
1081  __hashtable& __h = this->_M_conjure_hashtable();
1082  __node_gen_type __node_gen(__h);
1083  return __h._M_insert(__hint, std::move(__v), __node_gen,
1084  __unique_keys{});
1085  }
1086  };
1087 
1088  /// Specialization.
1089  template<typename _Key, typename _Value, typename _Alloc,
1090  typename _ExtractKey, typename _Equal,
1091  typename _Hash, typename _RangeHash, typename _Unused,
1092  typename _RehashPolicy, typename _Traits>
1093  struct _Insert<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1094  _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits, false>
1095  : public _Insert_base<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1096  _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>
1097  {
1098  using __base_type = _Insert_base<_Key, _Value, _Alloc, _ExtractKey,
1099  _Equal, _Hash, _RangeHash, _Unused,
1100  _RehashPolicy, _Traits>;
1101  using value_type = typename __base_type::value_type;
1102  using iterator = typename __base_type::iterator;
1103  using const_iterator = typename __base_type::const_iterator;
1104 
1105  using __unique_keys = typename __base_type::__unique_keys;
1106  using __hashtable = typename __base_type::__hashtable;
1107  using __ireturn_type = typename __base_type::__ireturn_type;
1108 
1109  using __base_type::insert;
1110 
1111  template<typename _Pair>
1113 
1114  template<typename _Pair>
1115  using _IFcons = std::enable_if<__is_cons<_Pair>::value>;
1116 
1117  template<typename _Pair>
1118  using _IFconsp = typename _IFcons<_Pair>::type;
1119 
1120  template<typename _Pair, typename = _IFconsp<_Pair>>
1121  __ireturn_type
1122  insert(_Pair&& __v)
1123  {
1124  __hashtable& __h = this->_M_conjure_hashtable();
1125  return __h._M_emplace(__unique_keys{}, std::forward<_Pair>(__v));
1126  }
1127 
1128  template<typename _Pair, typename = _IFconsp<_Pair>>
1129  iterator
1130  insert(const_iterator __hint, _Pair&& __v)
1131  {
1132  __hashtable& __h = this->_M_conjure_hashtable();
1133  return __h._M_emplace(__hint, __unique_keys{},
1134  std::forward<_Pair>(__v));
1135  }
1136  };
1137 
1138  template<typename _Policy>
1139  using __has_load_factor = typename _Policy::__has_load_factor;
1140 
1141  /**
1142  * Primary class template _Rehash_base.
1143  *
1144  * Give hashtable the max_load_factor functions and reserve iff the
1145  * rehash policy supports it.
1146  */
1147  template<typename _Key, typename _Value, typename _Alloc,
1148  typename _ExtractKey, typename _Equal,
1149  typename _Hash, typename _RangeHash, typename _Unused,
1150  typename _RehashPolicy, typename _Traits,
1151  typename =
1152  __detected_or_t<false_type, __has_load_factor, _RehashPolicy>>
1153  struct _Rehash_base;
1154 
1155  /// Specialization when rehash policy doesn't provide load factor management.
1156  template<typename _Key, typename _Value, typename _Alloc,
1157  typename _ExtractKey, typename _Equal,
1158  typename _Hash, typename _RangeHash, typename _Unused,
1159  typename _RehashPolicy, typename _Traits>
1160  struct _Rehash_base<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1161  _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits,
1162  false_type /* Has load factor */>
1163  {
1164  };
1165 
1166  /// Specialization when rehash policy provide load factor management.
1167  template<typename _Key, typename _Value, typename _Alloc,
1168  typename _ExtractKey, typename _Equal,
1169  typename _Hash, typename _RangeHash, typename _Unused,
1170  typename _RehashPolicy, typename _Traits>
1171  struct _Rehash_base<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1172  _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits,
1173  true_type /* Has load factor */>
1174  {
1175  private:
1176  using __hashtable = _Hashtable<_Key, _Value, _Alloc, _ExtractKey,
1177  _Equal, _Hash, _RangeHash, _Unused,
1178  _RehashPolicy, _Traits>;
1179 
1180  public:
1181  float
1182  max_load_factor() const noexcept
1183  {
1184  const __hashtable* __this = static_cast<const __hashtable*>(this);
1185  return __this->__rehash_policy().max_load_factor();
1186  }
1187 
1188  void
1189  max_load_factor(float __z)
1190  {
1191  __hashtable* __this = static_cast<__hashtable*>(this);
1192  __this->__rehash_policy(_RehashPolicy(__z));
1193  }
1194 
1195  void
1196  reserve(std::size_t __n)
1197  {
1198  __hashtable* __this = static_cast<__hashtable*>(this);
1199  __this->rehash(__this->__rehash_policy()._M_bkt_for_elements(__n));
1200  }
1201  };
1202 
1203  /**
1204  * Primary class template _Hashtable_ebo_helper.
1205  *
1206  * Helper class using EBO when it is not forbidden (the type is not
1207  * final) and when it is worth it (the type is empty.)
1208  */
1209  template<int _Nm, typename _Tp,
1210  bool __use_ebo = !__is_final(_Tp) && __is_empty(_Tp)>
1211  struct _Hashtable_ebo_helper;
1212 
1213  /// Specialization using EBO.
1214  template<int _Nm, typename _Tp>
1215  struct _Hashtable_ebo_helper<_Nm, _Tp, true>
1216  : private _Tp
1217  {
1218  _Hashtable_ebo_helper() noexcept(noexcept(_Tp())) : _Tp() { }
1219 
1220  template<typename _OtherTp>
1221  _Hashtable_ebo_helper(_OtherTp&& __tp)
1222  : _Tp(std::forward<_OtherTp>(__tp))
1223  { }
1224 
1225  const _Tp& _M_cget() const { return static_cast<const _Tp&>(*this); }
1226  _Tp& _M_get() { return static_cast<_Tp&>(*this); }
1227  };
1228 
1229  /// Specialization not using EBO.
1230  template<int _Nm, typename _Tp>
1231  struct _Hashtable_ebo_helper<_Nm, _Tp, false>
1232  {
1233  _Hashtable_ebo_helper() = default;
1234 
1235  template<typename _OtherTp>
1236  _Hashtable_ebo_helper(_OtherTp&& __tp)
1237  : _M_tp(std::forward<_OtherTp>(__tp))
1238  { }
1239 
1240  const _Tp& _M_cget() const { return _M_tp; }
1241  _Tp& _M_get() { return _M_tp; }
1242 
1243  private:
1244  _Tp _M_tp{};
1245  };
1246 
1247  /**
1248  * Primary class template _Local_iterator_base.
1249  *
1250  * Base class for local iterators, used to iterate within a bucket
1251  * but not between buckets.
1252  */
1253  template<typename _Key, typename _Value, typename _ExtractKey,
1254  typename _Hash, typename _RangeHash, typename _Unused,
1255  bool __cache_hash_code>
1256  struct _Local_iterator_base;
1257 
1258  /**
1259  * Primary class template _Hash_code_base.
1260  *
1261  * Encapsulates two policy issues that aren't quite orthogonal.
1262  * (1) the difference between using a ranged hash function and using
1263  * the combination of a hash function and a range-hashing function.
1264  * In the former case we don't have such things as hash codes, so
1265  * we have a dummy type as placeholder.
1266  * (2) Whether or not we cache hash codes. Caching hash codes is
1267  * meaningless if we have a ranged hash function.
1268  *
1269  * We also put the key extraction objects here, for convenience.
1270  * Each specialization derives from one or more of the template
1271  * parameters to benefit from Ebo. This is important as this type
1272  * is inherited in some cases by the _Local_iterator_base type used
1273  * to implement local_iterator and const_local_iterator. As with
1274  * any iterator type we prefer to make it as small as possible.
1275  */
1276  template<typename _Key, typename _Value, typename _ExtractKey,
1277  typename _Hash, typename _RangeHash, typename _Unused,
1278  bool __cache_hash_code>
1279  struct _Hash_code_base
1280  : private _Hashtable_ebo_helper<1, _Hash>
1281  {
1282  private:
1283  using __ebo_hash = _Hashtable_ebo_helper<1, _Hash>;
1284 
1285  // Gives the local iterator implementation access to _M_bucket_index().
1286  friend struct _Local_iterator_base<_Key, _Value, _ExtractKey,
1287  _Hash, _RangeHash, _Unused, false>;
1288 
1289  public:
1290  typedef _Hash hasher;
1291 
1292  hasher
1293  hash_function() const
1294  { return _M_hash(); }
1295 
1296  protected:
1297  typedef std::size_t __hash_code;
1298 
1299  // We need the default constructor for the local iterators and _Hashtable
1300  // default constructor.
1301  _Hash_code_base() = default;
1302 
1303  _Hash_code_base(const _Hash& __hash) : __ebo_hash(__hash) { }
1304 
1305  __hash_code
1306  _M_hash_code(const _Key& __k) const
1307  {
1308  static_assert(__is_invocable<const _Hash&, const _Key&>{},
1309  "hash function must be invocable with an argument of key type");
1310  return _M_hash()(__k);
1311  }
1312 
1313  template<typename _Kt>
1314  __hash_code
1315  _M_hash_code_tr(const _Kt& __k) const
1316  {
1317  static_assert(__is_invocable<const _Hash&, const _Kt&>{},
1318  "hash function must be invocable with an argument of key type");
1319  return _M_hash()(__k);
1320  }
1321 
1322  __hash_code
1323  _M_hash_code(const _Hash_node_value<_Value, false>& __n) const
1324  { return _M_hash_code(_ExtractKey{}(__n._M_v())); }
1325 
1326  __hash_code
1327  _M_hash_code(const _Hash_node_value<_Value, true>& __n) const
1328  { return __n._M_hash_code; }
1329 
1330  std::size_t
1331  _M_bucket_index(__hash_code __c, std::size_t __bkt_count) const
1332  { return _RangeHash{}(__c, __bkt_count); }
1333 
1334  std::size_t
1335  _M_bucket_index(const _Hash_node_value<_Value, false>& __n,
1336  std::size_t __bkt_count) const
1337  noexcept( noexcept(declval<const _Hash&>()(declval<const _Key&>()))
1338  && noexcept(declval<const _RangeHash&>()((__hash_code)0,
1339  (std::size_t)0)) )
1340  {
1341  return _RangeHash{}(_M_hash_code(_ExtractKey{}(__n._M_v())),
1342  __bkt_count);
1343  }
1344 
1345  std::size_t
1346  _M_bucket_index(const _Hash_node_value<_Value, true>& __n,
1347  std::size_t __bkt_count) const
1348  noexcept( noexcept(declval<const _RangeHash&>()((__hash_code)0,
1349  (std::size_t)0)) )
1350  { return _RangeHash{}(__n._M_hash_code, __bkt_count); }
1351 
1352  void
1353  _M_store_code(_Hash_node_code_cache<false>&, __hash_code) const
1354  { }
1355 
1356  void
1357  _M_copy_code(_Hash_node_code_cache<false>&,
1358  const _Hash_node_code_cache<false>&) const
1359  { }
1360 
1361  void
1362  _M_store_code(_Hash_node_code_cache<true>& __n, __hash_code __c) const
1363  { __n._M_hash_code = __c; }
1364 
1365  void
1366  _M_copy_code(_Hash_node_code_cache<true>& __to,
1367  const _Hash_node_code_cache<true>& __from) const
1368  { __to._M_hash_code = __from._M_hash_code; }
1369 
1370  void
1371  _M_swap(_Hash_code_base& __x)
1372  { std::swap(__ebo_hash::_M_get(), __x.__ebo_hash::_M_get()); }
1373 
1374  const _Hash&
1375  _M_hash() const { return __ebo_hash::_M_cget(); }
1376  };
1377 
1378  /// Partial specialization used when nodes contain a cached hash code.
1379  template<typename _Key, typename _Value, typename _ExtractKey,
1380  typename _Hash, typename _RangeHash, typename _Unused>
1381  struct _Local_iterator_base<_Key, _Value, _ExtractKey,
1382  _Hash, _RangeHash, _Unused, true>
1383  : public _Node_iterator_base<_Value, true>
1384  {
1385  protected:
1386  using __base_node_iter = _Node_iterator_base<_Value, true>;
1387  using __hash_code_base = _Hash_code_base<_Key, _Value, _ExtractKey,
1388  _Hash, _RangeHash, _Unused, true>;
1389 
1390  _Local_iterator_base() = default;
1391  _Local_iterator_base(const __hash_code_base&,
1392  _Hash_node<_Value, true>* __p,
1393  std::size_t __bkt, std::size_t __bkt_count)
1394  : __base_node_iter(__p), _M_bucket(__bkt), _M_bucket_count(__bkt_count)
1395  { }
1396 
1397  void
1398  _M_incr()
1399  {
1400  __base_node_iter::_M_incr();
1401  if (this->_M_cur)
1402  {
1403  std::size_t __bkt
1404  = _RangeHash{}(this->_M_cur->_M_hash_code, _M_bucket_count);
1405  if (__bkt != _M_bucket)
1406  this->_M_cur = nullptr;
1407  }
1408  }
1409 
1410  std::size_t _M_bucket;
1411  std::size_t _M_bucket_count;
1412 
1413  public:
1414  std::size_t
1415  _M_get_bucket() const { return _M_bucket; } // for debug mode
1416  };
1417 
1418  // Uninitialized storage for a _Hash_code_base.
1419  // This type is DefaultConstructible and Assignable even if the
1420  // _Hash_code_base type isn't, so that _Local_iterator_base<..., false>
1421  // can be DefaultConstructible and Assignable.
1422  template<typename _Tp, bool _IsEmpty = std::is_empty<_Tp>::value>
1423  struct _Hash_code_storage
1424  {
1425  __gnu_cxx::__aligned_buffer<_Tp> _M_storage;
1426 
1427  _Tp*
1428  _M_h() { return _M_storage._M_ptr(); }
1429 
1430  const _Tp*
1431  _M_h() const { return _M_storage._M_ptr(); }
1432  };
1433 
1434  // Empty partial specialization for empty _Hash_code_base types.
1435  template<typename _Tp>
1436  struct _Hash_code_storage<_Tp, true>
1437  {
1438  static_assert( std::is_empty<_Tp>::value, "Type must be empty" );
1439 
1440  // As _Tp is an empty type there will be no bytes written/read through
1441  // the cast pointer, so no strict-aliasing violation.
1442  _Tp*
1443  _M_h() { return reinterpret_cast<_Tp*>(this); }
1444 
1445  const _Tp*
1446  _M_h() const { return reinterpret_cast<const _Tp*>(this); }
1447  };
1448 
1449  template<typename _Key, typename _Value, typename _ExtractKey,
1450  typename _Hash, typename _RangeHash, typename _Unused>
1451  using __hash_code_for_local_iter
1452  = _Hash_code_storage<_Hash_code_base<_Key, _Value, _ExtractKey,
1453  _Hash, _RangeHash, _Unused, false>>;
1454 
1455  // Partial specialization used when hash codes are not cached
1456  template<typename _Key, typename _Value, typename _ExtractKey,
1457  typename _Hash, typename _RangeHash, typename _Unused>
1458  struct _Local_iterator_base<_Key, _Value, _ExtractKey,
1459  _Hash, _RangeHash, _Unused, false>
1460  : __hash_code_for_local_iter<_Key, _Value, _ExtractKey, _Hash, _RangeHash,
1461  _Unused>
1462  , _Node_iterator_base<_Value, false>
1463  {
1464  protected:
1465  using __hash_code_base = _Hash_code_base<_Key, _Value, _ExtractKey,
1466  _Hash, _RangeHash, _Unused, false>;
1467  using __node_iter_base = _Node_iterator_base<_Value, false>;
1468 
1469  _Local_iterator_base() : _M_bucket_count(-1) { }
1470 
1471  _Local_iterator_base(const __hash_code_base& __base,
1472  _Hash_node<_Value, false>* __p,
1473  std::size_t __bkt, std::size_t __bkt_count)
1474  : __node_iter_base(__p), _M_bucket(__bkt), _M_bucket_count(__bkt_count)
1475  { _M_init(__base); }
1476 
1477  ~_Local_iterator_base()
1478  {
1479  if (_M_bucket_count != size_t(-1))
1480  _M_destroy();
1481  }
1482 
1483  _Local_iterator_base(const _Local_iterator_base& __iter)
1484  : __node_iter_base(__iter._M_cur), _M_bucket(__iter._M_bucket)
1485  , _M_bucket_count(__iter._M_bucket_count)
1486  {
1487  if (_M_bucket_count != size_t(-1))
1488  _M_init(*__iter._M_h());
1489  }
1490 
1491  _Local_iterator_base&
1492  operator=(const _Local_iterator_base& __iter)
1493  {
1494  if (_M_bucket_count != -1)
1495  _M_destroy();
1496  this->_M_cur = __iter._M_cur;
1497  _M_bucket = __iter._M_bucket;
1498  _M_bucket_count = __iter._M_bucket_count;
1499  if (_M_bucket_count != -1)
1500  _M_init(*__iter._M_h());
1501  return *this;
1502  }
1503 
1504  void
1505  _M_incr()
1506  {
1507  __node_iter_base::_M_incr();
1508  if (this->_M_cur)
1509  {
1510  std::size_t __bkt = this->_M_h()->_M_bucket_index(*this->_M_cur,
1511  _M_bucket_count);
1512  if (__bkt != _M_bucket)
1513  this->_M_cur = nullptr;
1514  }
1515  }
1516 
1517  std::size_t _M_bucket;
1518  std::size_t _M_bucket_count;
1519 
1520  void
1521  _M_init(const __hash_code_base& __base)
1522  { ::new(this->_M_h()) __hash_code_base(__base); }
1523 
1524  void
1525  _M_destroy() { this->_M_h()->~__hash_code_base(); }
1526 
1527  public:
1528  std::size_t
1529  _M_get_bucket() const { return _M_bucket; } // for debug mode
1530  };
1531 
1532  /// local iterators
1533  template<typename _Key, typename _Value, typename _ExtractKey,
1534  typename _Hash, typename _RangeHash, typename _Unused,
1535  bool __constant_iterators, bool __cache>
1536  struct _Local_iterator
1537  : public _Local_iterator_base<_Key, _Value, _ExtractKey,
1538  _Hash, _RangeHash, _Unused, __cache>
1539  {
1540  private:
1541  using __base_type = _Local_iterator_base<_Key, _Value, _ExtractKey,
1542  _Hash, _RangeHash, _Unused, __cache>;
1543  using __hash_code_base = typename __base_type::__hash_code_base;
1544 
1545  public:
1546  using value_type = _Value;
1547  using pointer = __conditional_t<__constant_iterators,
1548  const value_type*, value_type*>;
1549  using reference = __conditional_t<__constant_iterators,
1550  const value_type&, value_type&>;
1551  using difference_type = ptrdiff_t;
1552  using iterator_category = forward_iterator_tag;
1553 
1554  _Local_iterator() = default;
1555 
1556  _Local_iterator(const __hash_code_base& __base,
1557  _Hash_node<_Value, __cache>* __n,
1558  std::size_t __bkt, std::size_t __bkt_count)
1559  : __base_type(__base, __n, __bkt, __bkt_count)
1560  { }
1561 
1562  reference
1563  operator*() const
1564  { return this->_M_cur->_M_v(); }
1565 
1566  pointer
1567  operator->() const
1568  { return this->_M_cur->_M_valptr(); }
1569 
1570  _Local_iterator&
1571  operator++()
1572  {
1573  this->_M_incr();
1574  return *this;
1575  }
1576 
1577  _Local_iterator
1578  operator++(int)
1579  {
1580  _Local_iterator __tmp(*this);
1581  this->_M_incr();
1582  return __tmp;
1583  }
1584  };
1585 
1586  /// local const_iterators
1587  template<typename _Key, typename _Value, typename _ExtractKey,
1588  typename _Hash, typename _RangeHash, typename _Unused,
1589  bool __constant_iterators, bool __cache>
1590  struct _Local_const_iterator
1591  : public _Local_iterator_base<_Key, _Value, _ExtractKey,
1592  _Hash, _RangeHash, _Unused, __cache>
1593  {
1594  private:
1595  using __base_type = _Local_iterator_base<_Key, _Value, _ExtractKey,
1596  _Hash, _RangeHash, _Unused, __cache>;
1597  using __hash_code_base = typename __base_type::__hash_code_base;
1598 
1599  public:
1600  typedef _Value value_type;
1601  typedef const value_type* pointer;
1602  typedef const value_type& reference;
1603  typedef std::ptrdiff_t difference_type;
1604  typedef std::forward_iterator_tag iterator_category;
1605 
1606  _Local_const_iterator() = default;
1607 
1608  _Local_const_iterator(const __hash_code_base& __base,
1609  _Hash_node<_Value, __cache>* __n,
1610  std::size_t __bkt, std::size_t __bkt_count)
1611  : __base_type(__base, __n, __bkt, __bkt_count)
1612  { }
1613 
1614  _Local_const_iterator(const _Local_iterator<_Key, _Value, _ExtractKey,
1615  _Hash, _RangeHash, _Unused,
1616  __constant_iterators,
1617  __cache>& __x)
1618  : __base_type(__x)
1619  { }
1620 
1621  reference
1622  operator*() const
1623  { return this->_M_cur->_M_v(); }
1624 
1625  pointer
1626  operator->() const
1627  { return this->_M_cur->_M_valptr(); }
1628 
1629  _Local_const_iterator&
1630  operator++()
1631  {
1632  this->_M_incr();
1633  return *this;
1634  }
1635 
1636  _Local_const_iterator
1637  operator++(int)
1638  {
1639  _Local_const_iterator __tmp(*this);
1640  this->_M_incr();
1641  return __tmp;
1642  }
1643  };
1644 
1645  /**
1646  * Primary class template _Hashtable_base.
1647  *
1648  * Helper class adding management of _Equal functor to
1649  * _Hash_code_base type.
1650  *
1651  * Base class templates are:
1652  * - __detail::_Hash_code_base
1653  * - __detail::_Hashtable_ebo_helper
1654  */
1655  template<typename _Key, typename _Value, typename _ExtractKey,
1656  typename _Equal, typename _Hash, typename _RangeHash,
1657  typename _Unused, typename _Traits>
1658  struct _Hashtable_base
1659  : public _Hash_code_base<_Key, _Value, _ExtractKey, _Hash, _RangeHash,
1660  _Unused, _Traits::__hash_cached::value>,
1661  private _Hashtable_ebo_helper<0, _Equal>
1662  {
1663  public:
1664  typedef _Key key_type;
1665  typedef _Value value_type;
1666  typedef _Equal key_equal;
1667  typedef std::size_t size_type;
1668  typedef std::ptrdiff_t difference_type;
1669 
1670  using __traits_type = _Traits;
1671  using __hash_cached = typename __traits_type::__hash_cached;
1672 
1673  using __hash_code_base = _Hash_code_base<_Key, _Value, _ExtractKey,
1674  _Hash, _RangeHash, _Unused,
1675  __hash_cached::value>;
1676 
1677  using __hash_code = typename __hash_code_base::__hash_code;
1678 
1679  private:
1680  using _EqualEBO = _Hashtable_ebo_helper<0, _Equal>;
1681 
1682  static bool
1683  _S_equals(__hash_code, const _Hash_node_code_cache<false>&)
1684  { return true; }
1685 
1686  static bool
1687  _S_node_equals(const _Hash_node_code_cache<false>&,
1688  const _Hash_node_code_cache<false>&)
1689  { return true; }
1690 
1691  static bool
1692  _S_equals(__hash_code __c, const _Hash_node_code_cache<true>& __n)
1693  { return __c == __n._M_hash_code; }
1694 
1695  static bool
1696  _S_node_equals(const _Hash_node_code_cache<true>& __lhn,
1697  const _Hash_node_code_cache<true>& __rhn)
1698  { return __lhn._M_hash_code == __rhn._M_hash_code; }
1699 
1700  protected:
1701  _Hashtable_base() = default;
1702 
1703  _Hashtable_base(const _Hash& __hash, const _Equal& __eq)
1704  : __hash_code_base(__hash), _EqualEBO(__eq)
1705  { }
1706 
1707  bool
1708  _M_key_equals(const _Key& __k,
1709  const _Hash_node_value<_Value,
1710  __hash_cached::value>& __n) const
1711  {
1712  static_assert(__is_invocable<const _Equal&, const _Key&, const _Key&>{},
1713  "key equality predicate must be invocable with two arguments of "
1714  "key type");
1715  return _M_eq()(__k, _ExtractKey{}(__n._M_v()));
1716  }
1717 
1718  template<typename _Kt>
1719  bool
1720  _M_key_equals_tr(const _Kt& __k,
1721  const _Hash_node_value<_Value,
1722  __hash_cached::value>& __n) const
1723  {
1724  static_assert(
1725  __is_invocable<const _Equal&, const _Kt&, const _Key&>{},
1726  "key equality predicate must be invocable with two arguments of "
1727  "key type");
1728  return _M_eq()(__k, _ExtractKey{}(__n._M_v()));
1729  }
1730 
1731  bool
1732  _M_equals(const _Key& __k, __hash_code __c,
1733  const _Hash_node_value<_Value, __hash_cached::value>& __n) const
1734  { return _S_equals(__c, __n) && _M_key_equals(__k, __n); }
1735 
1736  template<typename _Kt>
1737  bool
1738  _M_equals_tr(const _Kt& __k, __hash_code __c,
1739  const _Hash_node_value<_Value,
1740  __hash_cached::value>& __n) const
1741  { return _S_equals(__c, __n) && _M_key_equals_tr(__k, __n); }
1742 
1743  bool
1744  _M_node_equals(
1745  const _Hash_node_value<_Value, __hash_cached::value>& __lhn,
1746  const _Hash_node_value<_Value, __hash_cached::value>& __rhn) const
1747  {
1748  return _S_node_equals(__lhn, __rhn)
1749  && _M_key_equals(_ExtractKey{}(__lhn._M_v()), __rhn);
1750  }
1751 
1752  void
1753  _M_swap(_Hashtable_base& __x)
1754  {
1755  __hash_code_base::_M_swap(__x);
1756  std::swap(_EqualEBO::_M_get(), __x._EqualEBO::_M_get());
1757  }
1758 
1759  const _Equal&
1760  _M_eq() const { return _EqualEBO::_M_cget(); }
1761  };
1762 
1763  /**
1764  * Primary class template _Equality.
1765  *
1766  * This is for implementing equality comparison for unordered
1767  * containers, per N3068, by John Lakos and Pablo Halpern.
1768  * Algorithmically, we follow closely the reference implementations
1769  * therein.
1770  */
1771  template<typename _Key, typename _Value, typename _Alloc,
1772  typename _ExtractKey, typename _Equal,
1773  typename _Hash, typename _RangeHash, typename _Unused,
1774  typename _RehashPolicy, typename _Traits,
1775  bool _Unique_keys = _Traits::__unique_keys::value>
1776  struct _Equality;
1777 
1778  /// unordered_map and unordered_set specializations.
1779  template<typename _Key, typename _Value, typename _Alloc,
1780  typename _ExtractKey, typename _Equal,
1781  typename _Hash, typename _RangeHash, typename _Unused,
1782  typename _RehashPolicy, typename _Traits>
1783  struct _Equality<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1784  _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits, true>
1785  {
1786  using __hashtable = _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1787  _Hash, _RangeHash, _Unused,
1788  _RehashPolicy, _Traits>;
1789 
1790  bool
1791  _M_equal(const __hashtable&) const;
1792  };
1793 
1794  template<typename _Key, typename _Value, typename _Alloc,
1795  typename _ExtractKey, typename _Equal,
1796  typename _Hash, typename _RangeHash, typename _Unused,
1797  typename _RehashPolicy, typename _Traits>
1798  bool
1799  _Equality<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1800  _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits, true>::
1801  _M_equal(const __hashtable& __other) const
1802  {
1803  using __node_type = typename __hashtable::__node_type;
1804  const __hashtable* __this = static_cast<const __hashtable*>(this);
1805  if (__this->size() != __other.size())
1806  return false;
1807 
1808  for (auto __itx = __this->begin(); __itx != __this->end(); ++__itx)
1809  {
1810  std::size_t __ybkt = __other._M_bucket_index(*__itx._M_cur);
1811  auto __prev_n = __other._M_buckets[__ybkt];
1812  if (!__prev_n)
1813  return false;
1814 
1815  for (__node_type* __n = static_cast<__node_type*>(__prev_n->_M_nxt);;
1816  __n = __n->_M_next())
1817  {
1818  if (__n->_M_v() == *__itx)
1819  break;
1820 
1821  if (!__n->_M_nxt
1822  || __other._M_bucket_index(*__n->_M_next()) != __ybkt)
1823  return false;
1824  }
1825  }
1826 
1827  return true;
1828  }
1829 
1830  /// unordered_multiset and unordered_multimap specializations.
1831  template<typename _Key, typename _Value, typename _Alloc,
1832  typename _ExtractKey, typename _Equal,
1833  typename _Hash, typename _RangeHash, typename _Unused,
1834  typename _RehashPolicy, typename _Traits>
1835  struct _Equality<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1836  _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits, false>
1837  {
1838  using __hashtable = _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1839  _Hash, _RangeHash, _Unused,
1840  _RehashPolicy, _Traits>;
1841 
1842  bool
1843  _M_equal(const __hashtable&) const;
1844  };
1845 
1846  template<typename _Key, typename _Value, typename _Alloc,
1847  typename _ExtractKey, typename _Equal,
1848  typename _Hash, typename _RangeHash, typename _Unused,
1849  typename _RehashPolicy, typename _Traits>
1850  bool
1851  _Equality<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1852  _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits, false>::
1853  _M_equal(const __hashtable& __other) const
1854  {
1855  using __node_type = typename __hashtable::__node_type;
1856  const __hashtable* __this = static_cast<const __hashtable*>(this);
1857  if (__this->size() != __other.size())
1858  return false;
1859 
1860  for (auto __itx = __this->begin(); __itx != __this->end();)
1861  {
1862  std::size_t __x_count = 1;
1863  auto __itx_end = __itx;
1864  for (++__itx_end; __itx_end != __this->end()
1865  && __this->key_eq()(_ExtractKey{}(*__itx),
1866  _ExtractKey{}(*__itx_end));
1867  ++__itx_end)
1868  ++__x_count;
1869 
1870  std::size_t __ybkt = __other._M_bucket_index(*__itx._M_cur);
1871  auto __y_prev_n = __other._M_buckets[__ybkt];
1872  if (!__y_prev_n)
1873  return false;
1874 
1875  __node_type* __y_n = static_cast<__node_type*>(__y_prev_n->_M_nxt);
1876  for (;;)
1877  {
1878  if (__this->key_eq()(_ExtractKey{}(__y_n->_M_v()),
1879  _ExtractKey{}(*__itx)))
1880  break;
1881 
1882  auto __y_ref_n = __y_n;
1883  for (__y_n = __y_n->_M_next(); __y_n; __y_n = __y_n->_M_next())
1884  if (!__other._M_node_equals(*__y_ref_n, *__y_n))
1885  break;
1886 
1887  if (!__y_n || __other._M_bucket_index(*__y_n) != __ybkt)
1888  return false;
1889  }
1890 
1891  typename __hashtable::const_iterator __ity(__y_n);
1892  for (auto __ity_end = __ity; __ity_end != __other.end(); ++__ity_end)
1893  if (--__x_count == 0)
1894  break;
1895 
1896  if (__x_count != 0)
1897  return false;
1898 
1899  if (!std::is_permutation(__itx, __itx_end, __ity))
1900  return false;
1901 
1902  __itx = __itx_end;
1903  }
1904  return true;
1905  }
1906 
1907  /**
1908  * This type deals with all allocation and keeps an allocator instance
1909  * through inheritance to benefit from EBO when possible.
1910  */
1911  template<typename _NodeAlloc>
1912  struct _Hashtable_alloc : private _Hashtable_ebo_helper<0, _NodeAlloc>
1913  {
1914  private:
1915  using __ebo_node_alloc = _Hashtable_ebo_helper<0, _NodeAlloc>;
1916 
1917  template<typename>
1918  struct __get_value_type;
1919  template<typename _Val, bool _Cache_hash_code>
1920  struct __get_value_type<_Hash_node<_Val, _Cache_hash_code>>
1921  { using type = _Val; };
1922 
1923  public:
1924  using __node_type = typename _NodeAlloc::value_type;
1925  using __node_alloc_type = _NodeAlloc;
1926  // Use __gnu_cxx to benefit from _S_always_equal and al.
1927  using __node_alloc_traits = __gnu_cxx::__alloc_traits<__node_alloc_type>;
1928 
1929  using __value_alloc_traits = typename __node_alloc_traits::template
1930  rebind_traits<typename __get_value_type<__node_type>::type>;
1931 
1932  using __node_ptr = __node_type*;
1933  using __node_base = _Hash_node_base;
1934  using __node_base_ptr = __node_base*;
1935  using __buckets_alloc_type =
1936  __alloc_rebind<__node_alloc_type, __node_base_ptr>;
1937  using __buckets_alloc_traits = std::allocator_traits<__buckets_alloc_type>;
1938  using __buckets_ptr = __node_base_ptr*;
1939 
1940  _Hashtable_alloc() = default;
1941  _Hashtable_alloc(const _Hashtable_alloc&) = default;
1942  _Hashtable_alloc(_Hashtable_alloc&&) = default;
1943 
1944  template<typename _Alloc>
1945  _Hashtable_alloc(_Alloc&& __a)
1946  : __ebo_node_alloc(std::forward<_Alloc>(__a))
1947  { }
1948 
1949  __node_alloc_type&
1950  _M_node_allocator()
1951  { return __ebo_node_alloc::_M_get(); }
1952 
1953  const __node_alloc_type&
1954  _M_node_allocator() const
1955  { return __ebo_node_alloc::_M_cget(); }
1956 
1957  // Allocate a node and construct an element within it.
1958  template<typename... _Args>
1959  __node_ptr
1960  _M_allocate_node(_Args&&... __args);
1961 
1962  // Destroy the element within a node and deallocate the node.
1963  void
1964  _M_deallocate_node(__node_ptr __n);
1965 
1966  // Deallocate a node.
1967  void
1968  _M_deallocate_node_ptr(__node_ptr __n);
1969 
1970  // Deallocate the linked list of nodes pointed to by __n.
1971  // The elements within the nodes are destroyed.
1972  void
1973  _M_deallocate_nodes(__node_ptr __n);
1974 
1975  __buckets_ptr
1976  _M_allocate_buckets(std::size_t __bkt_count);
1977 
1978  void
1979  _M_deallocate_buckets(__buckets_ptr, std::size_t __bkt_count);
1980  };
1981 
1982  // Definitions of class template _Hashtable_alloc's out-of-line member
1983  // functions.
1984  template<typename _NodeAlloc>
1985  template<typename... _Args>
1986  auto
1987  _Hashtable_alloc<_NodeAlloc>::_M_allocate_node(_Args&&... __args)
1988  -> __node_ptr
1989  {
1990  auto __nptr = __node_alloc_traits::allocate(_M_node_allocator(), 1);
1991  __node_ptr __n = std::__to_address(__nptr);
1992  __try
1993  {
1994  ::new ((void*)__n) __node_type;
1995  __node_alloc_traits::construct(_M_node_allocator(),
1996  __n->_M_valptr(),
1997  std::forward<_Args>(__args)...);
1998  return __n;
1999  }
2000  __catch(...)
2001  {
2002  __node_alloc_traits::deallocate(_M_node_allocator(), __nptr, 1);
2003  __throw_exception_again;
2004  }
2005  }
2006 
2007  template<typename _NodeAlloc>
2008  void
2009  _Hashtable_alloc<_NodeAlloc>::_M_deallocate_node(__node_ptr __n)
2010  {
2011  __node_alloc_traits::destroy(_M_node_allocator(), __n->_M_valptr());
2012  _M_deallocate_node_ptr(__n);
2013  }
2014 
2015  template<typename _NodeAlloc>
2016  void
2017  _Hashtable_alloc<_NodeAlloc>::_M_deallocate_node_ptr(__node_ptr __n)
2018  {
2019  typedef typename __node_alloc_traits::pointer _Ptr;
2020  auto __ptr = std::pointer_traits<_Ptr>::pointer_to(*__n);
2021  __n->~__node_type();
2022  __node_alloc_traits::deallocate(_M_node_allocator(), __ptr, 1);
2023  }
2024 
2025  template<typename _NodeAlloc>
2026  void
2027  _Hashtable_alloc<_NodeAlloc>::_M_deallocate_nodes(__node_ptr __n)
2028  {
2029  while (__n)
2030  {
2031  __node_ptr __tmp = __n;
2032  __n = __n->_M_next();
2033  _M_deallocate_node(__tmp);
2034  }
2035  }
2036 
2037  template<typename _NodeAlloc>
2038  auto
2039  _Hashtable_alloc<_NodeAlloc>::_M_allocate_buckets(std::size_t __bkt_count)
2040  -> __buckets_ptr
2041  {
2042  __buckets_alloc_type __alloc(_M_node_allocator());
2043 
2044  auto __ptr = __buckets_alloc_traits::allocate(__alloc, __bkt_count);
2045  __buckets_ptr __p = std::__to_address(__ptr);
2046  __builtin_memset(__p, 0, __bkt_count * sizeof(__node_base_ptr));
2047  return __p;
2048  }
2049 
2050  template<typename _NodeAlloc>
2051  void
2052  _Hashtable_alloc<_NodeAlloc>::
2053  _M_deallocate_buckets(__buckets_ptr __bkts,
2054  std::size_t __bkt_count)
2055  {
2056  typedef typename __buckets_alloc_traits::pointer _Ptr;
2057  auto __ptr = std::pointer_traits<_Ptr>::pointer_to(*__bkts);
2058  __buckets_alloc_type __alloc(_M_node_allocator());
2059  __buckets_alloc_traits::deallocate(__alloc, __ptr, __bkt_count);
2060  }
2061 
2062  ///@} hashtable-detail
2063 } // namespace __detail
2064 /// @endcond
2065 _GLIBCXX_END_NAMESPACE_VERSION
2066 } // namespace std
2067 
2068 #endif // _HASHTABLE_POLICY_H
constexpr iterator_traits< _InputIterator >::difference_type distance(_InputIterator __first, _InputIterator __last)
A generalization of pointer arithmetic.
Primary class template, tuple.
Definition: tuple:58
constexpr _Iterator __base(_Iterator __it)
constexpr iterator_traits< _Iter >::iterator_category __iterator_category(const _Iter &)
constexpr tuple< _Elements &&... > forward_as_tuple(_Elements &&... __args) noexcept
Create a tuple of lvalue or rvalue references to the arguments.
Definition: tuple:2013
constexpr _Tp && forward(typename std::remove_reference< _Tp >::type &__t) noexcept
Forward an lvalue.
Definition: move.h:70
is_constructible
Definition: type_traits:1045
Definition: simd.h:286
Uniform interface to all allocator types.
Define a member typedef type only if a boolean constant is true.
Definition: type_traits:106
Marking input iterators.
Struct holding two objects of arbitrary type.
constexpr complex< _Tp > operator*(const complex< _Tp > &__x, const complex< _Tp > &__y)
Return new complex value x times y.
Definition: complex:395
constexpr piecewise_construct_t piecewise_construct
Tag for piecewise construction of std::pair objects.
Definition: stl_pair.h:83
Uniform interface to all pointer-like types.
Definition: ptr_traits.h:184
Forward iterators support a superset of input iterator operations.
integral_constant< bool, true > true_type
The type used as a compile-time boolean with true value.
Definition: type_traits:82
Traits class for iterators.
ISO C++ entities toplevel namespace is std.
Uniform interface to C++98 and C++11 allocators.
integral_constant< bool, false > false_type
The type used as a compile-time boolean with false value.
Definition: type_traits:85
constexpr std::remove_reference< _Tp >::type && move(_Tp &&__t) noexcept
Convert a value to an rvalue.
Definition: move.h:97
is_empty
Definition: type_traits:842
__numeric_traits_integer< _Tp > __int_traits
Convenience alias for __numeric_traits<integer-type>.