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 01226 if (__former_buckets) 01227 _M_deallocate_buckets(__former_buckets, __former_bucket_count); 01228 __ht.clear(); 01229 } 01230 __catch(...) 01231 { 01232 if (__former_buckets) 01233 { 01234 _M_deallocate_buckets(); 01235 _M_rehash_policy._M_reset(__former_state); 01236 _M_buckets = __former_buckets; 01237 _M_bucket_count = __former_bucket_count; 01238 } 01239 __builtin_memset(_M_buckets, 0, 01240 _M_bucket_count * sizeof(__bucket_type)); 01241 __throw_exception_again; 01242 } 01243 } 01244 } 01245 01246 template<typename _Key, typename _Value, 01247 typename _Alloc, typename _ExtractKey, typename _Equal, 01248 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 01249 typename _Traits> 01250 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, 01251 _H1, _H2, _Hash, _RehashPolicy, _Traits>:: 01252 _Hashtable(const _Hashtable& __ht) 01253 : __hashtable_base(__ht), 01254 __map_base(__ht), 01255 __rehash_base(__ht), 01256 __hashtable_alloc( 01257 __node_alloc_traits::_S_select_on_copy(__ht._M_node_allocator())), 01258 _M_buckets(nullptr), 01259 _M_bucket_count(__ht._M_bucket_count), 01260 _M_element_count(__ht._M_element_count), 01261 _M_rehash_policy(__ht._M_rehash_policy) 01262 { 01263 _M_assign(__ht, 01264 [this](const __node_type* __n) 01265 { return this->_M_allocate_node(__n->_M_v()); }); 01266 } 01267 01268 template<typename _Key, typename _Value, 01269 typename _Alloc, typename _ExtractKey, typename _Equal, 01270 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 01271 typename _Traits> 01272 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, 01273 _H1, _H2, _Hash, _RehashPolicy, _Traits>:: 01274 _Hashtable(_Hashtable&& __ht) noexcept 01275 : __hashtable_base(__ht), 01276 __map_base(__ht), 01277 __rehash_base(__ht), 01278 __hashtable_alloc(std::move(__ht._M_base_alloc())), 01279 _M_buckets(__ht._M_buckets), 01280 _M_bucket_count(__ht._M_bucket_count), 01281 _M_before_begin(__ht._M_before_begin._M_nxt), 01282 _M_element_count(__ht._M_element_count), 01283 _M_rehash_policy(__ht._M_rehash_policy) 01284 { 01285 // Update, if necessary, buckets if __ht is using its single bucket. 01286 if (__ht._M_uses_single_bucket()) 01287 { 01288 _M_buckets = &_M_single_bucket; 01289 _M_single_bucket = __ht._M_single_bucket; 01290 } 01291 01292 // Update, if necessary, bucket pointing to before begin that hasn't 01293 // moved. 01294 if (_M_begin()) 01295 _M_buckets[_M_bucket_index(_M_begin())] = &_M_before_begin; 01296 01297 __ht._M_reset(); 01298 } 01299 01300 template<typename _Key, typename _Value, 01301 typename _Alloc, typename _ExtractKey, typename _Equal, 01302 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 01303 typename _Traits> 01304 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, 01305 _H1, _H2, _Hash, _RehashPolicy, _Traits>:: 01306 _Hashtable(const _Hashtable& __ht, const allocator_type& __a) 01307 : __hashtable_base(__ht), 01308 __map_base(__ht), 01309 __rehash_base(__ht), 01310 __hashtable_alloc(__node_alloc_type(__a)), 01311 _M_buckets(), 01312 _M_bucket_count(__ht._M_bucket_count), 01313 _M_element_count(__ht._M_element_count), 01314 _M_rehash_policy(__ht._M_rehash_policy) 01315 { 01316 _M_assign(__ht, 01317 [this](const __node_type* __n) 01318 { return this->_M_allocate_node(__n->_M_v()); }); 01319 } 01320 01321 template<typename _Key, typename _Value, 01322 typename _Alloc, typename _ExtractKey, typename _Equal, 01323 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 01324 typename _Traits> 01325 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, 01326 _H1, _H2, _Hash, _RehashPolicy, _Traits>:: 01327 _Hashtable(_Hashtable&& __ht, const allocator_type& __a) 01328 : __hashtable_base(__ht), 01329 __map_base(__ht), 01330 __rehash_base(__ht), 01331 __hashtable_alloc(__node_alloc_type(__a)), 01332 _M_buckets(nullptr), 01333 _M_bucket_count(__ht._M_bucket_count), 01334 _M_element_count(__ht._M_element_count), 01335 _M_rehash_policy(__ht._M_rehash_policy) 01336 { 01337 if (__ht._M_node_allocator() == this->_M_node_allocator()) 01338 { 01339 if (__ht._M_uses_single_bucket()) 01340 { 01341 _M_buckets = &_M_single_bucket; 01342 _M_single_bucket = __ht._M_single_bucket; 01343 } 01344 else 01345 _M_buckets = __ht._M_buckets; 01346 01347 _M_before_begin._M_nxt = __ht._M_before_begin._M_nxt; 01348 // Update, if necessary, bucket pointing to before begin that hasn't 01349 // moved. 01350 if (_M_begin()) 01351 _M_buckets[_M_bucket_index(_M_begin())] = &_M_before_begin; 01352 __ht._M_reset(); 01353 } 01354 else 01355 { 01356 _M_assign(__ht, 01357 [this](__node_type* __n) 01358 { 01359 return this->_M_allocate_node( 01360 std::move_if_noexcept(__n->_M_v())); 01361 }); 01362 __ht.clear(); 01363 } 01364 } 01365 01366 template<typename _Key, typename _Value, 01367 typename _Alloc, typename _ExtractKey, typename _Equal, 01368 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 01369 typename _Traits> 01370 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, 01371 _H1, _H2, _Hash, _RehashPolicy, _Traits>:: 01372 ~_Hashtable() noexcept 01373 { 01374 clear(); 01375 _M_deallocate_buckets(); 01376 } 01377 01378 template<typename _Key, typename _Value, 01379 typename _Alloc, typename _ExtractKey, typename _Equal, 01380 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 01381 typename _Traits> 01382 void 01383 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, 01384 _H1, _H2, _Hash, _RehashPolicy, _Traits>:: 01385 swap(_Hashtable& __x) 01386 noexcept(__and_<__is_nothrow_swappable<_H1>, 01387 __is_nothrow_swappable<_Equal>>::value) 01388 { 01389 // The only base class with member variables is hash_code_base. 01390 // We define _Hash_code_base::_M_swap because different 01391 // specializations have different members. 01392 this->_M_swap(__x); 01393 01394 std::__alloc_on_swap(this->_M_node_allocator(), __x._M_node_allocator()); 01395 std::swap(_M_rehash_policy, __x._M_rehash_policy); 01396 01397 // Deal properly with potentially moved instances. 01398 if (this->_M_uses_single_bucket()) 01399 { 01400 if (!__x._M_uses_single_bucket()) 01401 { 01402 _M_buckets = __x._M_buckets; 01403 __x._M_buckets = &__x._M_single_bucket; 01404 } 01405 } 01406 else if (__x._M_uses_single_bucket()) 01407 { 01408 __x._M_buckets = _M_buckets; 01409 _M_buckets = &_M_single_bucket; 01410 } 01411 else 01412 std::swap(_M_buckets, __x._M_buckets); 01413 01414 std::swap(_M_bucket_count, __x._M_bucket_count); 01415 std::swap(_M_before_begin._M_nxt, __x._M_before_begin._M_nxt); 01416 std::swap(_M_element_count, __x._M_element_count); 01417 std::swap(_M_single_bucket, __x._M_single_bucket); 01418 01419 // Fix buckets containing the _M_before_begin pointers that can't be 01420 // swapped. 01421 if (_M_begin()) 01422 _M_buckets[_M_bucket_index(_M_begin())] = &_M_before_begin; 01423 01424 if (__x._M_begin()) 01425 __x._M_buckets[__x._M_bucket_index(__x._M_begin())] 01426 = &__x._M_before_begin; 01427 } 01428 01429 template<typename _Key, typename _Value, 01430 typename _Alloc, typename _ExtractKey, typename _Equal, 01431 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 01432 typename _Traits> 01433 auto 01434 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, 01435 _H1, _H2, _Hash, _RehashPolicy, _Traits>:: 01436 find(const key_type& __k) 01437 -> iterator 01438 { 01439 __hash_code __code = this->_M_hash_code(__k); 01440 std::size_t __n = _M_bucket_index(__k, __code); 01441 __node_type* __p = _M_find_node(__n, __k, __code); 01442 return __p ? iterator(__p) : end(); 01443 } 01444 01445 template<typename _Key, typename _Value, 01446 typename _Alloc, typename _ExtractKey, typename _Equal, 01447 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 01448 typename _Traits> 01449 auto 01450 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, 01451 _H1, _H2, _Hash, _RehashPolicy, _Traits>:: 01452 find(const key_type& __k) const 01453 -> const_iterator 01454 { 01455 __hash_code __code = this->_M_hash_code(__k); 01456 std::size_t __n = _M_bucket_index(__k, __code); 01457 __node_type* __p = _M_find_node(__n, __k, __code); 01458 return __p ? const_iterator(__p) : end(); 01459 } 01460 01461 template<typename _Key, typename _Value, 01462 typename _Alloc, typename _ExtractKey, typename _Equal, 01463 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 01464 typename _Traits> 01465 auto 01466 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, 01467 _H1, _H2, _Hash, _RehashPolicy, _Traits>:: 01468 count(const key_type& __k) const 01469 -> size_type 01470 { 01471 __hash_code __code = this->_M_hash_code(__k); 01472 std::size_t __n = _M_bucket_index(__k, __code); 01473 __node_type* __p = _M_bucket_begin(__n); 01474 if (!__p) 01475 return 0; 01476 01477 std::size_t __result = 0; 01478 for (;; __p = __p->_M_next()) 01479 { 01480 if (this->_M_equals(__k, __code, __p)) 01481 ++__result; 01482 else if (__result) 01483 // All equivalent values are next to each other, if we 01484 // found a non-equivalent value after an equivalent one it 01485 // means that we won't find any new equivalent value. 01486 break; 01487 if (!__p->_M_nxt || _M_bucket_index(__p->_M_next()) != __n) 01488 break; 01489 } 01490 return __result; 01491 } 01492 01493 template<typename _Key, typename _Value, 01494 typename _Alloc, typename _ExtractKey, typename _Equal, 01495 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 01496 typename _Traits> 01497 auto 01498 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, 01499 _H1, _H2, _Hash, _RehashPolicy, _Traits>:: 01500 equal_range(const key_type& __k) 01501 -> pair<iterator, iterator> 01502 { 01503 __hash_code __code = this->_M_hash_code(__k); 01504 std::size_t __n = _M_bucket_index(__k, __code); 01505 __node_type* __p = _M_find_node(__n, __k, __code); 01506 01507 if (__p) 01508 { 01509 __node_type* __p1 = __p->_M_next(); 01510 while (__p1 && _M_bucket_index(__p1) == __n 01511 && this->_M_equals(__k, __code, __p1)) 01512 __p1 = __p1->_M_next(); 01513 01514 return std::make_pair(iterator(__p), iterator(__p1)); 01515 } 01516 else 01517 return std::make_pair(end(), end()); 01518 } 01519 01520 template<typename _Key, typename _Value, 01521 typename _Alloc, typename _ExtractKey, typename _Equal, 01522 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 01523 typename _Traits> 01524 auto 01525 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, 01526 _H1, _H2, _Hash, _RehashPolicy, _Traits>:: 01527 equal_range(const key_type& __k) const 01528 -> pair<const_iterator, const_iterator> 01529 { 01530 __hash_code __code = this->_M_hash_code(__k); 01531 std::size_t __n = _M_bucket_index(__k, __code); 01532 __node_type* __p = _M_find_node(__n, __k, __code); 01533 01534 if (__p) 01535 { 01536 __node_type* __p1 = __p->_M_next(); 01537 while (__p1 && _M_bucket_index(__p1) == __n 01538 && this->_M_equals(__k, __code, __p1)) 01539 __p1 = __p1->_M_next(); 01540 01541 return std::make_pair(const_iterator(__p), const_iterator(__p1)); 01542 } 01543 else 01544 return std::make_pair(end(), end()); 01545 } 01546 01547 // Find the node whose key compares equal to k in the bucket n. 01548 // Return nullptr if no node is found. 01549 template<typename _Key, typename _Value, 01550 typename _Alloc, typename _ExtractKey, typename _Equal, 01551 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 01552 typename _Traits> 01553 auto 01554 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, 01555 _H1, _H2, _Hash, _RehashPolicy, _Traits>:: 01556 _M_find_before_node(size_type __n, const key_type& __k, 01557 __hash_code __code) const 01558 -> __node_base* 01559 { 01560 __node_base* __prev_p = _M_buckets[__n]; 01561 if (!__prev_p) 01562 return nullptr; 01563 01564 for (__node_type* __p = static_cast<__node_type*>(__prev_p->_M_nxt);; 01565 __p = __p->_M_next()) 01566 { 01567 if (this->_M_equals(__k, __code, __p)) 01568 return __prev_p; 01569 01570 if (!__p->_M_nxt || _M_bucket_index(__p->_M_next()) != __n) 01571 break; 01572 __prev_p = __p; 01573 } 01574 return nullptr; 01575 } 01576 01577 template<typename _Key, typename _Value, 01578 typename _Alloc, typename _ExtractKey, typename _Equal, 01579 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 01580 typename _Traits> 01581 void 01582 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, 01583 _H1, _H2, _Hash, _RehashPolicy, _Traits>:: 01584 _M_insert_bucket_begin(size_type __bkt, __node_type* __node) 01585 { 01586 if (_M_buckets[__bkt]) 01587 { 01588 // Bucket is not empty, we just need to insert the new node 01589 // after the bucket before begin. 01590 __node->_M_nxt = _M_buckets[__bkt]->_M_nxt; 01591 _M_buckets[__bkt]->_M_nxt = __node; 01592 } 01593 else 01594 { 01595 // The bucket is empty, the new node is inserted at the 01596 // beginning of the singly-linked list and the bucket will 01597 // contain _M_before_begin pointer. 01598 __node->_M_nxt = _M_before_begin._M_nxt; 01599 _M_before_begin._M_nxt = __node; 01600 if (__node->_M_nxt) 01601 // We must update former begin bucket that is pointing to 01602 // _M_before_begin. 01603 _M_buckets[_M_bucket_index(__node->_M_next())] = __node; 01604 _M_buckets[__bkt] = &_M_before_begin; 01605 } 01606 } 01607 01608 template<typename _Key, typename _Value, 01609 typename _Alloc, typename _ExtractKey, typename _Equal, 01610 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 01611 typename _Traits> 01612 void 01613 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, 01614 _H1, _H2, _Hash, _RehashPolicy, _Traits>:: 01615 _M_remove_bucket_begin(size_type __bkt, __node_type* __next, 01616 size_type __next_bkt) 01617 { 01618 if (!__next || __next_bkt != __bkt) 01619 { 01620 // Bucket is now empty 01621 // First update next bucket if any 01622 if (__next) 01623 _M_buckets[__next_bkt] = _M_buckets[__bkt]; 01624 01625 // Second update before begin node if necessary 01626 if (&_M_before_begin == _M_buckets[__bkt]) 01627 _M_before_begin._M_nxt = __next; 01628 _M_buckets[__bkt] = nullptr; 01629 } 01630 } 01631 01632 template<typename _Key, typename _Value, 01633 typename _Alloc, typename _ExtractKey, typename _Equal, 01634 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 01635 typename _Traits> 01636 auto 01637 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, 01638 _H1, _H2, _Hash, _RehashPolicy, _Traits>:: 01639 _M_get_previous_node(size_type __bkt, __node_base* __n) 01640 -> __node_base* 01641 { 01642 __node_base* __prev_n = _M_buckets[__bkt]; 01643 while (__prev_n->_M_nxt != __n) 01644 __prev_n = __prev_n->_M_nxt; 01645 return __prev_n; 01646 } 01647 01648 template<typename _Key, typename _Value, 01649 typename _Alloc, typename _ExtractKey, typename _Equal, 01650 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 01651 typename _Traits> 01652 template<typename... _Args> 01653 auto 01654 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, 01655 _H1, _H2, _Hash, _RehashPolicy, _Traits>:: 01656 _M_emplace(std::true_type, _Args&&... __args) 01657 -> pair<iterator, bool> 01658 { 01659 // First build the node to get access to the hash code 01660 __node_type* __node = this->_M_allocate_node(std::forward<_Args>(__args)...); 01661 const key_type& __k = this->_M_extract()(__node->_M_v()); 01662 __hash_code __code; 01663 __try 01664 { 01665 __code = this->_M_hash_code(__k); 01666 } 01667 __catch(...) 01668 { 01669 this->_M_deallocate_node(__node); 01670 __throw_exception_again; 01671 } 01672 01673 size_type __bkt = _M_bucket_index(__k, __code); 01674 if (__node_type* __p = _M_find_node(__bkt, __k, __code)) 01675 { 01676 // There is already an equivalent node, no insertion 01677 this->_M_deallocate_node(__node); 01678 return std::make_pair(iterator(__p), false); 01679 } 01680 01681 // Insert the node 01682 return std::make_pair(_M_insert_unique_node(__bkt, __code, __node), 01683 true); 01684 } 01685 01686 template<typename _Key, typename _Value, 01687 typename _Alloc, typename _ExtractKey, typename _Equal, 01688 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 01689 typename _Traits> 01690 template<typename... _Args> 01691 auto 01692 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, 01693 _H1, _H2, _Hash, _RehashPolicy, _Traits>:: 01694 _M_emplace(const_iterator __hint, std::false_type, _Args&&... __args) 01695 -> iterator 01696 { 01697 // First build the node to get its hash code. 01698 __node_type* __node = 01699 this->_M_allocate_node(std::forward<_Args>(__args)...); 01700 01701 __hash_code __code; 01702 __try 01703 { 01704 __code = this->_M_hash_code(this->_M_extract()(__node->_M_v())); 01705 } 01706 __catch(...) 01707 { 01708 this->_M_deallocate_node(__node); 01709 __throw_exception_again; 01710 } 01711 01712 return _M_insert_multi_node(__hint._M_cur, __code, __node); 01713 } 01714 01715 template<typename _Key, typename _Value, 01716 typename _Alloc, typename _ExtractKey, typename _Equal, 01717 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 01718 typename _Traits> 01719 auto 01720 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, 01721 _H1, _H2, _Hash, _RehashPolicy, _Traits>:: 01722 _M_insert_unique_node(size_type __bkt, __hash_code __code, 01723 __node_type* __node, size_type __n_elt) 01724 -> iterator 01725 { 01726 const __rehash_state& __saved_state = _M_rehash_policy._M_state(); 01727 std::pair<bool, std::size_t> __do_rehash 01728 = _M_rehash_policy._M_need_rehash(_M_bucket_count, _M_element_count, 01729 __n_elt); 01730 01731 __try 01732 { 01733 if (__do_rehash.first) 01734 { 01735 _M_rehash(__do_rehash.second, __saved_state); 01736 __bkt = _M_bucket_index(this->_M_extract()(__node->_M_v()), __code); 01737 } 01738 01739 this->_M_store_code(__node, __code); 01740 01741 // Always insert at the beginning of the bucket. 01742 _M_insert_bucket_begin(__bkt, __node); 01743 ++_M_element_count; 01744 return iterator(__node); 01745 } 01746 __catch(...) 01747 { 01748 this->_M_deallocate_node(__node); 01749 __throw_exception_again; 01750 } 01751 } 01752 01753 // Insert node, in bucket bkt if no rehash (assumes no element with its key 01754 // already present). Take ownership of the node, deallocate it on exception. 01755 template<typename _Key, typename _Value, 01756 typename _Alloc, typename _ExtractKey, typename _Equal, 01757 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 01758 typename _Traits> 01759 auto 01760 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, 01761 _H1, _H2, _Hash, _RehashPolicy, _Traits>:: 01762 _M_insert_multi_node(__node_type* __hint, __hash_code __code, 01763 __node_type* __node) 01764 -> iterator 01765 { 01766 const __rehash_state& __saved_state = _M_rehash_policy._M_state(); 01767 std::pair<bool, std::size_t> __do_rehash 01768 = _M_rehash_policy._M_need_rehash(_M_bucket_count, _M_element_count, 1); 01769 01770 __try 01771 { 01772 if (__do_rehash.first) 01773 _M_rehash(__do_rehash.second, __saved_state); 01774 01775 this->_M_store_code(__node, __code); 01776 const key_type& __k = this->_M_extract()(__node->_M_v()); 01777 size_type __bkt = _M_bucket_index(__k, __code); 01778 01779 // Find the node before an equivalent one or use hint if it exists and 01780 // if it is equivalent. 01781 __node_base* __prev 01782 = __builtin_expect(__hint != nullptr, false) 01783 && this->_M_equals(__k, __code, __hint) 01784 ? __hint 01785 : _M_find_before_node(__bkt, __k, __code); 01786 if (__prev) 01787 { 01788 // Insert after the node before the equivalent one. 01789 __node->_M_nxt = __prev->_M_nxt; 01790 __prev->_M_nxt = __node; 01791 if (__builtin_expect(__prev == __hint, false)) 01792 // hint might be the last bucket node, in this case we need to 01793 // update next bucket. 01794 if (__node->_M_nxt 01795 && !this->_M_equals(__k, __code, __node->_M_next())) 01796 { 01797 size_type __next_bkt = _M_bucket_index(__node->_M_next()); 01798 if (__next_bkt != __bkt) 01799 _M_buckets[__next_bkt] = __node; 01800 } 01801 } 01802 else 01803 // The inserted node has no equivalent in the 01804 // hashtable. We must insert the new node at the 01805 // beginning of the bucket to preserve equivalent 01806 // elements' relative positions. 01807 _M_insert_bucket_begin(__bkt, __node); 01808 ++_M_element_count; 01809 return iterator(__node); 01810 } 01811 __catch(...) 01812 { 01813 this->_M_deallocate_node(__node); 01814 __throw_exception_again; 01815 } 01816 } 01817 01818 // Insert v if no element with its key is already present. 01819 template<typename _Key, typename _Value, 01820 typename _Alloc, typename _ExtractKey, typename _Equal, 01821 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 01822 typename _Traits> 01823 template<typename _Arg, typename _NodeGenerator> 01824 auto 01825 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, 01826 _H1, _H2, _Hash, _RehashPolicy, _Traits>:: 01827 _M_insert(_Arg&& __v, const _NodeGenerator& __node_gen, true_type, 01828 size_type __n_elt) 01829 -> pair<iterator, bool> 01830 { 01831 const key_type& __k = this->_M_extract()(__v); 01832 __hash_code __code = this->_M_hash_code(__k); 01833 size_type __bkt = _M_bucket_index(__k, __code); 01834 01835 __node_type* __n = _M_find_node(__bkt, __k, __code); 01836 if (__n) 01837 return std::make_pair(iterator(__n), false); 01838 01839 __n = __node_gen(std::forward<_Arg>(__v)); 01840 return { _M_insert_unique_node(__bkt, __code, __n, __n_elt), true }; 01841 } 01842 01843 // Insert v unconditionally. 01844 template<typename _Key, typename _Value, 01845 typename _Alloc, typename _ExtractKey, typename _Equal, 01846 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 01847 typename _Traits> 01848 template<typename _Arg, typename _NodeGenerator> 01849 auto 01850 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, 01851 _H1, _H2, _Hash, _RehashPolicy, _Traits>:: 01852 _M_insert(const_iterator __hint, _Arg&& __v, 01853 const _NodeGenerator& __node_gen, false_type) 01854 -> iterator 01855 { 01856 // First compute the hash code so that we don't do anything if it 01857 // throws. 01858 __hash_code __code = this->_M_hash_code(this->_M_extract()(__v)); 01859 01860 // Second allocate new node so that we don't rehash if it throws. 01861 __node_type* __node = __node_gen(std::forward<_Arg>(__v)); 01862 01863 return _M_insert_multi_node(__hint._M_cur, __code, __node); 01864 } 01865 01866 template<typename _Key, typename _Value, 01867 typename _Alloc, typename _ExtractKey, typename _Equal, 01868 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 01869 typename _Traits> 01870 auto 01871 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, 01872 _H1, _H2, _Hash, _RehashPolicy, _Traits>:: 01873 erase(const_iterator __it) 01874 -> iterator 01875 { 01876 __node_type* __n = __it._M_cur; 01877 std::size_t __bkt = _M_bucket_index(__n); 01878 01879 // Look for previous node to unlink it from the erased one, this 01880 // is why we need buckets to contain the before begin to make 01881 // this search fast. 01882 __node_base* __prev_n = _M_get_previous_node(__bkt, __n); 01883 return _M_erase(__bkt, __prev_n, __n); 01884 } 01885 01886 template<typename _Key, typename _Value, 01887 typename _Alloc, typename _ExtractKey, typename _Equal, 01888 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 01889 typename _Traits> 01890 auto 01891 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, 01892 _H1, _H2, _Hash, _RehashPolicy, _Traits>:: 01893 _M_erase(size_type __bkt, __node_base* __prev_n, __node_type* __n) 01894 -> iterator 01895 { 01896 if (__prev_n == _M_buckets[__bkt]) 01897 _M_remove_bucket_begin(__bkt, __n->_M_next(), 01898 __n->_M_nxt ? _M_bucket_index(__n->_M_next()) : 0); 01899 else if (__n->_M_nxt) 01900 { 01901 size_type __next_bkt = _M_bucket_index(__n->_M_next()); 01902 if (__next_bkt != __bkt) 01903 _M_buckets[__next_bkt] = __prev_n; 01904 } 01905 01906 __prev_n->_M_nxt = __n->_M_nxt; 01907 iterator __result(__n->_M_next()); 01908 this->_M_deallocate_node(__n); 01909 --_M_element_count; 01910 01911 return __result; 01912 } 01913 01914 template<typename _Key, typename _Value, 01915 typename _Alloc, typename _ExtractKey, typename _Equal, 01916 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 01917 typename _Traits> 01918 auto 01919 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, 01920 _H1, _H2, _Hash, _RehashPolicy, _Traits>:: 01921 _M_erase(std::true_type, const key_type& __k) 01922 -> size_type 01923 { 01924 __hash_code __code = this->_M_hash_code(__k); 01925 std::size_t __bkt = _M_bucket_index(__k, __code); 01926 01927 // Look for the node before the first matching node. 01928 __node_base* __prev_n = _M_find_before_node(__bkt, __k, __code); 01929 if (!__prev_n) 01930 return 0; 01931 01932 // We found a matching node, erase it. 01933 __node_type* __n = static_cast<__node_type*>(__prev_n->_M_nxt); 01934 _M_erase(__bkt, __prev_n, __n); 01935 return 1; 01936 } 01937 01938 template<typename _Key, typename _Value, 01939 typename _Alloc, typename _ExtractKey, typename _Equal, 01940 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 01941 typename _Traits> 01942 auto 01943 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, 01944 _H1, _H2, _Hash, _RehashPolicy, _Traits>:: 01945 _M_erase(std::false_type, const key_type& __k) 01946 -> size_type 01947 { 01948 __hash_code __code = this->_M_hash_code(__k); 01949 std::size_t __bkt = _M_bucket_index(__k, __code); 01950 01951 // Look for the node before the first matching node. 01952 __node_base* __prev_n = _M_find_before_node(__bkt, __k, __code); 01953 if (!__prev_n) 01954 return 0; 01955 01956 // _GLIBCXX_RESOLVE_LIB_DEFECTS 01957 // 526. Is it undefined if a function in the standard changes 01958 // in parameters? 01959 // We use one loop to find all matching nodes and another to deallocate 01960 // them so that the key stays valid during the first loop. It might be 01961 // invalidated indirectly when destroying nodes. 01962 __node_type* __n = static_cast<__node_type*>(__prev_n->_M_nxt); 01963 __node_type* __n_last = __n; 01964 std::size_t __n_last_bkt = __bkt; 01965 do 01966 { 01967 __n_last = __n_last->_M_next(); 01968 if (!__n_last) 01969 break; 01970 __n_last_bkt = _M_bucket_index(__n_last); 01971 } 01972 while (__n_last_bkt == __bkt && this->_M_equals(__k, __code, __n_last)); 01973 01974 // Deallocate nodes. 01975 size_type __result = 0; 01976 do 01977 { 01978 __node_type* __p = __n->_M_next(); 01979 this->_M_deallocate_node(__n); 01980 __n = __p; 01981 ++__result; 01982 --_M_element_count; 01983 } 01984 while (__n != __n_last); 01985 01986 if (__prev_n == _M_buckets[__bkt]) 01987 _M_remove_bucket_begin(__bkt, __n_last, __n_last_bkt); 01988 else if (__n_last && __n_last_bkt != __bkt) 01989 _M_buckets[__n_last_bkt] = __prev_n; 01990 __prev_n->_M_nxt = __n_last; 01991 return __result; 01992 } 01993 01994 template<typename _Key, typename _Value, 01995 typename _Alloc, typename _ExtractKey, typename _Equal, 01996 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 01997 typename _Traits> 01998 auto 01999 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, 02000 _H1, _H2, _Hash, _RehashPolicy, _Traits>:: 02001 erase(const_iterator __first, const_iterator __last) 02002 -> iterator 02003 { 02004 __node_type* __n = __first._M_cur; 02005 __node_type* __last_n = __last._M_cur; 02006 if (__n == __last_n) 02007 return iterator(__n); 02008 02009 std::size_t __bkt = _M_bucket_index(__n); 02010 02011 __node_base* __prev_n = _M_get_previous_node(__bkt, __n); 02012 bool __is_bucket_begin = __n == _M_bucket_begin(__bkt); 02013 std::size_t __n_bkt = __bkt; 02014 for (;;) 02015 { 02016 do 02017 { 02018 __node_type* __tmp = __n; 02019 __n = __n->_M_next(); 02020 this->_M_deallocate_node(__tmp); 02021 --_M_element_count; 02022 if (!__n) 02023 break; 02024 __n_bkt = _M_bucket_index(__n); 02025 } 02026 while (__n != __last_n && __n_bkt == __bkt); 02027 if (__is_bucket_begin) 02028 _M_remove_bucket_begin(__bkt, __n, __n_bkt); 02029 if (__n == __last_n) 02030 break; 02031 __is_bucket_begin = true; 02032 __bkt = __n_bkt; 02033 } 02034 02035 if (__n && (__n_bkt != __bkt || __is_bucket_begin)) 02036 _M_buckets[__n_bkt] = __prev_n; 02037 __prev_n->_M_nxt = __n; 02038 return iterator(__n); 02039 } 02040 02041 template<typename _Key, typename _Value, 02042 typename _Alloc, typename _ExtractKey, typename _Equal, 02043 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 02044 typename _Traits> 02045 void 02046 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, 02047 _H1, _H2, _Hash, _RehashPolicy, _Traits>:: 02048 clear() noexcept 02049 { 02050 this->_M_deallocate_nodes(_M_begin()); 02051 __builtin_memset(_M_buckets, 0, _M_bucket_count * sizeof(__bucket_type)); 02052 _M_element_count = 0; 02053 _M_before_begin._M_nxt = nullptr; 02054 } 02055 02056 template<typename _Key, typename _Value, 02057 typename _Alloc, typename _ExtractKey, typename _Equal, 02058 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 02059 typename _Traits> 02060 void 02061 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, 02062 _H1, _H2, _Hash, _RehashPolicy, _Traits>:: 02063 rehash(size_type __n) 02064 { 02065 const __rehash_state& __saved_state = _M_rehash_policy._M_state(); 02066 std::size_t __buckets 02067 = std::max(_M_rehash_policy._M_bkt_for_elements(_M_element_count + 1), 02068 __n); 02069 __buckets = _M_rehash_policy._M_next_bkt(__buckets); 02070 02071 if (__buckets != _M_bucket_count) 02072 _M_rehash(__buckets, __saved_state); 02073 else 02074 // No rehash, restore previous state to keep a consistent state. 02075 _M_rehash_policy._M_reset(__saved_state); 02076 } 02077 02078 template<typename _Key, typename _Value, 02079 typename _Alloc, typename _ExtractKey, typename _Equal, 02080 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 02081 typename _Traits> 02082 void 02083 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, 02084 _H1, _H2, _Hash, _RehashPolicy, _Traits>:: 02085 _M_rehash(size_type __n, const __rehash_state& __state) 02086 { 02087 __try 02088 { 02089 _M_rehash_aux(__n, __unique_keys()); 02090 } 02091 __catch(...) 02092 { 02093 // A failure here means that buckets allocation failed. We only 02094 // have to restore hash policy previous state. 02095 _M_rehash_policy._M_reset(__state); 02096 __throw_exception_again; 02097 } 02098 } 02099 02100 // Rehash when there is no equivalent elements. 02101 template<typename _Key, typename _Value, 02102 typename _Alloc, typename _ExtractKey, typename _Equal, 02103 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 02104 typename _Traits> 02105 void 02106 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, 02107 _H1, _H2, _Hash, _RehashPolicy, _Traits>:: 02108 _M_rehash_aux(size_type __n, std::true_type) 02109 { 02110 __bucket_type* __new_buckets = _M_allocate_buckets(__n); 02111 __node_type* __p = _M_begin(); 02112 _M_before_begin._M_nxt = nullptr; 02113 std::size_t __bbegin_bkt = 0; 02114 while (__p) 02115 { 02116 __node_type* __next = __p->_M_next(); 02117 std::size_t __bkt = __hash_code_base::_M_bucket_index(__p, __n); 02118 if (!__new_buckets[__bkt]) 02119 { 02120 __p->_M_nxt = _M_before_begin._M_nxt; 02121 _M_before_begin._M_nxt = __p; 02122 __new_buckets[__bkt] = &_M_before_begin; 02123 if (__p->_M_nxt) 02124 __new_buckets[__bbegin_bkt] = __p; 02125 __bbegin_bkt = __bkt; 02126 } 02127 else 02128 { 02129 __p->_M_nxt = __new_buckets[__bkt]->_M_nxt; 02130 __new_buckets[__bkt]->_M_nxt = __p; 02131 } 02132 __p = __next; 02133 } 02134 02135 _M_deallocate_buckets(); 02136 _M_bucket_count = __n; 02137 _M_buckets = __new_buckets; 02138 } 02139 02140 // Rehash when there can be equivalent elements, preserve their relative 02141 // order. 02142 template<typename _Key, typename _Value, 02143 typename _Alloc, typename _ExtractKey, typename _Equal, 02144 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 02145 typename _Traits> 02146 void 02147 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, 02148 _H1, _H2, _Hash, _RehashPolicy, _Traits>:: 02149 _M_rehash_aux(size_type __n, std::false_type) 02150 { 02151 __bucket_type* __new_buckets = _M_allocate_buckets(__n); 02152 02153 __node_type* __p = _M_begin(); 02154 _M_before_begin._M_nxt = nullptr; 02155 std::size_t __bbegin_bkt = 0; 02156 std::size_t __prev_bkt = 0; 02157 __node_type* __prev_p = nullptr; 02158 bool __check_bucket = false; 02159 02160 while (__p) 02161 { 02162 __node_type* __next = __p->_M_next(); 02163 std::size_t __bkt = __hash_code_base::_M_bucket_index(__p, __n); 02164 02165 if (__prev_p && __prev_bkt == __bkt) 02166 { 02167 // Previous insert was already in this bucket, we insert after 02168 // the previously inserted one to preserve equivalent elements 02169 // relative order. 02170 __p->_M_nxt = __prev_p->_M_nxt; 02171 __prev_p->_M_nxt = __p; 02172 02173 // Inserting after a node in a bucket require to check that we 02174 // haven't change the bucket last node, in this case next 02175 // bucket containing its before begin node must be updated. We 02176 // schedule a check as soon as we move out of the sequence of 02177 // equivalent nodes to limit the number of checks. 02178 __check_bucket = true; 02179 } 02180 else 02181 { 02182 if (__check_bucket) 02183 { 02184 // Check if we shall update the next bucket because of 02185 // insertions into __prev_bkt bucket. 02186 if (__prev_p->_M_nxt) 02187 { 02188 std::size_t __next_bkt 02189 = __hash_code_base::_M_bucket_index(__prev_p->_M_next(), 02190 __n); 02191 if (__next_bkt != __prev_bkt) 02192 __new_buckets[__next_bkt] = __prev_p; 02193 } 02194 __check_bucket = false; 02195 } 02196 02197 if (!__new_buckets[__bkt]) 02198 { 02199 __p->_M_nxt = _M_before_begin._M_nxt; 02200 _M_before_begin._M_nxt = __p; 02201 __new_buckets[__bkt] = &_M_before_begin; 02202 if (__p->_M_nxt) 02203 __new_buckets[__bbegin_bkt] = __p; 02204 __bbegin_bkt = __bkt; 02205 } 02206 else 02207 { 02208 __p->_M_nxt = __new_buckets[__bkt]->_M_nxt; 02209 __new_buckets[__bkt]->_M_nxt = __p; 02210 } 02211 } 02212 __prev_p = __p; 02213 __prev_bkt = __bkt; 02214 __p = __next; 02215 } 02216 02217 if (__check_bucket && __prev_p->_M_nxt) 02218 { 02219 std::size_t __next_bkt 02220 = __hash_code_base::_M_bucket_index(__prev_p->_M_next(), __n); 02221 if (__next_bkt != __prev_bkt) 02222 __new_buckets[__next_bkt] = __prev_p; 02223 } 02224 02225 _M_deallocate_buckets(); 02226 _M_bucket_count = __n; 02227 _M_buckets = __new_buckets; 02228 } 02229 02230 #if __cplusplus > 201402L 02231 template<typename, typename, typename> class _Hash_merge_helper { }; 02232 #endif // C++17 02233 02234 _GLIBCXX_END_NAMESPACE_VERSION 02235 } // namespace std 02236 02237 #endif // _HASHTABLE_H