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
00035
00036
00037
00038
00039
00040
00041
00042
00043
00044
00045
00046
00047
00048
00049
00050
00051
00052
00053 #include <tr1_impl/hashtable_policy.h>
00054
00055 namespace std
00056 {
00057 _GLIBCXX_BEGIN_NAMESPACE_TR1
00058
00059
00060
00061
00062
00063
00064
00065
00066
00067
00068
00069
00070
00071
00072
00073
00074
00075
00076
00077
00078
00079
00080
00081
00082
00083
00084
00085
00086
00087
00088
00089
00090
00091
00092
00093
00094
00095
00096
00097
00098
00099
00100
00101
00102
00103
00104
00105
00106
00107
00108
00109
00110
00111
00112
00113
00114
00115
00116 template<typename _Key, typename _Value, typename _Allocator,
00117 typename _ExtractKey, typename _Equal,
00118 typename _H1, typename _H2, typename _Hash,
00119 typename _RehashPolicy,
00120 bool __cache_hash_code,
00121 bool __constant_iterators,
00122 bool __unique_keys>
00123 class _Hashtable
00124 : public __detail::_Rehash_base<_RehashPolicy,
00125 _Hashtable<_Key, _Value, _Allocator,
00126 _ExtractKey,
00127 _Equal, _H1, _H2, _Hash,
00128 _RehashPolicy,
00129 __cache_hash_code,
00130 __constant_iterators,
00131 __unique_keys> >,
00132 public __detail::_Hash_code_base<_Key, _Value, _ExtractKey, _Equal,
00133 _H1, _H2, _Hash, __cache_hash_code>,
00134 public __detail::_Map_base<_Key, _Value, _ExtractKey, __unique_keys,
00135 _Hashtable<_Key, _Value, _Allocator,
00136 _ExtractKey,
00137 _Equal, _H1, _H2, _Hash,
00138 _RehashPolicy,
00139 __cache_hash_code,
00140 __constant_iterators,
00141 __unique_keys> >
00142 {
00143 public:
00144 typedef _Allocator allocator_type;
00145 typedef _Value value_type;
00146 typedef _Key key_type;
00147 typedef _Equal key_equal;
00148
00149
00150 typedef typename _Allocator::difference_type difference_type;
00151 typedef typename _Allocator::size_type size_type;
00152 typedef typename _Allocator::reference reference;
00153 typedef typename _Allocator::const_reference const_reference;
00154
00155 typedef __detail::_Node_iterator<value_type, __constant_iterators,
00156 __cache_hash_code>
00157 local_iterator;
00158 typedef __detail::_Node_const_iterator<value_type,
00159 __constant_iterators,
00160 __cache_hash_code>
00161 const_local_iterator;
00162
00163 typedef __detail::_Hashtable_iterator<value_type, __constant_iterators,
00164 __cache_hash_code>
00165 iterator;
00166 typedef __detail::_Hashtable_const_iterator<value_type,
00167 __constant_iterators,
00168 __cache_hash_code>
00169 const_iterator;
00170
00171 template<typename _Key2, typename _Value2, typename _Ex2, bool __unique2,
00172 typename _Hashtable2>
00173 friend struct __detail::_Map_base;
00174
00175 private:
00176 typedef __detail::_Hash_node<_Value, __cache_hash_code> _Node;
00177 typedef typename _Allocator::template rebind<_Node>::other
00178 _Node_allocator_type;
00179 typedef typename _Allocator::template rebind<_Node*>::other
00180 _Bucket_allocator_type;
00181
00182 typedef typename _Allocator::template rebind<_Value>::other
00183 _Value_allocator_type;
00184
00185 _Node_allocator_type _M_node_allocator;
00186 _Node** _M_buckets;
00187 size_type _M_bucket_count;
00188 size_type _M_element_count;
00189 _RehashPolicy _M_rehash_policy;
00190
00191 _Node*
00192 _M_allocate_node(const value_type& __v);
00193
00194 void
00195 _M_deallocate_node(_Node* __n);
00196
00197 void
00198 _M_deallocate_nodes(_Node**, size_type);
00199
00200 _Node**
00201 _M_allocate_buckets(size_type __n);
00202
00203 void
00204 _M_deallocate_buckets(_Node**, size_type __n);
00205
00206 public:
00207
00208 _Hashtable(size_type __bucket_hint,
00209 const _H1&, const _H2&, const _Hash&,
00210 const _Equal&, const _ExtractKey&,
00211 const allocator_type&);
00212
00213 template<typename _InputIterator>
00214 _Hashtable(_InputIterator __first, _InputIterator __last,
00215 size_type __bucket_hint,
00216 const _H1&, const _H2&, const _Hash&,
00217 const _Equal&, const _ExtractKey&,
00218 const allocator_type&);
00219
00220 _Hashtable(const _Hashtable&);
00221
00222 #ifdef _GLIBCXX_INCLUDE_AS_CXX0X
00223 _Hashtable(_Hashtable&&);
00224 #endif
00225
00226 _Hashtable&
00227 operator=(const _Hashtable&);
00228
00229 ~_Hashtable();
00230
00231 #ifdef _GLIBCXX_INCLUDE_AS_CXX0X
00232 void swap(_Hashtable&&);
00233 #else
00234 void swap(_Hashtable&);
00235 #endif
00236
00237
00238 iterator
00239 begin()
00240 {
00241 iterator __i(_M_buckets);
00242 if (!__i._M_cur_node)
00243 __i._M_incr_bucket();
00244 return __i;
00245 }
00246
00247 const_iterator
00248 begin() const
00249 {
00250 const_iterator __i(_M_buckets);
00251 if (!__i._M_cur_node)
00252 __i._M_incr_bucket();
00253 return __i;
00254 }
00255
00256 iterator
00257 end()
00258 { return iterator(_M_buckets + _M_bucket_count); }
00259
00260 const_iterator
00261 end() const
00262 { return const_iterator(_M_buckets + _M_bucket_count); }
00263
00264 #ifdef _GLIBCXX_INCLUDE_AS_CXX0X
00265 const_iterator
00266 cbegin() const
00267 {
00268 const_iterator __i(_M_buckets);
00269 if (!__i._M_cur_node)
00270 __i._M_incr_bucket();
00271 return __i;
00272 }
00273
00274 const_iterator
00275 cend() const
00276 { return const_iterator(_M_buckets + _M_bucket_count); }
00277 #endif
00278
00279 size_type
00280 size() const
00281 { return _M_element_count; }
00282
00283 bool
00284 empty() const
00285 { return size() == 0; }
00286
00287 allocator_type
00288 get_allocator() const
00289 { return allocator_type(_M_node_allocator); }
00290
00291 _Value_allocator_type
00292 _M_get_Value_allocator() const
00293 { return _Value_allocator_type(_M_node_allocator); }
00294
00295 size_type
00296 max_size() const
00297 { return _M_get_Value_allocator().max_size(); }
00298
00299
00300 key_equal
00301 key_eq() const
00302 { return this->_M_eq; }
00303
00304
00305
00306
00307 size_type
00308 bucket_count() const
00309 { return _M_bucket_count; }
00310
00311 size_type
00312 max_bucket_count() const
00313 { return max_size(); }
00314
00315 size_type
00316 bucket_size(size_type __n) const
00317 { return std::distance(begin(__n), end(__n)); }
00318
00319 size_type
00320 bucket(const key_type& __k) const
00321 {
00322 return this->_M_bucket_index(__k, this->_M_hash_code(__k),
00323 bucket_count());
00324 }
00325
00326 local_iterator
00327 begin(size_type __n)
00328 { return local_iterator(_M_buckets[__n]); }
00329
00330 local_iterator
00331 end(size_type)
00332 { return local_iterator(0); }
00333
00334 const_local_iterator
00335 begin(size_type __n) const
00336 { return const_local_iterator(_M_buckets[__n]); }
00337
00338 const_local_iterator
00339 end(size_type) const
00340 { return const_local_iterator(0); }
00341
00342 float
00343 load_factor() const
00344 {
00345 return static_cast<float>(size()) / static_cast<float>(bucket_count());
00346 }
00347
00348
00349
00350
00351
00352 const _RehashPolicy&
00353 __rehash_policy() const
00354 { return _M_rehash_policy; }
00355
00356 void
00357 __rehash_policy(const _RehashPolicy&);
00358
00359
00360 iterator
00361 find(const key_type& __k);
00362
00363 const_iterator
00364 find(const key_type& __k) const;
00365
00366 size_type
00367 count(const key_type& __k) const;
00368
00369 std::pair<iterator, iterator>
00370 equal_range(const key_type& __k);
00371
00372 std::pair<const_iterator, const_iterator>
00373 equal_range(const key_type& __k) const;
00374
00375 private:
00376
00377
00378
00379
00380 typedef typename __gnu_cxx::__conditional_type<__unique_keys,
00381 std::pair<iterator, bool>, iterator>::__type
00382 _Insert_Return_Type;
00383
00384 typedef typename __gnu_cxx::__conditional_type<__unique_keys,
00385 std::_Select1st<_Insert_Return_Type>,
00386 std::_Identity<_Insert_Return_Type>
00387 >::__type
00388 _Insert_Conv_Type;
00389
00390 _Node*
00391 _M_find_node(_Node*, const key_type&,
00392 typename _Hashtable::_Hash_code_type) const;
00393
00394 iterator
00395 _M_insert_bucket(const value_type&, size_type,
00396 typename _Hashtable::_Hash_code_type);
00397
00398 std::pair<iterator, bool>
00399 _M_insert(const value_type&, std::_GLIBCXX_TR1 true_type);
00400
00401 iterator
00402 _M_insert(const value_type&, std::_GLIBCXX_TR1 false_type);
00403
00404 void
00405 _M_erase_node(_Node*, _Node**);
00406
00407 public:
00408
00409 _Insert_Return_Type
00410 insert(const value_type& __v)
00411 { return _M_insert(__v, std::_GLIBCXX_TR1 integral_constant<bool,
00412 __unique_keys>()); }
00413
00414 iterator
00415 insert(iterator, const value_type& __v)
00416 { return iterator(_Insert_Conv_Type()(this->insert(__v))); }
00417
00418 const_iterator
00419 insert(const_iterator, const value_type& __v)
00420 { return const_iterator(_Insert_Conv_Type()(this->insert(__v))); }
00421
00422 template<typename _InputIterator>
00423 void
00424 insert(_InputIterator __first, _InputIterator __last);
00425
00426 iterator
00427 erase(iterator);
00428
00429 const_iterator
00430 erase(const_iterator);
00431
00432 size_type
00433 erase(const key_type&);
00434
00435 iterator
00436 erase(iterator, iterator);
00437
00438 const_iterator
00439 erase(const_iterator, const_iterator);
00440
00441 void
00442 clear();
00443
00444
00445 void rehash(size_type __n);
00446
00447 private:
00448
00449 void _M_rehash(size_type __n);
00450 };
00451
00452
00453
00454 template<typename _Key, typename _Value,
00455 typename _Allocator, typename _ExtractKey, typename _Equal,
00456 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
00457 bool __chc, bool __cit, bool __uk>
00458 typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
00459 _H1, _H2, _Hash, _RehashPolicy,
00460 __chc, __cit, __uk>::_Node*
00461 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
00462 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
00463 _M_allocate_node(const value_type& __v)
00464 {
00465 _Node* __n = _M_node_allocator.allocate(1);
00466 try
00467 {
00468 _M_get_Value_allocator().construct(&__n->_M_v, __v);
00469 __n->_M_next = 0;
00470 return __n;
00471 }
00472 catch(...)
00473 {
00474 _M_node_allocator.deallocate(__n, 1);
00475 __throw_exception_again;
00476 }
00477 }
00478
00479 template<typename _Key, typename _Value,
00480 typename _Allocator, typename _ExtractKey, typename _Equal,
00481 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
00482 bool __chc, bool __cit, bool __uk>
00483 void
00484 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
00485 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
00486 _M_deallocate_node(_Node* __n)
00487 {
00488 _M_get_Value_allocator().destroy(&__n->_M_v);
00489 _M_node_allocator.deallocate(__n, 1);
00490 }
00491
00492 template<typename _Key, typename _Value,
00493 typename _Allocator, typename _ExtractKey, typename _Equal,
00494 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
00495 bool __chc, bool __cit, bool __uk>
00496 void
00497 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
00498 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
00499 _M_deallocate_nodes(_Node** __array, size_type __n)
00500 {
00501 for (size_type __i = 0; __i < __n; ++__i)
00502 {
00503 _Node* __p = __array[__i];
00504 while (__p)
00505 {
00506 _Node* __tmp = __p;
00507 __p = __p->_M_next;
00508 _M_deallocate_node(__tmp);
00509 }
00510 __array[__i] = 0;
00511 }
00512 }
00513
00514 template<typename _Key, typename _Value,
00515 typename _Allocator, typename _ExtractKey, typename _Equal,
00516 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
00517 bool __chc, bool __cit, bool __uk>
00518 typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
00519 _H1, _H2, _Hash, _RehashPolicy,
00520 __chc, __cit, __uk>::_Node**
00521 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
00522 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
00523 _M_allocate_buckets(size_type __n)
00524 {
00525 _Bucket_allocator_type __alloc(_M_node_allocator);
00526
00527
00528
00529 _Node** __p = __alloc.allocate(__n + 1);
00530 std::fill(__p, __p + __n, (_Node*) 0);
00531 __p[__n] = reinterpret_cast<_Node*>(0x1000);
00532 return __p;
00533 }
00534
00535 template<typename _Key, typename _Value,
00536 typename _Allocator, typename _ExtractKey, typename _Equal,
00537 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
00538 bool __chc, bool __cit, bool __uk>
00539 void
00540 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
00541 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
00542 _M_deallocate_buckets(_Node** __p, size_type __n)
00543 {
00544 _Bucket_allocator_type __alloc(_M_node_allocator);
00545 __alloc.deallocate(__p, __n + 1);
00546 }
00547
00548 template<typename _Key, typename _Value,
00549 typename _Allocator, typename _ExtractKey, typename _Equal,
00550 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
00551 bool __chc, bool __cit, bool __uk>
00552 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
00553 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
00554 _Hashtable(size_type __bucket_hint,
00555 const _H1& __h1, const _H2& __h2, const _Hash& __h,
00556 const _Equal& __eq, const _ExtractKey& __exk,
00557 const allocator_type& __a)
00558 : __detail::_Rehash_base<_RehashPolicy, _Hashtable>(),
00559 __detail::_Hash_code_base<_Key, _Value, _ExtractKey, _Equal,
00560 _H1, _H2, _Hash, __chc>(__exk, __eq,
00561 __h1, __h2, __h),
00562 __detail::_Map_base<_Key, _Value, _ExtractKey, __uk, _Hashtable>(),
00563 _M_node_allocator(__a),
00564 _M_bucket_count(0),
00565 _M_element_count(0),
00566 _M_rehash_policy()
00567 {
00568 _M_bucket_count = _M_rehash_policy._M_next_bkt(__bucket_hint);
00569 _M_buckets = _M_allocate_buckets(_M_bucket_count);
00570 }
00571
00572 template<typename _Key, typename _Value,
00573 typename _Allocator, typename _ExtractKey, typename _Equal,
00574 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
00575 bool __chc, bool __cit, bool __uk>
00576 template<typename _InputIterator>
00577 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
00578 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
00579 _Hashtable(_InputIterator __f, _InputIterator __l,
00580 size_type __bucket_hint,
00581 const _H1& __h1, const _H2& __h2, const _Hash& __h,
00582 const _Equal& __eq, const _ExtractKey& __exk,
00583 const allocator_type& __a)
00584 : __detail::_Rehash_base<_RehashPolicy, _Hashtable>(),
00585 __detail::_Hash_code_base<_Key, _Value, _ExtractKey, _Equal,
00586 _H1, _H2, _Hash, __chc>(__exk, __eq,
00587 __h1, __h2, __h),
00588 __detail::_Map_base<_Key, _Value, _ExtractKey, __uk, _Hashtable>(),
00589 _M_node_allocator(__a),
00590 _M_bucket_count(0),
00591 _M_element_count(0),
00592 _M_rehash_policy()
00593 {
00594 _M_bucket_count = std::max(_M_rehash_policy._M_next_bkt(__bucket_hint),
00595 _M_rehash_policy.
00596 _M_bkt_for_elements(__detail::
00597 __distance_fw(__f,
00598 __l)));
00599 _M_buckets = _M_allocate_buckets(_M_bucket_count);
00600 try
00601 {
00602 for (; __f != __l; ++__f)
00603 this->insert(*__f);
00604 }
00605 catch(...)
00606 {
00607 clear();
00608 _M_deallocate_buckets(_M_buckets, _M_bucket_count);
00609 __throw_exception_again;
00610 }
00611 }
00612
00613 template<typename _Key, typename _Value,
00614 typename _Allocator, typename _ExtractKey, typename _Equal,
00615 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
00616 bool __chc, bool __cit, bool __uk>
00617 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
00618 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
00619 _Hashtable(const _Hashtable& __ht)
00620 : __detail::_Rehash_base<_RehashPolicy, _Hashtable>(__ht),
00621 __detail::_Hash_code_base<_Key, _Value, _ExtractKey, _Equal,
00622 _H1, _H2, _Hash, __chc>(__ht),
00623 __detail::_Map_base<_Key, _Value, _ExtractKey, __uk, _Hashtable>(__ht),
00624 _M_node_allocator(__ht._M_node_allocator),
00625 _M_bucket_count(__ht._M_bucket_count),
00626 _M_element_count(__ht._M_element_count),
00627 _M_rehash_policy(__ht._M_rehash_policy)
00628 {
00629 _M_buckets = _M_allocate_buckets(_M_bucket_count);
00630 try
00631 {
00632 for (size_type __i = 0; __i < __ht._M_bucket_count; ++__i)
00633 {
00634 _Node* __n = __ht._M_buckets[__i];
00635 _Node** __tail = _M_buckets + __i;
00636 while (__n)
00637 {
00638 *__tail = _M_allocate_node(__n->_M_v);
00639 this->_M_copy_code(*__tail, __n);
00640 __tail = &((*__tail)->_M_next);
00641 __n = __n->_M_next;
00642 }
00643 }
00644 }
00645 catch(...)
00646 {
00647 clear();
00648 _M_deallocate_buckets(_M_buckets, _M_bucket_count);
00649 __throw_exception_again;
00650 }
00651 }
00652
00653 #ifdef _GLIBCXX_INCLUDE_AS_CXX0X
00654 template<typename _Key, typename _Value,
00655 typename _Allocator, typename _ExtractKey, typename _Equal,
00656 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
00657 bool __chc, bool __cit, bool __uk>
00658 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
00659 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
00660 _Hashtable(_Hashtable&& __ht)
00661 : __detail::_Rehash_base<_RehashPolicy, _Hashtable>(__ht),
00662 __detail::_Hash_code_base<_Key, _Value, _ExtractKey, _Equal,
00663 _H1, _H2, _Hash, __chc>(__ht),
00664 __detail::_Map_base<_Key, _Value, _ExtractKey, __uk, _Hashtable>(__ht),
00665 _M_node_allocator(__ht._M_node_allocator),
00666 _M_bucket_count(__ht._M_bucket_count),
00667 _M_element_count(__ht._M_element_count),
00668 _M_rehash_policy(__ht._M_rehash_policy),
00669 _M_buckets(__ht._M_buckets)
00670 {
00671 size_type __n_bkt = __ht._M_rehash_policy._M_next_bkt(0);
00672 __ht._M_buckets = __ht._M_allocate_buckets(__n_bkt);
00673 __ht._M_bucket_count = __n_bkt;
00674 __ht._M_element_count = 0;
00675 __ht._M_rehash_policy = _RehashPolicy();
00676 }
00677 #endif
00678
00679 template<typename _Key, typename _Value,
00680 typename _Allocator, typename _ExtractKey, typename _Equal,
00681 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
00682 bool __chc, bool __cit, bool __uk>
00683 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
00684 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>&
00685 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
00686 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
00687 operator=(const _Hashtable& __ht)
00688 {
00689 _Hashtable __tmp(__ht);
00690 this->swap(__tmp);
00691 return *this;
00692 }
00693
00694 template<typename _Key, typename _Value,
00695 typename _Allocator, typename _ExtractKey, typename _Equal,
00696 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
00697 bool __chc, bool __cit, bool __uk>
00698 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
00699 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
00700 ~_Hashtable()
00701 {
00702 clear();
00703 _M_deallocate_buckets(_M_buckets, _M_bucket_count);
00704 }
00705
00706 template<typename _Key, typename _Value,
00707 typename _Allocator, typename _ExtractKey, typename _Equal,
00708 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
00709 bool __chc, bool __cit, bool __uk>
00710 void
00711 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
00712 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
00713 #ifdef _GLIBCXX_INCLUDE_AS_CXX0X
00714 swap(_Hashtable&& __x)
00715 #else
00716 swap(_Hashtable& __x)
00717 #endif
00718 {
00719
00720
00721
00722 __detail::_Hash_code_base<_Key, _Value, _ExtractKey, _Equal,
00723 _H1, _H2, _Hash, __chc>::_M_swap(__x);
00724
00725
00726
00727 std::__alloc_swap<_Node_allocator_type>::_S_do_it(_M_node_allocator,
00728 __x._M_node_allocator);
00729
00730 std::swap(_M_rehash_policy, __x._M_rehash_policy);
00731 std::swap(_M_buckets, __x._M_buckets);
00732 std::swap(_M_bucket_count, __x._M_bucket_count);
00733 std::swap(_M_element_count, __x._M_element_count);
00734 }
00735
00736 template<typename _Key, typename _Value,
00737 typename _Allocator, typename _ExtractKey, typename _Equal,
00738 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
00739 bool __chc, bool __cit, bool __uk>
00740 void
00741 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
00742 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
00743 __rehash_policy(const _RehashPolicy& __pol)
00744 {
00745 _M_rehash_policy = __pol;
00746 size_type __n_bkt = __pol._M_bkt_for_elements(_M_element_count);
00747 if (__n_bkt > _M_bucket_count)
00748 _M_rehash(__n_bkt);
00749 }
00750
00751 template<typename _Key, typename _Value,
00752 typename _Allocator, typename _ExtractKey, typename _Equal,
00753 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
00754 bool __chc, bool __cit, bool __uk>
00755 typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
00756 _H1, _H2, _Hash, _RehashPolicy,
00757 __chc, __cit, __uk>::iterator
00758 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
00759 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
00760 find(const key_type& __k)
00761 {
00762 typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k);
00763 std::size_t __n = this->_M_bucket_index(__k, __code, _M_bucket_count);
00764 _Node* __p = _M_find_node(_M_buckets[__n], __k, __code);
00765 return __p ? iterator(__p, _M_buckets + __n) : this->end();
00766 }
00767
00768 template<typename _Key, typename _Value,
00769 typename _Allocator, typename _ExtractKey, typename _Equal,
00770 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
00771 bool __chc, bool __cit, bool __uk>
00772 typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
00773 _H1, _H2, _Hash, _RehashPolicy,
00774 __chc, __cit, __uk>::const_iterator
00775 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
00776 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
00777 find(const key_type& __k) const
00778 {
00779 typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k);
00780 std::size_t __n = this->_M_bucket_index(__k, __code, _M_bucket_count);
00781 _Node* __p = _M_find_node(_M_buckets[__n], __k, __code);
00782 return __p ? const_iterator(__p, _M_buckets + __n) : this->end();
00783 }
00784
00785 template<typename _Key, typename _Value,
00786 typename _Allocator, typename _ExtractKey, typename _Equal,
00787 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
00788 bool __chc, bool __cit, bool __uk>
00789 typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
00790 _H1, _H2, _Hash, _RehashPolicy,
00791 __chc, __cit, __uk>::size_type
00792 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
00793 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
00794 count(const key_type& __k) const
00795 {
00796 typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k);
00797 std::size_t __n = this->_M_bucket_index(__k, __code, _M_bucket_count);
00798 std::size_t __result = 0;
00799 for (_Node* __p = _M_buckets[__n]; __p; __p = __p->_M_next)
00800 if (this->_M_compare(__k, __code, __p))
00801 ++__result;
00802 return __result;
00803 }
00804
00805 template<typename _Key, typename _Value,
00806 typename _Allocator, typename _ExtractKey, typename _Equal,
00807 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
00808 bool __chc, bool __cit, bool __uk>
00809 std::pair<typename _Hashtable<_Key, _Value, _Allocator,
00810 _ExtractKey, _Equal, _H1,
00811 _H2, _Hash, _RehashPolicy,
00812 __chc, __cit, __uk>::iterator,
00813 typename _Hashtable<_Key, _Value, _Allocator,
00814 _ExtractKey, _Equal, _H1,
00815 _H2, _Hash, _RehashPolicy,
00816 __chc, __cit, __uk>::iterator>
00817 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
00818 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
00819 equal_range(const key_type& __k)
00820 {
00821 typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k);
00822 std::size_t __n = this->_M_bucket_index(__k, __code, _M_bucket_count);
00823 _Node** __head = _M_buckets + __n;
00824 _Node* __p = _M_find_node(*__head, __k, __code);
00825
00826 if (__p)
00827 {
00828 _Node* __p1 = __p->_M_next;
00829 for (; __p1; __p1 = __p1->_M_next)
00830 if (!this->_M_compare(__k, __code, __p1))
00831 break;
00832
00833 iterator __first(__p, __head);
00834 iterator __last(__p1, __head);
00835 if (!__p1)
00836 __last._M_incr_bucket();
00837 return std::make_pair(__first, __last);
00838 }
00839 else
00840 return std::make_pair(this->end(), this->end());
00841 }
00842
00843 template<typename _Key, typename _Value,
00844 typename _Allocator, typename _ExtractKey, typename _Equal,
00845 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
00846 bool __chc, bool __cit, bool __uk>
00847 std::pair<typename _Hashtable<_Key, _Value, _Allocator,
00848 _ExtractKey, _Equal, _H1,
00849 _H2, _Hash, _RehashPolicy,
00850 __chc, __cit, __uk>::const_iterator,
00851 typename _Hashtable<_Key, _Value, _Allocator,
00852 _ExtractKey, _Equal, _H1,
00853 _H2, _Hash, _RehashPolicy,
00854 __chc, __cit, __uk>::const_iterator>
00855 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
00856 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
00857 equal_range(const key_type& __k) const
00858 {
00859 typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k);
00860 std::size_t __n = this->_M_bucket_index(__k, __code, _M_bucket_count);
00861 _Node** __head = _M_buckets + __n;
00862 _Node* __p = _M_find_node(*__head, __k, __code);
00863
00864 if (__p)
00865 {
00866 _Node* __p1 = __p->_M_next;
00867 for (; __p1; __p1 = __p1->_M_next)
00868 if (!this->_M_compare(__k, __code, __p1))
00869 break;
00870
00871 const_iterator __first(__p, __head);
00872 const_iterator __last(__p1, __head);
00873 if (!__p1)
00874 __last._M_incr_bucket();
00875 return std::make_pair(__first, __last);
00876 }
00877 else
00878 return std::make_pair(this->end(), this->end());
00879 }
00880
00881
00882
00883 template<typename _Key, typename _Value,
00884 typename _Allocator, typename _ExtractKey, typename _Equal,
00885 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
00886 bool __chc, bool __cit, bool __uk>
00887 typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey,
00888 _Equal, _H1, _H2, _Hash, _RehashPolicy,
00889 __chc, __cit, __uk>::_Node*
00890 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
00891 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
00892 _M_find_node(_Node* __p, const key_type& __k,
00893 typename _Hashtable::_Hash_code_type __code) const
00894 {
00895 for (; __p; __p = __p->_M_next)
00896 if (this->_M_compare(__k, __code, __p))
00897 return __p;
00898 return false;
00899 }
00900
00901
00902 template<typename _Key, typename _Value,
00903 typename _Allocator, typename _ExtractKey, typename _Equal,
00904 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
00905 bool __chc, bool __cit, bool __uk>
00906 typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
00907 _H1, _H2, _Hash, _RehashPolicy,
00908 __chc, __cit, __uk>::iterator
00909 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
00910 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
00911 _M_insert_bucket(const value_type& __v, size_type __n,
00912 typename _Hashtable::_Hash_code_type __code)
00913 {
00914 std::pair<bool, std::size_t> __do_rehash
00915 = _M_rehash_policy._M_need_rehash(_M_bucket_count,
00916 _M_element_count, 1);
00917
00918
00919
00920 _Node* __new_node = _M_allocate_node(__v);
00921
00922 try
00923 {
00924 if (__do_rehash.first)
00925 {
00926 const key_type& __k = this->_M_extract(__v);
00927 __n = this->_M_bucket_index(__k, __code, __do_rehash.second);
00928 _M_rehash(__do_rehash.second);
00929 }
00930
00931 __new_node->_M_next = _M_buckets[__n];
00932 this->_M_store_code(__new_node, __code);
00933 _M_buckets[__n] = __new_node;
00934 ++_M_element_count;
00935 return iterator(__new_node, _M_buckets + __n);
00936 }
00937 catch(...)
00938 {
00939 _M_deallocate_node(__new_node);
00940 __throw_exception_again;
00941 }
00942 }
00943
00944
00945 template<typename _Key, typename _Value,
00946 typename _Allocator, typename _ExtractKey, typename _Equal,
00947 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
00948 bool __chc, bool __cit, bool __uk>
00949 std::pair<typename _Hashtable<_Key, _Value, _Allocator,
00950 _ExtractKey, _Equal, _H1,
00951 _H2, _Hash, _RehashPolicy,
00952 __chc, __cit, __uk>::iterator, bool>
00953 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
00954 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
00955 _M_insert(const value_type& __v, std::_GLIBCXX_TR1 true_type)
00956 {
00957 const key_type& __k = this->_M_extract(__v);
00958 typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k);
00959 size_type __n = this->_M_bucket_index(__k, __code, _M_bucket_count);
00960
00961 if (_Node* __p = _M_find_node(_M_buckets[__n], __k, __code))
00962 return std::make_pair(iterator(__p, _M_buckets + __n), false);
00963 return std::make_pair(_M_insert_bucket(__v, __n, __code), true);
00964 }
00965
00966
00967 template<typename _Key, typename _Value,
00968 typename _Allocator, typename _ExtractKey, typename _Equal,
00969 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
00970 bool __chc, bool __cit, bool __uk>
00971 typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
00972 _H1, _H2, _Hash, _RehashPolicy,
00973 __chc, __cit, __uk>::iterator
00974 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
00975 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
00976 _M_insert(const value_type& __v, std::_GLIBCXX_TR1 false_type)
00977 {
00978 std::pair<bool, std::size_t> __do_rehash
00979 = _M_rehash_policy._M_need_rehash(_M_bucket_count,
00980 _M_element_count, 1);
00981 if (__do_rehash.first)
00982 _M_rehash(__do_rehash.second);
00983
00984 const key_type& __k = this->_M_extract(__v);
00985 typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k);
00986 size_type __n = this->_M_bucket_index(__k, __code, _M_bucket_count);
00987
00988
00989 _Node* __prev = _M_find_node(_M_buckets[__n], __k, __code);
00990 _Node* __new_node = _M_allocate_node(__v);
00991
00992 if (__prev)
00993 {
00994 __new_node->_M_next = __prev->_M_next;
00995 __prev->_M_next = __new_node;
00996 }
00997 else
00998 {
00999 __new_node->_M_next = _M_buckets[__n];
01000 _M_buckets[__n] = __new_node;
01001 }
01002 this->_M_store_code(__new_node, __code);
01003
01004 ++_M_element_count;
01005 return iterator(__new_node, _M_buckets + __n);
01006 }
01007
01008
01009 template<typename _Key, typename _Value,
01010 typename _Allocator, typename _ExtractKey, typename _Equal,
01011 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
01012 bool __chc, bool __cit, bool __uk>
01013 void
01014 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
01015 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
01016 _M_erase_node(_Node* __p, _Node** __b)
01017 {
01018 _Node* __cur = *__b;
01019 if (__cur == __p)
01020 *__b = __cur->_M_next;
01021 else
01022 {
01023 _Node* __next = __cur->_M_next;
01024 while (__next != __p)
01025 {
01026 __cur = __next;
01027 __next = __cur->_M_next;
01028 }
01029 __cur->_M_next = __next->_M_next;
01030 }
01031
01032 _M_deallocate_node(__p);
01033 --_M_element_count;
01034 }
01035
01036 template<typename _Key, typename _Value,
01037 typename _Allocator, typename _ExtractKey, typename _Equal,
01038 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
01039 bool __chc, bool __cit, bool __uk>
01040 template<typename _InputIterator>
01041 void
01042 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
01043 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
01044 insert(_InputIterator __first, _InputIterator __last)
01045 {
01046 size_type __n_elt = __detail::__distance_fw(__first, __last);
01047 std::pair<bool, std::size_t> __do_rehash
01048 = _M_rehash_policy._M_need_rehash(_M_bucket_count,
01049 _M_element_count, __n_elt);
01050 if (__do_rehash.first)
01051 _M_rehash(__do_rehash.second);
01052
01053 for (; __first != __last; ++__first)
01054 this->insert(*__first);
01055 }
01056
01057 template<typename _Key, typename _Value,
01058 typename _Allocator, typename _ExtractKey, typename _Equal,
01059 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
01060 bool __chc, bool __cit, bool __uk>
01061 typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
01062 _H1, _H2, _Hash, _RehashPolicy,
01063 __chc, __cit, __uk>::iterator
01064 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
01065 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
01066 erase(iterator __it)
01067 {
01068 iterator __result = __it;
01069 ++__result;
01070 _M_erase_node(__it._M_cur_node, __it._M_cur_bucket);
01071 return __result;
01072 }
01073
01074 template<typename _Key, typename _Value,
01075 typename _Allocator, typename _ExtractKey, typename _Equal,
01076 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
01077 bool __chc, bool __cit, bool __uk>
01078 typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
01079 _H1, _H2, _Hash, _RehashPolicy,
01080 __chc, __cit, __uk>::const_iterator
01081 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
01082 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
01083 erase(const_iterator __it)
01084 {
01085 const_iterator __result = __it;
01086 ++__result;
01087 _M_erase_node(__it._M_cur_node, __it._M_cur_bucket);
01088 return __result;
01089 }
01090
01091 template<typename _Key, typename _Value,
01092 typename _Allocator, typename _ExtractKey, typename _Equal,
01093 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
01094 bool __chc, bool __cit, bool __uk>
01095 typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
01096 _H1, _H2, _Hash, _RehashPolicy,
01097 __chc, __cit, __uk>::size_type
01098 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
01099 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
01100 erase(const key_type& __k)
01101 {
01102 typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k);
01103 std::size_t __n = this->_M_bucket_index(__k, __code, _M_bucket_count);
01104 size_type __result = 0;
01105
01106 _Node** __slot = _M_buckets + __n;
01107 while (*__slot && !this->_M_compare(__k, __code, *__slot))
01108 __slot = &((*__slot)->_M_next);
01109
01110 _Node** __saved_slot = 0;
01111 while (*__slot && this->_M_compare(__k, __code, *__slot))
01112 {
01113
01114
01115
01116 if (&this->_M_extract((*__slot)->_M_v) != &__k)
01117 {
01118 _Node* __p = *__slot;
01119 *__slot = __p->_M_next;
01120 _M_deallocate_node(__p);
01121 --_M_element_count;
01122 ++__result;
01123 }
01124 else
01125 {
01126 __saved_slot = __slot;
01127 __slot = &((*__slot)->_M_next);
01128 }
01129 }
01130
01131 if (__saved_slot)
01132 {
01133 _Node* __p = *__saved_slot;
01134 *__saved_slot = __p->_M_next;
01135 _M_deallocate_node(__p);
01136 --_M_element_count;
01137 ++__result;
01138 }
01139
01140 return __result;
01141 }
01142
01143
01144
01145
01146 template<typename _Key, typename _Value,
01147 typename _Allocator, typename _ExtractKey, typename _Equal,
01148 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
01149 bool __chc, bool __cit, bool __uk>
01150 typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
01151 _H1, _H2, _Hash, _RehashPolicy,
01152 __chc, __cit, __uk>::iterator
01153 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
01154 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
01155 erase(iterator __first, iterator __last)
01156 {
01157 while (__first != __last)
01158 __first = this->erase(__first);
01159 return __last;
01160 }
01161
01162 template<typename _Key, typename _Value,
01163 typename _Allocator, typename _ExtractKey, typename _Equal,
01164 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
01165 bool __chc, bool __cit, bool __uk>
01166 typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
01167 _H1, _H2, _Hash, _RehashPolicy,
01168 __chc, __cit, __uk>::const_iterator
01169 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
01170 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
01171 erase(const_iterator __first, const_iterator __last)
01172 {
01173 while (__first != __last)
01174 __first = this->erase(__first);
01175 return __last;
01176 }
01177
01178 template<typename _Key, typename _Value,
01179 typename _Allocator, typename _ExtractKey, typename _Equal,
01180 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
01181 bool __chc, bool __cit, bool __uk>
01182 void
01183 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
01184 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
01185 clear()
01186 {
01187 _M_deallocate_nodes(_M_buckets, _M_bucket_count);
01188 _M_element_count = 0;
01189 }
01190
01191 template<typename _Key, typename _Value,
01192 typename _Allocator, typename _ExtractKey, typename _Equal,
01193 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
01194 bool __chc, bool __cit, bool __uk>
01195 void
01196 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
01197 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
01198 rehash(size_type __n)
01199 {
01200 _M_rehash(std::max(_M_rehash_policy._M_next_bkt(__n),
01201 _M_rehash_policy._M_bkt_for_elements(_M_element_count
01202 + 1)));
01203 }
01204
01205 template<typename _Key, typename _Value,
01206 typename _Allocator, typename _ExtractKey, typename _Equal,
01207 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
01208 bool __chc, bool __cit, bool __uk>
01209 void
01210 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
01211 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
01212 _M_rehash(size_type __n)
01213 {
01214 _Node** __new_array = _M_allocate_buckets(__n);
01215 try
01216 {
01217 for (size_type __i = 0; __i < _M_bucket_count; ++__i)
01218 while (_Node* __p = _M_buckets[__i])
01219 {
01220 std::size_t __new_index = this->_M_bucket_index(__p, __n);
01221 _M_buckets[__i] = __p->_M_next;
01222 __p->_M_next = __new_array[__new_index];
01223 __new_array[__new_index] = __p;
01224 }
01225 _M_deallocate_buckets(_M_buckets, _M_bucket_count);
01226 _M_bucket_count = __n;
01227 _M_buckets = __new_array;
01228 }
01229 catch(...)
01230 {
01231
01232
01233
01234
01235 _M_deallocate_nodes(__new_array, __n);
01236 _M_deallocate_buckets(__new_array, __n);
01237 _M_deallocate_nodes(_M_buckets, _M_bucket_count);
01238 _M_element_count = 0;
01239 __throw_exception_again;
01240 }
01241 }
01242
01243 _GLIBCXX_END_NAMESPACE_TR1
01244 }