libstdc++
|
00001 // Internal header for TR1 unordered_set and unordered_map -*- C++ -*- 00002 00003 // Copyright (C) 2007, 2008, 2009 Free Software Foundation, Inc. 00004 // 00005 // This file is part of the GNU ISO C++ Library. This library is free 00006 // software; you can redistribute it and/or modify it under the 00007 // terms of the GNU General Public License as published by the 00008 // Free Software Foundation; either version 3, or (at your option) 00009 // any later version. 00010 00011 // This library is distributed in the hope that it will be useful, 00012 // but WITHOUT ANY WARRANTY; without even the implied warranty of 00013 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 00014 // GNU General Public License for more details. 00015 00016 // Under Section 7 of GPL version 3, you are granted additional 00017 // permissions described in the GCC Runtime Library Exception, version 00018 // 3.1, as published by the Free Software Foundation. 00019 00020 // You should have received a copy of the GNU General Public License and 00021 // a copy of the GCC Runtime Library Exception along with this program; 00022 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see 00023 // <http://www.gnu.org/licenses/>. 00024 00025 /** @file tr1_impl/hashtable 00026 * This is an internal header file, included by other library headers. 00027 * You should not attempt to use it directly. 00028 */ 00029 00030 // This header file defines std::tr1::hashtable, which is used to 00031 // implement std::tr1::unordered_set, std::tr1::unordered_map, 00032 // std::tr1::unordered_multiset, and std::tr1::unordered_multimap. 00033 // hashtable has many template parameters, partly to accommodate 00034 // the differences between those four classes and partly to 00035 // accommodate policy choices that go beyond TR1 specifications. 00036 00037 // Class template hashtable attempts to encapsulate all reasonable 00038 // variation among hash tables that use chaining. It does not handle 00039 // open addressing. 00040 00041 // References: 00042 // M. Austern, "A Proposal to Add Hash Tables to the Standard 00043 // Library (revision 4)," WG21 Document N1456=03-0039, 2003. 00044 // D. E. Knuth, The Art of Computer Programming, v. 3, Sorting and Searching. 00045 // A. Tavori and V. Dreizin, "Policy-Based Data Structures", 2004. 00046 // http://gcc.gnu.org/onlinedocs/libstdc++/ext/pb_ds/index.html 00047 00048 #include <tr1_impl/hashtable_policy.h> 00049 00050 namespace std 00051 { 00052 _GLIBCXX_BEGIN_NAMESPACE_TR1 00053 00054 // Class template _Hashtable, class definition. 00055 00056 // Meaning of class template _Hashtable's template parameters 00057 00058 // _Key and _Value: arbitrary CopyConstructible types. 00059 00060 // _Allocator: an allocator type ([lib.allocator.requirements]) whose 00061 // value type is Value. As a conforming extension, we allow for 00062 // value type != Value. 00063 00064 // _ExtractKey: function object that takes a object of type Value 00065 // and returns a value of type _Key. 00066 00067 // _Equal: function object that takes two objects of type k and returns 00068 // a bool-like value that is true if the two objects are considered equal. 00069 00070 // _H1: the hash function. A unary function object with argument type 00071 // Key and result type size_t. Return values should be distributed 00072 // over the entire range [0, numeric_limits<size_t>:::max()]. 00073 00074 // _H2: the range-hashing function (in the terminology of Tavori and 00075 // Dreizin). A binary function object whose argument types and result 00076 // type are all size_t. Given arguments r and N, the return value is 00077 // in the range [0, N). 00078 00079 // _Hash: the ranged hash function (Tavori and Dreizin). A binary function 00080 // whose argument types are _Key and size_t and whose result type is 00081 // size_t. Given arguments k and N, the return value is in the range 00082 // [0, N). Default: hash(k, N) = h2(h1(k), N). If _Hash is anything other 00083 // than the default, _H1 and _H2 are ignored. 00084 00085 // _RehashPolicy: Policy class with three members, all of which govern 00086 // the bucket count. _M_next_bkt(n) returns a bucket count no smaller 00087 // than n. _M_bkt_for_elements(n) returns a bucket count appropriate 00088 // for an element count of n. _M_need_rehash(n_bkt, n_elt, n_ins) 00089 // determines whether, if the current bucket count is n_bkt and the 00090 // current element count is n_elt, we need to increase the bucket 00091 // count. If so, returns make_pair(true, n), where n is the new 00092 // bucket count. If not, returns make_pair(false, <anything>). 00093 00094 // ??? Right now it is hard-wired that the number of buckets never 00095 // shrinks. Should we allow _RehashPolicy to change that? 00096 00097 // __cache_hash_code: bool. true if we store the value of the hash 00098 // function along with the value. This is a time-space tradeoff. 00099 // Storing it may improve lookup speed by reducing the number of times 00100 // we need to call the Equal function. 00101 00102 // __constant_iterators: bool. true if iterator and const_iterator are 00103 // both constant iterator types. This is true for unordered_set and 00104 // unordered_multiset, false for unordered_map and unordered_multimap. 00105 00106 // __unique_keys: bool. true if the return value of _Hashtable::count(k) 00107 // is always at most one, false if it may be an arbitrary number. This 00108 // true for unordered_set and unordered_map, false for unordered_multiset 00109 // and unordered_multimap. 00110 00111 template<typename _Key, typename _Value, typename _Allocator, 00112 typename _ExtractKey, typename _Equal, 00113 typename _H1, typename _H2, typename _Hash, 00114 typename _RehashPolicy, 00115 bool __cache_hash_code, 00116 bool __constant_iterators, 00117 bool __unique_keys> 00118 class _Hashtable 00119 : public __detail::_Rehash_base<_RehashPolicy, 00120 _Hashtable<_Key, _Value, _Allocator, 00121 _ExtractKey, 00122 _Equal, _H1, _H2, _Hash, 00123 _RehashPolicy, 00124 __cache_hash_code, 00125 __constant_iterators, 00126 __unique_keys> >, 00127 public __detail::_Hash_code_base<_Key, _Value, _ExtractKey, _Equal, 00128 _H1, _H2, _Hash, __cache_hash_code>, 00129 public __detail::_Map_base<_Key, _Value, _ExtractKey, __unique_keys, 00130 _Hashtable<_Key, _Value, _Allocator, 00131 _ExtractKey, 00132 _Equal, _H1, _H2, _Hash, 00133 _RehashPolicy, 00134 __cache_hash_code, 00135 __constant_iterators, 00136 __unique_keys> > 00137 { 00138 public: 00139 typedef _Allocator allocator_type; 00140 typedef _Value value_type; 00141 typedef _Key key_type; 00142 typedef _Equal key_equal; 00143 // mapped_type, if present, comes from _Map_base. 00144 // hasher, if present, comes from _Hash_code_base. 00145 typedef typename _Allocator::difference_type difference_type; 00146 typedef typename _Allocator::size_type size_type; 00147 typedef typename _Allocator::pointer pointer; 00148 typedef typename _Allocator::const_pointer const_pointer; 00149 typedef typename _Allocator::reference reference; 00150 typedef typename _Allocator::const_reference const_reference; 00151 00152 typedef __detail::_Node_iterator<value_type, __constant_iterators, 00153 __cache_hash_code> 00154 local_iterator; 00155 typedef __detail::_Node_const_iterator<value_type, 00156 __constant_iterators, 00157 __cache_hash_code> 00158 const_local_iterator; 00159 00160 typedef __detail::_Hashtable_iterator<value_type, __constant_iterators, 00161 __cache_hash_code> 00162 iterator; 00163 typedef __detail::_Hashtable_const_iterator<value_type, 00164 __constant_iterators, 00165 __cache_hash_code> 00166 const_iterator; 00167 00168 template<typename _Key2, typename _Value2, typename _Ex2, bool __unique2, 00169 typename _Hashtable2> 00170 friend struct __detail::_Map_base; 00171 00172 private: 00173 typedef __detail::_Hash_node<_Value, __cache_hash_code> _Node; 00174 typedef typename _Allocator::template rebind<_Node>::other 00175 _Node_allocator_type; 00176 typedef typename _Allocator::template rebind<_Node*>::other 00177 _Bucket_allocator_type; 00178 00179 typedef typename _Allocator::template rebind<_Value>::other 00180 _Value_allocator_type; 00181 00182 _Node_allocator_type _M_node_allocator; 00183 _Node** _M_buckets; 00184 size_type _M_bucket_count; 00185 size_type _M_element_count; 00186 _RehashPolicy _M_rehash_policy; 00187 00188 _Node* 00189 _M_allocate_node(const value_type& __v); 00190 00191 void 00192 _M_deallocate_node(_Node* __n); 00193 00194 void 00195 _M_deallocate_nodes(_Node**, size_type); 00196 00197 _Node** 00198 _M_allocate_buckets(size_type __n); 00199 00200 void 00201 _M_deallocate_buckets(_Node**, size_type __n); 00202 00203 public: 00204 // Constructor, destructor, assignment, swap 00205 _Hashtable(size_type __bucket_hint, 00206 const _H1&, const _H2&, const _Hash&, 00207 const _Equal&, const _ExtractKey&, 00208 const allocator_type&); 00209 00210 template<typename _InputIterator> 00211 _Hashtable(_InputIterator __first, _InputIterator __last, 00212 size_type __bucket_hint, 00213 const _H1&, const _H2&, const _Hash&, 00214 const _Equal&, const _ExtractKey&, 00215 const allocator_type&); 00216 00217 _Hashtable(const _Hashtable&); 00218 00219 #ifdef _GLIBCXX_INCLUDE_AS_CXX0X 00220 _Hashtable(_Hashtable&&); 00221 #endif 00222 00223 _Hashtable& 00224 operator=(const _Hashtable&); 00225 00226 ~_Hashtable(); 00227 00228 #ifdef _GLIBCXX_INCLUDE_AS_CXX0X 00229 void swap(_Hashtable&&); 00230 #else 00231 void swap(_Hashtable&); 00232 #endif 00233 00234 // Basic container operations 00235 iterator 00236 begin() 00237 { 00238 iterator __i(_M_buckets); 00239 if (!__i._M_cur_node) 00240 __i._M_incr_bucket(); 00241 return __i; 00242 } 00243 00244 const_iterator 00245 begin() const 00246 { 00247 const_iterator __i(_M_buckets); 00248 if (!__i._M_cur_node) 00249 __i._M_incr_bucket(); 00250 return __i; 00251 } 00252 00253 iterator 00254 end() 00255 { return iterator(_M_buckets + _M_bucket_count); } 00256 00257 const_iterator 00258 end() const 00259 { return const_iterator(_M_buckets + _M_bucket_count); } 00260 00261 #ifdef _GLIBCXX_INCLUDE_AS_CXX0X 00262 const_iterator 00263 cbegin() const 00264 { 00265 const_iterator __i(_M_buckets); 00266 if (!__i._M_cur_node) 00267 __i._M_incr_bucket(); 00268 return __i; 00269 } 00270 00271 const_iterator 00272 cend() const 00273 { return const_iterator(_M_buckets + _M_bucket_count); } 00274 #endif 00275 00276 size_type 00277 size() const 00278 { return _M_element_count; } 00279 00280 bool 00281 empty() const 00282 { return size() == 0; } 00283 00284 allocator_type 00285 get_allocator() const 00286 { return allocator_type(_M_node_allocator); } 00287 00288 _Value_allocator_type 00289 _M_get_Value_allocator() const 00290 { return _Value_allocator_type(_M_node_allocator); } 00291 00292 size_type 00293 max_size() const 00294 { return _M_node_allocator.max_size(); } 00295 00296 // Observers 00297 key_equal 00298 key_eq() const 00299 { return this->_M_eq; } 00300 00301 // hash_function, if present, comes from _Hash_code_base. 00302 00303 // Bucket operations 00304 size_type 00305 bucket_count() const 00306 { return _M_bucket_count; } 00307 00308 size_type 00309 max_bucket_count() const 00310 { return max_size(); } 00311 00312 size_type 00313 bucket_size(size_type __n) const 00314 { return std::distance(begin(__n), end(__n)); } 00315 00316 size_type 00317 bucket(const key_type& __k) const 00318 { 00319 return this->_M_bucket_index(__k, this->_M_hash_code(__k), 00320 bucket_count()); 00321 } 00322 00323 local_iterator 00324 begin(size_type __n) 00325 { return local_iterator(_M_buckets[__n]); } 00326 00327 local_iterator 00328 end(size_type) 00329 { return local_iterator(0); } 00330 00331 const_local_iterator 00332 begin(size_type __n) const 00333 { return const_local_iterator(_M_buckets[__n]); } 00334 00335 const_local_iterator 00336 end(size_type) const 00337 { return const_local_iterator(0); } 00338 00339 #ifdef _GLIBCXX_INCLUDE_AS_CXX0X 00340 // DR 691. 00341 const_local_iterator 00342 cbegin(size_type __n) const 00343 { return const_local_iterator(_M_buckets[__n]); } 00344 00345 const_local_iterator 00346 cend(size_type) const 00347 { return const_local_iterator(0); } 00348 #endif 00349 00350 float 00351 load_factor() const 00352 { 00353 return static_cast<float>(size()) / static_cast<float>(bucket_count()); 00354 } 00355 00356 // max_load_factor, if present, comes from _Rehash_base. 00357 00358 // Generalization of max_load_factor. Extension, not found in TR1. Only 00359 // useful if _RehashPolicy is something other than the default. 00360 const _RehashPolicy& 00361 __rehash_policy() const 00362 { return _M_rehash_policy; } 00363 00364 void 00365 __rehash_policy(const _RehashPolicy&); 00366 00367 // Lookup. 00368 iterator 00369 find(const key_type& __k); 00370 00371 const_iterator 00372 find(const key_type& __k) const; 00373 00374 size_type 00375 count(const key_type& __k) const; 00376 00377 std::pair<iterator, iterator> 00378 equal_range(const key_type& __k); 00379 00380 std::pair<const_iterator, const_iterator> 00381 equal_range(const key_type& __k) const; 00382 00383 private: // Find, insert and erase helper functions 00384 // ??? This dispatching is a workaround for the fact that we don't 00385 // have partial specialization of member templates; it would be 00386 // better to just specialize insert on __unique_keys. There may be a 00387 // cleaner workaround. 00388 typedef typename __gnu_cxx::__conditional_type<__unique_keys, 00389 std::pair<iterator, bool>, iterator>::__type 00390 _Insert_Return_Type; 00391 00392 typedef typename __gnu_cxx::__conditional_type<__unique_keys, 00393 std::_Select1st<_Insert_Return_Type>, 00394 std::_Identity<_Insert_Return_Type> 00395 >::__type 00396 _Insert_Conv_Type; 00397 00398 _Node* 00399 _M_find_node(_Node*, const key_type&, 00400 typename _Hashtable::_Hash_code_type) const; 00401 00402 iterator 00403 _M_insert_bucket(const value_type&, size_type, 00404 typename _Hashtable::_Hash_code_type); 00405 00406 std::pair<iterator, bool> 00407 _M_insert(const value_type&, std::_GLIBCXX_TR1 true_type); 00408 00409 iterator 00410 _M_insert(const value_type&, std::_GLIBCXX_TR1 false_type); 00411 00412 void 00413 _M_erase_node(_Node*, _Node**); 00414 00415 public: 00416 // Insert and erase 00417 _Insert_Return_Type 00418 insert(const value_type& __v) 00419 { return _M_insert(__v, std::_GLIBCXX_TR1 integral_constant<bool, 00420 __unique_keys>()); } 00421 00422 iterator 00423 insert(iterator, const value_type& __v) 00424 { return iterator(_Insert_Conv_Type()(this->insert(__v))); } 00425 00426 const_iterator 00427 insert(const_iterator, const value_type& __v) 00428 { return const_iterator(_Insert_Conv_Type()(this->insert(__v))); } 00429 00430 template<typename _InputIterator> 00431 void 00432 insert(_InputIterator __first, _InputIterator __last); 00433 00434 #ifdef _GLIBCXX_INCLUDE_AS_CXX0X 00435 void 00436 insert(initializer_list<value_type> __l) 00437 { this->insert(__l.begin(), __l.end()); } 00438 #endif 00439 00440 iterator 00441 erase(iterator); 00442 00443 const_iterator 00444 erase(const_iterator); 00445 00446 size_type 00447 erase(const key_type&); 00448 00449 iterator 00450 erase(iterator, iterator); 00451 00452 const_iterator 00453 erase(const_iterator, const_iterator); 00454 00455 void 00456 clear(); 00457 00458 // Set number of buckets to be appropriate for container of n element. 00459 void rehash(size_type __n); 00460 00461 private: 00462 // Unconditionally change size of bucket array to n. 00463 void _M_rehash(size_type __n); 00464 }; 00465 00466 00467 // Definitions of class template _Hashtable's out-of-line member functions. 00468 template<typename _Key, typename _Value, 00469 typename _Allocator, typename _ExtractKey, typename _Equal, 00470 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 00471 bool __chc, bool __cit, bool __uk> 00472 typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 00473 _H1, _H2, _Hash, _RehashPolicy, 00474 __chc, __cit, __uk>::_Node* 00475 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 00476 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 00477 _M_allocate_node(const value_type& __v) 00478 { 00479 _Node* __n = _M_node_allocator.allocate(1); 00480 __try 00481 { 00482 #ifdef _GLIBCXX_INCLUDE_AS_CXX0X 00483 _M_node_allocator.construct(__n, __v); 00484 #else 00485 _M_get_Value_allocator().construct(&__n->_M_v, __v); 00486 #endif 00487 __n->_M_next = 0; 00488 return __n; 00489 } 00490 __catch(...) 00491 { 00492 _M_node_allocator.deallocate(__n, 1); 00493 __throw_exception_again; 00494 } 00495 } 00496 00497 template<typename _Key, typename _Value, 00498 typename _Allocator, typename _ExtractKey, typename _Equal, 00499 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 00500 bool __chc, bool __cit, bool __uk> 00501 void 00502 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 00503 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 00504 _M_deallocate_node(_Node* __n) 00505 { 00506 #ifdef _GLIBCXX_INCLUDE_AS_CXX0X 00507 _M_node_allocator.destroy(__n); 00508 #else 00509 _M_get_Value_allocator().destroy(&__n->_M_v); 00510 #endif 00511 _M_node_allocator.deallocate(__n, 1); 00512 } 00513 00514 template<typename _Key, typename _Value, 00515 typename _Allocator, typename _ExtractKey, typename _Equal, 00516 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 00517 bool __chc, bool __cit, bool __uk> 00518 void 00519 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 00520 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 00521 _M_deallocate_nodes(_Node** __array, size_type __n) 00522 { 00523 for (size_type __i = 0; __i < __n; ++__i) 00524 { 00525 _Node* __p = __array[__i]; 00526 while (__p) 00527 { 00528 _Node* __tmp = __p; 00529 __p = __p->_M_next; 00530 _M_deallocate_node(__tmp); 00531 } 00532 __array[__i] = 0; 00533 } 00534 } 00535 00536 template<typename _Key, typename _Value, 00537 typename _Allocator, typename _ExtractKey, typename _Equal, 00538 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 00539 bool __chc, bool __cit, bool __uk> 00540 typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 00541 _H1, _H2, _Hash, _RehashPolicy, 00542 __chc, __cit, __uk>::_Node** 00543 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 00544 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 00545 _M_allocate_buckets(size_type __n) 00546 { 00547 _Bucket_allocator_type __alloc(_M_node_allocator); 00548 00549 // We allocate one extra bucket to hold a sentinel, an arbitrary 00550 // non-null pointer. Iterator increment relies on this. 00551 _Node** __p = __alloc.allocate(__n + 1); 00552 std::fill(__p, __p + __n, (_Node*) 0); 00553 __p[__n] = reinterpret_cast<_Node*>(0x1000); 00554 return __p; 00555 } 00556 00557 template<typename _Key, typename _Value, 00558 typename _Allocator, typename _ExtractKey, typename _Equal, 00559 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 00560 bool __chc, bool __cit, bool __uk> 00561 void 00562 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 00563 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 00564 _M_deallocate_buckets(_Node** __p, size_type __n) 00565 { 00566 _Bucket_allocator_type __alloc(_M_node_allocator); 00567 __alloc.deallocate(__p, __n + 1); 00568 } 00569 00570 template<typename _Key, typename _Value, 00571 typename _Allocator, typename _ExtractKey, typename _Equal, 00572 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 00573 bool __chc, bool __cit, bool __uk> 00574 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 00575 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 00576 _Hashtable(size_type __bucket_hint, 00577 const _H1& __h1, const _H2& __h2, const _Hash& __h, 00578 const _Equal& __eq, const _ExtractKey& __exk, 00579 const allocator_type& __a) 00580 : __detail::_Rehash_base<_RehashPolicy, _Hashtable>(), 00581 __detail::_Hash_code_base<_Key, _Value, _ExtractKey, _Equal, 00582 _H1, _H2, _Hash, __chc>(__exk, __eq, 00583 __h1, __h2, __h), 00584 __detail::_Map_base<_Key, _Value, _ExtractKey, __uk, _Hashtable>(), 00585 _M_node_allocator(__a), 00586 _M_bucket_count(0), 00587 _M_element_count(0), 00588 _M_rehash_policy() 00589 { 00590 _M_bucket_count = _M_rehash_policy._M_next_bkt(__bucket_hint); 00591 _M_buckets = _M_allocate_buckets(_M_bucket_count); 00592 } 00593 00594 template<typename _Key, typename _Value, 00595 typename _Allocator, typename _ExtractKey, typename _Equal, 00596 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 00597 bool __chc, bool __cit, bool __uk> 00598 template<typename _InputIterator> 00599 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 00600 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 00601 _Hashtable(_InputIterator __f, _InputIterator __l, 00602 size_type __bucket_hint, 00603 const _H1& __h1, const _H2& __h2, const _Hash& __h, 00604 const _Equal& __eq, const _ExtractKey& __exk, 00605 const allocator_type& __a) 00606 : __detail::_Rehash_base<_RehashPolicy, _Hashtable>(), 00607 __detail::_Hash_code_base<_Key, _Value, _ExtractKey, _Equal, 00608 _H1, _H2, _Hash, __chc>(__exk, __eq, 00609 __h1, __h2, __h), 00610 __detail::_Map_base<_Key, _Value, _ExtractKey, __uk, _Hashtable>(), 00611 _M_node_allocator(__a), 00612 _M_bucket_count(0), 00613 _M_element_count(0), 00614 _M_rehash_policy() 00615 { 00616 _M_bucket_count = std::max(_M_rehash_policy._M_next_bkt(__bucket_hint), 00617 _M_rehash_policy. 00618 _M_bkt_for_elements(__detail:: 00619 __distance_fw(__f, 00620 __l))); 00621 _M_buckets = _M_allocate_buckets(_M_bucket_count); 00622 __try 00623 { 00624 for (; __f != __l; ++__f) 00625 this->insert(*__f); 00626 } 00627 __catch(...) 00628 { 00629 clear(); 00630 _M_deallocate_buckets(_M_buckets, _M_bucket_count); 00631 __throw_exception_again; 00632 } 00633 } 00634 00635 template<typename _Key, typename _Value, 00636 typename _Allocator, typename _ExtractKey, typename _Equal, 00637 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 00638 bool __chc, bool __cit, bool __uk> 00639 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 00640 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 00641 _Hashtable(const _Hashtable& __ht) 00642 : __detail::_Rehash_base<_RehashPolicy, _Hashtable>(__ht), 00643 __detail::_Hash_code_base<_Key, _Value, _ExtractKey, _Equal, 00644 _H1, _H2, _Hash, __chc>(__ht), 00645 __detail::_Map_base<_Key, _Value, _ExtractKey, __uk, _Hashtable>(__ht), 00646 _M_node_allocator(__ht._M_node_allocator), 00647 _M_bucket_count(__ht._M_bucket_count), 00648 _M_element_count(__ht._M_element_count), 00649 _M_rehash_policy(__ht._M_rehash_policy) 00650 { 00651 _M_buckets = _M_allocate_buckets(_M_bucket_count); 00652 __try 00653 { 00654 for (size_type __i = 0; __i < __ht._M_bucket_count; ++__i) 00655 { 00656 _Node* __n = __ht._M_buckets[__i]; 00657 _Node** __tail = _M_buckets + __i; 00658 while (__n) 00659 { 00660 *__tail = _M_allocate_node(__n->_M_v); 00661 this->_M_copy_code(*__tail, __n); 00662 __tail = &((*__tail)->_M_next); 00663 __n = __n->_M_next; 00664 } 00665 } 00666 } 00667 __catch(...) 00668 { 00669 clear(); 00670 _M_deallocate_buckets(_M_buckets, _M_bucket_count); 00671 __throw_exception_again; 00672 } 00673 } 00674 00675 #ifdef _GLIBCXX_INCLUDE_AS_CXX0X 00676 template<typename _Key, typename _Value, 00677 typename _Allocator, typename _ExtractKey, typename _Equal, 00678 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 00679 bool __chc, bool __cit, bool __uk> 00680 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 00681 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 00682 _Hashtable(_Hashtable&& __ht) 00683 : __detail::_Rehash_base<_RehashPolicy, _Hashtable>(__ht), 00684 __detail::_Hash_code_base<_Key, _Value, _ExtractKey, _Equal, 00685 _H1, _H2, _Hash, __chc>(__ht), 00686 __detail::_Map_base<_Key, _Value, _ExtractKey, __uk, _Hashtable>(__ht), 00687 _M_node_allocator(__ht._M_node_allocator), 00688 _M_bucket_count(__ht._M_bucket_count), 00689 _M_element_count(__ht._M_element_count), 00690 _M_rehash_policy(__ht._M_rehash_policy), 00691 _M_buckets(__ht._M_buckets) 00692 { 00693 size_type __n_bkt = __ht._M_rehash_policy._M_next_bkt(0); 00694 __ht._M_buckets = __ht._M_allocate_buckets(__n_bkt); 00695 __ht._M_bucket_count = __n_bkt; 00696 __ht._M_element_count = 0; 00697 __ht._M_rehash_policy = _RehashPolicy(); 00698 } 00699 #endif 00700 00701 template<typename _Key, typename _Value, 00702 typename _Allocator, typename _ExtractKey, typename _Equal, 00703 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 00704 bool __chc, bool __cit, bool __uk> 00705 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 00706 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>& 00707 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 00708 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 00709 operator=(const _Hashtable& __ht) 00710 { 00711 _Hashtable __tmp(__ht); 00712 this->swap(__tmp); 00713 return *this; 00714 } 00715 00716 template<typename _Key, typename _Value, 00717 typename _Allocator, typename _ExtractKey, typename _Equal, 00718 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 00719 bool __chc, bool __cit, bool __uk> 00720 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 00721 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 00722 ~_Hashtable() 00723 { 00724 clear(); 00725 _M_deallocate_buckets(_M_buckets, _M_bucket_count); 00726 } 00727 00728 template<typename _Key, typename _Value, 00729 typename _Allocator, typename _ExtractKey, typename _Equal, 00730 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 00731 bool __chc, bool __cit, bool __uk> 00732 void 00733 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 00734 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 00735 #ifdef _GLIBCXX_INCLUDE_AS_CXX0X 00736 swap(_Hashtable&& __x) 00737 #else 00738 swap(_Hashtable& __x) 00739 #endif 00740 { 00741 // The only base class with member variables is hash_code_base. We 00742 // define _Hash_code_base::_M_swap because different specializations 00743 // have different members. 00744 __detail::_Hash_code_base<_Key, _Value, _ExtractKey, _Equal, 00745 _H1, _H2, _Hash, __chc>::_M_swap(__x); 00746 00747 // _GLIBCXX_RESOLVE_LIB_DEFECTS 00748 // 431. Swapping containers with unequal allocators. 00749 std::__alloc_swap<_Node_allocator_type>::_S_do_it(_M_node_allocator, 00750 __x._M_node_allocator); 00751 00752 std::swap(_M_rehash_policy, __x._M_rehash_policy); 00753 std::swap(_M_buckets, __x._M_buckets); 00754 std::swap(_M_bucket_count, __x._M_bucket_count); 00755 std::swap(_M_element_count, __x._M_element_count); 00756 } 00757 00758 template<typename _Key, typename _Value, 00759 typename _Allocator, typename _ExtractKey, typename _Equal, 00760 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 00761 bool __chc, bool __cit, bool __uk> 00762 void 00763 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 00764 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 00765 __rehash_policy(const _RehashPolicy& __pol) 00766 { 00767 _M_rehash_policy = __pol; 00768 size_type __n_bkt = __pol._M_bkt_for_elements(_M_element_count); 00769 if (__n_bkt > _M_bucket_count) 00770 _M_rehash(__n_bkt); 00771 } 00772 00773 template<typename _Key, typename _Value, 00774 typename _Allocator, typename _ExtractKey, typename _Equal, 00775 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 00776 bool __chc, bool __cit, bool __uk> 00777 typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 00778 _H1, _H2, _Hash, _RehashPolicy, 00779 __chc, __cit, __uk>::iterator 00780 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 00781 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 00782 find(const key_type& __k) 00783 { 00784 typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k); 00785 std::size_t __n = this->_M_bucket_index(__k, __code, _M_bucket_count); 00786 _Node* __p = _M_find_node(_M_buckets[__n], __k, __code); 00787 return __p ? iterator(__p, _M_buckets + __n) : this->end(); 00788 } 00789 00790 template<typename _Key, typename _Value, 00791 typename _Allocator, typename _ExtractKey, typename _Equal, 00792 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 00793 bool __chc, bool __cit, bool __uk> 00794 typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 00795 _H1, _H2, _Hash, _RehashPolicy, 00796 __chc, __cit, __uk>::const_iterator 00797 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 00798 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 00799 find(const key_type& __k) const 00800 { 00801 typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k); 00802 std::size_t __n = this->_M_bucket_index(__k, __code, _M_bucket_count); 00803 _Node* __p = _M_find_node(_M_buckets[__n], __k, __code); 00804 return __p ? const_iterator(__p, _M_buckets + __n) : this->end(); 00805 } 00806 00807 template<typename _Key, typename _Value, 00808 typename _Allocator, typename _ExtractKey, typename _Equal, 00809 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 00810 bool __chc, bool __cit, bool __uk> 00811 typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 00812 _H1, _H2, _Hash, _RehashPolicy, 00813 __chc, __cit, __uk>::size_type 00814 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 00815 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 00816 count(const key_type& __k) const 00817 { 00818 typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k); 00819 std::size_t __n = this->_M_bucket_index(__k, __code, _M_bucket_count); 00820 std::size_t __result = 0; 00821 for (_Node* __p = _M_buckets[__n]; __p; __p = __p->_M_next) 00822 if (this->_M_compare(__k, __code, __p)) 00823 ++__result; 00824 return __result; 00825 } 00826 00827 template<typename _Key, typename _Value, 00828 typename _Allocator, typename _ExtractKey, typename _Equal, 00829 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 00830 bool __chc, bool __cit, bool __uk> 00831 std::pair<typename _Hashtable<_Key, _Value, _Allocator, 00832 _ExtractKey, _Equal, _H1, 00833 _H2, _Hash, _RehashPolicy, 00834 __chc, __cit, __uk>::iterator, 00835 typename _Hashtable<_Key, _Value, _Allocator, 00836 _ExtractKey, _Equal, _H1, 00837 _H2, _Hash, _RehashPolicy, 00838 __chc, __cit, __uk>::iterator> 00839 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 00840 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 00841 equal_range(const key_type& __k) 00842 { 00843 typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k); 00844 std::size_t __n = this->_M_bucket_index(__k, __code, _M_bucket_count); 00845 _Node** __head = _M_buckets + __n; 00846 _Node* __p = _M_find_node(*__head, __k, __code); 00847 00848 if (__p) 00849 { 00850 _Node* __p1 = __p->_M_next; 00851 for (; __p1; __p1 = __p1->_M_next) 00852 if (!this->_M_compare(__k, __code, __p1)) 00853 break; 00854 00855 iterator __first(__p, __head); 00856 iterator __last(__p1, __head); 00857 if (!__p1) 00858 __last._M_incr_bucket(); 00859 return std::make_pair(__first, __last); 00860 } 00861 else 00862 return std::make_pair(this->end(), this->end()); 00863 } 00864 00865 template<typename _Key, typename _Value, 00866 typename _Allocator, typename _ExtractKey, typename _Equal, 00867 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 00868 bool __chc, bool __cit, bool __uk> 00869 std::pair<typename _Hashtable<_Key, _Value, _Allocator, 00870 _ExtractKey, _Equal, _H1, 00871 _H2, _Hash, _RehashPolicy, 00872 __chc, __cit, __uk>::const_iterator, 00873 typename _Hashtable<_Key, _Value, _Allocator, 00874 _ExtractKey, _Equal, _H1, 00875 _H2, _Hash, _RehashPolicy, 00876 __chc, __cit, __uk>::const_iterator> 00877 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 00878 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 00879 equal_range(const key_type& __k) const 00880 { 00881 typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k); 00882 std::size_t __n = this->_M_bucket_index(__k, __code, _M_bucket_count); 00883 _Node** __head = _M_buckets + __n; 00884 _Node* __p = _M_find_node(*__head, __k, __code); 00885 00886 if (__p) 00887 { 00888 _Node* __p1 = __p->_M_next; 00889 for (; __p1; __p1 = __p1->_M_next) 00890 if (!this->_M_compare(__k, __code, __p1)) 00891 break; 00892 00893 const_iterator __first(__p, __head); 00894 const_iterator __last(__p1, __head); 00895 if (!__p1) 00896 __last._M_incr_bucket(); 00897 return std::make_pair(__first, __last); 00898 } 00899 else 00900 return std::make_pair(this->end(), this->end()); 00901 } 00902 00903 // Find the node whose key compares equal to k, beginning the search 00904 // at p (usually the head of a bucket). Return nil if no node is found. 00905 template<typename _Key, typename _Value, 00906 typename _Allocator, typename _ExtractKey, typename _Equal, 00907 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 00908 bool __chc, bool __cit, bool __uk> 00909 typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, 00910 _Equal, _H1, _H2, _Hash, _RehashPolicy, 00911 __chc, __cit, __uk>::_Node* 00912 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 00913 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 00914 _M_find_node(_Node* __p, const key_type& __k, 00915 typename _Hashtable::_Hash_code_type __code) const 00916 { 00917 for (; __p; __p = __p->_M_next) 00918 if (this->_M_compare(__k, __code, __p)) 00919 return __p; 00920 return false; 00921 } 00922 00923 // Insert v in bucket n (assumes no element with its key already present). 00924 template<typename _Key, typename _Value, 00925 typename _Allocator, typename _ExtractKey, typename _Equal, 00926 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 00927 bool __chc, bool __cit, bool __uk> 00928 typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 00929 _H1, _H2, _Hash, _RehashPolicy, 00930 __chc, __cit, __uk>::iterator 00931 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 00932 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 00933 _M_insert_bucket(const value_type& __v, size_type __n, 00934 typename _Hashtable::_Hash_code_type __code) 00935 { 00936 std::pair<bool, std::size_t> __do_rehash 00937 = _M_rehash_policy._M_need_rehash(_M_bucket_count, 00938 _M_element_count, 1); 00939 00940 // Allocate the new node before doing the rehash so that we don't 00941 // do a rehash if the allocation throws. 00942 _Node* __new_node = _M_allocate_node(__v); 00943 00944 __try 00945 { 00946 if (__do_rehash.first) 00947 { 00948 const key_type& __k = this->_M_extract(__v); 00949 __n = this->_M_bucket_index(__k, __code, __do_rehash.second); 00950 _M_rehash(__do_rehash.second); 00951 } 00952 00953 __new_node->_M_next = _M_buckets[__n]; 00954 this->_M_store_code(__new_node, __code); 00955 _M_buckets[__n] = __new_node; 00956 ++_M_element_count; 00957 return iterator(__new_node, _M_buckets + __n); 00958 } 00959 __catch(...) 00960 { 00961 _M_deallocate_node(__new_node); 00962 __throw_exception_again; 00963 } 00964 } 00965 00966 // Insert v if no element with its key is already present. 00967 template<typename _Key, typename _Value, 00968 typename _Allocator, typename _ExtractKey, typename _Equal, 00969 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 00970 bool __chc, bool __cit, bool __uk> 00971 std::pair<typename _Hashtable<_Key, _Value, _Allocator, 00972 _ExtractKey, _Equal, _H1, 00973 _H2, _Hash, _RehashPolicy, 00974 __chc, __cit, __uk>::iterator, bool> 00975 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 00976 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 00977 _M_insert(const value_type& __v, std::_GLIBCXX_TR1 true_type) 00978 { 00979 const key_type& __k = this->_M_extract(__v); 00980 typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k); 00981 size_type __n = this->_M_bucket_index(__k, __code, _M_bucket_count); 00982 00983 if (_Node* __p = _M_find_node(_M_buckets[__n], __k, __code)) 00984 return std::make_pair(iterator(__p, _M_buckets + __n), false); 00985 return std::make_pair(_M_insert_bucket(__v, __n, __code), true); 00986 } 00987 00988 // Insert v unconditionally. 00989 template<typename _Key, typename _Value, 00990 typename _Allocator, typename _ExtractKey, typename _Equal, 00991 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 00992 bool __chc, bool __cit, bool __uk> 00993 typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 00994 _H1, _H2, _Hash, _RehashPolicy, 00995 __chc, __cit, __uk>::iterator 00996 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 00997 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 00998 _M_insert(const value_type& __v, std::_GLIBCXX_TR1 false_type) 00999 { 01000 std::pair<bool, std::size_t> __do_rehash 01001 = _M_rehash_policy._M_need_rehash(_M_bucket_count, 01002 _M_element_count, 1); 01003 if (__do_rehash.first) 01004 _M_rehash(__do_rehash.second); 01005 01006 const key_type& __k = this->_M_extract(__v); 01007 typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k); 01008 size_type __n = this->_M_bucket_index(__k, __code, _M_bucket_count); 01009 01010 // First find the node, avoid leaking new_node if compare throws. 01011 _Node* __prev = _M_find_node(_M_buckets[__n], __k, __code); 01012 _Node* __new_node = _M_allocate_node(__v); 01013 01014 if (__prev) 01015 { 01016 __new_node->_M_next = __prev->_M_next; 01017 __prev->_M_next = __new_node; 01018 } 01019 else 01020 { 01021 __new_node->_M_next = _M_buckets[__n]; 01022 _M_buckets[__n] = __new_node; 01023 } 01024 this->_M_store_code(__new_node, __code); 01025 01026 ++_M_element_count; 01027 return iterator(__new_node, _M_buckets + __n); 01028 } 01029 01030 // For erase(iterator) and erase(const_iterator). 01031 template<typename _Key, typename _Value, 01032 typename _Allocator, typename _ExtractKey, typename _Equal, 01033 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 01034 bool __chc, bool __cit, bool __uk> 01035 void 01036 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 01037 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 01038 _M_erase_node(_Node* __p, _Node** __b) 01039 { 01040 _Node* __cur = *__b; 01041 if (__cur == __p) 01042 *__b = __cur->_M_next; 01043 else 01044 { 01045 _Node* __next = __cur->_M_next; 01046 while (__next != __p) 01047 { 01048 __cur = __next; 01049 __next = __cur->_M_next; 01050 } 01051 __cur->_M_next = __next->_M_next; 01052 } 01053 01054 _M_deallocate_node(__p); 01055 --_M_element_count; 01056 } 01057 01058 template<typename _Key, typename _Value, 01059 typename _Allocator, typename _ExtractKey, typename _Equal, 01060 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 01061 bool __chc, bool __cit, bool __uk> 01062 template<typename _InputIterator> 01063 void 01064 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 01065 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 01066 insert(_InputIterator __first, _InputIterator __last) 01067 { 01068 size_type __n_elt = __detail::__distance_fw(__first, __last); 01069 std::pair<bool, std::size_t> __do_rehash 01070 = _M_rehash_policy._M_need_rehash(_M_bucket_count, 01071 _M_element_count, __n_elt); 01072 if (__do_rehash.first) 01073 _M_rehash(__do_rehash.second); 01074 01075 for (; __first != __last; ++__first) 01076 this->insert(*__first); 01077 } 01078 01079 template<typename _Key, typename _Value, 01080 typename _Allocator, typename _ExtractKey, typename _Equal, 01081 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 01082 bool __chc, bool __cit, bool __uk> 01083 typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 01084 _H1, _H2, _Hash, _RehashPolicy, 01085 __chc, __cit, __uk>::iterator 01086 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 01087 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 01088 erase(iterator __it) 01089 { 01090 iterator __result = __it; 01091 ++__result; 01092 _M_erase_node(__it._M_cur_node, __it._M_cur_bucket); 01093 return __result; 01094 } 01095 01096 template<typename _Key, typename _Value, 01097 typename _Allocator, typename _ExtractKey, typename _Equal, 01098 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 01099 bool __chc, bool __cit, bool __uk> 01100 typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 01101 _H1, _H2, _Hash, _RehashPolicy, 01102 __chc, __cit, __uk>::const_iterator 01103 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 01104 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 01105 erase(const_iterator __it) 01106 { 01107 const_iterator __result = __it; 01108 ++__result; 01109 _M_erase_node(__it._M_cur_node, __it._M_cur_bucket); 01110 return __result; 01111 } 01112 01113 template<typename _Key, typename _Value, 01114 typename _Allocator, typename _ExtractKey, typename _Equal, 01115 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 01116 bool __chc, bool __cit, bool __uk> 01117 typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 01118 _H1, _H2, _Hash, _RehashPolicy, 01119 __chc, __cit, __uk>::size_type 01120 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 01121 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 01122 erase(const key_type& __k) 01123 { 01124 typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k); 01125 std::size_t __n = this->_M_bucket_index(__k, __code, _M_bucket_count); 01126 size_type __result = 0; 01127 01128 _Node** __slot = _M_buckets + __n; 01129 while (*__slot && !this->_M_compare(__k, __code, *__slot)) 01130 __slot = &((*__slot)->_M_next); 01131 01132 _Node** __saved_slot = 0; 01133 while (*__slot && this->_M_compare(__k, __code, *__slot)) 01134 { 01135 // _GLIBCXX_RESOLVE_LIB_DEFECTS 01136 // 526. Is it undefined if a function in the standard changes 01137 // in parameters? 01138 if (&this->_M_extract((*__slot)->_M_v) != &__k) 01139 { 01140 _Node* __p = *__slot; 01141 *__slot = __p->_M_next; 01142 _M_deallocate_node(__p); 01143 --_M_element_count; 01144 ++__result; 01145 } 01146 else 01147 { 01148 __saved_slot = __slot; 01149 __slot = &((*__slot)->_M_next); 01150 } 01151 } 01152 01153 if (__saved_slot) 01154 { 01155 _Node* __p = *__saved_slot; 01156 *__saved_slot = __p->_M_next; 01157 _M_deallocate_node(__p); 01158 --_M_element_count; 01159 ++__result; 01160 } 01161 01162 return __result; 01163 } 01164 01165 // ??? This could be optimized by taking advantage of the bucket 01166 // structure, but it's not clear that it's worth doing. It probably 01167 // wouldn't even be an optimization unless the load factor is large. 01168 template<typename _Key, typename _Value, 01169 typename _Allocator, typename _ExtractKey, typename _Equal, 01170 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 01171 bool __chc, bool __cit, bool __uk> 01172 typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 01173 _H1, _H2, _Hash, _RehashPolicy, 01174 __chc, __cit, __uk>::iterator 01175 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 01176 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 01177 erase(iterator __first, iterator __last) 01178 { 01179 while (__first != __last) 01180 __first = this->erase(__first); 01181 return __last; 01182 } 01183 01184 template<typename _Key, typename _Value, 01185 typename _Allocator, typename _ExtractKey, typename _Equal, 01186 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 01187 bool __chc, bool __cit, bool __uk> 01188 typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 01189 _H1, _H2, _Hash, _RehashPolicy, 01190 __chc, __cit, __uk>::const_iterator 01191 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 01192 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 01193 erase(const_iterator __first, const_iterator __last) 01194 { 01195 while (__first != __last) 01196 __first = this->erase(__first); 01197 return __last; 01198 } 01199 01200 template<typename _Key, typename _Value, 01201 typename _Allocator, typename _ExtractKey, typename _Equal, 01202 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 01203 bool __chc, bool __cit, bool __uk> 01204 void 01205 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 01206 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 01207 clear() 01208 { 01209 _M_deallocate_nodes(_M_buckets, _M_bucket_count); 01210 _M_element_count = 0; 01211 } 01212 01213 template<typename _Key, typename _Value, 01214 typename _Allocator, typename _ExtractKey, typename _Equal, 01215 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 01216 bool __chc, bool __cit, bool __uk> 01217 void 01218 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 01219 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 01220 rehash(size_type __n) 01221 { 01222 _M_rehash(std::max(_M_rehash_policy._M_next_bkt(__n), 01223 _M_rehash_policy._M_bkt_for_elements(_M_element_count 01224 + 1))); 01225 } 01226 01227 template<typename _Key, typename _Value, 01228 typename _Allocator, typename _ExtractKey, typename _Equal, 01229 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 01230 bool __chc, bool __cit, bool __uk> 01231 void 01232 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 01233 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 01234 _M_rehash(size_type __n) 01235 { 01236 _Node** __new_array = _M_allocate_buckets(__n); 01237 __try 01238 { 01239 for (size_type __i = 0; __i < _M_bucket_count; ++__i) 01240 while (_Node* __p = _M_buckets[__i]) 01241 { 01242 std::size_t __new_index = this->_M_bucket_index(__p, __n); 01243 _M_buckets[__i] = __p->_M_next; 01244 __p->_M_next = __new_array[__new_index]; 01245 __new_array[__new_index] = __p; 01246 } 01247 _M_deallocate_buckets(_M_buckets, _M_bucket_count); 01248 _M_bucket_count = __n; 01249 _M_buckets = __new_array; 01250 } 01251 __catch(...) 01252 { 01253 // A failure here means that a hash function threw an exception. 01254 // We can't restore the previous state without calling the hash 01255 // function again, so the only sensible recovery is to delete 01256 // everything. 01257 _M_deallocate_nodes(__new_array, __n); 01258 _M_deallocate_buckets(__new_array, __n); 01259 _M_deallocate_nodes(_M_buckets, _M_bucket_count); 01260 _M_element_count = 0; 01261 __throw_exception_again; 01262 } 01263 } 01264 01265 _GLIBCXX_END_NAMESPACE_TR1 01266 }