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