OSDN Git Service

2012-04-22 Paolo Carlini <paolo.carlini@oracle.com>
[pf3gnuchains/gcc-fork.git] / libstdc++-v3 / include / bits / hashtable_policy.h
1 // Internal policy header for unordered_set and unordered_map -*- C++ -*-
2
3 // Copyright (C) 2010, 2011, 2012 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 namespace __detail
37 {
38 _GLIBCXX_BEGIN_NAMESPACE_VERSION
39
40   // Helper function: return distance(first, last) for forward
41   // iterators, or 0 for input iterators.
42   template<class _Iterator>
43     inline typename std::iterator_traits<_Iterator>::difference_type
44     __distance_fw(_Iterator __first, _Iterator __last,
45                   std::input_iterator_tag)
46     { return 0; }
47
48   template<class _Iterator>
49     inline typename std::iterator_traits<_Iterator>::difference_type
50     __distance_fw(_Iterator __first, _Iterator __last,
51                   std::forward_iterator_tag)
52     { return std::distance(__first, __last); }
53
54   template<class _Iterator>
55     inline typename std::iterator_traits<_Iterator>::difference_type
56     __distance_fw(_Iterator __first, _Iterator __last)
57     {
58       typedef typename std::iterator_traits<_Iterator>::iterator_category _Tag;
59       return __distance_fw(__first, __last, _Tag());
60     }
61
62   // Helper type used to detect when the hash functor is noexcept qualified or
63   // not
64   template <typename _Key, typename _Hash>
65     struct __is_noexcept_hash : std::integral_constant<bool,
66         noexcept(declval<const _Hash&>()(declval<const _Key&>()))>
67     {};
68
69   // Auxiliary types used for all instantiations of _Hashtable: nodes
70   // and iterators.
71
72   // Nodes, used to wrap elements stored in the hash table.  A policy
73   // template parameter of class template _Hashtable controls whether
74   // nodes also store a hash code. In some cases (e.g. strings) this
75   // may be a performance win.
76   struct _Hash_node_base
77   {
78     _Hash_node_base* _M_nxt;
79
80     _Hash_node_base()
81       : _M_nxt() { }
82     _Hash_node_base(_Hash_node_base* __next)
83       : _M_nxt(__next) { }
84   };
85
86   template<typename _Value, bool __cache_hash_code>
87     struct _Hash_node;
88
89   template<typename _Value>
90     struct _Hash_node<_Value, true> : _Hash_node_base
91     {
92       _Value       _M_v;
93       std::size_t  _M_hash_code;
94
95       template<typename... _Args>
96         _Hash_node(_Args&&... __args)
97         : _M_v(std::forward<_Args>(__args)...), _M_hash_code() { }
98
99       _Hash_node* _M_next() const
100       { return static_cast<_Hash_node*>(_M_nxt); }
101     };
102
103   template<typename _Value>
104     struct _Hash_node<_Value, false> : _Hash_node_base
105     {
106       _Value       _M_v;
107
108       template<typename... _Args>
109         _Hash_node(_Args&&... __args)
110         : _M_v(std::forward<_Args>(__args)...) { }
111
112       _Hash_node* _M_next() const
113       { return static_cast<_Hash_node*>(_M_nxt); }
114     };
115
116   // Node iterators, used to iterate through all the hashtable.
117   template<typename _Value, bool __cache>
118     struct _Node_iterator_base
119     {
120       _Node_iterator_base(_Hash_node<_Value, __cache>* __p)
121       : _M_cur(__p) { }
122
123       void
124       _M_incr()
125       { _M_cur = _M_cur->_M_next(); }
126
127       _Hash_node<_Value, __cache>*  _M_cur;
128     };
129
130   template<typename _Value, bool __cache>
131     inline bool
132     operator==(const _Node_iterator_base<_Value, __cache>& __x,
133                const _Node_iterator_base<_Value, __cache>& __y)
134     { return __x._M_cur == __y._M_cur; }
135
136   template<typename _Value, bool __cache>
137     inline bool
138     operator!=(const _Node_iterator_base<_Value, __cache>& __x,
139                const _Node_iterator_base<_Value, __cache>& __y)
140     { return __x._M_cur != __y._M_cur; }
141
142   template<typename _Value, bool __constant_iterators, bool __cache>
143     struct _Node_iterator
144     : public _Node_iterator_base<_Value, __cache>
145     {
146       typedef _Value                                   value_type;
147       typedef typename std::conditional<__constant_iterators,
148                                         const _Value*, _Value*>::type
149                                                        pointer;
150       typedef typename std::conditional<__constant_iterators,
151                                         const _Value&, _Value&>::type
152                                                        reference;
153       typedef std::ptrdiff_t                           difference_type;
154       typedef std::forward_iterator_tag                iterator_category;
155
156       _Node_iterator()
157       : _Node_iterator_base<_Value, __cache>(0) { }
158
159       explicit
160       _Node_iterator(_Hash_node<_Value, __cache>* __p)
161       : _Node_iterator_base<_Value, __cache>(__p) { }
162
163       reference
164       operator*() const
165       { return this->_M_cur->_M_v; }
166
167       pointer
168       operator->() const
169       { return std::__addressof(this->_M_cur->_M_v); }
170
171       _Node_iterator&
172       operator++()
173       {
174         this->_M_incr();
175         return *this;
176       }
177
178       _Node_iterator
179       operator++(int)
180       {
181         _Node_iterator __tmp(*this);
182         this->_M_incr();
183         return __tmp;
184       }
185     };
186
187   template<typename _Value, bool __constant_iterators, bool __cache>
188     struct _Node_const_iterator
189     : public _Node_iterator_base<_Value, __cache>
190     {
191       typedef _Value                                   value_type;
192       typedef const _Value*                            pointer;
193       typedef const _Value&                            reference;
194       typedef std::ptrdiff_t                           difference_type;
195       typedef std::forward_iterator_tag                iterator_category;
196
197       _Node_const_iterator()
198       : _Node_iterator_base<_Value, __cache>(0) { }
199
200       explicit
201       _Node_const_iterator(_Hash_node<_Value, __cache>* __p)
202       : _Node_iterator_base<_Value, __cache>(__p) { }
203
204       _Node_const_iterator(const _Node_iterator<_Value, __constant_iterators,
205                            __cache>& __x)
206       : _Node_iterator_base<_Value, __cache>(__x._M_cur) { }
207
208       reference
209       operator*() const
210       { return this->_M_cur->_M_v; }
211
212       pointer
213       operator->() const
214       { return std::__addressof(this->_M_cur->_M_v); }
215
216       _Node_const_iterator&
217       operator++()
218       {
219         this->_M_incr();
220         return *this;
221       }
222
223       _Node_const_iterator
224       operator++(int)
225       {
226         _Node_const_iterator __tmp(*this);
227         this->_M_incr();
228         return __tmp;
229       }
230     };
231
232   // Many of class template _Hashtable's template parameters are policy
233   // classes.  These are defaults for the policies.
234
235   // Default range hashing function: use division to fold a large number
236   // into the range [0, N).
237   struct _Mod_range_hashing
238   {
239     typedef std::size_t first_argument_type;
240     typedef std::size_t second_argument_type;
241     typedef std::size_t result_type;
242
243     result_type
244     operator()(first_argument_type __num, second_argument_type __den) const
245     { return __num % __den; }
246   };
247
248   // Default ranged hash function H.  In principle it should be a
249   // function object composed from objects of type H1 and H2 such that
250   // h(k, N) = h2(h1(k), N), but that would mean making extra copies of
251   // h1 and h2.  So instead we'll just use a tag to tell class template
252   // hashtable to do that composition.
253   struct _Default_ranged_hash { };
254
255   // Default value for rehash policy.  Bucket size is (usually) the
256   // smallest prime that keeps the load factor small enough.
257   struct _Prime_rehash_policy
258   {
259     _Prime_rehash_policy(float __z = 1.0)
260     : _M_max_load_factor(__z), _M_prev_resize(0), _M_next_resize(0) { }
261
262     float
263     max_load_factor() const noexcept
264     { return _M_max_load_factor; }
265
266     // Return a bucket size no smaller than n.
267     std::size_t
268     _M_next_bkt(std::size_t __n) const;
269
270     // Return a bucket count appropriate for n elements
271     std::size_t
272     _M_bkt_for_elements(std::size_t __n) const;
273
274     // __n_bkt is current bucket count, __n_elt is current element count,
275     // and __n_ins is number of elements to be inserted.  Do we need to
276     // increase bucket count?  If so, return make_pair(true, n), where n
277     // is the new bucket count.  If not, return make_pair(false, 0).
278     std::pair<bool, std::size_t>
279     _M_need_rehash(std::size_t __n_bkt, std::size_t __n_elt,
280                    std::size_t __n_ins) const;
281
282     typedef std::pair<std::size_t, std::size_t> _State;
283
284     _State
285     _M_state() const
286     { return std::make_pair(_M_prev_resize, _M_next_resize); }
287
288     void
289     _M_reset(const _State& __state)
290     {
291       _M_prev_resize = __state.first;
292       _M_next_resize = __state.second;
293     }
294
295     enum { _S_n_primes = sizeof(unsigned long) != 8 ? 256 : 256 + 48 };
296
297     float                _M_max_load_factor;
298     mutable std::size_t  _M_prev_resize;
299     mutable std::size_t  _M_next_resize;
300   };
301
302   extern const unsigned long __prime_list[];
303
304   // XXX This is a hack.  There's no good reason for any of
305   // _Prime_rehash_policy's member functions to be inline.
306
307   // Return a prime no smaller than n.
308   inline std::size_t
309   _Prime_rehash_policy::
310   _M_next_bkt(std::size_t __n) const
311   {
312     // Optimize lookups involving the first elements of __prime_list.
313     // (useful to speed-up, eg, constructors)
314     static const unsigned char __fast_bkt[12]
315       = { 2, 2, 2, 3, 5, 5, 7, 7, 11, 11, 11, 11 };
316
317     if (__n <= 11)
318       {
319         _M_prev_resize = 0;
320         _M_next_resize
321           = __builtin_ceil(__fast_bkt[__n] * (long double)_M_max_load_factor);
322         return __fast_bkt[__n];
323       }
324
325     const unsigned long* __p
326       = std::lower_bound(__prime_list + 5, __prime_list + _S_n_primes, __n);
327
328     // Shrink will take place only if the number of elements is small enough
329     // so that the prime number 2 steps before __p is large enough to still
330     // conform to the max load factor:
331     _M_prev_resize
332       = __builtin_floor(*(__p - 2) * (long double)_M_max_load_factor);
333
334     // Let's guaranty that a minimal grow step of 11 is used
335     if (*__p - __n < 11)
336       __p = std::lower_bound(__p, __prime_list + _S_n_primes, __n + 11);
337     _M_next_resize = __builtin_ceil(*__p * (long double)_M_max_load_factor);
338     return *__p;
339   }
340
341   // Return the smallest prime p such that alpha p >= n, where alpha
342   // is the load factor.
343   inline std::size_t
344   _Prime_rehash_policy::
345   _M_bkt_for_elements(std::size_t __n) const
346   { return _M_next_bkt(__builtin_ceil(__n / (long double)_M_max_load_factor)); }
347
348   // Finds the smallest prime p such that alpha p > __n_elt + __n_ins.
349   // If p > __n_bkt, return make_pair(true, p); otherwise return
350   // make_pair(false, 0).  In principle this isn't very different from
351   // _M_bkt_for_elements.
352
353   // The only tricky part is that we're caching the element count at
354   // which we need to rehash, so we don't have to do a floating-point
355   // multiply for every insertion.
356
357   inline std::pair<bool, std::size_t>
358   _Prime_rehash_policy::
359   _M_need_rehash(std::size_t __n_bkt, std::size_t __n_elt,
360                  std::size_t __n_ins) const
361   {
362     if (__n_elt + __n_ins >= _M_next_resize)
363       {
364         long double __min_bkts = (__n_elt + __n_ins)
365                                  / (long double)_M_max_load_factor;
366         if (__min_bkts >= __n_bkt)
367           return std::make_pair(true,
368                                 _M_next_bkt(__builtin_floor(__min_bkts) + 1));
369         else
370           {
371             _M_next_resize
372               = __builtin_floor(__n_bkt * (long double)_M_max_load_factor);
373             return std::make_pair(false, 0);
374           }
375       }
376     else if (__n_elt + __n_ins < _M_prev_resize)
377       {
378         long double __min_bkts = (__n_elt + __n_ins)
379                                  / (long double)_M_max_load_factor;
380         return std::make_pair(true,
381                               _M_next_bkt(__builtin_floor(__min_bkts) + 1));
382       }
383     else
384       return std::make_pair(false, 0);
385   }
386
387   // Base classes for std::_Hashtable.  We define these base classes
388   // because in some cases we want to do different things depending
389   // on the value of a policy class.  In some cases the policy class
390   // affects which member functions and nested typedefs are defined;
391   // we handle that by specializing base class templates.  Several of
392   // the base class templates need to access other members of class
393   // template _Hashtable, so we use the "curiously recurring template
394   // pattern" for them.
395
396   // class template _Map_base.  If the hashtable has a value type of
397   // the form pair<T1, T2> and a key extraction policy that returns the
398   // first part of the pair, the hashtable gets a mapped_type typedef.
399   // If it satisfies those criteria and also has unique keys, then it
400   // also gets an operator[].
401   template<typename _Key, typename _Value, typename _Ex, bool __unique,
402            typename _Hashtable>
403     struct _Map_base { };
404
405   template<typename _Key, typename _Pair, typename _Hashtable>
406     struct _Map_base<_Key, _Pair, std::_Select1st<_Pair>, false, _Hashtable>
407     {
408       typedef typename _Pair::second_type mapped_type;
409     };
410
411   template<typename _Key, typename _Pair, typename _Hashtable>
412     struct _Map_base<_Key, _Pair, std::_Select1st<_Pair>, true, _Hashtable>
413     {
414       typedef typename _Pair::second_type mapped_type;
415
416       mapped_type&
417       operator[](const _Key& __k);
418
419       mapped_type&
420       operator[](_Key&& __k);
421
422       // _GLIBCXX_RESOLVE_LIB_DEFECTS
423       // DR 761. unordered_map needs an at() member function.
424       mapped_type&
425       at(const _Key& __k);
426
427       const mapped_type&
428       at(const _Key& __k) const;
429     };
430
431   template<typename _Key, typename _Pair, typename _Hashtable>
432     typename _Map_base<_Key, _Pair, std::_Select1st<_Pair>,
433                        true, _Hashtable>::mapped_type&
434     _Map_base<_Key, _Pair, std::_Select1st<_Pair>, true, _Hashtable>::
435     operator[](const _Key& __k)
436     {
437       _Hashtable* __h = static_cast<_Hashtable*>(this);
438       typename _Hashtable::_Hash_code_type __code = __h->_M_hash_code(__k);
439       std::size_t __n = __h->_M_bucket_index(__k, __code);
440
441       typename _Hashtable::_Node* __p = __h->_M_find_node(__n, __k, __code);
442       if (!__p)
443         return __h->_M_insert_bucket(std::make_pair(__k, mapped_type()),
444                                      __n, __code)->second;
445       return (__p->_M_v).second;
446     }
447
448   template<typename _Key, typename _Pair, typename _Hashtable>
449     typename _Map_base<_Key, _Pair, std::_Select1st<_Pair>,
450                        true, _Hashtable>::mapped_type&
451     _Map_base<_Key, _Pair, std::_Select1st<_Pair>, true, _Hashtable>::
452     operator[](_Key&& __k)
453     {
454       _Hashtable* __h = static_cast<_Hashtable*>(this);
455       typename _Hashtable::_Hash_code_type __code = __h->_M_hash_code(__k);
456       std::size_t __n = __h->_M_bucket_index(__k, __code);
457
458       typename _Hashtable::_Node* __p = __h->_M_find_node(__n, __k, __code);
459       if (!__p)
460         return __h->_M_insert_bucket(std::make_pair(std::move(__k),
461                                                     mapped_type()),
462                                      __n, __code)->second;
463       return (__p->_M_v).second;
464     }
465
466   template<typename _Key, typename _Pair, typename _Hashtable>
467     typename _Map_base<_Key, _Pair, std::_Select1st<_Pair>,
468                        true, _Hashtable>::mapped_type&
469     _Map_base<_Key, _Pair, std::_Select1st<_Pair>, true, _Hashtable>::
470     at(const _Key& __k)
471     {
472       _Hashtable* __h = static_cast<_Hashtable*>(this);
473       typename _Hashtable::_Hash_code_type __code = __h->_M_hash_code(__k);
474       std::size_t __n = __h->_M_bucket_index(__k, __code);
475
476       typename _Hashtable::_Node* __p = __h->_M_find_node(__n, __k, __code);
477       if (!__p)
478         __throw_out_of_range(__N("_Map_base::at"));
479       return (__p->_M_v).second;
480     }
481
482   template<typename _Key, typename _Pair, typename _Hashtable>
483     const typename _Map_base<_Key, _Pair, std::_Select1st<_Pair>,
484                              true, _Hashtable>::mapped_type&
485     _Map_base<_Key, _Pair, std::_Select1st<_Pair>, true, _Hashtable>::
486     at(const _Key& __k) const
487     {
488       const _Hashtable* __h = static_cast<const _Hashtable*>(this);
489       typename _Hashtable::_Hash_code_type __code = __h->_M_hash_code(__k);
490       std::size_t __n = __h->_M_bucket_index(__k, __code);
491
492       typename _Hashtable::_Node* __p = __h->_M_find_node(__n, __k, __code);
493       if (!__p)
494         __throw_out_of_range(__N("_Map_base::at"));
495       return (__p->_M_v).second;
496     }
497
498   // class template _Rehash_base.  Give hashtable the max_load_factor
499   // functions and reserve iff the rehash policy is _Prime_rehash_policy.
500   template<typename _RehashPolicy, typename _Hashtable>
501     struct _Rehash_base { };
502
503   template<typename _Hashtable>
504     struct _Rehash_base<_Prime_rehash_policy, _Hashtable>
505     {
506       float
507       max_load_factor() const noexcept
508       {
509         const _Hashtable* __this = static_cast<const _Hashtable*>(this);
510         return __this->__rehash_policy().max_load_factor();
511       }
512
513       void
514       max_load_factor(float __z)
515       {
516         _Hashtable* __this = static_cast<_Hashtable*>(this);
517         __this->__rehash_policy(_Prime_rehash_policy(__z));
518       }
519
520       void
521       reserve(std::size_t __n)
522       {
523         _Hashtable* __this = static_cast<_Hashtable*>(this);
524         __this->rehash(__builtin_ceil(__n / max_load_factor()));
525       }
526     };
527
528   // Helper class using EBO when it is not forbidden, type is not final,
529   // and when it worth it, type is empty.
530   template<int _Nm, typename _Tp,
531            bool __use_ebo = !__is_final(_Tp) && __is_empty(_Tp)>
532     struct _Hashtable_ebo_helper;
533
534   // Specialization using EBO.
535   template<int _Nm, typename _Tp>
536     struct _Hashtable_ebo_helper<_Nm, _Tp, true>
537     // See PR53067.
538     : public _Tp
539     {
540       _Hashtable_ebo_helper() = default;
541       _Hashtable_ebo_helper(const _Tp& __tp) : _Tp(__tp)
542       { }
543
544       static const _Tp&
545       _S_cget(const _Hashtable_ebo_helper& __eboh)
546       { return static_cast<const _Tp&>(__eboh); }
547
548       static _Tp&
549       _S_get(_Hashtable_ebo_helper& __eboh)
550       { return static_cast<_Tp&>(__eboh); }
551     };
552
553   // Specialization not using EBO.
554   template<int _Nm, typename _Tp>
555     struct _Hashtable_ebo_helper<_Nm, _Tp, false>
556     {
557       _Hashtable_ebo_helper() = default;
558       _Hashtable_ebo_helper(const _Tp& __tp) : _M_tp(__tp)
559       { }
560
561       static const _Tp&
562       _S_cget(const _Hashtable_ebo_helper& __eboh)
563       { return __eboh._M_tp; }
564
565       static _Tp&
566       _S_get(_Hashtable_ebo_helper& __eboh)
567       { return __eboh._M_tp; }
568
569     private:
570       _Tp _M_tp;
571     };
572
573   // Class template _Hash_code_base.  Encapsulates two policy issues that
574   // aren't quite orthogonal.
575   //   (1) the difference between using a ranged hash function and using
576   //       the combination of a hash function and a range-hashing function.
577   //       In the former case we don't have such things as hash codes, so
578   //       we have a dummy type as placeholder.
579   //   (2) Whether or not we cache hash codes.  Caching hash codes is
580   //       meaningless if we have a ranged hash function.
581   // We also put the key extraction objects here, for convenience.
582   //
583   // Each specialization derives from one or more of the template parameters to
584   // benefit from Ebo. This is important as this type is inherited in some cases
585   // by the _Local_iterator_base type used to implement local_iterator and
586   // const_local_iterator. As with any iterator type we prefer to make it as
587   // small as possible.
588
589   // Primary template: unused except as a hook for specializations.
590   template<typename _Key, typename _Value, typename _ExtractKey,
591            typename _H1, typename _H2, typename _Hash,
592            bool __cache_hash_code>
593     struct _Hash_code_base;
594
595   // Specialization: ranged hash function, no caching hash codes.  H1
596   // and H2 are provided but ignored.  We define a dummy hash code type.
597   template<typename _Key, typename _Value, typename _ExtractKey, 
598            typename _H1, typename _H2, typename _Hash>
599     struct _Hash_code_base<_Key, _Value, _ExtractKey, _H1, _H2, _Hash, false>
600     // See PR53067.
601     : public  _Hashtable_ebo_helper<0, _ExtractKey>,
602       public  _Hashtable_ebo_helper<1, _Hash>
603     {
604     private:
605       typedef _Hashtable_ebo_helper<0, _ExtractKey> _EboExtractKey;
606       typedef _Hashtable_ebo_helper<1, _Hash> _EboHash;
607
608     protected:
609       // We need the default constructor for the local iterators.
610       _Hash_code_base() = default;
611       _Hash_code_base(const _ExtractKey& __ex,
612                       const _H1&, const _H2&, const _Hash& __h)
613         : _EboExtractKey(__ex), _EboHash(__h) { }
614
615       typedef void* _Hash_code_type;
616
617       _Hash_code_type
618       _M_hash_code(const _Key& __key) const
619       { return 0; }
620
621       std::size_t
622       _M_bucket_index(const _Key& __k, _Hash_code_type,
623                       std::size_t __n) const
624       { return _M_ranged_hash()(__k, __n); }
625
626       std::size_t
627       _M_bucket_index(const _Hash_node<_Value, false>* __p,
628                       std::size_t __n) const
629       { return _M_ranged_hash()(_M_extract()(__p->_M_v), __n); }
630
631       void
632       _M_store_code(_Hash_node<_Value, false>*, _Hash_code_type) const
633       { }
634
635       void
636       _M_copy_code(_Hash_node<_Value, false>*,
637                    const _Hash_node<_Value, false>*) const
638       { }
639
640       void
641       _M_swap(_Hash_code_base& __x)
642       {
643         std::swap(_M_extract(), __x._M_extract());
644         std::swap(_M_ranged_hash(), __x._M_ranged_hash());
645       }
646
647     protected:
648       const _ExtractKey&
649       _M_extract() const { return _EboExtractKey::_S_cget(*this); }
650       _ExtractKey&
651       _M_extract() { return _EboExtractKey::_S_get(*this); }
652       const _Hash&
653       _M_ranged_hash() const { return _EboHash::_S_cget(*this); }
654       _Hash&
655       _M_ranged_hash() { return _EboHash::_S_get(*this); }
656     };
657
658   // No specialization for ranged hash function while caching hash codes.
659   // That combination is meaningless, and trying to do it is an error.
660
661   // Specialization: ranged hash function, cache hash codes.  This
662   // combination is meaningless, so we provide only a declaration
663   // and no definition.
664   template<typename _Key, typename _Value, typename _ExtractKey,
665            typename _H1, typename _H2, typename _Hash>
666     struct _Hash_code_base<_Key, _Value, _ExtractKey, _H1, _H2, _Hash, true>;
667
668   // Specialization: hash function and range-hashing function, no
669   // caching of hash codes.
670   // Provides typedef and accessor required by TR1.
671   template<typename _Key, typename _Value, typename _ExtractKey,
672            typename _H1, typename _H2>
673     struct _Hash_code_base<_Key, _Value, _ExtractKey, _H1, _H2,
674                            _Default_ranged_hash, false>
675     // See PR53067.
676     : public  _Hashtable_ebo_helper<0, _ExtractKey>,
677       public  _Hashtable_ebo_helper<1, _H1>,
678       public  _Hashtable_ebo_helper<2, _H2>
679     {
680     private:
681       typedef _Hashtable_ebo_helper<0, _ExtractKey> _EboExtractKey;
682       typedef _Hashtable_ebo_helper<1, _H1> _EboH1;
683       typedef _Hashtable_ebo_helper<2, _H2> _EboH2;
684
685     public:
686       typedef _H1 hasher;
687
688       hasher
689       hash_function() const
690       { return _M_h1(); }
691
692     protected:
693       // We need the default constructor for the local iterators.
694       _Hash_code_base() = default;
695       _Hash_code_base(const _ExtractKey& __ex,
696                       const _H1& __h1, const _H2& __h2,
697                       const _Default_ranged_hash&)
698       : _EboExtractKey(__ex), _EboH1(__h1), _EboH2(__h2) { }
699
700       typedef std::size_t _Hash_code_type;
701
702       _Hash_code_type
703       _M_hash_code(const _Key& __k) const
704       { return _M_h1()(__k); }
705
706       std::size_t
707       _M_bucket_index(const _Key&, _Hash_code_type __c,
708                       std::size_t __n) const
709       { return _M_h2()(__c, __n); }
710
711       std::size_t
712       _M_bucket_index(const _Hash_node<_Value, false>* __p,
713                       std::size_t __n) const
714       { return _M_h2()(_M_h1()(_M_extract()(__p->_M_v)), __n); }
715
716       void
717       _M_store_code(_Hash_node<_Value, false>*, _Hash_code_type) const
718       { }
719
720       void
721       _M_copy_code(_Hash_node<_Value, false>*,
722                    const _Hash_node<_Value, false>*) const
723       { }
724
725       void
726       _M_swap(_Hash_code_base& __x)
727       {
728         std::swap(_M_extract(), __x._M_extract());
729         std::swap(_M_h1(), __x._M_h1());
730         std::swap(_M_h2(), __x._M_h2());
731       }
732
733     protected:
734       const _ExtractKey&
735       _M_extract() const { return _EboExtractKey::_S_cget(*this); }
736       _ExtractKey&
737       _M_extract() { return _EboExtractKey::_S_get(*this); }
738       const _H1&
739       _M_h1() const { return _EboH1::_S_cget(*this); }
740       _H1&
741       _M_h1() { return _EboH1::_S_get(*this); }
742       const _H2&
743       _M_h2() const { return _EboH2::_S_cget(*this); }
744       _H2&
745       _M_h2() { return _EboH2::_S_get(*this); }
746     };
747
748   // Specialization: hash function and range-hashing function,
749   // caching hash codes.  H is provided but ignored.  Provides
750   // typedef and accessor required by TR1.
751   template<typename _Key, typename _Value, typename _ExtractKey,
752            typename _H1, typename _H2>
753     struct _Hash_code_base<_Key, _Value, _ExtractKey, _H1, _H2,
754                            _Default_ranged_hash, true>
755     // See PR53067.
756     : public  _Hashtable_ebo_helper<0, _ExtractKey>,
757       public  _Hashtable_ebo_helper<1, _H1>,
758       public  _Hashtable_ebo_helper<2, _H2>
759     {
760     private:
761       typedef _Hashtable_ebo_helper<0, _ExtractKey> _EboExtractKey;
762       typedef _Hashtable_ebo_helper<1, _H1> _EboH1;
763       typedef _Hashtable_ebo_helper<2, _H2> _EboH2;
764
765     public:
766       typedef _H1 hasher;
767
768       hasher
769       hash_function() const
770       { return _M_h1(); }
771
772     protected:
773       _Hash_code_base(const _ExtractKey& __ex,
774                       const _H1& __h1, const _H2& __h2,
775                       const _Default_ranged_hash&)
776       : _EboExtractKey(__ex), _EboH1(__h1), _EboH2(__h2) { }
777
778       typedef std::size_t _Hash_code_type;
779
780       _Hash_code_type
781       _M_hash_code(const _Key& __k) const
782       { return _M_h1()(__k); }
783
784       std::size_t
785       _M_bucket_index(const _Key&, _Hash_code_type __c,
786                       std::size_t __n) const
787       { return _M_h2()(__c, __n); }
788
789       std::size_t
790       _M_bucket_index(const _Hash_node<_Value, true>* __p,
791                       std::size_t __n) const
792       { return _M_h2()(__p->_M_hash_code, __n); }
793
794       void
795       _M_store_code(_Hash_node<_Value, true>* __n, _Hash_code_type __c) const
796       { __n->_M_hash_code = __c; }
797
798       void
799       _M_copy_code(_Hash_node<_Value, true>* __to,
800                    const _Hash_node<_Value, true>* __from) const
801       { __to->_M_hash_code = __from->_M_hash_code; }
802
803       void
804       _M_swap(_Hash_code_base& __x)
805       {
806         std::swap(_M_extract(), __x._M_extract());
807         std::swap(_M_h1(), __x._M_h1());
808         std::swap(_M_h2(), __x._M_h2());
809       }
810
811     protected:
812       const _ExtractKey&
813       _M_extract() const { return _EboExtractKey::_S_cget(*this); }
814       _ExtractKey&
815       _M_extract() { return _EboExtractKey::_S_get(*this); }
816       const _H1&
817       _M_h1() const { return _EboH1::_S_cget(*this); }
818       _H1&
819       _M_h1() { return _EboH1::_S_get(*this); }
820       const _H2&
821       _M_h2() const { return _EboH2::_S_cget(*this); }
822       _H2&
823       _M_h2() { return _EboH2::_S_get(*this); }
824     };
825
826   template <typename _Key, typename _Value, typename _ExtractKey,
827             typename _Equal, typename _HashCodeType,
828             bool __cache_hash_code>
829   struct _Equal_helper;
830
831   template<typename _Key, typename _Value, typename _ExtractKey,
832            typename _Equal, typename _HashCodeType>
833   struct _Equal_helper<_Key, _Value, _ExtractKey, _Equal, _HashCodeType, true>
834   {
835     static bool
836     _S_equals(const _Equal& __eq, const _ExtractKey& __extract,
837               const _Key& __k, _HashCodeType __c,
838               _Hash_node<_Value, true>* __n)
839     { return __c == __n->_M_hash_code
840              && __eq(__k, __extract(__n->_M_v)); }
841   };
842
843   template<typename _Key, typename _Value, typename _ExtractKey,
844            typename _Equal, typename _HashCodeType>
845   struct _Equal_helper<_Key, _Value, _ExtractKey, _Equal, _HashCodeType, false>
846   {
847     static bool
848     _S_equals(const _Equal& __eq, const _ExtractKey& __extract,
849               const _Key& __k, _HashCodeType,
850               _Hash_node<_Value, false>* __n)
851     { return __eq(__k, __extract(__n->_M_v)); }
852   };
853
854   // Helper class adding management of _Equal functor to _Hash_code_base
855   // type.
856   template<typename _Key, typename _Value,
857            typename _ExtractKey, typename _Equal,
858            typename _H1, typename _H2, typename _Hash,
859            bool __cache_hash_code>
860   struct _Hashtable_base
861   // See PR53067.
862   : public  _Hash_code_base<_Key, _Value, _ExtractKey, _H1, _H2, _Hash,
863                             __cache_hash_code>,
864     public _Hashtable_ebo_helper<0, _Equal>
865   {
866   private:
867     typedef _Hashtable_ebo_helper<0, _Equal> _EboEqual;
868
869   protected:
870     typedef _Hash_code_base<_Key, _Value, _ExtractKey,
871                             _H1, _H2, _Hash, __cache_hash_code> _HCBase;
872     typedef typename _HCBase::_Hash_code_type _Hash_code_type;
873
874     _Hashtable_base(const _ExtractKey& __ex,
875                     const _H1& __h1, const _H2& __h2,
876                     const _Hash& __hash, const _Equal& __eq)
877       : _HCBase(__ex, __h1, __h2, __hash), _EboEqual(__eq) { }
878
879     bool
880     _M_equals(const _Key& __k, _Hash_code_type __c,
881               _Hash_node<_Value, __cache_hash_code>* __n) const
882     {
883       typedef _Equal_helper<_Key, _Value, _ExtractKey,
884                            _Equal, _Hash_code_type,
885                            __cache_hash_code> _EqualHelper;
886       return _EqualHelper::_S_equals(_M_eq(), this->_M_extract(),
887                                      __k, __c, __n);
888     }
889
890     void
891     _M_swap(_Hashtable_base& __x)
892     {
893       _HCBase::_M_swap(__x);
894       std::swap(_M_eq(), __x._M_eq());
895     }
896
897   protected:
898     const _Equal&
899     _M_eq() const { return _EboEqual::_S_cget(*this); }
900     _Equal&
901     _M_eq() { return _EboEqual::_S_get(*this); }
902   };
903
904   // Local iterators, used to iterate within a bucket but not between
905   // buckets.
906   template<typename _Key, typename _Value, typename _ExtractKey,
907            typename _H1, typename _H2, typename _Hash,
908            bool __cache_hash_code>
909     struct _Local_iterator_base;
910
911   template<typename _Key, typename _Value, typename _ExtractKey,
912            typename _H1, typename _H2, typename _Hash>
913     struct _Local_iterator_base<_Key, _Value, _ExtractKey,
914                                 _H1, _H2, _Hash, true>
915     // See PR53067.
916     : public _H2
917     {
918       _Local_iterator_base() = default;
919       _Local_iterator_base(_Hash_node<_Value, true>* __p,
920                            std::size_t __bkt, std::size_t __bkt_count)
921       : _M_cur(__p), _M_bucket(__bkt), _M_bucket_count(__bkt_count) { }
922
923       void
924       _M_incr()
925       {
926         _M_cur = _M_cur->_M_next();
927         if (_M_cur)
928           {
929             std::size_t __bkt = _M_h2()(_M_cur->_M_hash_code, _M_bucket_count);
930             if (__bkt != _M_bucket)
931               _M_cur = nullptr;
932           }
933       }
934
935       const _H2& _M_h2() const
936       { return *this; }
937
938       _Hash_node<_Value, true>*  _M_cur;
939       std::size_t _M_bucket;
940       std::size_t _M_bucket_count;
941     };
942
943   template<typename _Key, typename _Value, typename _ExtractKey,
944            typename _H1, typename _H2, typename _Hash>
945     struct _Local_iterator_base<_Key, _Value, _ExtractKey,
946                                 _H1, _H2, _Hash, false>
947     // See PR53067.
948     : public _Hash_code_base<_Key, _Value, _ExtractKey,
949                              _H1, _H2, _Hash, false>
950     {
951       _Local_iterator_base() = default;
952       _Local_iterator_base(_Hash_node<_Value, false>* __p,
953                            std::size_t __bkt, std::size_t __bkt_count)
954       : _M_cur(__p), _M_bucket(__bkt), _M_bucket_count(__bkt_count) { }
955
956       void
957       _M_incr()
958       {
959         _M_cur = _M_cur->_M_next();
960         if (_M_cur)
961           {
962             std::size_t __bkt = this->_M_bucket_index(_M_cur, _M_bucket_count);
963             if (__bkt != _M_bucket)
964               _M_cur = nullptr;
965           }
966       }
967
968       _Hash_node<_Value, false>*  _M_cur;
969       std::size_t _M_bucket;
970       std::size_t _M_bucket_count;
971     };
972
973   template<typename _Key, typename _Value, typename _ExtractKey,
974            typename _H1, typename _H2, typename _Hash, bool __cache>
975     inline bool
976     operator==(const _Local_iterator_base<_Key, _Value, _ExtractKey,
977                                           _H1, _H2, _Hash, __cache>& __x,
978                const _Local_iterator_base<_Key, _Value, _ExtractKey,
979                                           _H1, _H2, _Hash, __cache>& __y)
980     { return __x._M_cur == __y._M_cur; }
981
982   template<typename _Key, typename _Value, typename _ExtractKey,
983            typename _H1, typename _H2, typename _Hash, bool __cache>
984     inline bool
985     operator!=(const _Local_iterator_base<_Key, _Value, _ExtractKey,
986                                           _H1, _H2, _Hash, __cache>& __x,
987                const _Local_iterator_base<_Key, _Value, _ExtractKey,
988                                           _H1, _H2, _Hash, __cache>& __y)
989     { return __x._M_cur != __y._M_cur; }
990
991   template<typename _Key, typename _Value, typename _ExtractKey,
992            typename _H1, typename _H2, typename _Hash,
993            bool __constant_iterators, bool __cache>
994     struct _Local_iterator
995     : public _Local_iterator_base<_Key, _Value, _ExtractKey,
996                                   _H1, _H2, _Hash, __cache>
997     {
998       typedef _Value                                   value_type;
999       typedef typename std::conditional<__constant_iterators,
1000                                         const _Value*, _Value*>::type
1001                                                        pointer;
1002       typedef typename std::conditional<__constant_iterators,
1003                                         const _Value&, _Value&>::type
1004                                                        reference;
1005       typedef std::ptrdiff_t                           difference_type;
1006       typedef std::forward_iterator_tag                iterator_category;
1007
1008       _Local_iterator() = default;
1009
1010       explicit
1011       _Local_iterator(_Hash_node<_Value, __cache>* __p,
1012                       std::size_t __bkt, std::size_t __bkt_count)
1013       : _Local_iterator_base<_Key, _Value, _ExtractKey, _H1, _H2, _Hash,
1014                              __cache>(__p, __bkt, __bkt_count)
1015       { }
1016
1017       reference
1018       operator*() const
1019       { return this->_M_cur->_M_v; }
1020
1021       pointer
1022       operator->() const
1023       { return std::__addressof(this->_M_cur->_M_v); }
1024
1025       _Local_iterator&
1026       operator++()
1027       {
1028         this->_M_incr();
1029         return *this;
1030       }
1031
1032       _Local_iterator
1033       operator++(int)
1034       {
1035         _Local_iterator __tmp(*this);
1036         this->_M_incr();
1037         return __tmp;
1038       }
1039     };
1040
1041   template<typename _Key, typename _Value, typename _ExtractKey,
1042            typename _H1, typename _H2, typename _Hash,
1043            bool __constant_iterators, bool __cache>
1044     struct _Local_const_iterator
1045     : public _Local_iterator_base<_Key, _Value, _ExtractKey,
1046                                   _H1, _H2, _Hash, __cache>
1047     {
1048       typedef _Value                                   value_type;
1049       typedef const _Value*                            pointer;
1050       typedef const _Value&                            reference;
1051       typedef std::ptrdiff_t                           difference_type;
1052       typedef std::forward_iterator_tag                iterator_category;
1053
1054       _Local_const_iterator() = default;
1055
1056       explicit
1057       _Local_const_iterator(_Hash_node<_Value, __cache>* __p,
1058                             std::size_t __bkt, std::size_t __bkt_count)
1059       : _Local_iterator_base<_Key, _Value, _ExtractKey, _H1, _H2, _Hash,
1060                              __cache>(__p, __bkt, __bkt_count)
1061       { }
1062
1063       _Local_const_iterator(const _Local_iterator<_Key, _Value, _ExtractKey,
1064                                                   _H1, _H2, _Hash,
1065                                                   __constant_iterators,
1066                                                   __cache>& __x)
1067       : _Local_iterator_base<_Key, _Value, _ExtractKey, _H1, _H2, _Hash,
1068                              __cache>(__x._M_cur, __x._M_bucket,
1069                                       __x._M_bucket_count)
1070       { }
1071
1072       reference
1073       operator*() const
1074       { return this->_M_cur->_M_v; }
1075
1076       pointer
1077       operator->() const
1078       { return std::__addressof(this->_M_cur->_M_v); }
1079
1080       _Local_const_iterator&
1081       operator++()
1082       {
1083         this->_M_incr();
1084         return *this;
1085       }
1086
1087       _Local_const_iterator
1088       operator++(int)
1089       {
1090         _Local_const_iterator __tmp(*this);
1091         this->_M_incr();
1092         return __tmp;
1093       }
1094     };
1095
1096
1097   // Class template _Equality_base.  This is for implementing equality
1098   // comparison for unordered containers, per N3068, by John Lakos and
1099   // Pablo Halpern.  Algorithmically, we follow closely the reference
1100   // implementations therein.
1101   template<typename _ExtractKey, bool __unique_keys,
1102            typename _Hashtable>
1103     struct _Equality_base;
1104
1105   template<typename _ExtractKey, typename _Hashtable>
1106     struct _Equality_base<_ExtractKey, true, _Hashtable>
1107     {
1108       bool _M_equal(const _Hashtable&) const;
1109     };
1110
1111   template<typename _ExtractKey, typename _Hashtable>
1112     bool
1113     _Equality_base<_ExtractKey, true, _Hashtable>::
1114     _M_equal(const _Hashtable& __other) const
1115     {
1116       const _Hashtable* __this = static_cast<const _Hashtable*>(this);
1117
1118       if (__this->size() != __other.size())
1119         return false;
1120
1121       for (auto __itx = __this->begin(); __itx != __this->end(); ++__itx)
1122         {
1123           const auto __ity = __other.find(_ExtractKey()(*__itx));
1124           if (__ity == __other.end() || !bool(*__ity == *__itx))
1125             return false;
1126         }
1127       return true;
1128     }
1129
1130   template<typename _ExtractKey, typename _Hashtable>
1131     struct _Equality_base<_ExtractKey, false, _Hashtable>
1132     {
1133       bool _M_equal(const _Hashtable&) const;
1134
1135     private:
1136       template<typename _Uiterator>
1137         static bool
1138         _S_is_permutation(_Uiterator, _Uiterator, _Uiterator);
1139     };
1140
1141   // See std::is_permutation in N3068.
1142   template<typename _ExtractKey, typename _Hashtable>
1143     template<typename _Uiterator>
1144       bool
1145       _Equality_base<_ExtractKey, false, _Hashtable>::
1146       _S_is_permutation(_Uiterator __first1, _Uiterator __last1,
1147                         _Uiterator __first2)
1148       {
1149         for (; __first1 != __last1; ++__first1, ++__first2)
1150           if (!(*__first1 == *__first2))
1151             break;
1152
1153         if (__first1 == __last1)
1154           return true;
1155
1156         _Uiterator __last2 = __first2;
1157         std::advance(__last2, std::distance(__first1, __last1));
1158
1159         for (_Uiterator __it1 = __first1; __it1 != __last1; ++__it1)
1160           {
1161             _Uiterator __tmp =  __first1;
1162             while (__tmp != __it1 && !bool(*__tmp == *__it1))
1163               ++__tmp;
1164
1165             // We've seen this one before.
1166             if (__tmp != __it1)
1167               continue;
1168
1169             std::ptrdiff_t __n2 = 0;
1170             for (__tmp = __first2; __tmp != __last2; ++__tmp)
1171               if (*__tmp == *__it1)
1172                 ++__n2;
1173
1174             if (!__n2)
1175               return false;
1176
1177             std::ptrdiff_t __n1 = 0;
1178             for (__tmp = __it1; __tmp != __last1; ++__tmp)
1179               if (*__tmp == *__it1)
1180                 ++__n1;
1181
1182             if (__n1 != __n2)
1183               return false;
1184           }
1185         return true;
1186       }
1187
1188   template<typename _ExtractKey, typename _Hashtable>
1189     bool
1190     _Equality_base<_ExtractKey, false, _Hashtable>::
1191     _M_equal(const _Hashtable& __other) const
1192     {
1193       const _Hashtable* __this = static_cast<const _Hashtable*>(this);
1194
1195       if (__this->size() != __other.size())
1196         return false;
1197
1198       for (auto __itx = __this->begin(); __itx != __this->end();)
1199         {
1200           const auto __xrange = __this->equal_range(_ExtractKey()(*__itx));
1201           const auto __yrange = __other.equal_range(_ExtractKey()(*__itx));
1202
1203           if (std::distance(__xrange.first, __xrange.second)
1204               != std::distance(__yrange.first, __yrange.second))
1205             return false;
1206
1207           if (!_S_is_permutation(__xrange.first,
1208                                  __xrange.second,
1209                                  __yrange.first))
1210             return false;
1211
1212           __itx = __xrange.second;
1213         }
1214       return true;
1215     }
1216
1217 _GLIBCXX_END_NAMESPACE_VERSION
1218 } // namespace __detail
1219 } // namespace std
1220
1221 #endif // _HASHTABLE_POLICY_H