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