1 // hashtable.h header -*- C++ -*- 2 3 // Copyright (C) 2007-2020 Free Software Foundation, Inc. 4 // 5 // This file is part of the GNU ISO C++ Library. This library is free 6 // software; you can redistribute it and/or modify it under the 7 // terms of the GNU General Public License as published by the 8 // Free Software Foundation; either version 3, or (at your option) 9 // any later version. 10 11 // This library is distributed in the hope that it will be useful, 12 // but WITHOUT ANY WARRANTY; without even the implied warranty of 13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 14 // GNU General Public License for more details. 15 16 // Under Section 7 of GPL version 3, you are granted additional 17 // permissions described in the GCC Runtime Library Exception, version 18 // 3.1, as published by the Free Software Foundation. 19 20 // You should have received a copy of the GNU General Public License and 21 // a copy of the GCC Runtime Library Exception along with this program; 22 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see 23 // <http://www.gnu.org/licenses/>. 24 25 /** @file bits/hashtable.h 26 * This is an internal header file, included by other library headers. 27 * Do not attempt to use it directly. @headername{unordered_map, unordered_set} 28 */ 29 30 #ifndef _HASHTABLE_H 31 #define _HASHTABLE_H 1 32 33 #pragma GCC system_header 34 35 #include <bits/hashtable_policy.h> 36 #include <bits/enable_special_members.h> 37 #if __cplusplus > 201402L 38 # include <bits/node_handle.h> 39 #endif 40 41 namespace std _GLIBCXX_VISIBILITY(default) 42 { 43 _GLIBCXX_BEGIN_NAMESPACE_VERSION 44 45 template<typename _Tp, typename _Hash> 46 using __cache_default 47 = __not_<__and_<// Do not cache for fast hasher. 48 __is_fast_hash<_Hash>, 49 // Mandatory to have erase not throwing. 50 __is_nothrow_invocable<const _Hash&, const _Tp&>>>; 51 52 // Helper to conditionally delete the default constructor. 53 // The _Hash_node_base type is used to distinguish this specialization 54 // from any other potentially-overlapping subobjects of the hashtable. 55 template<typename _Equal, typename _Hash, typename _Allocator> 56 using _Hashtable_enable_default_ctor 57 = _Enable_default_constructor<__and_<is_default_constructible<_Equal>, 58 is_default_constructible<_Hash>, 59 is_default_constructible<_Allocator>>{}, 60 __detail::_Hash_node_base>; 61 62 /** 63 * Primary class template _Hashtable. 64 * 65 * @ingroup hashtable-detail 66 * 67 * @tparam _Value CopyConstructible type. 68 * 69 * @tparam _Key CopyConstructible type. 70 * 71 * @tparam _Alloc An allocator type 72 * ([lib.allocator.requirements]) whose _Alloc::value_type is 73 * _Value. As a conforming extension, we allow for 74 * _Alloc::value_type != _Value. 75 * 76 * @tparam _ExtractKey Function object that takes an object of type 77 * _Value and returns a value of type _Key. 78 * 79 * @tparam _Equal Function object that takes two objects of type k 80 * and returns a bool-like value that is true if the two objects 81 * are considered equal. 82 * 83 * @tparam _H1 The hash function. A unary function object with 84 * argument type _Key and result type size_t. Return values should 85 * be distributed over the entire range [0, numeric_limits<size_t>:::max()]. 86 * 87 * @tparam _H2 The range-hashing function (in the terminology of 88 * Tavori and Dreizin). A binary function object whose argument 89 * types and result type are all size_t. Given arguments r and N, 90 * the return value is in the range [0, N). 91 * 92 * @tparam _Hash The ranged hash function (Tavori and Dreizin). A 93 * binary function whose argument types are _Key and size_t and 94 * whose result type is size_t. Given arguments k and N, the 95 * return value is in the range [0, N). Default: hash(k, N) = 96 * h2(h1(k), N). If _Hash is anything other than the default, _H1 97 * and _H2 are ignored. 98 * 99 * @tparam _RehashPolicy Policy class with three members, all of 100 * which govern the bucket count. _M_next_bkt(n) returns a bucket 101 * count no smaller than n. _M_bkt_for_elements(n) returns a 102 * bucket count appropriate for an element count of n. 103 * _M_need_rehash(n_bkt, n_elt, n_ins) determines whether, if the 104 * current bucket count is n_bkt and the current element count is 105 * n_elt, we need to increase the bucket count. If so, returns 106 * make_pair(true, n), where n is the new bucket count. If not, 107 * returns make_pair(false, <anything>) 108 * 109 * @tparam _Traits Compile-time class with three boolean 110 * std::integral_constant members: __cache_hash_code, __constant_iterators, 111 * __unique_keys. 112 * 113 * Each _Hashtable data structure has: 114 * 115 * - _Bucket[] _M_buckets 116 * - _Hash_node_base _M_before_begin 117 * - size_type _M_bucket_count 118 * - size_type _M_element_count 119 * 120 * with _Bucket being _Hash_node* and _Hash_node containing: 121 * 122 * - _Hash_node* _M_next 123 * - Tp _M_value 124 * - size_t _M_hash_code if cache_hash_code is true 125 * 126 * In terms of Standard containers the hashtable is like the aggregation of: 127 * 128 * - std::forward_list<_Node> containing the elements 129 * - std::vector<std::forward_list<_Node>::iterator> representing the buckets 130 * 131 * The non-empty buckets contain the node before the first node in the 132 * bucket. This design makes it possible to implement something like a 133 * std::forward_list::insert_after on container insertion and 134 * std::forward_list::erase_after on container erase 135 * calls. _M_before_begin is equivalent to 136 * std::forward_list::before_begin. Empty buckets contain 137 * nullptr. Note that one of the non-empty buckets contains 138 * &_M_before_begin which is not a dereferenceable node so the 139 * node pointer in a bucket shall never be dereferenced, only its 140 * next node can be. 141 * 142 * Walking through a bucket's nodes requires a check on the hash code to 143 * see if each node is still in the bucket. Such a design assumes a 144 * quite efficient hash functor and is one of the reasons it is 145 * highly advisable to set __cache_hash_code to true. 146 * 147 * The container iterators are simply built from nodes. This way 148 * incrementing the iterator is perfectly efficient independent of 149 * how many empty buckets there are in the container. 150 * 151 * On insert we compute the element's hash code and use it to find the 152 * bucket index. If the element must be inserted in an empty bucket 153 * we add it at the beginning of the singly linked list and make the 154 * bucket point to _M_before_begin. The bucket that used to point to 155 * _M_before_begin, if any, is updated to point to its new before 156 * begin node. 157 * 158 * On erase, the simple iterator design requires using the hash 159 * functor to get the index of the bucket to update. For this 160 * reason, when __cache_hash_code is set to false the hash functor must 161 * not throw and this is enforced by a static assertion. 162 * 163 * Functionality is implemented by decomposition into base classes, 164 * where the derived _Hashtable class is used in _Map_base, 165 * _Insert, _Rehash_base, and _Equality base classes to access the 166 * "this" pointer. _Hashtable_base is used in the base classes as a 167 * non-recursive, fully-completed-type so that detailed nested type 168 * information, such as iterator type and node type, can be 169 * used. This is similar to the "Curiously Recurring Template 170 * Pattern" (CRTP) technique, but uses a reconstructed, not 171 * explicitly passed, template pattern. 172 * 173 * Base class templates are: 174 * - __detail::_Hashtable_base 175 * - __detail::_Map_base 176 * - __detail::_Insert 177 * - __detail::_Rehash_base 178 * - __detail::_Equality 179 */ 180 template<typename _Key, typename _Value, typename _Alloc, 181 typename _ExtractKey, typename _Equal, 182 typename _H1, typename _H2, typename _Hash, 183 typename _RehashPolicy, typename _Traits> 184 class _Hashtable 185 : public __detail::_Hashtable_base<_Key, _Value, _ExtractKey, _Equal, 186 _H1, _H2, _Hash, _Traits>, 187 public __detail::_Map_base<_Key, _Value, _Alloc, _ExtractKey, _Equal, 188 _H1, _H2, _Hash, _RehashPolicy, _Traits>, 189 public __detail::_Insert<_Key, _Value, _Alloc, _ExtractKey, _Equal, 190 _H1, _H2, _Hash, _RehashPolicy, _Traits>, 191 public __detail::_Rehash_base<_Key, _Value, _Alloc, _ExtractKey, _Equal, 192 _H1, _H2, _Hash, _RehashPolicy, _Traits>, 193 public __detail::_Equality<_Key, _Value, _Alloc, _ExtractKey, _Equal, 194 _H1, _H2, _Hash, _RehashPolicy, _Traits>, 195 private __detail::_Hashtable_alloc< 196 __alloc_rebind<_Alloc, 197 __detail::_Hash_node<_Value, 198 _Traits::__hash_cached::value>>>, 199 private _Hashtable_enable_default_ctor<_Equal, _H1, _Alloc> 200 { 201 static_assert(is_same<typename remove_cv<_Value>::type, _Value>::value, 202 "unordered container must have a non-const, non-volatile value_type"); 203 #if __cplusplus > 201703L || defined __STRICT_ANSI__ 204 static_assert(is_same<typename _Alloc::value_type, _Value>{}, 205 "unordered container must have the same value_type as its allocator"); 206 #endif 207 208 using __traits_type = _Traits; 209 using __hash_cached = typename __traits_type::__hash_cached; 210 using __node_type = __detail::_Hash_node<_Value, __hash_cached::value>; 211 using __node_alloc_type = __alloc_rebind<_Alloc, __node_type>; 212 213 using __hashtable_alloc = __detail::_Hashtable_alloc<__node_alloc_type>; 214 215 using __value_alloc_traits = 216 typename __hashtable_alloc::__value_alloc_traits; 217 using __node_alloc_traits = 218 typename __hashtable_alloc::__node_alloc_traits; 219 using __node_base = typename __hashtable_alloc::__node_base; 220 using __bucket_type = typename __hashtable_alloc::__bucket_type; 221 using __enable_default_ctor 222 = _Hashtable_enable_default_ctor<_Equal, _H1, _Alloc>; 223 224 public: 225 typedef _Key key_type; 226 typedef _Value value_type; 227 typedef _Alloc allocator_type; 228 typedef _Equal key_equal; 229 230 // mapped_type, if present, comes from _Map_base. 231 // hasher, if present, comes from _Hash_code_base/_Hashtable_base. 232 typedef typename __value_alloc_traits::pointer pointer; 233 typedef typename __value_alloc_traits::const_pointer const_pointer; 234 typedef value_type& reference; 235 typedef const value_type& const_reference; 236 237 private: 238 using __rehash_type = _RehashPolicy; 239 using __rehash_state = typename __rehash_type::_State; 240 241 using __constant_iterators = typename __traits_type::__constant_iterators; 242 using __unique_keys = typename __traits_type::__unique_keys; 243 244 using __key_extract = typename std::conditional< 245 __constant_iterators::value, 246 __detail::_Identity, 247 __detail::_Select1st>::type; 248 249 using __hashtable_base = __detail:: 250 _Hashtable_base<_Key, _Value, _ExtractKey, 251 _Equal, _H1, _H2, _Hash, _Traits>; 252 253 using __hash_code_base = typename __hashtable_base::__hash_code_base; 254 using __hash_code = typename __hashtable_base::__hash_code; 255 using __ireturn_type = typename __hashtable_base::__ireturn_type; 256 257 using __map_base = __detail::_Map_base<_Key, _Value, _Alloc, _ExtractKey, 258 _Equal, _H1, _H2, _Hash, 259 _RehashPolicy, _Traits>; 260 261 using __rehash_base = __detail::_Rehash_base<_Key, _Value, _Alloc, 262 _ExtractKey, _Equal, 263 _H1, _H2, _Hash, 264 _RehashPolicy, _Traits>; 265 266 using __eq_base = __detail::_Equality<_Key, _Value, _Alloc, _ExtractKey, 267 _Equal, _H1, _H2, _Hash, 268 _RehashPolicy, _Traits>; 269 270 using __reuse_or_alloc_node_gen_t = 271 __detail::_ReuseOrAllocNode<__node_alloc_type>; 272 using __alloc_node_gen_t = 273 __detail::_AllocNode<__node_alloc_type>; 274 275 // Simple RAII type for managing a node containing an element 276 struct _Scoped_node 277 { 278 // Take ownership of a node with a constructed element. 279 _Scoped_node(__node_type* __n, __hashtable_alloc* __h) 280 : _M_h(__h), _M_node(__n) { } 281 282 // Allocate a node and construct an element within it. 283 template<typename... _Args> 284 _Scoped_node(__hashtable_alloc* __h, _Args&&... __args) 285 : _M_h(__h), 286 _M_node(__h->_M_allocate_node(std::forward<_Args>(__args)...)) 287 { } 288 289 // Destroy element and deallocate node. 290 ~_Scoped_node() { if (_M_node) _M_h->_M_deallocate_node(_M_node); }; 291 292 _Scoped_node(const _Scoped_node&) = delete; 293 _Scoped_node& operator=(const _Scoped_node&) = delete; 294 295 __hashtable_alloc* _M_h; 296 __node_type* _M_node; 297 }; 298 299 template<typename _Ht> 300 static constexpr 301 typename conditional<std::is_lvalue_reference<_Ht>::value, 302 const value_type&, value_type&&>::type 303 __fwd_value_for(value_type& __val) noexcept 304 { return std::move(__val); } 305 306 // Metaprogramming for picking apart hash caching. 307 template<typename _Cond> 308 using __if_hash_cached = __or_<__not_<__hash_cached>, _Cond>; 309 310 template<typename _Cond> 311 using __if_hash_not_cached = __or_<__hash_cached, _Cond>; 312 313 // Compile-time diagnostics. 314 315 // _Hash_code_base has everything protected, so use this derived type to 316 // access it. 317 struct __hash_code_base_access : __hash_code_base 318 { using __hash_code_base::_M_bucket_index; }; 319 320 // Getting a bucket index from a node shall not throw because it is used 321 // in methods (erase, swap...) that shall not throw. 322 static_assert(noexcept(declval<const __hash_code_base_access&>() 323 ._M_bucket_index((const __node_type*)nullptr, 324 (std::size_t)0)), 325 "Cache the hash code or qualify your functors involved" 326 " in hash code and bucket index computation with noexcept"); 327 328 // When hash codes are cached local iterator inherits from H2 functor 329 // which must then be default constructible. 330 static_assert(__if_hash_cached<is_default_constructible<_H2>>::value, 331 "Functor used to map hash code to bucket index" 332 " must be default constructible"); 333 334 template<typename _Keya, typename _Valuea, typename _Alloca, 335 typename _ExtractKeya, typename _Equala, 336 typename _H1a, typename _H2a, typename _Hasha, 337 typename _RehashPolicya, typename _Traitsa, 338 bool _Unique_keysa> 339 friend struct __detail::_Map_base; 340 341 template<typename _Keya, typename _Valuea, typename _Alloca, 342 typename _ExtractKeya, typename _Equala, 343 typename _H1a, typename _H2a, typename _Hasha, 344 typename _RehashPolicya, typename _Traitsa> 345 friend struct __detail::_Insert_base; 346 347 template<typename _Keya, typename _Valuea, typename _Alloca, 348 typename _ExtractKeya, typename _Equala, 349 typename _H1a, typename _H2a, typename _Hasha, 350 typename _RehashPolicya, typename _Traitsa, 351 bool _Constant_iteratorsa> 352 friend struct __detail::_Insert; 353 354 template<typename _Keya, typename _Valuea, typename _Alloca, 355 typename _ExtractKeya, typename _Equala, 356 typename _H1a, typename _H2a, typename _Hasha, 357 typename _RehashPolicya, typename _Traitsa, 358 bool _Unique_keysa> 359 friend struct __detail::_Equality; 360 361 public: 362 using size_type = typename __hashtable_base::size_type; 363 using difference_type = typename __hashtable_base::difference_type; 364 365 using iterator = typename __hashtable_base::iterator; 366 using const_iterator = typename __hashtable_base::const_iterator; 367 368 using local_iterator = typename __hashtable_base::local_iterator; 369 using const_local_iterator = typename __hashtable_base:: 370 const_local_iterator; 371 372 #if __cplusplus > 201402L 373 using node_type = _Node_handle<_Key, _Value, __node_alloc_type>; 374 using insert_return_type = _Node_insert_return<iterator, node_type>; 375 #endif 376 377 private: 378 __bucket_type* _M_buckets = &_M_single_bucket; 379 size_type _M_bucket_count = 1; 380 __node_base _M_before_begin; 381 size_type _M_element_count = 0; 382 _RehashPolicy _M_rehash_policy; 383 384 // A single bucket used when only need for 1 bucket. Especially 385 // interesting in move semantic to leave hashtable with only 1 bucket 386 // which is not allocated so that we can have those operations noexcept 387 // qualified. 388 // Note that we can't leave hashtable with 0 bucket without adding 389 // numerous checks in the code to avoid 0 modulus. 390 __bucket_type _M_single_bucket = nullptr; 391 392 bool 393 _M_uses_single_bucket(__bucket_type* __bkts) const 394 { return __builtin_expect(__bkts == &_M_single_bucket, false); } 395 396 bool 397 _M_uses_single_bucket() const 398 { return _M_uses_single_bucket(_M_buckets); } 399 400 __hashtable_alloc& 401 _M_base_alloc() { return *this; } 402 403 __bucket_type* 404 _M_allocate_buckets(size_type __bkt_count) 405 { 406 if (__builtin_expect(__bkt_count == 1, false)) 407 { 408 _M_single_bucket = nullptr; 409 return &_M_single_bucket; 410 } 411 412 return __hashtable_alloc::_M_allocate_buckets(__bkt_count); 413 } 414 415 void 416 _M_deallocate_buckets(__bucket_type* __bkts, size_type __bkt_count) 417 { 418 if (_M_uses_single_bucket(__bkts)) 419 return; 420 421 __hashtable_alloc::_M_deallocate_buckets(__bkts, __bkt_count); 422 } 423 424 void 425 _M_deallocate_buckets() 426 { _M_deallocate_buckets(_M_buckets, _M_bucket_count); } 427 428 // Gets bucket begin, deals with the fact that non-empty buckets contain 429 // their before begin node. 430 __node_type* 431 _M_bucket_begin(size_type __bkt) const; 432 433 __node_type* 434 _M_begin() const 435 { return static_cast<__node_type*>(_M_before_begin._M_nxt); } 436 437 // Assign *this using another _Hashtable instance. Whether elements 438 // are copied or moved depends on the _Ht reference. 439 template<typename _Ht> 440 void 441 _M_assign_elements(_Ht&&); 442 443 template<typename _Ht, typename _NodeGenerator> 444 void 445 _M_assign(_Ht&&, const _NodeGenerator&); 446 447 void 448 _M_move_assign(_Hashtable&&, true_type); 449 450 void 451 _M_move_assign(_Hashtable&&, false_type); 452 453 void 454 _M_reset() noexcept; 455 456 _Hashtable(const _H1& __h1, const _H2& __h2, const _Hash& __h, 457 const _Equal& __eq, const _ExtractKey& __exk, 458 const allocator_type& __a) 459 : __hashtable_base(__exk, __h1, __h2, __h, __eq), 460 __hashtable_alloc(__node_alloc_type(__a)), 461 __enable_default_ctor(_Enable_default_constructor_tag{}) 462 { } 463 464 template<bool _No_realloc = true> 465 static constexpr bool 466 _S_nothrow_move() 467 { 468 #if __cplusplus <= 201402L 469 return __and_<__bool_constant<_No_realloc>, 470 is_nothrow_copy_constructible<_H1>, 471 is_nothrow_copy_constructible<_Equal>>::value; 472 #else 473 if constexpr (_No_realloc) 474 if constexpr (is_nothrow_copy_constructible<_H1>()) 475 return is_nothrow_copy_constructible<_Equal>(); 476 return false; 477 #endif 478 } 479 480 _Hashtable(_Hashtable&& __ht, __node_alloc_type&& __a, 481 true_type /* alloc always equal */) 482 noexcept(_S_nothrow_move()); 483 484 _Hashtable(_Hashtable&&, __node_alloc_type&&, 485 false_type /* alloc always equal */); 486 487 488 public: 489 // Constructor, destructor, assignment, swap 490 _Hashtable() = default; 491 _Hashtable(size_type __bkt_count_hint, 492 const _H1&, const _H2&, const _Hash&, 493 const _Equal&, const _ExtractKey&, 494 const allocator_type&); 495 496 template<typename _InputIterator> 497 _Hashtable(_InputIterator __first, _InputIterator __last, 498 size_type __bkt_count_hint, 499 const _H1&, const _H2&, const _Hash&, 500 const _Equal&, const _ExtractKey&, 501 const allocator_type&); 502 503 _Hashtable(const _Hashtable&); 504 505 _Hashtable(_Hashtable&& __ht) 506 noexcept(_S_nothrow_move()) 507 : _Hashtable(std::move(__ht), std::move(__ht._M_node_allocator()), 508 true_type{}) 509 { } 510 511 _Hashtable(const _Hashtable&, const allocator_type&); 512 513 _Hashtable(_Hashtable&& __ht, const allocator_type& __a) 514 noexcept(_S_nothrow_move<__node_alloc_traits::_S_always_equal()>()) 515 : _Hashtable(std::move(__ht), __node_alloc_type(__a), 516 typename __node_alloc_traits::is_always_equal{}) 517 { } 518 519 // Use delegating constructors. 520 explicit 521 _Hashtable(const allocator_type& __a) 522 : __hashtable_alloc(__node_alloc_type(__a)), 523 __enable_default_ctor(_Enable_default_constructor_tag{}) 524 { } 525 526 explicit 527 _Hashtable(size_type __bkt_count_hint, 528 const _H1& __hf = _H1(), 529 const key_equal& __eql = key_equal(), 530 const allocator_type& __a = allocator_type()) 531 : _Hashtable(__bkt_count_hint, __hf, _H2(), _Hash(), __eql, 532 __key_extract(), __a) 533 { } 534 535 template<typename _InputIterator> 536 _Hashtable(_InputIterator __f, _InputIterator __l, 537 size_type __bkt_count_hint = 0, 538 const _H1& __hf = _H1(), 539 const key_equal& __eql = key_equal(), 540 const allocator_type& __a = allocator_type()) 541 : _Hashtable(__f, __l, __bkt_count_hint, __hf, _H2(), _Hash(), __eql, 542 __key_extract(), __a) 543 { } 544 545 _Hashtable(initializer_list<value_type> __l, 546 size_type __bkt_count_hint = 0, 547 const _H1& __hf = _H1(), 548 const key_equal& __eql = key_equal(), 549 const allocator_type& __a = allocator_type()) 550 : _Hashtable(__l.begin(), __l.end(), __bkt_count_hint, 551 __hf, _H2(), _Hash(), __eql, 552 __key_extract(), __a) 553 { } 554 555 _Hashtable& 556 operator=(const _Hashtable& __ht); 557 558 _Hashtable& 559 operator=(_Hashtable&& __ht) 560 noexcept(__node_alloc_traits::_S_nothrow_move() 561 && is_nothrow_move_assignable<_H1>::value 562 && is_nothrow_move_assignable<_Equal>::value) 563 { 564 constexpr bool __move_storage = 565 __node_alloc_traits::_S_propagate_on_move_assign() 566 || __node_alloc_traits::_S_always_equal(); 567 _M_move_assign(std::move(__ht), __bool_constant<__move_storage>()); 568 return *this; 569 } 570 571 _Hashtable& 572 operator=(initializer_list<value_type> __l) 573 { 574 __reuse_or_alloc_node_gen_t __roan(_M_begin(), *this); 575 _M_before_begin._M_nxt = nullptr; 576 clear(); 577 this->_M_insert_range(__l.begin(), __l.end(), __roan, __unique_keys()); 578 return *this; 579 } 580 581 ~_Hashtable() noexcept; 582 583 void 584 swap(_Hashtable&) 585 noexcept(__and_<__is_nothrow_swappable<_H1>, 586 __is_nothrow_swappable<_Equal>>::value); 587 588 // Basic container operations 589 iterator 590 begin() noexcept 591 { return iterator(_M_begin()); } 592 593 const_iterator 594 begin() const noexcept 595 { return const_iterator(_M_begin()); } 596 597 iterator 598 end() noexcept 599 { return iterator(nullptr); } 600 601 const_iterator 602 end() const noexcept 603 { return const_iterator(nullptr); } 604 605 const_iterator 606 cbegin() const noexcept 607 { return const_iterator(_M_begin()); } 608 609 const_iterator 610 cend() const noexcept 611 { return const_iterator(nullptr); } 612 613 size_type 614 size() const noexcept 615 { return _M_element_count; } 616 617 _GLIBCXX_NODISCARD bool 618 empty() const noexcept 619 { return size() == 0; } 620 621 allocator_type 622 get_allocator() const noexcept 623 { return allocator_type(this->_M_node_allocator()); } 624 625 size_type 626 max_size() const noexcept 627 { return __node_alloc_traits::max_size(this->_M_node_allocator()); } 628 629 // Observers 630 key_equal 631 key_eq() const 632 { return this->_M_eq(); } 633 634 // hash_function, if present, comes from _Hash_code_base. 635 636 // Bucket operations 637 size_type 638 bucket_count() const noexcept 639 { return _M_bucket_count; } 640 641 size_type 642 max_bucket_count() const noexcept 643 { return max_size(); } 644 645 size_type 646 bucket_size(size_type __bkt) const 647 { return std::distance(begin(__bkt), end(__bkt)); } 648 649 size_type 650 bucket(const key_type& __k) const 651 { return _M_bucket_index(__k, this->_M_hash_code(__k)); } 652 653 local_iterator 654 begin(size_type __bkt) 655 { 656 return local_iterator(*this, _M_bucket_begin(__bkt), 657 __bkt, _M_bucket_count); 658 } 659 660 local_iterator 661 end(size_type __bkt) 662 { return local_iterator(*this, nullptr, __bkt, _M_bucket_count); } 663 664 const_local_iterator 665 begin(size_type __bkt) const 666 { 667 return const_local_iterator(*this, _M_bucket_begin(__bkt), 668 __bkt, _M_bucket_count); 669 } 670 671 const_local_iterator 672 end(size_type __bkt) const 673 { return const_local_iterator(*this, nullptr, __bkt, _M_bucket_count); } 674 675 // DR 691. 676 const_local_iterator 677 cbegin(size_type __bkt) const 678 { 679 return const_local_iterator(*this, _M_bucket_begin(__bkt), 680 __bkt, _M_bucket_count); 681 } 682 683 const_local_iterator 684 cend(size_type __bkt) const 685 { return const_local_iterator(*this, nullptr, __bkt, _M_bucket_count); } 686 687 float 688 load_factor() const noexcept 689 { 690 return static_cast<float>(size()) / static_cast<float>(bucket_count()); 691 } 692 693 // max_load_factor, if present, comes from _Rehash_base. 694 695 // Generalization of max_load_factor. Extension, not found in 696 // TR1. Only useful if _RehashPolicy is something other than 697 // the default. 698 const _RehashPolicy& 699 __rehash_policy() const 700 { return _M_rehash_policy; } 701 702 void 703 __rehash_policy(const _RehashPolicy& __pol) 704 { _M_rehash_policy = __pol; } 705 706 // Lookup. 707 iterator 708 find(const key_type& __k); 709 710 const_iterator 711 find(const key_type& __k) const; 712 713 size_type 714 count(const key_type& __k) const; 715 716 std::pair<iterator, iterator> 717 equal_range(const key_type& __k); 718 719 std::pair<const_iterator, const_iterator> 720 equal_range(const key_type& __k) const; 721 722 protected: 723 // Bucket index computation helpers. 724 size_type 725 _M_bucket_index(__node_type* __n) const noexcept 726 { return __hash_code_base::_M_bucket_index(__n, _M_bucket_count); } 727 728 size_type 729 _M_bucket_index(const key_type& __k, __hash_code __c) const 730 { return __hash_code_base::_M_bucket_index(__k, __c, _M_bucket_count); } 731 732 // Find and insert helper functions and types 733 // Find the node before the one matching the criteria. 734 __node_base* 735 _M_find_before_node(size_type, const key_type&, __hash_code) const; 736 737 __node_type* 738 _M_find_node(size_type __bkt, const key_type& __key, 739 __hash_code __c) const 740 { 741 __node_base* __before_n = _M_find_before_node(__bkt, __key, __c); 742 if (__before_n) 743 return static_cast<__node_type*>(__before_n->_M_nxt); 744 return nullptr; 745 } 746 747 // Insert a node at the beginning of a bucket. 748 void 749 _M_insert_bucket_begin(size_type, __node_type*); 750 751 // Remove the bucket first node 752 void 753 _M_remove_bucket_begin(size_type __bkt, __node_type* __next_n, 754 size_type __next_bkt); 755 756 // Get the node before __n in the bucket __bkt 757 __node_base* 758 _M_get_previous_node(size_type __bkt, __node_base* __n); 759 760 // Insert node __n with key __k and hash code __code, in bucket __bkt 761 // if no rehash (assumes no element with same key already present). 762 // Takes ownership of __n if insertion succeeds, throws otherwise. 763 iterator 764 _M_insert_unique_node(const key_type& __k, size_type __bkt, 765 __hash_code __code, __node_type* __n, 766 size_type __n_elt = 1); 767 768 // Insert node __n with key __k and hash code __code. 769 // Takes ownership of __n if insertion succeeds, throws otherwise. 770 iterator 771 _M_insert_multi_node(__node_type* __hint, const key_type& __k, 772 __hash_code __code, __node_type* __n); 773 774 template<typename... _Args> 775 std::pair<iterator, bool> 776 _M_emplace(true_type, _Args&&... __args); 777 778 template<typename... _Args> 779 iterator 780 _M_emplace(false_type __uk, _Args&&... __args) 781 { return _M_emplace(cend(), __uk, std::forward<_Args>(__args)...); } 782 783 // Emplace with hint, useless when keys are unique. 784 template<typename... _Args> 785 iterator 786 _M_emplace(const_iterator, true_type __uk, _Args&&... __args) 787 { return _M_emplace(__uk, std::forward<_Args>(__args)...).first; } 788 789 template<typename... _Args> 790 iterator 791 _M_emplace(const_iterator, false_type, _Args&&... __args); 792 793 template<typename _Arg, typename _NodeGenerator> 794 std::pair<iterator, bool> 795 _M_insert(_Arg&&, const _NodeGenerator&, true_type, size_type = 1); 796 797 template<typename _Arg, typename _NodeGenerator> 798 iterator 799 _M_insert(_Arg&& __arg, const _NodeGenerator& __node_gen, 800 false_type __uk) 801 { 802 return _M_insert(cend(), std::forward<_Arg>(__arg), __node_gen, 803 __uk); 804 } 805 806 // Insert with hint, not used when keys are unique. 807 template<typename _Arg, typename _NodeGenerator> 808 iterator 809 _M_insert(const_iterator, _Arg&& __arg, 810 const _NodeGenerator& __node_gen, true_type __uk) 811 { 812 return 813 _M_insert(std::forward<_Arg>(__arg), __node_gen, __uk).first; 814 } 815 816 // Insert with hint when keys are not unique. 817 template<typename _Arg, typename _NodeGenerator> 818 iterator 819 _M_insert(const_iterator, _Arg&&, 820 const _NodeGenerator&, false_type); 821 822 size_type 823 _M_erase(true_type, const key_type&); 824 825 size_type 826 _M_erase(false_type, const key_type&); 827 828 iterator 829 _M_erase(size_type __bkt, __node_base* __prev_n, __node_type* __n); 830 831 public: 832 // Emplace 833 template<typename... _Args> 834 __ireturn_type 835 emplace(_Args&&... __args) 836 { return _M_emplace(__unique_keys(), std::forward<_Args>(__args)...); } 837 838 template<typename... _Args> 839 iterator 840 emplace_hint(const_iterator __hint, _Args&&... __args) 841 { 842 return _M_emplace(__hint, __unique_keys(), 843 std::forward<_Args>(__args)...); 844 } 845 846 // Insert member functions via inheritance. 847 848 // Erase 849 iterator 850 erase(const_iterator); 851 852 // LWG 2059. 853 iterator 854 erase(iterator __it) 855 { return erase(const_iterator(__it)); } 856 857 size_type 858 erase(const key_type& __k) 859 { return _M_erase(__unique_keys(), __k); } 860 861 iterator 862 erase(const_iterator, const_iterator); 863 864 void 865 clear() noexcept; 866 867 // Set number of buckets keeping it appropriate for container's number 868 // of elements. 869 void rehash(size_type __bkt_count); 870 871 // DR 1189. 872 // reserve, if present, comes from _Rehash_base. 873 874 #if __cplusplus > 201402L 875 /// Re-insert an extracted node into a container with unique keys. 876 insert_return_type 877 _M_reinsert_node(node_type&& __nh) 878 { 879 insert_return_type __ret; 880 if (__nh.empty()) 881 __ret.position = end(); 882 else 883 { 884 __glibcxx_assert(get_allocator() == __nh.get_allocator()); 885 886 const key_type& __k = __nh._M_key(); 887 __hash_code __code = this->_M_hash_code(__k); 888 size_type __bkt = _M_bucket_index(__k, __code); 889 if (__node_type* __n = _M_find_node(__bkt, __k, __code)) 890 { 891 __ret.node = std::move(__nh); 892 __ret.position = iterator(__n); 893 __ret.inserted = false; 894 } 895 else 896 { 897 __ret.position 898 = _M_insert_unique_node(__k, __bkt, __code, __nh._M_ptr); 899 __nh._M_ptr = nullptr; 900 __ret.inserted = true; 901 } 902 } 903 return __ret; 904 } 905 906 /// Re-insert an extracted node into a container with equivalent keys. 907 iterator 908 _M_reinsert_node_multi(const_iterator __hint, node_type&& __nh) 909 { 910 if (__nh.empty()) 911 return end(); 912 913 __glibcxx_assert(get_allocator() == __nh.get_allocator()); 914 915 const key_type& __k = __nh._M_key(); 916 auto __code = this->_M_hash_code(__k); 917 auto __ret 918 = _M_insert_multi_node(__hint._M_cur, __k, __code, __nh._M_ptr); 919 __nh._M_ptr = nullptr; 920 return __ret; 921 } 922 923 private: 924 node_type 925 _M_extract_node(size_t __bkt, __node_base* __prev_n) 926 { 927 __node_type* __n = static_cast<__node_type*>(__prev_n->_M_nxt); 928 if (__prev_n == _M_buckets[__bkt]) 929 _M_remove_bucket_begin(__bkt, __n->_M_next(), 930 __n->_M_nxt ? _M_bucket_index(__n->_M_next()) : 0); 931 else if (__n->_M_nxt) 932 { 933 size_type __next_bkt = _M_bucket_index(__n->_M_next()); 934 if (__next_bkt != __bkt) 935 _M_buckets[__next_bkt] = __prev_n; 936 } 937 938 __prev_n->_M_nxt = __n->_M_nxt; 939 __n->_M_nxt = nullptr; 940 --_M_element_count; 941 return { __n, this->_M_node_allocator() }; 942 } 943 944 public: 945 // Extract a node. 946 node_type 947 extract(const_iterator __pos) 948 { 949 size_t __bkt = _M_bucket_index(__pos._M_cur); 950 return _M_extract_node(__bkt, 951 _M_get_previous_node(__bkt, __pos._M_cur)); 952 } 953 954 /// Extract a node. 955 node_type 956 extract(const _Key& __k) 957 { 958 node_type __nh; 959 __hash_code __code = this->_M_hash_code(__k); 960 std::size_t __bkt = _M_bucket_index(__k, __code); 961 if (__node_base* __prev_node = _M_find_before_node(__bkt, __k, __code)) 962 __nh = _M_extract_node(__bkt, __prev_node); 963 return __nh; 964 } 965 966 /// Merge from a compatible container into one with unique keys. 967 template<typename _Compatible_Hashtable> 968 void 969 _M_merge_unique(_Compatible_Hashtable& __src) noexcept 970 { 971 static_assert(is_same_v<typename _Compatible_Hashtable::node_type, 972 node_type>, "Node types are compatible"); 973 __glibcxx_assert(get_allocator() == __src.get_allocator()); 974 975 auto __n_elt = __src.size(); 976 for (auto __i = __src.begin(), __end = __src.end(); __i != __end;) 977 { 978 auto __pos = __i++; 979 const key_type& __k = this->_M_extract()(*__pos); 980 __hash_code __code = this->_M_hash_code(__k); 981 size_type __bkt = _M_bucket_index(__k, __code); 982 if (_M_find_node(__bkt, __k, __code) == nullptr) 983 { 984 auto __nh = __src.extract(__pos); 985 _M_insert_unique_node(__k, __bkt, __code, __nh._M_ptr, 986 __n_elt); 987 __nh._M_ptr = nullptr; 988 __n_elt = 1; 989 } 990 else if (__n_elt != 1) 991 --__n_elt; 992 } 993 } 994 995 /// Merge from a compatible container into one with equivalent keys. 996 template<typename _Compatible_Hashtable> 997 void 998 _M_merge_multi(_Compatible_Hashtable& __src) noexcept 999 { 1000 static_assert(is_same_v<typename _Compatible_Hashtable::node_type, 1001 node_type>, "Node types are compatible"); 1002 __glibcxx_assert(get_allocator() == __src.get_allocator()); 1003 1004 this->reserve(size() + __src.size()); 1005 for (auto __i = __src.begin(), __end = __src.end(); __i != __end;) 1006 _M_reinsert_node_multi(cend(), __src.extract(__i++)); 1007 } 1008 #endif // C++17 1009 1010 private: 1011 // Helper rehash method used when keys are unique. 1012 void _M_rehash_aux(size_type __bkt_count, true_type); 1013 1014 // Helper rehash method used when keys can be non-unique. 1015 void _M_rehash_aux(size_type __bkt_count, false_type); 1016 1017 // Unconditionally change size of bucket array to n, restore 1018 // hash policy state to __state on exception. 1019 void _M_rehash(size_type __bkt_count, const __rehash_state& __state); 1020 }; 1021 1022 1023 // Definitions of class template _Hashtable's out-of-line member functions. 1024 template<typename _Key, typename _Value, 1025 typename _Alloc, typename _ExtractKey, typename _Equal, 1026 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 1027 typename _Traits> 1028 auto 1029 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, 1030 _H1, _H2, _Hash, _RehashPolicy, _Traits>:: 1031 _M_bucket_begin(size_type __bkt) const 1032 -> __node_type* 1033 { 1034 __node_base* __n = _M_buckets[__bkt]; 1035 return __n ? static_cast<__node_type*>(__n->_M_nxt) : nullptr; 1036 } 1037 1038 template<typename _Key, typename _Value, 1039 typename _Alloc, typename _ExtractKey, typename _Equal, 1040 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 1041 typename _Traits> 1042 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, 1043 _H1, _H2, _Hash, _RehashPolicy, _Traits>:: 1044 _Hashtable(size_type __bkt_count_hint, 1045 const _H1& __h1, const _H2& __h2, const _Hash& __h, 1046 const _Equal& __eq, const _ExtractKey& __exk, 1047 const allocator_type& __a) 1048 : _Hashtable(__h1, __h2, __h, __eq, __exk, __a) 1049 { 1050 auto __bkt_count = _M_rehash_policy._M_next_bkt(__bkt_count_hint); 1051 if (__bkt_count > _M_bucket_count) 1052 { 1053 _M_buckets = _M_allocate_buckets(__bkt_count); 1054 _M_bucket_count = __bkt_count; 1055 } 1056 } 1057 1058 template<typename _Key, typename _Value, 1059 typename _Alloc, typename _ExtractKey, typename _Equal, 1060 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 1061 typename _Traits> 1062 template<typename _InputIterator> 1063 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, 1064 _H1, _H2, _Hash, _RehashPolicy, _Traits>:: 1065 _Hashtable(_InputIterator __f, _InputIterator __l, 1066 size_type __bkt_count_hint, 1067 const _H1& __h1, const _H2& __h2, const _Hash& __h, 1068 const _Equal& __eq, const _ExtractKey& __exk, 1069 const allocator_type& __a) 1070 : _Hashtable(__h1, __h2, __h, __eq, __exk, __a) 1071 { 1072 auto __nb_elems = __detail::__distance_fw(__f, __l); 1073 auto __bkt_count = 1074 _M_rehash_policy._M_next_bkt( 1075 std::max(_M_rehash_policy._M_bkt_for_elements(__nb_elems), 1076 __bkt_count_hint)); 1077 1078 if (__bkt_count > _M_bucket_count) 1079 { 1080 _M_buckets = _M_allocate_buckets(__bkt_count); 1081 _M_bucket_count = __bkt_count; 1082 } 1083 1084 for (; __f != __l; ++__f) 1085 this->insert(*__f); 1086 } 1087 1088 template<typename _Key, typename _Value, 1089 typename _Alloc, typename _ExtractKey, typename _Equal, 1090 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 1091 typename _Traits> 1092 auto 1093 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, 1094 _H1, _H2, _Hash, _RehashPolicy, _Traits>:: 1095 operator=(const _Hashtable& __ht) 1096 -> _Hashtable& 1097 { 1098 if (&__ht == this) 1099 return *this; 1100 1101 if (__node_alloc_traits::_S_propagate_on_copy_assign()) 1102 { 1103 auto& __this_alloc = this->_M_node_allocator(); 1104 auto& __that_alloc = __ht._M_node_allocator(); 1105 if (!__node_alloc_traits::_S_always_equal() 1106 && __this_alloc != __that_alloc) 1107 { 1108 // Replacement allocator cannot free existing storage. 1109 this->_M_deallocate_nodes(_M_begin()); 1110 _M_before_begin._M_nxt = nullptr; 1111 _M_deallocate_buckets(); 1112 _M_buckets = nullptr; 1113 std::__alloc_on_copy(__this_alloc, __that_alloc); 1114 __hashtable_base::operator=(__ht); 1115 _M_bucket_count = __ht._M_bucket_count; 1116 _M_element_count = __ht._M_element_count; 1117 _M_rehash_policy = __ht._M_rehash_policy; 1118 __alloc_node_gen_t __alloc_node_gen(*this); 1119 __try 1120 { 1121 _M_assign(__ht, __alloc_node_gen); 1122 } 1123 __catch(...) 1124 { 1125 // _M_assign took care of deallocating all memory. Now we 1126 // must make sure this instance remains in a usable state. 1127 _M_reset(); 1128 __throw_exception_again; 1129 } 1130 return *this; 1131 } 1132 std::__alloc_on_copy(__this_alloc, __that_alloc); 1133 } 1134 1135 // Reuse allocated buckets and nodes. 1136 _M_assign_elements(__ht); 1137 return *this; 1138 } 1139 1140 template<typename _Key, typename _Value, 1141 typename _Alloc, typename _ExtractKey, typename _Equal, 1142 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 1143 typename _Traits> 1144 template<typename _Ht> 1145 void 1146 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, 1147 _H1, _H2, _Hash, _RehashPolicy, _Traits>:: 1148 _M_assign_elements(_Ht&& __ht) 1149 { 1150 __bucket_type* __former_buckets = nullptr; 1151 std::size_t __former_bucket_count = _M_bucket_count; 1152 const __rehash_state& __former_state = _M_rehash_policy._M_state(); 1153 1154 if (_M_bucket_count != __ht._M_bucket_count) 1155 { 1156 __former_buckets = _M_buckets; 1157 _M_buckets = _M_allocate_buckets(__ht._M_bucket_count); 1158 _M_bucket_count = __ht._M_bucket_count; 1159 } 1160 else 1161 __builtin_memset(_M_buckets, 0, 1162 _M_bucket_count * sizeof(__bucket_type)); 1163 1164 __try 1165 { 1166 __hashtable_base::operator=(std::forward<_Ht>(__ht)); 1167 _M_element_count = __ht._M_element_count; 1168 _M_rehash_policy = __ht._M_rehash_policy; 1169 __reuse_or_alloc_node_gen_t __roan(_M_begin(), *this); 1170 _M_before_begin._M_nxt = nullptr; 1171 _M_assign(std::forward<_Ht>(__ht), __roan); 1172 if (__former_buckets) 1173 _M_deallocate_buckets(__former_buckets, __former_bucket_count); 1174 } 1175 __catch(...) 1176 { 1177 if (__former_buckets) 1178 { 1179 // Restore previous buckets. 1180 _M_deallocate_buckets(); 1181 _M_rehash_policy._M_reset(__former_state); 1182 _M_buckets = __former_buckets; 1183 _M_bucket_count = __former_bucket_count; 1184 } 1185 __builtin_memset(_M_buckets, 0, 1186 _M_bucket_count * sizeof(__bucket_type)); 1187 __throw_exception_again; 1188 } 1189 } 1190 1191 template<typename _Key, typename _Value, 1192 typename _Alloc, typename _ExtractKey, typename _Equal, 1193 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 1194 typename _Traits> 1195 template<typename _Ht, typename _NodeGenerator> 1196 void 1197 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, 1198 _H1, _H2, _Hash, _RehashPolicy, _Traits>:: 1199 _M_assign(_Ht&& __ht, const _NodeGenerator& __node_gen) 1200 { 1201 __bucket_type* __buckets = nullptr; 1202 if (!_M_buckets) 1203 _M_buckets = __buckets = _M_allocate_buckets(_M_bucket_count); 1204 1205 __try 1206 { 1207 if (!__ht._M_before_begin._M_nxt) 1208 return; 1209 1210 // First deal with the special first node pointed to by 1211 // _M_before_begin. 1212 __node_type* __ht_n = __ht._M_begin(); 1213 __node_type* __this_n 1214 = __node_gen(__fwd_value_for<_Ht>(__ht_n->_M_v())); 1215 this->_M_copy_code(__this_n, __ht_n); 1216 _M_before_begin._M_nxt = __this_n; 1217 _M_buckets[_M_bucket_index(__this_n)] = &_M_before_begin; 1218 1219 // Then deal with other nodes. 1220 __node_base* __prev_n = __this_n; 1221 for (__ht_n = __ht_n->_M_next(); __ht_n; __ht_n = __ht_n->_M_next()) 1222 { 1223 __this_n = __node_gen(__fwd_value_for<_Ht>(__ht_n->_M_v())); 1224 __prev_n->_M_nxt = __this_n; 1225 this->_M_copy_code(__this_n, __ht_n); 1226 size_type __bkt = _M_bucket_index(__this_n); 1227 if (!_M_buckets[__bkt]) 1228 _M_buckets[__bkt] = __prev_n; 1229 __prev_n = __this_n; 1230 } 1231 } 1232 __catch(...) 1233 { 1234 clear(); 1235 if (__buckets) 1236 _M_deallocate_buckets(); 1237 __throw_exception_again; 1238 } 1239 } 1240 1241 template<typename _Key, typename _Value, 1242 typename _Alloc, typename _ExtractKey, typename _Equal, 1243 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 1244 typename _Traits> 1245 void 1246 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, 1247 _H1, _H2, _Hash, _RehashPolicy, _Traits>:: 1248 _M_reset() noexcept 1249 { 1250 _M_rehash_policy._M_reset(); 1251 _M_bucket_count = 1; 1252 _M_single_bucket = nullptr; 1253 _M_buckets = &_M_single_bucket; 1254 _M_before_begin._M_nxt = nullptr; 1255 _M_element_count = 0; 1256 } 1257 1258 template<typename _Key, typename _Value, 1259 typename _Alloc, typename _ExtractKey, typename _Equal, 1260 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 1261 typename _Traits> 1262 void 1263 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, 1264 _H1, _H2, _Hash, _RehashPolicy, _Traits>:: 1265 _M_move_assign(_Hashtable&& __ht, true_type) 1266 { 1267 this->_M_deallocate_nodes(_M_begin()); 1268 _M_deallocate_buckets(); 1269 __hashtable_base::operator=(std::move(__ht)); 1270 _M_rehash_policy = __ht._M_rehash_policy; 1271 if (!__ht._M_uses_single_bucket()) 1272 _M_buckets = __ht._M_buckets; 1273 else 1274 { 1275 _M_buckets = &_M_single_bucket; 1276 _M_single_bucket = __ht._M_single_bucket; 1277 } 1278 _M_bucket_count = __ht._M_bucket_count; 1279 _M_before_begin._M_nxt = __ht._M_before_begin._M_nxt; 1280 _M_element_count = __ht._M_element_count; 1281 std::__alloc_on_move(this->_M_node_allocator(), __ht._M_node_allocator()); 1282 1283 // Fix buckets containing the _M_before_begin pointers that can't be 1284 // moved. 1285 if (_M_begin()) 1286 _M_buckets[_M_bucket_index(_M_begin())] = &_M_before_begin; 1287 __ht._M_reset(); 1288 } 1289 1290 template<typename _Key, typename _Value, 1291 typename _Alloc, typename _ExtractKey, typename _Equal, 1292 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 1293 typename _Traits> 1294 void 1295 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, 1296 _H1, _H2, _Hash, _RehashPolicy, _Traits>:: 1297 _M_move_assign(_Hashtable&& __ht, false_type) 1298 { 1299 if (__ht._M_node_allocator() == this->_M_node_allocator()) 1300 _M_move_assign(std::move(__ht), true_type()); 1301 else 1302 { 1303 // Can't move memory, move elements then. 1304 _M_assign_elements(std::move(__ht)); 1305 __ht.clear(); 1306 } 1307 } 1308 1309 template<typename _Key, typename _Value, 1310 typename _Alloc, typename _ExtractKey, typename _Equal, 1311 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 1312 typename _Traits> 1313 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, 1314 _H1, _H2, _Hash, _RehashPolicy, _Traits>:: 1315 _Hashtable(const _Hashtable& __ht) 1316 : __hashtable_base(__ht), 1317 __map_base(__ht), 1318 __rehash_base(__ht), 1319 __hashtable_alloc( 1320 __node_alloc_traits::_S_select_on_copy(__ht._M_node_allocator())), 1321 __enable_default_ctor(__ht), 1322 _M_buckets(nullptr), 1323 _M_bucket_count(__ht._M_bucket_count), 1324 _M_element_count(__ht._M_element_count), 1325 _M_rehash_policy(__ht._M_rehash_policy) 1326 { 1327 __alloc_node_gen_t __alloc_node_gen(*this); 1328 _M_assign(__ht, __alloc_node_gen); 1329 } 1330 1331 template<typename _Key, typename _Value, 1332 typename _Alloc, typename _ExtractKey, typename _Equal, 1333 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 1334 typename _Traits> 1335 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, 1336 _H1, _H2, _Hash, _RehashPolicy, _Traits>:: 1337 _Hashtable(_Hashtable&& __ht, __node_alloc_type&& __a, 1338 true_type /* alloc always equal */) 1339 noexcept(_S_nothrow_move()) 1340 : __hashtable_base(__ht), 1341 __map_base(__ht), 1342 __rehash_base(__ht), 1343 __hashtable_alloc(std::move(__a)), 1344 __enable_default_ctor(__ht), 1345 _M_buckets(__ht._M_buckets), 1346 _M_bucket_count(__ht._M_bucket_count), 1347 _M_before_begin(__ht._M_before_begin._M_nxt), 1348 _M_element_count(__ht._M_element_count), 1349 _M_rehash_policy(__ht._M_rehash_policy) 1350 { 1351 // Update buckets if __ht is using its single bucket. 1352 if (__ht._M_uses_single_bucket()) 1353 { 1354 _M_buckets = &_M_single_bucket; 1355 _M_single_bucket = __ht._M_single_bucket; 1356 } 1357 1358 // Update, if necessary, bucket pointing to before begin that hasn't 1359 // moved. 1360 if (_M_begin()) 1361 _M_buckets[_M_bucket_index(_M_begin())] = &_M_before_begin; 1362 1363 __ht._M_reset(); 1364 } 1365 1366 template<typename _Key, typename _Value, 1367 typename _Alloc, typename _ExtractKey, typename _Equal, 1368 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 1369 typename _Traits> 1370 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, 1371 _H1, _H2, _Hash, _RehashPolicy, _Traits>:: 1372 _Hashtable(const _Hashtable& __ht, const allocator_type& __a) 1373 : __hashtable_base(__ht), 1374 __map_base(__ht), 1375 __rehash_base(__ht), 1376 __hashtable_alloc(__node_alloc_type(__a)), 1377 __enable_default_ctor(__ht), 1378 _M_buckets(), 1379 _M_bucket_count(__ht._M_bucket_count), 1380 _M_element_count(__ht._M_element_count), 1381 _M_rehash_policy(__ht._M_rehash_policy) 1382 { 1383 __alloc_node_gen_t __alloc_node_gen(*this); 1384 _M_assign(__ht, __alloc_node_gen); 1385 } 1386 1387 template<typename _Key, typename _Value, 1388 typename _Alloc, typename _ExtractKey, typename _Equal, 1389 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 1390 typename _Traits> 1391 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, 1392 _H1, _H2, _Hash, _RehashPolicy, _Traits>:: 1393 _Hashtable(_Hashtable&& __ht, __node_alloc_type&& __a, 1394 false_type /* alloc always equal */) 1395 : __hashtable_base(__ht), 1396 __map_base(__ht), 1397 __rehash_base(__ht), 1398 __hashtable_alloc(std::move(__a)), 1399 __enable_default_ctor(__ht), 1400 _M_buckets(nullptr), 1401 _M_bucket_count(__ht._M_bucket_count), 1402 _M_element_count(__ht._M_element_count), 1403 _M_rehash_policy(__ht._M_rehash_policy) 1404 { 1405 if (__ht._M_node_allocator() == this->_M_node_allocator()) 1406 { 1407 if (__ht._M_uses_single_bucket()) 1408 { 1409 _M_buckets = &_M_single_bucket; 1410 _M_single_bucket = __ht._M_single_bucket; 1411 } 1412 else 1413 _M_buckets = __ht._M_buckets; 1414 1415 _M_before_begin._M_nxt = __ht._M_before_begin._M_nxt; 1416 // Update, if necessary, bucket pointing to before begin that hasn't 1417 // moved. 1418 if (_M_begin()) 1419 _M_buckets[_M_bucket_index(_M_begin())] = &_M_before_begin; 1420 __ht._M_reset(); 1421 } 1422 else 1423 { 1424 __alloc_node_gen_t __alloc_gen(*this); 1425 1426 using _Fwd_Ht = typename 1427 conditional<__move_if_noexcept_cond<value_type>::value, 1428 const _Hashtable&, _Hashtable&&>::type; 1429 _M_assign(std::forward<_Fwd_Ht>(__ht), __alloc_gen); 1430 __ht.clear(); 1431 } 1432 } 1433 1434 template<typename _Key, typename _Value, 1435 typename _Alloc, typename _ExtractKey, typename _Equal, 1436 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 1437 typename _Traits> 1438 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, 1439 _H1, _H2, _Hash, _RehashPolicy, _Traits>:: 1440 ~_Hashtable() noexcept 1441 { 1442 clear(); 1443 _M_deallocate_buckets(); 1444 } 1445 1446 template<typename _Key, typename _Value, 1447 typename _Alloc, typename _ExtractKey, typename _Equal, 1448 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 1449 typename _Traits> 1450 void 1451 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, 1452 _H1, _H2, _Hash, _RehashPolicy, _Traits>:: 1453 swap(_Hashtable& __x) 1454 noexcept(__and_<__is_nothrow_swappable<_H1>, 1455 __is_nothrow_swappable<_Equal>>::value) 1456 { 1457 // The only base class with member variables is hash_code_base. 1458 // We define _Hash_code_base::_M_swap because different 1459 // specializations have different members. 1460 this->_M_swap(__x); 1461 1462 std::__alloc_on_swap(this->_M_node_allocator(), __x._M_node_allocator()); 1463 std::swap(_M_rehash_policy, __x._M_rehash_policy); 1464 1465 // Deal properly with potentially moved instances. 1466 if (this->_M_uses_single_bucket()) 1467 { 1468 if (!__x._M_uses_single_bucket()) 1469 { 1470 _M_buckets = __x._M_buckets; 1471 __x._M_buckets = &__x._M_single_bucket; 1472 } 1473 } 1474 else if (__x._M_uses_single_bucket()) 1475 { 1476 __x._M_buckets = _M_buckets; 1477 _M_buckets = &_M_single_bucket; 1478 } 1479 else 1480 std::swap(_M_buckets, __x._M_buckets); 1481 1482 std::swap(_M_bucket_count, __x._M_bucket_count); 1483 std::swap(_M_before_begin._M_nxt, __x._M_before_begin._M_nxt); 1484 std::swap(_M_element_count, __x._M_element_count); 1485 std::swap(_M_single_bucket, __x._M_single_bucket); 1486 1487 // Fix buckets containing the _M_before_begin pointers that can't be 1488 // swapped. 1489 if (_M_begin()) 1490 _M_buckets[_M_bucket_index(_M_begin())] = &_M_before_begin; 1491 1492 if (__x._M_begin()) 1493 __x._M_buckets[__x._M_bucket_index(__x._M_begin())] 1494 = &__x._M_before_begin; 1495 } 1496 1497 template<typename _Key, typename _Value, 1498 typename _Alloc, typename _ExtractKey, typename _Equal, 1499 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 1500 typename _Traits> 1501 auto 1502 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, 1503 _H1, _H2, _Hash, _RehashPolicy, _Traits>:: 1504 find(const key_type& __k) 1505 -> iterator 1506 { 1507 __hash_code __code = this->_M_hash_code(__k); 1508 std::size_t __bkt = _M_bucket_index(__k, __code); 1509 __node_type* __p = _M_find_node(__bkt, __k, __code); 1510 return __p ? iterator(__p) : end(); 1511 } 1512 1513 template<typename _Key, typename _Value, 1514 typename _Alloc, typename _ExtractKey, typename _Equal, 1515 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 1516 typename _Traits> 1517 auto 1518 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, 1519 _H1, _H2, _Hash, _RehashPolicy, _Traits>:: 1520 find(const key_type& __k) const 1521 -> const_iterator 1522 { 1523 __hash_code __code = this->_M_hash_code(__k); 1524 std::size_t __bkt = _M_bucket_index(__k, __code); 1525 __node_type* __p = _M_find_node(__bkt, __k, __code); 1526 return __p ? const_iterator(__p) : end(); 1527 } 1528 1529 template<typename _Key, typename _Value, 1530 typename _Alloc, typename _ExtractKey, typename _Equal, 1531 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 1532 typename _Traits> 1533 auto 1534 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, 1535 _H1, _H2, _Hash, _RehashPolicy, _Traits>:: 1536 count(const key_type& __k) const 1537 -> size_type 1538 { 1539 __hash_code __code = this->_M_hash_code(__k); 1540 std::size_t __bkt = _M_bucket_index(__k, __code); 1541 __node_type* __p = _M_bucket_begin(__bkt); 1542 if (!__p) 1543 return 0; 1544 1545 std::size_t __result = 0; 1546 for (;; __p = __p->_M_next()) 1547 { 1548 if (this->_M_equals(__k, __code, __p)) 1549 ++__result; 1550 else if (__result) 1551 // All equivalent values are next to each other, if we 1552 // found a non-equivalent value after an equivalent one it 1553 // means that we won't find any new equivalent value. 1554 break; 1555 if (!__p->_M_nxt || _M_bucket_index(__p->_M_next()) != __bkt) 1556 break; 1557 } 1558 return __result; 1559 } 1560 1561 template<typename _Key, typename _Value, 1562 typename _Alloc, typename _ExtractKey, typename _Equal, 1563 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 1564 typename _Traits> 1565 auto 1566 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, 1567 _H1, _H2, _Hash, _RehashPolicy, _Traits>:: 1568 equal_range(const key_type& __k) 1569 -> pair<iterator, iterator> 1570 { 1571 __hash_code __code = this->_M_hash_code(__k); 1572 std::size_t __bkt = _M_bucket_index(__k, __code); 1573 __node_type* __p = _M_find_node(__bkt, __k, __code); 1574 1575 if (__p) 1576 { 1577 __node_type* __p1 = __p->_M_next(); 1578 while (__p1 && _M_bucket_index(__p1) == __bkt 1579 && this->_M_equals(__k, __code, __p1)) 1580 __p1 = __p1->_M_next(); 1581 1582 return std::make_pair(iterator(__p), iterator(__p1)); 1583 } 1584 else 1585 return std::make_pair(end(), end()); 1586 } 1587 1588 template<typename _Key, typename _Value, 1589 typename _Alloc, typename _ExtractKey, typename _Equal, 1590 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 1591 typename _Traits> 1592 auto 1593 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, 1594 _H1, _H2, _Hash, _RehashPolicy, _Traits>:: 1595 equal_range(const key_type& __k) const 1596 -> pair<const_iterator, const_iterator> 1597 { 1598 __hash_code __code = this->_M_hash_code(__k); 1599 std::size_t __bkt = _M_bucket_index(__k, __code); 1600 __node_type* __p = _M_find_node(__bkt, __k, __code); 1601 1602 if (__p) 1603 { 1604 __node_type* __p1 = __p->_M_next(); 1605 while (__p1 && _M_bucket_index(__p1) == __bkt 1606 && this->_M_equals(__k, __code, __p1)) 1607 __p1 = __p1->_M_next(); 1608 1609 return std::make_pair(const_iterator(__p), const_iterator(__p1)); 1610 } 1611 else 1612 return std::make_pair(end(), end()); 1613 } 1614 1615 // Find the node whose key compares equal to k in the bucket bkt. 1616 // Return nullptr if no node is found. 1617 template<typename _Key, typename _Value, 1618 typename _Alloc, typename _ExtractKey, typename _Equal, 1619 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 1620 typename _Traits> 1621 auto 1622 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, 1623 _H1, _H2, _Hash, _RehashPolicy, _Traits>:: 1624 _M_find_before_node(size_type __bkt, const key_type& __k, 1625 __hash_code __code) const 1626 -> __node_base* 1627 { 1628 __node_base* __prev_p = _M_buckets[__bkt]; 1629 if (!__prev_p) 1630 return nullptr; 1631 1632 for (__node_type* __p = static_cast<__node_type*>(__prev_p->_M_nxt);; 1633 __p = __p->_M_next()) 1634 { 1635 if (this->_M_equals(__k, __code, __p)) 1636 return __prev_p; 1637 1638 if (!__p->_M_nxt || _M_bucket_index(__p->_M_next()) != __bkt) 1639 break; 1640 __prev_p = __p; 1641 } 1642 return nullptr; 1643 } 1644 1645 template<typename _Key, typename _Value, 1646 typename _Alloc, typename _ExtractKey, typename _Equal, 1647 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 1648 typename _Traits> 1649 void 1650 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, 1651 _H1, _H2, _Hash, _RehashPolicy, _Traits>:: 1652 _M_insert_bucket_begin(size_type __bkt, __node_type* __node) 1653 { 1654 if (_M_buckets[__bkt]) 1655 { 1656 // Bucket is not empty, we just need to insert the new node 1657 // after the bucket before begin. 1658 __node->_M_nxt = _M_buckets[__bkt]->_M_nxt; 1659 _M_buckets[__bkt]->_M_nxt = __node; 1660 } 1661 else 1662 { 1663 // The bucket is empty, the new node is inserted at the 1664 // beginning of the singly-linked list and the bucket will 1665 // contain _M_before_begin pointer. 1666 __node->_M_nxt = _M_before_begin._M_nxt; 1667 _M_before_begin._M_nxt = __node; 1668 if (__node->_M_nxt) 1669 // We must update former begin bucket that is pointing to 1670 // _M_before_begin. 1671 _M_buckets[_M_bucket_index(__node->_M_next())] = __node; 1672 _M_buckets[__bkt] = &_M_before_begin; 1673 } 1674 } 1675 1676 template<typename _Key, typename _Value, 1677 typename _Alloc, typename _ExtractKey, typename _Equal, 1678 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 1679 typename _Traits> 1680 void 1681 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, 1682 _H1, _H2, _Hash, _RehashPolicy, _Traits>:: 1683 _M_remove_bucket_begin(size_type __bkt, __node_type* __next, 1684 size_type __next_bkt) 1685 { 1686 if (!__next || __next_bkt != __bkt) 1687 { 1688 // Bucket is now empty 1689 // First update next bucket if any 1690 if (__next) 1691 _M_buckets[__next_bkt] = _M_buckets[__bkt]; 1692 1693 // Second update before begin node if necessary 1694 if (&_M_before_begin == _M_buckets[__bkt]) 1695 _M_before_begin._M_nxt = __next; 1696 _M_buckets[__bkt] = nullptr; 1697 } 1698 } 1699 1700 template<typename _Key, typename _Value, 1701 typename _Alloc, typename _ExtractKey, typename _Equal, 1702 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 1703 typename _Traits> 1704 auto 1705 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, 1706 _H1, _H2, _Hash, _RehashPolicy, _Traits>:: 1707 _M_get_previous_node(size_type __bkt, __node_base* __n) 1708 -> __node_base* 1709 { 1710 __node_base* __prev_n = _M_buckets[__bkt]; 1711 while (__prev_n->_M_nxt != __n) 1712 __prev_n = __prev_n->_M_nxt; 1713 return __prev_n; 1714 } 1715 1716 template<typename _Key, typename _Value, 1717 typename _Alloc, typename _ExtractKey, typename _Equal, 1718 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 1719 typename _Traits> 1720 template<typename... _Args> 1721 auto 1722 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, 1723 _H1, _H2, _Hash, _RehashPolicy, _Traits>:: 1724 _M_emplace(true_type, _Args&&... __args) 1725 -> pair<iterator, bool> 1726 { 1727 // First build the node to get access to the hash code 1728 _Scoped_node __node { this, std::forward<_Args>(__args)... }; 1729 const key_type& __k = this->_M_extract()(__node._M_node->_M_v()); 1730 __hash_code __code = this->_M_hash_code(__k); 1731 size_type __bkt = _M_bucket_index(__k, __code); 1732 if (__node_type* __p = _M_find_node(__bkt, __k, __code)) 1733 // There is already an equivalent node, no insertion 1734 return std::make_pair(iterator(__p), false); 1735 1736 // Insert the node 1737 auto __pos = _M_insert_unique_node(__k, __bkt, __code, __node._M_node); 1738 __node._M_node = nullptr; 1739 return { __pos, true }; 1740 } 1741 1742 template<typename _Key, typename _Value, 1743 typename _Alloc, typename _ExtractKey, typename _Equal, 1744 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 1745 typename _Traits> 1746 template<typename... _Args> 1747 auto 1748 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, 1749 _H1, _H2, _Hash, _RehashPolicy, _Traits>:: 1750 _M_emplace(const_iterator __hint, false_type, _Args&&... __args) 1751 -> iterator 1752 { 1753 // First build the node to get its hash code. 1754 _Scoped_node __node { this, std::forward<_Args>(__args)... }; 1755 const key_type& __k = this->_M_extract()(__node._M_node->_M_v()); 1756 1757 __hash_code __code = this->_M_hash_code(__k); 1758 auto __pos 1759 = _M_insert_multi_node(__hint._M_cur, __k, __code, __node._M_node); 1760 __node._M_node = nullptr; 1761 return __pos; 1762 } 1763 1764 template<typename _Key, typename _Value, 1765 typename _Alloc, typename _ExtractKey, typename _Equal, 1766 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 1767 typename _Traits> 1768 auto 1769 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, 1770 _H1, _H2, _Hash, _RehashPolicy, _Traits>:: 1771 _M_insert_unique_node(const key_type& __k, size_type __bkt, 1772 __hash_code __code, __node_type* __node, 1773 size_type __n_elt) 1774 -> iterator 1775 { 1776 const __rehash_state& __saved_state = _M_rehash_policy._M_state(); 1777 std::pair<bool, std::size_t> __do_rehash 1778 = _M_rehash_policy._M_need_rehash(_M_bucket_count, _M_element_count, 1779 __n_elt); 1780 1781 if (__do_rehash.first) 1782 { 1783 _M_rehash(__do_rehash.second, __saved_state); 1784 __bkt = _M_bucket_index(__k, __code); 1785 } 1786 1787 this->_M_store_code(__node, __code); 1788 1789 // Always insert at the beginning of the bucket. 1790 _M_insert_bucket_begin(__bkt, __node); 1791 ++_M_element_count; 1792 return iterator(__node); 1793 } 1794 1795 template<typename _Key, typename _Value, 1796 typename _Alloc, typename _ExtractKey, typename _Equal, 1797 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 1798 typename _Traits> 1799 auto 1800 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, 1801 _H1, _H2, _Hash, _RehashPolicy, _Traits>:: 1802 _M_insert_multi_node(__node_type* __hint, const key_type& __k, 1803 __hash_code __code, __node_type* __node) 1804 -> iterator 1805 { 1806 const __rehash_state& __saved_state = _M_rehash_policy._M_state(); 1807 std::pair<bool, std::size_t> __do_rehash 1808 = _M_rehash_policy._M_need_rehash(_M_bucket_count, _M_element_count, 1); 1809 1810 if (__do_rehash.first) 1811 _M_rehash(__do_rehash.second, __saved_state); 1812 1813 this->_M_store_code(__node, __code); 1814 size_type __bkt = _M_bucket_index(__k, __code); 1815 1816 // Find the node before an equivalent one or use hint if it exists and 1817 // if it is equivalent. 1818 __node_base* __prev 1819 = __builtin_expect(__hint != nullptr, false) 1820 && this->_M_equals(__k, __code, __hint) 1821 ? __hint 1822 : _M_find_before_node(__bkt, __k, __code); 1823 if (__prev) 1824 { 1825 // Insert after the node before the equivalent one. 1826 __node->_M_nxt = __prev->_M_nxt; 1827 __prev->_M_nxt = __node; 1828 if (__builtin_expect(__prev == __hint, false)) 1829 // hint might be the last bucket node, in this case we need to 1830 // update next bucket. 1831 if (__node->_M_nxt 1832 && !this->_M_equals(__k, __code, __node->_M_next())) 1833 { 1834 size_type __next_bkt = _M_bucket_index(__node->_M_next()); 1835 if (__next_bkt != __bkt) 1836 _M_buckets[__next_bkt] = __node; 1837 } 1838 } 1839 else 1840 // The inserted node has no equivalent in the hashtable. We must 1841 // insert the new node at the beginning of the bucket to preserve 1842 // equivalent elements' relative positions. 1843 _M_insert_bucket_begin(__bkt, __node); 1844 ++_M_element_count; 1845 return iterator(__node); 1846 } 1847 1848 // Insert v if no element with its key is already present. 1849 template<typename _Key, typename _Value, 1850 typename _Alloc, typename _ExtractKey, typename _Equal, 1851 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 1852 typename _Traits> 1853 template<typename _Arg, typename _NodeGenerator> 1854 auto 1855 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, 1856 _H1, _H2, _Hash, _RehashPolicy, _Traits>:: 1857 _M_insert(_Arg&& __v, const _NodeGenerator& __node_gen, true_type, 1858 size_type __n_elt) 1859 -> pair<iterator, bool> 1860 { 1861 const key_type& __k = this->_M_extract()(__v); 1862 __hash_code __code = this->_M_hash_code(__k); 1863 size_type __bkt = _M_bucket_index(__k, __code); 1864 1865 if (__node_type* __node = _M_find_node(__bkt, __k, __code)) 1866 return { iterator(__node), false }; 1867 1868 _Scoped_node __node{ __node_gen(std::forward<_Arg>(__v)), this }; 1869 auto __pos 1870 = _M_insert_unique_node(__k, __bkt, __code, __node._M_node, __n_elt); 1871 __node._M_node = nullptr; 1872 return { __pos, true }; 1873 } 1874 1875 // Insert v unconditionally. 1876 template<typename _Key, typename _Value, 1877 typename _Alloc, typename _ExtractKey, typename _Equal, 1878 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 1879 typename _Traits> 1880 template<typename _Arg, typename _NodeGenerator> 1881 auto 1882 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, 1883 _H1, _H2, _Hash, _RehashPolicy, _Traits>:: 1884 _M_insert(const_iterator __hint, _Arg&& __v, 1885 const _NodeGenerator& __node_gen, false_type) 1886 -> iterator 1887 { 1888 // First compute the hash code so that we don't do anything if it 1889 // throws. 1890 __hash_code __code = this->_M_hash_code(this->_M_extract()(__v)); 1891 1892 // Second allocate new node so that we don't rehash if it throws. 1893 _Scoped_node __node{ __node_gen(std::forward<_Arg>(__v)), this }; 1894 const key_type& __k = this->_M_extract()(__node._M_node->_M_v()); 1895 auto __pos 1896 = _M_insert_multi_node(__hint._M_cur, __k, __code, __node._M_node); 1897 __node._M_node = nullptr; 1898 return __pos; 1899 } 1900 1901 template<typename _Key, typename _Value, 1902 typename _Alloc, typename _ExtractKey, typename _Equal, 1903 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 1904 typename _Traits> 1905 auto 1906 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, 1907 _H1, _H2, _Hash, _RehashPolicy, _Traits>:: 1908 erase(const_iterator __it) 1909 -> iterator 1910 { 1911 __node_type* __n = __it._M_cur; 1912 std::size_t __bkt = _M_bucket_index(__n); 1913 1914 // Look for previous node to unlink it from the erased one, this 1915 // is why we need buckets to contain the before begin to make 1916 // this search fast. 1917 __node_base* __prev_n = _M_get_previous_node(__bkt, __n); 1918 return _M_erase(__bkt, __prev_n, __n); 1919 } 1920 1921 template<typename _Key, typename _Value, 1922 typename _Alloc, typename _ExtractKey, typename _Equal, 1923 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 1924 typename _Traits> 1925 auto 1926 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, 1927 _H1, _H2, _Hash, _RehashPolicy, _Traits>:: 1928 _M_erase(size_type __bkt, __node_base* __prev_n, __node_type* __n) 1929 -> iterator 1930 { 1931 if (__prev_n == _M_buckets[__bkt]) 1932 _M_remove_bucket_begin(__bkt, __n->_M_next(), 1933 __n->_M_nxt ? _M_bucket_index(__n->_M_next()) : 0); 1934 else if (__n->_M_nxt) 1935 { 1936 size_type __next_bkt = _M_bucket_index(__n->_M_next()); 1937 if (__next_bkt != __bkt) 1938 _M_buckets[__next_bkt] = __prev_n; 1939 } 1940 1941 __prev_n->_M_nxt = __n->_M_nxt; 1942 iterator __result(__n->_M_next()); 1943 this->_M_deallocate_node(__n); 1944 --_M_element_count; 1945 1946 return __result; 1947 } 1948 1949 template<typename _Key, typename _Value, 1950 typename _Alloc, typename _ExtractKey, typename _Equal, 1951 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 1952 typename _Traits> 1953 auto 1954 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, 1955 _H1, _H2, _Hash, _RehashPolicy, _Traits>:: 1956 _M_erase(true_type, const key_type& __k) 1957 -> size_type 1958 { 1959 __hash_code __code = this->_M_hash_code(__k); 1960 std::size_t __bkt = _M_bucket_index(__k, __code); 1961 1962 // Look for the node before the first matching node. 1963 __node_base* __prev_n = _M_find_before_node(__bkt, __k, __code); 1964 if (!__prev_n) 1965 return 0; 1966 1967 // We found a matching node, erase it. 1968 __node_type* __n = static_cast<__node_type*>(__prev_n->_M_nxt); 1969 _M_erase(__bkt, __prev_n, __n); 1970 return 1; 1971 } 1972 1973 template<typename _Key, typename _Value, 1974 typename _Alloc, typename _ExtractKey, typename _Equal, 1975 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 1976 typename _Traits> 1977 auto 1978 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, 1979 _H1, _H2, _Hash, _RehashPolicy, _Traits>:: 1980 _M_erase(false_type, const key_type& __k) 1981 -> size_type 1982 { 1983 __hash_code __code = this->_M_hash_code(__k); 1984 std::size_t __bkt = _M_bucket_index(__k, __code); 1985 1986 // Look for the node before the first matching node. 1987 __node_base* __prev_n = _M_find_before_node(__bkt, __k, __code); 1988 if (!__prev_n) 1989 return 0; 1990 1991 // _GLIBCXX_RESOLVE_LIB_DEFECTS 1992 // 526. Is it undefined if a function in the standard changes 1993 // in parameters? 1994 // We use one loop to find all matching nodes and another to deallocate 1995 // them so that the key stays valid during the first loop. It might be 1996 // invalidated indirectly when destroying nodes. 1997 __node_type* __n = static_cast<__node_type*>(__prev_n->_M_nxt); 1998 __node_type* __n_last = __n; 1999 std::size_t __n_last_bkt = __bkt; 2000 do 2001 { 2002 __n_last = __n_last->_M_next(); 2003 if (!__n_last) 2004 break; 2005 __n_last_bkt = _M_bucket_index(__n_last); 2006 } 2007 while (__n_last_bkt == __bkt && this->_M_equals(__k, __code, __n_last)); 2008 2009 // Deallocate nodes. 2010 size_type __result = 0; 2011 do 2012 { 2013 __node_type* __p = __n->_M_next(); 2014 this->_M_deallocate_node(__n); 2015 __n = __p; 2016 ++__result; 2017 --_M_element_count; 2018 } 2019 while (__n != __n_last); 2020 2021 if (__prev_n == _M_buckets[__bkt]) 2022 _M_remove_bucket_begin(__bkt, __n_last, __n_last_bkt); 2023 else if (__n_last && __n_last_bkt != __bkt) 2024 _M_buckets[__n_last_bkt] = __prev_n; 2025 __prev_n->_M_nxt = __n_last; 2026 return __result; 2027 } 2028 2029 template<typename _Key, typename _Value, 2030 typename _Alloc, typename _ExtractKey, typename _Equal, 2031 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 2032 typename _Traits> 2033 auto 2034 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, 2035 _H1, _H2, _Hash, _RehashPolicy, _Traits>:: 2036 erase(const_iterator __first, const_iterator __last) 2037 -> iterator 2038 { 2039 __node_type* __n = __first._M_cur; 2040 __node_type* __last_n = __last._M_cur; 2041 if (__n == __last_n) 2042 return iterator(__n); 2043 2044 std::size_t __bkt = _M_bucket_index(__n); 2045 2046 __node_base* __prev_n = _M_get_previous_node(__bkt, __n); 2047 bool __is_bucket_begin = __n == _M_bucket_begin(__bkt); 2048 std::size_t __n_bkt = __bkt; 2049 for (;;) 2050 { 2051 do 2052 { 2053 __node_type* __tmp = __n; 2054 __n = __n->_M_next(); 2055 this->_M_deallocate_node(__tmp); 2056 --_M_element_count; 2057 if (!__n) 2058 break; 2059 __n_bkt = _M_bucket_index(__n); 2060 } 2061 while (__n != __last_n && __n_bkt == __bkt); 2062 if (__is_bucket_begin) 2063 _M_remove_bucket_begin(__bkt, __n, __n_bkt); 2064 if (__n == __last_n) 2065 break; 2066 __is_bucket_begin = true; 2067 __bkt = __n_bkt; 2068 } 2069 2070 if (__n && (__n_bkt != __bkt || __is_bucket_begin)) 2071 _M_buckets[__n_bkt] = __prev_n; 2072 __prev_n->_M_nxt = __n; 2073 return iterator(__n); 2074 } 2075 2076 template<typename _Key, typename _Value, 2077 typename _Alloc, typename _ExtractKey, typename _Equal, 2078 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 2079 typename _Traits> 2080 void 2081 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, 2082 _H1, _H2, _Hash, _RehashPolicy, _Traits>:: 2083 clear() noexcept 2084 { 2085 this->_M_deallocate_nodes(_M_begin()); 2086 __builtin_memset(_M_buckets, 0, _M_bucket_count * sizeof(__bucket_type)); 2087 _M_element_count = 0; 2088 _M_before_begin._M_nxt = nullptr; 2089 } 2090 2091 template<typename _Key, typename _Value, 2092 typename _Alloc, typename _ExtractKey, typename _Equal, 2093 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 2094 typename _Traits> 2095 void 2096 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, 2097 _H1, _H2, _Hash, _RehashPolicy, _Traits>:: 2098 rehash(size_type __bkt_count) 2099 { 2100 const __rehash_state& __saved_state = _M_rehash_policy._M_state(); 2101 __bkt_count 2102 = std::max(_M_rehash_policy._M_bkt_for_elements(_M_element_count + 1), 2103 __bkt_count); 2104 __bkt_count = _M_rehash_policy._M_next_bkt(__bkt_count); 2105 2106 if (__bkt_count != _M_bucket_count) 2107 _M_rehash(__bkt_count, __saved_state); 2108 else 2109 // No rehash, restore previous state to keep it consistent with 2110 // container state. 2111 _M_rehash_policy._M_reset(__saved_state); 2112 } 2113 2114 template<typename _Key, typename _Value, 2115 typename _Alloc, typename _ExtractKey, typename _Equal, 2116 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 2117 typename _Traits> 2118 void 2119 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, 2120 _H1, _H2, _Hash, _RehashPolicy, _Traits>:: 2121 _M_rehash(size_type __bkt_count, const __rehash_state& __state) 2122 { 2123 __try 2124 { 2125 _M_rehash_aux(__bkt_count, __unique_keys()); 2126 } 2127 __catch(...) 2128 { 2129 // A failure here means that buckets allocation failed. We only 2130 // have to restore hash policy previous state. 2131 _M_rehash_policy._M_reset(__state); 2132 __throw_exception_again; 2133 } 2134 } 2135 2136 // Rehash when there is no equivalent elements. 2137 template<typename _Key, typename _Value, 2138 typename _Alloc, typename _ExtractKey, typename _Equal, 2139 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 2140 typename _Traits> 2141 void 2142 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, 2143 _H1, _H2, _Hash, _RehashPolicy, _Traits>:: 2144 _M_rehash_aux(size_type __bkt_count, true_type) 2145 { 2146 __bucket_type* __new_buckets = _M_allocate_buckets(__bkt_count); 2147 __node_type* __p = _M_begin(); 2148 _M_before_begin._M_nxt = nullptr; 2149 std::size_t __bbegin_bkt = 0; 2150 while (__p) 2151 { 2152 __node_type* __next = __p->_M_next(); 2153 std::size_t __bkt 2154 = __hash_code_base::_M_bucket_index(__p, __bkt_count); 2155 if (!__new_buckets[__bkt]) 2156 { 2157 __p->_M_nxt = _M_before_begin._M_nxt; 2158 _M_before_begin._M_nxt = __p; 2159 __new_buckets[__bkt] = &_M_before_begin; 2160 if (__p->_M_nxt) 2161 __new_buckets[__bbegin_bkt] = __p; 2162 __bbegin_bkt = __bkt; 2163 } 2164 else 2165 { 2166 __p->_M_nxt = __new_buckets[__bkt]->_M_nxt; 2167 __new_buckets[__bkt]->_M_nxt = __p; 2168 } 2169 __p = __next; 2170 } 2171 2172 _M_deallocate_buckets(); 2173 _M_bucket_count = __bkt_count; 2174 _M_buckets = __new_buckets; 2175 } 2176 2177 // Rehash when there can be equivalent elements, preserve their relative 2178 // order. 2179 template<typename _Key, typename _Value, 2180 typename _Alloc, typename _ExtractKey, typename _Equal, 2181 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 2182 typename _Traits> 2183 void 2184 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, 2185 _H1, _H2, _Hash, _RehashPolicy, _Traits>:: 2186 _M_rehash_aux(size_type __bkt_count, false_type) 2187 { 2188 __bucket_type* __new_buckets = _M_allocate_buckets(__bkt_count); 2189 2190 __node_type* __p = _M_begin(); 2191 _M_before_begin._M_nxt = nullptr; 2192 std::size_t __bbegin_bkt = 0; 2193 std::size_t __prev_bkt = 0; 2194 __node_type* __prev_p = nullptr; 2195 bool __check_bucket = false; 2196 2197 while (__p) 2198 { 2199 __node_type* __next = __p->_M_next(); 2200 std::size_t __bkt 2201 = __hash_code_base::_M_bucket_index(__p, __bkt_count); 2202 2203 if (__prev_p && __prev_bkt == __bkt) 2204 { 2205 // Previous insert was already in this bucket, we insert after 2206 // the previously inserted one to preserve equivalent elements 2207 // relative order. 2208 __p->_M_nxt = __prev_p->_M_nxt; 2209 __prev_p->_M_nxt = __p; 2210 2211 // Inserting after a node in a bucket require to check that we 2212 // haven't change the bucket last node, in this case next 2213 // bucket containing its before begin node must be updated. We 2214 // schedule a check as soon as we move out of the sequence of 2215 // equivalent nodes to limit the number of checks. 2216 __check_bucket = true; 2217 } 2218 else 2219 { 2220 if (__check_bucket) 2221 { 2222 // Check if we shall update the next bucket because of 2223 // insertions into __prev_bkt bucket. 2224 if (__prev_p->_M_nxt) 2225 { 2226 std::size_t __next_bkt 2227 = __hash_code_base::_M_bucket_index(__prev_p->_M_next(), 2228 __bkt_count); 2229 if (__next_bkt != __prev_bkt) 2230 __new_buckets[__next_bkt] = __prev_p; 2231 } 2232 __check_bucket = false; 2233 } 2234 2235 if (!__new_buckets[__bkt]) 2236 { 2237 __p->_M_nxt = _M_before_begin._M_nxt; 2238 _M_before_begin._M_nxt = __p; 2239 __new_buckets[__bkt] = &_M_before_begin; 2240 if (__p->_M_nxt) 2241 __new_buckets[__bbegin_bkt] = __p; 2242 __bbegin_bkt = __bkt; 2243 } 2244 else 2245 { 2246 __p->_M_nxt = __new_buckets[__bkt]->_M_nxt; 2247 __new_buckets[__bkt]->_M_nxt = __p; 2248 } 2249 } 2250 __prev_p = __p; 2251 __prev_bkt = __bkt; 2252 __p = __next; 2253 } 2254 2255 if (__check_bucket && __prev_p->_M_nxt) 2256 { 2257 std::size_t __next_bkt 2258 = __hash_code_base::_M_bucket_index(__prev_p->_M_next(), 2259 __bkt_count); 2260 if (__next_bkt != __prev_bkt) 2261 __new_buckets[__next_bkt] = __prev_p; 2262 } 2263 2264 _M_deallocate_buckets(); 2265 _M_bucket_count = __bkt_count; 2266 _M_buckets = __new_buckets; 2267 } 2268 2269 #if __cplusplus > 201402L 2270 template<typename, typename, typename> class _Hash_merge_helper { }; 2271 #endif // C++17 2272 2273 #if __cpp_deduction_guides >= 201606 2274 // Used to constrain deduction guides 2275 template<typename _Hash> 2276 using _RequireNotAllocatorOrIntegral 2277 = __enable_if_t<!__or_<is_integral<_Hash>, __is_allocator<_Hash>>::value>; 2278 #endif 2279 2280 _GLIBCXX_END_NAMESPACE_VERSION 2281 } // namespace std 2282 2283 #endif // _HASHTABLE_H 2284