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