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