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

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