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