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