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