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