OSDN Git Service

acb7e99a8dfb3ab1666c4d1759aef75806314107
[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 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   // Auxiliary types used for all instantiations of _Hashtable: nodes
63   // and iterators.
64
65   // Nodes, used to wrap elements stored in the hash table.  A policy
66   // template parameter of class template _Hashtable controls whether
67   // nodes also store a hash code. In some cases (e.g. strings) this
68   // may be a performance win.
69   template<typename _Value, bool __cache_hash_code>
70     struct _Hash_node;
71
72   template<typename _Value>
73     struct _Hash_node<_Value, true>
74     {
75       _Value       _M_v;
76       std::size_t  _M_hash_code;
77       _Hash_node*  _M_next;
78
79       template<typename... _Args>
80         _Hash_node(_Args&&... __args)
81         : _M_v(std::forward<_Args>(__args)...),
82           _M_hash_code(), _M_next() { }
83     };
84
85   template<typename _Value>
86     struct _Hash_node<_Value, false>
87     {
88       _Value       _M_v;
89       _Hash_node*  _M_next;
90
91       template<typename... _Args>
92         _Hash_node(_Args&&... __args)
93         : _M_v(std::forward<_Args>(__args)...),
94           _M_next() { }
95     };
96
97   // Local iterators, used to iterate within a bucket but not between
98   // buckets.
99   template<typename _Value, bool __cache>
100     struct _Node_iterator_base
101     {
102       _Node_iterator_base(_Hash_node<_Value, __cache>* __p)
103       : _M_cur(__p) { }
104
105       void
106       _M_incr()
107       { _M_cur = _M_cur->_M_next; }
108
109       _Hash_node<_Value, __cache>*  _M_cur;
110     };
111
112   template<typename _Value, bool __cache>
113     inline bool
114     operator==(const _Node_iterator_base<_Value, __cache>& __x,
115                const _Node_iterator_base<_Value, __cache>& __y)
116     { return __x._M_cur == __y._M_cur; }
117
118   template<typename _Value, bool __cache>
119     inline bool
120     operator!=(const _Node_iterator_base<_Value, __cache>& __x,
121                const _Node_iterator_base<_Value, __cache>& __y)
122     { return __x._M_cur != __y._M_cur; }
123
124   template<typename _Value, bool __constant_iterators, bool __cache>
125     struct _Node_iterator
126     : public _Node_iterator_base<_Value, __cache>
127     {
128       typedef _Value                                   value_type;
129       typedef typename std::conditional<__constant_iterators,
130                                         const _Value*, _Value*>::type
131                                                        pointer;
132       typedef typename std::conditional<__constant_iterators,
133                                         const _Value&, _Value&>::type
134                                                        reference;
135       typedef std::ptrdiff_t                           difference_type;
136       typedef std::forward_iterator_tag                iterator_category;
137
138       _Node_iterator()
139       : _Node_iterator_base<_Value, __cache>(0) { }
140
141       explicit
142       _Node_iterator(_Hash_node<_Value, __cache>* __p)
143       : _Node_iterator_base<_Value, __cache>(__p) { }
144
145       reference
146       operator*() const
147       { return this->_M_cur->_M_v; }
148
149       pointer
150       operator->() const
151       { return std::__addressof(this->_M_cur->_M_v); }
152
153       _Node_iterator&
154       operator++()
155       {
156         this->_M_incr();
157         return *this;
158       }
159
160       _Node_iterator
161       operator++(int)
162       {
163         _Node_iterator __tmp(*this);
164         this->_M_incr();
165         return __tmp;
166       }
167     };
168
169   template<typename _Value, bool __constant_iterators, bool __cache>
170     struct _Node_const_iterator
171     : public _Node_iterator_base<_Value, __cache>
172     {
173       typedef _Value                                   value_type;
174       typedef const _Value*                            pointer;
175       typedef const _Value&                            reference;
176       typedef std::ptrdiff_t                           difference_type;
177       typedef std::forward_iterator_tag                iterator_category;
178
179       _Node_const_iterator()
180       : _Node_iterator_base<_Value, __cache>(0) { }
181
182       explicit
183       _Node_const_iterator(_Hash_node<_Value, __cache>* __p)
184       : _Node_iterator_base<_Value, __cache>(__p) { }
185
186       _Node_const_iterator(const _Node_iterator<_Value, __constant_iterators,
187                            __cache>& __x)
188       : _Node_iterator_base<_Value, __cache>(__x._M_cur) { }
189
190       reference
191       operator*() const
192       { return this->_M_cur->_M_v; }
193
194       pointer
195       operator->() const
196       { return std::__addressof(this->_M_cur->_M_v); }
197
198       _Node_const_iterator&
199       operator++()
200       {
201         this->_M_incr();
202         return *this;
203       }
204
205       _Node_const_iterator
206       operator++(int)
207       {
208         _Node_const_iterator __tmp(*this);
209         this->_M_incr();
210         return __tmp;
211       }
212     };
213
214   template<typename _Value, bool __cache>
215     struct _Hashtable_iterator_base
216     {
217       _Hashtable_iterator_base(_Hash_node<_Value, __cache>* __node,
218                                _Hash_node<_Value, __cache>** __bucket)
219       : _M_cur_node(__node), _M_cur_bucket(__bucket) { }
220
221       void
222       _M_incr()
223       {
224         _M_cur_node = _M_cur_node->_M_next;
225         if (!_M_cur_node)
226           _M_incr_bucket();
227       }
228
229       void
230       _M_incr_bucket();
231
232       _Hash_node<_Value, __cache>*   _M_cur_node;
233       _Hash_node<_Value, __cache>**  _M_cur_bucket;
234     };
235
236   // Global iterators, used for arbitrary iteration within a hash
237   // table.  Larger and more expensive than local iterators.
238   template<typename _Value, bool __cache>
239     void
240     _Hashtable_iterator_base<_Value, __cache>::
241     _M_incr_bucket()
242     {
243       ++_M_cur_bucket;
244
245       // This loop requires the bucket array to have a non-null sentinel.
246       while (!*_M_cur_bucket)
247         ++_M_cur_bucket;
248       _M_cur_node = *_M_cur_bucket;
249     }
250
251   template<typename _Value, bool __cache>
252     inline bool
253     operator==(const _Hashtable_iterator_base<_Value, __cache>& __x,
254                const _Hashtable_iterator_base<_Value, __cache>& __y)
255     { return __x._M_cur_node == __y._M_cur_node; }
256
257   template<typename _Value, bool __cache>
258     inline bool
259     operator!=(const _Hashtable_iterator_base<_Value, __cache>& __x,
260                const _Hashtable_iterator_base<_Value, __cache>& __y)
261     { return __x._M_cur_node != __y._M_cur_node; }
262
263   template<typename _Value, bool __constant_iterators, bool __cache>
264     struct _Hashtable_iterator
265     : public _Hashtable_iterator_base<_Value, __cache>
266     {
267       typedef _Value                                   value_type;
268       typedef typename std::conditional<__constant_iterators,
269                                         const _Value*, _Value*>::type
270                                                        pointer;
271       typedef typename std::conditional<__constant_iterators,
272                                         const _Value&, _Value&>::type
273                                                        reference;
274       typedef std::ptrdiff_t                           difference_type;
275       typedef std::forward_iterator_tag                iterator_category;
276
277       _Hashtable_iterator()
278       : _Hashtable_iterator_base<_Value, __cache>(0, 0) { }
279
280       _Hashtable_iterator(_Hash_node<_Value, __cache>* __p,
281                           _Hash_node<_Value, __cache>** __b)
282       : _Hashtable_iterator_base<_Value, __cache>(__p, __b) { }
283
284       explicit
285       _Hashtable_iterator(_Hash_node<_Value, __cache>** __b)
286       : _Hashtable_iterator_base<_Value, __cache>(*__b, __b) { }
287
288       reference
289       operator*() const
290       { return this->_M_cur_node->_M_v; }
291
292       pointer
293       operator->() const
294       { return std::__addressof(this->_M_cur_node->_M_v); }
295
296       _Hashtable_iterator&
297       operator++()
298       {
299         this->_M_incr();
300         return *this;
301       }
302
303       _Hashtable_iterator
304       operator++(int)
305       {
306         _Hashtable_iterator __tmp(*this);
307         this->_M_incr();
308         return __tmp;
309       }
310     };
311
312   template<typename _Value, bool __constant_iterators, bool __cache>
313     struct _Hashtable_const_iterator
314     : public _Hashtable_iterator_base<_Value, __cache>
315     {
316       typedef _Value                                   value_type;
317       typedef const _Value*                            pointer;
318       typedef const _Value&                            reference;
319       typedef std::ptrdiff_t                           difference_type;
320       typedef std::forward_iterator_tag                iterator_category;
321
322       _Hashtable_const_iterator()
323       : _Hashtable_iterator_base<_Value, __cache>(0, 0) { }
324
325       _Hashtable_const_iterator(_Hash_node<_Value, __cache>* __p,
326                                 _Hash_node<_Value, __cache>** __b)
327       : _Hashtable_iterator_base<_Value, __cache>(__p, __b) { }
328
329       explicit
330       _Hashtable_const_iterator(_Hash_node<_Value, __cache>** __b)
331       : _Hashtable_iterator_base<_Value, __cache>(*__b, __b) { }
332
333       _Hashtable_const_iterator(const _Hashtable_iterator<_Value,
334                                 __constant_iterators, __cache>& __x)
335       : _Hashtable_iterator_base<_Value, __cache>(__x._M_cur_node,
336                                                   __x._M_cur_bucket) { }
337
338       reference
339       operator*() const
340       { return this->_M_cur_node->_M_v; }
341
342       pointer
343       operator->() const
344       { return std::__addressof(this->_M_cur_node->_M_v); }
345
346       _Hashtable_const_iterator&
347       operator++()
348       {
349         this->_M_incr();
350         return *this;
351       }
352
353       _Hashtable_const_iterator
354       operator++(int)
355       {
356         _Hashtable_const_iterator __tmp(*this);
357         this->_M_incr();
358         return __tmp;
359       }
360     };
361
362
363   // Many of class template _Hashtable's template parameters are policy
364   // classes.  These are defaults for the policies.
365
366   // Default range hashing function: use division to fold a large number
367   // into the range [0, N).
368   struct _Mod_range_hashing
369   {
370     typedef std::size_t first_argument_type;
371     typedef std::size_t second_argument_type;
372     typedef std::size_t result_type;
373
374     result_type
375     operator()(first_argument_type __num, second_argument_type __den) const
376     { return __num % __den; }
377   };
378
379   // Default ranged hash function H.  In principle it should be a
380   // function object composed from objects of type H1 and H2 such that
381   // h(k, N) = h2(h1(k), N), but that would mean making extra copies of
382   // h1 and h2.  So instead we'll just use a tag to tell class template
383   // hashtable to do that composition.
384   struct _Default_ranged_hash { };
385
386   // Default value for rehash policy.  Bucket size is (usually) the
387   // smallest prime that keeps the load factor small enough.
388   struct _Prime_rehash_policy
389   {
390     _Prime_rehash_policy(float __z = 1.0)
391     : _M_max_load_factor(__z), _M_growth_factor(2.f), _M_next_resize(0) { }
392
393     float
394     max_load_factor() const noexcept
395     { return _M_max_load_factor; }
396
397     // Return a bucket size no smaller than n.
398     std::size_t
399     _M_next_bkt(std::size_t __n) const;
400
401     // Return a bucket count appropriate for n elements
402     std::size_t
403     _M_bkt_for_elements(std::size_t __n) const;
404
405     // __n_bkt is current bucket count, __n_elt is current element count,
406     // and __n_ins is number of elements to be inserted.  Do we need to
407     // increase bucket count?  If so, return make_pair(true, n), where n
408     // is the new bucket count.  If not, return make_pair(false, 0).
409     std::pair<bool, std::size_t>
410     _M_need_rehash(std::size_t __n_bkt, std::size_t __n_elt,
411                    std::size_t __n_ins) const;
412
413     enum { _S_n_primes = sizeof(unsigned long) != 8 ? 256 : 256 + 48 };
414
415     float                _M_max_load_factor;
416     float                _M_growth_factor;
417     mutable std::size_t  _M_next_resize;
418   };
419
420   extern const unsigned long __prime_list[];
421
422   // XXX This is a hack.  There's no good reason for any of
423   // _Prime_rehash_policy's member functions to be inline.
424
425   // Return a prime no smaller than n.
426   inline std::size_t
427   _Prime_rehash_policy::
428   _M_next_bkt(std::size_t __n) const
429   {
430     // Optimize lookups involving the first elements of __prime_list.
431     // (useful to speed-up, eg, constructors)
432     static const unsigned char __fast_bkt[12]
433       = { 2, 2, 2, 3, 5, 5, 7, 7, 11, 11, 11, 11 };
434
435     const unsigned long __p
436       = __n <= 11 ? __fast_bkt[__n]
437                   : *std::lower_bound(__prime_list + 5,
438                                       __prime_list + _S_n_primes, __n);
439     _M_next_resize = __builtin_floor(__p * (long double)_M_max_load_factor);
440     return __p;
441   }
442
443   // Return the smallest prime p such that alpha p >= n, where alpha
444   // is the load factor.
445   inline std::size_t
446   _Prime_rehash_policy::
447   _M_bkt_for_elements(std::size_t __n) const
448   { return _M_next_bkt(__builtin_ceil(__n / (long double)_M_max_load_factor)); }
449
450   // Finds the smallest prime p such that alpha p > __n_elt + __n_ins.
451   // If p > __n_bkt, return make_pair(true, p); otherwise return
452   // make_pair(false, 0).  In principle this isn't very different from
453   // _M_bkt_for_elements.
454
455   // The only tricky part is that we're caching the element count at
456   // which we need to rehash, so we don't have to do a floating-point
457   // multiply for every insertion.
458
459   inline std::pair<bool, std::size_t>
460   _Prime_rehash_policy::
461   _M_need_rehash(std::size_t __n_bkt, std::size_t __n_elt,
462                  std::size_t __n_ins) const
463   {
464     if (__n_elt + __n_ins > _M_next_resize)
465       {
466         long double __min_bkts = ((__n_elt + __n_ins)
467                                   / (long double)_M_max_load_factor);
468         if (__min_bkts > __n_bkt)
469           {
470             __min_bkts = std::max(__min_bkts, (long double)_M_growth_factor
471                                   * __n_bkt);
472             return std::make_pair(true,
473                                   _M_next_bkt(__builtin_ceil(__min_bkts)));
474           }
475         else
476           {
477             _M_next_resize
478               = __builtin_floor(__n_bkt * (long double)_M_max_load_factor);
479             return std::make_pair(false, 0);
480           }
481       }
482     else
483       return std::make_pair(false, 0);
484   }
485
486   // Base classes for std::_Hashtable.  We define these base classes
487   // because in some cases we want to do different things depending
488   // on the value of a policy class.  In some cases the policy class
489   // affects which member functions and nested typedefs are defined;
490   // we handle that by specializing base class templates.  Several of
491   // the base class templates need to access other members of class
492   // template _Hashtable, so we use the "curiously recurring template
493   // pattern" for them.
494
495   // class template _Map_base.  If the hashtable has a value type of
496   // the form pair<T1, T2> and a key extraction policy that returns the
497   // first part of the pair, the hashtable gets a mapped_type typedef.
498   // If it satisfies those criteria and also has unique keys, then it
499   // also gets an operator[].
500   template<typename _Key, typename _Value, typename _Ex, bool __unique,
501            typename _Hashtable>
502     struct _Map_base { };
503
504   template<typename _Key, typename _Pair, typename _Hashtable>
505     struct _Map_base<_Key, _Pair, std::_Select1st<_Pair>, false, _Hashtable>
506     {
507       typedef typename _Pair::second_type mapped_type;
508     };
509
510   template<typename _Key, typename _Pair, typename _Hashtable>
511     struct _Map_base<_Key, _Pair, std::_Select1st<_Pair>, true, _Hashtable>
512     {
513       typedef typename _Pair::second_type mapped_type;
514
515       mapped_type&
516       operator[](const _Key& __k);
517
518       mapped_type&
519       operator[](_Key&& __k);
520
521       // _GLIBCXX_RESOLVE_LIB_DEFECTS
522       // DR 761. unordered_map needs an at() member function.
523       mapped_type&
524       at(const _Key& __k);
525
526       const mapped_type&
527       at(const _Key& __k) const;
528     };
529
530   template<typename _Key, typename _Pair, typename _Hashtable>
531     typename _Map_base<_Key, _Pair, std::_Select1st<_Pair>,
532                        true, _Hashtable>::mapped_type&
533     _Map_base<_Key, _Pair, std::_Select1st<_Pair>, true, _Hashtable>::
534     operator[](const _Key& __k)
535     {
536       _Hashtable* __h = static_cast<_Hashtable*>(this);
537       typename _Hashtable::_Hash_code_type __code = __h->_M_hash_code(__k);
538       std::size_t __n = __h->_M_bucket_index(__k, __code,
539                                              __h->_M_bucket_count);
540
541       typename _Hashtable::_Node* __p =
542         __h->_M_find_node(__h->_M_buckets[__n], __k, __code);
543       if (!__p)
544         return __h->_M_insert_bucket(std::make_pair(__k, mapped_type()),
545                                      __n, __code)->second;
546       return (__p->_M_v).second;
547     }
548
549   template<typename _Key, typename _Pair, typename _Hashtable>
550     typename _Map_base<_Key, _Pair, std::_Select1st<_Pair>,
551                        true, _Hashtable>::mapped_type&
552     _Map_base<_Key, _Pair, std::_Select1st<_Pair>, true, _Hashtable>::
553     operator[](_Key&& __k)
554     {
555       _Hashtable* __h = static_cast<_Hashtable*>(this);
556       typename _Hashtable::_Hash_code_type __code = __h->_M_hash_code(__k);
557       std::size_t __n = __h->_M_bucket_index(__k, __code,
558                                              __h->_M_bucket_count);
559
560       typename _Hashtable::_Node* __p =
561         __h->_M_find_node(__h->_M_buckets[__n], __k, __code);
562       if (!__p)
563         return __h->_M_insert_bucket(std::make_pair(std::move(__k),
564                                                     mapped_type()),
565                                      __n, __code)->second;
566       return (__p->_M_v).second;
567     }
568
569   template<typename _Key, typename _Pair, typename _Hashtable>
570     typename _Map_base<_Key, _Pair, std::_Select1st<_Pair>,
571                        true, _Hashtable>::mapped_type&
572     _Map_base<_Key, _Pair, std::_Select1st<_Pair>, true, _Hashtable>::
573     at(const _Key& __k)
574     {
575       _Hashtable* __h = static_cast<_Hashtable*>(this);
576       typename _Hashtable::_Hash_code_type __code = __h->_M_hash_code(__k);
577       std::size_t __n = __h->_M_bucket_index(__k, __code,
578                                              __h->_M_bucket_count);
579
580       typename _Hashtable::_Node* __p =
581         __h->_M_find_node(__h->_M_buckets[__n], __k, __code);
582       if (!__p)
583         __throw_out_of_range(__N("_Map_base::at"));
584       return (__p->_M_v).second;
585     }
586
587   template<typename _Key, typename _Pair, typename _Hashtable>
588     const typename _Map_base<_Key, _Pair, std::_Select1st<_Pair>,
589                              true, _Hashtable>::mapped_type&
590     _Map_base<_Key, _Pair, std::_Select1st<_Pair>, true, _Hashtable>::
591     at(const _Key& __k) const
592     {
593       const _Hashtable* __h = static_cast<const _Hashtable*>(this);
594       typename _Hashtable::_Hash_code_type __code = __h->_M_hash_code(__k);
595       std::size_t __n = __h->_M_bucket_index(__k, __code,
596                                              __h->_M_bucket_count);
597
598       typename _Hashtable::_Node* __p =
599         __h->_M_find_node(__h->_M_buckets[__n], __k, __code);
600       if (!__p)
601         __throw_out_of_range(__N("_Map_base::at"));
602       return (__p->_M_v).second;
603     }
604
605   // class template _Rehash_base.  Give hashtable the max_load_factor
606   // functions and reserve iff the rehash policy is _Prime_rehash_policy.
607   template<typename _RehashPolicy, typename _Hashtable>
608     struct _Rehash_base { };
609
610   template<typename _Hashtable>
611     struct _Rehash_base<_Prime_rehash_policy, _Hashtable>
612     {
613       float
614       max_load_factor() const noexcept
615       {
616         const _Hashtable* __this = static_cast<const _Hashtable*>(this);
617         return __this->__rehash_policy().max_load_factor();
618       }
619
620       void
621       max_load_factor(float __z)
622       {
623         _Hashtable* __this = static_cast<_Hashtable*>(this);
624         __this->__rehash_policy(_Prime_rehash_policy(__z));
625       }
626
627       void
628       reserve(std::size_t __n)
629       {
630         _Hashtable* __this = static_cast<_Hashtable*>(this);
631         __this->rehash(__builtin_ceil(__n / max_load_factor()));
632       }
633     };
634
635   // Class template _Hash_code_base.  Encapsulates two policy issues that
636   // aren't quite orthogonal.
637   //   (1) the difference between using a ranged hash function and using
638   //       the combination of a hash function and a range-hashing function.
639   //       In the former case we don't have such things as hash codes, so
640   //       we have a dummy type as placeholder.
641   //   (2) Whether or not we cache hash codes.  Caching hash codes is
642   //       meaningless if we have a ranged hash function.
643   // We also put the key extraction and equality comparison function
644   // objects here, for convenience.
645
646   // Primary template: unused except as a hook for specializations.
647   template<typename _Key, typename _Value,
648            typename _ExtractKey, typename _Equal,
649            typename _H1, typename _H2, typename _Hash,
650            bool __cache_hash_code>
651     struct _Hash_code_base;
652
653   // Specialization: ranged hash function, no caching hash codes.  H1
654   // and H2 are provided but ignored.  We define a dummy hash code type.
655   template<typename _Key, typename _Value,
656            typename _ExtractKey, typename _Equal,
657            typename _H1, typename _H2, typename _Hash>
658     struct _Hash_code_base<_Key, _Value, _ExtractKey, _Equal, _H1, _H2,
659                            _Hash, false>
660     {
661     protected:
662       _Hash_code_base(const _ExtractKey& __ex, const _Equal& __eq,
663                       const _H1&, const _H2&, const _Hash& __h)
664       : _M_extract(__ex), _M_eq(__eq), _M_ranged_hash(__h) { }
665
666       typedef void* _Hash_code_type;
667
668       _Hash_code_type
669       _M_hash_code(const _Key& __key) const
670       { return 0; }
671
672       std::size_t
673       _M_bucket_index(const _Key& __k, _Hash_code_type,
674                       std::size_t __n) const
675       { return _M_ranged_hash(__k, __n); }
676
677       std::size_t
678       _M_bucket_index(const _Hash_node<_Value, false>* __p,
679                       std::size_t __n) const
680       { return _M_ranged_hash(_M_extract(__p->_M_v), __n); }
681
682       bool
683       _M_compare(const _Key& __k, _Hash_code_type,
684                  _Hash_node<_Value, false>* __n) const
685       { return _M_eq(__k, _M_extract(__n->_M_v)); }
686
687       void
688       _M_store_code(_Hash_node<_Value, false>*, _Hash_code_type) const
689       { }
690
691       void
692       _M_copy_code(_Hash_node<_Value, false>*,
693                    const _Hash_node<_Value, false>*) const
694       { }
695
696       void
697       _M_swap(_Hash_code_base& __x)
698       {
699         std::swap(_M_extract, __x._M_extract);
700         std::swap(_M_eq, __x._M_eq);
701         std::swap(_M_ranged_hash, __x._M_ranged_hash);
702       }
703
704     protected:
705       _ExtractKey  _M_extract;
706       _Equal       _M_eq;
707       _Hash        _M_ranged_hash;
708     };
709
710
711   // No specialization for ranged hash function while caching hash codes.
712   // That combination is meaningless, and trying to do it is an error.
713
714
715   // Specialization: ranged hash function, cache hash codes.  This
716   // combination is meaningless, so we provide only a declaration
717   // and no definition.
718   template<typename _Key, typename _Value,
719            typename _ExtractKey, typename _Equal,
720            typename _H1, typename _H2, typename _Hash>
721     struct _Hash_code_base<_Key, _Value, _ExtractKey, _Equal, _H1, _H2,
722                            _Hash, true>;
723
724   // Specialization: hash function and range-hashing function, no
725   // caching of hash codes.  H is provided but ignored.  Provides
726   // typedef and accessor required by TR1.
727   template<typename _Key, typename _Value,
728            typename _ExtractKey, typename _Equal,
729            typename _H1, typename _H2>
730     struct _Hash_code_base<_Key, _Value, _ExtractKey, _Equal, _H1, _H2,
731                            _Default_ranged_hash, false>
732     {
733       typedef _H1 hasher;
734
735       hasher
736       hash_function() const
737       { return _M_h1; }
738
739     protected:
740       _Hash_code_base(const _ExtractKey& __ex, const _Equal& __eq,
741                       const _H1& __h1, const _H2& __h2,
742                       const _Default_ranged_hash&)
743       : _M_extract(__ex), _M_eq(__eq), _M_h1(__h1), _M_h2(__h2) { }
744
745       typedef std::size_t _Hash_code_type;
746
747       _Hash_code_type
748       _M_hash_code(const _Key& __k) const
749       { return _M_h1(__k); }
750
751       std::size_t
752       _M_bucket_index(const _Key&, _Hash_code_type __c,
753                       std::size_t __n) const
754       { return _M_h2(__c, __n); }
755
756       std::size_t
757       _M_bucket_index(const _Hash_node<_Value, false>* __p,
758                       std::size_t __n) const
759       { return _M_h2(_M_h1(_M_extract(__p->_M_v)), __n); }
760
761       bool
762       _M_compare(const _Key& __k, _Hash_code_type,
763                  _Hash_node<_Value, false>* __n) const
764       { return _M_eq(__k, _M_extract(__n->_M_v)); }
765
766       void
767       _M_store_code(_Hash_node<_Value, false>*, _Hash_code_type) const
768       { }
769
770       void
771       _M_copy_code(_Hash_node<_Value, false>*,
772                    const _Hash_node<_Value, false>*) const
773       { }
774
775       void
776       _M_swap(_Hash_code_base& __x)
777       {
778         std::swap(_M_extract, __x._M_extract);
779         std::swap(_M_eq, __x._M_eq);
780         std::swap(_M_h1, __x._M_h1);
781         std::swap(_M_h2, __x._M_h2);
782       }
783
784     protected:
785       _ExtractKey  _M_extract;
786       _Equal       _M_eq;
787       _H1          _M_h1;
788       _H2          _M_h2;
789     };
790
791   // Specialization: hash function and range-hashing function,
792   // caching hash codes.  H is provided but ignored.  Provides
793   // typedef and accessor required by TR1.
794   template<typename _Key, typename _Value,
795            typename _ExtractKey, typename _Equal,
796            typename _H1, typename _H2>
797     struct _Hash_code_base<_Key, _Value, _ExtractKey, _Equal, _H1, _H2,
798                            _Default_ranged_hash, true>
799     {
800       typedef _H1 hasher;
801
802       hasher
803       hash_function() const
804       { return _M_h1; }
805
806     protected:
807       _Hash_code_base(const _ExtractKey& __ex, const _Equal& __eq,
808                       const _H1& __h1, const _H2& __h2,
809                       const _Default_ranged_hash&)
810       : _M_extract(__ex), _M_eq(__eq), _M_h1(__h1), _M_h2(__h2) { }
811
812       typedef std::size_t _Hash_code_type;
813
814       _Hash_code_type
815       _M_hash_code(const _Key& __k) const
816       { return _M_h1(__k); }
817
818       std::size_t
819       _M_bucket_index(const _Key&, _Hash_code_type __c,
820                       std::size_t __n) const
821       { return _M_h2(__c, __n); }
822
823       std::size_t
824       _M_bucket_index(const _Hash_node<_Value, true>* __p,
825                       std::size_t __n) const
826       { return _M_h2(__p->_M_hash_code, __n); }
827
828       bool
829       _M_compare(const _Key& __k, _Hash_code_type __c,
830                  _Hash_node<_Value, true>* __n) const
831       { return __c == __n->_M_hash_code && _M_eq(__k, _M_extract(__n->_M_v)); }
832
833       void
834       _M_store_code(_Hash_node<_Value, true>* __n, _Hash_code_type __c) const
835       { __n->_M_hash_code = __c; }
836
837       void
838       _M_copy_code(_Hash_node<_Value, true>* __to,
839                    const _Hash_node<_Value, true>* __from) const
840       { __to->_M_hash_code = __from->_M_hash_code; }
841
842       void
843       _M_swap(_Hash_code_base& __x)
844       {
845         std::swap(_M_extract, __x._M_extract);
846         std::swap(_M_eq, __x._M_eq);
847         std::swap(_M_h1, __x._M_h1);
848         std::swap(_M_h2, __x._M_h2);
849       }
850
851     protected:
852       _ExtractKey  _M_extract;
853       _Equal       _M_eq;
854       _H1          _M_h1;
855       _H2          _M_h2;
856     };
857
858
859   // Class template _Equality_base.  This is for implementing equality
860   // comparison for unordered containers, per N3068, by John Lakos and
861   // Pablo Halpern.  Algorithmically, we follow closely the reference
862   // implementations therein.
863   template<typename _ExtractKey, bool __unique_keys,
864            typename _Hashtable>
865     struct _Equality_base;
866
867   template<typename _ExtractKey, typename _Hashtable>
868     struct _Equality_base<_ExtractKey, true, _Hashtable>
869     {
870       bool _M_equal(const _Hashtable&) const;
871     };
872
873   template<typename _ExtractKey, typename _Hashtable>
874     bool
875     _Equality_base<_ExtractKey, true, _Hashtable>::
876     _M_equal(const _Hashtable& __other) const
877     {
878       const _Hashtable* __this = static_cast<const _Hashtable*>(this);
879
880       if (__this->size() != __other.size())
881         return false;
882
883       for (auto __itx = __this->begin(); __itx != __this->end(); ++__itx)
884         {
885           const auto __ity = __other.find(_ExtractKey()(*__itx));
886           if (__ity == __other.end() || *__ity != *__itx)
887             return false;
888         }
889       return true;
890     }
891
892   template<typename _ExtractKey, typename _Hashtable>
893     struct _Equality_base<_ExtractKey, false, _Hashtable>
894     {
895       bool _M_equal(const _Hashtable&) const;
896
897     private:
898       template<typename _Uiterator>
899         static bool
900         _S_is_permutation(_Uiterator, _Uiterator, _Uiterator);
901     };
902
903   // See std::is_permutation in N3068.
904   template<typename _ExtractKey, typename _Hashtable>
905     template<typename _Uiterator>
906       bool
907       _Equality_base<_ExtractKey, false, _Hashtable>::
908       _S_is_permutation(_Uiterator __first1, _Uiterator __last1,
909                         _Uiterator __first2)
910       {
911         for (; __first1 != __last1; ++__first1, ++__first2)
912           if (!(*__first1 == *__first2))
913             break;
914
915         if (__first1 == __last1)
916           return true;
917
918         _Uiterator __last2 = __first2;
919         std::advance(__last2, std::distance(__first1, __last1));
920
921         for (_Uiterator __it1 = __first1; __it1 != __last1; ++__it1)
922           {
923             _Uiterator __tmp =  __first1;
924             while (__tmp != __it1 && !(*__tmp == *__it1))
925               ++__tmp;
926
927             // We've seen this one before.
928             if (__tmp != __it1)
929               continue;
930
931             std::ptrdiff_t __n2 = 0;
932             for (__tmp = __first2; __tmp != __last2; ++__tmp)
933               if (*__tmp == *__it1)
934                 ++__n2;
935
936             if (!__n2)
937               return false;
938
939             std::ptrdiff_t __n1 = 0;
940             for (__tmp = __it1; __tmp != __last1; ++__tmp)
941               if (*__tmp == *__it1)
942                 ++__n1;
943
944             if (__n1 != __n2)
945               return false;
946           }
947         return true;
948       }
949
950   template<typename _ExtractKey, typename _Hashtable>
951     bool
952     _Equality_base<_ExtractKey, false, _Hashtable>::
953     _M_equal(const _Hashtable& __other) const
954     {
955       const _Hashtable* __this = static_cast<const _Hashtable*>(this);
956
957       if (__this->size() != __other.size())
958         return false;
959
960       for (auto __itx = __this->begin(); __itx != __this->end();)
961         {
962           const auto __xrange = __this->equal_range(_ExtractKey()(*__itx));
963           const auto __yrange = __other.equal_range(_ExtractKey()(*__itx));
964
965           if (std::distance(__xrange.first, __xrange.second)
966               != std::distance(__yrange.first, __yrange.second))
967             return false;
968
969           if (!_S_is_permutation(__xrange.first,
970                                  __xrange.second,
971                                  __yrange.first))
972             return false;
973
974           __itx = __xrange.second;
975         }
976       return true;
977     }
978
979 _GLIBCXX_END_NAMESPACE_VERSION
980 } // namespace __detail
981 } // namespace std
982
983 #endif // _HASHTABLE_POLICY_H