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-2018 Free Software Foundation, Inc.
4 //
5 // This file is part of the GNU ISO C++ Library. This library is free
6 // software; you can redistribute it and/or modify it under the
7 // terms of the GNU General Public License as published by the
8 // Free Software Foundation; either version 3, or (at your option)
9 // any later version.
10 
11 // This library is distributed in the hope that it will be useful,
12 // but WITHOUT ANY WARRANTY; without even the implied warranty of
13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 // GNU General Public License for more details.
15 
16 // Under Section 7 of GPL version 3, you are granted additional
17 // permissions described in the GCC Runtime Library Exception, version
18 // 3.1, as published by the Free Software Foundation.
19 
20 // You should have received a copy of the GNU General Public License and
21 // a copy of the GCC Runtime Library Exception along with this program;
22 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
23 // <http://www.gnu.org/licenses/>.
24 
25 /** @file bits/hashtable_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 <cstdint> // for std::uint_fast64_t
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  __node->~__node_type();
139  __node_alloc_traits::deallocate(__a, __node, 1);
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 _Equal
186  * function.
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_ceil(__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.
508  _GLIBCXX14_CONSTEXPR
509  inline std::size_t
510  __clp2(std::size_t __n) noexcept
511  {
512 #if __SIZEOF_SIZE_T__ >= 8
513  std::uint_fast64_t __x = __n;
514 #else
515  std::uint_fast32_t __x = __n;
516 #endif
517  // Algorithm from Hacker's Delight, Figure 3-3.
518  __x = __x - 1;
519  __x = __x | (__x >> 1);
520  __x = __x | (__x >> 2);
521  __x = __x | (__x >> 4);
522  __x = __x | (__x >> 8);
523  __x = __x | (__x >>16);
524 #if __SIZEOF_SIZE_T__ >= 8
525  __x = __x | (__x >>32);
526 #endif
527  return __x + 1;
528  }
529 
530  /// Rehash policy providing power of 2 bucket numbers. Avoids modulo
531  /// operations.
533  {
535 
536  _Power2_rehash_policy(float __z = 1.0) noexcept
537  : _M_max_load_factor(__z), _M_next_resize(0) { }
538 
539  float
540  max_load_factor() const noexcept
541  { return _M_max_load_factor; }
542 
543  // Return a bucket size no smaller than n (as long as n is not above the
544  // highest power of 2).
545  std::size_t
546  _M_next_bkt(std::size_t __n) noexcept
547  {
548  const auto __max_width = std::min<size_t>(sizeof(size_t), 8);
549  const auto __max_bkt = size_t(1) << (__max_width * __CHAR_BIT__ - 1);
550  std::size_t __res = __clp2(__n);
551 
552  if (__res == __n)
553  __res <<= 1;
554 
555  if (__res == 0)
556  __res = __max_bkt;
557 
558  if (__res == __max_bkt)
559  // Set next resize to the max value so that we never try to rehash again
560  // as we already reach the biggest possible bucket number.
561  // Note that it might result in max_load_factor not being respected.
562  _M_next_resize = std::size_t(-1);
563  else
564  _M_next_resize
565  = __builtin_ceil(__res * (long double)_M_max_load_factor);
566 
567  return __res;
568  }
569 
570  // Return a bucket count appropriate for n elements
571  std::size_t
572  _M_bkt_for_elements(std::size_t __n) const noexcept
573  { return __builtin_ceil(__n / (long double)_M_max_load_factor); }
574 
575  // __n_bkt is current bucket count, __n_elt is current element count,
576  // and __n_ins is number of elements to be inserted. Do we need to
577  // increase bucket count? If so, return make_pair(true, n), where n
578  // is the new bucket count. If not, return make_pair(false, 0).
580  _M_need_rehash(std::size_t __n_bkt, std::size_t __n_elt,
581  std::size_t __n_ins) noexcept
582  {
583  if (__n_elt + __n_ins >= _M_next_resize)
584  {
585  long double __min_bkts = (__n_elt + __n_ins)
586  / (long double)_M_max_load_factor;
587  if (__min_bkts >= __n_bkt)
588  return std::make_pair(true,
589  _M_next_bkt(std::max<std::size_t>(__builtin_floor(__min_bkts) + 1,
590  __n_bkt * _S_growth_factor)));
591 
592  _M_next_resize
593  = __builtin_floor(__n_bkt * (long double)_M_max_load_factor);
594  return std::make_pair(false, 0);
595  }
596  else
597  return std::make_pair(false, 0);
598  }
599 
600  typedef std::size_t _State;
601 
602  _State
603  _M_state() const noexcept
604  { return _M_next_resize; }
605 
606  void
607  _M_reset() noexcept
608  { _M_next_resize = 0; }
609 
610  void
611  _M_reset(_State __state) noexcept
612  { _M_next_resize = __state; }
613 
614  static const std::size_t _S_growth_factor = 2;
615 
616  float _M_max_load_factor;
617  std::size_t _M_next_resize;
618  };
619 
620  // Base classes for std::_Hashtable. We define these base classes
621  // because in some cases we want to do different things depending on
622  // the value of a policy class. In some cases the policy class
623  // affects which member functions and nested typedefs are defined;
624  // we handle that by specializing base class templates. Several of
625  // the base class templates need to access other members of class
626  // template _Hashtable, so we use a variant of the "Curiously
627  // Recurring Template Pattern" (CRTP) technique.
628 
629  /**
630  * Primary class template _Map_base.
631  *
632  * If the hashtable has a value type of the form pair<T1, T2> and a
633  * key extraction policy (_ExtractKey) that returns the first part
634  * of the pair, the hashtable gets a mapped_type typedef. If it
635  * satisfies those criteria and also has unique keys, then it also
636  * gets an operator[].
637  */
638  template<typename _Key, typename _Value, typename _Alloc,
639  typename _ExtractKey, typename _Equal,
640  typename _H1, typename _H2, typename _Hash,
641  typename _RehashPolicy, typename _Traits,
642  bool _Unique_keys = _Traits::__unique_keys::value>
643  struct _Map_base { };
644 
645  /// Partial specialization, __unique_keys set to false.
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, false>
651  {
652  using mapped_type = typename std::tuple_element<1, _Pair>::type;
653  };
654 
655  /// Partial specialization, __unique_keys set to true.
656  template<typename _Key, typename _Pair, typename _Alloc, typename _Equal,
657  typename _H1, typename _H2, typename _Hash,
658  typename _RehashPolicy, typename _Traits>
659  struct _Map_base<_Key, _Pair, _Alloc, _Select1st, _Equal,
660  _H1, _H2, _Hash, _RehashPolicy, _Traits, true>
661  {
662  private:
663  using __hashtable_base = __detail::_Hashtable_base<_Key, _Pair,
664  _Select1st,
665  _Equal, _H1, _H2, _Hash,
666  _Traits>;
667 
668  using __hashtable = _Hashtable<_Key, _Pair, _Alloc,
669  _Select1st, _Equal,
670  _H1, _H2, _Hash, _RehashPolicy, _Traits>;
671 
672  using __hash_code = typename __hashtable_base::__hash_code;
673  using __node_type = typename __hashtable_base::__node_type;
674 
675  public:
676  using key_type = typename __hashtable_base::key_type;
677  using iterator = typename __hashtable_base::iterator;
678  using mapped_type = typename std::tuple_element<1, _Pair>::type;
679 
680  mapped_type&
681  operator[](const key_type& __k);
682 
683  mapped_type&
684  operator[](key_type&& __k);
685 
686  // _GLIBCXX_RESOLVE_LIB_DEFECTS
687  // DR 761. unordered_map needs an at() member function.
688  mapped_type&
689  at(const key_type& __k);
690 
691  const mapped_type&
692  at(const key_type& __k) const;
693  };
694 
695  template<typename _Key, typename _Pair, typename _Alloc, typename _Equal,
696  typename _H1, typename _H2, typename _Hash,
697  typename _RehashPolicy, typename _Traits>
698  auto
699  _Map_base<_Key, _Pair, _Alloc, _Select1st, _Equal,
700  _H1, _H2, _Hash, _RehashPolicy, _Traits, true>::
701  operator[](const key_type& __k)
702  -> mapped_type&
703  {
704  __hashtable* __h = static_cast<__hashtable*>(this);
705  __hash_code __code = __h->_M_hash_code(__k);
706  std::size_t __n = __h->_M_bucket_index(__k, __code);
707  __node_type* __p = __h->_M_find_node(__n, __k, __code);
708 
709  if (!__p)
710  {
711  __p = __h->_M_allocate_node(std::piecewise_construct,
713  std::tuple<>());
714  return __h->_M_insert_unique_node(__n, __code, __p)->second;
715  }
716 
717  return __p->_M_v().second;
718  }
719 
720  template<typename _Key, typename _Pair, typename _Alloc, typename _Equal,
721  typename _H1, typename _H2, typename _Hash,
722  typename _RehashPolicy, typename _Traits>
723  auto
724  _Map_base<_Key, _Pair, _Alloc, _Select1st, _Equal,
725  _H1, _H2, _Hash, _RehashPolicy, _Traits, true>::
726  operator[](key_type&& __k)
727  -> mapped_type&
728  {
729  __hashtable* __h = static_cast<__hashtable*>(this);
730  __hash_code __code = __h->_M_hash_code(__k);
731  std::size_t __n = __h->_M_bucket_index(__k, __code);
732  __node_type* __p = __h->_M_find_node(__n, __k, __code);
733 
734  if (!__p)
735  {
736  __p = __h->_M_allocate_node(std::piecewise_construct,
737  std::forward_as_tuple(std::move(__k)),
738  std::tuple<>());
739  return __h->_M_insert_unique_node(__n, __code, __p)->second;
740  }
741 
742  return __p->_M_v().second;
743  }
744 
745  template<typename _Key, typename _Pair, typename _Alloc, typename _Equal,
746  typename _H1, typename _H2, typename _Hash,
747  typename _RehashPolicy, typename _Traits>
748  auto
749  _Map_base<_Key, _Pair, _Alloc, _Select1st, _Equal,
750  _H1, _H2, _Hash, _RehashPolicy, _Traits, true>::
751  at(const key_type& __k)
752  -> mapped_type&
753  {
754  __hashtable* __h = static_cast<__hashtable*>(this);
755  __hash_code __code = __h->_M_hash_code(__k);
756  std::size_t __n = __h->_M_bucket_index(__k, __code);
757  __node_type* __p = __h->_M_find_node(__n, __k, __code);
758 
759  if (!__p)
760  __throw_out_of_range(__N("_Map_base::at"));
761  return __p->_M_v().second;
762  }
763 
764  template<typename _Key, typename _Pair, typename _Alloc, typename _Equal,
765  typename _H1, typename _H2, typename _Hash,
766  typename _RehashPolicy, typename _Traits>
767  auto
768  _Map_base<_Key, _Pair, _Alloc, _Select1st, _Equal,
769  _H1, _H2, _Hash, _RehashPolicy, _Traits, true>::
770  at(const key_type& __k) const
771  -> const mapped_type&
772  {
773  const __hashtable* __h = static_cast<const __hashtable*>(this);
774  __hash_code __code = __h->_M_hash_code(__k);
775  std::size_t __n = __h->_M_bucket_index(__k, __code);
776  __node_type* __p = __h->_M_find_node(__n, __k, __code);
777 
778  if (!__p)
779  __throw_out_of_range(__N("_Map_base::at"));
780  return __p->_M_v().second;
781  }
782 
783  /**
784  * Primary class template _Insert_base.
785  *
786  * Defines @c insert member functions appropriate to all _Hashtables.
787  */
788  template<typename _Key, typename _Value, typename _Alloc,
789  typename _ExtractKey, typename _Equal,
790  typename _H1, typename _H2, typename _Hash,
791  typename _RehashPolicy, typename _Traits>
793  {
794  protected:
795  using __hashtable = _Hashtable<_Key, _Value, _Alloc, _ExtractKey,
796  _Equal, _H1, _H2, _Hash,
797  _RehashPolicy, _Traits>;
798 
799  using __hashtable_base = _Hashtable_base<_Key, _Value, _ExtractKey,
800  _Equal, _H1, _H2, _Hash,
801  _Traits>;
802 
803  using value_type = typename __hashtable_base::value_type;
804  using iterator = typename __hashtable_base::iterator;
805  using const_iterator = typename __hashtable_base::const_iterator;
806  using size_type = typename __hashtable_base::size_type;
807 
808  using __unique_keys = typename __hashtable_base::__unique_keys;
809  using __ireturn_type = typename __hashtable_base::__ireturn_type;
811  using __node_alloc_type = __alloc_rebind<_Alloc, __node_type>;
812  using __node_gen_type = _AllocNode<__node_alloc_type>;
813 
814  __hashtable&
815  _M_conjure_hashtable()
816  { return *(static_cast<__hashtable*>(this)); }
817 
818  template<typename _InputIterator, typename _NodeGetter>
819  void
820  _M_insert_range(_InputIterator __first, _InputIterator __last,
821  const _NodeGetter&, true_type);
822 
823  template<typename _InputIterator, typename _NodeGetter>
824  void
825  _M_insert_range(_InputIterator __first, _InputIterator __last,
826  const _NodeGetter&, false_type);
827 
828  public:
829  __ireturn_type
830  insert(const value_type& __v)
831  {
832  __hashtable& __h = _M_conjure_hashtable();
833  __node_gen_type __node_gen(__h);
834  return __h._M_insert(__v, __node_gen, __unique_keys());
835  }
836 
837  iterator
838  insert(const_iterator __hint, const value_type& __v)
839  {
840  __hashtable& __h = _M_conjure_hashtable();
841  __node_gen_type __node_gen(__h);
842  return __h._M_insert(__hint, __v, __node_gen, __unique_keys());
843  }
844 
845  void
846  insert(initializer_list<value_type> __l)
847  { this->insert(__l.begin(), __l.end()); }
848 
849  template<typename _InputIterator>
850  void
851  insert(_InputIterator __first, _InputIterator __last)
852  {
853  __hashtable& __h = _M_conjure_hashtable();
854  __node_gen_type __node_gen(__h);
855  return _M_insert_range(__first, __last, __node_gen, __unique_keys());
856  }
857  };
858 
859  template<typename _Key, typename _Value, typename _Alloc,
860  typename _ExtractKey, typename _Equal,
861  typename _H1, typename _H2, typename _Hash,
862  typename _RehashPolicy, typename _Traits>
863  template<typename _InputIterator, typename _NodeGetter>
864  void
865  _Insert_base<_Key, _Value, _Alloc, _ExtractKey, _Equal, _H1, _H2, _Hash,
866  _RehashPolicy, _Traits>::
867  _M_insert_range(_InputIterator __first, _InputIterator __last,
868  const _NodeGetter& __node_gen, true_type)
869  {
870  size_type __n_elt = __detail::__distance_fw(__first, __last);
871  if (__n_elt == 0)
872  return;
873 
874  __hashtable& __h = _M_conjure_hashtable();
875  for (; __first != __last; ++__first)
876  {
877  if (__h._M_insert(*__first, __node_gen, __unique_keys(),
878  __n_elt).second)
879  __n_elt = 1;
880  else if (__n_elt != 1)
881  --__n_elt;
882  }
883  }
884 
885  template<typename _Key, typename _Value, typename _Alloc,
886  typename _ExtractKey, typename _Equal,
887  typename _H1, typename _H2, typename _Hash,
888  typename _RehashPolicy, typename _Traits>
889  template<typename _InputIterator, typename _NodeGetter>
890  void
891  _Insert_base<_Key, _Value, _Alloc, _ExtractKey, _Equal, _H1, _H2, _Hash,
892  _RehashPolicy, _Traits>::
893  _M_insert_range(_InputIterator __first, _InputIterator __last,
894  const _NodeGetter& __node_gen, false_type)
895  {
896  using __rehash_type = typename __hashtable::__rehash_type;
897  using __rehash_state = typename __hashtable::__rehash_state;
898  using pair_type = std::pair<bool, std::size_t>;
899 
900  size_type __n_elt = __detail::__distance_fw(__first, __last);
901  if (__n_elt == 0)
902  return;
903 
904  __hashtable& __h = _M_conjure_hashtable();
905  __rehash_type& __rehash = __h._M_rehash_policy;
906  const __rehash_state& __saved_state = __rehash._M_state();
907  pair_type __do_rehash = __rehash._M_need_rehash(__h._M_bucket_count,
908  __h._M_element_count,
909  __n_elt);
910 
911  if (__do_rehash.first)
912  __h._M_rehash(__do_rehash.second, __saved_state);
913 
914  for (; __first != __last; ++__first)
915  __h._M_insert(*__first, __node_gen, __unique_keys());
916  }
917 
918  /**
919  * Primary class template _Insert.
920  *
921  * Defines @c insert member functions that depend on _Hashtable policies,
922  * via partial specializations.
923  */
924  template<typename _Key, typename _Value, typename _Alloc,
925  typename _ExtractKey, typename _Equal,
926  typename _H1, typename _H2, typename _Hash,
927  typename _RehashPolicy, typename _Traits,
928  bool _Constant_iterators = _Traits::__constant_iterators::value>
929  struct _Insert;
930 
931  /// Specialization.
932  template<typename _Key, typename _Value, typename _Alloc,
933  typename _ExtractKey, typename _Equal,
934  typename _H1, typename _H2, typename _Hash,
935  typename _RehashPolicy, typename _Traits>
936  struct _Insert<_Key, _Value, _Alloc, _ExtractKey, _Equal, _H1, _H2, _Hash,
937  _RehashPolicy, _Traits, true>
938  : public _Insert_base<_Key, _Value, _Alloc, _ExtractKey, _Equal,
939  _H1, _H2, _Hash, _RehashPolicy, _Traits>
940  {
941  using __base_type = _Insert_base<_Key, _Value, _Alloc, _ExtractKey,
942  _Equal, _H1, _H2, _Hash,
943  _RehashPolicy, _Traits>;
944 
945  using __hashtable_base = _Hashtable_base<_Key, _Value, _ExtractKey,
946  _Equal, _H1, _H2, _Hash,
947  _Traits>;
948 
949  using value_type = typename __base_type::value_type;
950  using iterator = typename __base_type::iterator;
951  using const_iterator = typename __base_type::const_iterator;
952 
953  using __unique_keys = typename __base_type::__unique_keys;
954  using __ireturn_type = typename __hashtable_base::__ireturn_type;
955  using __hashtable = typename __base_type::__hashtable;
956  using __node_gen_type = typename __base_type::__node_gen_type;
957 
958  using __base_type::insert;
959 
960  __ireturn_type
961  insert(value_type&& __v)
962  {
963  __hashtable& __h = this->_M_conjure_hashtable();
964  __node_gen_type __node_gen(__h);
965  return __h._M_insert(std::move(__v), __node_gen, __unique_keys());
966  }
967 
968  iterator
969  insert(const_iterator __hint, value_type&& __v)
970  {
971  __hashtable& __h = this->_M_conjure_hashtable();
972  __node_gen_type __node_gen(__h);
973  return __h._M_insert(__hint, std::move(__v), __node_gen,
974  __unique_keys());
975  }
976  };
977 
978  /// Specialization.
979  template<typename _Key, typename _Value, typename _Alloc,
980  typename _ExtractKey, typename _Equal,
981  typename _H1, typename _H2, typename _Hash,
982  typename _RehashPolicy, typename _Traits>
983  struct _Insert<_Key, _Value, _Alloc, _ExtractKey, _Equal, _H1, _H2, _Hash,
984  _RehashPolicy, _Traits, false>
985  : public _Insert_base<_Key, _Value, _Alloc, _ExtractKey, _Equal,
986  _H1, _H2, _Hash, _RehashPolicy, _Traits>
987  {
988  using __base_type = _Insert_base<_Key, _Value, _Alloc, _ExtractKey,
989  _Equal, _H1, _H2, _Hash,
990  _RehashPolicy, _Traits>;
991  using value_type = typename __base_type::value_type;
992  using iterator = typename __base_type::iterator;
993  using const_iterator = typename __base_type::const_iterator;
994 
995  using __unique_keys = typename __base_type::__unique_keys;
996  using __hashtable = typename __base_type::__hashtable;
997  using __ireturn_type = typename __base_type::__ireturn_type;
998 
999  using __base_type::insert;
1000 
1001  template<typename _Pair>
1003 
1004  template<typename _Pair>
1006 
1007  template<typename _Pair>
1008  using _IFconsp = typename _IFcons<_Pair>::type;
1009 
1010  template<typename _Pair, typename = _IFconsp<_Pair>>
1011  __ireturn_type
1012  insert(_Pair&& __v)
1013  {
1014  __hashtable& __h = this->_M_conjure_hashtable();
1015  return __h._M_emplace(__unique_keys(), std::forward<_Pair>(__v));
1016  }
1017 
1018  template<typename _Pair, typename = _IFconsp<_Pair>>
1019  iterator
1020  insert(const_iterator __hint, _Pair&& __v)
1021  {
1022  __hashtable& __h = this->_M_conjure_hashtable();
1023  return __h._M_emplace(__hint, __unique_keys(),
1024  std::forward<_Pair>(__v));
1025  }
1026  };
1027 
1028  template<typename _Policy>
1029  using __has_load_factor = typename _Policy::__has_load_factor;
1030 
1031  /**
1032  * Primary class template _Rehash_base.
1033  *
1034  * Give hashtable the max_load_factor functions and reserve iff the
1035  * rehash policy supports it.
1036  */
1037  template<typename _Key, typename _Value, typename _Alloc,
1038  typename _ExtractKey, typename _Equal,
1039  typename _H1, typename _H2, typename _Hash,
1040  typename _RehashPolicy, typename _Traits,
1041  typename =
1042  __detected_or_t<std::false_type, __has_load_factor, _RehashPolicy>>
1044 
1045  /// Specialization when rehash policy doesn't provide load factor management.
1046  template<typename _Key, typename _Value, typename _Alloc,
1047  typename _ExtractKey, typename _Equal,
1048  typename _H1, typename _H2, typename _Hash,
1049  typename _RehashPolicy, typename _Traits>
1050  struct _Rehash_base<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1051  _H1, _H2, _Hash, _RehashPolicy, _Traits,
1052  std::false_type>
1053  {
1054  };
1055 
1056  /// Specialization when rehash policy provide load factor management.
1057  template<typename _Key, typename _Value, typename _Alloc,
1058  typename _ExtractKey, typename _Equal,
1059  typename _H1, typename _H2, typename _Hash,
1060  typename _RehashPolicy, typename _Traits>
1061  struct _Rehash_base<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1062  _H1, _H2, _Hash, _RehashPolicy, _Traits,
1063  std::true_type>
1064  {
1065  using __hashtable = _Hashtable<_Key, _Value, _Alloc, _ExtractKey,
1066  _Equal, _H1, _H2, _Hash,
1067  _RehashPolicy, _Traits>;
1068 
1069  float
1070  max_load_factor() const noexcept
1071  {
1072  const __hashtable* __this = static_cast<const __hashtable*>(this);
1073  return __this->__rehash_policy().max_load_factor();
1074  }
1075 
1076  void
1077  max_load_factor(float __z)
1078  {
1079  __hashtable* __this = static_cast<__hashtable*>(this);
1080  __this->__rehash_policy(_RehashPolicy(__z));
1081  }
1082 
1083  void
1084  reserve(std::size_t __n)
1085  {
1086  __hashtable* __this = static_cast<__hashtable*>(this);
1087  __this->rehash(__builtin_ceil(__n / max_load_factor()));
1088  }
1089  };
1090 
1091  /**
1092  * Primary class template _Hashtable_ebo_helper.
1093  *
1094  * Helper class using EBO when it is not forbidden (the type is not
1095  * final) and when it is worth it (the type is empty.)
1096  */
1097  template<int _Nm, typename _Tp,
1098  bool __use_ebo = !__is_final(_Tp) && __is_empty(_Tp)>
1100 
1101  /// Specialization using EBO.
1102  template<int _Nm, typename _Tp>
1103  struct _Hashtable_ebo_helper<_Nm, _Tp, true>
1104  : private _Tp
1105  {
1106  _Hashtable_ebo_helper() = default;
1107 
1108  template<typename _OtherTp>
1109  _Hashtable_ebo_helper(_OtherTp&& __tp)
1110  : _Tp(std::forward<_OtherTp>(__tp))
1111  { }
1112 
1113  static const _Tp&
1114  _S_cget(const _Hashtable_ebo_helper& __eboh)
1115  { return static_cast<const _Tp&>(__eboh); }
1116 
1117  static _Tp&
1118  _S_get(_Hashtable_ebo_helper& __eboh)
1119  { return static_cast<_Tp&>(__eboh); }
1120  };
1121 
1122  /// Specialization not using EBO.
1123  template<int _Nm, typename _Tp>
1124  struct _Hashtable_ebo_helper<_Nm, _Tp, false>
1125  {
1126  _Hashtable_ebo_helper() = default;
1127 
1128  template<typename _OtherTp>
1129  _Hashtable_ebo_helper(_OtherTp&& __tp)
1130  : _M_tp(std::forward<_OtherTp>(__tp))
1131  { }
1132 
1133  static const _Tp&
1134  _S_cget(const _Hashtable_ebo_helper& __eboh)
1135  { return __eboh._M_tp; }
1136 
1137  static _Tp&
1138  _S_get(_Hashtable_ebo_helper& __eboh)
1139  { return __eboh._M_tp; }
1140 
1141  private:
1142  _Tp _M_tp;
1143  };
1144 
1145  /**
1146  * Primary class template _Local_iterator_base.
1147  *
1148  * Base class for local iterators, used to iterate within a bucket
1149  * but not between buckets.
1150  */
1151  template<typename _Key, typename _Value, typename _ExtractKey,
1152  typename _H1, typename _H2, typename _Hash,
1153  bool __cache_hash_code>
1155 
1156  /**
1157  * Primary class template _Hash_code_base.
1158  *
1159  * Encapsulates two policy issues that aren't quite orthogonal.
1160  * (1) the difference between using a ranged hash function and using
1161  * the combination of a hash function and a range-hashing function.
1162  * In the former case we don't have such things as hash codes, so
1163  * we have a dummy type as placeholder.
1164  * (2) Whether or not we cache hash codes. Caching hash codes is
1165  * meaningless if we have a ranged hash function.
1166  *
1167  * We also put the key extraction objects here, for convenience.
1168  * Each specialization derives from one or more of the template
1169  * parameters to benefit from Ebo. This is important as this type
1170  * is inherited in some cases by the _Local_iterator_base type used
1171  * to implement local_iterator and const_local_iterator. As with
1172  * any iterator type we prefer to make it as small as possible.
1173  *
1174  * Primary template is unused except as a hook for specializations.
1175  */
1176  template<typename _Key, typename _Value, typename _ExtractKey,
1177  typename _H1, typename _H2, typename _Hash,
1178  bool __cache_hash_code>
1180 
1181  /// Specialization: ranged hash function, no caching hash codes. H1
1182  /// and H2 are provided but ignored. We define a dummy hash code type.
1183  template<typename _Key, typename _Value, typename _ExtractKey,
1184  typename _H1, typename _H2, typename _Hash>
1185  struct _Hash_code_base<_Key, _Value, _ExtractKey, _H1, _H2, _Hash, false>
1186  : private _Hashtable_ebo_helper<0, _ExtractKey>,
1187  private _Hashtable_ebo_helper<1, _Hash>
1188  {
1189  private:
1192 
1193  protected:
1194  typedef void* __hash_code;
1196 
1197  // We need the default constructor for the local iterators and _Hashtable
1198  // default constructor.
1199  _Hash_code_base() = default;
1200 
1201  _Hash_code_base(const _ExtractKey& __ex, const _H1&, const _H2&,
1202  const _Hash& __h)
1203  : __ebo_extract_key(__ex), __ebo_hash(__h) { }
1204 
1205  __hash_code
1206  _M_hash_code(const _Key& __key) const
1207  { return 0; }
1208 
1209  std::size_t
1210  _M_bucket_index(const _Key& __k, __hash_code, std::size_t __n) const
1211  { return _M_ranged_hash()(__k, __n); }
1212 
1213  std::size_t
1214  _M_bucket_index(const __node_type* __p, std::size_t __n) const
1215  noexcept( noexcept(declval<const _Hash&>()(declval<const _Key&>(),
1216  (std::size_t)0)) )
1217  { return _M_ranged_hash()(_M_extract()(__p->_M_v()), __n); }
1218 
1219  void
1220  _M_store_code(__node_type*, __hash_code) const
1221  { }
1222 
1223  void
1224  _M_copy_code(__node_type*, const __node_type*) const
1225  { }
1226 
1227  void
1228  _M_swap(_Hash_code_base& __x)
1229  {
1230  std::swap(_M_extract(), __x._M_extract());
1231  std::swap(_M_ranged_hash(), __x._M_ranged_hash());
1232  }
1233 
1234  const _ExtractKey&
1235  _M_extract() const { return __ebo_extract_key::_S_cget(*this); }
1236 
1237  _ExtractKey&
1238  _M_extract() { return __ebo_extract_key::_S_get(*this); }
1239 
1240  const _Hash&
1241  _M_ranged_hash() const { return __ebo_hash::_S_cget(*this); }
1242 
1243  _Hash&
1244  _M_ranged_hash() { return __ebo_hash::_S_get(*this); }
1245  };
1246 
1247  // No specialization for ranged hash function while caching hash codes.
1248  // That combination is meaningless, and trying to do it is an error.
1249 
1250  /// Specialization: ranged hash function, cache hash codes. This
1251  /// combination is meaningless, so we provide only a declaration
1252  /// and no definition.
1253  template<typename _Key, typename _Value, typename _ExtractKey,
1254  typename _H1, typename _H2, typename _Hash>
1255  struct _Hash_code_base<_Key, _Value, _ExtractKey, _H1, _H2, _Hash, true>;
1256 
1257  /// Specialization: hash function and range-hashing function, no
1258  /// caching of hash codes.
1259  /// Provides typedef and accessor required by C++ 11.
1260  template<typename _Key, typename _Value, typename _ExtractKey,
1261  typename _H1, typename _H2>
1262  struct _Hash_code_base<_Key, _Value, _ExtractKey, _H1, _H2,
1263  _Default_ranged_hash, false>
1264  : private _Hashtable_ebo_helper<0, _ExtractKey>,
1265  private _Hashtable_ebo_helper<1, _H1>,
1266  private _Hashtable_ebo_helper<2, _H2>
1267  {
1268  private:
1272 
1273  // Gives the local iterator implementation access to _M_bucket_index().
1274  friend struct _Local_iterator_base<_Key, _Value, _ExtractKey, _H1, _H2,
1275  _Default_ranged_hash, false>;
1276 
1277  public:
1278  typedef _H1 hasher;
1279 
1280  hasher
1281  hash_function() const
1282  { return _M_h1(); }
1283 
1284  protected:
1285  typedef std::size_t __hash_code;
1287 
1288  // We need the default constructor for the local iterators and _Hashtable
1289  // default constructor.
1290  _Hash_code_base() = default;
1291 
1292  _Hash_code_base(const _ExtractKey& __ex,
1293  const _H1& __h1, const _H2& __h2,
1294  const _Default_ranged_hash&)
1295  : __ebo_extract_key(__ex), __ebo_h1(__h1), __ebo_h2(__h2) { }
1296 
1297  __hash_code
1298  _M_hash_code(const _Key& __k) const
1299  {
1300  static_assert(__is_invocable<const _H1&, const _Key&>{},
1301  "hash function must be invocable with an argument of key type");
1302  return _M_h1()(__k);
1303  }
1304 
1305  std::size_t
1306  _M_bucket_index(const _Key&, __hash_code __c, std::size_t __n) const
1307  { return _M_h2()(__c, __n); }
1308 
1309  std::size_t
1310  _M_bucket_index(const __node_type* __p, std::size_t __n) const
1311  noexcept( noexcept(declval<const _H1&>()(declval<const _Key&>()))
1312  && noexcept(declval<const _H2&>()((__hash_code)0,
1313  (std::size_t)0)) )
1314  { return _M_h2()(_M_h1()(_M_extract()(__p->_M_v())), __n); }
1315 
1316  void
1317  _M_store_code(__node_type*, __hash_code) const
1318  { }
1319 
1320  void
1321  _M_copy_code(__node_type*, const __node_type*) const
1322  { }
1323 
1324  void
1325  _M_swap(_Hash_code_base& __x)
1326  {
1327  std::swap(_M_extract(), __x._M_extract());
1328  std::swap(_M_h1(), __x._M_h1());
1329  std::swap(_M_h2(), __x._M_h2());
1330  }
1331 
1332  const _ExtractKey&
1333  _M_extract() const { return __ebo_extract_key::_S_cget(*this); }
1334 
1335  _ExtractKey&
1336  _M_extract() { return __ebo_extract_key::_S_get(*this); }
1337 
1338  const _H1&
1339  _M_h1() const { return __ebo_h1::_S_cget(*this); }
1340 
1341  _H1&
1342  _M_h1() { return __ebo_h1::_S_get(*this); }
1343 
1344  const _H2&
1345  _M_h2() const { return __ebo_h2::_S_cget(*this); }
1346 
1347  _H2&
1348  _M_h2() { return __ebo_h2::_S_get(*this); }
1349  };
1350 
1351  /// Specialization: hash function and range-hashing function,
1352  /// caching hash codes. H is provided but ignored. Provides
1353  /// typedef and accessor required by C++ 11.
1354  template<typename _Key, typename _Value, typename _ExtractKey,
1355  typename _H1, typename _H2>
1356  struct _Hash_code_base<_Key, _Value, _ExtractKey, _H1, _H2,
1357  _Default_ranged_hash, true>
1358  : private _Hashtable_ebo_helper<0, _ExtractKey>,
1359  private _Hashtable_ebo_helper<1, _H1>,
1360  private _Hashtable_ebo_helper<2, _H2>
1361  {
1362  private:
1363  // Gives the local iterator implementation access to _M_h2().
1364  friend struct _Local_iterator_base<_Key, _Value, _ExtractKey, _H1, _H2,
1365  _Default_ranged_hash, true>;
1366 
1370 
1371  public:
1372  typedef _H1 hasher;
1373 
1374  hasher
1375  hash_function() const
1376  { return _M_h1(); }
1377 
1378  protected:
1379  typedef std::size_t __hash_code;
1381 
1382  // We need the default constructor for _Hashtable default constructor.
1383  _Hash_code_base() = default;
1384  _Hash_code_base(const _ExtractKey& __ex,
1385  const _H1& __h1, const _H2& __h2,
1386  const _Default_ranged_hash&)
1387  : __ebo_extract_key(__ex), __ebo_h1(__h1), __ebo_h2(__h2) { }
1388 
1389  __hash_code
1390  _M_hash_code(const _Key& __k) const
1391  {
1392  static_assert(__is_invocable<const _H1&, const _Key&>{},
1393  "hash function must be invocable with an argument of key type");
1394  return _M_h1()(__k);
1395  }
1396 
1397  std::size_t
1398  _M_bucket_index(const _Key&, __hash_code __c,
1399  std::size_t __n) const
1400  { return _M_h2()(__c, __n); }
1401 
1402  std::size_t
1403  _M_bucket_index(const __node_type* __p, std::size_t __n) const
1404  noexcept( noexcept(declval<const _H2&>()((__hash_code)0,
1405  (std::size_t)0)) )
1406  { return _M_h2()(__p->_M_hash_code, __n); }
1407 
1408  void
1409  _M_store_code(__node_type* __n, __hash_code __c) const
1410  { __n->_M_hash_code = __c; }
1411 
1412  void
1413  _M_copy_code(__node_type* __to, const __node_type* __from) const
1414  { __to->_M_hash_code = __from->_M_hash_code; }
1415 
1416  void
1417  _M_swap(_Hash_code_base& __x)
1418  {
1419  std::swap(_M_extract(), __x._M_extract());
1420  std::swap(_M_h1(), __x._M_h1());
1421  std::swap(_M_h2(), __x._M_h2());
1422  }
1423 
1424  const _ExtractKey&
1425  _M_extract() const { return __ebo_extract_key::_S_cget(*this); }
1426 
1427  _ExtractKey&
1428  _M_extract() { return __ebo_extract_key::_S_get(*this); }
1429 
1430  const _H1&
1431  _M_h1() const { return __ebo_h1::_S_cget(*this); }
1432 
1433  _H1&
1434  _M_h1() { return __ebo_h1::_S_get(*this); }
1435 
1436  const _H2&
1437  _M_h2() const { return __ebo_h2::_S_cget(*this); }
1438 
1439  _H2&
1440  _M_h2() { return __ebo_h2::_S_get(*this); }
1441  };
1442 
1443  /**
1444  * Primary class template _Equal_helper.
1445  *
1446  */
1447  template <typename _Key, typename _Value, typename _ExtractKey,
1448  typename _Equal, typename _HashCodeType,
1449  bool __cache_hash_code>
1451 
1452  /// Specialization.
1453  template<typename _Key, typename _Value, typename _ExtractKey,
1454  typename _Equal, typename _HashCodeType>
1455  struct _Equal_helper<_Key, _Value, _ExtractKey, _Equal, _HashCodeType, true>
1456  {
1457  static bool
1458  _S_equals(const _Equal& __eq, const _ExtractKey& __extract,
1459  const _Key& __k, _HashCodeType __c, _Hash_node<_Value, true>* __n)
1460  { return __c == __n->_M_hash_code && __eq(__k, __extract(__n->_M_v())); }
1461  };
1462 
1463  /// Specialization.
1464  template<typename _Key, typename _Value, typename _ExtractKey,
1465  typename _Equal, typename _HashCodeType>
1466  struct _Equal_helper<_Key, _Value, _ExtractKey, _Equal, _HashCodeType, false>
1467  {
1468  static bool
1469  _S_equals(const _Equal& __eq, const _ExtractKey& __extract,
1470  const _Key& __k, _HashCodeType, _Hash_node<_Value, false>* __n)
1471  { return __eq(__k, __extract(__n->_M_v())); }
1472  };
1473 
1474 
1475  /// Partial specialization used when nodes contain a cached hash code.
1476  template<typename _Key, typename _Value, typename _ExtractKey,
1477  typename _H1, typename _H2, typename _Hash>
1478  struct _Local_iterator_base<_Key, _Value, _ExtractKey,
1479  _H1, _H2, _Hash, true>
1480  : private _Hashtable_ebo_helper<0, _H2>
1481  {
1482  protected:
1484  using __hash_code_base = _Hash_code_base<_Key, _Value, _ExtractKey,
1485  _H1, _H2, _Hash, true>;
1486 
1487  _Local_iterator_base() = default;
1488  _Local_iterator_base(const __hash_code_base& __base,
1490  std::size_t __bkt, std::size_t __bkt_count)
1491  : __base_type(__base._M_h2()),
1492  _M_cur(__p), _M_bucket(__bkt), _M_bucket_count(__bkt_count) { }
1493 
1494  void
1495  _M_incr()
1496  {
1497  _M_cur = _M_cur->_M_next();
1498  if (_M_cur)
1499  {
1500  std::size_t __bkt
1501  = __base_type::_S_get(*this)(_M_cur->_M_hash_code,
1502  _M_bucket_count);
1503  if (__bkt != _M_bucket)
1504  _M_cur = nullptr;
1505  }
1506  }
1507 
1508  _Hash_node<_Value, true>* _M_cur;
1509  std::size_t _M_bucket;
1510  std::size_t _M_bucket_count;
1511 
1512  public:
1513  const void*
1514  _M_curr() const { return _M_cur; } // for equality ops
1515 
1516  std::size_t
1517  _M_get_bucket() const { return _M_bucket; } // for debug mode
1518  };
1519 
1520  // Uninitialized storage for a _Hash_code_base.
1521  // This type is DefaultConstructible and Assignable even if the
1522  // _Hash_code_base type isn't, so that _Local_iterator_base<..., false>
1523  // can be DefaultConstructible and Assignable.
1524  template<typename _Tp, bool _IsEmpty = std::is_empty<_Tp>::value>
1525  struct _Hash_code_storage
1526  {
1527  __gnu_cxx::__aligned_buffer<_Tp> _M_storage;
1528 
1529  _Tp*
1530  _M_h() { return _M_storage._M_ptr(); }
1531 
1532  const _Tp*
1533  _M_h() const { return _M_storage._M_ptr(); }
1534  };
1535 
1536  // Empty partial specialization for empty _Hash_code_base types.
1537  template<typename _Tp>
1538  struct _Hash_code_storage<_Tp, true>
1539  {
1540  static_assert( std::is_empty<_Tp>::value, "Type must be empty" );
1541 
1542  // As _Tp is an empty type there will be no bytes written/read through
1543  // the cast pointer, so no strict-aliasing violation.
1544  _Tp*
1545  _M_h() { return reinterpret_cast<_Tp*>(this); }
1546 
1547  const _Tp*
1548  _M_h() const { return reinterpret_cast<const _Tp*>(this); }
1549  };
1550 
1551  template<typename _Key, typename _Value, typename _ExtractKey,
1552  typename _H1, typename _H2, typename _Hash>
1553  using __hash_code_for_local_iter
1554  = _Hash_code_storage<_Hash_code_base<_Key, _Value, _ExtractKey,
1555  _H1, _H2, _Hash, false>>;
1556 
1557  // Partial specialization used when hash codes are not cached
1558  template<typename _Key, typename _Value, typename _ExtractKey,
1559  typename _H1, typename _H2, typename _Hash>
1560  struct _Local_iterator_base<_Key, _Value, _ExtractKey,
1561  _H1, _H2, _Hash, false>
1562  : __hash_code_for_local_iter<_Key, _Value, _ExtractKey, _H1, _H2, _Hash>
1563  {
1564  protected:
1565  using __hash_code_base = _Hash_code_base<_Key, _Value, _ExtractKey,
1566  _H1, _H2, _Hash, false>;
1567 
1568  _Local_iterator_base() : _M_bucket_count(-1) { }
1569 
1570  _Local_iterator_base(const __hash_code_base& __base,
1571  _Hash_node<_Value, false>* __p,
1572  std::size_t __bkt, std::size_t __bkt_count)
1573  : _M_cur(__p), _M_bucket(__bkt), _M_bucket_count(__bkt_count)
1574  { _M_init(__base); }
1575 
1576  ~_Local_iterator_base()
1577  {
1578  if (_M_bucket_count != -1)
1579  _M_destroy();
1580  }
1581 
1582  _Local_iterator_base(const _Local_iterator_base& __iter)
1583  : _M_cur(__iter._M_cur), _M_bucket(__iter._M_bucket),
1584  _M_bucket_count(__iter._M_bucket_count)
1585  {
1586  if (_M_bucket_count != -1)
1587  _M_init(*__iter._M_h());
1588  }
1589 
1590  _Local_iterator_base&
1591  operator=(const _Local_iterator_base& __iter)
1592  {
1593  if (_M_bucket_count != -1)
1594  _M_destroy();
1595  _M_cur = __iter._M_cur;
1596  _M_bucket = __iter._M_bucket;
1597  _M_bucket_count = __iter._M_bucket_count;
1598  if (_M_bucket_count != -1)
1599  _M_init(*__iter._M_h());
1600  return *this;
1601  }
1602 
1603  void
1604  _M_incr()
1605  {
1606  _M_cur = _M_cur->_M_next();
1607  if (_M_cur)
1608  {
1609  std::size_t __bkt = this->_M_h()->_M_bucket_index(_M_cur,
1610  _M_bucket_count);
1611  if (__bkt != _M_bucket)
1612  _M_cur = nullptr;
1613  }
1614  }
1615 
1616  _Hash_node<_Value, false>* _M_cur;
1617  std::size_t _M_bucket;
1618  std::size_t _M_bucket_count;
1619 
1620  void
1621  _M_init(const __hash_code_base& __base)
1622  { ::new(this->_M_h()) __hash_code_base(__base); }
1623 
1624  void
1625  _M_destroy() { this->_M_h()->~__hash_code_base(); }
1626 
1627  public:
1628  const void*
1629  _M_curr() const { return _M_cur; } // for equality ops and debug mode
1630 
1631  std::size_t
1632  _M_get_bucket() const { return _M_bucket; } // for debug mode
1633  };
1634 
1635  template<typename _Key, typename _Value, typename _ExtractKey,
1636  typename _H1, typename _H2, typename _Hash, bool __cache>
1637  inline bool
1638  operator==(const _Local_iterator_base<_Key, _Value, _ExtractKey,
1639  _H1, _H2, _Hash, __cache>& __x,
1640  const _Local_iterator_base<_Key, _Value, _ExtractKey,
1641  _H1, _H2, _Hash, __cache>& __y)
1642  { return __x._M_curr() == __y._M_curr(); }
1643 
1644  template<typename _Key, typename _Value, typename _ExtractKey,
1645  typename _H1, typename _H2, typename _Hash, bool __cache>
1646  inline bool
1647  operator!=(const _Local_iterator_base<_Key, _Value, _ExtractKey,
1648  _H1, _H2, _Hash, __cache>& __x,
1649  const _Local_iterator_base<_Key, _Value, _ExtractKey,
1650  _H1, _H2, _Hash, __cache>& __y)
1651  { return __x._M_curr() != __y._M_curr(); }
1652 
1653  /// local iterators
1654  template<typename _Key, typename _Value, typename _ExtractKey,
1655  typename _H1, typename _H2, typename _Hash,
1656  bool __constant_iterators, bool __cache>
1658  : public _Local_iterator_base<_Key, _Value, _ExtractKey,
1659  _H1, _H2, _Hash, __cache>
1660  {
1661  private:
1662  using __base_type = _Local_iterator_base<_Key, _Value, _ExtractKey,
1663  _H1, _H2, _Hash, __cache>;
1664  using __hash_code_base = typename __base_type::__hash_code_base;
1665  public:
1666  typedef _Value value_type;
1667  typedef typename std::conditional<__constant_iterators,
1668  const _Value*, _Value*>::type
1669  pointer;
1670  typedef typename std::conditional<__constant_iterators,
1671  const _Value&, _Value&>::type
1672  reference;
1673  typedef std::ptrdiff_t difference_type;
1675 
1676  _Local_iterator() = default;
1677 
1678  _Local_iterator(const __hash_code_base& __base,
1680  std::size_t __bkt, std::size_t __bkt_count)
1681  : __base_type(__base, __p, __bkt, __bkt_count)
1682  { }
1683 
1684  reference
1685  operator*() const
1686  { return this->_M_cur->_M_v(); }
1687 
1688  pointer
1689  operator->() const
1690  { return this->_M_cur->_M_valptr(); }
1691 
1693  operator++()
1694  {
1695  this->_M_incr();
1696  return *this;
1697  }
1698 
1700  operator++(int)
1701  {
1702  _Local_iterator __tmp(*this);
1703  this->_M_incr();
1704  return __tmp;
1705  }
1706  };
1707 
1708  /// local const_iterators
1709  template<typename _Key, typename _Value, typename _ExtractKey,
1710  typename _H1, typename _H2, typename _Hash,
1711  bool __constant_iterators, bool __cache>
1713  : public _Local_iterator_base<_Key, _Value, _ExtractKey,
1714  _H1, _H2, _Hash, __cache>
1715  {
1716  private:
1717  using __base_type = _Local_iterator_base<_Key, _Value, _ExtractKey,
1718  _H1, _H2, _Hash, __cache>;
1719  using __hash_code_base = typename __base_type::__hash_code_base;
1720 
1721  public:
1722  typedef _Value value_type;
1723  typedef const _Value* pointer;
1724  typedef const _Value& reference;
1725  typedef std::ptrdiff_t difference_type;
1727 
1728  _Local_const_iterator() = default;
1729 
1730  _Local_const_iterator(const __hash_code_base& __base,
1732  std::size_t __bkt, std::size_t __bkt_count)
1733  : __base_type(__base, __p, __bkt, __bkt_count)
1734  { }
1735 
1736  _Local_const_iterator(const _Local_iterator<_Key, _Value, _ExtractKey,
1737  _H1, _H2, _Hash,
1738  __constant_iterators,
1739  __cache>& __x)
1740  : __base_type(__x)
1741  { }
1742 
1743  reference
1744  operator*() const
1745  { return this->_M_cur->_M_v(); }
1746 
1747  pointer
1748  operator->() const
1749  { return this->_M_cur->_M_valptr(); }
1750 
1752  operator++()
1753  {
1754  this->_M_incr();
1755  return *this;
1756  }
1757 
1759  operator++(int)
1760  {
1761  _Local_const_iterator __tmp(*this);
1762  this->_M_incr();
1763  return __tmp;
1764  }
1765  };
1766 
1767  /**
1768  * Primary class template _Hashtable_base.
1769  *
1770  * Helper class adding management of _Equal functor to
1771  * _Hash_code_base type.
1772  *
1773  * Base class templates are:
1774  * - __detail::_Hash_code_base
1775  * - __detail::_Hashtable_ebo_helper
1776  */
1777  template<typename _Key, typename _Value,
1778  typename _ExtractKey, typename _Equal,
1779  typename _H1, typename _H2, typename _Hash, typename _Traits>
1781  : public _Hash_code_base<_Key, _Value, _ExtractKey, _H1, _H2, _Hash,
1782  _Traits::__hash_cached::value>,
1783  private _Hashtable_ebo_helper<0, _Equal>
1784  {
1785  public:
1786  typedef _Key key_type;
1787  typedef _Value value_type;
1788  typedef _Equal key_equal;
1789  typedef std::size_t size_type;
1790  typedef std::ptrdiff_t difference_type;
1791 
1792  using __traits_type = _Traits;
1793  using __hash_cached = typename __traits_type::__hash_cached;
1794  using __constant_iterators = typename __traits_type::__constant_iterators;
1795  using __unique_keys = typename __traits_type::__unique_keys;
1796 
1797  using __hash_code_base = _Hash_code_base<_Key, _Value, _ExtractKey,
1798  _H1, _H2, _Hash,
1799  __hash_cached::value>;
1800 
1801  using __hash_code = typename __hash_code_base::__hash_code;
1802  using __node_type = typename __hash_code_base::__node_type;
1803 
1804  using iterator = __detail::_Node_iterator<value_type,
1805  __constant_iterators::value,
1806  __hash_cached::value>;
1807 
1809  __constant_iterators::value,
1810  __hash_cached::value>;
1811 
1812  using local_iterator = __detail::_Local_iterator<key_type, value_type,
1813  _ExtractKey, _H1, _H2, _Hash,
1814  __constant_iterators::value,
1815  __hash_cached::value>;
1816 
1818  value_type,
1819  _ExtractKey, _H1, _H2, _Hash,
1820  __constant_iterators::value,
1821  __hash_cached::value>;
1822 
1823  using __ireturn_type = typename std::conditional<__unique_keys::value,
1825  iterator>::type;
1826  private:
1828  using _EqualHelper = _Equal_helper<_Key, _Value, _ExtractKey, _Equal,
1829  __hash_code, __hash_cached::value>;
1830 
1831  protected:
1832  _Hashtable_base() = default;
1833  _Hashtable_base(const _ExtractKey& __ex, const _H1& __h1, const _H2& __h2,
1834  const _Hash& __hash, const _Equal& __eq)
1835  : __hash_code_base(__ex, __h1, __h2, __hash), _EqualEBO(__eq)
1836  { }
1837 
1838  bool
1839  _M_equals(const _Key& __k, __hash_code __c, __node_type* __n) const
1840  {
1841  static_assert(__is_invocable<const _Equal&, const _Key&, const _Key&>{},
1842  "key equality predicate must be invocable with two arguments of "
1843  "key type");
1844  return _EqualHelper::_S_equals(_M_eq(), this->_M_extract(),
1845  __k, __c, __n);
1846  }
1847 
1848  void
1849  _M_swap(_Hashtable_base& __x)
1850  {
1851  __hash_code_base::_M_swap(__x);
1852  std::swap(_M_eq(), __x._M_eq());
1853  }
1854 
1855  const _Equal&
1856  _M_eq() const { return _EqualEBO::_S_cget(*this); }
1857 
1858  _Equal&
1859  _M_eq() { return _EqualEBO::_S_get(*this); }
1860  };
1861 
1862  /**
1863  * struct _Equality_base.
1864  *
1865  * Common types and functions for class _Equality.
1866  */
1868  {
1869  protected:
1870  template<typename _Uiterator>
1871  static bool
1872  _S_is_permutation(_Uiterator, _Uiterator, _Uiterator);
1873  };
1874 
1875  // See std::is_permutation in N3068.
1876  template<typename _Uiterator>
1877  bool
1878  _Equality_base::
1879  _S_is_permutation(_Uiterator __first1, _Uiterator __last1,
1880  _Uiterator __first2)
1881  {
1882  for (; __first1 != __last1; ++__first1, ++__first2)
1883  if (!(*__first1 == *__first2))
1884  break;
1885 
1886  if (__first1 == __last1)
1887  return true;
1888 
1889  _Uiterator __last2 = __first2;
1890  std::advance(__last2, std::distance(__first1, __last1));
1891 
1892  for (_Uiterator __it1 = __first1; __it1 != __last1; ++__it1)
1893  {
1894  _Uiterator __tmp = __first1;
1895  while (__tmp != __it1 && !bool(*__tmp == *__it1))
1896  ++__tmp;
1897 
1898  // We've seen this one before.
1899  if (__tmp != __it1)
1900  continue;
1901 
1902  std::ptrdiff_t __n2 = 0;
1903  for (__tmp = __first2; __tmp != __last2; ++__tmp)
1904  if (*__tmp == *__it1)
1905  ++__n2;
1906 
1907  if (!__n2)
1908  return false;
1909 
1910  std::ptrdiff_t __n1 = 0;
1911  for (__tmp = __it1; __tmp != __last1; ++__tmp)
1912  if (*__tmp == *__it1)
1913  ++__n1;
1914 
1915  if (__n1 != __n2)
1916  return false;
1917  }
1918  return true;
1919  }
1920 
1921  /**
1922  * Primary class template _Equality.
1923  *
1924  * This is for implementing equality comparison for unordered
1925  * containers, per N3068, by John Lakos and Pablo Halpern.
1926  * Algorithmically, we follow closely the reference implementations
1927  * therein.
1928  */
1929  template<typename _Key, typename _Value, typename _Alloc,
1930  typename _ExtractKey, typename _Equal,
1931  typename _H1, typename _H2, typename _Hash,
1932  typename _RehashPolicy, typename _Traits,
1933  bool _Unique_keys = _Traits::__unique_keys::value>
1934  struct _Equality;
1935 
1936  /// Specialization.
1937  template<typename _Key, typename _Value, typename _Alloc,
1938  typename _ExtractKey, typename _Equal,
1939  typename _H1, typename _H2, typename _Hash,
1940  typename _RehashPolicy, typename _Traits>
1941  struct _Equality<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1942  _H1, _H2, _Hash, _RehashPolicy, _Traits, true>
1943  {
1944  using __hashtable = _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1945  _H1, _H2, _Hash, _RehashPolicy, _Traits>;
1946 
1947  bool
1948  _M_equal(const __hashtable&) const;
1949  };
1950 
1951  template<typename _Key, typename _Value, typename _Alloc,
1952  typename _ExtractKey, typename _Equal,
1953  typename _H1, typename _H2, typename _Hash,
1954  typename _RehashPolicy, typename _Traits>
1955  bool
1956  _Equality<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1957  _H1, _H2, _Hash, _RehashPolicy, _Traits, true>::
1958  _M_equal(const __hashtable& __other) const
1959  {
1960  const __hashtable* __this = static_cast<const __hashtable*>(this);
1961 
1962  if (__this->size() != __other.size())
1963  return false;
1964 
1965  for (auto __itx = __this->begin(); __itx != __this->end(); ++__itx)
1966  {
1967  const auto __ity = __other.find(_ExtractKey()(*__itx));
1968  if (__ity == __other.end() || !bool(*__ity == *__itx))
1969  return false;
1970  }
1971  return true;
1972  }
1973 
1974  /// Specialization.
1975  template<typename _Key, typename _Value, typename _Alloc,
1976  typename _ExtractKey, typename _Equal,
1977  typename _H1, typename _H2, typename _Hash,
1978  typename _RehashPolicy, typename _Traits>
1979  struct _Equality<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1980  _H1, _H2, _Hash, _RehashPolicy, _Traits, false>
1981  : public _Equality_base
1982  {
1983  using __hashtable = _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1984  _H1, _H2, _Hash, _RehashPolicy, _Traits>;
1985 
1986  bool
1987  _M_equal(const __hashtable&) const;
1988  };
1989 
1990  template<typename _Key, typename _Value, typename _Alloc,
1991  typename _ExtractKey, typename _Equal,
1992  typename _H1, typename _H2, typename _Hash,
1993  typename _RehashPolicy, typename _Traits>
1994  bool
1995  _Equality<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1996  _H1, _H2, _Hash, _RehashPolicy, _Traits, false>::
1997  _M_equal(const __hashtable& __other) const
1998  {
1999  const __hashtable* __this = static_cast<const __hashtable*>(this);
2000 
2001  if (__this->size() != __other.size())
2002  return false;
2003 
2004  for (auto __itx = __this->begin(); __itx != __this->end();)
2005  {
2006  const auto __xrange = __this->equal_range(_ExtractKey()(*__itx));
2007  const auto __yrange = __other.equal_range(_ExtractKey()(*__itx));
2008 
2009  if (std::distance(__xrange.first, __xrange.second)
2010  != std::distance(__yrange.first, __yrange.second))
2011  return false;
2012 
2013  if (!_S_is_permutation(__xrange.first, __xrange.second,
2014  __yrange.first))
2015  return false;
2016 
2017  __itx = __xrange.second;
2018  }
2019  return true;
2020  }
2021 
2022  /**
2023  * This type deals with all allocation and keeps an allocator instance through
2024  * inheritance to benefit from EBO when possible.
2025  */
2026  template<typename _NodeAlloc>
2027  struct _Hashtable_alloc : private _Hashtable_ebo_helper<0, _NodeAlloc>
2028  {
2029  private:
2031  public:
2032  using __node_type = typename _NodeAlloc::value_type;
2033  using __node_alloc_type = _NodeAlloc;
2034  // Use __gnu_cxx to benefit from _S_always_equal and al.
2036 
2037  using __value_alloc_traits = typename __node_alloc_traits::template
2038  rebind_traits<typename __node_type::value_type>;
2039 
2041  using __bucket_type = __node_base*;
2042  using __bucket_alloc_type =
2043  __alloc_rebind<__node_alloc_type, __bucket_type>;
2045 
2046  _Hashtable_alloc() = default;
2047  _Hashtable_alloc(const _Hashtable_alloc&) = default;
2048  _Hashtable_alloc(_Hashtable_alloc&&) = default;
2049 
2050  template<typename _Alloc>
2051  _Hashtable_alloc(_Alloc&& __a)
2052  : __ebo_node_alloc(std::forward<_Alloc>(__a))
2053  { }
2054 
2055  __node_alloc_type&
2056  _M_node_allocator()
2057  { return __ebo_node_alloc::_S_get(*this); }
2058 
2059  const __node_alloc_type&
2060  _M_node_allocator() const
2061  { return __ebo_node_alloc::_S_cget(*this); }
2062 
2063  template<typename... _Args>
2064  __node_type*
2065  _M_allocate_node(_Args&&... __args);
2066 
2067  void
2068  _M_deallocate_node(__node_type* __n);
2069 
2070  // Deallocate the linked list of nodes pointed to by __n
2071  void
2072  _M_deallocate_nodes(__node_type* __n);
2073 
2074  __bucket_type*
2075  _M_allocate_buckets(std::size_t __n);
2076 
2077  void
2078  _M_deallocate_buckets(__bucket_type*, std::size_t __n);
2079  };
2080 
2081  // Definitions of class template _Hashtable_alloc's out-of-line member
2082  // functions.
2083  template<typename _NodeAlloc>
2084  template<typename... _Args>
2085  typename _Hashtable_alloc<_NodeAlloc>::__node_type*
2087  {
2088  auto __nptr = __node_alloc_traits::allocate(_M_node_allocator(), 1);
2089  __node_type* __n = std::__to_address(__nptr);
2090  __try
2091  {
2092  ::new ((void*)__n) __node_type;
2093  __node_alloc_traits::construct(_M_node_allocator(),
2094  __n->_M_valptr(),
2095  std::forward<_Args>(__args)...);
2096  return __n;
2097  }
2098  __catch(...)
2099  {
2100  __node_alloc_traits::deallocate(_M_node_allocator(), __nptr, 1);
2101  __throw_exception_again;
2102  }
2103  }
2104 
2105  template<typename _NodeAlloc>
2106  void
2107  _Hashtable_alloc<_NodeAlloc>::_M_deallocate_node(__node_type* __n)
2108  {
2109  typedef typename __node_alloc_traits::pointer _Ptr;
2110  auto __ptr = std::pointer_traits<_Ptr>::pointer_to(*__n);
2111  __node_alloc_traits::destroy(_M_node_allocator(), __n->_M_valptr());
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
complex< _Tp > operator*(const complex< _Tp > &__x, const complex< _Tp > &__y)
Return new complex value x times y.
Definition: complex:386
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
_GLIBCXX14_CONSTEXPR std::size_t __clp2(std::size_t __n) noexcept
Compute closest power of 2.
ISO C++ entities toplevel namespace is std.
constexpr iterator_traits< _Iter >::iterator_category __iterator_category(const _Iter &)
_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.
initializer_list
tuple_element
Definition: array:359
Primary class template, tuple.
Definition: tuple:557
integral_constant
Definition: type_traits:58
Define a member typedef type to one of two argument types.
Definition: type_traits:1921
is_empty
Definition: type_traits:694
is_constructible
Definition: type_traits:874
Define a member typedef type only if a boolean constant is true.
Definition: type_traits:1907
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:83
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.