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