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