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