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