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