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