OSDN Git Service

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