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

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