1// Internal policy header for TR1 unordered_set and unordered_map -*- C++ -*- 2 3// Copyright (C) 2005, 2006 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 2, 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// You should have received a copy of the GNU General Public License along 17// with this library; see the file COPYING. If not, write to the Free 18// Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, 19// USA. 20 21// As a special exception, you may use this file as part of a free software 22// library without restriction. Specifically, if other files instantiate 23// templates or use macros or inline functions from this file, or you compile 24// this file and link it with other files to produce an executable, this 25// file does not by itself cause the resulting executable to be covered by 26// the GNU General Public License. This exception does not however 27// invalidate any other reasons why the executable file might be covered by 28// the GNU General Public License. 29 30/** @file tr1/hashtable_policy.h 31 * This is a TR1 C++ Library header. 32 */ 33 34#ifndef _TR1_HASHTABLE_POLICY_H 35#define _TR1_HASHTABLE_POLICY_H 1 36 37#include <functional> // _Identity, _Select1st 38#include <tr1/utility> 39#include <ext/type_traits.h> 40 41namespace std 42{ 43_GLIBCXX_BEGIN_NAMESPACE(tr1) 44namespace __detail 45{ 46 // Helper function: return distance(first, last) for forward 47 // iterators, or 0 for input iterators. 48 template<class _Iterator> 49 inline typename std::iterator_traits<_Iterator>::difference_type 50 __distance_fw(_Iterator __first, _Iterator __last, 51 std::input_iterator_tag) 52 { return 0; } 53 54 template<class _Iterator> 55 inline typename std::iterator_traits<_Iterator>::difference_type 56 __distance_fw(_Iterator __first, _Iterator __last, 57 std::forward_iterator_tag) 58 { return std::distance(__first, __last); } 59 60 template<class _Iterator> 61 inline typename std::iterator_traits<_Iterator>::difference_type 62 __distance_fw(_Iterator __first, _Iterator __last) 63 { 64 typedef typename std::iterator_traits<_Iterator>::iterator_category _Tag; 65 return __distance_fw(__first, __last, _Tag()); 66 } 67 68 // XXX This is a hack. _Prime_rehash_policy's member functions, and 69 // certainly the list of primes, should be defined in a .cc file. 70 // We're temporarily putting them in a header because we don't have a 71 // place to put TR1 .cc files yet. There's no good reason for any of 72 // _Prime_rehash_policy's member functions to be inline, and there's 73 // certainly no good reason for _Primes<> to exist at all. 74 struct _LessThan 75 { 76 template<typename _Tp, typename _Up> 77 bool 78 operator()(_Tp __x, _Up __y) 79 { return __x < __y; } 80 }; 81 82 template<int __ulongsize = sizeof(unsigned long)> 83 struct _Primes 84 { 85 static const int __n_primes = __ulongsize != 8 ? 256 : 256 + 48; 86 static const unsigned long __primes[256 + 48 + 1]; 87 }; 88 89 template<int __ulongsize> 90 const int _Primes<__ulongsize>::__n_primes; 91 92 template<int __ulongsize> 93 const unsigned long _Primes<__ulongsize>::__primes[256 + 48 + 1] = 94 { 95 2ul, 3ul, 5ul, 7ul, 11ul, 13ul, 17ul, 19ul, 23ul, 29ul, 31ul, 96 37ul, 41ul, 43ul, 47ul, 53ul, 59ul, 61ul, 67ul, 71ul, 73ul, 79ul, 97 83ul, 89ul, 97ul, 103ul, 109ul, 113ul, 127ul, 137ul, 139ul, 149ul, 98 157ul, 167ul, 179ul, 193ul, 199ul, 211ul, 227ul, 241ul, 257ul, 99 277ul, 293ul, 313ul, 337ul, 359ul, 383ul, 409ul, 439ul, 467ul, 100 503ul, 541ul, 577ul, 619ul, 661ul, 709ul, 761ul, 823ul, 887ul, 101 953ul, 1031ul, 1109ul, 1193ul, 1289ul, 1381ul, 1493ul, 1613ul, 102 1741ul, 1879ul, 2029ul, 2179ul, 2357ul, 2549ul, 2753ul, 2971ul, 103 3209ul, 3469ul, 3739ul, 4027ul, 4349ul, 4703ul, 5087ul, 5503ul, 104 5953ul, 6427ul, 6949ul, 7517ul, 8123ul, 8783ul, 9497ul, 10273ul, 105 11113ul, 12011ul, 12983ul, 14033ul, 15173ul, 16411ul, 17749ul, 106 19183ul, 20753ul, 22447ul, 24281ul, 26267ul, 28411ul, 30727ul, 107 33223ul, 35933ul, 38873ul, 42043ul, 45481ul, 49201ul, 53201ul, 108 57557ul, 62233ul, 67307ul, 72817ul, 78779ul, 85229ul, 92203ul, 109 99733ul, 107897ul, 116731ul, 126271ul, 136607ul, 147793ul, 110 159871ul, 172933ul, 187091ul, 202409ul, 218971ul, 236897ul, 111 256279ul, 277261ul, 299951ul, 324503ul, 351061ul, 379787ul, 112 410857ul, 444487ul, 480881ul, 520241ul, 562841ul, 608903ul, 113 658753ul, 712697ul, 771049ul, 834181ul, 902483ul, 976369ul, 114 1056323ul, 1142821ul, 1236397ul, 1337629ul, 1447153ul, 1565659ul, 115 1693859ul, 1832561ul, 1982627ul, 2144977ul, 2320627ul, 2510653ul, 116 2716249ul, 2938679ul, 3179303ul, 3439651ul, 3721303ul, 4026031ul, 117 4355707ul, 4712381ul, 5098259ul, 5515729ul, 5967347ul, 6456007ul, 118 6984629ul, 7556579ul, 8175383ul, 8844859ul, 9569143ul, 10352717ul, 119 11200489ul, 12117689ul, 13109983ul, 14183539ul, 15345007ul, 120 16601593ul, 17961079ul, 19431899ul, 21023161ul, 22744717ul, 121 24607243ul, 26622317ul, 28802401ul, 31160981ul, 33712729ul, 122 36473443ul, 39460231ul, 42691603ul, 46187573ul, 49969847ul, 123 54061849ul, 58488943ul, 63278561ul, 68460391ul, 74066549ul, 124 80131819ul, 86693767ul, 93793069ul, 101473717ul, 109783337ul, 125 118773397ul, 128499677ul, 139022417ul, 150406843ul, 162723577ul, 126 176048909ul, 190465427ul, 206062531ul, 222936881ul, 241193053ul, 127 260944219ul, 282312799ul, 305431229ul, 330442829ul, 357502601ul, 128 386778277ul, 418451333ul, 452718089ul, 489790921ul, 529899637ul, 129 573292817ul, 620239453ul, 671030513ul, 725980837ul, 785430967ul, 130 849749479ul, 919334987ul, 994618837ul, 1076067617ul, 1164186217ul, 131 1259520799ul, 1362662261ul, 1474249943ul, 1594975441ul, 132 1725587117ul, 1866894511ul, 2019773507ul, 2185171673ul, 133 2364114217ul, 2557710269ul, 2767159799ul, 2993761039ul, 134 3238918481ul, 3504151727ul, 3791104843ul, 4101556399ul, 135 4294967291ul, 136 // Sentinel, so we don't have to test the result of lower_bound, 137 // or, on 64-bit machines, rest of the table. 138 __ulongsize != 8 ? 4294967291ul : (unsigned long)6442450933ull, 139 (unsigned long)8589934583ull, 140 (unsigned long)12884901857ull, (unsigned long)17179869143ull, 141 (unsigned long)25769803693ull, (unsigned long)34359738337ull, 142 (unsigned long)51539607367ull, (unsigned long)68719476731ull, 143 (unsigned long)103079215087ull, (unsigned long)137438953447ull, 144 (unsigned long)206158430123ull, (unsigned long)274877906899ull, 145 (unsigned long)412316860387ull, (unsigned long)549755813881ull, 146 (unsigned long)824633720731ull, (unsigned long)1099511627689ull, 147 (unsigned long)1649267441579ull, (unsigned long)2199023255531ull, 148 (unsigned long)3298534883309ull, (unsigned long)4398046511093ull, 149 (unsigned long)6597069766607ull, (unsigned long)8796093022151ull, 150 (unsigned long)13194139533241ull, (unsigned long)17592186044399ull, 151 (unsigned long)26388279066581ull, (unsigned long)35184372088777ull, 152 (unsigned long)52776558133177ull, (unsigned long)70368744177643ull, 153 (unsigned long)105553116266399ull, (unsigned long)140737488355213ull, 154 (unsigned long)211106232532861ull, (unsigned long)281474976710597ull, 155 (unsigned long)562949953421231ull, (unsigned long)1125899906842597ull, 156 (unsigned long)2251799813685119ull, (unsigned long)4503599627370449ull, 157 (unsigned long)9007199254740881ull, (unsigned long)18014398509481951ull, 158 (unsigned long)36028797018963913ull, (unsigned long)72057594037927931ull, 159 (unsigned long)144115188075855859ull, 160 (unsigned long)288230376151711717ull, 161 (unsigned long)576460752303423433ull, 162 (unsigned long)1152921504606846883ull, 163 (unsigned long)2305843009213693951ull, 164 (unsigned long)4611686018427387847ull, 165 (unsigned long)9223372036854775783ull, 166 (unsigned long)18446744073709551557ull, 167 (unsigned long)18446744073709551557ull 168 }; 169 170 // Auxiliary types used for all instantiations of _Hashtable: nodes 171 // and iterators. 172 173 // Nodes, used to wrap elements stored in the hash table. A policy 174 // template parameter of class template _Hashtable controls whether 175 // nodes also store a hash code. In some cases (e.g. strings) this 176 // may be a performance win. 177 template<typename _Value, bool __cache_hash_code> 178 struct _Hash_node; 179 180 template<typename _Value> 181 struct _Hash_node<_Value, true> 182 { 183 _Value _M_v; 184 std::size_t _M_hash_code; 185 _Hash_node* _M_next; 186 }; 187 188 template<typename _Value> 189 struct _Hash_node<_Value, false> 190 { 191 _Value _M_v; 192 _Hash_node* _M_next; 193 }; 194 195 // Local iterators, used to iterate within a bucket but not between 196 // buckets. 197 template<typename _Value, bool __cache> 198 struct _Node_iterator_base 199 { 200 _Node_iterator_base(_Hash_node<_Value, __cache>* __p) 201 : _M_cur(__p) { } 202 203 void 204 _M_incr() 205 { _M_cur = _M_cur->_M_next; } 206 207 _Hash_node<_Value, __cache>* _M_cur; 208 }; 209 210 template<typename _Value, bool __cache> 211 inline bool 212 operator==(const _Node_iterator_base<_Value, __cache>& __x, 213 const _Node_iterator_base<_Value, __cache>& __y) 214 { return __x._M_cur == __y._M_cur; } 215 216 template<typename _Value, bool __cache> 217 inline bool 218 operator!=(const _Node_iterator_base<_Value, __cache>& __x, 219 const _Node_iterator_base<_Value, __cache>& __y) 220 { return __x._M_cur != __y._M_cur; } 221 222 template<typename _Value, bool __constant_iterators, bool __cache> 223 struct _Node_iterator 224 : public _Node_iterator_base<_Value, __cache> 225 { 226 typedef _Value value_type; 227 typedef typename 228 __gnu_cxx::__conditional_type<__constant_iterators, 229 const _Value*, _Value*>::__type 230 pointer; 231 typedef typename 232 __gnu_cxx::__conditional_type<__constant_iterators, 233 const _Value&, _Value&>::__type 234 reference; 235 typedef std::ptrdiff_t difference_type; 236 typedef std::forward_iterator_tag iterator_category; 237 238 _Node_iterator() 239 : _Node_iterator_base<_Value, __cache>(0) { } 240 241 explicit 242 _Node_iterator(_Hash_node<_Value, __cache>* __p) 243 : _Node_iterator_base<_Value, __cache>(__p) { } 244 245 reference 246 operator*() const 247 { return this->_M_cur->_M_v; } 248 249 pointer 250 operator->() const 251 { return &this->_M_cur->_M_v; } 252 253 _Node_iterator& 254 operator++() 255 { 256 this->_M_incr(); 257 return *this; 258 } 259 260 _Node_iterator 261 operator++(int) 262 { 263 _Node_iterator __tmp(*this); 264 this->_M_incr(); 265 return __tmp; 266 } 267 }; 268 269 template<typename _Value, bool __constant_iterators, bool __cache> 270 struct _Node_const_iterator 271 : public _Node_iterator_base<_Value, __cache> 272 { 273 typedef _Value value_type; 274 typedef const _Value* pointer; 275 typedef const _Value& reference; 276 typedef std::ptrdiff_t difference_type; 277 typedef std::forward_iterator_tag iterator_category; 278 279 _Node_const_iterator() 280 : _Node_iterator_base<_Value, __cache>(0) { } 281 282 explicit 283 _Node_const_iterator(_Hash_node<_Value, __cache>* __p) 284 : _Node_iterator_base<_Value, __cache>(__p) { } 285 286 _Node_const_iterator(const _Node_iterator<_Value, __constant_iterators, 287 __cache>& __x) 288 : _Node_iterator_base<_Value, __cache>(__x._M_cur) { } 289 290 reference 291 operator*() const 292 { return this->_M_cur->_M_v; } 293 294 pointer 295 operator->() const 296 { return &this->_M_cur->_M_v; } 297 298 _Node_const_iterator& 299 operator++() 300 { 301 this->_M_incr(); 302 return *this; 303 } 304 305 _Node_const_iterator 306 operator++(int) 307 { 308 _Node_const_iterator __tmp(*this); 309 this->_M_incr(); 310 return __tmp; 311 } 312 }; 313 314 template<typename _Value, bool __cache> 315 struct _Hashtable_iterator_base 316 { 317 _Hashtable_iterator_base(_Hash_node<_Value, __cache>* __node, 318 _Hash_node<_Value, __cache>** __bucket) 319 : _M_cur_node(__node), _M_cur_bucket(__bucket) { } 320 321 void 322 _M_incr() 323 { 324 _M_cur_node = _M_cur_node->_M_next; 325 if (!_M_cur_node) 326 _M_incr_bucket(); 327 } 328 329 void 330 _M_incr_bucket(); 331 332 _Hash_node<_Value, __cache>* _M_cur_node; 333 _Hash_node<_Value, __cache>** _M_cur_bucket; 334 }; 335 336 // Global iterators, used for arbitrary iteration within a hash 337 // table. Larger and more expensive than local iterators. 338 template<typename _Value, bool __cache> 339 void 340 _Hashtable_iterator_base<_Value, __cache>:: 341 _M_incr_bucket() 342 { 343 ++_M_cur_bucket; 344 345 // This loop requires the bucket array to have a non-null sentinel. 346 while (!*_M_cur_bucket) 347 ++_M_cur_bucket; 348 _M_cur_node = *_M_cur_bucket; 349 } 350 351 template<typename _Value, bool __cache> 352 inline bool 353 operator==(const _Hashtable_iterator_base<_Value, __cache>& __x, 354 const _Hashtable_iterator_base<_Value, __cache>& __y) 355 { return __x._M_cur_node == __y._M_cur_node; } 356 357 template<typename _Value, bool __cache> 358 inline bool 359 operator!=(const _Hashtable_iterator_base<_Value, __cache>& __x, 360 const _Hashtable_iterator_base<_Value, __cache>& __y) 361 { return __x._M_cur_node != __y._M_cur_node; } 362 363 template<typename _Value, bool __constant_iterators, bool __cache> 364 struct _Hashtable_iterator 365 : public _Hashtable_iterator_base<_Value, __cache> 366 { 367 typedef _Value value_type; 368 typedef typename 369 __gnu_cxx::__conditional_type<__constant_iterators, 370 const _Value*, _Value*>::__type 371 pointer; 372 typedef typename 373 __gnu_cxx::__conditional_type<__constant_iterators, 374 const _Value&, _Value&>::__type 375 reference; 376 typedef std::ptrdiff_t difference_type; 377 typedef std::forward_iterator_tag iterator_category; 378 379 _Hashtable_iterator() 380 : _Hashtable_iterator_base<_Value, __cache>(0, 0) { } 381 382 _Hashtable_iterator(_Hash_node<_Value, __cache>* __p, 383 _Hash_node<_Value, __cache>** __b) 384 : _Hashtable_iterator_base<_Value, __cache>(__p, __b) { } 385 386 explicit 387 _Hashtable_iterator(_Hash_node<_Value, __cache>** __b) 388 : _Hashtable_iterator_base<_Value, __cache>(*__b, __b) { } 389 390 reference 391 operator*() const 392 { return this->_M_cur_node->_M_v; } 393 394 pointer 395 operator->() const 396 { return &this->_M_cur_node->_M_v; } 397 398 _Hashtable_iterator& 399 operator++() 400 { 401 this->_M_incr(); 402 return *this; 403 } 404 405 _Hashtable_iterator 406 operator++(int) 407 { 408 _Hashtable_iterator __tmp(*this); 409 this->_M_incr(); 410 return __tmp; 411 } 412 }; 413 414 template<typename _Value, bool __constant_iterators, bool __cache> 415 struct _Hashtable_const_iterator 416 : public _Hashtable_iterator_base<_Value, __cache> 417 { 418 typedef _Value value_type; 419 typedef const _Value* pointer; 420 typedef const _Value& reference; 421 typedef std::ptrdiff_t difference_type; 422 typedef std::forward_iterator_tag iterator_category; 423 424 _Hashtable_const_iterator() 425 : _Hashtable_iterator_base<_Value, __cache>(0, 0) { } 426 427 _Hashtable_const_iterator(_Hash_node<_Value, __cache>* __p, 428 _Hash_node<_Value, __cache>** __b) 429 : _Hashtable_iterator_base<_Value, __cache>(__p, __b) { } 430 431 explicit 432 _Hashtable_const_iterator(_Hash_node<_Value, __cache>** __b) 433 : _Hashtable_iterator_base<_Value, __cache>(*__b, __b) { } 434 435 _Hashtable_const_iterator(const _Hashtable_iterator<_Value, 436 __constant_iterators, __cache>& __x) 437 : _Hashtable_iterator_base<_Value, __cache>(__x._M_cur_node, 438 __x._M_cur_bucket) { } 439 440 reference 441 operator*() const 442 { return this->_M_cur_node->_M_v; } 443 444 pointer 445 operator->() const 446 { return &this->_M_cur_node->_M_v; } 447 448 _Hashtable_const_iterator& 449 operator++() 450 { 451 this->_M_incr(); 452 return *this; 453 } 454 455 _Hashtable_const_iterator 456 operator++(int) 457 { 458 _Hashtable_const_iterator __tmp(*this); 459 this->_M_incr(); 460 return __tmp; 461 } 462 }; 463 464 465 // Many of class template _Hashtable's template parameters are policy 466 // classes. These are defaults for the policies. 467 468 // Default range hashing function: use division to fold a large number 469 // into the range [0, N). 470 struct _Mod_range_hashing 471 { 472 typedef std::size_t first_argument_type; 473 typedef std::size_t second_argument_type; 474 typedef std::size_t result_type; 475 476 result_type 477 operator()(first_argument_type __num, second_argument_type __den) const 478 { return __num % __den; } 479 }; 480 481 // Default ranged hash function H. In principle it should be a 482 // function object composed from objects of type H1 and H2 such that 483 // h(k, N) = h2(h1(k), N), but that would mean making extra copies of 484 // h1 and h2. So instead we'll just use a tag to tell class template 485 // hashtable to do that composition. 486 struct _Default_ranged_hash { }; 487 488 // Default value for rehash policy. Bucket size is (usually) the 489 // smallest prime that keeps the load factor small enough. 490 struct _Prime_rehash_policy 491 { 492 _Prime_rehash_policy(float __z = 1.0); 493 494 float 495 max_load_factor() const; 496 497 // Return a bucket size no smaller than n. 498 std::size_t 499 _M_next_bkt(std::size_t __n) const; 500 501 // Return a bucket count appropriate for n elements 502 std::size_t 503 _M_bkt_for_elements(std::size_t __n) const; 504 505 // __n_bkt is current bucket count, __n_elt is current element count, 506 // and __n_ins is number of elements to be inserted. Do we need to 507 // increase bucket count? If so, return make_pair(true, n), where n 508 // is the new bucket count. If not, return make_pair(false, 0). 509 std::pair<bool, std::size_t> 510 _M_need_rehash(std::size_t __n_bkt, std::size_t __n_elt, 511 std::size_t __n_ins) const; 512 513 float _M_max_load_factor; 514 float _M_growth_factor; 515 mutable std::size_t _M_next_resize; 516 }; 517 518 inline 519 _Prime_rehash_policy:: 520 _Prime_rehash_policy(float __z) 521 : _M_max_load_factor(__z), _M_growth_factor(2.f), _M_next_resize(0) 522 { } 523 524 inline float 525 _Prime_rehash_policy:: 526 max_load_factor() const 527 { return _M_max_load_factor; } 528 529 // Return a prime no smaller than n. 530 inline std::size_t 531 _Prime_rehash_policy:: 532 _M_next_bkt(std::size_t __n) const 533 { 534 const unsigned long* const __last = (_Primes<>::__primes 535 + _Primes<>::__n_primes); 536 const unsigned long* __p = std::lower_bound(_Primes<>::__primes, __last, 537 __n); 538 _M_next_resize = static_cast<std::size_t>(std::ceil(*__p 539 * _M_max_load_factor)); 540 return *__p; 541 } 542 543 // Return the smallest prime p such that alpha p >= n, where alpha 544 // is the load factor. 545 inline std::size_t 546 _Prime_rehash_policy:: 547 _M_bkt_for_elements(std::size_t __n) const 548 { 549 const unsigned long* const __last = (_Primes<>::__primes 550 + _Primes<>::__n_primes); 551 const float __min_bkts = __n / _M_max_load_factor; 552 const unsigned long* __p = std::lower_bound(_Primes<>::__primes, __last, 553 __min_bkts, _LessThan()); 554 _M_next_resize = static_cast<std::size_t>(std::ceil(*__p 555 * _M_max_load_factor)); 556 return *__p; 557 } 558 559 // Finds the smallest prime p such that alpha p > __n_elt + __n_ins. 560 // If p > __n_bkt, return make_pair(true, p); otherwise return 561 // make_pair(false, 0). In principle this isn't very different from 562 // _M_bkt_for_elements. 563 564 // The only tricky part is that we're caching the element count at 565 // which we need to rehash, so we don't have to do a floating-point 566 // multiply for every insertion. 567 568 inline std::pair<bool, std::size_t> 569 _Prime_rehash_policy:: 570 _M_need_rehash(std::size_t __n_bkt, std::size_t __n_elt, 571 std::size_t __n_ins) const 572 { 573 if (__n_elt + __n_ins > _M_next_resize) 574 { 575 float __min_bkts = ((float(__n_ins) + float(__n_elt)) 576 / _M_max_load_factor); 577 if (__min_bkts > __n_bkt) 578 { 579 __min_bkts = std::max(__min_bkts, _M_growth_factor * __n_bkt); 580 const unsigned long* const __last = (_Primes<>::__primes 581 + _Primes<>::__n_primes); 582 const unsigned long* __p = std::lower_bound(_Primes<>::__primes, 583 __last, __min_bkts, 584 _LessThan()); 585 _M_next_resize = 586 static_cast<std::size_t>(std::ceil(*__p * _M_max_load_factor)); 587 return std::make_pair(true, *__p); 588 } 589 else 590 { 591 _M_next_resize = 592 static_cast<std::size_t>(std::ceil(__n_bkt 593 * _M_max_load_factor)); 594 return std::make_pair(false, 0); 595 } 596 } 597 else 598 return std::make_pair(false, 0); 599 } 600 601 // Base classes for std::tr1::_Hashtable. We define these base 602 // classes because in some cases we want to do different things 603 // depending on the value of a policy class. In some cases the 604 // policy class affects which member functions and nested typedefs 605 // are defined; we handle that by specializing base class templates. 606 // Several of the base class templates need to access other members 607 // of class template _Hashtable, so we use the "curiously recurring 608 // template pattern" for them. 609 610 // class template _Map_base. If the hashtable has a value type of the 611 // form pair<T1, T2> and a key extraction policy that returns the 612 // first part of the pair, the hashtable gets a mapped_type typedef. 613 // If it satisfies those criteria and also has unique keys, then it 614 // also gets an operator[]. 615 template<typename _Key, typename _Value, typename _Ex, bool __unique, 616 typename _Hashtable> 617 struct _Map_base { }; 618 619 template<typename _Key, typename _Pair, typename _Hashtable> 620 struct _Map_base<_Key, _Pair, std::_Select1st<_Pair>, false, _Hashtable> 621 { 622 typedef typename _Pair::second_type mapped_type; 623 }; 624 625 template<typename _Key, typename _Pair, typename _Hashtable> 626 struct _Map_base<_Key, _Pair, std::_Select1st<_Pair>, true, _Hashtable> 627 { 628 typedef typename _Pair::second_type mapped_type; 629 630 mapped_type& 631 operator[](const _Key& __k); 632 }; 633 634 template<typename _Key, typename _Pair, typename _Hashtable> 635 typename _Map_base<_Key, _Pair, std::_Select1st<_Pair>, 636 true, _Hashtable>::mapped_type& 637 _Map_base<_Key, _Pair, std::_Select1st<_Pair>, true, _Hashtable>:: 638 operator[](const _Key& __k) 639 { 640 _Hashtable* __h = static_cast<_Hashtable*>(this); 641 typename _Hashtable::_Hash_code_type __code = __h->_M_hash_code(__k); 642 std::size_t __n = __h->_M_bucket_index(__k, __code, 643 __h->_M_bucket_count); 644 645 typename _Hashtable::_Node* __p = 646 __h->_M_find_node(__h->_M_buckets[__n], __k, __code); 647 if (!__p) 648 return __h->_M_insert_bucket(std::make_pair(__k, mapped_type()), 649 __n, __code)->second; 650 return (__p->_M_v).second; 651 } 652 653 // class template _Rehash_base. Give hashtable the max_load_factor 654 // functions iff the rehash policy is _Prime_rehash_policy. 655 template<typename _RehashPolicy, typename _Hashtable> 656 struct _Rehash_base { }; 657 658 template<typename _Hashtable> 659 struct _Rehash_base<_Prime_rehash_policy, _Hashtable> 660 { 661 float 662 max_load_factor() const 663 { 664 const _Hashtable* __this = static_cast<const _Hashtable*>(this); 665 return __this->__rehash_policy().max_load_factor(); 666 } 667 668 void 669 max_load_factor(float __z) 670 { 671 _Hashtable* __this = static_cast<_Hashtable*>(this); 672 __this->__rehash_policy(_Prime_rehash_policy(__z)); 673 } 674 }; 675 676 // Class template _Hash_code_base. Encapsulates two policy issues that 677 // aren't quite orthogonal. 678 // (1) the difference between using a ranged hash function and using 679 // the combination of a hash function and a range-hashing function. 680 // In the former case we don't have such things as hash codes, so 681 // we have a dummy type as placeholder. 682 // (2) Whether or not we cache hash codes. Caching hash codes is 683 // meaningless if we have a ranged hash function. 684 // We also put the key extraction and equality comparison function 685 // objects here, for convenience. 686 687 // Primary template: unused except as a hook for specializations. 688 template<typename _Key, typename _Value, 689 typename _ExtractKey, typename _Equal, 690 typename _H1, typename _H2, typename _Hash, 691 bool __cache_hash_code> 692 struct _Hash_code_base; 693 694 // Specialization: ranged hash function, no caching hash codes. H1 695 // and H2 are provided but ignored. We define a dummy hash code type. 696 template<typename _Key, typename _Value, 697 typename _ExtractKey, typename _Equal, 698 typename _H1, typename _H2, typename _Hash> 699 struct _Hash_code_base<_Key, _Value, _ExtractKey, _Equal, _H1, _H2, 700 _Hash, false> 701 { 702 protected: 703 _Hash_code_base(const _ExtractKey& __ex, const _Equal& __eq, 704 const _H1&, const _H2&, const _Hash& __h) 705 : _M_extract(__ex), _M_eq(__eq), _M_ranged_hash(__h) { } 706 707 typedef void* _Hash_code_type; 708 709 _Hash_code_type 710 _M_hash_code(const _Key& __key) const 711 { return 0; } 712 713 std::size_t 714 _M_bucket_index(const _Key& __k, _Hash_code_type, 715 std::size_t __n) const 716 { return _M_ranged_hash(__k, __n); } 717 718 std::size_t 719 _M_bucket_index(const _Hash_node<_Value, false>* __p, 720 std::size_t __n) const 721 { return _M_ranged_hash(_M_extract(__p->_M_v), __n); } 722 723 bool 724 _M_compare(const _Key& __k, _Hash_code_type, 725 _Hash_node<_Value, false>* __n) const 726 { return _M_eq(__k, _M_extract(__n->_M_v)); } 727 728 void 729 _M_store_code(_Hash_node<_Value, false>*, _Hash_code_type) const 730 { } 731 732 void 733 _M_copy_code(_Hash_node<_Value, false>*, 734 const _Hash_node<_Value, false>*) const 735 { } 736 737 void 738 _M_swap(_Hash_code_base& __x) 739 { 740 std::swap(_M_extract, __x._M_extract); 741 std::swap(_M_eq, __x._M_eq); 742 std::swap(_M_ranged_hash, __x._M_ranged_hash); 743 } 744 745 protected: 746 _ExtractKey _M_extract; 747 _Equal _M_eq; 748 _Hash _M_ranged_hash; 749 }; 750 751 752 // No specialization for ranged hash function while caching hash codes. 753 // That combination is meaningless, and trying to do it is an error. 754 755 756 // Specialization: ranged hash function, cache hash codes. This 757 // combination is meaningless, so we provide only a declaration 758 // and no definition. 759 template<typename _Key, typename _Value, 760 typename _ExtractKey, typename _Equal, 761 typename _H1, typename _H2, typename _Hash> 762 struct _Hash_code_base<_Key, _Value, _ExtractKey, _Equal, _H1, _H2, 763 _Hash, true>; 764 765 // Specialization: hash function and range-hashing function, no 766 // caching of hash codes. H is provided but ignored. Provides 767 // typedef and accessor required by TR1. 768 template<typename _Key, typename _Value, 769 typename _ExtractKey, typename _Equal, 770 typename _H1, typename _H2> 771 struct _Hash_code_base<_Key, _Value, _ExtractKey, _Equal, _H1, _H2, 772 _Default_ranged_hash, false> 773 { 774 typedef _H1 hasher; 775 776 hasher 777 hash_function() const 778 { return _M_h1; } 779 780 protected: 781 _Hash_code_base(const _ExtractKey& __ex, const _Equal& __eq, 782 const _H1& __h1, const _H2& __h2, 783 const _Default_ranged_hash&) 784 : _M_extract(__ex), _M_eq(__eq), _M_h1(__h1), _M_h2(__h2) { } 785 786 typedef std::size_t _Hash_code_type; 787 788 _Hash_code_type 789 _M_hash_code(const _Key& __k) const 790 { return _M_h1(__k); } 791 792 std::size_t 793 _M_bucket_index(const _Key&, _Hash_code_type __c, 794 std::size_t __n) const 795 { return _M_h2(__c, __n); } 796 797 std::size_t 798 _M_bucket_index(const _Hash_node<_Value, false>* __p, 799 std::size_t __n) const 800 { return _M_h2(_M_h1(_M_extract(__p->_M_v)), __n); } 801 802 bool 803 _M_compare(const _Key& __k, _Hash_code_type, 804 _Hash_node<_Value, false>* __n) const 805 { return _M_eq(__k, _M_extract(__n->_M_v)); } 806 807 void 808 _M_store_code(_Hash_node<_Value, false>*, _Hash_code_type) const 809 { } 810 811 void 812 _M_copy_code(_Hash_node<_Value, false>*, 813 const _Hash_node<_Value, false>*) const 814 { } 815 816 void 817 _M_swap(_Hash_code_base& __x) 818 { 819 std::swap(_M_extract, __x._M_extract); 820 std::swap(_M_eq, __x._M_eq); 821 std::swap(_M_h1, __x._M_h1); 822 std::swap(_M_h2, __x._M_h2); 823 } 824 825 protected: 826 _ExtractKey _M_extract; 827 _Equal _M_eq; 828 _H1 _M_h1; 829 _H2 _M_h2; 830 }; 831 832 // Specialization: hash function and range-hashing function, 833 // caching hash codes. H is provided but ignored. Provides 834 // typedef and accessor required by TR1. 835 template<typename _Key, typename _Value, 836 typename _ExtractKey, typename _Equal, 837 typename _H1, typename _H2> 838 struct _Hash_code_base<_Key, _Value, _ExtractKey, _Equal, _H1, _H2, 839 _Default_ranged_hash, true> 840 { 841 typedef _H1 hasher; 842 843 hasher 844 hash_function() const 845 { return _M_h1; } 846 847 protected: 848 _Hash_code_base(const _ExtractKey& __ex, const _Equal& __eq, 849 const _H1& __h1, const _H2& __h2, 850 const _Default_ranged_hash&) 851 : _M_extract(__ex), _M_eq(__eq), _M_h1(__h1), _M_h2(__h2) { } 852 853 typedef std::size_t _Hash_code_type; 854 855 _Hash_code_type 856 _M_hash_code(const _Key& __k) const 857 { return _M_h1(__k); } 858 859 std::size_t 860 _M_bucket_index(const _Key&, _Hash_code_type __c, 861 std::size_t __n) const 862 { return _M_h2(__c, __n); } 863 864 std::size_t 865 _M_bucket_index(const _Hash_node<_Value, true>* __p, 866 std::size_t __n) const 867 { return _M_h2(__p->_M_hash_code, __n); } 868 869 bool 870 _M_compare(const _Key& __k, _Hash_code_type __c, 871 _Hash_node<_Value, true>* __n) const 872 { return __c == __n->_M_hash_code && _M_eq(__k, _M_extract(__n->_M_v)); } 873 874 void 875 _M_store_code(_Hash_node<_Value, true>* __n, _Hash_code_type __c) const 876 { __n->_M_hash_code = __c; } 877 878 void 879 _M_copy_code(_Hash_node<_Value, true>* __to, 880 const _Hash_node<_Value, true>* __from) const 881 { __to->_M_hash_code = __from->_M_hash_code; } 882 883 void 884 _M_swap(_Hash_code_base& __x) 885 { 886 std::swap(_M_extract, __x._M_extract); 887 std::swap(_M_eq, __x._M_eq); 888 std::swap(_M_h1, __x._M_h1); 889 std::swap(_M_h2, __x._M_h2); 890 } 891 892 protected: 893 _ExtractKey _M_extract; 894 _Equal _M_eq; 895 _H1 _M_h1; 896 _H2 _M_h2; 897 }; 898} // namespace __detail 899_GLIBCXX_END_NAMESPACE 900} // namespace std::tr1 901 902#endif // _TR1_HASHTABLE_POLICY_H 903 904