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

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