libstdc++-v3/include/bits/hashtable_policy.h

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