1 // Internal policy header for TR1 unordered_set and unordered_map -*- C++ -*- 2 3 // Copyright (C) 2010, 2011 Free Software Foundation, Inc. 4 // 5 // This file is part of the GNU ISO C++ Library. This library is free 6 // software; you can redistribute it and/or modify it under the 7 // terms of the GNU General Public License as published by the 8 // Free Software Foundation; either version 3, or (at your option) 9 // any later version. 10 11 // This library is distributed in the hope that it will be useful, 12 // but WITHOUT ANY WARRANTY; without even the implied warranty of 13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 14 // GNU General Public License for more details. 15 16 // Under Section 7 of GPL version 3, you are granted additional 17 // permissions described in the GCC Runtime Library Exception, version 18 // 3.1, as published by the Free Software Foundation. 19 20 // You should have received a copy of the GNU General Public License and 21 // a copy of the GCC Runtime Library Exception along with this program; 22 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see 23 // <http://www.gnu.org/licenses/>. 24 25 /** @file 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 namespace tr1 34 { 35 namespace __detail 36 { 37 _GLIBCXX_BEGIN_NAMESPACE_VERSION 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 const unsigned long* __p = std::lower_bound(__prime_list, __prime_list 424 + _S_n_primes, __n); 425 _M_next_resize = 426 static_cast<std::size_t>(__builtin_ceil(*__p * _M_max_load_factor)); 427 return *__p; 428 } 429 430 // Return the smallest prime p such that alpha p >= n, where alpha 431 // is the load factor. 432 inline std::size_t 433 _Prime_rehash_policy:: 434 _M_bkt_for_elements(std::size_t __n) const 435 { 436 const float __min_bkts = __n / _M_max_load_factor; 437 const unsigned long* __p = std::lower_bound(__prime_list, __prime_list 438 + _S_n_primes, __min_bkts); 439 _M_next_resize = 440 static_cast<std::size_t>(__builtin_ceil(*__p * _M_max_load_factor)); 441 return *__p; 442 } 443 444 // Finds the smallest prime p such that alpha p > __n_elt + __n_ins. 445 // If p > __n_bkt, return make_pair(true, p); otherwise return 446 // make_pair(false, 0). In principle this isn't very different from 447 // _M_bkt_for_elements. 448 449 // The only tricky part is that we're caching the element count at 450 // which we need to rehash, so we don't have to do a floating-point 451 // multiply for every insertion. 452 453 inline std::pair<bool, std::size_t> 454 _Prime_rehash_policy:: 455 _M_need_rehash(std::size_t __n_bkt, std::size_t __n_elt, 456 std::size_t __n_ins) const 457 { 458 if (__n_elt + __n_ins > _M_next_resize) 459 { 460 float __min_bkts = ((float(__n_ins) + float(__n_elt)) 461 / _M_max_load_factor); 462 if (__min_bkts > __n_bkt) 463 { 464 __min_bkts = std::max(__min_bkts, _M_growth_factor * __n_bkt); 465 const unsigned long* __p = 466 std::lower_bound(__prime_list, __prime_list + _S_n_primes, 467 __min_bkts); 468 _M_next_resize = static_cast<std::size_t> 469 (__builtin_ceil(*__p * _M_max_load_factor)); 470 return std::make_pair(true, *__p); 471 } 472 else 473 { 474 _M_next_resize = static_cast<std::size_t> 475 (__builtin_ceil(__n_bkt * _M_max_load_factor)); 476 return std::make_pair(false, 0); 477 } 478 } 479 else 480 return std::make_pair(false, 0); 481 } 482 483 // Base classes for std::tr1::_Hashtable. We define these base 484 // classes because in some cases we want to do different things 485 // depending on the value of a policy class. In some cases the 486 // policy class affects which member functions and nested typedefs 487 // are defined; we handle that by specializing base class templates. 488 // Several of the base class templates need to access other members 489 // of class template _Hashtable, so we use the "curiously recurring 490 // template pattern" for them. 491 492 // class template _Map_base. If the hashtable has a value type of the 493 // form pair<T1, T2> and a key extraction policy that returns the 494 // first part of the pair, the hashtable gets a mapped_type typedef. 495 // If it satisfies those criteria and also has unique keys, then it 496 // also gets an operator[]. 497 template<typename _Key, typename _Value, typename _Ex, bool __unique, 498 typename _Hashtable> 499 struct _Map_base { }; 500 501 template<typename _Key, typename _Pair, typename _Hashtable> 502 struct _Map_base<_Key, _Pair, std::_Select1st<_Pair>, false, _Hashtable> 503 { 504 typedef typename _Pair::second_type mapped_type; 505 }; 506 507 template<typename _Key, typename _Pair, typename _Hashtable> 508 struct _Map_base<_Key, _Pair, std::_Select1st<_Pair>, true, _Hashtable> 509 { 510 typedef typename _Pair::second_type mapped_type; 511 512 mapped_type& 513 operator[](const _Key& __k); 514 }; 515 516 template<typename _Key, typename _Pair, typename _Hashtable> 517 typename _Map_base<_Key, _Pair, std::_Select1st<_Pair>, 518 true, _Hashtable>::mapped_type& 519 _Map_base<_Key, _Pair, std::_Select1st<_Pair>, true, _Hashtable>:: 520 operator[](const _Key& __k) 521 { 522 _Hashtable* __h = static_cast<_Hashtable*>(this); 523 typename _Hashtable::_Hash_code_type __code = __h->_M_hash_code(__k); 524 std::size_t __n = __h->_M_bucket_index(__k, __code, 525 __h->_M_bucket_count); 526 527 typename _Hashtable::_Node* __p = 528 __h->_M_find_node(__h->_M_buckets[__n], __k, __code); 529 if (!__p) 530 return __h->_M_insert_bucket(std::make_pair(__k, mapped_type()), 531 __n, __code)->second; 532 return (__p->_M_v).second; 533 } 534 535 // class template _Rehash_base. Give hashtable the max_load_factor 536 // functions iff the rehash policy is _Prime_rehash_policy. 537 template<typename _RehashPolicy, typename _Hashtable> 538 struct _Rehash_base { }; 539 540 template<typename _Hashtable> 541 struct _Rehash_base<_Prime_rehash_policy, _Hashtable> 542 { 543 float 544 max_load_factor() const 545 { 546 const _Hashtable* __this = static_cast<const _Hashtable*>(this); 547 return __this->__rehash_policy().max_load_factor(); 548 } 549 550 void 551 max_load_factor(float __z) 552 { 553 _Hashtable* __this = static_cast<_Hashtable*>(this); 554 __this->__rehash_policy(_Prime_rehash_policy(__z)); 555 } 556 }; 557 558 // Class template _Hash_code_base. Encapsulates two policy issues that 559 // aren't quite orthogonal. 560 // (1) the difference between using a ranged hash function and using 561 // the combination of a hash function and a range-hashing function. 562 // In the former case we don't have such things as hash codes, so 563 // we have a dummy type as placeholder. 564 // (2) Whether or not we cache hash codes. Caching hash codes is 565 // meaningless if we have a ranged hash function. 566 // We also put the key extraction and equality comparison function 567 // objects here, for convenience. 568 569 // Primary template: unused except as a hook for specializations. 570 template<typename _Key, typename _Value, 571 typename _ExtractKey, typename _Equal, 572 typename _H1, typename _H2, typename _Hash, 573 bool __cache_hash_code> 574 struct _Hash_code_base; 575 576 // Specialization: ranged hash function, no caching hash codes. H1 577 // and H2 are provided but ignored. We define a dummy hash code type. 578 template<typename _Key, typename _Value, 579 typename _ExtractKey, typename _Equal, 580 typename _H1, typename _H2, typename _Hash> 581 struct _Hash_code_base<_Key, _Value, _ExtractKey, _Equal, _H1, _H2, 582 _Hash, false> 583 { 584 protected: 585 _Hash_code_base(const _ExtractKey& __ex, const _Equal& __eq, 586 const _H1&, const _H2&, const _Hash& __h) 587 : _M_extract(__ex), _M_eq(__eq), _M_ranged_hash(__h) { } 588 589 typedef void* _Hash_code_type; 590 591 _Hash_code_type 592 _M_hash_code(const _Key& __key) const 593 { return 0; } 594 595 std::size_t 596 _M_bucket_index(const _Key& __k, _Hash_code_type, 597 std::size_t __n) const 598 { return _M_ranged_hash(__k, __n); } 599 600 std::size_t 601 _M_bucket_index(const _Hash_node<_Value, false>* __p, 602 std::size_t __n) const 603 { return _M_ranged_hash(_M_extract(__p->_M_v), __n); } 604 605 bool 606 _M_compare(const _Key& __k, _Hash_code_type, 607 _Hash_node<_Value, false>* __n) const 608 { return _M_eq(__k, _M_extract(__n->_M_v)); } 609 610 void 611 _M_store_code(_Hash_node<_Value, false>*, _Hash_code_type) const 612 { } 613 614 void 615 _M_copy_code(_Hash_node<_Value, false>*, 616 const _Hash_node<_Value, false>*) const 617 { } 618 619 void 620 _M_swap(_Hash_code_base& __x) 621 { 622 std::swap(_M_extract, __x._M_extract); 623 std::swap(_M_eq, __x._M_eq); 624 std::swap(_M_ranged_hash, __x._M_ranged_hash); 625 } 626 627 protected: 628 _ExtractKey _M_extract; 629 _Equal _M_eq; 630 _Hash _M_ranged_hash; 631 }; 632 633 634 // No specialization for ranged hash function while caching hash codes. 635 // That combination is meaningless, and trying to do it is an error. 636 637 638 // Specialization: ranged hash function, cache hash codes. This 639 // combination is meaningless, so we provide only a declaration 640 // and no definition. 641 template<typename _Key, typename _Value, 642 typename _ExtractKey, typename _Equal, 643 typename _H1, typename _H2, typename _Hash> 644 struct _Hash_code_base<_Key, _Value, _ExtractKey, _Equal, _H1, _H2, 645 _Hash, true>; 646 647 // Specialization: hash function and range-hashing function, no 648 // caching of hash codes. H is provided but ignored. Provides 649 // typedef and accessor required by TR1. 650 template<typename _Key, typename _Value, 651 typename _ExtractKey, typename _Equal, 652 typename _H1, typename _H2> 653 struct _Hash_code_base<_Key, _Value, _ExtractKey, _Equal, _H1, _H2, 654 _Default_ranged_hash, false> 655 { 656 typedef _H1 hasher; 657 658 hasher 659 hash_function() const 660 { return _M_h1; } 661 662 protected: 663 _Hash_code_base(const _ExtractKey& __ex, const _Equal& __eq, 664 const _H1& __h1, const _H2& __h2, 665 const _Default_ranged_hash&) 666 : _M_extract(__ex), _M_eq(__eq), _M_h1(__h1), _M_h2(__h2) { } 667 668 typedef std::size_t _Hash_code_type; 669 670 _Hash_code_type 671 _M_hash_code(const _Key& __k) const 672 { return _M_h1(__k); } 673 674 std::size_t 675 _M_bucket_index(const _Key&, _Hash_code_type __c, 676 std::size_t __n) const 677 { return _M_h2(__c, __n); } 678 679 std::size_t 680 _M_bucket_index(const _Hash_node<_Value, false>* __p, 681 std::size_t __n) const 682 { return _M_h2(_M_h1(_M_extract(__p->_M_v)), __n); } 683 684 bool 685 _M_compare(const _Key& __k, _Hash_code_type, 686 _Hash_node<_Value, false>* __n) const 687 { return _M_eq(__k, _M_extract(__n->_M_v)); } 688 689 void 690 _M_store_code(_Hash_node<_Value, false>*, _Hash_code_type) const 691 { } 692 693 void 694 _M_copy_code(_Hash_node<_Value, false>*, 695 const _Hash_node<_Value, false>*) const 696 { } 697 698 void 699 _M_swap(_Hash_code_base& __x) 700 { 701 std::swap(_M_extract, __x._M_extract); 702 std::swap(_M_eq, __x._M_eq); 703 std::swap(_M_h1, __x._M_h1); 704 std::swap(_M_h2, __x._M_h2); 705 } 706 707 protected: 708 _ExtractKey _M_extract; 709 _Equal _M_eq; 710 _H1 _M_h1; 711 _H2 _M_h2; 712 }; 713 714 // Specialization: hash function and range-hashing function, 715 // caching hash codes. H is provided but ignored. Provides 716 // typedef and accessor required by TR1. 717 template<typename _Key, typename _Value, 718 typename _ExtractKey, typename _Equal, 719 typename _H1, typename _H2> 720 struct _Hash_code_base<_Key, _Value, _ExtractKey, _Equal, _H1, _H2, 721 _Default_ranged_hash, true> 722 { 723 typedef _H1 hasher; 724 725 hasher 726 hash_function() const 727 { return _M_h1; } 728 729 protected: 730 _Hash_code_base(const _ExtractKey& __ex, const _Equal& __eq, 731 const _H1& __h1, const _H2& __h2, 732 const _Default_ranged_hash&) 733 : _M_extract(__ex), _M_eq(__eq), _M_h1(__h1), _M_h2(__h2) { } 734 735 typedef std::size_t _Hash_code_type; 736 737 _Hash_code_type 738 _M_hash_code(const _Key& __k) const 739 { return _M_h1(__k); } 740 741 std::size_t 742 _M_bucket_index(const _Key&, _Hash_code_type __c, 743 std::size_t __n) const 744 { return _M_h2(__c, __n); } 745 746 std::size_t 747 _M_bucket_index(const _Hash_node<_Value, true>* __p, 748 std::size_t __n) const 749 { return _M_h2(__p->_M_hash_code, __n); } 750 751 bool 752 _M_compare(const _Key& __k, _Hash_code_type __c, 753 _Hash_node<_Value, true>* __n) const 754 { return __c == __n->_M_hash_code && _M_eq(__k, _M_extract(__n->_M_v)); } 755 756 void 757 _M_store_code(_Hash_node<_Value, true>* __n, _Hash_code_type __c) const 758 { __n->_M_hash_code = __c; } 759 760 void 761 _M_copy_code(_Hash_node<_Value, true>* __to, 762 const _Hash_node<_Value, true>* __from) const 763 { __to->_M_hash_code = __from->_M_hash_code; } 764 765 void 766 _M_swap(_Hash_code_base& __x) 767 { 768 std::swap(_M_extract, __x._M_extract); 769 std::swap(_M_eq, __x._M_eq); 770 std::swap(_M_h1, __x._M_h1); 771 std::swap(_M_h2, __x._M_h2); 772 } 773 774 protected: 775 _ExtractKey _M_extract; 776 _Equal _M_eq; 777 _H1 _M_h1; 778 _H2 _M_h2; 779 }; 780 _GLIBCXX_END_NAMESPACE_VERSION 781 } // namespace __detail 782 } 783 } 784