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