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-2013 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 namespace std _GLIBCXX_VISIBILITY(default)
35 {
36 _GLIBCXX_BEGIN_NAMESPACE_VERSION
37 
38  template<typename _Key, typename _Value, typename _Alloc,
39  typename _ExtractKey, typename _Equal,
40  typename _H1, typename _H2, typename _Hash,
41  typename _RehashPolicy, typename _Traits>
42  class _Hashtable;
43 
44 _GLIBCXX_END_NAMESPACE_VERSION
45 
46 namespace __detail
47 {
48 _GLIBCXX_BEGIN_NAMESPACE_VERSION
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 for input iterators.
62  template<class _Iterator>
63  inline typename std::iterator_traits<_Iterator>::difference_type
64  __distance_fw(_Iterator __first, _Iterator __last,
65  std::input_iterator_tag)
66  { return 0; }
67 
68  template<class _Iterator>
69  inline typename std::iterator_traits<_Iterator>::difference_type
70  __distance_fw(_Iterator __first, _Iterator __last,
71  std::forward_iterator_tag)
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  {
78  typedef typename std::iterator_traits<_Iterator>::iterator_category _Tag;
79  return __distance_fw(__first, __last, _Tag());
80  }
81 
82  // Helper type used to detect whether the hash functor is noexcept.
83  template <typename _Key, typename _Hash>
84  struct __is_noexcept_hash : std::integral_constant<bool,
85  noexcept(declval<const _Hash&>()(declval<const _Key&>()))>
86  { };
87 
88  struct _Identity
89  {
90  template<typename _Tp>
91  _Tp&&
92  operator()(_Tp&& __x) const
93  { return std::forward<_Tp>(__x); }
94  };
95 
96  struct _Select1st
97  {
98  template<typename _Tp>
99  auto
100  operator()(_Tp&& __x) const
101  -> decltype(std::get<0>(std::forward<_Tp>(__x)))
102  { return std::get<0>(std::forward<_Tp>(__x)); }
103  };
104 
105  // Auxiliary types used for all instantiations of _Hashtable nodes
106  // and iterators.
107 
108  /**
109  * struct _Hashtable_traits
110  *
111  * Important traits for hash tables.
112  *
113  * @tparam _Cache_hash_code Boolean value. True if the value of
114  * the hash function is stored along with the value. This is a
115  * time-space tradeoff. Storing it may improve lookup speed by
116  * reducing the number of times we need to call the _Equal
117  * function.
118  *
119  * @tparam _Constant_iterators Boolean value. True if iterator and
120  * const_iterator are both constant iterator types. This is true
121  * for unordered_set and unordered_multiset, false for
122  * unordered_map and unordered_multimap.
123  *
124  * @tparam _Unique_keys Boolean value. True if the return value
125  * of _Hashtable::count(k) is always at most one, false if it may
126  * be an arbitrary number. This is true for unordered_set and
127  * unordered_map, false for unordered_multiset and
128  * unordered_multimap.
129  */
130  template<bool _Cache_hash_code, bool _Constant_iterators, bool _Unique_keys>
131  struct _Hashtable_traits
132  {
133  template<bool _Cond>
134  using __bool_constant = integral_constant<bool, _Cond>;
135 
136  using __hash_cached = __bool_constant<_Cache_hash_code>;
137  using __constant_iterators = __bool_constant<_Constant_iterators>;
138  using __unique_keys = __bool_constant<_Unique_keys>;
139  };
140 
141  /**
142  * struct _Hash_node_base
143  *
144  * Nodes, used to wrap elements stored in the hash table. A policy
145  * template parameter of class template _Hashtable controls whether
146  * nodes also store a hash code. In some cases (e.g. strings) this
147  * may be a performance win.
148  */
149  struct _Hash_node_base
150  {
151  _Hash_node_base* _M_nxt;
152 
153  _Hash_node_base() : _M_nxt() { }
154 
155  _Hash_node_base(_Hash_node_base* __next) : _M_nxt(__next) { }
156  };
157 
158  /**
159  * Primary template struct _Hash_node.
160  */
161  template<typename _Value, bool _Cache_hash_code>
162  struct _Hash_node;
163 
164  /**
165  * Specialization for nodes with caches, struct _Hash_node.
166  *
167  * Base class is __detail::_Hash_node_base.
168  */
169  template<typename _Value>
170  struct _Hash_node<_Value, true> : _Hash_node_base
171  {
172  _Value _M_v;
173  std::size_t _M_hash_code;
174 
175  template<typename... _Args>
176  _Hash_node(_Args&&... __args)
177  : _M_v(std::forward<_Args>(__args)...), _M_hash_code() { }
178 
179  _Hash_node*
180  _M_next() const { return static_cast<_Hash_node*>(_M_nxt); }
181  };
182 
183  /**
184  * Specialization for nodes without caches, struct _Hash_node.
185  *
186  * Base class is __detail::_Hash_node_base.
187  */
188  template<typename _Value>
189  struct _Hash_node<_Value, false> : _Hash_node_base
190  {
191  _Value _M_v;
192 
193  template<typename... _Args>
194  _Hash_node(_Args&&... __args)
195  : _M_v(std::forward<_Args>(__args)...) { }
196 
197  _Hash_node*
198  _M_next() const { return static_cast<_Hash_node*>(_M_nxt); }
199  };
200 
201  /// Base class for node iterators.
202  template<typename _Value, bool _Cache_hash_code>
203  struct _Node_iterator_base
204  {
205  using __node_type = _Hash_node<_Value, _Cache_hash_code>;
206 
207  __node_type* _M_cur;
208 
209  _Node_iterator_base(__node_type* __p)
210  : _M_cur(__p) { }
211 
212  void
213  _M_incr()
214  { _M_cur = _M_cur->_M_next(); }
215  };
216 
217  template<typename _Value, bool _Cache_hash_code>
218  inline bool
219  operator==(const _Node_iterator_base<_Value, _Cache_hash_code>& __x,
220  const _Node_iterator_base<_Value, _Cache_hash_code >& __y)
221  { return __x._M_cur == __y._M_cur; }
222 
223  template<typename _Value, bool _Cache_hash_code>
224  inline bool
225  operator!=(const _Node_iterator_base<_Value, _Cache_hash_code>& __x,
226  const _Node_iterator_base<_Value, _Cache_hash_code>& __y)
227  { return __x._M_cur != __y._M_cur; }
228 
229  /// Node iterators, used to iterate through all the hashtable.
230  template<typename _Value, bool __constant_iterators, bool __cache>
231  struct _Node_iterator
232  : public _Node_iterator_base<_Value, __cache>
233  {
234  private:
235  using __base_type = _Node_iterator_base<_Value, __cache>;
236  using __node_type = typename __base_type::__node_type;
237 
238  public:
239  typedef _Value value_type;
240  typedef std::ptrdiff_t difference_type;
241  typedef std::forward_iterator_tag iterator_category;
242 
243  using pointer = typename std::conditional<__constant_iterators,
244  const _Value*, _Value*>::type;
245 
246  using reference = typename std::conditional<__constant_iterators,
247  const _Value&, _Value&>::type;
248 
249  _Node_iterator()
250  : __base_type(0) { }
251 
252  explicit
253  _Node_iterator(__node_type* __p)
254  : __base_type(__p) { }
255 
256  reference
257  operator*() const
258  { return this->_M_cur->_M_v; }
259 
260  pointer
261  operator->() const
262  { return std::__addressof(this->_M_cur->_M_v); }
263 
264  _Node_iterator&
265  operator++()
266  {
267  this->_M_incr();
268  return *this;
269  }
270 
271  _Node_iterator
272  operator++(int)
273  {
274  _Node_iterator __tmp(*this);
275  this->_M_incr();
276  return __tmp;
277  }
278  };
279 
280  /// Node const_iterators, used to iterate through all the hashtable.
281  template<typename _Value, bool __constant_iterators, bool __cache>
282  struct _Node_const_iterator
283  : public _Node_iterator_base<_Value, __cache>
284  {
285  private:
286  using __base_type = _Node_iterator_base<_Value, __cache>;
287  using __node_type = typename __base_type::__node_type;
288 
289  public:
290  typedef _Value value_type;
291  typedef std::ptrdiff_t difference_type;
292  typedef std::forward_iterator_tag iterator_category;
293 
294  typedef const _Value* pointer;
295  typedef const _Value& reference;
296 
297  _Node_const_iterator()
298  : __base_type(0) { }
299 
300  explicit
301  _Node_const_iterator(__node_type* __p)
302  : __base_type(__p) { }
303 
304  _Node_const_iterator(const _Node_iterator<_Value, __constant_iterators,
305  __cache>& __x)
306  : __base_type(__x._M_cur) { }
307 
308  reference
309  operator*() const
310  { return this->_M_cur->_M_v; }
311 
312  pointer
313  operator->() const
314  { return std::__addressof(this->_M_cur->_M_v); }
315 
316  _Node_const_iterator&
317  operator++()
318  {
319  this->_M_incr();
320  return *this;
321  }
322 
323  _Node_const_iterator
324  operator++(int)
325  {
326  _Node_const_iterator __tmp(*this);
327  this->_M_incr();
328  return __tmp;
329  }
330  };
331 
332  // Many of class template _Hashtable's template parameters are policy
333  // classes. These are defaults for the policies.
334 
335  /// Default range hashing function: use division to fold a large number
336  /// into the range [0, N).
337  struct _Mod_range_hashing
338  {
339  typedef std::size_t first_argument_type;
340  typedef std::size_t second_argument_type;
341  typedef std::size_t result_type;
342 
343  result_type
344  operator()(first_argument_type __num, second_argument_type __den) const
345  { return __num % __den; }
346  };
347 
348  /// Default ranged hash function H. In principle it should be a
349  /// function object composed from objects of type H1 and H2 such that
350  /// h(k, N) = h2(h1(k), N), but that would mean making extra copies of
351  /// h1 and h2. So instead we'll just use a tag to tell class template
352  /// hashtable to do that composition.
353  struct _Default_ranged_hash { };
354 
355  /// Default value for rehash policy. Bucket size is (usually) the
356  /// smallest prime that keeps the load factor small enough.
357  struct _Prime_rehash_policy
358  {
359  _Prime_rehash_policy(float __z = 1.0)
360  : _M_max_load_factor(__z), _M_next_resize(0) { }
361 
362  float
363  max_load_factor() const noexcept
364  { return _M_max_load_factor; }
365 
366  // Return a bucket size no smaller than n.
367  std::size_t
368  _M_next_bkt(std::size_t __n) const;
369 
370  // Return a bucket count appropriate for n elements
371  std::size_t
372  _M_bkt_for_elements(std::size_t __n) const
373  { return __builtin_ceil(__n / (long double)_M_max_load_factor); }
374 
375  // __n_bkt is current bucket count, __n_elt is current element count,
376  // and __n_ins is number of elements to be inserted. Do we need to
377  // increase bucket count? If so, return make_pair(true, n), where n
378  // is the new bucket count. If not, return make_pair(false, 0).
379  std::pair<bool, std::size_t>
380  _M_need_rehash(std::size_t __n_bkt, std::size_t __n_elt,
381  std::size_t __n_ins) const;
382 
383  typedef std::size_t _State;
384 
385  _State
386  _M_state() const
387  { return _M_next_resize; }
388 
389  void
390  _M_reset(_State __state)
391  { _M_next_resize = __state; }
392 
393  enum { _S_n_primes = sizeof(unsigned long) != 8 ? 256 : 256 + 48 };
394 
395  static const std::size_t _S_growth_factor = 2;
396 
397  float _M_max_load_factor;
398  mutable std::size_t _M_next_resize;
399  };
400 
401  // Base classes for std::_Hashtable. We define these base classes
402  // because in some cases we want to do different things depending on
403  // the value of a policy class. In some cases the policy class
404  // affects which member functions and nested typedefs are defined;
405  // we handle that by specializing base class templates. Several of
406  // the base class templates need to access other members of class
407  // template _Hashtable, so we use a variant of the "Curiously
408  // Recurring Template Pattern" (CRTP) technique.
409 
410  /**
411  * Primary class template _Map_base.
412  *
413  * If the hashtable has a value type of the form pair<T1, T2> and a
414  * key extraction policy (_ExtractKey) that returns the first part
415  * of the pair, the hashtable gets a mapped_type typedef. If it
416  * satisfies those criteria and also has unique keys, then it also
417  * gets an operator[].
418  */
419  template<typename _Key, typename _Value, typename _Alloc,
420  typename _ExtractKey, typename _Equal,
421  typename _H1, typename _H2, typename _Hash,
422  typename _RehashPolicy, typename _Traits,
423  bool _Unique_keys = _Traits::__unique_keys::value>
424  struct _Map_base { };
425 
426  /// Partial specialization, __unique_keys set to false.
427  template<typename _Key, typename _Pair, typename _Alloc, typename _Equal,
428  typename _H1, typename _H2, typename _Hash,
429  typename _RehashPolicy, typename _Traits>
430  struct _Map_base<_Key, _Pair, _Alloc, _Select1st, _Equal,
431  _H1, _H2, _Hash, _RehashPolicy, _Traits, false>
432  {
433  using mapped_type = typename std::tuple_element<1, _Pair>::type;
434  };
435 
436  /// Partial specialization, __unique_keys set to true.
437  template<typename _Key, typename _Pair, typename _Alloc, typename _Equal,
438  typename _H1, typename _H2, typename _Hash,
439  typename _RehashPolicy, typename _Traits>
440  struct _Map_base<_Key, _Pair, _Alloc, _Select1st, _Equal,
441  _H1, _H2, _Hash, _RehashPolicy, _Traits, true>
442  {
443  private:
444  using __hashtable_base = __detail::_Hashtable_base<_Key, _Pair,
445  _Select1st,
446  _Equal, _H1, _H2, _Hash,
447  _Traits>;
448 
449  using __hashtable = _Hashtable<_Key, _Pair, _Alloc,
450  _Select1st, _Equal,
451  _H1, _H2, _Hash, _RehashPolicy, _Traits>;
452 
453  using __hash_code = typename __hashtable_base::__hash_code;
454  using __node_type = typename __hashtable_base::__node_type;
455 
456  public:
457  using key_type = typename __hashtable_base::key_type;
458  using iterator = typename __hashtable_base::iterator;
459  using mapped_type = typename std::tuple_element<1, _Pair>::type;
460 
461  mapped_type&
462  operator[](const key_type& __k);
463 
464  mapped_type&
465  operator[](key_type&& __k);
466 
467  // _GLIBCXX_RESOLVE_LIB_DEFECTS
468  // DR 761. unordered_map needs an at() member function.
469  mapped_type&
470  at(const key_type& __k);
471 
472  const mapped_type&
473  at(const key_type& __k) const;
474  };
475 
476  template<typename _Key, typename _Pair, typename _Alloc, typename _Equal,
477  typename _H1, typename _H2, typename _Hash,
478  typename _RehashPolicy, typename _Traits>
479  typename _Map_base<_Key, _Pair, _Alloc, _Select1st, _Equal,
480  _H1, _H2, _Hash, _RehashPolicy, _Traits, true>
481  ::mapped_type&
482  _Map_base<_Key, _Pair, _Alloc, _Select1st, _Equal,
483  _H1, _H2, _Hash, _RehashPolicy, _Traits, true>::
484  operator[](const key_type& __k)
485  {
486  __hashtable* __h = static_cast<__hashtable*>(this);
487  __hash_code __code = __h->_M_hash_code(__k);
488  std::size_t __n = __h->_M_bucket_index(__k, __code);
489  __node_type* __p = __h->_M_find_node(__n, __k, __code);
490 
491  if (!__p)
492  {
493  __p = __h->_M_allocate_node(std::piecewise_construct,
494  std::tuple<const key_type&>(__k),
495  std::tuple<>());
496  return __h->_M_insert_unique_node(__n, __code, __p)->second;
497  }
498 
499  return (__p->_M_v).second;
500  }
501 
502  template<typename _Key, typename _Pair, typename _Alloc, typename _Equal,
503  typename _H1, typename _H2, typename _Hash,
504  typename _RehashPolicy, typename _Traits>
505  typename _Map_base<_Key, _Pair, _Alloc, _Select1st, _Equal,
506  _H1, _H2, _Hash, _RehashPolicy, _Traits, true>
507  ::mapped_type&
508  _Map_base<_Key, _Pair, _Alloc, _Select1st, _Equal,
509  _H1, _H2, _Hash, _RehashPolicy, _Traits, true>::
510  operator[](key_type&& __k)
511  {
512  __hashtable* __h = static_cast<__hashtable*>(this);
513  __hash_code __code = __h->_M_hash_code(__k);
514  std::size_t __n = __h->_M_bucket_index(__k, __code);
515  __node_type* __p = __h->_M_find_node(__n, __k, __code);
516 
517  if (!__p)
518  {
519  __p = __h->_M_allocate_node(std::piecewise_construct,
520  std::forward_as_tuple(std::move(__k)),
521  std::tuple<>());
522  return __h->_M_insert_unique_node(__n, __code, __p)->second;
523  }
524 
525  return (__p->_M_v).second;
526  }
527 
528  template<typename _Key, typename _Pair, typename _Alloc, typename _Equal,
529  typename _H1, typename _H2, typename _Hash,
530  typename _RehashPolicy, typename _Traits>
531  typename _Map_base<_Key, _Pair, _Alloc, _Select1st, _Equal,
532  _H1, _H2, _Hash, _RehashPolicy, _Traits, true>
533  ::mapped_type&
534  _Map_base<_Key, _Pair, _Alloc, _Select1st, _Equal,
535  _H1, _H2, _Hash, _RehashPolicy, _Traits, true>::
536  at(const key_type& __k)
537  {
538  __hashtable* __h = static_cast<__hashtable*>(this);
539  __hash_code __code = __h->_M_hash_code(__k);
540  std::size_t __n = __h->_M_bucket_index(__k, __code);
541  __node_type* __p = __h->_M_find_node(__n, __k, __code);
542 
543  if (!__p)
544  __throw_out_of_range(__N("_Map_base::at"));
545  return (__p->_M_v).second;
546  }
547 
548  template<typename _Key, typename _Pair, typename _Alloc, typename _Equal,
549  typename _H1, typename _H2, typename _Hash,
550  typename _RehashPolicy, typename _Traits>
551  const typename _Map_base<_Key, _Pair, _Alloc, _Select1st,
552  _Equal, _H1, _H2, _Hash, _RehashPolicy,
553  _Traits, true>::mapped_type&
554  _Map_base<_Key, _Pair, _Alloc, _Select1st, _Equal,
555  _H1, _H2, _Hash, _RehashPolicy, _Traits, true>::
556  at(const key_type& __k) const
557  {
558  const __hashtable* __h = static_cast<const __hashtable*>(this);
559  __hash_code __code = __h->_M_hash_code(__k);
560  std::size_t __n = __h->_M_bucket_index(__k, __code);
561  __node_type* __p = __h->_M_find_node(__n, __k, __code);
562 
563  if (!__p)
564  __throw_out_of_range(__N("_Map_base::at"));
565  return (__p->_M_v).second;
566  }
567 
568  /**
569  * Primary class template _Insert_base.
570  *
571  * insert member functions appropriate to all _Hashtables.
572  */
573  template<typename _Key, typename _Value, typename _Alloc,
574  typename _ExtractKey, typename _Equal,
575  typename _H1, typename _H2, typename _Hash,
576  typename _RehashPolicy, typename _Traits>
577  struct _Insert_base
578  {
579  using __hashtable = _Hashtable<_Key, _Value, _Alloc, _ExtractKey,
580  _Equal, _H1, _H2, _Hash,
581  _RehashPolicy, _Traits>;
582 
583  using __hashtable_base = _Hashtable_base<_Key, _Value, _ExtractKey,
584  _Equal, _H1, _H2, _Hash,
585  _Traits>;
586 
587  using value_type = typename __hashtable_base::value_type;
588  using iterator = typename __hashtable_base::iterator;
589  using const_iterator = typename __hashtable_base::const_iterator;
590  using size_type = typename __hashtable_base::size_type;
591 
592  using __unique_keys = typename __hashtable_base::__unique_keys;
593  using __ireturn_type = typename __hashtable_base::__ireturn_type;
594  using __iconv_type = typename __hashtable_base::__iconv_type;
595 
596  __hashtable&
597  _M_conjure_hashtable()
598  { return *(static_cast<__hashtable*>(this)); }
599 
600  __ireturn_type
601  insert(const value_type& __v)
602  {
603  __hashtable& __h = _M_conjure_hashtable();
604  return __h._M_insert(__v, __unique_keys());
605  }
606 
607  iterator
608  insert(const_iterator, const value_type& __v)
609  { return __iconv_type()(insert(__v)); }
610 
611  void
612  insert(initializer_list<value_type> __l)
613  { this->insert(__l.begin(), __l.end()); }
614 
615  template<typename _InputIterator>
616  void
617  insert(_InputIterator __first, _InputIterator __last);
618  };
619 
620  template<typename _Key, typename _Value, typename _Alloc,
621  typename _ExtractKey, typename _Equal,
622  typename _H1, typename _H2, typename _Hash,
623  typename _RehashPolicy, typename _Traits>
624  template<typename _InputIterator>
625  void
626  _Insert_base<_Key, _Value, _Alloc, _ExtractKey, _Equal, _H1, _H2, _Hash,
627  _RehashPolicy, _Traits>::
628  insert(_InputIterator __first, _InputIterator __last)
629  {
630  using __rehash_type = typename __hashtable::__rehash_type;
631  using __rehash_state = typename __hashtable::__rehash_state;
632  using pair_type = std::pair<bool, std::size_t>;
633 
634  size_type __n_elt = __detail::__distance_fw(__first, __last);
635 
636  __hashtable& __h = _M_conjure_hashtable();
637  __rehash_type& __rehash = __h._M_rehash_policy;
638  const __rehash_state& __saved_state = __rehash._M_state();
639  pair_type __do_rehash = __rehash._M_need_rehash(__h._M_bucket_count,
640  __h._M_element_count,
641  __n_elt);
642 
643  if (__do_rehash.first)
644  __h._M_rehash(__do_rehash.second, __saved_state);
645 
646  for (; __first != __last; ++__first)
647  __h._M_insert(*__first, __unique_keys());
648  }
649 
650  /**
651  * Primary class template _Insert.
652  *
653  * Select insert member functions appropriate to _Hashtable policy choices.
654  */
655  template<typename _Key, typename _Value, typename _Alloc,
656  typename _ExtractKey, typename _Equal,
657  typename _H1, typename _H2, typename _Hash,
658  typename _RehashPolicy, typename _Traits,
659  bool _Constant_iterators = _Traits::__constant_iterators::value,
660  bool _Unique_keys = _Traits::__unique_keys::value>
661  struct _Insert;
662 
663  /// Specialization.
664  template<typename _Key, typename _Value, typename _Alloc,
665  typename _ExtractKey, typename _Equal,
666  typename _H1, typename _H2, typename _Hash,
667  typename _RehashPolicy, typename _Traits>
668  struct _Insert<_Key, _Value, _Alloc, _ExtractKey, _Equal, _H1, _H2, _Hash,
669  _RehashPolicy, _Traits, true, true>
670  : public _Insert_base<_Key, _Value, _Alloc, _ExtractKey, _Equal,
671  _H1, _H2, _Hash, _RehashPolicy, _Traits>
672  {
673  using __base_type = _Insert_base<_Key, _Value, _Alloc, _ExtractKey,
674  _Equal, _H1, _H2, _Hash,
675  _RehashPolicy, _Traits>;
676  using value_type = typename __base_type::value_type;
677  using iterator = typename __base_type::iterator;
678  using const_iterator = typename __base_type::const_iterator;
679 
680  using __unique_keys = typename __base_type::__unique_keys;
681  using __hashtable = typename __base_type::__hashtable;
682 
683  using __base_type::insert;
684 
685  std::pair<iterator, bool>
686  insert(value_type&& __v)
687  {
688  __hashtable& __h = this->_M_conjure_hashtable();
689  return __h._M_insert(std::move(__v), __unique_keys());
690  }
691 
692  iterator
693  insert(const_iterator, value_type&& __v)
694  { return insert(std::move(__v)).first; }
695  };
696 
697  /// Specialization.
698  template<typename _Key, typename _Value, typename _Alloc,
699  typename _ExtractKey, typename _Equal,
700  typename _H1, typename _H2, typename _Hash,
701  typename _RehashPolicy, typename _Traits>
702  struct _Insert<_Key, _Value, _Alloc, _ExtractKey, _Equal, _H1, _H2, _Hash,
703  _RehashPolicy, _Traits, true, false>
704  : public _Insert_base<_Key, _Value, _Alloc, _ExtractKey, _Equal,
705  _H1, _H2, _Hash, _RehashPolicy, _Traits>
706  {
707  using __base_type = _Insert_base<_Key, _Value, _Alloc, _ExtractKey,
708  _Equal, _H1, _H2, _Hash,
709  _RehashPolicy, _Traits>;
710  using value_type = typename __base_type::value_type;
711  using iterator = typename __base_type::iterator;
712  using const_iterator = typename __base_type::const_iterator;
713 
714  using __unique_keys = typename __base_type::__unique_keys;
715  using __hashtable = typename __base_type::__hashtable;
716 
717  using __base_type::insert;
718 
719  iterator
720  insert(value_type&& __v)
721  {
722  __hashtable& __h = this->_M_conjure_hashtable();
723  return __h._M_insert(std::move(__v), __unique_keys());
724  }
725 
726  iterator
727  insert(const_iterator, value_type&& __v)
728  { return insert(std::move(__v)); }
729  };
730 
731  /// Specialization.
732  template<typename _Key, typename _Value, typename _Alloc,
733  typename _ExtractKey, typename _Equal,
734  typename _H1, typename _H2, typename _Hash,
735  typename _RehashPolicy, typename _Traits, bool _Unique_keys>
736  struct _Insert<_Key, _Value, _Alloc, _ExtractKey, _Equal, _H1, _H2, _Hash,
737  _RehashPolicy, _Traits, false, _Unique_keys>
738  : public _Insert_base<_Key, _Value, _Alloc, _ExtractKey, _Equal,
739  _H1, _H2, _Hash, _RehashPolicy, _Traits>
740  {
741  using __base_type = _Insert_base<_Key, _Value, _Alloc, _ExtractKey,
742  _Equal, _H1, _H2, _Hash,
743  _RehashPolicy, _Traits>;
744  using value_type = typename __base_type::value_type;
745  using iterator = typename __base_type::iterator;
746  using const_iterator = typename __base_type::const_iterator;
747 
748  using __unique_keys = typename __base_type::__unique_keys;
749  using __hashtable = typename __base_type::__hashtable;
750  using __ireturn_type = typename __base_type::__ireturn_type;
751  using __iconv_type = typename __base_type::__iconv_type;
752 
753  using __base_type::insert;
754 
755  template<typename _Pair>
756  using __is_cons = std::is_constructible<value_type, _Pair&&>;
757 
758  template<typename _Pair>
759  using _IFcons = std::enable_if<__is_cons<_Pair>::value>;
760 
761  template<typename _Pair>
762  using _IFconsp = typename _IFcons<_Pair>::type;
763 
764  template<typename _Pair, typename = _IFconsp<_Pair>>
765  __ireturn_type
766  insert(_Pair&& __v)
767  {
768  __hashtable& __h = this->_M_conjure_hashtable();
769  return __h._M_emplace(__unique_keys(), std::forward<_Pair>(__v));
770  }
771 
772  template<typename _Pair, typename = _IFconsp<_Pair>>
773  iterator
774  insert(const_iterator, _Pair&& __v)
775  { return __iconv_type()(insert(std::forward<_Pair>(__v))); }
776  };
777 
778  /**
779  * Primary class template _Rehash_base.
780  *
781  * Give hashtable the max_load_factor functions and reserve iff the
782  * rehash policy is _Prime_rehash_policy.
783  */
784  template<typename _Key, typename _Value, typename _Alloc,
785  typename _ExtractKey, typename _Equal,
786  typename _H1, typename _H2, typename _Hash,
787  typename _RehashPolicy, typename _Traits>
788  struct _Rehash_base;
789 
790  /// Specialization.
791  template<typename _Key, typename _Value, typename _Alloc,
792  typename _ExtractKey, typename _Equal,
793  typename _H1, typename _H2, typename _Hash, typename _Traits>
794  struct _Rehash_base<_Key, _Value, _Alloc, _ExtractKey, _Equal,
795  _H1, _H2, _Hash, _Prime_rehash_policy, _Traits>
796  {
797  using __hashtable = _Hashtable<_Key, _Value, _Alloc, _ExtractKey,
798  _Equal, _H1, _H2, _Hash,
799  _Prime_rehash_policy, _Traits>;
800 
801  float
802  max_load_factor() const noexcept
803  {
804  const __hashtable* __this = static_cast<const __hashtable*>(this);
805  return __this->__rehash_policy().max_load_factor();
806  }
807 
808  void
809  max_load_factor(float __z)
810  {
811  __hashtable* __this = static_cast<__hashtable*>(this);
812  __this->__rehash_policy(_Prime_rehash_policy(__z));
813  }
814 
815  void
816  reserve(std::size_t __n)
817  {
818  __hashtable* __this = static_cast<__hashtable*>(this);
819  __this->rehash(__builtin_ceil(__n / max_load_factor()));
820  }
821  };
822 
823  /**
824  * Primary class template _Hashtable_ebo_helper.
825  *
826  * Helper class using EBO when it is not forbidden, type is not
827  * final, and when it worth it, type is empty.
828  */
829  template<int _Nm, typename _Tp,
830  bool __use_ebo = !__is_final(_Tp) && __is_empty(_Tp)>
831  struct _Hashtable_ebo_helper;
832 
833  /// Specialization using EBO.
834  template<int _Nm, typename _Tp>
835  struct _Hashtable_ebo_helper<_Nm, _Tp, true>
836  : private _Tp
837  {
838  _Hashtable_ebo_helper() = default;
839 
840  _Hashtable_ebo_helper(const _Tp& __tp) : _Tp(__tp)
841  { }
842 
843  static const _Tp&
844  _S_cget(const _Hashtable_ebo_helper& __eboh)
845  { return static_cast<const _Tp&>(__eboh); }
846 
847  static _Tp&
848  _S_get(_Hashtable_ebo_helper& __eboh)
849  { return static_cast<_Tp&>(__eboh); }
850  };
851 
852  /// Specialization not using EBO.
853  template<int _Nm, typename _Tp>
854  struct _Hashtable_ebo_helper<_Nm, _Tp, false>
855  {
856  _Hashtable_ebo_helper() = default;
857 
858  _Hashtable_ebo_helper(const _Tp& __tp) : _M_tp(__tp)
859  { }
860 
861  static const _Tp&
862  _S_cget(const _Hashtable_ebo_helper& __eboh)
863  { return __eboh._M_tp; }
864 
865  static _Tp&
866  _S_get(_Hashtable_ebo_helper& __eboh)
867  { return __eboh._M_tp; }
868 
869  private:
870  _Tp _M_tp;
871  };
872 
873  /**
874  * Primary class template _Local_iterator_base.
875  *
876  * Base class for local iterators, used to iterate within a bucket
877  * but not between buckets.
878  */
879  template<typename _Key, typename _Value, typename _ExtractKey,
880  typename _H1, typename _H2, typename _Hash,
881  bool __cache_hash_code>
882  struct _Local_iterator_base;
883 
884  /**
885  * Primary class template _Hash_code_base.
886  *
887  * Encapsulates two policy issues that aren't quite orthogonal.
888  * (1) the difference between using a ranged hash function and using
889  * the combination of a hash function and a range-hashing function.
890  * In the former case we don't have such things as hash codes, so
891  * we have a dummy type as placeholder.
892  * (2) Whether or not we cache hash codes. Caching hash codes is
893  * meaningless if we have a ranged hash function.
894  *
895  * We also put the key extraction objects here, for convenience.
896  * Each specialization derives from one or more of the template
897  * parameters to benefit from Ebo. This is important as this type
898  * is inherited in some cases by the _Local_iterator_base type used
899  * to implement local_iterator and const_local_iterator. As with
900  * any iterator type we prefer to make it as small as possible.
901  *
902  * Primary template is unused except as a hook for specializations.
903  */
904  template<typename _Key, typename _Value, typename _ExtractKey,
905  typename _H1, typename _H2, typename _Hash,
906  bool __cache_hash_code>
907  struct _Hash_code_base;
908 
909  /// Specialization: ranged hash function, no caching hash codes. H1
910  /// and H2 are provided but ignored. We define a dummy hash code type.
911  template<typename _Key, typename _Value, typename _ExtractKey,
912  typename _H1, typename _H2, typename _Hash>
913  struct _Hash_code_base<_Key, _Value, _ExtractKey, _H1, _H2, _Hash, false>
914  : private _Hashtable_ebo_helper<0, _ExtractKey>,
915  private _Hashtable_ebo_helper<1, _Hash>
916  {
917  private:
918  using __ebo_extract_key = _Hashtable_ebo_helper<0, _ExtractKey>;
919  using __ebo_hash = _Hashtable_ebo_helper<1, _Hash>;
920 
921  protected:
922  typedef void* __hash_code;
923  typedef _Hash_node<_Value, false> __node_type;
924 
925  // We need the default constructor for the local iterators.
926  _Hash_code_base() = default;
927 
928  _Hash_code_base(const _ExtractKey& __ex, const _H1&, const _H2&,
929  const _Hash& __h)
930  : __ebo_extract_key(__ex), __ebo_hash(__h) { }
931 
932  __hash_code
933  _M_hash_code(const _Key& __key) const
934  { return 0; }
935 
936  std::size_t
937  _M_bucket_index(const _Key& __k, __hash_code, std::size_t __n) const
938  { return _M_ranged_hash()(__k, __n); }
939 
940  std::size_t
941  _M_bucket_index(const __node_type* __p, std::size_t __n) const
942  { return _M_ranged_hash()(_M_extract()(__p->_M_v), __n); }
943 
944  void
945  _M_store_code(__node_type*, __hash_code) const
946  { }
947 
948  void
949  _M_copy_code(__node_type*, const __node_type*) const
950  { }
951 
952  void
953  _M_swap(_Hash_code_base& __x)
954  {
955  std::swap(_M_extract(), __x._M_extract());
956  std::swap(_M_ranged_hash(), __x._M_ranged_hash());
957  }
958 
959  const _ExtractKey&
960  _M_extract() const { return __ebo_extract_key::_S_cget(*this); }
961 
962  _ExtractKey&
963  _M_extract() { return __ebo_extract_key::_S_get(*this); }
964 
965  const _Hash&
966  _M_ranged_hash() const { return __ebo_hash::_S_cget(*this); }
967 
968  _Hash&
969  _M_ranged_hash() { return __ebo_hash::_S_get(*this); }
970  };
971 
972  // No specialization for ranged hash function while caching hash codes.
973  // That combination is meaningless, and trying to do it is an error.
974 
975  /// Specialization: ranged hash function, cache hash codes. This
976  /// combination is meaningless, so we provide only a declaration
977  /// and no definition.
978  template<typename _Key, typename _Value, typename _ExtractKey,
979  typename _H1, typename _H2, typename _Hash>
980  struct _Hash_code_base<_Key, _Value, _ExtractKey, _H1, _H2, _Hash, true>;
981 
982  /// Specialization: hash function and range-hashing function, no
983  /// caching of hash codes.
984  /// Provides typedef and accessor required by C++ 11.
985  template<typename _Key, typename _Value, typename _ExtractKey,
986  typename _H1, typename _H2>
987  struct _Hash_code_base<_Key, _Value, _ExtractKey, _H1, _H2,
988  _Default_ranged_hash, false>
989  : private _Hashtable_ebo_helper<0, _ExtractKey>,
990  private _Hashtable_ebo_helper<1, _H1>,
991  private _Hashtable_ebo_helper<2, _H2>
992  {
993  private:
994  using __ebo_extract_key = _Hashtable_ebo_helper<0, _ExtractKey>;
995  using __ebo_h1 = _Hashtable_ebo_helper<1, _H1>;
996  using __ebo_h2 = _Hashtable_ebo_helper<2, _H2>;
997 
998  public:
999  typedef _H1 hasher;
1000 
1001  hasher
1002  hash_function() const
1003  { return _M_h1(); }
1004 
1005  protected:
1006  typedef std::size_t __hash_code;
1007  typedef _Hash_node<_Value, false> __node_type;
1008 
1009  // We need the default constructor for the local iterators.
1010  _Hash_code_base() = default;
1011 
1012  _Hash_code_base(const _ExtractKey& __ex,
1013  const _H1& __h1, const _H2& __h2,
1014  const _Default_ranged_hash&)
1015  : __ebo_extract_key(__ex), __ebo_h1(__h1), __ebo_h2(__h2) { }
1016 
1017  __hash_code
1018  _M_hash_code(const _Key& __k) const
1019  { return _M_h1()(__k); }
1020 
1021  std::size_t
1022  _M_bucket_index(const _Key&, __hash_code __c, std::size_t __n) const
1023  { return _M_h2()(__c, __n); }
1024 
1025  std::size_t
1026  _M_bucket_index(const __node_type* __p,
1027  std::size_t __n) const
1028  { return _M_h2()(_M_h1()(_M_extract()(__p->_M_v)), __n); }
1029 
1030  void
1031  _M_store_code(__node_type*, __hash_code) const
1032  { }
1033 
1034  void
1035  _M_copy_code(__node_type*, const __node_type*) const
1036  { }
1037 
1038  void
1039  _M_swap(_Hash_code_base& __x)
1040  {
1041  std::swap(_M_extract(), __x._M_extract());
1042  std::swap(_M_h1(), __x._M_h1());
1043  std::swap(_M_h2(), __x._M_h2());
1044  }
1045 
1046  const _ExtractKey&
1047  _M_extract() const { return __ebo_extract_key::_S_cget(*this); }
1048 
1049  _ExtractKey&
1050  _M_extract() { return __ebo_extract_key::_S_get(*this); }
1051 
1052  const _H1&
1053  _M_h1() const { return __ebo_h1::_S_cget(*this); }
1054 
1055  _H1&
1056  _M_h1() { return __ebo_h1::_S_get(*this); }
1057 
1058  const _H2&
1059  _M_h2() const { return __ebo_h2::_S_cget(*this); }
1060 
1061  _H2&
1062  _M_h2() { return __ebo_h2::_S_get(*this); }
1063  };
1064 
1065  /// Specialization: hash function and range-hashing function,
1066  /// caching hash codes. H is provided but ignored. Provides
1067  /// typedef and accessor required by C++ 11.
1068  template<typename _Key, typename _Value, typename _ExtractKey,
1069  typename _H1, typename _H2>
1070  struct _Hash_code_base<_Key, _Value, _ExtractKey, _H1, _H2,
1071  _Default_ranged_hash, true>
1072  : private _Hashtable_ebo_helper<0, _ExtractKey>,
1073  private _Hashtable_ebo_helper<1, _H1>,
1074  private _Hashtable_ebo_helper<2, _H2>
1075  {
1076  private:
1077  // Gives access to _M_h2() to the local iterator implementation.
1078  friend struct _Local_iterator_base<_Key, _Value, _ExtractKey, _H1, _H2,
1079  _Default_ranged_hash, true>;
1080 
1081  using __ebo_extract_key = _Hashtable_ebo_helper<0, _ExtractKey>;
1082  using __ebo_h1 = _Hashtable_ebo_helper<1, _H1>;
1083  using __ebo_h2 = _Hashtable_ebo_helper<2, _H2>;
1084 
1085  public:
1086  typedef _H1 hasher;
1087 
1088  hasher
1089  hash_function() const
1090  { return _M_h1(); }
1091 
1092  protected:
1093  typedef std::size_t __hash_code;
1094  typedef _Hash_node<_Value, true> __node_type;
1095 
1096  _Hash_code_base(const _ExtractKey& __ex,
1097  const _H1& __h1, const _H2& __h2,
1098  const _Default_ranged_hash&)
1099  : __ebo_extract_key(__ex), __ebo_h1(__h1), __ebo_h2(__h2) { }
1100 
1101  __hash_code
1102  _M_hash_code(const _Key& __k) const
1103  { return _M_h1()(__k); }
1104 
1105  std::size_t
1106  _M_bucket_index(const _Key&, __hash_code __c,
1107  std::size_t __n) const
1108  { return _M_h2()(__c, __n); }
1109 
1110  std::size_t
1111  _M_bucket_index(const __node_type* __p, std::size_t __n) const
1112  { return _M_h2()(__p->_M_hash_code, __n); }
1113 
1114  void
1115  _M_store_code(__node_type* __n, __hash_code __c) const
1116  { __n->_M_hash_code = __c; }
1117 
1118  void
1119  _M_copy_code(__node_type* __to, const __node_type* __from) const
1120  { __to->_M_hash_code = __from->_M_hash_code; }
1121 
1122  void
1123  _M_swap(_Hash_code_base& __x)
1124  {
1125  std::swap(_M_extract(), __x._M_extract());
1126  std::swap(_M_h1(), __x._M_h1());
1127  std::swap(_M_h2(), __x._M_h2());
1128  }
1129 
1130  const _ExtractKey&
1131  _M_extract() const { return __ebo_extract_key::_S_cget(*this); }
1132 
1133  _ExtractKey&
1134  _M_extract() { return __ebo_extract_key::_S_get(*this); }
1135 
1136  const _H1&
1137  _M_h1() const { return __ebo_h1::_S_cget(*this); }
1138 
1139  _H1&
1140  _M_h1() { return __ebo_h1::_S_get(*this); }
1141 
1142  const _H2&
1143  _M_h2() const { return __ebo_h2::_S_cget(*this); }
1144 
1145  _H2&
1146  _M_h2() { return __ebo_h2::_S_get(*this); }
1147  };
1148 
1149  /**
1150  * Primary class template _Equal_helper.
1151  *
1152  */
1153  template <typename _Key, typename _Value, typename _ExtractKey,
1154  typename _Equal, typename _HashCodeType,
1155  bool __cache_hash_code>
1156  struct _Equal_helper;
1157 
1158  /// Specialization.
1159  template<typename _Key, typename _Value, typename _ExtractKey,
1160  typename _Equal, typename _HashCodeType>
1161  struct _Equal_helper<_Key, _Value, _ExtractKey, _Equal, _HashCodeType, true>
1162  {
1163  static bool
1164  _S_equals(const _Equal& __eq, const _ExtractKey& __extract,
1165  const _Key& __k, _HashCodeType __c, _Hash_node<_Value, true>* __n)
1166  { return __c == __n->_M_hash_code && __eq(__k, __extract(__n->_M_v)); }
1167  };
1168 
1169  /// Specialization.
1170  template<typename _Key, typename _Value, typename _ExtractKey,
1171  typename _Equal, typename _HashCodeType>
1172  struct _Equal_helper<_Key, _Value, _ExtractKey, _Equal, _HashCodeType, false>
1173  {
1174  static bool
1175  _S_equals(const _Equal& __eq, const _ExtractKey& __extract,
1176  const _Key& __k, _HashCodeType, _Hash_node<_Value, false>* __n)
1177  { return __eq(__k, __extract(__n->_M_v)); }
1178  };
1179 
1180 
1181  /// Specialization.
1182  template<typename _Key, typename _Value, typename _ExtractKey,
1183  typename _H1, typename _H2, typename _Hash>
1184  struct _Local_iterator_base<_Key, _Value, _ExtractKey,
1185  _H1, _H2, _Hash, true>
1186  : private _Hashtable_ebo_helper<0, _H2>
1187  {
1188  protected:
1189  using __base_type = _Hashtable_ebo_helper<0, _H2>;
1190  using __hash_code_base = _Hash_code_base<_Key, _Value, _ExtractKey,
1191  _H1, _H2, _Hash, true>;
1192 
1193  public:
1194  _Local_iterator_base() = default;
1195  _Local_iterator_base(const __hash_code_base& __base,
1196  _Hash_node<_Value, true>* __p,
1197  std::size_t __bkt, std::size_t __bkt_count)
1198  : __base_type(__base._M_h2()),
1199  _M_cur(__p), _M_bucket(__bkt), _M_bucket_count(__bkt_count) { }
1200 
1201  void
1202  _M_incr()
1203  {
1204  _M_cur = _M_cur->_M_next();
1205  if (_M_cur)
1206  {
1207  std::size_t __bkt
1208  = __base_type::_S_get(*this)(_M_cur->_M_hash_code,
1209  _M_bucket_count);
1210  if (__bkt != _M_bucket)
1211  _M_cur = nullptr;
1212  }
1213  }
1214 
1215  _Hash_node<_Value, true>* _M_cur;
1216  std::size_t _M_bucket;
1217  std::size_t _M_bucket_count;
1218  };
1219 
1220  /// Specialization.
1221  template<typename _Key, typename _Value, typename _ExtractKey,
1222  typename _H1, typename _H2, typename _Hash>
1223  struct _Local_iterator_base<_Key, _Value, _ExtractKey,
1224  _H1, _H2, _Hash, false>
1225  : private _Hash_code_base<_Key, _Value, _ExtractKey,
1226  _H1, _H2, _Hash, false>
1227  {
1228  protected:
1229  using __hash_code_base = _Hash_code_base<_Key, _Value, _ExtractKey,
1230  _H1, _H2, _Hash, false>;
1231 
1232  public:
1233  _Local_iterator_base() = default;
1234  _Local_iterator_base(const __hash_code_base& __base,
1235  _Hash_node<_Value, false>* __p,
1236  std::size_t __bkt, std::size_t __bkt_count)
1237  : __hash_code_base(__base),
1238  _M_cur(__p), _M_bucket(__bkt), _M_bucket_count(__bkt_count) { }
1239 
1240  void
1241  _M_incr()
1242  {
1243  _M_cur = _M_cur->_M_next();
1244  if (_M_cur)
1245  {
1246  std::size_t __bkt = this->_M_bucket_index(_M_cur, _M_bucket_count);
1247  if (__bkt != _M_bucket)
1248  _M_cur = nullptr;
1249  }
1250  }
1251 
1252  _Hash_node<_Value, false>* _M_cur;
1253  std::size_t _M_bucket;
1254  std::size_t _M_bucket_count;
1255  };
1256 
1257  template<typename _Key, typename _Value, typename _ExtractKey,
1258  typename _H1, typename _H2, typename _Hash, bool __cache>
1259  inline bool
1260  operator==(const _Local_iterator_base<_Key, _Value, _ExtractKey,
1261  _H1, _H2, _Hash, __cache>& __x,
1262  const _Local_iterator_base<_Key, _Value, _ExtractKey,
1263  _H1, _H2, _Hash, __cache>& __y)
1264  { return __x._M_cur == __y._M_cur; }
1265 
1266  template<typename _Key, typename _Value, typename _ExtractKey,
1267  typename _H1, typename _H2, typename _Hash, bool __cache>
1268  inline bool
1269  operator!=(const _Local_iterator_base<_Key, _Value, _ExtractKey,
1270  _H1, _H2, _Hash, __cache>& __x,
1271  const _Local_iterator_base<_Key, _Value, _ExtractKey,
1272  _H1, _H2, _Hash, __cache>& __y)
1273  { return __x._M_cur != __y._M_cur; }
1274 
1275  /// local iterators
1276  template<typename _Key, typename _Value, typename _ExtractKey,
1277  typename _H1, typename _H2, typename _Hash,
1278  bool __constant_iterators, bool __cache>
1279  struct _Local_iterator
1280  : public _Local_iterator_base<_Key, _Value, _ExtractKey,
1281  _H1, _H2, _Hash, __cache>
1282  {
1283  private:
1284  using __base_type = _Local_iterator_base<_Key, _Value, _ExtractKey,
1285  _H1, _H2, _Hash, __cache>;
1286  using __hash_code_base = typename __base_type::__hash_code_base;
1287  public:
1288  typedef _Value value_type;
1289  typedef typename std::conditional<__constant_iterators,
1290  const _Value*, _Value*>::type
1291  pointer;
1292  typedef typename std::conditional<__constant_iterators,
1293  const _Value&, _Value&>::type
1294  reference;
1295  typedef std::ptrdiff_t difference_type;
1296  typedef std::forward_iterator_tag iterator_category;
1297 
1298  _Local_iterator() = default;
1299 
1300  _Local_iterator(const __hash_code_base& __base,
1301  _Hash_node<_Value, __cache>* __p,
1302  std::size_t __bkt, std::size_t __bkt_count)
1303  : __base_type(__base, __p, __bkt, __bkt_count)
1304  { }
1305 
1306  reference
1307  operator*() const
1308  { return this->_M_cur->_M_v; }
1309 
1310  pointer
1311  operator->() const
1312  { return std::__addressof(this->_M_cur->_M_v); }
1313 
1314  _Local_iterator&
1315  operator++()
1316  {
1317  this->_M_incr();
1318  return *this;
1319  }
1320 
1321  _Local_iterator
1322  operator++(int)
1323  {
1324  _Local_iterator __tmp(*this);
1325  this->_M_incr();
1326  return __tmp;
1327  }
1328  };
1329 
1330  /// local const_iterators
1331  template<typename _Key, typename _Value, typename _ExtractKey,
1332  typename _H1, typename _H2, typename _Hash,
1333  bool __constant_iterators, bool __cache>
1334  struct _Local_const_iterator
1335  : public _Local_iterator_base<_Key, _Value, _ExtractKey,
1336  _H1, _H2, _Hash, __cache>
1337  {
1338  private:
1339  using __base_type = _Local_iterator_base<_Key, _Value, _ExtractKey,
1340  _H1, _H2, _Hash, __cache>;
1341  using __hash_code_base = typename __base_type::__hash_code_base;
1342 
1343  public:
1344  typedef _Value value_type;
1345  typedef const _Value* pointer;
1346  typedef const _Value& reference;
1347  typedef std::ptrdiff_t difference_type;
1348  typedef std::forward_iterator_tag iterator_category;
1349 
1350  _Local_const_iterator() = default;
1351 
1352  _Local_const_iterator(const __hash_code_base& __base,
1353  _Hash_node<_Value, __cache>* __p,
1354  std::size_t __bkt, std::size_t __bkt_count)
1355  : __base_type(__base, __p, __bkt, __bkt_count)
1356  { }
1357 
1358  _Local_const_iterator(const _Local_iterator<_Key, _Value, _ExtractKey,
1359  _H1, _H2, _Hash,
1360  __constant_iterators,
1361  __cache>& __x)
1362  : __base_type(__x)
1363  { }
1364 
1365  reference
1366  operator*() const
1367  { return this->_M_cur->_M_v; }
1368 
1369  pointer
1370  operator->() const
1371  { return std::__addressof(this->_M_cur->_M_v); }
1372 
1373  _Local_const_iterator&
1374  operator++()
1375  {
1376  this->_M_incr();
1377  return *this;
1378  }
1379 
1380  _Local_const_iterator
1381  operator++(int)
1382  {
1383  _Local_const_iterator __tmp(*this);
1384  this->_M_incr();
1385  return __tmp;
1386  }
1387  };
1388 
1389  /**
1390  * Primary class template _Hashtable_base.
1391  *
1392  * Helper class adding management of _Equal functor to
1393  * _Hash_code_base type.
1394  *
1395  * Base class templates are:
1396  * - __detail::_Hash_code_base
1397  * - __detail::_Hashtable_ebo_helper
1398  */
1399  template<typename _Key, typename _Value,
1400  typename _ExtractKey, typename _Equal,
1401  typename _H1, typename _H2, typename _Hash, typename _Traits>
1402  struct _Hashtable_base
1403  : public _Hash_code_base<_Key, _Value, _ExtractKey, _H1, _H2, _Hash,
1404  _Traits::__hash_cached::value>,
1405  private _Hashtable_ebo_helper<0, _Equal>
1406  {
1407  public:
1408  typedef _Key key_type;
1409  typedef _Value value_type;
1410  typedef _Equal key_equal;
1411  typedef std::size_t size_type;
1412  typedef std::ptrdiff_t difference_type;
1413 
1414  using __traits_type = _Traits;
1415  using __hash_cached = typename __traits_type::__hash_cached;
1416  using __constant_iterators = typename __traits_type::__constant_iterators;
1417  using __unique_keys = typename __traits_type::__unique_keys;
1418 
1419  using __hash_code_base = _Hash_code_base<_Key, _Value, _ExtractKey,
1420  _H1, _H2, _Hash,
1421  __hash_cached::value>;
1422 
1423  using __hash_code = typename __hash_code_base::__hash_code;
1424  using __node_type = typename __hash_code_base::__node_type;
1425 
1426  using iterator = __detail::_Node_iterator<value_type,
1427  __constant_iterators::value,
1428  __hash_cached::value>;
1429 
1430  using const_iterator = __detail::_Node_const_iterator<value_type,
1431  __constant_iterators::value,
1432  __hash_cached::value>;
1433 
1434  using local_iterator = __detail::_Local_iterator<key_type, value_type,
1435  _ExtractKey, _H1, _H2, _Hash,
1436  __constant_iterators::value,
1437  __hash_cached::value>;
1438 
1439  using const_local_iterator = __detail::_Local_const_iterator<key_type,
1440  value_type,
1441  _ExtractKey, _H1, _H2, _Hash,
1442  __constant_iterators::value,
1443  __hash_cached::value>;
1444 
1445  using __ireturn_type = typename std::conditional<__unique_keys::value,
1446  std::pair<iterator, bool>,
1447  iterator>::type;
1448 
1449  using __iconv_type = typename std::conditional<__unique_keys::value,
1450  _Select1st, _Identity
1451  >::type;
1452  private:
1453  using _EqualEBO = _Hashtable_ebo_helper<0, _Equal>;
1454  using _EqualHelper = _Equal_helper<_Key, _Value, _ExtractKey, _Equal,
1455  __hash_code, __hash_cached::value>;
1456 
1457  protected:
1458  using __node_base = __detail::_Hash_node_base;
1459  using __bucket_type = __node_base*;
1460 
1461  _Hashtable_base(const _ExtractKey& __ex, const _H1& __h1, const _H2& __h2,
1462  const _Hash& __hash, const _Equal& __eq)
1463  : __hash_code_base(__ex, __h1, __h2, __hash), _EqualEBO(__eq)
1464  { }
1465 
1466  bool
1467  _M_equals(const _Key& __k, __hash_code __c, __node_type* __n) const
1468  {
1469  return _EqualHelper::_S_equals(_M_eq(), this->_M_extract(),
1470  __k, __c, __n);
1471  }
1472 
1473  void
1474  _M_swap(_Hashtable_base& __x)
1475  {
1476  __hash_code_base::_M_swap(__x);
1477  std::swap(_M_eq(), __x._M_eq());
1478  }
1479 
1480  const _Equal&
1481  _M_eq() const { return _EqualEBO::_S_cget(*this); }
1482 
1483  _Equal&
1484  _M_eq() { return _EqualEBO::_S_get(*this); }
1485  };
1486 
1487  /**
1488  * struct _Equality_base.
1489  *
1490  * Common types and functions for class _Equality.
1491  */
1492  struct _Equality_base
1493  {
1494  protected:
1495  template<typename _Uiterator>
1496  static bool
1497  _S_is_permutation(_Uiterator, _Uiterator, _Uiterator);
1498  };
1499 
1500  // See std::is_permutation in N3068.
1501  template<typename _Uiterator>
1502  bool
1503  _Equality_base::
1504  _S_is_permutation(_Uiterator __first1, _Uiterator __last1,
1505  _Uiterator __first2)
1506  {
1507  for (; __first1 != __last1; ++__first1, ++__first2)
1508  if (!(*__first1 == *__first2))
1509  break;
1510 
1511  if (__first1 == __last1)
1512  return true;
1513 
1514  _Uiterator __last2 = __first2;
1515  std::advance(__last2, std::distance(__first1, __last1));
1516 
1517  for (_Uiterator __it1 = __first1; __it1 != __last1; ++__it1)
1518  {
1519  _Uiterator __tmp = __first1;
1520  while (__tmp != __it1 && !bool(*__tmp == *__it1))
1521  ++__tmp;
1522 
1523  // We've seen this one before.
1524  if (__tmp != __it1)
1525  continue;
1526 
1527  std::ptrdiff_t __n2 = 0;
1528  for (__tmp = __first2; __tmp != __last2; ++__tmp)
1529  if (*__tmp == *__it1)
1530  ++__n2;
1531 
1532  if (!__n2)
1533  return false;
1534 
1535  std::ptrdiff_t __n1 = 0;
1536  for (__tmp = __it1; __tmp != __last1; ++__tmp)
1537  if (*__tmp == *__it1)
1538  ++__n1;
1539 
1540  if (__n1 != __n2)
1541  return false;
1542  }
1543  return true;
1544  }
1545 
1546  /**
1547  * Primary class template _Equality.
1548  *
1549  * This is for implementing equality comparison for unordered
1550  * containers, per N3068, by John Lakos and Pablo Halpern.
1551  * Algorithmically, we follow closely the reference implementations
1552  * therein.
1553  */
1554  template<typename _Key, typename _Value, typename _Alloc,
1555  typename _ExtractKey, typename _Equal,
1556  typename _H1, typename _H2, typename _Hash,
1557  typename _RehashPolicy, typename _Traits,
1558  bool _Unique_keys = _Traits::__unique_keys::value>
1559  struct _Equality;
1560 
1561  /// Specialization.
1562  template<typename _Key, typename _Value, typename _Alloc,
1563  typename _ExtractKey, typename _Equal,
1564  typename _H1, typename _H2, typename _Hash,
1565  typename _RehashPolicy, typename _Traits>
1566  struct _Equality<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1567  _H1, _H2, _Hash, _RehashPolicy, _Traits, true>
1568  {
1569  using __hashtable = _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1570  _H1, _H2, _Hash, _RehashPolicy, _Traits>;
1571 
1572  bool
1573  _M_equal(const __hashtable&) const;
1574  };
1575 
1576  template<typename _Key, typename _Value, typename _Alloc,
1577  typename _ExtractKey, typename _Equal,
1578  typename _H1, typename _H2, typename _Hash,
1579  typename _RehashPolicy, typename _Traits>
1580  bool
1581  _Equality<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1582  _H1, _H2, _Hash, _RehashPolicy, _Traits, true>::
1583  _M_equal(const __hashtable& __other) const
1584  {
1585  const __hashtable* __this = static_cast<const __hashtable*>(this);
1586 
1587  if (__this->size() != __other.size())
1588  return false;
1589 
1590  for (auto __itx = __this->begin(); __itx != __this->end(); ++__itx)
1591  {
1592  const auto __ity = __other.find(_ExtractKey()(*__itx));
1593  if (__ity == __other.end() || !bool(*__ity == *__itx))
1594  return false;
1595  }
1596  return true;
1597  }
1598 
1599  /// Specialization.
1600  template<typename _Key, typename _Value, typename _Alloc,
1601  typename _ExtractKey, typename _Equal,
1602  typename _H1, typename _H2, typename _Hash,
1603  typename _RehashPolicy, typename _Traits>
1604  struct _Equality<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1605  _H1, _H2, _Hash, _RehashPolicy, _Traits, false>
1606  : public _Equality_base
1607  {
1608  using __hashtable = _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1609  _H1, _H2, _Hash, _RehashPolicy, _Traits>;
1610 
1611  bool
1612  _M_equal(const __hashtable&) const;
1613  };
1614 
1615  template<typename _Key, typename _Value, typename _Alloc,
1616  typename _ExtractKey, typename _Equal,
1617  typename _H1, typename _H2, typename _Hash,
1618  typename _RehashPolicy, typename _Traits>
1619  bool
1620  _Equality<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1621  _H1, _H2, _Hash, _RehashPolicy, _Traits, false>::
1622  _M_equal(const __hashtable& __other) const
1623  {
1624  const __hashtable* __this = static_cast<const __hashtable*>(this);
1625 
1626  if (__this->size() != __other.size())
1627  return false;
1628 
1629  for (auto __itx = __this->begin(); __itx != __this->end();)
1630  {
1631  const auto __xrange = __this->equal_range(_ExtractKey()(*__itx));
1632  const auto __yrange = __other.equal_range(_ExtractKey()(*__itx));
1633 
1634  if (std::distance(__xrange.first, __xrange.second)
1635  != std::distance(__yrange.first, __yrange.second))
1636  return false;
1637 
1638  if (!_S_is_permutation(__xrange.first, __xrange.second,
1639  __yrange.first))
1640  return false;
1641 
1642  __itx = __xrange.second;
1643  }
1644  return true;
1645  }
1646 
1647  /**
1648  * This type is to combine a _Hash_node_base instance with an allocator
1649  * instance through inheritance to benefit from EBO when possible.
1650  */
1651  template<typename _NodeAlloc>
1652  struct _Before_begin : public _NodeAlloc
1653  {
1654  _Hash_node_base _M_node;
1655 
1656  _Before_begin(const _Before_begin&) = default;
1657  _Before_begin(_Before_begin&&) = default;
1658 
1659  template<typename _Alloc>
1660  _Before_begin(_Alloc&& __a)
1661  : _NodeAlloc(std::forward<_Alloc>(__a))
1662  { }
1663  };
1664 
1665  //@} hashtable-detail
1666 _GLIBCXX_END_NAMESPACE_VERSION
1667 } // namespace __detail
1668 } // namespace std
1669 
1670 #endif // _HASHTABLE_POLICY_H
std::iterator
Common iterator class.
Definition: stl_iterator_base_types.h:118
__gnu_debug::__base
_Siter_base< _Iterator >::iterator_type __base(_Iterator __it)
Definition: functions.h:446
std::__detail::_Default_ranged_hash
Default ranged hash function H. In principle it should be a function object composed from objects of ...
Definition: hashtable_policy.h:353
std::piecewise_construct
constexpr piecewise_construct_t piecewise_construct
piecewise_construct
Definition: stl_pair.h:79
std::distance
iterator_traits< _InputIterator >::difference_type distance(_InputIterator __first, _InputIterator __last)
A generalization of pointer arithmetic.
Definition: stl_iterator_base_funcs.h:114
std::forward
constexpr _Tp && forward(typename std::remove_reference< _Tp >::type &__t) noexcept
Forward an lvalue.
Definition: move.h:76
std::__addressof
_Tp * __addressof(_Tp &__r) noexcept
Same as C++11 std::addressof.
Definition: move.h:47
std::__detail::_Hash_code_base< _Key, _Value, _ExtractKey, _H1, _H2, _Hash, false >
Specialization: ranged hash function, no caching hash codes. H1 and H2 are provided but ignored...
Definition: hashtable_policy.h:913
std::move
constexpr std::remove_reference< _Tp >::type && move(_Tp &&__t) noexcept
Convert a value to an rvalue.
Definition: move.h:101
std::__detail::_Mod_range_hashing
Default range hashing function: use division to fold a large number into the range [0...
Definition: hashtable_policy.h:337
std::advance
void advance(_InputIterator &__i, _Distance __n)
A generalization of pointer arithmetic.
Definition: stl_iterator_base_funcs.h:173
std
ISO C++ entities toplevel namespace is std.
std::__detail::_Node_iterator
Node iterators, used to iterate through all the hashtable.
Definition: hashtable_policy.h:231
std::forward_iterator_tag
Forward iterators support a superset of input iterator operations.
Definition: stl_iterator_base_types.h:95
std::__detail::_Node_iterator_base
Base class for node iterators.
Definition: hashtable_policy.h:203
std::input_iterator_tag
Marking input iterators.
Definition: stl_iterator_base_types.h:89
std::swap
void swap(_Tp &, _Tp &) noexcept(__and_< is_nothrow_move_constructible< _Tp >, is_nothrow_move_assignable< _Tp >>::value)
Swaps two values.
Definition: move.h:166
std::__detail::_Node_const_iterator
Node const_iterators, used to iterate through all the hashtable.
Definition: hashtable_policy.h:282
std::pair
Struct holding two objects of arbitrary type.
Definition: stl_pair.h:96
std::__detail::_Prime_rehash_policy
Default value for rehash policy. Bucket size is (usually) the smallest prime that keeps the load fact...
Definition: hashtable_policy.h:357