00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033
00034 #ifndef _TR1_HASHTABLE_POLICY_H
00035 #define _TR1_HASHTABLE_POLICY_H 1
00036
00037 #include <functional>
00038 #include <tr1/utility>
00039 #include <ext/type_traits.h>
00040
00041 namespace std
00042 {
00043 _GLIBCXX_BEGIN_NAMESPACE(tr1)
00044 namespace __detail
00045 {
00046
00047
00048 template<class _Iterator>
00049 inline typename std::iterator_traits<_Iterator>::difference_type
00050 __distance_fw(_Iterator __first, _Iterator __last,
00051 std::input_iterator_tag)
00052 { return 0; }
00053
00054 template<class _Iterator>
00055 inline typename std::iterator_traits<_Iterator>::difference_type
00056 __distance_fw(_Iterator __first, _Iterator __last,
00057 std::forward_iterator_tag)
00058 { return std::distance(__first, __last); }
00059
00060 template<class _Iterator>
00061 inline typename std::iterator_traits<_Iterator>::difference_type
00062 __distance_fw(_Iterator __first, _Iterator __last)
00063 {
00064 typedef typename std::iterator_traits<_Iterator>::iterator_category _Tag;
00065 return __distance_fw(__first, __last, _Tag());
00066 }
00067
00068
00069
00070
00071
00072
00073
00074 struct _LessThan
00075 {
00076 template<typename _Tp, typename _Up>
00077 bool
00078 operator()(_Tp __x, _Up __y)
00079 { return __x < __y; }
00080 };
00081
00082 template<int __ulongsize = sizeof(unsigned long)>
00083 struct _Primes
00084 {
00085 static const int __n_primes = __ulongsize != 8 ? 256 : 256 + 48;
00086 static const unsigned long __primes[256 + 48 + 1];
00087 };
00088
00089 template<int __ulongsize>
00090 const int _Primes<__ulongsize>::__n_primes;
00091
00092 template<int __ulongsize>
00093 const unsigned long _Primes<__ulongsize>::__primes[256 + 48 + 1] =
00094 {
00095 2ul, 3ul, 5ul, 7ul, 11ul, 13ul, 17ul, 19ul, 23ul, 29ul, 31ul,
00096 37ul, 41ul, 43ul, 47ul, 53ul, 59ul, 61ul, 67ul, 71ul, 73ul, 79ul,
00097 83ul, 89ul, 97ul, 103ul, 109ul, 113ul, 127ul, 137ul, 139ul, 149ul,
00098 157ul, 167ul, 179ul, 193ul, 199ul, 211ul, 227ul, 241ul, 257ul,
00099 277ul, 293ul, 313ul, 337ul, 359ul, 383ul, 409ul, 439ul, 467ul,
00100 503ul, 541ul, 577ul, 619ul, 661ul, 709ul, 761ul, 823ul, 887ul,
00101 953ul, 1031ul, 1109ul, 1193ul, 1289ul, 1381ul, 1493ul, 1613ul,
00102 1741ul, 1879ul, 2029ul, 2179ul, 2357ul, 2549ul, 2753ul, 2971ul,
00103 3209ul, 3469ul, 3739ul, 4027ul, 4349ul, 4703ul, 5087ul, 5503ul,
00104 5953ul, 6427ul, 6949ul, 7517ul, 8123ul, 8783ul, 9497ul, 10273ul,
00105 11113ul, 12011ul, 12983ul, 14033ul, 15173ul, 16411ul, 17749ul,
00106 19183ul, 20753ul, 22447ul, 24281ul, 26267ul, 28411ul, 30727ul,
00107 33223ul, 35933ul, 38873ul, 42043ul, 45481ul, 49201ul, 53201ul,
00108 57557ul, 62233ul, 67307ul, 72817ul, 78779ul, 85229ul, 92203ul,
00109 99733ul, 107897ul, 116731ul, 126271ul, 136607ul, 147793ul,
00110 159871ul, 172933ul, 187091ul, 202409ul, 218971ul, 236897ul,
00111 256279ul, 277261ul, 299951ul, 324503ul, 351061ul, 379787ul,
00112 410857ul, 444487ul, 480881ul, 520241ul, 562841ul, 608903ul,
00113 658753ul, 712697ul, 771049ul, 834181ul, 902483ul, 976369ul,
00114 1056323ul, 1142821ul, 1236397ul, 1337629ul, 1447153ul, 1565659ul,
00115 1693859ul, 1832561ul, 1982627ul, 2144977ul, 2320627ul, 2510653ul,
00116 2716249ul, 2938679ul, 3179303ul, 3439651ul, 3721303ul, 4026031ul,
00117 4355707ul, 4712381ul, 5098259ul, 5515729ul, 5967347ul, 6456007ul,
00118 6984629ul, 7556579ul, 8175383ul, 8844859ul, 9569143ul, 10352717ul,
00119 11200489ul, 12117689ul, 13109983ul, 14183539ul, 15345007ul,
00120 16601593ul, 17961079ul, 19431899ul, 21023161ul, 22744717ul,
00121 24607243ul, 26622317ul, 28802401ul, 31160981ul, 33712729ul,
00122 36473443ul, 39460231ul, 42691603ul, 46187573ul, 49969847ul,
00123 54061849ul, 58488943ul, 63278561ul, 68460391ul, 74066549ul,
00124 80131819ul, 86693767ul, 93793069ul, 101473717ul, 109783337ul,
00125 118773397ul, 128499677ul, 139022417ul, 150406843ul, 162723577ul,
00126 176048909ul, 190465427ul, 206062531ul, 222936881ul, 241193053ul,
00127 260944219ul, 282312799ul, 305431229ul, 330442829ul, 357502601ul,
00128 386778277ul, 418451333ul, 452718089ul, 489790921ul, 529899637ul,
00129 573292817ul, 620239453ul, 671030513ul, 725980837ul, 785430967ul,
00130 849749479ul, 919334987ul, 994618837ul, 1076067617ul, 1164186217ul,
00131 1259520799ul, 1362662261ul, 1474249943ul, 1594975441ul,
00132 1725587117ul, 1866894511ul, 2019773507ul, 2185171673ul,
00133 2364114217ul, 2557710269ul, 2767159799ul, 2993761039ul,
00134 3238918481ul, 3504151727ul, 3791104843ul, 4101556399ul,
00135 4294967291ul,
00136
00137
00138 __ulongsize != 8 ? 4294967291ul : (unsigned long)6442450933ull,
00139 (unsigned long)8589934583ull,
00140 (unsigned long)12884901857ull, (unsigned long)17179869143ull,
00141 (unsigned long)25769803693ull, (unsigned long)34359738337ull,
00142 (unsigned long)51539607367ull, (unsigned long)68719476731ull,
00143 (unsigned long)103079215087ull, (unsigned long)137438953447ull,
00144 (unsigned long)206158430123ull, (unsigned long)274877906899ull,
00145 (unsigned long)412316860387ull, (unsigned long)549755813881ull,
00146 (unsigned long)824633720731ull, (unsigned long)1099511627689ull,
00147 (unsigned long)1649267441579ull, (unsigned long)2199023255531ull,
00148 (unsigned long)3298534883309ull, (unsigned long)4398046511093ull,
00149 (unsigned long)6597069766607ull, (unsigned long)8796093022151ull,
00150 (unsigned long)13194139533241ull, (unsigned long)17592186044399ull,
00151 (unsigned long)26388279066581ull, (unsigned long)35184372088777ull,
00152 (unsigned long)52776558133177ull, (unsigned long)70368744177643ull,
00153 (unsigned long)105553116266399ull, (unsigned long)140737488355213ull,
00154 (unsigned long)211106232532861ull, (unsigned long)281474976710597ull,
00155 (unsigned long)562949953421231ull, (unsigned long)1125899906842597ull,
00156 (unsigned long)2251799813685119ull, (unsigned long)4503599627370449ull,
00157 (unsigned long)9007199254740881ull, (unsigned long)18014398509481951ull,
00158 (unsigned long)36028797018963913ull, (unsigned long)72057594037927931ull,
00159 (unsigned long)144115188075855859ull,
00160 (unsigned long)288230376151711717ull,
00161 (unsigned long)576460752303423433ull,
00162 (unsigned long)1152921504606846883ull,
00163 (unsigned long)2305843009213693951ull,
00164 (unsigned long)4611686018427387847ull,
00165 (unsigned long)9223372036854775783ull,
00166 (unsigned long)18446744073709551557ull,
00167 (unsigned long)18446744073709551557ull
00168 };
00169
00170
00171
00172
00173
00174
00175
00176
00177 template<typename _Value, bool __cache_hash_code>
00178 struct _Hash_node;
00179
00180 template<typename _Value>
00181 struct _Hash_node<_Value, true>
00182 {
00183 _Value _M_v;
00184 std::size_t _M_hash_code;
00185 _Hash_node* _M_next;
00186 };
00187
00188 template<typename _Value>
00189 struct _Hash_node<_Value, false>
00190 {
00191 _Value _M_v;
00192 _Hash_node* _M_next;
00193 };
00194
00195
00196
00197 template<typename _Value, bool __cache>
00198 struct _Node_iterator_base
00199 {
00200 _Node_iterator_base(_Hash_node<_Value, __cache>* __p)
00201 : _M_cur(__p) { }
00202
00203 void
00204 _M_incr()
00205 { _M_cur = _M_cur->_M_next; }
00206
00207 _Hash_node<_Value, __cache>* _M_cur;
00208 };
00209
00210 template<typename _Value, bool __cache>
00211 inline bool
00212 operator==(const _Node_iterator_base<_Value, __cache>& __x,
00213 const _Node_iterator_base<_Value, __cache>& __y)
00214 { return __x._M_cur == __y._M_cur; }
00215
00216 template<typename _Value, bool __cache>
00217 inline bool
00218 operator!=(const _Node_iterator_base<_Value, __cache>& __x,
00219 const _Node_iterator_base<_Value, __cache>& __y)
00220 { return __x._M_cur != __y._M_cur; }
00221
00222 template<typename _Value, bool __constant_iterators, bool __cache>
00223 struct _Node_iterator
00224 : public _Node_iterator_base<_Value, __cache>
00225 {
00226 typedef _Value value_type;
00227 typedef typename
00228 __gnu_cxx::__conditional_type<__constant_iterators,
00229 const _Value*, _Value*>::__type
00230 pointer;
00231 typedef typename
00232 __gnu_cxx::__conditional_type<__constant_iterators,
00233 const _Value&, _Value&>::__type
00234 reference;
00235 typedef std::ptrdiff_t difference_type;
00236 typedef std::forward_iterator_tag iterator_category;
00237
00238 _Node_iterator()
00239 : _Node_iterator_base<_Value, __cache>(0) { }
00240
00241 explicit
00242 _Node_iterator(_Hash_node<_Value, __cache>* __p)
00243 : _Node_iterator_base<_Value, __cache>(__p) { }
00244
00245 reference
00246 operator*() const
00247 { return this->_M_cur->_M_v; }
00248
00249 pointer
00250 operator->() const
00251 { return &this->_M_cur->_M_v; }
00252
00253 _Node_iterator&
00254 operator++()
00255 {
00256 this->_M_incr();
00257 return *this;
00258 }
00259
00260 _Node_iterator
00261 operator++(int)
00262 {
00263 _Node_iterator __tmp(*this);
00264 this->_M_incr();
00265 return __tmp;
00266 }
00267 };
00268
00269 template<typename _Value, bool __constant_iterators, bool __cache>
00270 struct _Node_const_iterator
00271 : public _Node_iterator_base<_Value, __cache>
00272 {
00273 typedef _Value value_type;
00274 typedef const _Value* pointer;
00275 typedef const _Value& reference;
00276 typedef std::ptrdiff_t difference_type;
00277 typedef std::forward_iterator_tag iterator_category;
00278
00279 _Node_const_iterator()
00280 : _Node_iterator_base<_Value, __cache>(0) { }
00281
00282 explicit
00283 _Node_const_iterator(_Hash_node<_Value, __cache>* __p)
00284 : _Node_iterator_base<_Value, __cache>(__p) { }
00285
00286 _Node_const_iterator(const _Node_iterator<_Value, __constant_iterators,
00287 __cache>& __x)
00288 : _Node_iterator_base<_Value, __cache>(__x._M_cur) { }
00289
00290 reference
00291 operator*() const
00292 { return this->_M_cur->_M_v; }
00293
00294 pointer
00295 operator->() const
00296 { return &this->_M_cur->_M_v; }
00297
00298 _Node_const_iterator&
00299 operator++()
00300 {
00301 this->_M_incr();
00302 return *this;
00303 }
00304
00305 _Node_const_iterator
00306 operator++(int)
00307 {
00308 _Node_const_iterator __tmp(*this);
00309 this->_M_incr();
00310 return __tmp;
00311 }
00312 };
00313
00314 template<typename _Value, bool __cache>
00315 struct _Hashtable_iterator_base
00316 {
00317 _Hashtable_iterator_base(_Hash_node<_Value, __cache>* __node,
00318 _Hash_node<_Value, __cache>** __bucket)
00319 : _M_cur_node(__node), _M_cur_bucket(__bucket) { }
00320
00321 void
00322 _M_incr()
00323 {
00324 _M_cur_node = _M_cur_node->_M_next;
00325 if (!_M_cur_node)
00326 _M_incr_bucket();
00327 }
00328
00329 void
00330 _M_incr_bucket();
00331
00332 _Hash_node<_Value, __cache>* _M_cur_node;
00333 _Hash_node<_Value, __cache>** _M_cur_bucket;
00334 };
00335
00336
00337
00338 template<typename _Value, bool __cache>
00339 void
00340 _Hashtable_iterator_base<_Value, __cache>::
00341 _M_incr_bucket()
00342 {
00343 ++_M_cur_bucket;
00344
00345
00346 while (!*_M_cur_bucket)
00347 ++_M_cur_bucket;
00348 _M_cur_node = *_M_cur_bucket;
00349 }
00350
00351 template<typename _Value, bool __cache>
00352 inline bool
00353 operator==(const _Hashtable_iterator_base<_Value, __cache>& __x,
00354 const _Hashtable_iterator_base<_Value, __cache>& __y)
00355 { return __x._M_cur_node == __y._M_cur_node; }
00356
00357 template<typename _Value, bool __cache>
00358 inline bool
00359 operator!=(const _Hashtable_iterator_base<_Value, __cache>& __x,
00360 const _Hashtable_iterator_base<_Value, __cache>& __y)
00361 { return __x._M_cur_node != __y._M_cur_node; }
00362
00363 template<typename _Value, bool __constant_iterators, bool __cache>
00364 struct _Hashtable_iterator
00365 : public _Hashtable_iterator_base<_Value, __cache>
00366 {
00367 typedef _Value value_type;
00368 typedef typename
00369 __gnu_cxx::__conditional_type<__constant_iterators,
00370 const _Value*, _Value*>::__type
00371 pointer;
00372 typedef typename
00373 __gnu_cxx::__conditional_type<__constant_iterators,
00374 const _Value&, _Value&>::__type
00375 reference;
00376 typedef std::ptrdiff_t difference_type;
00377 typedef std::forward_iterator_tag iterator_category;
00378
00379 _Hashtable_iterator()
00380 : _Hashtable_iterator_base<_Value, __cache>(0, 0) { }
00381
00382 _Hashtable_iterator(_Hash_node<_Value, __cache>* __p,
00383 _Hash_node<_Value, __cache>** __b)
00384 : _Hashtable_iterator_base<_Value, __cache>(__p, __b) { }
00385
00386 explicit
00387 _Hashtable_iterator(_Hash_node<_Value, __cache>** __b)
00388 : _Hashtable_iterator_base<_Value, __cache>(*__b, __b) { }
00389
00390 reference
00391 operator*() const
00392 { return this->_M_cur_node->_M_v; }
00393
00394 pointer
00395 operator->() const
00396 { return &this->_M_cur_node->_M_v; }
00397
00398 _Hashtable_iterator&
00399 operator++()
00400 {
00401 this->_M_incr();
00402 return *this;
00403 }
00404
00405 _Hashtable_iterator
00406 operator++(int)
00407 {
00408 _Hashtable_iterator __tmp(*this);
00409 this->_M_incr();
00410 return __tmp;
00411 }
00412 };
00413
00414 template<typename _Value, bool __constant_iterators, bool __cache>
00415 struct _Hashtable_const_iterator
00416 : public _Hashtable_iterator_base<_Value, __cache>
00417 {
00418 typedef _Value value_type;
00419 typedef const _Value* pointer;
00420 typedef const _Value& reference;
00421 typedef std::ptrdiff_t difference_type;
00422 typedef std::forward_iterator_tag iterator_category;
00423
00424 _Hashtable_const_iterator()
00425 : _Hashtable_iterator_base<_Value, __cache>(0, 0) { }
00426
00427 _Hashtable_const_iterator(_Hash_node<_Value, __cache>* __p,
00428 _Hash_node<_Value, __cache>** __b)
00429 : _Hashtable_iterator_base<_Value, __cache>(__p, __b) { }
00430
00431 explicit
00432 _Hashtable_const_iterator(_Hash_node<_Value, __cache>** __b)
00433 : _Hashtable_iterator_base<_Value, __cache>(*__b, __b) { }
00434
00435 _Hashtable_const_iterator(const _Hashtable_iterator<_Value,
00436 __constant_iterators, __cache>& __x)
00437 : _Hashtable_iterator_base<_Value, __cache>(__x._M_cur_node,
00438 __x._M_cur_bucket) { }
00439
00440 reference
00441 operator*() const
00442 { return this->_M_cur_node->_M_v; }
00443
00444 pointer
00445 operator->() const
00446 { return &this->_M_cur_node->_M_v; }
00447
00448 _Hashtable_const_iterator&
00449 operator++()
00450 {
00451 this->_M_incr();
00452 return *this;
00453 }
00454
00455 _Hashtable_const_iterator
00456 operator++(int)
00457 {
00458 _Hashtable_const_iterator __tmp(*this);
00459 this->_M_incr();
00460 return __tmp;
00461 }
00462 };
00463
00464
00465
00466
00467
00468
00469
00470 struct _Mod_range_hashing
00471 {
00472 typedef std::size_t first_argument_type;
00473 typedef std::size_t second_argument_type;
00474 typedef std::size_t result_type;
00475
00476 result_type
00477 operator()(first_argument_type __num, second_argument_type __den) const
00478 { return __num % __den; }
00479 };
00480
00481
00482
00483
00484
00485
00486 struct _Default_ranged_hash { };
00487
00488
00489
00490 struct _Prime_rehash_policy
00491 {
00492 _Prime_rehash_policy(float __z = 1.0);
00493
00494 float
00495 max_load_factor() const;
00496
00497
00498 std::size_t
00499 _M_next_bkt(std::size_t __n) const;
00500
00501
00502 std::size_t
00503 _M_bkt_for_elements(std::size_t __n) const;
00504
00505
00506
00507
00508
00509 std::pair<bool, std::size_t>
00510 _M_need_rehash(std::size_t __n_bkt, std::size_t __n_elt,
00511 std::size_t __n_ins) const;
00512
00513 float _M_max_load_factor;
00514 float _M_growth_factor;
00515 mutable std::size_t _M_next_resize;
00516 };
00517
00518 inline
00519 _Prime_rehash_policy::
00520 _Prime_rehash_policy(float __z)
00521 : _M_max_load_factor(__z), _M_growth_factor(2.f), _M_next_resize(0)
00522 { }
00523
00524 inline float
00525 _Prime_rehash_policy::
00526 max_load_factor() const
00527 { return _M_max_load_factor; }
00528
00529
00530 inline std::size_t
00531 _Prime_rehash_policy::
00532 _M_next_bkt(std::size_t __n) const
00533 {
00534 const unsigned long* const __last = (_Primes<>::__primes
00535 + _Primes<>::__n_primes);
00536 const unsigned long* __p = std::lower_bound(_Primes<>::__primes, __last,
00537 __n);
00538 _M_next_resize = static_cast<std::size_t>(std::ceil(*__p
00539 * _M_max_load_factor));
00540 return *__p;
00541 }
00542
00543
00544
00545 inline std::size_t
00546 _Prime_rehash_policy::
00547 _M_bkt_for_elements(std::size_t __n) const
00548 {
00549 const unsigned long* const __last = (_Primes<>::__primes
00550 + _Primes<>::__n_primes);
00551 const float __min_bkts = __n / _M_max_load_factor;
00552 const unsigned long* __p = std::lower_bound(_Primes<>::__primes, __last,
00553 __min_bkts, _LessThan());
00554 _M_next_resize = static_cast<std::size_t>(std::ceil(*__p
00555 * _M_max_load_factor));
00556 return *__p;
00557 }
00558
00559
00560
00561
00562
00563
00564
00565
00566
00567
00568 inline std::pair<bool, std::size_t>
00569 _Prime_rehash_policy::
00570 _M_need_rehash(std::size_t __n_bkt, std::size_t __n_elt,
00571 std::size_t __n_ins) const
00572 {
00573 if (__n_elt + __n_ins > _M_next_resize)
00574 {
00575 float __min_bkts = ((float(__n_ins) + float(__n_elt))
00576 / _M_max_load_factor);
00577 if (__min_bkts > __n_bkt)
00578 {
00579 __min_bkts = std::max(__min_bkts, _M_growth_factor * __n_bkt);
00580 const unsigned long* const __last = (_Primes<>::__primes
00581 + _Primes<>::__n_primes);
00582 const unsigned long* __p = std::lower_bound(_Primes<>::__primes,
00583 __last, __min_bkts,
00584 _LessThan());
00585 _M_next_resize =
00586 static_cast<std::size_t>(std::ceil(*__p * _M_max_load_factor));
00587 return std::make_pair(true, *__p);
00588 }
00589 else
00590 {
00591 _M_next_resize =
00592 static_cast<std::size_t>(std::ceil(__n_bkt
00593 * _M_max_load_factor));
00594 return std::make_pair(false, 0);
00595 }
00596 }
00597 else
00598 return std::make_pair(false, 0);
00599 }
00600
00601
00602
00603
00604
00605
00606
00607
00608
00609
00610
00611
00612
00613
00614
00615 template<typename _Key, typename _Value, typename _Ex, bool __unique,
00616 typename _Hashtable>
00617 struct _Map_base { };
00618
00619 template<typename _Key, typename _Pair, typename _Hashtable>
00620 struct _Map_base<_Key, _Pair, std::_Select1st<_Pair>, false, _Hashtable>
00621 {
00622 typedef typename _Pair::second_type mapped_type;
00623 };
00624
00625 template<typename _Key, typename _Pair, typename _Hashtable>
00626 struct _Map_base<_Key, _Pair, std::_Select1st<_Pair>, true, _Hashtable>
00627 {
00628 typedef typename _Pair::second_type mapped_type;
00629
00630 mapped_type&
00631 operator[](const _Key& __k);
00632 };
00633
00634 template<typename _Key, typename _Pair, typename _Hashtable>
00635 typename _Map_base<_Key, _Pair, std::_Select1st<_Pair>,
00636 true, _Hashtable>::mapped_type&
00637 _Map_base<_Key, _Pair, std::_Select1st<_Pair>, true, _Hashtable>::
00638 operator[](const _Key& __k)
00639 {
00640 _Hashtable* __h = static_cast<_Hashtable*>(this);
00641 typename _Hashtable::_Hash_code_type __code = __h->_M_hash_code(__k);
00642 std::size_t __n = __h->_M_bucket_index(__k, __code,
00643 __h->_M_bucket_count);
00644
00645 typename _Hashtable::_Node* __p =
00646 __h->_M_find_node(__h->_M_buckets[__n], __k, __code);
00647 if (!__p)
00648 return __h->_M_insert_bucket(std::make_pair(__k, mapped_type()),
00649 __n, __code)->second;
00650 return (__p->_M_v).second;
00651 }
00652
00653
00654
00655 template<typename _RehashPolicy, typename _Hashtable>
00656 struct _Rehash_base { };
00657
00658 template<typename _Hashtable>
00659 struct _Rehash_base<_Prime_rehash_policy, _Hashtable>
00660 {
00661 float
00662 max_load_factor() const
00663 {
00664 const _Hashtable* __this = static_cast<const _Hashtable*>(this);
00665 return __this->__rehash_policy().max_load_factor();
00666 }
00667
00668 void
00669 max_load_factor(float __z)
00670 {
00671 _Hashtable* __this = static_cast<_Hashtable*>(this);
00672 __this->__rehash_policy(_Prime_rehash_policy(__z));
00673 }
00674 };
00675
00676
00677
00678
00679
00680
00681
00682
00683
00684
00685
00686
00687
00688 template<typename _Key, typename _Value,
00689 typename _ExtractKey, typename _Equal,
00690 typename _H1, typename _H2, typename _Hash,
00691 bool __cache_hash_code>
00692 struct _Hash_code_base;
00693
00694
00695
00696 template<typename _Key, typename _Value,
00697 typename _ExtractKey, typename _Equal,
00698 typename _H1, typename _H2, typename _Hash>
00699 struct _Hash_code_base<_Key, _Value, _ExtractKey, _Equal, _H1, _H2,
00700 _Hash, false>
00701 {
00702 protected:
00703 _Hash_code_base(const _ExtractKey& __ex, const _Equal& __eq,
00704 const _H1&, const _H2&, const _Hash& __h)
00705 : _M_extract(__ex), _M_eq(__eq), _M_ranged_hash(__h) { }
00706
00707 typedef void* _Hash_code_type;
00708
00709 _Hash_code_type
00710 _M_hash_code(const _Key& __key) const
00711 { return 0; }
00712
00713 std::size_t
00714 _M_bucket_index(const _Key& __k, _Hash_code_type,
00715 std::size_t __n) const
00716 { return _M_ranged_hash(__k, __n); }
00717
00718 std::size_t
00719 _M_bucket_index(const _Hash_node<_Value, false>* __p,
00720 std::size_t __n) const
00721 { return _M_ranged_hash(_M_extract(__p->_M_v), __n); }
00722
00723 bool
00724 _M_compare(const _Key& __k, _Hash_code_type,
00725 _Hash_node<_Value, false>* __n) const
00726 { return _M_eq(__k, _M_extract(__n->_M_v)); }
00727
00728 void
00729 _M_store_code(_Hash_node<_Value, false>*, _Hash_code_type) const
00730 { }
00731
00732 void
00733 _M_copy_code(_Hash_node<_Value, false>*,
00734 const _Hash_node<_Value, false>*) const
00735 { }
00736
00737 void
00738 _M_swap(_Hash_code_base& __x)
00739 {
00740 std::swap(_M_extract, __x._M_extract);
00741 std::swap(_M_eq, __x._M_eq);
00742 std::swap(_M_ranged_hash, __x._M_ranged_hash);
00743 }
00744
00745 protected:
00746 _ExtractKey _M_extract;
00747 _Equal _M_eq;
00748 _Hash _M_ranged_hash;
00749 };
00750
00751
00752
00753
00754
00755
00756
00757
00758
00759 template<typename _Key, typename _Value,
00760 typename _ExtractKey, typename _Equal,
00761 typename _H1, typename _H2, typename _Hash>
00762 struct _Hash_code_base<_Key, _Value, _ExtractKey, _Equal, _H1, _H2,
00763 _Hash, true>;
00764
00765
00766
00767
00768 template<typename _Key, typename _Value,
00769 typename _ExtractKey, typename _Equal,
00770 typename _H1, typename _H2>
00771 struct _Hash_code_base<_Key, _Value, _ExtractKey, _Equal, _H1, _H2,
00772 _Default_ranged_hash, false>
00773 {
00774 typedef _H1 hasher;
00775
00776 hasher
00777 hash_function() const
00778 { return _M_h1; }
00779
00780 protected:
00781 _Hash_code_base(const _ExtractKey& __ex, const _Equal& __eq,
00782 const _H1& __h1, const _H2& __h2,
00783 const _Default_ranged_hash&)
00784 : _M_extract(__ex), _M_eq(__eq), _M_h1(__h1), _M_h2(__h2) { }
00785
00786 typedef std::size_t _Hash_code_type;
00787
00788 _Hash_code_type
00789 _M_hash_code(const _Key& __k) const
00790 { return _M_h1(__k); }
00791
00792 std::size_t
00793 _M_bucket_index(const _Key&, _Hash_code_type __c,
00794 std::size_t __n) const
00795 { return _M_h2(__c, __n); }
00796
00797 std::size_t
00798 _M_bucket_index(const _Hash_node<_Value, false>* __p,
00799 std::size_t __n) const
00800 { return _M_h2(_M_h1(_M_extract(__p->_M_v)), __n); }
00801
00802 bool
00803 _M_compare(const _Key& __k, _Hash_code_type,
00804 _Hash_node<_Value, false>* __n) const
00805 { return _M_eq(__k, _M_extract(__n->_M_v)); }
00806
00807 void
00808 _M_store_code(_Hash_node<_Value, false>*, _Hash_code_type) const
00809 { }
00810
00811 void
00812 _M_copy_code(_Hash_node<_Value, false>*,
00813 const _Hash_node<_Value, false>*) const
00814 { }
00815
00816 void
00817 _M_swap(_Hash_code_base& __x)
00818 {
00819 std::swap(_M_extract, __x._M_extract);
00820 std::swap(_M_eq, __x._M_eq);
00821 std::swap(_M_h1, __x._M_h1);
00822 std::swap(_M_h2, __x._M_h2);
00823 }
00824
00825 protected:
00826 _ExtractKey _M_extract;
00827 _Equal _M_eq;
00828 _H1 _M_h1;
00829 _H2 _M_h2;
00830 };
00831
00832
00833
00834
00835 template<typename _Key, typename _Value,
00836 typename _ExtractKey, typename _Equal,
00837 typename _H1, typename _H2>
00838 struct _Hash_code_base<_Key, _Value, _ExtractKey, _Equal, _H1, _H2,
00839 _Default_ranged_hash, true>
00840 {
00841 typedef _H1 hasher;
00842
00843 hasher
00844 hash_function() const
00845 { return _M_h1; }
00846
00847 protected:
00848 _Hash_code_base(const _ExtractKey& __ex, const _Equal& __eq,
00849 const _H1& __h1, const _H2& __h2,
00850 const _Default_ranged_hash&)
00851 : _M_extract(__ex), _M_eq(__eq), _M_h1(__h1), _M_h2(__h2) { }
00852
00853 typedef std::size_t _Hash_code_type;
00854
00855 _Hash_code_type
00856 _M_hash_code(const _Key& __k) const
00857 { return _M_h1(__k); }
00858
00859 std::size_t
00860 _M_bucket_index(const _Key&, _Hash_code_type __c,
00861 std::size_t __n) const
00862 { return _M_h2(__c, __n); }
00863
00864 std::size_t
00865 _M_bucket_index(const _Hash_node<_Value, true>* __p,
00866 std::size_t __n) const
00867 { return _M_h2(__p->_M_hash_code, __n); }
00868
00869 bool
00870 _M_compare(const _Key& __k, _Hash_code_type __c,
00871 _Hash_node<_Value, true>* __n) const
00872 { return __c == __n->_M_hash_code && _M_eq(__k, _M_extract(__n->_M_v)); }
00873
00874 void
00875 _M_store_code(_Hash_node<_Value, true>* __n, _Hash_code_type __c) const
00876 { __n->_M_hash_code = __c; }
00877
00878 void
00879 _M_copy_code(_Hash_node<_Value, true>* __to,
00880 const _Hash_node<_Value, true>* __from) const
00881 { __to->_M_hash_code = __from->_M_hash_code; }
00882
00883 void
00884 _M_swap(_Hash_code_base& __x)
00885 {
00886 std::swap(_M_extract, __x._M_extract);
00887 std::swap(_M_eq, __x._M_eq);
00888 std::swap(_M_h1, __x._M_h1);
00889 std::swap(_M_h2, __x._M_h2);
00890 }
00891
00892 protected:
00893 _ExtractKey _M_extract;
00894 _Equal _M_eq;
00895 _H1 _M_h1;
00896 _H2 _M_h2;
00897 };
00898 }
00899 _GLIBCXX_END_NAMESPACE
00900 }
00901
00902 #endif // _TR1_HASHTABLE_POLICY_H
00903