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

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