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