OSDN Git Service

2012-07-29 Fran├žois Dumont <fdumont@gcc.gnu.org>
[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     static const std::size_t _S_growth_factor = 2;
298
299     float                _M_max_load_factor;
300     mutable std::size_t  _M_prev_resize;
301     mutable std::size_t  _M_next_resize;
302   };
303
304   extern const unsigned long __prime_list[];
305
306   // XXX This is a hack.  There's no good reason for any of
307   // _Prime_rehash_policy's member functions to be inline.
308
309   // Return a prime no smaller than n.
310   inline std::size_t
311   _Prime_rehash_policy::
312   _M_next_bkt(std::size_t __n) const
313   {
314     // Optimize lookups involving the first elements of __prime_list.
315     // (useful to speed-up, eg, constructors)
316     static const unsigned char __fast_bkt[12]
317       = { 2, 2, 2, 3, 5, 5, 7, 7, 11, 11, 11, 11 };
318
319     const std::size_t __grown_n = __n * _S_growth_factor;
320     if (__grown_n <= 11)
321       {
322         _M_prev_resize = 0;
323         _M_next_resize
324           = __builtin_ceil(__fast_bkt[__grown_n]
325                            * (long double)_M_max_load_factor);
326         return __fast_bkt[__grown_n];
327       }
328
329     const unsigned long* __next_bkt
330       = std::lower_bound(__prime_list + 5, __prime_list + _S_n_primes,
331                          __grown_n);
332     const unsigned long* __prev_bkt
333       = std::lower_bound(__prime_list + 1, __next_bkt, __n / _S_growth_factor);
334
335     _M_prev_resize
336       = __builtin_floor(*(__prev_bkt - 1) * (long double)_M_max_load_factor);
337     _M_next_resize
338       = __builtin_ceil(*__next_bkt * (long double)_M_max_load_factor);
339     return *__next_bkt;
340   }
341
342   // Return the smallest prime p such that alpha p >= n, where alpha
343   // is the load factor.
344   inline std::size_t
345   _Prime_rehash_policy::
346   _M_bkt_for_elements(std::size_t __n) const
347   { return _M_next_bkt(__builtin_ceil(__n / (long double)_M_max_load_factor)); }
348
349   // Finds the smallest prime p such that alpha p > __n_elt + __n_ins.
350   // If p > __n_bkt, return make_pair(true, p); otherwise return
351   // make_pair(false, 0).  In principle this isn't very different from
352   // _M_bkt_for_elements.
353
354   // The only tricky part is that we're caching the element count at
355   // which we need to rehash, so we don't have to do a floating-point
356   // multiply for every insertion.
357
358   inline std::pair<bool, std::size_t>
359   _Prime_rehash_policy::
360   _M_need_rehash(std::size_t __n_bkt, std::size_t __n_elt,
361                  std::size_t __n_ins) const
362   {
363     if (__n_elt + __n_ins >= _M_next_resize)
364       {
365         long double __min_bkts = (__n_elt + __n_ins)
366                                  / (long double)_M_max_load_factor;
367         if (__min_bkts >= __n_bkt)
368           return std::make_pair(true,
369                                 _M_next_bkt(__builtin_floor(__min_bkts) + 1));
370         else
371           {
372             _M_next_resize
373               = __builtin_floor(__n_bkt * (long double)_M_max_load_factor);
374             return std::make_pair(false, 0);
375           }
376       }
377     else if (__n_elt + __n_ins < _M_prev_resize)
378       {
379         long double __min_bkts = (__n_elt + __n_ins)
380                                  / (long double)_M_max_load_factor;
381         return std::make_pair(true,
382                               _M_next_bkt(__builtin_floor(__min_bkts) + 1));
383       }
384     else
385       return std::make_pair(false, 0);
386   }
387
388   // Base classes for std::_Hashtable.  We define these base classes
389   // because in some cases we want to do different things depending
390   // on the value of a policy class.  In some cases the policy class
391   // affects which member functions and nested typedefs are defined;
392   // we handle that by specializing base class templates.  Several of
393   // the base class templates need to access other members of class
394   // template _Hashtable, so we use the "curiously recurring template
395   // pattern" for them.
396
397   // class template _Map_base.  If the hashtable has a value type of
398   // the form pair<T1, T2> and a key extraction policy that returns the
399   // first part of the pair, the hashtable gets a mapped_type typedef.
400   // If it satisfies those criteria and also has unique keys, then it
401   // also gets an operator[].
402   template<typename _Key, typename _Value, typename _Ex, bool __unique,
403            typename _Hashtable>
404     struct _Map_base { };
405
406   template<typename _Key, typename _Pair, typename _Hashtable>
407     struct _Map_base<_Key, _Pair, std::_Select1st<_Pair>, false, _Hashtable>
408     {
409       typedef typename _Pair::second_type mapped_type;
410     };
411
412   template<typename _Key, typename _Pair, typename _Hashtable>
413     struct _Map_base<_Key, _Pair, std::_Select1st<_Pair>, true, _Hashtable>
414     {
415       typedef typename _Pair::second_type mapped_type;
416
417       mapped_type&
418       operator[](const _Key& __k);
419
420       mapped_type&
421       operator[](_Key&& __k);
422
423       // _GLIBCXX_RESOLVE_LIB_DEFECTS
424       // DR 761. unordered_map needs an at() member function.
425       mapped_type&
426       at(const _Key& __k);
427
428       const mapped_type&
429       at(const _Key& __k) const;
430     };
431
432   template<typename _Key, typename _Pair, typename _Hashtable>
433     typename _Map_base<_Key, _Pair, std::_Select1st<_Pair>,
434                        true, _Hashtable>::mapped_type&
435     _Map_base<_Key, _Pair, std::_Select1st<_Pair>, true, _Hashtable>::
436     operator[](const _Key& __k)
437     {
438       _Hashtable* __h = static_cast<_Hashtable*>(this);
439       typename _Hashtable::_Hash_code_type __code = __h->_M_hash_code(__k);
440       std::size_t __n = __h->_M_bucket_index(__k, __code);
441
442       typename _Hashtable::_Node* __p = __h->_M_find_node(__n, __k, __code);
443       if (!__p)
444         return __h->_M_insert_bucket(std::make_pair(__k, mapped_type()),
445                                      __n, __code)->second;
446       return (__p->_M_v).second;
447     }
448
449   template<typename _Key, typename _Pair, typename _Hashtable>
450     typename _Map_base<_Key, _Pair, std::_Select1st<_Pair>,
451                        true, _Hashtable>::mapped_type&
452     _Map_base<_Key, _Pair, std::_Select1st<_Pair>, true, _Hashtable>::
453     operator[](_Key&& __k)
454     {
455       _Hashtable* __h = static_cast<_Hashtable*>(this);
456       typename _Hashtable::_Hash_code_type __code = __h->_M_hash_code(__k);
457       std::size_t __n = __h->_M_bucket_index(__k, __code);
458
459       typename _Hashtable::_Node* __p = __h->_M_find_node(__n, __k, __code);
460       if (!__p)
461         return __h->_M_insert_bucket(std::make_pair(std::move(__k),
462                                                     mapped_type()),
463                                      __n, __code)->second;
464       return (__p->_M_v).second;
465     }
466
467   template<typename _Key, typename _Pair, typename _Hashtable>
468     typename _Map_base<_Key, _Pair, std::_Select1st<_Pair>,
469                        true, _Hashtable>::mapped_type&
470     _Map_base<_Key, _Pair, std::_Select1st<_Pair>, true, _Hashtable>::
471     at(const _Key& __k)
472     {
473       _Hashtable* __h = static_cast<_Hashtable*>(this);
474       typename _Hashtable::_Hash_code_type __code = __h->_M_hash_code(__k);
475       std::size_t __n = __h->_M_bucket_index(__k, __code);
476
477       typename _Hashtable::_Node* __p = __h->_M_find_node(__n, __k, __code);
478       if (!__p)
479         __throw_out_of_range(__N("_Map_base::at"));
480       return (__p->_M_v).second;
481     }
482
483   template<typename _Key, typename _Pair, typename _Hashtable>
484     const typename _Map_base<_Key, _Pair, std::_Select1st<_Pair>,
485                              true, _Hashtable>::mapped_type&
486     _Map_base<_Key, _Pair, std::_Select1st<_Pair>, true, _Hashtable>::
487     at(const _Key& __k) const
488     {
489       const _Hashtable* __h = static_cast<const _Hashtable*>(this);
490       typename _Hashtable::_Hash_code_type __code = __h->_M_hash_code(__k);
491       std::size_t __n = __h->_M_bucket_index(__k, __code);
492
493       typename _Hashtable::_Node* __p = __h->_M_find_node(__n, __k, __code);
494       if (!__p)
495         __throw_out_of_range(__N("_Map_base::at"));
496       return (__p->_M_v).second;
497     }
498
499   // class template _Rehash_base.  Give hashtable the max_load_factor
500   // functions and reserve iff the rehash policy is _Prime_rehash_policy.
501   template<typename _RehashPolicy, typename _Hashtable>
502     struct _Rehash_base { };
503
504   template<typename _Hashtable>
505     struct _Rehash_base<_Prime_rehash_policy, _Hashtable>
506     {
507       float
508       max_load_factor() const noexcept
509       {
510         const _Hashtable* __this = static_cast<const _Hashtable*>(this);
511         return __this->__rehash_policy().max_load_factor();
512       }
513
514       void
515       max_load_factor(float __z)
516       {
517         _Hashtable* __this = static_cast<_Hashtable*>(this);
518         __this->__rehash_policy(_Prime_rehash_policy(__z));
519       }
520
521       void
522       reserve(std::size_t __n)
523       {
524         _Hashtable* __this = static_cast<_Hashtable*>(this);
525         __this->rehash(__builtin_ceil(__n / max_load_factor()));
526       }
527     };
528
529   // Helper class using EBO when it is not forbidden, type is not final,
530   // and when it worth it, type is empty.
531   template<int _Nm, typename _Tp,
532            bool __use_ebo = !__is_final(_Tp) && __is_empty(_Tp)>
533     struct _Hashtable_ebo_helper;
534
535   // Specialization using EBO.
536   template<int _Nm, typename _Tp>
537     struct _Hashtable_ebo_helper<_Nm, _Tp, true>
538     // See PR53067.
539     : public _Tp
540     {
541       _Hashtable_ebo_helper() = default;
542       _Hashtable_ebo_helper(const _Tp& __tp) : _Tp(__tp)
543       { }
544
545       static const _Tp&
546       _S_cget(const _Hashtable_ebo_helper& __eboh)
547       { return static_cast<const _Tp&>(__eboh); }
548
549       static _Tp&
550       _S_get(_Hashtable_ebo_helper& __eboh)
551       { return static_cast<_Tp&>(__eboh); }
552     };
553
554   // Specialization not using EBO.
555   template<int _Nm, typename _Tp>
556     struct _Hashtable_ebo_helper<_Nm, _Tp, false>
557     {
558       _Hashtable_ebo_helper() = default;
559       _Hashtable_ebo_helper(const _Tp& __tp) : _M_tp(__tp)
560       { }
561
562       static const _Tp&
563       _S_cget(const _Hashtable_ebo_helper& __eboh)
564       { return __eboh._M_tp; }
565
566       static _Tp&
567       _S_get(_Hashtable_ebo_helper& __eboh)
568       { return __eboh._M_tp; }
569
570     private:
571       _Tp _M_tp;
572     };
573
574   // Class template _Hash_code_base.  Encapsulates two policy issues that
575   // aren't quite orthogonal.
576   //   (1) the difference between using a ranged hash function and using
577   //       the combination of a hash function and a range-hashing function.
578   //       In the former case we don't have such things as hash codes, so
579   //       we have a dummy type as placeholder.
580   //   (2) Whether or not we cache hash codes.  Caching hash codes is
581   //       meaningless if we have a ranged hash function.
582   // We also put the key extraction objects here, for convenience.
583   //
584   // Each specialization derives from one or more of the template parameters to
585   // benefit from Ebo. This is important as this type is inherited in some cases
586   // by the _Local_iterator_base type used to implement local_iterator and
587   // const_local_iterator. As with any iterator type we prefer to make it as
588   // small as possible.
589
590   // Primary template: unused except as a hook for specializations.
591   template<typename _Key, typename _Value, typename _ExtractKey,
592            typename _H1, typename _H2, typename _Hash,
593            bool __cache_hash_code>
594     struct _Hash_code_base;
595
596   // Specialization: ranged hash function, no caching hash codes.  H1
597   // and H2 are provided but ignored.  We define a dummy hash code type.
598   template<typename _Key, typename _Value, typename _ExtractKey, 
599            typename _H1, typename _H2, typename _Hash>
600     struct _Hash_code_base<_Key, _Value, _ExtractKey, _H1, _H2, _Hash, false>
601     // See PR53067.
602     : public  _Hashtable_ebo_helper<0, _ExtractKey>,
603       public  _Hashtable_ebo_helper<1, _Hash>
604     {
605     private:
606       typedef _Hashtable_ebo_helper<0, _ExtractKey> _EboExtractKey;
607       typedef _Hashtable_ebo_helper<1, _Hash> _EboHash;
608
609     protected:
610       // We need the default constructor for the local iterators.
611       _Hash_code_base() = default;
612       _Hash_code_base(const _ExtractKey& __ex,
613                       const _H1&, const _H2&, const _Hash& __h)
614         : _EboExtractKey(__ex), _EboHash(__h) { }
615
616       typedef void* _Hash_code_type;
617
618       _Hash_code_type
619       _M_hash_code(const _Key& __key) const
620       { return 0; }
621
622       std::size_t
623       _M_bucket_index(const _Key& __k, _Hash_code_type,
624                       std::size_t __n) const
625       { return _M_ranged_hash()(__k, __n); }
626
627       std::size_t
628       _M_bucket_index(const _Hash_node<_Value, false>* __p,
629                       std::size_t __n) const
630       { return _M_ranged_hash()(_M_extract()(__p->_M_v), __n); }
631
632       void
633       _M_store_code(_Hash_node<_Value, false>*, _Hash_code_type) const
634       { }
635
636       void
637       _M_copy_code(_Hash_node<_Value, false>*,
638                    const _Hash_node<_Value, false>*) const
639       { }
640
641       void
642       _M_swap(_Hash_code_base& __x)
643       {
644         std::swap(_M_extract(), __x._M_extract());
645         std::swap(_M_ranged_hash(), __x._M_ranged_hash());
646       }
647
648     protected:
649       const _ExtractKey&
650       _M_extract() const { return _EboExtractKey::_S_cget(*this); }
651       _ExtractKey&
652       _M_extract() { return _EboExtractKey::_S_get(*this); }
653       const _Hash&
654       _M_ranged_hash() const { return _EboHash::_S_cget(*this); }
655       _Hash&
656       _M_ranged_hash() { return _EboHash::_S_get(*this); }
657     };
658
659   // No specialization for ranged hash function while caching hash codes.
660   // That combination is meaningless, and trying to do it is an error.
661
662   // Specialization: ranged hash function, cache hash codes.  This
663   // combination is meaningless, so we provide only a declaration
664   // and no definition.
665   template<typename _Key, typename _Value, typename _ExtractKey,
666            typename _H1, typename _H2, typename _Hash>
667     struct _Hash_code_base<_Key, _Value, _ExtractKey, _H1, _H2, _Hash, true>;
668
669   // Specialization: hash function and range-hashing function, no
670   // caching of hash codes.
671   // Provides typedef and accessor required by TR1.
672   template<typename _Key, typename _Value, typename _ExtractKey,
673            typename _H1, typename _H2>
674     struct _Hash_code_base<_Key, _Value, _ExtractKey, _H1, _H2,
675                            _Default_ranged_hash, false>
676     // See PR53067.
677     : public  _Hashtable_ebo_helper<0, _ExtractKey>,
678       public  _Hashtable_ebo_helper<1, _H1>,
679       public  _Hashtable_ebo_helper<2, _H2>
680     {
681     private:
682       typedef _Hashtable_ebo_helper<0, _ExtractKey> _EboExtractKey;
683       typedef _Hashtable_ebo_helper<1, _H1> _EboH1;
684       typedef _Hashtable_ebo_helper<2, _H2> _EboH2;
685
686     public:
687       typedef _H1 hasher;
688
689       hasher
690       hash_function() const
691       { return _M_h1(); }
692
693     protected:
694       // We need the default constructor for the local iterators.
695       _Hash_code_base() = default;
696       _Hash_code_base(const _ExtractKey& __ex,
697                       const _H1& __h1, const _H2& __h2,
698                       const _Default_ranged_hash&)
699       : _EboExtractKey(__ex), _EboH1(__h1), _EboH2(__h2) { }
700
701       typedef std::size_t _Hash_code_type;
702
703       _Hash_code_type
704       _M_hash_code(const _Key& __k) const
705       { return _M_h1()(__k); }
706
707       std::size_t
708       _M_bucket_index(const _Key&, _Hash_code_type __c,
709                       std::size_t __n) const
710       { return _M_h2()(__c, __n); }
711
712       std::size_t
713       _M_bucket_index(const _Hash_node<_Value, false>* __p,
714                       std::size_t __n) const
715       { return _M_h2()(_M_h1()(_M_extract()(__p->_M_v)), __n); }
716
717       void
718       _M_store_code(_Hash_node<_Value, false>*, _Hash_code_type) const
719       { }
720
721       void
722       _M_copy_code(_Hash_node<_Value, false>*,
723                    const _Hash_node<_Value, false>*) const
724       { }
725
726       void
727       _M_swap(_Hash_code_base& __x)
728       {
729         std::swap(_M_extract(), __x._M_extract());
730         std::swap(_M_h1(), __x._M_h1());
731         std::swap(_M_h2(), __x._M_h2());
732       }
733
734     protected:
735       const _ExtractKey&
736       _M_extract() const { return _EboExtractKey::_S_cget(*this); }
737       _ExtractKey&
738       _M_extract() { return _EboExtractKey::_S_get(*this); }
739       const _H1&
740       _M_h1() const { return _EboH1::_S_cget(*this); }
741       _H1&
742       _M_h1() { return _EboH1::_S_get(*this); }
743       const _H2&
744       _M_h2() const { return _EboH2::_S_cget(*this); }
745       _H2&
746       _M_h2() { return _EboH2::_S_get(*this); }
747     };
748
749   // Specialization: hash function and range-hashing function,
750   // caching hash codes.  H is provided but ignored.  Provides
751   // typedef and accessor required by TR1.
752   template<typename _Key, typename _Value, typename _ExtractKey,
753            typename _H1, typename _H2>
754     struct _Hash_code_base<_Key, _Value, _ExtractKey, _H1, _H2,
755                            _Default_ranged_hash, true>
756     // See PR53067.
757     : public  _Hashtable_ebo_helper<0, _ExtractKey>,
758       public  _Hashtable_ebo_helper<1, _H1>,
759       public  _Hashtable_ebo_helper<2, _H2>
760     {
761     private:
762       typedef _Hashtable_ebo_helper<0, _ExtractKey> _EboExtractKey;
763       typedef _Hashtable_ebo_helper<1, _H1> _EboH1;
764       typedef _Hashtable_ebo_helper<2, _H2> _EboH2;
765
766     public:
767       typedef _H1 hasher;
768
769       hasher
770       hash_function() const
771       { return _M_h1(); }
772
773     protected:
774       _Hash_code_base(const _ExtractKey& __ex,
775                       const _H1& __h1, const _H2& __h2,
776                       const _Default_ranged_hash&)
777       : _EboExtractKey(__ex), _EboH1(__h1), _EboH2(__h2) { }
778
779       typedef std::size_t _Hash_code_type;
780
781       _Hash_code_type
782       _M_hash_code(const _Key& __k) const
783       { return _M_h1()(__k); }
784
785       std::size_t
786       _M_bucket_index(const _Key&, _Hash_code_type __c,
787                       std::size_t __n) const
788       { return _M_h2()(__c, __n); }
789
790       std::size_t
791       _M_bucket_index(const _Hash_node<_Value, true>* __p,
792                       std::size_t __n) const
793       { return _M_h2()(__p->_M_hash_code, __n); }
794
795       void
796       _M_store_code(_Hash_node<_Value, true>* __n, _Hash_code_type __c) const
797       { __n->_M_hash_code = __c; }
798
799       void
800       _M_copy_code(_Hash_node<_Value, true>* __to,
801                    const _Hash_node<_Value, true>* __from) const
802       { __to->_M_hash_code = __from->_M_hash_code; }
803
804       void
805       _M_swap(_Hash_code_base& __x)
806       {
807         std::swap(_M_extract(), __x._M_extract());
808         std::swap(_M_h1(), __x._M_h1());
809         std::swap(_M_h2(), __x._M_h2());
810       }
811
812     protected:
813       const _ExtractKey&
814       _M_extract() const { return _EboExtractKey::_S_cget(*this); }
815       _ExtractKey&
816       _M_extract() { return _EboExtractKey::_S_get(*this); }
817       const _H1&
818       _M_h1() const { return _EboH1::_S_cget(*this); }
819       _H1&
820       _M_h1() { return _EboH1::_S_get(*this); }
821       const _H2&
822       _M_h2() const { return _EboH2::_S_cget(*this); }
823       _H2&
824       _M_h2() { return _EboH2::_S_get(*this); }
825     };
826
827   template <typename _Key, typename _Value, typename _ExtractKey,
828             typename _Equal, typename _HashCodeType,
829             bool __cache_hash_code>
830   struct _Equal_helper;
831
832   template<typename _Key, typename _Value, typename _ExtractKey,
833            typename _Equal, typename _HashCodeType>
834   struct _Equal_helper<_Key, _Value, _ExtractKey, _Equal, _HashCodeType, true>
835   {
836     static bool
837     _S_equals(const _Equal& __eq, const _ExtractKey& __extract,
838               const _Key& __k, _HashCodeType __c,
839               _Hash_node<_Value, true>* __n)
840     { return __c == __n->_M_hash_code
841              && __eq(__k, __extract(__n->_M_v)); }
842   };
843
844   template<typename _Key, typename _Value, typename _ExtractKey,
845            typename _Equal, typename _HashCodeType>
846   struct _Equal_helper<_Key, _Value, _ExtractKey, _Equal, _HashCodeType, false>
847   {
848     static bool
849     _S_equals(const _Equal& __eq, const _ExtractKey& __extract,
850               const _Key& __k, _HashCodeType,
851               _Hash_node<_Value, false>* __n)
852     { return __eq(__k, __extract(__n->_M_v)); }
853   };
854
855   // Helper class adding management of _Equal functor to _Hash_code_base
856   // type.
857   template<typename _Key, typename _Value,
858            typename _ExtractKey, typename _Equal,
859            typename _H1, typename _H2, typename _Hash,
860            bool __cache_hash_code>
861   struct _Hashtable_base
862   // See PR53067.
863   : public  _Hash_code_base<_Key, _Value, _ExtractKey, _H1, _H2, _Hash,
864                             __cache_hash_code>,
865     public _Hashtable_ebo_helper<0, _Equal>
866   {
867   private:
868     typedef _Hashtable_ebo_helper<0, _Equal> _EboEqual;
869
870   protected:
871     typedef _Hash_code_base<_Key, _Value, _ExtractKey,
872                             _H1, _H2, _Hash, __cache_hash_code> _HCBase;
873     typedef typename _HCBase::_Hash_code_type _Hash_code_type;
874
875     _Hashtable_base(const _ExtractKey& __ex,
876                     const _H1& __h1, const _H2& __h2,
877                     const _Hash& __hash, const _Equal& __eq)
878       : _HCBase(__ex, __h1, __h2, __hash), _EboEqual(__eq) { }
879
880     bool
881     _M_equals(const _Key& __k, _Hash_code_type __c,
882               _Hash_node<_Value, __cache_hash_code>* __n) const
883     {
884       typedef _Equal_helper<_Key, _Value, _ExtractKey,
885                            _Equal, _Hash_code_type,
886                            __cache_hash_code> _EqualHelper;
887       return _EqualHelper::_S_equals(_M_eq(), this->_M_extract(),
888                                      __k, __c, __n);
889     }
890
891     void
892     _M_swap(_Hashtable_base& __x)
893     {
894       _HCBase::_M_swap(__x);
895       std::swap(_M_eq(), __x._M_eq());
896     }
897
898   protected:
899     const _Equal&
900     _M_eq() const { return _EboEqual::_S_cget(*this); }
901     _Equal&
902     _M_eq() { return _EboEqual::_S_get(*this); }
903   };
904
905   // Local iterators, used to iterate within a bucket but not between
906   // buckets.
907   template<typename _Key, typename _Value, typename _ExtractKey,
908            typename _H1, typename _H2, typename _Hash,
909            bool __cache_hash_code>
910     struct _Local_iterator_base;
911
912   template<typename _Key, typename _Value, typename _ExtractKey,
913            typename _H1, typename _H2, typename _Hash>
914     struct _Local_iterator_base<_Key, _Value, _ExtractKey,
915                                 _H1, _H2, _Hash, true>
916     // See PR53067.
917     : public _H2
918     {
919       _Local_iterator_base() = default;
920       _Local_iterator_base(_Hash_node<_Value, true>* __p,
921                            std::size_t __bkt, std::size_t __bkt_count)
922       : _M_cur(__p), _M_bucket(__bkt), _M_bucket_count(__bkt_count) { }
923
924       void
925       _M_incr()
926       {
927         _M_cur = _M_cur->_M_next();
928         if (_M_cur)
929           {
930             std::size_t __bkt = _M_h2()(_M_cur->_M_hash_code, _M_bucket_count);
931             if (__bkt != _M_bucket)
932               _M_cur = nullptr;
933           }
934       }
935
936       const _H2& _M_h2() const
937       { return *this; }
938
939       _Hash_node<_Value, true>*  _M_cur;
940       std::size_t _M_bucket;
941       std::size_t _M_bucket_count;
942     };
943
944   template<typename _Key, typename _Value, typename _ExtractKey,
945            typename _H1, typename _H2, typename _Hash>
946     struct _Local_iterator_base<_Key, _Value, _ExtractKey,
947                                 _H1, _H2, _Hash, false>
948     // See PR53067.
949     : public _Hash_code_base<_Key, _Value, _ExtractKey,
950                              _H1, _H2, _Hash, false>
951     {
952       _Local_iterator_base() = default;
953       _Local_iterator_base(_Hash_node<_Value, false>* __p,
954                            std::size_t __bkt, std::size_t __bkt_count)
955       : _M_cur(__p), _M_bucket(__bkt), _M_bucket_count(__bkt_count) { }
956
957       void
958       _M_incr()
959       {
960         _M_cur = _M_cur->_M_next();
961         if (_M_cur)
962           {
963             std::size_t __bkt = this->_M_bucket_index(_M_cur, _M_bucket_count);
964             if (__bkt != _M_bucket)
965               _M_cur = nullptr;
966           }
967       }
968
969       _Hash_node<_Value, false>*  _M_cur;
970       std::size_t _M_bucket;
971       std::size_t _M_bucket_count;
972     };
973
974   template<typename _Key, typename _Value, typename _ExtractKey,
975            typename _H1, typename _H2, typename _Hash, bool __cache>
976     inline bool
977     operator==(const _Local_iterator_base<_Key, _Value, _ExtractKey,
978                                           _H1, _H2, _Hash, __cache>& __x,
979                const _Local_iterator_base<_Key, _Value, _ExtractKey,
980                                           _H1, _H2, _Hash, __cache>& __y)
981     { return __x._M_cur == __y._M_cur; }
982
983   template<typename _Key, typename _Value, typename _ExtractKey,
984            typename _H1, typename _H2, typename _Hash, bool __cache>
985     inline bool
986     operator!=(const _Local_iterator_base<_Key, _Value, _ExtractKey,
987                                           _H1, _H2, _Hash, __cache>& __x,
988                const _Local_iterator_base<_Key, _Value, _ExtractKey,
989                                           _H1, _H2, _Hash, __cache>& __y)
990     { return __x._M_cur != __y._M_cur; }
991
992   template<typename _Key, typename _Value, typename _ExtractKey,
993            typename _H1, typename _H2, typename _Hash,
994            bool __constant_iterators, bool __cache>
995     struct _Local_iterator
996     : public _Local_iterator_base<_Key, _Value, _ExtractKey,
997                                   _H1, _H2, _Hash, __cache>
998     {
999       typedef _Value                                   value_type;
1000       typedef typename std::conditional<__constant_iterators,
1001                                         const _Value*, _Value*>::type
1002                                                        pointer;
1003       typedef typename std::conditional<__constant_iterators,
1004                                         const _Value&, _Value&>::type
1005                                                        reference;
1006       typedef std::ptrdiff_t                           difference_type;
1007       typedef std::forward_iterator_tag                iterator_category;
1008
1009       _Local_iterator() = default;
1010
1011       explicit
1012       _Local_iterator(_Hash_node<_Value, __cache>* __p,
1013                       std::size_t __bkt, std::size_t __bkt_count)
1014       : _Local_iterator_base<_Key, _Value, _ExtractKey, _H1, _H2, _Hash,
1015                              __cache>(__p, __bkt, __bkt_count)
1016       { }
1017
1018       reference
1019       operator*() const
1020       { return this->_M_cur->_M_v; }
1021
1022       pointer
1023       operator->() const
1024       { return std::__addressof(this->_M_cur->_M_v); }
1025
1026       _Local_iterator&
1027       operator++()
1028       {
1029         this->_M_incr();
1030         return *this;
1031       }
1032
1033       _Local_iterator
1034       operator++(int)
1035       {
1036         _Local_iterator __tmp(*this);
1037         this->_M_incr();
1038         return __tmp;
1039       }
1040     };
1041
1042   template<typename _Key, typename _Value, typename _ExtractKey,
1043            typename _H1, typename _H2, typename _Hash,
1044            bool __constant_iterators, bool __cache>
1045     struct _Local_const_iterator
1046     : public _Local_iterator_base<_Key, _Value, _ExtractKey,
1047                                   _H1, _H2, _Hash, __cache>
1048     {
1049       typedef _Value                                   value_type;
1050       typedef const _Value*                            pointer;
1051       typedef const _Value&                            reference;
1052       typedef std::ptrdiff_t                           difference_type;
1053       typedef std::forward_iterator_tag                iterator_category;
1054
1055       _Local_const_iterator() = default;
1056
1057       explicit
1058       _Local_const_iterator(_Hash_node<_Value, __cache>* __p,
1059                             std::size_t __bkt, std::size_t __bkt_count)
1060       : _Local_iterator_base<_Key, _Value, _ExtractKey, _H1, _H2, _Hash,
1061                              __cache>(__p, __bkt, __bkt_count)
1062       { }
1063
1064       _Local_const_iterator(const _Local_iterator<_Key, _Value, _ExtractKey,
1065                                                   _H1, _H2, _Hash,
1066                                                   __constant_iterators,
1067                                                   __cache>& __x)
1068       : _Local_iterator_base<_Key, _Value, _ExtractKey, _H1, _H2, _Hash,
1069                              __cache>(__x._M_cur, __x._M_bucket,
1070                                       __x._M_bucket_count)
1071       { }
1072
1073       reference
1074       operator*() const
1075       { return this->_M_cur->_M_v; }
1076
1077       pointer
1078       operator->() const
1079       { return std::__addressof(this->_M_cur->_M_v); }
1080
1081       _Local_const_iterator&
1082       operator++()
1083       {
1084         this->_M_incr();
1085         return *this;
1086       }
1087
1088       _Local_const_iterator
1089       operator++(int)
1090       {
1091         _Local_const_iterator __tmp(*this);
1092         this->_M_incr();
1093         return __tmp;
1094       }
1095     };
1096
1097
1098   // Class template _Equality_base.  This is for implementing equality
1099   // comparison for unordered containers, per N3068, by John Lakos and
1100   // Pablo Halpern.  Algorithmically, we follow closely the reference
1101   // implementations therein.
1102   template<typename _ExtractKey, bool __unique_keys,
1103            typename _Hashtable>
1104     struct _Equality_base;
1105
1106   template<typename _ExtractKey, typename _Hashtable>
1107     struct _Equality_base<_ExtractKey, true, _Hashtable>
1108     {
1109       bool _M_equal(const _Hashtable&) const;
1110     };
1111
1112   template<typename _ExtractKey, typename _Hashtable>
1113     bool
1114     _Equality_base<_ExtractKey, true, _Hashtable>::
1115     _M_equal(const _Hashtable& __other) const
1116     {
1117       const _Hashtable* __this = static_cast<const _Hashtable*>(this);
1118
1119       if (__this->size() != __other.size())
1120         return false;
1121
1122       for (auto __itx = __this->begin(); __itx != __this->end(); ++__itx)
1123         {
1124           const auto __ity = __other.find(_ExtractKey()(*__itx));
1125           if (__ity == __other.end() || !bool(*__ity == *__itx))
1126             return false;
1127         }
1128       return true;
1129     }
1130
1131   template<typename _ExtractKey, typename _Hashtable>
1132     struct _Equality_base<_ExtractKey, false, _Hashtable>
1133     {
1134       bool _M_equal(const _Hashtable&) const;
1135
1136     private:
1137       template<typename _Uiterator>
1138         static bool
1139         _S_is_permutation(_Uiterator, _Uiterator, _Uiterator);
1140     };
1141
1142   // See std::is_permutation in N3068.
1143   template<typename _ExtractKey, typename _Hashtable>
1144     template<typename _Uiterator>
1145       bool
1146       _Equality_base<_ExtractKey, false, _Hashtable>::
1147       _S_is_permutation(_Uiterator __first1, _Uiterator __last1,
1148                         _Uiterator __first2)
1149       {
1150         for (; __first1 != __last1; ++__first1, ++__first2)
1151           if (!(*__first1 == *__first2))
1152             break;
1153
1154         if (__first1 == __last1)
1155           return true;
1156
1157         _Uiterator __last2 = __first2;
1158         std::advance(__last2, std::distance(__first1, __last1));
1159
1160         for (_Uiterator __it1 = __first1; __it1 != __last1; ++__it1)
1161           {
1162             _Uiterator __tmp =  __first1;
1163             while (__tmp != __it1 && !bool(*__tmp == *__it1))
1164               ++__tmp;
1165
1166             // We've seen this one before.
1167             if (__tmp != __it1)
1168               continue;
1169
1170             std::ptrdiff_t __n2 = 0;
1171             for (__tmp = __first2; __tmp != __last2; ++__tmp)
1172               if (*__tmp == *__it1)
1173                 ++__n2;
1174
1175             if (!__n2)
1176               return false;
1177
1178             std::ptrdiff_t __n1 = 0;
1179             for (__tmp = __it1; __tmp != __last1; ++__tmp)
1180               if (*__tmp == *__it1)
1181                 ++__n1;
1182
1183             if (__n1 != __n2)
1184               return false;
1185           }
1186         return true;
1187       }
1188
1189   template<typename _ExtractKey, typename _Hashtable>
1190     bool
1191     _Equality_base<_ExtractKey, false, _Hashtable>::
1192     _M_equal(const _Hashtable& __other) const
1193     {
1194       const _Hashtable* __this = static_cast<const _Hashtable*>(this);
1195
1196       if (__this->size() != __other.size())
1197         return false;
1198
1199       for (auto __itx = __this->begin(); __itx != __this->end();)
1200         {
1201           const auto __xrange = __this->equal_range(_ExtractKey()(*__itx));
1202           const auto __yrange = __other.equal_range(_ExtractKey()(*__itx));
1203
1204           if (std::distance(__xrange.first, __xrange.second)
1205               != std::distance(__yrange.first, __yrange.second))
1206             return false;
1207
1208           if (!_S_is_permutation(__xrange.first,
1209                                  __xrange.second,
1210                                  __yrange.first))
1211             return false;
1212
1213           __itx = __xrange.second;
1214         }
1215       return true;
1216     }
1217
1218 _GLIBCXX_END_NAMESPACE_VERSION
1219 } // namespace __detail
1220 } // namespace std
1221
1222 #endif // _HASHTABLE_POLICY_H