libstdc++
|
00001 // hashtable.h header -*- C++ -*- 00002 00003 // Copyright (C) 2007, 2008, 2009, 2010, 2011 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 bits/hashtable.h 00026 * This is an internal header file, included by other library headers. 00027 * Do not attempt to use it directly. @headername{unordered_map, unordered_set} 00028 */ 00029 00030 #ifndef _HASHTABLE_H 00031 #define _HASHTABLE_H 1 00032 00033 #pragma GCC system_header 00034 00035 #include <bits/hashtable_policy.h> 00036 00037 namespace std _GLIBCXX_VISIBILITY(default) 00038 { 00039 _GLIBCXX_BEGIN_NAMESPACE_VERSION 00040 00041 // Class template _Hashtable, class definition. 00042 00043 // Meaning of class template _Hashtable's template parameters 00044 00045 // _Key and _Value: arbitrary CopyConstructible types. 00046 00047 // _Allocator: an allocator type ([lib.allocator.requirements]) whose 00048 // value type is Value. As a conforming extension, we allow for 00049 // value type != Value. 00050 00051 // _ExtractKey: function object that takes an object of type Value 00052 // and returns a value of type _Key. 00053 00054 // _Equal: function object that takes two objects of type k and returns 00055 // a bool-like value that is true if the two objects are considered equal. 00056 00057 // _H1: the hash function. A unary function object with argument type 00058 // Key and result type size_t. Return values should be distributed 00059 // over the entire range [0, numeric_limits<size_t>:::max()]. 00060 00061 // _H2: the range-hashing function (in the terminology of Tavori and 00062 // Dreizin). A binary function object whose argument types and result 00063 // type are all size_t. Given arguments r and N, the return value is 00064 // in the range [0, N). 00065 00066 // _Hash: the ranged hash function (Tavori and Dreizin). A binary function 00067 // whose argument types are _Key and size_t and whose result type is 00068 // size_t. Given arguments k and N, the return value is in the range 00069 // [0, N). Default: hash(k, N) = h2(h1(k), N). If _Hash is anything other 00070 // than the default, _H1 and _H2 are ignored. 00071 00072 // _RehashPolicy: Policy class with three members, all of which govern 00073 // the bucket count. _M_next_bkt(n) returns a bucket count no smaller 00074 // than n. _M_bkt_for_elements(n) returns a bucket count appropriate 00075 // for an element count of n. _M_need_rehash(n_bkt, n_elt, n_ins) 00076 // determines whether, if the current bucket count is n_bkt and the 00077 // current element count is n_elt, we need to increase the bucket 00078 // count. If so, returns make_pair(true, n), where n is the new 00079 // bucket count. If not, returns make_pair(false, <anything>). 00080 00081 // __cache_hash_code: bool. true if we store the value of the hash 00082 // function along with the value. This is a time-space tradeoff. 00083 // Storing it may improve lookup speed by reducing the number of times 00084 // we need to call the Equal function. 00085 00086 // __constant_iterators: bool. true if iterator and const_iterator are 00087 // both constant iterator types. This is true for unordered_set and 00088 // unordered_multiset, false for unordered_map and unordered_multimap. 00089 00090 // __unique_keys: bool. true if the return value of _Hashtable::count(k) 00091 // is always at most one, false if it may be an arbitrary number. This 00092 // true for unordered_set and unordered_map, false for unordered_multiset 00093 // and unordered_multimap. 00094 /** 00095 * Here's _Hashtable data structure, each _Hashtable has: 00096 * - _Bucket[] _M_buckets 00097 * - _Hash_node_base _M_before_begin 00098 * - size_type _M_bucket_count 00099 * - size_type _M_element_count 00100 * 00101 * with _Bucket being _Hash_node* and _Hash_node constaining: 00102 * - _Hash_node* _M_next 00103 * - Tp _M_value 00104 * - size_t _M_code if cache_hash_code is true 00105 * 00106 * In terms of Standard containers the hastable is like the aggregation of: 00107 * - std::forward_list<_Node> containing the elements 00108 * - std::vector<std::forward_list<_Node>::iterator> representing the buckets 00109 * 00110 * The non-empty buckets contain the node before the first bucket node. This 00111 * design allow to implement something like a std::forward_list::insert_after 00112 * on container insertion and std::forward_list::erase_after on container 00113 * erase calls. _M_before_begin is equivalent to 00114 * std::foward_list::before_begin. Empty buckets are containing nullptr. 00115 * Note that one of the non-empty bucket contains &_M_before_begin which is 00116 * not a derefenrenceable node so the node pointers in buckets shall never be 00117 * derefenrenced, only its next node can be. 00118 * 00119 * Walk through a bucket nodes require a check on the hash code to see if the 00120 * node is still in the bucket. Such a design impose a quite efficient hash 00121 * functor and is one of the reasons it is highly advise to set 00122 * __cache_hash_code to true. 00123 * 00124 * The container iterators are simply built from nodes. This way incrementing 00125 * the iterator is perfectly efficient independent of how many empty buckets 00126 * there are in the container. 00127 * 00128 * On insert we compute element hash code and thanks to it find the bucket 00129 * index. If the element must be inserted on an empty bucket we add it at the 00130 * beginning of the singly linked list and make the bucket point to 00131 * _M_before_begin. The bucket that used to point to _M_before_begin, if any, 00132 * is updated to point to its new before begin node. 00133 * 00134 * On erase, the simple iterator design impose to use the hash functor to get 00135 * the index of the bucket to update. For this reason, when __cache_hash_code 00136 * is set to false, there is a static assertion that the hash functor cannot 00137 * throw. 00138 */ 00139 00140 template<typename _Key, typename _Value, typename _Allocator, 00141 typename _ExtractKey, typename _Equal, 00142 typename _H1, typename _H2, typename _Hash, 00143 typename _RehashPolicy, 00144 bool __cache_hash_code, 00145 bool __constant_iterators, 00146 bool __unique_keys> 00147 class _Hashtable 00148 : public __detail::_Rehash_base<_RehashPolicy, 00149 _Hashtable<_Key, _Value, _Allocator, 00150 _ExtractKey, 00151 _Equal, _H1, _H2, _Hash, 00152 _RehashPolicy, 00153 __cache_hash_code, 00154 __constant_iterators, 00155 __unique_keys> >, 00156 public __detail::_Hashtable_base<_Key, _Value, _ExtractKey, _Equal, 00157 _H1, _H2, _Hash, __cache_hash_code>, 00158 public __detail::_Map_base<_Key, _Value, _ExtractKey, __unique_keys, 00159 _Hashtable<_Key, _Value, _Allocator, 00160 _ExtractKey, 00161 _Equal, _H1, _H2, _Hash, 00162 _RehashPolicy, 00163 __cache_hash_code, 00164 __constant_iterators, 00165 __unique_keys> >, 00166 public __detail::_Equality_base<_ExtractKey, __unique_keys, 00167 _Hashtable<_Key, _Value, _Allocator, 00168 _ExtractKey, 00169 _Equal, _H1, _H2, _Hash, 00170 _RehashPolicy, 00171 __cache_hash_code, 00172 __constant_iterators, 00173 __unique_keys> > 00174 { 00175 template<typename _Cond> 00176 using __if_hash_code_cached 00177 = __or_<__not_<integral_constant<bool, __cache_hash_code>>, _Cond>; 00178 00179 template<typename _Cond> 00180 using __if_hash_code_not_cached 00181 = __or_<integral_constant<bool, __cache_hash_code>, _Cond>; 00182 00183 // When hash codes are not cached the hash functor shall not throw 00184 // because it is used in methods (erase, swap...) that shall not throw. 00185 static_assert(__if_hash_code_not_cached<__detail::__is_noexcept_hash<_Key, 00186 _H1>>::value, 00187 "Cache the hash code or qualify your hash functor with noexcept"); 00188 00189 // Following two static assertions are necessary to guarantee that 00190 // swapping two hashtable instances won't invalidate associated local 00191 // iterators. 00192 00193 // When hash codes are cached local iterator only uses H2 which must then 00194 // be empty. 00195 static_assert(__if_hash_code_cached<is_empty<_H2>>::value, 00196 "Functor used to map hash code to bucket index must be empty"); 00197 00198 typedef __detail::_Hash_code_base<_Key, _Value, _ExtractKey, 00199 _H1, _H2, _Hash, 00200 __cache_hash_code> _HCBase; 00201 00202 // When hash codes are not cached local iterator is going to use _HCBase 00203 // above to compute node bucket index so it has to be empty. 00204 static_assert(__if_hash_code_not_cached<is_empty<_HCBase>>::value, 00205 "Cache the hash code or make functors involved in hash code" 00206 " and bucket index computation empty"); 00207 00208 public: 00209 typedef _Allocator allocator_type; 00210 typedef _Value value_type; 00211 typedef _Key key_type; 00212 typedef _Equal key_equal; 00213 // mapped_type, if present, comes from _Map_base. 00214 // hasher, if present, comes from _Hash_code_base. 00215 typedef typename _Allocator::pointer pointer; 00216 typedef typename _Allocator::const_pointer const_pointer; 00217 typedef typename _Allocator::reference reference; 00218 typedef typename _Allocator::const_reference const_reference; 00219 00220 typedef std::size_t size_type; 00221 typedef std::ptrdiff_t difference_type; 00222 typedef __detail::_Local_iterator<key_type, value_type, _ExtractKey, 00223 _H1, _H2, _Hash, 00224 __constant_iterators, 00225 __cache_hash_code> 00226 local_iterator; 00227 typedef __detail::_Local_const_iterator<key_type, value_type, _ExtractKey, 00228 _H1, _H2, _Hash, 00229 __constant_iterators, 00230 __cache_hash_code> 00231 const_local_iterator; 00232 typedef __detail::_Node_iterator<value_type, __constant_iterators, 00233 __cache_hash_code> 00234 iterator; 00235 typedef __detail::_Node_const_iterator<value_type, 00236 __constant_iterators, 00237 __cache_hash_code> 00238 const_iterator; 00239 00240 template<typename _Key2, typename _Value2, typename _Ex2, bool __unique2, 00241 typename _Hashtable2> 00242 friend struct __detail::_Map_base; 00243 00244 private: 00245 typedef typename _RehashPolicy::_State _RehashPolicyState; 00246 typedef __detail::_Hash_node<_Value, __cache_hash_code> _Node; 00247 typedef typename _Allocator::template rebind<_Node>::other 00248 _Node_allocator_type; 00249 typedef __detail::_Hash_node_base _BaseNode; 00250 typedef _BaseNode* _Bucket; 00251 typedef typename _Allocator::template rebind<_Bucket>::other 00252 _Bucket_allocator_type; 00253 00254 typedef typename _Allocator::template rebind<_Value>::other 00255 _Value_allocator_type; 00256 00257 _Node_allocator_type _M_node_allocator; 00258 _Bucket* _M_buckets; 00259 size_type _M_bucket_count; 00260 _BaseNode _M_before_begin; 00261 size_type _M_element_count; 00262 _RehashPolicy _M_rehash_policy; 00263 00264 template<typename... _Args> 00265 _Node* 00266 _M_allocate_node(_Args&&... __args); 00267 00268 void 00269 _M_deallocate_node(_Node* __n); 00270 00271 // Deallocate the linked list of nodes pointed to by __n 00272 void 00273 _M_deallocate_nodes(_Node* __n); 00274 00275 _Bucket* 00276 _M_allocate_buckets(size_type __n); 00277 00278 void 00279 _M_deallocate_buckets(_Bucket*, size_type __n); 00280 00281 // Gets bucket begin, deals with the fact that non-empty buckets contain 00282 // their before begin node. 00283 _Node* 00284 _M_bucket_begin(size_type __bkt) const; 00285 00286 _Node* 00287 _M_begin() const 00288 { return static_cast<_Node*>(_M_before_begin._M_nxt); } 00289 00290 public: 00291 // Constructor, destructor, assignment, swap 00292 _Hashtable(size_type __bucket_hint, 00293 const _H1&, const _H2&, const _Hash&, 00294 const _Equal&, const _ExtractKey&, 00295 const allocator_type&); 00296 00297 template<typename _InputIterator> 00298 _Hashtable(_InputIterator __first, _InputIterator __last, 00299 size_type __bucket_hint, 00300 const _H1&, const _H2&, const _Hash&, 00301 const _Equal&, const _ExtractKey&, 00302 const allocator_type&); 00303 00304 _Hashtable(const _Hashtable&); 00305 00306 _Hashtable(_Hashtable&&); 00307 00308 _Hashtable& 00309 operator=(const _Hashtable& __ht) 00310 { 00311 _Hashtable __tmp(__ht); 00312 this->swap(__tmp); 00313 return *this; 00314 } 00315 00316 _Hashtable& 00317 operator=(_Hashtable&& __ht) 00318 { 00319 // NB: DR 1204. 00320 // NB: DR 675. 00321 this->clear(); 00322 this->swap(__ht); 00323 return *this; 00324 } 00325 00326 ~_Hashtable() noexcept; 00327 00328 void swap(_Hashtable&); 00329 00330 // Basic container operations 00331 iterator 00332 begin() noexcept 00333 { return iterator(_M_begin()); } 00334 00335 const_iterator 00336 begin() const noexcept 00337 { return const_iterator(_M_begin()); } 00338 00339 iterator 00340 end() noexcept 00341 { return iterator(nullptr); } 00342 00343 const_iterator 00344 end() const noexcept 00345 { return const_iterator(nullptr); } 00346 00347 const_iterator 00348 cbegin() const noexcept 00349 { return const_iterator(_M_begin()); } 00350 00351 const_iterator 00352 cend() const noexcept 00353 { return const_iterator(nullptr); } 00354 00355 size_type 00356 size() const noexcept 00357 { return _M_element_count; } 00358 00359 bool 00360 empty() const noexcept 00361 { return size() == 0; } 00362 00363 allocator_type 00364 get_allocator() const noexcept 00365 { return allocator_type(_M_node_allocator); } 00366 00367 size_type 00368 max_size() const noexcept 00369 { return _M_node_allocator.max_size(); } 00370 00371 // Observers 00372 key_equal 00373 key_eq() const 00374 { return this->_M_eq(); } 00375 00376 // hash_function, if present, comes from _Hash_code_base. 00377 00378 // Bucket operations 00379 size_type 00380 bucket_count() const noexcept 00381 { return _M_bucket_count; } 00382 00383 size_type 00384 max_bucket_count() const noexcept 00385 { return max_size(); } 00386 00387 size_type 00388 bucket_size(size_type __n) const 00389 { return std::distance(begin(__n), end(__n)); } 00390 00391 size_type 00392 bucket(const key_type& __k) const 00393 { return _M_bucket_index(__k, this->_M_hash_code(__k)); } 00394 00395 local_iterator 00396 begin(size_type __n) 00397 { return local_iterator(_M_bucket_begin(__n), __n, 00398 _M_bucket_count); } 00399 00400 local_iterator 00401 end(size_type __n) 00402 { return local_iterator(nullptr, __n, _M_bucket_count); } 00403 00404 const_local_iterator 00405 begin(size_type __n) const 00406 { return const_local_iterator(_M_bucket_begin(__n), __n, 00407 _M_bucket_count); } 00408 00409 const_local_iterator 00410 end(size_type __n) const 00411 { return const_local_iterator(nullptr, __n, _M_bucket_count); } 00412 00413 // DR 691. 00414 const_local_iterator 00415 cbegin(size_type __n) const 00416 { return const_local_iterator(_M_bucket_begin(__n), __n, 00417 _M_bucket_count); } 00418 00419 const_local_iterator 00420 cend(size_type __n) const 00421 { return const_local_iterator(nullptr, __n, _M_bucket_count); } 00422 00423 float 00424 load_factor() const noexcept 00425 { 00426 return static_cast<float>(size()) / static_cast<float>(bucket_count()); 00427 } 00428 00429 // max_load_factor, if present, comes from _Rehash_base. 00430 00431 // Generalization of max_load_factor. Extension, not found in TR1. Only 00432 // useful if _RehashPolicy is something other than the default. 00433 const _RehashPolicy& 00434 __rehash_policy() const 00435 { return _M_rehash_policy; } 00436 00437 void 00438 __rehash_policy(const _RehashPolicy&); 00439 00440 // Lookup. 00441 iterator 00442 find(const key_type& __k); 00443 00444 const_iterator 00445 find(const key_type& __k) const; 00446 00447 size_type 00448 count(const key_type& __k) const; 00449 00450 std::pair<iterator, iterator> 00451 equal_range(const key_type& __k); 00452 00453 std::pair<const_iterator, const_iterator> 00454 equal_range(const key_type& __k) const; 00455 00456 private: 00457 // Bucket index computation helpers. 00458 size_type 00459 _M_bucket_index(_Node* __n) const 00460 { return _HCBase::_M_bucket_index(__n, _M_bucket_count); } 00461 00462 size_type 00463 _M_bucket_index(const key_type& __k, 00464 typename _Hashtable::_Hash_code_type __c) const 00465 { return _HCBase::_M_bucket_index(__k, __c, _M_bucket_count); } 00466 00467 // Find and insert helper functions and types 00468 // Find the node before the one matching the criteria. 00469 _BaseNode* 00470 _M_find_before_node(size_type, const key_type&, 00471 typename _Hashtable::_Hash_code_type) const; 00472 00473 _Node* 00474 _M_find_node(size_type __bkt, const key_type& __key, 00475 typename _Hashtable::_Hash_code_type __c) const 00476 { 00477 _BaseNode* __before_n = _M_find_before_node(__bkt, __key, __c); 00478 if (__before_n) 00479 return static_cast<_Node*>(__before_n->_M_nxt); 00480 return nullptr; 00481 } 00482 00483 // Insert a node at the beginning of a bucket. 00484 void 00485 _M_insert_bucket_begin(size_type, _Node*); 00486 00487 // Remove the bucket first node 00488 void 00489 _M_remove_bucket_begin(size_type __bkt, _Node* __next_n, 00490 size_type __next_bkt); 00491 00492 // Get the node before __n in the bucket __bkt 00493 _BaseNode* 00494 _M_get_previous_node(size_type __bkt, _BaseNode* __n); 00495 00496 template<typename _Arg> 00497 iterator 00498 _M_insert_bucket(_Arg&&, size_type, 00499 typename _Hashtable::_Hash_code_type); 00500 00501 typedef typename std::conditional<__unique_keys, 00502 std::pair<iterator, bool>, 00503 iterator>::type 00504 _Insert_Return_Type; 00505 00506 typedef typename std::conditional<__unique_keys, 00507 std::_Select1st<_Insert_Return_Type>, 00508 std::_Identity<_Insert_Return_Type> 00509 >::type 00510 _Insert_Conv_Type; 00511 00512 protected: 00513 template<typename... _Args> 00514 std::pair<iterator, bool> 00515 _M_emplace(std::true_type, _Args&&... __args); 00516 00517 template<typename... _Args> 00518 iterator 00519 _M_emplace(std::false_type, _Args&&... __args); 00520 00521 template<typename _Arg> 00522 std::pair<iterator, bool> 00523 _M_insert(_Arg&&, std::true_type); 00524 00525 template<typename _Arg> 00526 iterator 00527 _M_insert(_Arg&&, std::false_type); 00528 00529 public: 00530 // Emplace, insert and erase 00531 template<typename... _Args> 00532 _Insert_Return_Type 00533 emplace(_Args&&... __args) 00534 { return _M_emplace(integral_constant<bool, __unique_keys>(), 00535 std::forward<_Args>(__args)...); } 00536 00537 template<typename... _Args> 00538 iterator 00539 emplace_hint(const_iterator, _Args&&... __args) 00540 { return _Insert_Conv_Type()(emplace(std::forward<_Args>(__args)...)); } 00541 00542 _Insert_Return_Type 00543 insert(const value_type& __v) 00544 { return _M_insert(__v, integral_constant<bool, __unique_keys>()); } 00545 00546 iterator 00547 insert(const_iterator, const value_type& __v) 00548 { return _Insert_Conv_Type()(insert(__v)); } 00549 00550 template<typename _Pair, typename = typename 00551 std::enable_if<__and_<integral_constant<bool, !__constant_iterators>, 00552 std::is_convertible<_Pair, 00553 value_type>>::value>::type> 00554 _Insert_Return_Type 00555 insert(_Pair&& __v) 00556 { return _M_insert(std::forward<_Pair>(__v), 00557 integral_constant<bool, __unique_keys>()); } 00558 00559 template<typename _Pair, typename = typename 00560 std::enable_if<__and_<integral_constant<bool, !__constant_iterators>, 00561 std::is_convertible<_Pair, 00562 value_type>>::value>::type> 00563 iterator 00564 insert(const_iterator, _Pair&& __v) 00565 { return _Insert_Conv_Type()(insert(std::forward<_Pair>(__v))); } 00566 00567 template<typename _InputIterator> 00568 void 00569 insert(_InputIterator __first, _InputIterator __last); 00570 00571 void 00572 insert(initializer_list<value_type> __l) 00573 { this->insert(__l.begin(), __l.end()); } 00574 00575 iterator 00576 erase(const_iterator); 00577 00578 // LWG 2059. 00579 iterator 00580 erase(iterator __it) 00581 { return erase(const_iterator(__it)); } 00582 00583 size_type 00584 erase(const key_type&); 00585 00586 iterator 00587 erase(const_iterator, const_iterator); 00588 00589 void 00590 clear() noexcept; 00591 00592 // Set number of buckets to be appropriate for container of n element. 00593 void rehash(size_type __n); 00594 00595 // DR 1189. 00596 // reserve, if present, comes from _Rehash_base. 00597 00598 private: 00599 // Helper rehash method used when keys are unique. 00600 void _M_rehash_aux(size_type __n, std::true_type); 00601 00602 // Helper rehash method used when keys can be non-unique. 00603 void _M_rehash_aux(size_type __n, std::false_type); 00604 00605 // Unconditionally change size of bucket array to n, restore hash policy 00606 // state to __state on exception. 00607 void _M_rehash(size_type __n, const _RehashPolicyState& __state); 00608 }; 00609 00610 00611 // Definitions of class template _Hashtable's out-of-line member functions. 00612 template<typename _Key, typename _Value, 00613 typename _Allocator, typename _ExtractKey, typename _Equal, 00614 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 00615 bool __chc, bool __cit, bool __uk> 00616 template<typename... _Args> 00617 typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 00618 _H1, _H2, _Hash, _RehashPolicy, 00619 __chc, __cit, __uk>::_Node* 00620 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 00621 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 00622 _M_allocate_node(_Args&&... __args) 00623 { 00624 _Node* __n = _M_node_allocator.allocate(1); 00625 __try 00626 { 00627 _M_node_allocator.construct(__n, std::forward<_Args>(__args)...); 00628 return __n; 00629 } 00630 __catch(...) 00631 { 00632 _M_node_allocator.deallocate(__n, 1); 00633 __throw_exception_again; 00634 } 00635 } 00636 00637 template<typename _Key, typename _Value, 00638 typename _Allocator, typename _ExtractKey, typename _Equal, 00639 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 00640 bool __chc, bool __cit, bool __uk> 00641 void 00642 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 00643 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 00644 _M_deallocate_node(_Node* __n) 00645 { 00646 _M_node_allocator.destroy(__n); 00647 _M_node_allocator.deallocate(__n, 1); 00648 } 00649 00650 template<typename _Key, typename _Value, 00651 typename _Allocator, typename _ExtractKey, typename _Equal, 00652 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 00653 bool __chc, bool __cit, bool __uk> 00654 void 00655 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 00656 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 00657 _M_deallocate_nodes(_Node* __n) 00658 { 00659 while (__n) 00660 { 00661 _Node* __tmp = __n; 00662 __n = __n->_M_next(); 00663 _M_deallocate_node(__tmp); 00664 } 00665 } 00666 00667 template<typename _Key, typename _Value, 00668 typename _Allocator, typename _ExtractKey, typename _Equal, 00669 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 00670 bool __chc, bool __cit, bool __uk> 00671 typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 00672 _H1, _H2, _Hash, _RehashPolicy, 00673 __chc, __cit, __uk>::_Bucket* 00674 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 00675 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 00676 _M_allocate_buckets(size_type __n) 00677 { 00678 _Bucket_allocator_type __alloc(_M_node_allocator); 00679 00680 _Bucket* __p = __alloc.allocate(__n); 00681 __builtin_memset(__p, 0, __n * sizeof(_Bucket)); 00682 return __p; 00683 } 00684 00685 template<typename _Key, typename _Value, 00686 typename _Allocator, typename _ExtractKey, typename _Equal, 00687 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 00688 bool __chc, bool __cit, bool __uk> 00689 void 00690 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 00691 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 00692 _M_deallocate_buckets(_Bucket* __p, size_type __n) 00693 { 00694 _Bucket_allocator_type __alloc(_M_node_allocator); 00695 __alloc.deallocate(__p, __n); 00696 } 00697 00698 template<typename _Key, typename _Value, 00699 typename _Allocator, typename _ExtractKey, typename _Equal, 00700 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 00701 bool __chc, bool __cit, bool __uk> 00702 typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, 00703 _Equal, _H1, _H2, _Hash, _RehashPolicy, 00704 __chc, __cit, __uk>::_Node* 00705 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 00706 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 00707 _M_bucket_begin(size_type __bkt) const 00708 { 00709 _BaseNode* __n = _M_buckets[__bkt]; 00710 return __n ? static_cast<_Node*>(__n->_M_nxt) : nullptr; 00711 } 00712 00713 template<typename _Key, typename _Value, 00714 typename _Allocator, typename _ExtractKey, typename _Equal, 00715 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 00716 bool __chc, bool __cit, bool __uk> 00717 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 00718 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 00719 _Hashtable(size_type __bucket_hint, 00720 const _H1& __h1, const _H2& __h2, const _Hash& __h, 00721 const _Equal& __eq, const _ExtractKey& __exk, 00722 const allocator_type& __a) 00723 : __detail::_Rehash_base<_RehashPolicy, _Hashtable>(), 00724 __detail::_Hashtable_base<_Key, _Value, _ExtractKey, _Equal, 00725 _H1, _H2, _Hash, __chc>(__exk, __h1, __h2, __h, 00726 __eq), 00727 __detail::_Map_base<_Key, _Value, _ExtractKey, __uk, _Hashtable>(), 00728 _M_node_allocator(__a), 00729 _M_bucket_count(0), 00730 _M_element_count(0), 00731 _M_rehash_policy() 00732 { 00733 _M_bucket_count = _M_rehash_policy._M_next_bkt(__bucket_hint); 00734 // We don't want the rehash policy to ask for the hashtable to shrink 00735 // on the first insertion so we need to reset its previous resize level. 00736 _M_rehash_policy._M_prev_resize = 0; 00737 _M_buckets = _M_allocate_buckets(_M_bucket_count); 00738 } 00739 00740 template<typename _Key, typename _Value, 00741 typename _Allocator, typename _ExtractKey, typename _Equal, 00742 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 00743 bool __chc, bool __cit, bool __uk> 00744 template<typename _InputIterator> 00745 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 00746 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 00747 _Hashtable(_InputIterator __f, _InputIterator __l, 00748 size_type __bucket_hint, 00749 const _H1& __h1, const _H2& __h2, const _Hash& __h, 00750 const _Equal& __eq, const _ExtractKey& __exk, 00751 const allocator_type& __a) 00752 : __detail::_Rehash_base<_RehashPolicy, _Hashtable>(), 00753 __detail::_Hashtable_base<_Key, _Value, _ExtractKey, _Equal, 00754 _H1, _H2, _Hash, __chc>(__exk, __h1, __h2, __h, 00755 __eq), 00756 __detail::_Map_base<_Key, _Value, _ExtractKey, __uk, _Hashtable>(), 00757 _M_node_allocator(__a), 00758 _M_bucket_count(0), 00759 _M_element_count(0), 00760 _M_rehash_policy() 00761 { 00762 _M_bucket_count = std::max(_M_rehash_policy._M_next_bkt(__bucket_hint), 00763 _M_rehash_policy. 00764 _M_bkt_for_elements(__detail:: 00765 __distance_fw(__f, 00766 __l))); 00767 // We don't want the rehash policy to ask for the hashtable to shrink 00768 // on the first insertion so we need to reset its previous resize 00769 // level. 00770 _M_rehash_policy._M_prev_resize = 0; 00771 _M_buckets = _M_allocate_buckets(_M_bucket_count); 00772 __try 00773 { 00774 for (; __f != __l; ++__f) 00775 this->insert(*__f); 00776 } 00777 __catch(...) 00778 { 00779 clear(); 00780 _M_deallocate_buckets(_M_buckets, _M_bucket_count); 00781 __throw_exception_again; 00782 } 00783 } 00784 00785 template<typename _Key, typename _Value, 00786 typename _Allocator, typename _ExtractKey, typename _Equal, 00787 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 00788 bool __chc, bool __cit, bool __uk> 00789 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 00790 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 00791 _Hashtable(const _Hashtable& __ht) 00792 : __detail::_Rehash_base<_RehashPolicy, _Hashtable>(__ht), 00793 __detail::_Hashtable_base<_Key, _Value, _ExtractKey, _Equal, 00794 _H1, _H2, _Hash, __chc>(__ht), 00795 __detail::_Map_base<_Key, _Value, _ExtractKey, __uk, _Hashtable>(__ht), 00796 _M_node_allocator(__ht._M_node_allocator), 00797 _M_bucket_count(__ht._M_bucket_count), 00798 _M_element_count(__ht._M_element_count), 00799 _M_rehash_policy(__ht._M_rehash_policy) 00800 { 00801 _M_buckets = _M_allocate_buckets(_M_bucket_count); 00802 __try 00803 { 00804 if (!__ht._M_before_begin._M_nxt) 00805 return; 00806 00807 // First deal with the special first node pointed to by 00808 // _M_before_begin. 00809 const _Node* __ht_n = __ht._M_begin(); 00810 _Node* __this_n = _M_allocate_node(__ht_n->_M_v); 00811 this->_M_copy_code(__this_n, __ht_n); 00812 _M_before_begin._M_nxt = __this_n; 00813 _M_buckets[_M_bucket_index(__this_n)] = &_M_before_begin; 00814 00815 // Then deal with other nodes. 00816 _BaseNode* __prev_n = __this_n; 00817 for (__ht_n = __ht_n->_M_next(); __ht_n; __ht_n = __ht_n->_M_next()) 00818 { 00819 __this_n = _M_allocate_node(__ht_n->_M_v); 00820 __prev_n->_M_nxt = __this_n; 00821 this->_M_copy_code(__this_n, __ht_n); 00822 size_type __bkt = _M_bucket_index(__this_n); 00823 if (!_M_buckets[__bkt]) 00824 _M_buckets[__bkt] = __prev_n; 00825 __prev_n = __this_n; 00826 } 00827 } 00828 __catch(...) 00829 { 00830 clear(); 00831 _M_deallocate_buckets(_M_buckets, _M_bucket_count); 00832 __throw_exception_again; 00833 } 00834 } 00835 00836 template<typename _Key, typename _Value, 00837 typename _Allocator, typename _ExtractKey, typename _Equal, 00838 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 00839 bool __chc, bool __cit, bool __uk> 00840 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 00841 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 00842 _Hashtable(_Hashtable&& __ht) 00843 : __detail::_Rehash_base<_RehashPolicy, _Hashtable>(__ht), 00844 __detail::_Hashtable_base<_Key, _Value, _ExtractKey, _Equal, 00845 _H1, _H2, _Hash, __chc>(__ht), 00846 __detail::_Map_base<_Key, _Value, _ExtractKey, __uk, _Hashtable>(__ht), 00847 _M_node_allocator(std::move(__ht._M_node_allocator)), 00848 _M_buckets(__ht._M_buckets), 00849 _M_bucket_count(__ht._M_bucket_count), 00850 _M_before_begin(__ht._M_before_begin._M_nxt), 00851 _M_element_count(__ht._M_element_count), 00852 _M_rehash_policy(__ht._M_rehash_policy) 00853 { 00854 // Update, if necessary, bucket pointing to before begin that hasn't move. 00855 if (_M_begin()) 00856 _M_buckets[_M_bucket_index(_M_begin())] = &_M_before_begin; 00857 __ht._M_rehash_policy = _RehashPolicy(); 00858 __ht._M_bucket_count = __ht._M_rehash_policy._M_next_bkt(0); 00859 __ht._M_buckets = __ht._M_allocate_buckets(__ht._M_bucket_count); 00860 __ht._M_before_begin._M_nxt = nullptr; 00861 __ht._M_element_count = 0; 00862 } 00863 00864 template<typename _Key, typename _Value, 00865 typename _Allocator, typename _ExtractKey, typename _Equal, 00866 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 00867 bool __chc, bool __cit, bool __uk> 00868 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 00869 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 00870 ~_Hashtable() noexcept 00871 { 00872 clear(); 00873 _M_deallocate_buckets(_M_buckets, _M_bucket_count); 00874 } 00875 00876 template<typename _Key, typename _Value, 00877 typename _Allocator, typename _ExtractKey, typename _Equal, 00878 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 00879 bool __chc, bool __cit, bool __uk> 00880 void 00881 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 00882 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 00883 swap(_Hashtable& __x) 00884 { 00885 // The only base class with member variables is hash_code_base. We 00886 // define _Hash_code_base::_M_swap because different specializations 00887 // have different members. 00888 this->_M_swap(__x); 00889 00890 // _GLIBCXX_RESOLVE_LIB_DEFECTS 00891 // 431. Swapping containers with unequal allocators. 00892 std::__alloc_swap<_Node_allocator_type>::_S_do_it(_M_node_allocator, 00893 __x._M_node_allocator); 00894 00895 std::swap(_M_rehash_policy, __x._M_rehash_policy); 00896 std::swap(_M_buckets, __x._M_buckets); 00897 std::swap(_M_bucket_count, __x._M_bucket_count); 00898 std::swap(_M_before_begin._M_nxt, __x._M_before_begin._M_nxt); 00899 std::swap(_M_element_count, __x._M_element_count); 00900 // Fix buckets containing the _M_before_begin pointers that can't be 00901 // swapped. 00902 if (_M_begin()) 00903 _M_buckets[_M_bucket_index(_M_begin())] = &_M_before_begin; 00904 if (__x._M_begin()) 00905 __x._M_buckets[__x._M_bucket_index(__x._M_begin())] 00906 = &(__x._M_before_begin); 00907 } 00908 00909 template<typename _Key, typename _Value, 00910 typename _Allocator, typename _ExtractKey, typename _Equal, 00911 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 00912 bool __chc, bool __cit, bool __uk> 00913 void 00914 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 00915 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 00916 __rehash_policy(const _RehashPolicy& __pol) 00917 { 00918 size_type __n_bkt = __pol._M_bkt_for_elements(_M_element_count); 00919 if (__n_bkt != _M_bucket_count) 00920 _M_rehash(__n_bkt, _M_rehash_policy._M_state()); 00921 _M_rehash_policy = __pol; 00922 } 00923 00924 template<typename _Key, typename _Value, 00925 typename _Allocator, typename _ExtractKey, typename _Equal, 00926 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 00927 bool __chc, bool __cit, bool __uk> 00928 typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 00929 _H1, _H2, _Hash, _RehashPolicy, 00930 __chc, __cit, __uk>::iterator 00931 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 00932 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 00933 find(const key_type& __k) 00934 { 00935 typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k); 00936 std::size_t __n = _M_bucket_index(__k, __code); 00937 _Node* __p = _M_find_node(__n, __k, __code); 00938 return __p ? iterator(__p) : this->end(); 00939 } 00940 00941 template<typename _Key, typename _Value, 00942 typename _Allocator, typename _ExtractKey, typename _Equal, 00943 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 00944 bool __chc, bool __cit, bool __uk> 00945 typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 00946 _H1, _H2, _Hash, _RehashPolicy, 00947 __chc, __cit, __uk>::const_iterator 00948 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 00949 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 00950 find(const key_type& __k) const 00951 { 00952 typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k); 00953 std::size_t __n = _M_bucket_index(__k, __code); 00954 _Node* __p = _M_find_node(__n, __k, __code); 00955 return __p ? const_iterator(__p) : this->end(); 00956 } 00957 00958 template<typename _Key, typename _Value, 00959 typename _Allocator, typename _ExtractKey, typename _Equal, 00960 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 00961 bool __chc, bool __cit, bool __uk> 00962 typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 00963 _H1, _H2, _Hash, _RehashPolicy, 00964 __chc, __cit, __uk>::size_type 00965 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 00966 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 00967 count(const key_type& __k) const 00968 { 00969 typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k); 00970 std::size_t __n = _M_bucket_index(__k, __code); 00971 _Node* __p = _M_bucket_begin(__n); 00972 if (!__p) 00973 return 0; 00974 00975 std::size_t __result = 0; 00976 for (;; __p = __p->_M_next()) 00977 { 00978 if (this->_M_equals(__k, __code, __p)) 00979 ++__result; 00980 else if (__result) 00981 // All equivalent values are next to each other, if we found a not 00982 // equivalent value after an equivalent one it means that we won't 00983 // find anymore an equivalent value. 00984 break; 00985 if (!__p->_M_nxt || _M_bucket_index(__p->_M_next()) != __n) 00986 break; 00987 } 00988 return __result; 00989 } 00990 00991 template<typename _Key, typename _Value, 00992 typename _Allocator, typename _ExtractKey, typename _Equal, 00993 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 00994 bool __chc, bool __cit, bool __uk> 00995 std::pair<typename _Hashtable<_Key, _Value, _Allocator, 00996 _ExtractKey, _Equal, _H1, 00997 _H2, _Hash, _RehashPolicy, 00998 __chc, __cit, __uk>::iterator, 00999 typename _Hashtable<_Key, _Value, _Allocator, 01000 _ExtractKey, _Equal, _H1, 01001 _H2, _Hash, _RehashPolicy, 01002 __chc, __cit, __uk>::iterator> 01003 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 01004 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 01005 equal_range(const key_type& __k) 01006 { 01007 typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k); 01008 std::size_t __n = _M_bucket_index(__k, __code); 01009 _Node* __p = _M_find_node(__n, __k, __code); 01010 01011 if (__p) 01012 { 01013 _Node* __p1 = __p->_M_next(); 01014 while (__p1 && _M_bucket_index(__p1) == __n 01015 && this->_M_equals(__k, __code, __p1)) 01016 __p1 = __p1->_M_next(); 01017 01018 return std::make_pair(iterator(__p), iterator(__p1)); 01019 } 01020 else 01021 return std::make_pair(this->end(), this->end()); 01022 } 01023 01024 template<typename _Key, typename _Value, 01025 typename _Allocator, typename _ExtractKey, typename _Equal, 01026 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 01027 bool __chc, bool __cit, bool __uk> 01028 std::pair<typename _Hashtable<_Key, _Value, _Allocator, 01029 _ExtractKey, _Equal, _H1, 01030 _H2, _Hash, _RehashPolicy, 01031 __chc, __cit, __uk>::const_iterator, 01032 typename _Hashtable<_Key, _Value, _Allocator, 01033 _ExtractKey, _Equal, _H1, 01034 _H2, _Hash, _RehashPolicy, 01035 __chc, __cit, __uk>::const_iterator> 01036 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 01037 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 01038 equal_range(const key_type& __k) const 01039 { 01040 typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k); 01041 std::size_t __n = _M_bucket_index(__k, __code); 01042 _Node* __p = _M_find_node(__n, __k, __code); 01043 01044 if (__p) 01045 { 01046 _Node* __p1 = __p->_M_next(); 01047 while (__p1 && _M_bucket_index(__p1) == __n 01048 && this->_M_equals(__k, __code, __p1)) 01049 __p1 = __p1->_M_next(); 01050 01051 return std::make_pair(const_iterator(__p), const_iterator(__p1)); 01052 } 01053 else 01054 return std::make_pair(this->end(), this->end()); 01055 } 01056 01057 // Find the node whose key compares equal to k in the bucket n. Return nullptr 01058 // if no node is found. 01059 template<typename _Key, typename _Value, 01060 typename _Allocator, typename _ExtractKey, typename _Equal, 01061 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 01062 bool __chc, bool __cit, bool __uk> 01063 typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, 01064 _Equal, _H1, _H2, _Hash, _RehashPolicy, 01065 __chc, __cit, __uk>::_BaseNode* 01066 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 01067 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 01068 _M_find_before_node(size_type __n, const key_type& __k, 01069 typename _Hashtable::_Hash_code_type __code) const 01070 { 01071 _BaseNode* __prev_p = _M_buckets[__n]; 01072 if (!__prev_p) 01073 return nullptr; 01074 _Node* __p = static_cast<_Node*>(__prev_p->_M_nxt); 01075 for (;; __p = __p->_M_next()) 01076 { 01077 if (this->_M_equals(__k, __code, __p)) 01078 return __prev_p; 01079 if (!(__p->_M_nxt) || _M_bucket_index(__p->_M_next()) != __n) 01080 break; 01081 __prev_p = __p; 01082 } 01083 return nullptr; 01084 } 01085 01086 template<typename _Key, typename _Value, 01087 typename _Allocator, typename _ExtractKey, typename _Equal, 01088 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 01089 bool __chc, bool __cit, bool __uk> 01090 void 01091 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 01092 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 01093 _M_insert_bucket_begin(size_type __bkt, _Node* __new_node) 01094 { 01095 if (_M_buckets[__bkt]) 01096 { 01097 // Bucket is not empty, we just need to insert the new node after the 01098 // bucket before begin. 01099 __new_node->_M_nxt = _M_buckets[__bkt]->_M_nxt; 01100 _M_buckets[__bkt]->_M_nxt = __new_node; 01101 } 01102 else 01103 { 01104 // The bucket is empty, the new node is inserted at the beginning of 01105 // the singly linked list and the bucket will contain _M_before_begin 01106 // pointer. 01107 __new_node->_M_nxt = _M_before_begin._M_nxt; 01108 _M_before_begin._M_nxt = __new_node; 01109 if (__new_node->_M_nxt) 01110 // We must update former begin bucket that is pointing to 01111 // _M_before_begin. 01112 _M_buckets[_M_bucket_index(__new_node->_M_next())] = __new_node; 01113 _M_buckets[__bkt] = &_M_before_begin; 01114 } 01115 } 01116 01117 template<typename _Key, typename _Value, 01118 typename _Allocator, typename _ExtractKey, typename _Equal, 01119 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 01120 bool __chc, bool __cit, bool __uk> 01121 void 01122 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 01123 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 01124 _M_remove_bucket_begin(size_type __bkt, _Node* __next, size_type __next_bkt) 01125 { 01126 if (!__next || __next_bkt != __bkt) 01127 { 01128 // Bucket is now empty 01129 // First update next bucket if any 01130 if (__next) 01131 _M_buckets[__next_bkt] = _M_buckets[__bkt]; 01132 // Second update before begin node if necessary 01133 if (&_M_before_begin == _M_buckets[__bkt]) 01134 _M_before_begin._M_nxt = __next; 01135 _M_buckets[__bkt] = nullptr; 01136 } 01137 } 01138 01139 template<typename _Key, typename _Value, 01140 typename _Allocator, typename _ExtractKey, typename _Equal, 01141 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 01142 bool __chc, bool __cit, bool __uk> 01143 typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, 01144 _Equal, _H1, _H2, _Hash, _RehashPolicy, 01145 __chc, __cit, __uk>::_BaseNode* 01146 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 01147 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 01148 _M_get_previous_node(size_type __bkt, _BaseNode* __n) 01149 { 01150 _BaseNode* __prev_n = _M_buckets[__bkt]; 01151 while (__prev_n->_M_nxt != __n) 01152 __prev_n = __prev_n->_M_nxt; 01153 return __prev_n; 01154 } 01155 01156 template<typename _Key, typename _Value, 01157 typename _Allocator, typename _ExtractKey, typename _Equal, 01158 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 01159 bool __chc, bool __cit, bool __uk> 01160 template<typename... _Args> 01161 std::pair<typename _Hashtable<_Key, _Value, _Allocator, 01162 _ExtractKey, _Equal, _H1, 01163 _H2, _Hash, _RehashPolicy, 01164 __chc, __cit, __uk>::iterator, bool> 01165 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 01166 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 01167 _M_emplace(std::true_type, _Args&&... __args) 01168 { 01169 // First build the node to get access to the hash code 01170 _Node* __new_node = _M_allocate_node(std::forward<_Args>(__args)...); 01171 __try 01172 { 01173 const key_type& __k = this->_M_extract()(__new_node->_M_v); 01174 typename _Hashtable::_Hash_code_type __code 01175 = this->_M_hash_code(__k); 01176 size_type __bkt = _M_bucket_index(__k, __code); 01177 01178 if (_Node* __p = _M_find_node(__bkt, __k, __code)) 01179 { 01180 // There is already an equivalent node, no insertion 01181 _M_deallocate_node(__new_node); 01182 return std::make_pair(iterator(__p), false); 01183 } 01184 01185 // We are going to insert this node 01186 this->_M_store_code(__new_node, __code); 01187 const _RehashPolicyState& __saved_state 01188 = _M_rehash_policy._M_state(); 01189 std::pair<bool, std::size_t> __do_rehash 01190 = _M_rehash_policy._M_need_rehash(_M_bucket_count, 01191 _M_element_count, 1); 01192 01193 if (__do_rehash.first) 01194 { 01195 _M_rehash(__do_rehash.second, __saved_state); 01196 __bkt = _M_bucket_index(__k, __code); 01197 } 01198 01199 _M_insert_bucket_begin(__bkt, __new_node); 01200 ++_M_element_count; 01201 return std::make_pair(iterator(__new_node), true); 01202 } 01203 __catch(...) 01204 { 01205 _M_deallocate_node(__new_node); 01206 __throw_exception_again; 01207 } 01208 } 01209 01210 template<typename _Key, typename _Value, 01211 typename _Allocator, typename _ExtractKey, typename _Equal, 01212 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 01213 bool __chc, bool __cit, bool __uk> 01214 template<typename... _Args> 01215 typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 01216 _H1, _H2, _Hash, _RehashPolicy, 01217 __chc, __cit, __uk>::iterator 01218 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 01219 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 01220 _M_emplace(std::false_type, _Args&&... __args) 01221 { 01222 const _RehashPolicyState& __saved_state = _M_rehash_policy._M_state(); 01223 std::pair<bool, std::size_t> __do_rehash 01224 = _M_rehash_policy._M_need_rehash(_M_bucket_count, 01225 _M_element_count, 1); 01226 01227 // First build the node to get its hash code. 01228 _Node* __new_node = _M_allocate_node(std::forward<_Args>(__args)...); 01229 __try 01230 { 01231 const key_type& __k = this->_M_extract()(__new_node->_M_v); 01232 typename _Hashtable::_Hash_code_type __code 01233 = this->_M_hash_code(__k); 01234 this->_M_store_code(__new_node, __code); 01235 01236 // Second, do rehash if necessary. 01237 if (__do_rehash.first) 01238 _M_rehash(__do_rehash.second, __saved_state); 01239 01240 // Third, find the node before an equivalent one. 01241 size_type __bkt = _M_bucket_index(__k, __code); 01242 _BaseNode* __prev = _M_find_before_node(__bkt, __k, __code); 01243 01244 if (__prev) 01245 { 01246 // Insert after the node before the equivalent one. 01247 __new_node->_M_nxt = __prev->_M_nxt; 01248 __prev->_M_nxt = __new_node; 01249 } 01250 else 01251 // The inserted node has no equivalent in the hashtable. We must 01252 // insert the new node at the beginning of the bucket to preserve 01253 // equivalent elements relative positions. 01254 _M_insert_bucket_begin(__bkt, __new_node); 01255 ++_M_element_count; 01256 return iterator(__new_node); 01257 } 01258 __catch(...) 01259 { 01260 _M_deallocate_node(__new_node); 01261 __throw_exception_again; 01262 } 01263 } 01264 01265 // Insert v in bucket n (assumes no element with its key already present). 01266 template<typename _Key, typename _Value, 01267 typename _Allocator, typename _ExtractKey, typename _Equal, 01268 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 01269 bool __chc, bool __cit, bool __uk> 01270 template<typename _Arg> 01271 typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 01272 _H1, _H2, _Hash, _RehashPolicy, 01273 __chc, __cit, __uk>::iterator 01274 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 01275 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 01276 _M_insert_bucket(_Arg&& __v, size_type __n, 01277 typename _Hashtable::_Hash_code_type __code) 01278 { 01279 const _RehashPolicyState& __saved_state = _M_rehash_policy._M_state(); 01280 std::pair<bool, std::size_t> __do_rehash 01281 = _M_rehash_policy._M_need_rehash(_M_bucket_count, 01282 _M_element_count, 1); 01283 01284 if (__do_rehash.first) 01285 { 01286 const key_type& __k = this->_M_extract()(__v); 01287 __n = _HCBase::_M_bucket_index(__k, __code, __do_rehash.second); 01288 } 01289 01290 _Node* __new_node = nullptr; 01291 __try 01292 { 01293 // Allocate the new node before doing the rehash so that we 01294 // don't do a rehash if the allocation throws. 01295 __new_node = _M_allocate_node(std::forward<_Arg>(__v)); 01296 this->_M_store_code(__new_node, __code); 01297 if (__do_rehash.first) 01298 _M_rehash(__do_rehash.second, __saved_state); 01299 01300 _M_insert_bucket_begin(__n, __new_node); 01301 ++_M_element_count; 01302 return iterator(__new_node); 01303 } 01304 __catch(...) 01305 { 01306 if (!__new_node) 01307 _M_rehash_policy._M_reset(__saved_state); 01308 else 01309 _M_deallocate_node(__new_node); 01310 __throw_exception_again; 01311 } 01312 } 01313 01314 // Insert v if no element with its key is already present. 01315 template<typename _Key, typename _Value, 01316 typename _Allocator, typename _ExtractKey, typename _Equal, 01317 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 01318 bool __chc, bool __cit, bool __uk> 01319 template<typename _Arg> 01320 std::pair<typename _Hashtable<_Key, _Value, _Allocator, 01321 _ExtractKey, _Equal, _H1, 01322 _H2, _Hash, _RehashPolicy, 01323 __chc, __cit, __uk>::iterator, bool> 01324 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 01325 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 01326 _M_insert(_Arg&& __v, std::true_type) 01327 { 01328 const key_type& __k = this->_M_extract()(__v); 01329 typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k); 01330 size_type __n = _M_bucket_index(__k, __code); 01331 01332 if (_Node* __p = _M_find_node(__n, __k, __code)) 01333 return std::make_pair(iterator(__p), false); 01334 return std::make_pair(_M_insert_bucket(std::forward<_Arg>(__v), 01335 __n, __code), true); 01336 } 01337 01338 // Insert v unconditionally. 01339 template<typename _Key, typename _Value, 01340 typename _Allocator, typename _ExtractKey, typename _Equal, 01341 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 01342 bool __chc, bool __cit, bool __uk> 01343 template<typename _Arg> 01344 typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 01345 _H1, _H2, _Hash, _RehashPolicy, 01346 __chc, __cit, __uk>::iterator 01347 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 01348 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 01349 _M_insert(_Arg&& __v, std::false_type) 01350 { 01351 const _RehashPolicyState& __saved_state = _M_rehash_policy._M_state(); 01352 std::pair<bool, std::size_t> __do_rehash 01353 = _M_rehash_policy._M_need_rehash(_M_bucket_count, 01354 _M_element_count, 1); 01355 01356 // First compute the hash code so that we don't do anything if it throws. 01357 typename _Hashtable::_Hash_code_type __code 01358 = this->_M_hash_code(this->_M_extract()(__v)); 01359 01360 _Node* __new_node = nullptr; 01361 __try 01362 { 01363 // Second allocate new node so that we don't rehash if it throws. 01364 __new_node = _M_allocate_node(std::forward<_Arg>(__v)); 01365 this->_M_store_code(__new_node, __code); 01366 if (__do_rehash.first) 01367 _M_rehash(__do_rehash.second, __saved_state); 01368 01369 // Third, find the node before an equivalent one. 01370 size_type __bkt = _M_bucket_index(__new_node); 01371 _BaseNode* __prev 01372 = _M_find_before_node(__bkt, this->_M_extract()(__new_node->_M_v), 01373 __code); 01374 if (__prev) 01375 { 01376 // Insert after the node before the equivalent one. 01377 __new_node->_M_nxt = __prev->_M_nxt; 01378 __prev->_M_nxt = __new_node; 01379 } 01380 else 01381 // The inserted node has no equivalent in the hashtable. We must 01382 // insert the new node at the beginning of the bucket to preserve 01383 // equivalent elements relative positions. 01384 _M_insert_bucket_begin(__bkt, __new_node); 01385 ++_M_element_count; 01386 return iterator(__new_node); 01387 } 01388 __catch(...) 01389 { 01390 if (!__new_node) 01391 _M_rehash_policy._M_reset(__saved_state); 01392 else 01393 _M_deallocate_node(__new_node); 01394 __throw_exception_again; 01395 } 01396 } 01397 01398 template<typename _Key, typename _Value, 01399 typename _Allocator, typename _ExtractKey, typename _Equal, 01400 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 01401 bool __chc, bool __cit, bool __uk> 01402 template<typename _InputIterator> 01403 void 01404 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 01405 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 01406 insert(_InputIterator __first, _InputIterator __last) 01407 { 01408 size_type __n_elt = __detail::__distance_fw(__first, __last); 01409 const _RehashPolicyState& __saved_state = _M_rehash_policy._M_state(); 01410 std::pair<bool, std::size_t> __do_rehash 01411 = _M_rehash_policy._M_need_rehash(_M_bucket_count, 01412 _M_element_count, __n_elt); 01413 if (__do_rehash.first) 01414 _M_rehash(__do_rehash.second, __saved_state); 01415 01416 for (; __first != __last; ++__first) 01417 this->insert(*__first); 01418 } 01419 01420 template<typename _Key, typename _Value, 01421 typename _Allocator, typename _ExtractKey, typename _Equal, 01422 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 01423 bool __chc, bool __cit, bool __uk> 01424 typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 01425 _H1, _H2, _Hash, _RehashPolicy, 01426 __chc, __cit, __uk>::iterator 01427 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 01428 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 01429 erase(const_iterator __it) 01430 { 01431 _Node* __n = __it._M_cur; 01432 std::size_t __bkt = _M_bucket_index(__n); 01433 01434 // Look for previous node to unlink it from the erased one, this is why 01435 // we need buckets to contain the before begin to make this research fast. 01436 _BaseNode* __prev_n = _M_get_previous_node(__bkt, __n); 01437 if (__n == _M_bucket_begin(__bkt)) 01438 _M_remove_bucket_begin(__bkt, __n->_M_next(), 01439 __n->_M_nxt ? _M_bucket_index(__n->_M_next()) : 0); 01440 else if (__n->_M_nxt) 01441 { 01442 size_type __next_bkt = _M_bucket_index(__n->_M_next()); 01443 if (__next_bkt != __bkt) 01444 _M_buckets[__next_bkt] = __prev_n; 01445 } 01446 01447 __prev_n->_M_nxt = __n->_M_nxt; 01448 iterator __result(__n->_M_next()); 01449 _M_deallocate_node(__n); 01450 --_M_element_count; 01451 01452 return __result; 01453 } 01454 01455 template<typename _Key, typename _Value, 01456 typename _Allocator, typename _ExtractKey, typename _Equal, 01457 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 01458 bool __chc, bool __cit, bool __uk> 01459 typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 01460 _H1, _H2, _Hash, _RehashPolicy, 01461 __chc, __cit, __uk>::size_type 01462 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 01463 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 01464 erase(const key_type& __k) 01465 { 01466 typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k); 01467 std::size_t __bkt = _M_bucket_index(__k, __code); 01468 // Look for the node before the first matching node. 01469 _BaseNode* __prev_n = _M_find_before_node(__bkt, __k, __code); 01470 if (!__prev_n) 01471 return 0; 01472 _Node* __n = static_cast<_Node*>(__prev_n->_M_nxt); 01473 bool __is_bucket_begin = _M_buckets[__bkt] == __prev_n; 01474 01475 // We found a matching node, start deallocation loop from it 01476 std::size_t __next_bkt = __bkt; 01477 _Node* __next_n = __n; 01478 size_type __result = 0; 01479 _Node* __saved_n = nullptr; 01480 do 01481 { 01482 _Node* __p = __next_n; 01483 __next_n = __p->_M_next(); 01484 // _GLIBCXX_RESOLVE_LIB_DEFECTS 01485 // 526. Is it undefined if a function in the standard changes 01486 // in parameters? 01487 if (std::__addressof(this->_M_extract()(__p->_M_v)) 01488 != std::__addressof(__k)) 01489 _M_deallocate_node(__p); 01490 else 01491 __saved_n = __p; 01492 --_M_element_count; 01493 ++__result; 01494 if (!__next_n) 01495 break; 01496 __next_bkt = _M_bucket_index(__next_n); 01497 } 01498 while (__next_bkt == __bkt && this->_M_equals(__k, __code, __next_n)); 01499 01500 if (__saved_n) 01501 _M_deallocate_node(__saved_n); 01502 if (__is_bucket_begin) 01503 _M_remove_bucket_begin(__bkt, __next_n, __next_bkt); 01504 else if (__next_n && __next_bkt != __bkt) 01505 _M_buckets[__next_bkt] = __prev_n; 01506 if (__prev_n) 01507 __prev_n->_M_nxt = __next_n; 01508 return __result; 01509 } 01510 01511 template<typename _Key, typename _Value, 01512 typename _Allocator, typename _ExtractKey, typename _Equal, 01513 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 01514 bool __chc, bool __cit, bool __uk> 01515 typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 01516 _H1, _H2, _Hash, _RehashPolicy, 01517 __chc, __cit, __uk>::iterator 01518 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 01519 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 01520 erase(const_iterator __first, const_iterator __last) 01521 { 01522 _Node* __n = __first._M_cur; 01523 _Node* __last_n = __last._M_cur; 01524 if (__n == __last_n) 01525 return iterator(__n); 01526 01527 std::size_t __bkt = _M_bucket_index(__n); 01528 01529 _BaseNode* __prev_n = _M_get_previous_node(__bkt, __n); 01530 bool __is_bucket_begin = __n == _M_bucket_begin(__bkt); 01531 std::size_t __n_bkt = __bkt; 01532 for (;;) 01533 { 01534 do 01535 { 01536 _Node* __tmp = __n; 01537 __n = __n->_M_next(); 01538 _M_deallocate_node(__tmp); 01539 --_M_element_count; 01540 if (!__n) 01541 break; 01542 __n_bkt = _M_bucket_index(__n); 01543 } 01544 while (__n != __last_n && __n_bkt == __bkt); 01545 if (__is_bucket_begin) 01546 _M_remove_bucket_begin(__bkt, __n, __n_bkt); 01547 if (__n == __last_n) 01548 break; 01549 __is_bucket_begin = true; 01550 __bkt = __n_bkt; 01551 } 01552 01553 if (__n && (__n_bkt != __bkt || __is_bucket_begin)) 01554 _M_buckets[__n_bkt] = __prev_n; 01555 __prev_n->_M_nxt = __n; 01556 return iterator(__n); 01557 } 01558 01559 template<typename _Key, typename _Value, 01560 typename _Allocator, typename _ExtractKey, typename _Equal, 01561 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 01562 bool __chc, bool __cit, bool __uk> 01563 void 01564 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 01565 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 01566 clear() noexcept 01567 { 01568 _M_deallocate_nodes(_M_begin()); 01569 __builtin_memset(_M_buckets, 0, _M_bucket_count * sizeof(_Bucket)); 01570 _M_element_count = 0; 01571 _M_before_begin._M_nxt = nullptr; 01572 } 01573 01574 template<typename _Key, typename _Value, 01575 typename _Allocator, typename _ExtractKey, typename _Equal, 01576 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 01577 bool __chc, bool __cit, bool __uk> 01578 void 01579 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 01580 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 01581 rehash(size_type __n) 01582 { 01583 const _RehashPolicyState& __saved_state = _M_rehash_policy._M_state(); 01584 _M_rehash(std::max(_M_rehash_policy._M_next_bkt(__n), 01585 _M_rehash_policy._M_bkt_for_elements(_M_element_count 01586 + 1)), 01587 __saved_state); 01588 } 01589 01590 template<typename _Key, typename _Value, 01591 typename _Allocator, typename _ExtractKey, typename _Equal, 01592 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 01593 bool __chc, bool __cit, bool __uk> 01594 void 01595 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 01596 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 01597 _M_rehash(size_type __n, const _RehashPolicyState& __state) 01598 { 01599 __try 01600 { 01601 _M_rehash_aux(__n, integral_constant<bool, __uk>()); 01602 } 01603 __catch(...) 01604 { 01605 // A failure here means that buckets allocation failed. We only 01606 // have to restore hash policy previous state. 01607 _M_rehash_policy._M_reset(__state); 01608 __throw_exception_again; 01609 } 01610 } 01611 01612 // Rehash when there is no equivalent elements. 01613 template<typename _Key, typename _Value, 01614 typename _Allocator, typename _ExtractKey, typename _Equal, 01615 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 01616 bool __chc, bool __cit, bool __uk> 01617 void 01618 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 01619 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 01620 _M_rehash_aux(size_type __n, std::true_type) 01621 { 01622 _Bucket* __new_buckets = _M_allocate_buckets(__n); 01623 _Node* __p = _M_begin(); 01624 _M_before_begin._M_nxt = nullptr; 01625 std::size_t __bbegin_bkt; 01626 while (__p) 01627 { 01628 _Node* __next = __p->_M_next(); 01629 std::size_t __bkt = _HCBase::_M_bucket_index(__p, __n); 01630 if (!__new_buckets[__bkt]) 01631 { 01632 __p->_M_nxt = _M_before_begin._M_nxt; 01633 _M_before_begin._M_nxt = __p; 01634 __new_buckets[__bkt] = &_M_before_begin; 01635 if (__p->_M_nxt) 01636 __new_buckets[__bbegin_bkt] = __p; 01637 __bbegin_bkt = __bkt; 01638 } 01639 else 01640 { 01641 __p->_M_nxt = __new_buckets[__bkt]->_M_nxt; 01642 __new_buckets[__bkt]->_M_nxt = __p; 01643 } 01644 __p = __next; 01645 } 01646 _M_deallocate_buckets(_M_buckets, _M_bucket_count); 01647 _M_bucket_count = __n; 01648 _M_buckets = __new_buckets; 01649 } 01650 01651 // Rehash when there can be equivalent elements, preserve their relative 01652 // order. 01653 template<typename _Key, typename _Value, 01654 typename _Allocator, typename _ExtractKey, typename _Equal, 01655 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 01656 bool __chc, bool __cit, bool __uk> 01657 void 01658 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 01659 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 01660 _M_rehash_aux(size_type __n, std::false_type) 01661 { 01662 _Bucket* __new_buckets = _M_allocate_buckets(__n); 01663 01664 _Node* __p = _M_begin(); 01665 _M_before_begin._M_nxt = nullptr; 01666 std::size_t __bbegin_bkt; 01667 std::size_t __prev_bkt; 01668 _Node* __prev_p = nullptr; 01669 bool __check_bucket = false; 01670 01671 while (__p) 01672 { 01673 bool __check_now = true; 01674 _Node* __next = __p->_M_next(); 01675 std::size_t __bkt = _HCBase::_M_bucket_index(__p, __n); 01676 01677 if (!__new_buckets[__bkt]) 01678 { 01679 __p->_M_nxt = _M_before_begin._M_nxt; 01680 _M_before_begin._M_nxt = __p; 01681 __new_buckets[__bkt] = &_M_before_begin; 01682 if (__p->_M_nxt) 01683 __new_buckets[__bbegin_bkt] = __p; 01684 __bbegin_bkt = __bkt; 01685 } 01686 else 01687 { 01688 if (__prev_p && __prev_bkt == __bkt) 01689 { 01690 // Previous insert was already in this bucket, we insert after 01691 // the previously inserted one to preserve equivalent elements 01692 // relative order. 01693 __p->_M_nxt = __prev_p->_M_nxt; 01694 __prev_p->_M_nxt = __p; 01695 01696 // Inserting after a node in a bucket require to check that we 01697 // haven't change the bucket last node, in this case next 01698 // bucket containing its before begin node must be updated. We 01699 // schedule a check as soon as we move out of the sequence of 01700 // equivalent nodes to limit the number of checks. 01701 __check_bucket = true; 01702 __check_now = false; 01703 } 01704 else 01705 { 01706 __p->_M_nxt = __new_buckets[__bkt]->_M_nxt; 01707 __new_buckets[__bkt]->_M_nxt = __p; 01708 } 01709 } 01710 01711 if (__check_now && __check_bucket) 01712 { 01713 // Check if we shall update the next bucket because of insertions 01714 // into __prev_bkt bucket. 01715 if (__prev_p->_M_nxt) 01716 { 01717 std::size_t __next_bkt 01718 = _HCBase::_M_bucket_index(__prev_p->_M_next(), __n); 01719 if (__next_bkt != __prev_bkt) 01720 __new_buckets[__next_bkt] = __prev_p; 01721 } 01722 __check_bucket = false; 01723 } 01724 __prev_p = __p; 01725 __prev_bkt = __bkt; 01726 __p = __next; 01727 } 01728 01729 if (__check_bucket && __prev_p->_M_nxt) 01730 { 01731 std::size_t __next_bkt 01732 = _HCBase::_M_bucket_index(__prev_p->_M_next(), __n); 01733 if (__next_bkt != __prev_bkt) 01734 __new_buckets[__next_bkt] = __prev_p; 01735 } 01736 01737 _M_deallocate_buckets(_M_buckets, _M_bucket_count); 01738 _M_bucket_count = __n; 01739 _M_buckets = __new_buckets; 01740 } 01741 01742 _GLIBCXX_END_NAMESPACE_VERSION 01743 } // namespace std 01744 01745 #endif // _HASHTABLE_H