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