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