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