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 namespace std
00031 {
00032 _GLIBCXX_BEGIN_NAMESPACE_TR1
00033
00034 namespace __detail
00035 {
00036
00037
00038 template<class _Iterator>
00039 inline typename std::iterator_traits<_Iterator>::difference_type
00040 __distance_fw(_Iterator __first, _Iterator __last,
00041 std::input_iterator_tag)
00042 { return 0; }
00043
00044 template<class _Iterator>
00045 inline typename std::iterator_traits<_Iterator>::difference_type
00046 __distance_fw(_Iterator __first, _Iterator __last,
00047 std::forward_iterator_tag)
00048 { return std::distance(__first, __last); }
00049
00050 template<class _Iterator>
00051 inline typename std::iterator_traits<_Iterator>::difference_type
00052 __distance_fw(_Iterator __first, _Iterator __last)
00053 {
00054 typedef typename std::iterator_traits<_Iterator>::iterator_category _Tag;
00055 return __distance_fw(__first, __last, _Tag());
00056 }
00057
00058 template<typename _RAIter, typename _Tp>
00059 _RAIter
00060 __lower_bound(_RAIter __first, _RAIter __last, const _Tp& __val)
00061 {
00062 typedef typename std::iterator_traits<_RAIter>::difference_type _DType;
00063
00064 _DType __len = __last - __first;
00065 while (__len > 0)
00066 {
00067 _DType __half = __len >> 1;
00068 _RAIter __middle = __first + __half;
00069 if (*__middle < __val)
00070 {
00071 __first = __middle;
00072 ++__first;
00073 __len = __len - __half - 1;
00074 }
00075 else
00076 __len = __half;
00077 }
00078 return __first;
00079 }
00080
00081
00082
00083
00084
00085
00086
00087
00088 template<typename _Value, bool __cache_hash_code>
00089 struct _Hash_node;
00090
00091 template<typename _Value>
00092 struct _Hash_node<_Value, true>
00093 {
00094 _Value _M_v;
00095 std::size_t _M_hash_code;
00096 _Hash_node* _M_next;
00097
00098 #ifdef _GLIBCXX_INCLUDE_AS_CXX0X
00099 template<typename... _Args>
00100 _Hash_node(_Args&&... __args)
00101 : _M_v(std::forward<_Args>(__args)...),
00102 _M_hash_code(), _M_next() { }
00103 #endif
00104 };
00105
00106 template<typename _Value>
00107 struct _Hash_node<_Value, false>
00108 {
00109 _Value _M_v;
00110 _Hash_node* _M_next;
00111
00112 #ifdef _GLIBCXX_INCLUDE_AS_CXX0X
00113 template<typename... _Args>
00114 _Hash_node(_Args&&... __args)
00115 : _M_v(std::forward<_Args>(__args)...),
00116 _M_next() { }
00117 #endif
00118 };
00119
00120
00121
00122 template<typename _Value, bool __cache>
00123 struct _Node_iterator_base
00124 {
00125 _Node_iterator_base(_Hash_node<_Value, __cache>* __p)
00126 : _M_cur(__p) { }
00127
00128 void
00129 _M_incr()
00130 { _M_cur = _M_cur->_M_next; }
00131
00132 _Hash_node<_Value, __cache>* _M_cur;
00133 };
00134
00135 template<typename _Value, bool __cache>
00136 inline bool
00137 operator==(const _Node_iterator_base<_Value, __cache>& __x,
00138 const _Node_iterator_base<_Value, __cache>& __y)
00139 { return __x._M_cur == __y._M_cur; }
00140
00141 template<typename _Value, bool __cache>
00142 inline bool
00143 operator!=(const _Node_iterator_base<_Value, __cache>& __x,
00144 const _Node_iterator_base<_Value, __cache>& __y)
00145 { return __x._M_cur != __y._M_cur; }
00146
00147 template<typename _Value, bool __constant_iterators, bool __cache>
00148 struct _Node_iterator
00149 : public _Node_iterator_base<_Value, __cache>
00150 {
00151 typedef _Value value_type;
00152 typedef typename
00153 __gnu_cxx::__conditional_type<__constant_iterators,
00154 const _Value*, _Value*>::__type
00155 pointer;
00156 typedef typename
00157 __gnu_cxx::__conditional_type<__constant_iterators,
00158 const _Value&, _Value&>::__type
00159 reference;
00160 typedef std::ptrdiff_t difference_type;
00161 typedef std::forward_iterator_tag iterator_category;
00162
00163 _Node_iterator()
00164 : _Node_iterator_base<_Value, __cache>(0) { }
00165
00166 explicit
00167 _Node_iterator(_Hash_node<_Value, __cache>* __p)
00168 : _Node_iterator_base<_Value, __cache>(__p) { }
00169
00170 reference
00171 operator*() const
00172 { return this->_M_cur->_M_v; }
00173
00174 pointer
00175 operator->() const
00176 { return &this->_M_cur->_M_v; }
00177
00178 _Node_iterator&
00179 operator++()
00180 {
00181 this->_M_incr();
00182 return *this;
00183 }
00184
00185 _Node_iterator
00186 operator++(int)
00187 {
00188 _Node_iterator __tmp(*this);
00189 this->_M_incr();
00190 return __tmp;
00191 }
00192 };
00193
00194 template<typename _Value, bool __constant_iterators, bool __cache>
00195 struct _Node_const_iterator
00196 : public _Node_iterator_base<_Value, __cache>
00197 {
00198 typedef _Value value_type;
00199 typedef const _Value* pointer;
00200 typedef const _Value& reference;
00201 typedef std::ptrdiff_t difference_type;
00202 typedef std::forward_iterator_tag iterator_category;
00203
00204 _Node_const_iterator()
00205 : _Node_iterator_base<_Value, __cache>(0) { }
00206
00207 explicit
00208 _Node_const_iterator(_Hash_node<_Value, __cache>* __p)
00209 : _Node_iterator_base<_Value, __cache>(__p) { }
00210
00211 _Node_const_iterator(const _Node_iterator<_Value, __constant_iterators,
00212 __cache>& __x)
00213 : _Node_iterator_base<_Value, __cache>(__x._M_cur) { }
00214
00215 reference
00216 operator*() const
00217 { return this->_M_cur->_M_v; }
00218
00219 pointer
00220 operator->() const
00221 { return &this->_M_cur->_M_v; }
00222
00223 _Node_const_iterator&
00224 operator++()
00225 {
00226 this->_M_incr();
00227 return *this;
00228 }
00229
00230 _Node_const_iterator
00231 operator++(int)
00232 {
00233 _Node_const_iterator __tmp(*this);
00234 this->_M_incr();
00235 return __tmp;
00236 }
00237 };
00238
00239 template<typename _Value, bool __cache>
00240 struct _Hashtable_iterator_base
00241 {
00242 _Hashtable_iterator_base(_Hash_node<_Value, __cache>* __node,
00243 _Hash_node<_Value, __cache>** __bucket)
00244 : _M_cur_node(__node), _M_cur_bucket(__bucket) { }
00245
00246 void
00247 _M_incr()
00248 {
00249 _M_cur_node = _M_cur_node->_M_next;
00250 if (!_M_cur_node)
00251 _M_incr_bucket();
00252 }
00253
00254 void
00255 _M_incr_bucket();
00256
00257 _Hash_node<_Value, __cache>* _M_cur_node;
00258 _Hash_node<_Value, __cache>** _M_cur_bucket;
00259 };
00260
00261
00262
00263 template<typename _Value, bool __cache>
00264 void
00265 _Hashtable_iterator_base<_Value, __cache>::
00266 _M_incr_bucket()
00267 {
00268 ++_M_cur_bucket;
00269
00270
00271 while (!*_M_cur_bucket)
00272 ++_M_cur_bucket;
00273 _M_cur_node = *_M_cur_bucket;
00274 }
00275
00276 template<typename _Value, bool __cache>
00277 inline bool
00278 operator==(const _Hashtable_iterator_base<_Value, __cache>& __x,
00279 const _Hashtable_iterator_base<_Value, __cache>& __y)
00280 { return __x._M_cur_node == __y._M_cur_node; }
00281
00282 template<typename _Value, bool __cache>
00283 inline bool
00284 operator!=(const _Hashtable_iterator_base<_Value, __cache>& __x,
00285 const _Hashtable_iterator_base<_Value, __cache>& __y)
00286 { return __x._M_cur_node != __y._M_cur_node; }
00287
00288 template<typename _Value, bool __constant_iterators, bool __cache>
00289 struct _Hashtable_iterator
00290 : public _Hashtable_iterator_base<_Value, __cache>
00291 {
00292 typedef _Value value_type;
00293 typedef typename
00294 __gnu_cxx::__conditional_type<__constant_iterators,
00295 const _Value*, _Value*>::__type
00296 pointer;
00297 typedef typename
00298 __gnu_cxx::__conditional_type<__constant_iterators,
00299 const _Value&, _Value&>::__type
00300 reference;
00301 typedef std::ptrdiff_t difference_type;
00302 typedef std::forward_iterator_tag iterator_category;
00303
00304 _Hashtable_iterator()
00305 : _Hashtable_iterator_base<_Value, __cache>(0, 0) { }
00306
00307 _Hashtable_iterator(_Hash_node<_Value, __cache>* __p,
00308 _Hash_node<_Value, __cache>** __b)
00309 : _Hashtable_iterator_base<_Value, __cache>(__p, __b) { }
00310
00311 explicit
00312 _Hashtable_iterator(_Hash_node<_Value, __cache>** __b)
00313 : _Hashtable_iterator_base<_Value, __cache>(*__b, __b) { }
00314
00315 reference
00316 operator*() const
00317 { return this->_M_cur_node->_M_v; }
00318
00319 pointer
00320 operator->() const
00321 { return &this->_M_cur_node->_M_v; }
00322
00323 _Hashtable_iterator&
00324 operator++()
00325 {
00326 this->_M_incr();
00327 return *this;
00328 }
00329
00330 _Hashtable_iterator
00331 operator++(int)
00332 {
00333 _Hashtable_iterator __tmp(*this);
00334 this->_M_incr();
00335 return __tmp;
00336 }
00337 };
00338
00339 template<typename _Value, bool __constant_iterators, bool __cache>
00340 struct _Hashtable_const_iterator
00341 : public _Hashtable_iterator_base<_Value, __cache>
00342 {
00343 typedef _Value value_type;
00344 typedef const _Value* pointer;
00345 typedef const _Value& reference;
00346 typedef std::ptrdiff_t difference_type;
00347 typedef std::forward_iterator_tag iterator_category;
00348
00349 _Hashtable_const_iterator()
00350 : _Hashtable_iterator_base<_Value, __cache>(0, 0) { }
00351
00352 _Hashtable_const_iterator(_Hash_node<_Value, __cache>* __p,
00353 _Hash_node<_Value, __cache>** __b)
00354 : _Hashtable_iterator_base<_Value, __cache>(__p, __b) { }
00355
00356 explicit
00357 _Hashtable_const_iterator(_Hash_node<_Value, __cache>** __b)
00358 : _Hashtable_iterator_base<_Value, __cache>(*__b, __b) { }
00359
00360 _Hashtable_const_iterator(const _Hashtable_iterator<_Value,
00361 __constant_iterators, __cache>& __x)
00362 : _Hashtable_iterator_base<_Value, __cache>(__x._M_cur_node,
00363 __x._M_cur_bucket) { }
00364
00365 reference
00366 operator*() const
00367 { return this->_M_cur_node->_M_v; }
00368
00369 pointer
00370 operator->() const
00371 { return &this->_M_cur_node->_M_v; }
00372
00373 _Hashtable_const_iterator&
00374 operator++()
00375 {
00376 this->_M_incr();
00377 return *this;
00378 }
00379
00380 _Hashtable_const_iterator
00381 operator++(int)
00382 {
00383 _Hashtable_const_iterator __tmp(*this);
00384 this->_M_incr();
00385 return __tmp;
00386 }
00387 };
00388
00389
00390
00391
00392
00393
00394
00395 struct _Mod_range_hashing
00396 {
00397 typedef std::size_t first_argument_type;
00398 typedef std::size_t second_argument_type;
00399 typedef std::size_t result_type;
00400
00401 result_type
00402 operator()(first_argument_type __num, second_argument_type __den) const
00403 { return __num % __den; }
00404 };
00405
00406
00407
00408
00409
00410
00411 struct _Default_ranged_hash { };
00412
00413
00414
00415 struct _Prime_rehash_policy
00416 {
00417 _Prime_rehash_policy(float __z = 1.0)
00418 : _M_max_load_factor(__z), _M_growth_factor(2.f), _M_next_resize(0) { }
00419
00420 float
00421 max_load_factor() const
00422 { return _M_max_load_factor; }
00423
00424
00425 std::size_t
00426 _M_next_bkt(std::size_t __n) const;
00427
00428
00429 std::size_t
00430 _M_bkt_for_elements(std::size_t __n) const;
00431
00432
00433
00434
00435
00436 std::pair<bool, std::size_t>
00437 _M_need_rehash(std::size_t __n_bkt, std::size_t __n_elt,
00438 std::size_t __n_ins) const;
00439
00440 enum { _S_n_primes = sizeof(unsigned long) != 8 ? 256 : 256 + 48 };
00441
00442 float _M_max_load_factor;
00443 float _M_growth_factor;
00444 mutable std::size_t _M_next_resize;
00445 };
00446
00447 extern const unsigned long __prime_list[];
00448
00449
00450
00451
00452
00453 inline std::size_t
00454 _Prime_rehash_policy::
00455 _M_next_bkt(std::size_t __n) const
00456 {
00457 const unsigned long* __p = __lower_bound(__prime_list, __prime_list
00458 + _S_n_primes, __n);
00459 _M_next_resize =
00460 static_cast<std::size_t>(__builtin_ceil(*__p * _M_max_load_factor));
00461 return *__p;
00462 }
00463
00464
00465
00466 inline std::size_t
00467 _Prime_rehash_policy::
00468 _M_bkt_for_elements(std::size_t __n) const
00469 {
00470 const float __min_bkts = __n / _M_max_load_factor;
00471 const unsigned long* __p = __lower_bound(__prime_list, __prime_list
00472 + _S_n_primes, __min_bkts);
00473 _M_next_resize =
00474 static_cast<std::size_t>(__builtin_ceil(*__p * _M_max_load_factor));
00475 return *__p;
00476 }
00477
00478
00479
00480
00481
00482
00483
00484
00485
00486
00487 inline std::pair<bool, std::size_t>
00488 _Prime_rehash_policy::
00489 _M_need_rehash(std::size_t __n_bkt, std::size_t __n_elt,
00490 std::size_t __n_ins) const
00491 {
00492 if (__n_elt + __n_ins > _M_next_resize)
00493 {
00494 float __min_bkts = ((float(__n_ins) + float(__n_elt))
00495 / _M_max_load_factor);
00496 if (__min_bkts > __n_bkt)
00497 {
00498 __min_bkts = std::max(__min_bkts, _M_growth_factor * __n_bkt);
00499 const unsigned long* __p =
00500 __lower_bound(__prime_list, __prime_list + _S_n_primes,
00501 __min_bkts);
00502 _M_next_resize = static_cast<std::size_t>
00503 (__builtin_ceil(*__p * _M_max_load_factor));
00504 return std::make_pair(true, *__p);
00505 }
00506 else
00507 {
00508 _M_next_resize = static_cast<std::size_t>
00509 (__builtin_ceil(__n_bkt * _M_max_load_factor));
00510 return std::make_pair(false, 0);
00511 }
00512 }
00513 else
00514 return std::make_pair(false, 0);
00515 }
00516
00517
00518
00519
00520
00521
00522
00523
00524
00525
00526
00527
00528
00529
00530
00531 template<typename _Key, typename _Value, typename _Ex, bool __unique,
00532 typename _Hashtable>
00533 struct _Map_base { };
00534
00535 template<typename _Key, typename _Pair, typename _Hashtable>
00536 struct _Map_base<_Key, _Pair, std::_Select1st<_Pair>, false, _Hashtable>
00537 {
00538 typedef typename _Pair::second_type mapped_type;
00539 };
00540
00541 template<typename _Key, typename _Pair, typename _Hashtable>
00542 struct _Map_base<_Key, _Pair, std::_Select1st<_Pair>, true, _Hashtable>
00543 {
00544 typedef typename _Pair::second_type mapped_type;
00545
00546 mapped_type&
00547 operator[](const _Key& __k);
00548
00549 #ifdef _GLIBCXX_INCLUDE_AS_CXX0X
00550
00551
00552 mapped_type&
00553 at(const _Key& __k);
00554
00555 const mapped_type&
00556 at(const _Key& __k) const;
00557 #endif
00558 };
00559
00560 template<typename _Key, typename _Pair, typename _Hashtable>
00561 typename _Map_base<_Key, _Pair, std::_Select1st<_Pair>,
00562 true, _Hashtable>::mapped_type&
00563 _Map_base<_Key, _Pair, std::_Select1st<_Pair>, true, _Hashtable>::
00564 operator[](const _Key& __k)
00565 {
00566 _Hashtable* __h = static_cast<_Hashtable*>(this);
00567 typename _Hashtable::_Hash_code_type __code = __h->_M_hash_code(__k);
00568 std::size_t __n = __h->_M_bucket_index(__k, __code,
00569 __h->_M_bucket_count);
00570
00571 typename _Hashtable::_Node* __p =
00572 __h->_M_find_node(__h->_M_buckets[__n], __k, __code);
00573 if (!__p)
00574 return __h->_M_insert_bucket(std::make_pair(__k, mapped_type()),
00575 __n, __code)->second;
00576 return (__p->_M_v).second;
00577 }
00578
00579 #ifdef _GLIBCXX_INCLUDE_AS_CXX0X
00580 template<typename _Key, typename _Pair, typename _Hashtable>
00581 typename _Map_base<_Key, _Pair, std::_Select1st<_Pair>,
00582 true, _Hashtable>::mapped_type&
00583 _Map_base<_Key, _Pair, std::_Select1st<_Pair>, true, _Hashtable>::
00584 at(const _Key& __k)
00585 {
00586 _Hashtable* __h = static_cast<_Hashtable*>(this);
00587 typename _Hashtable::_Hash_code_type __code = __h->_M_hash_code(__k);
00588 std::size_t __n = __h->_M_bucket_index(__k, __code,
00589 __h->_M_bucket_count);
00590
00591 typename _Hashtable::_Node* __p =
00592 __h->_M_find_node(__h->_M_buckets[__n], __k, __code);
00593 if (!__p)
00594 __throw_out_of_range(__N("_Map_base::at"));
00595 return (__p->_M_v).second;
00596 }
00597
00598 template<typename _Key, typename _Pair, typename _Hashtable>
00599 const typename _Map_base<_Key, _Pair, std::_Select1st<_Pair>,
00600 true, _Hashtable>::mapped_type&
00601 _Map_base<_Key, _Pair, std::_Select1st<_Pair>, true, _Hashtable>::
00602 at(const _Key& __k) const
00603 {
00604 const _Hashtable* __h = static_cast<const _Hashtable*>(this);
00605 typename _Hashtable::_Hash_code_type __code = __h->_M_hash_code(__k);
00606 std::size_t __n = __h->_M_bucket_index(__k, __code,
00607 __h->_M_bucket_count);
00608
00609 typename _Hashtable::_Node* __p =
00610 __h->_M_find_node(__h->_M_buckets[__n], __k, __code);
00611 if (!__p)
00612 __throw_out_of_range(__N("_Map_base::at"));
00613 return (__p->_M_v).second;
00614 }
00615 #endif
00616
00617
00618
00619 template<typename _RehashPolicy, typename _Hashtable>
00620 struct _Rehash_base { };
00621
00622 template<typename _Hashtable>
00623 struct _Rehash_base<_Prime_rehash_policy, _Hashtable>
00624 {
00625 float
00626 max_load_factor() const
00627 {
00628 const _Hashtable* __this = static_cast<const _Hashtable*>(this);
00629 return __this->__rehash_policy().max_load_factor();
00630 }
00631
00632 void
00633 max_load_factor(float __z)
00634 {
00635 _Hashtable* __this = static_cast<_Hashtable*>(this);
00636 __this->__rehash_policy(_Prime_rehash_policy(__z));
00637 }
00638 };
00639
00640
00641
00642
00643
00644
00645
00646
00647
00648
00649
00650
00651
00652 template<typename _Key, typename _Value,
00653 typename _ExtractKey, typename _Equal,
00654 typename _H1, typename _H2, typename _Hash,
00655 bool __cache_hash_code>
00656 struct _Hash_code_base;
00657
00658
00659
00660 template<typename _Key, typename _Value,
00661 typename _ExtractKey, typename _Equal,
00662 typename _H1, typename _H2, typename _Hash>
00663 struct _Hash_code_base<_Key, _Value, _ExtractKey, _Equal, _H1, _H2,
00664 _Hash, false>
00665 {
00666 protected:
00667 _Hash_code_base(const _ExtractKey& __ex, const _Equal& __eq,
00668 const _H1&, const _H2&, const _Hash& __h)
00669 : _M_extract(__ex), _M_eq(__eq), _M_ranged_hash(__h) { }
00670
00671 typedef void* _Hash_code_type;
00672
00673 _Hash_code_type
00674 _M_hash_code(const _Key& __key) const
00675 { return 0; }
00676
00677 std::size_t
00678 _M_bucket_index(const _Key& __k, _Hash_code_type,
00679 std::size_t __n) const
00680 { return _M_ranged_hash(__k, __n); }
00681
00682 std::size_t
00683 _M_bucket_index(const _Hash_node<_Value, false>* __p,
00684 std::size_t __n) const
00685 { return _M_ranged_hash(_M_extract(__p->_M_v), __n); }
00686
00687 bool
00688 _M_compare(const _Key& __k, _Hash_code_type,
00689 _Hash_node<_Value, false>* __n) const
00690 { return _M_eq(__k, _M_extract(__n->_M_v)); }
00691
00692 void
00693 _M_store_code(_Hash_node<_Value, false>*, _Hash_code_type) const
00694 { }
00695
00696 void
00697 _M_copy_code(_Hash_node<_Value, false>*,
00698 const _Hash_node<_Value, false>*) const
00699 { }
00700
00701 void
00702 _M_swap(_Hash_code_base& __x)
00703 {
00704 std::swap(_M_extract, __x._M_extract);
00705 std::swap(_M_eq, __x._M_eq);
00706 std::swap(_M_ranged_hash, __x._M_ranged_hash);
00707 }
00708
00709 protected:
00710 _ExtractKey _M_extract;
00711 _Equal _M_eq;
00712 _Hash _M_ranged_hash;
00713 };
00714
00715
00716
00717
00718
00719
00720
00721
00722
00723 template<typename _Key, typename _Value,
00724 typename _ExtractKey, typename _Equal,
00725 typename _H1, typename _H2, typename _Hash>
00726 struct _Hash_code_base<_Key, _Value, _ExtractKey, _Equal, _H1, _H2,
00727 _Hash, true>;
00728
00729
00730
00731
00732 template<typename _Key, typename _Value,
00733 typename _ExtractKey, typename _Equal,
00734 typename _H1, typename _H2>
00735 struct _Hash_code_base<_Key, _Value, _ExtractKey, _Equal, _H1, _H2,
00736 _Default_ranged_hash, false>
00737 {
00738 typedef _H1 hasher;
00739
00740 hasher
00741 hash_function() const
00742 { return _M_h1; }
00743
00744 protected:
00745 _Hash_code_base(const _ExtractKey& __ex, const _Equal& __eq,
00746 const _H1& __h1, const _H2& __h2,
00747 const _Default_ranged_hash&)
00748 : _M_extract(__ex), _M_eq(__eq), _M_h1(__h1), _M_h2(__h2) { }
00749
00750 typedef std::size_t _Hash_code_type;
00751
00752 _Hash_code_type
00753 _M_hash_code(const _Key& __k) const
00754 { return _M_h1(__k); }
00755
00756 std::size_t
00757 _M_bucket_index(const _Key&, _Hash_code_type __c,
00758 std::size_t __n) const
00759 { return _M_h2(__c, __n); }
00760
00761 std::size_t
00762 _M_bucket_index(const _Hash_node<_Value, false>* __p,
00763 std::size_t __n) const
00764 { return _M_h2(_M_h1(_M_extract(__p->_M_v)), __n); }
00765
00766 bool
00767 _M_compare(const _Key& __k, _Hash_code_type,
00768 _Hash_node<_Value, false>* __n) const
00769 { return _M_eq(__k, _M_extract(__n->_M_v)); }
00770
00771 void
00772 _M_store_code(_Hash_node<_Value, false>*, _Hash_code_type) const
00773 { }
00774
00775 void
00776 _M_copy_code(_Hash_node<_Value, false>*,
00777 const _Hash_node<_Value, false>*) const
00778 { }
00779
00780 void
00781 _M_swap(_Hash_code_base& __x)
00782 {
00783 std::swap(_M_extract, __x._M_extract);
00784 std::swap(_M_eq, __x._M_eq);
00785 std::swap(_M_h1, __x._M_h1);
00786 std::swap(_M_h2, __x._M_h2);
00787 }
00788
00789 protected:
00790 _ExtractKey _M_extract;
00791 _Equal _M_eq;
00792 _H1 _M_h1;
00793 _H2 _M_h2;
00794 };
00795
00796
00797
00798
00799 template<typename _Key, typename _Value,
00800 typename _ExtractKey, typename _Equal,
00801 typename _H1, typename _H2>
00802 struct _Hash_code_base<_Key, _Value, _ExtractKey, _Equal, _H1, _H2,
00803 _Default_ranged_hash, true>
00804 {
00805 typedef _H1 hasher;
00806
00807 hasher
00808 hash_function() const
00809 { return _M_h1; }
00810
00811 protected:
00812 _Hash_code_base(const _ExtractKey& __ex, const _Equal& __eq,
00813 const _H1& __h1, const _H2& __h2,
00814 const _Default_ranged_hash&)
00815 : _M_extract(__ex), _M_eq(__eq), _M_h1(__h1), _M_h2(__h2) { }
00816
00817 typedef std::size_t _Hash_code_type;
00818
00819 _Hash_code_type
00820 _M_hash_code(const _Key& __k) const
00821 { return _M_h1(__k); }
00822
00823 std::size_t
00824 _M_bucket_index(const _Key&, _Hash_code_type __c,
00825 std::size_t __n) const
00826 { return _M_h2(__c, __n); }
00827
00828 std::size_t
00829 _M_bucket_index(const _Hash_node<_Value, true>* __p,
00830 std::size_t __n) const
00831 { return _M_h2(__p->_M_hash_code, __n); }
00832
00833 bool
00834 _M_compare(const _Key& __k, _Hash_code_type __c,
00835 _Hash_node<_Value, true>* __n) const
00836 { return __c == __n->_M_hash_code && _M_eq(__k, _M_extract(__n->_M_v)); }
00837
00838 void
00839 _M_store_code(_Hash_node<_Value, true>* __n, _Hash_code_type __c) const
00840 { __n->_M_hash_code = __c; }
00841
00842 void
00843 _M_copy_code(_Hash_node<_Value, true>* __to,
00844 const _Hash_node<_Value, true>* __from) const
00845 { __to->_M_hash_code = __from->_M_hash_code; }
00846
00847 void
00848 _M_swap(_Hash_code_base& __x)
00849 {
00850 std::swap(_M_extract, __x._M_extract);
00851 std::swap(_M_eq, __x._M_eq);
00852 std::swap(_M_h1, __x._M_h1);
00853 std::swap(_M_h2, __x._M_h2);
00854 }
00855
00856 protected:
00857 _ExtractKey _M_extract;
00858 _Equal _M_eq;
00859 _H1 _M_h1;
00860 _H2 _M_h2;
00861 };
00862 }
00863
00864 _GLIBCXX_END_NAMESPACE_TR1
00865 }