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 1226 if (__former_buckets) 1227 _M_deallocate_buckets(__former_buckets, __former_bucket_count); 1228 __ht.clear(); 1229 } 1230 __catch(...) 1231 { 1232 if (__former_buckets) 1233 { 1234 _M_deallocate_buckets(); 1235 _M_rehash_policy._M_reset(__former_state); 1236 _M_buckets = __former_buckets; 1237 _M_bucket_count = __former_bucket_count; 1238 } 1239 __builtin_memset(_M_buckets, 0, 1240 _M_bucket_count * sizeof(__bucket_type)); 1241 __throw_exception_again; 1242 } 1243 } 1244 } 1245 1246 template<typename _Key, typename _Value, 1247 typename _Alloc, typename _ExtractKey, typename _Equal, 1248 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 1249 typename _Traits> 1250 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, 1251 _H1, _H2, _Hash, _RehashPolicy, _Traits>:: 1252 _Hashtable(const _Hashtable& __ht) 1253 : __hashtable_base(__ht), 1254 __map_base(__ht), 1255 __rehash_base(__ht), 1256 __hashtable_alloc( 1257 __node_alloc_traits::_S_select_on_copy(__ht._M_node_allocator())), 1258 _M_buckets(nullptr), 1259 _M_bucket_count(__ht._M_bucket_count), 1260 _M_element_count(__ht._M_element_count), 1261 _M_rehash_policy(__ht._M_rehash_policy) 1262 { 1263 _M_assign(__ht, 1264 [this](const __node_type* __n) 1265 { return this->_M_allocate_node(__n->_M_v()); }); 1266 } 1267 1268 template<typename _Key, typename _Value, 1269 typename _Alloc, typename _ExtractKey, typename _Equal, 1270 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 1271 typename _Traits> 1272 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, 1273 _H1, _H2, _Hash, _RehashPolicy, _Traits>:: 1274 _Hashtable(_Hashtable&& __ht) noexcept 1275 : __hashtable_base(__ht), 1276 __map_base(__ht), 1277 __rehash_base(__ht), 1278 __hashtable_alloc(std::move(__ht._M_base_alloc())), 1279 _M_buckets(__ht._M_buckets), 1280 _M_bucket_count(__ht._M_bucket_count), 1281 _M_before_begin(__ht._M_before_begin._M_nxt), 1282 _M_element_count(__ht._M_element_count), 1283 _M_rehash_policy(__ht._M_rehash_policy) 1284 { 1285 // Update, if necessary, buckets if __ht is using its single bucket. 1286 if (__ht._M_uses_single_bucket()) 1287 { 1288 _M_buckets = &_M_single_bucket; 1289 _M_single_bucket = __ht._M_single_bucket; 1290 } 1291 1292 // Update, if necessary, bucket pointing to before begin that hasn't 1293 // moved. 1294 if (_M_begin()) 1295 _M_buckets[_M_bucket_index(_M_begin())] = &_M_before_begin; 1296 1297 __ht._M_reset(); 1298 } 1299 1300 template<typename _Key, typename _Value, 1301 typename _Alloc, typename _ExtractKey, typename _Equal, 1302 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 1303 typename _Traits> 1304 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, 1305 _H1, _H2, _Hash, _RehashPolicy, _Traits>:: 1306 _Hashtable(const _Hashtable& __ht, const allocator_type& __a) 1307 : __hashtable_base(__ht), 1308 __map_base(__ht), 1309 __rehash_base(__ht), 1310 __hashtable_alloc(__node_alloc_type(__a)), 1311 _M_buckets(), 1312 _M_bucket_count(__ht._M_bucket_count), 1313 _M_element_count(__ht._M_element_count), 1314 _M_rehash_policy(__ht._M_rehash_policy) 1315 { 1316 _M_assign(__ht, 1317 [this](const __node_type* __n) 1318 { return this->_M_allocate_node(__n->_M_v()); }); 1319 } 1320 1321 template<typename _Key, typename _Value, 1322 typename _Alloc, typename _ExtractKey, typename _Equal, 1323 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 1324 typename _Traits> 1325 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, 1326 _H1, _H2, _Hash, _RehashPolicy, _Traits>:: 1327 _Hashtable(_Hashtable&& __ht, const allocator_type& __a) 1328 : __hashtable_base(__ht), 1329 __map_base(__ht), 1330 __rehash_base(__ht), 1331 __hashtable_alloc(__node_alloc_type(__a)), 1332 _M_buckets(nullptr), 1333 _M_bucket_count(__ht._M_bucket_count), 1334 _M_element_count(__ht._M_element_count), 1335 _M_rehash_policy(__ht._M_rehash_policy) 1336 { 1337 if (__ht._M_node_allocator() == this->_M_node_allocator()) 1338 { 1339 if (__ht._M_uses_single_bucket()) 1340 { 1341 _M_buckets = &_M_single_bucket; 1342 _M_single_bucket = __ht._M_single_bucket; 1343 } 1344 else 1345 _M_buckets = __ht._M_buckets; 1346 1347 _M_before_begin._M_nxt = __ht._M_before_begin._M_nxt; 1348 // Update, if necessary, bucket pointing to before begin that hasn't 1349 // moved. 1350 if (_M_begin()) 1351 _M_buckets[_M_bucket_index(_M_begin())] = &_M_before_begin; 1352 __ht._M_reset(); 1353 } 1354 else 1355 { 1356 _M_assign(__ht, 1357 [this](__node_type* __n) 1358 { 1359 return this->_M_allocate_node( 1360 std::move_if_noexcept(__n->_M_v())); 1361 }); 1362 __ht.clear(); 1363 } 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() noexcept 1373 { 1374 clear(); 1375 _M_deallocate_buckets(); 1376 } 1377 1378 template<typename _Key, typename _Value, 1379 typename _Alloc, typename _ExtractKey, typename _Equal, 1380 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 1381 typename _Traits> 1382 void 1383 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, 1384 _H1, _H2, _Hash, _RehashPolicy, _Traits>:: 1385 swap(_Hashtable& __x) 1386 noexcept(__and_<__is_nothrow_swappable<_H1>, 1387 __is_nothrow_swappable<_Equal>>::value) 1388 { 1389 // The only base class with member variables is hash_code_base. 1390 // We define _Hash_code_base::_M_swap because different 1391 // specializations have different members. 1392 this->_M_swap(__x); 1393 1394 std::__alloc_on_swap(this->_M_node_allocator(), __x._M_node_allocator()); 1395 std::swap(_M_rehash_policy, __x._M_rehash_policy); 1396 1397 // Deal properly with potentially moved instances. 1398 if (this->_M_uses_single_bucket()) 1399 { 1400 if (!__x._M_uses_single_bucket()) 1401 { 1402 _M_buckets = __x._M_buckets; 1403 __x._M_buckets = &__x._M_single_bucket; 1404 } 1405 } 1406 else if (__x._M_uses_single_bucket()) 1407 { 1408 __x._M_buckets = _M_buckets; 1409 _M_buckets = &_M_single_bucket; 1410 } 1411 else 1412 std::swap(_M_buckets, __x._M_buckets); 1413 1414 std::swap(_M_bucket_count, __x._M_bucket_count); 1415 std::swap(_M_before_begin._M_nxt, __x._M_before_begin._M_nxt); 1416 std::swap(_M_element_count, __x._M_element_count); 1417 std::swap(_M_single_bucket, __x._M_single_bucket); 1418 1419 // Fix buckets containing the _M_before_begin pointers that can't be 1420 // swapped. 1421 if (_M_begin()) 1422 _M_buckets[_M_bucket_index(_M_begin())] = &_M_before_begin; 1423 1424 if (__x._M_begin()) 1425 __x._M_buckets[__x._M_bucket_index(__x._M_begin())] 1426 = &__x._M_before_begin; 1427 } 1428 1429 template<typename _Key, typename _Value, 1430 typename _Alloc, typename _ExtractKey, typename _Equal, 1431 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 1432 typename _Traits> 1433 auto 1434 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, 1435 _H1, _H2, _Hash, _RehashPolicy, _Traits>:: 1436 find(const key_type& __k) 1437 -> iterator 1438 { 1439 __hash_code __code = this->_M_hash_code(__k); 1440 std::size_t __n = _M_bucket_index(__k, __code); 1441 __node_type* __p = _M_find_node(__n, __k, __code); 1442 return __p ? iterator(__p) : end(); 1443 } 1444 1445 template<typename _Key, typename _Value, 1446 typename _Alloc, typename _ExtractKey, typename _Equal, 1447 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 1448 typename _Traits> 1449 auto 1450 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, 1451 _H1, _H2, _Hash, _RehashPolicy, _Traits>:: 1452 find(const key_type& __k) const 1453 -> const_iterator 1454 { 1455 __hash_code __code = this->_M_hash_code(__k); 1456 std::size_t __n = _M_bucket_index(__k, __code); 1457 __node_type* __p = _M_find_node(__n, __k, __code); 1458 return __p ? const_iterator(__p) : end(); 1459 } 1460 1461 template<typename _Key, typename _Value, 1462 typename _Alloc, typename _ExtractKey, typename _Equal, 1463 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 1464 typename _Traits> 1465 auto 1466 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, 1467 _H1, _H2, _Hash, _RehashPolicy, _Traits>:: 1468 count(const key_type& __k) const 1469 -> size_type 1470 { 1471 __hash_code __code = this->_M_hash_code(__k); 1472 std::size_t __n = _M_bucket_index(__k, __code); 1473 __node_type* __p = _M_bucket_begin(__n); 1474 if (!__p) 1475 return 0; 1476 1477 std::size_t __result = 0; 1478 for (;; __p = __p->_M_next()) 1479 { 1480 if (this->_M_equals(__k, __code, __p)) 1481 ++__result; 1482 else if (__result) 1483 // All equivalent values are next to each other, if we 1484 // found a non-equivalent value after an equivalent one it 1485 // means that we won't find any new equivalent value. 1486 break; 1487 if (!__p->_M_nxt || _M_bucket_index(__p->_M_next()) != __n) 1488 break; 1489 } 1490 return __result; 1491 } 1492 1493 template<typename _Key, typename _Value, 1494 typename _Alloc, typename _ExtractKey, typename _Equal, 1495 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 1496 typename _Traits> 1497 auto 1498 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, 1499 _H1, _H2, _Hash, _RehashPolicy, _Traits>:: 1500 equal_range(const key_type& __k) 1501 -> pair<iterator, iterator> 1502 { 1503 __hash_code __code = this->_M_hash_code(__k); 1504 std::size_t __n = _M_bucket_index(__k, __code); 1505 __node_type* __p = _M_find_node(__n, __k, __code); 1506 1507 if (__p) 1508 { 1509 __node_type* __p1 = __p->_M_next(); 1510 while (__p1 && _M_bucket_index(__p1) == __n 1511 && this->_M_equals(__k, __code, __p1)) 1512 __p1 = __p1->_M_next(); 1513 1514 return std::make_pair(iterator(__p), iterator(__p1)); 1515 } 1516 else 1517 return std::make_pair(end(), end()); 1518 } 1519 1520 template<typename _Key, typename _Value, 1521 typename _Alloc, typename _ExtractKey, typename _Equal, 1522 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 1523 typename _Traits> 1524 auto 1525 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, 1526 _H1, _H2, _Hash, _RehashPolicy, _Traits>:: 1527 equal_range(const key_type& __k) const 1528 -> pair<const_iterator, const_iterator> 1529 { 1530 __hash_code __code = this->_M_hash_code(__k); 1531 std::size_t __n = _M_bucket_index(__k, __code); 1532 __node_type* __p = _M_find_node(__n, __k, __code); 1533 1534 if (__p) 1535 { 1536 __node_type* __p1 = __p->_M_next(); 1537 while (__p1 && _M_bucket_index(__p1) == __n 1538 && this->_M_equals(__k, __code, __p1)) 1539 __p1 = __p1->_M_next(); 1540 1541 return std::make_pair(const_iterator(__p), const_iterator(__p1)); 1542 } 1543 else 1544 return std::make_pair(end(), end()); 1545 } 1546 1547 // Find the node whose key compares equal to k in the bucket n. 1548 // Return nullptr if no node is found. 1549 template<typename _Key, typename _Value, 1550 typename _Alloc, typename _ExtractKey, typename _Equal, 1551 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 1552 typename _Traits> 1553 auto 1554 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, 1555 _H1, _H2, _Hash, _RehashPolicy, _Traits>:: 1556 _M_find_before_node(size_type __n, const key_type& __k, 1557 __hash_code __code) const 1558 -> __node_base* 1559 { 1560 __node_base* __prev_p = _M_buckets[__n]; 1561 if (!__prev_p) 1562 return nullptr; 1563 1564 for (__node_type* __p = static_cast<__node_type*>(__prev_p->_M_nxt);; 1565 __p = __p->_M_next()) 1566 { 1567 if (this->_M_equals(__k, __code, __p)) 1568 return __prev_p; 1569 1570 if (!__p->_M_nxt || _M_bucket_index(__p->_M_next()) != __n) 1571 break; 1572 __prev_p = __p; 1573 } 1574 return nullptr; 1575 } 1576 1577 template<typename _Key, typename _Value, 1578 typename _Alloc, typename _ExtractKey, typename _Equal, 1579 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 1580 typename _Traits> 1581 void 1582 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, 1583 _H1, _H2, _Hash, _RehashPolicy, _Traits>:: 1584 _M_insert_bucket_begin(size_type __bkt, __node_type* __node) 1585 { 1586 if (_M_buckets[__bkt]) 1587 { 1588 // Bucket is not empty, we just need to insert the new node 1589 // after the bucket before begin. 1590 __node->_M_nxt = _M_buckets[__bkt]->_M_nxt; 1591 _M_buckets[__bkt]->_M_nxt = __node; 1592 } 1593 else 1594 { 1595 // The bucket is empty, the new node is inserted at the 1596 // beginning of the singly-linked list and the bucket will 1597 // contain _M_before_begin pointer. 1598 __node->_M_nxt = _M_before_begin._M_nxt; 1599 _M_before_begin._M_nxt = __node; 1600 if (__node->_M_nxt) 1601 // We must update former begin bucket that is pointing to 1602 // _M_before_begin. 1603 _M_buckets[_M_bucket_index(__node->_M_next())] = __node; 1604 _M_buckets[__bkt] = &_M_before_begin; 1605 } 1606 } 1607 1608 template<typename _Key, typename _Value, 1609 typename _Alloc, typename _ExtractKey, typename _Equal, 1610 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 1611 typename _Traits> 1612 void 1613 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, 1614 _H1, _H2, _Hash, _RehashPolicy, _Traits>:: 1615 _M_remove_bucket_begin(size_type __bkt, __node_type* __next, 1616 size_type __next_bkt) 1617 { 1618 if (!__next || __next_bkt != __bkt) 1619 { 1620 // Bucket is now empty 1621 // First update next bucket if any 1622 if (__next) 1623 _M_buckets[__next_bkt] = _M_buckets[__bkt]; 1624 1625 // Second update before begin node if necessary 1626 if (&_M_before_begin == _M_buckets[__bkt]) 1627 _M_before_begin._M_nxt = __next; 1628 _M_buckets[__bkt] = nullptr; 1629 } 1630 } 1631 1632 template<typename _Key, typename _Value, 1633 typename _Alloc, typename _ExtractKey, typename _Equal, 1634 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 1635 typename _Traits> 1636 auto 1637 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, 1638 _H1, _H2, _Hash, _RehashPolicy, _Traits>:: 1639 _M_get_previous_node(size_type __bkt, __node_base* __n) 1640 -> __node_base* 1641 { 1642 __node_base* __prev_n = _M_buckets[__bkt]; 1643 while (__prev_n->_M_nxt != __n) 1644 __prev_n = __prev_n->_M_nxt; 1645 return __prev_n; 1646 } 1647 1648 template<typename _Key, typename _Value, 1649 typename _Alloc, typename _ExtractKey, typename _Equal, 1650 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 1651 typename _Traits> 1652 template<typename... _Args> 1653 auto 1654 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, 1655 _H1, _H2, _Hash, _RehashPolicy, _Traits>:: 1656 _M_emplace(std::true_type, _Args&&... __args) 1657 -> pair<iterator, bool> 1658 { 1659 // First build the node to get access to the hash code 1660 __node_type* __node = this->_M_allocate_node(std::forward<_Args>(__args)...); 1661 const key_type& __k = this->_M_extract()(__node->_M_v()); 1662 __hash_code __code; 1663 __try 1664 { 1665 __code = this->_M_hash_code(__k); 1666 } 1667 __catch(...) 1668 { 1669 this->_M_deallocate_node(__node); 1670 __throw_exception_again; 1671 } 1672 1673 size_type __bkt = _M_bucket_index(__k, __code); 1674 if (__node_type* __p = _M_find_node(__bkt, __k, __code)) 1675 { 1676 // There is already an equivalent node, no insertion 1677 this->_M_deallocate_node(__node); 1678 return std::make_pair(iterator(__p), false); 1679 } 1680 1681 // Insert the node 1682 return std::make_pair(_M_insert_unique_node(__bkt, __code, __node), 1683 true); 1684 } 1685 1686 template<typename _Key, typename _Value, 1687 typename _Alloc, typename _ExtractKey, typename _Equal, 1688 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 1689 typename _Traits> 1690 template<typename... _Args> 1691 auto 1692 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, 1693 _H1, _H2, _Hash, _RehashPolicy, _Traits>:: 1694 _M_emplace(const_iterator __hint, std::false_type, _Args&&... __args) 1695 -> iterator 1696 { 1697 // First build the node to get its hash code. 1698 __node_type* __node = 1699 this->_M_allocate_node(std::forward<_Args>(__args)...); 1700 1701 __hash_code __code; 1702 __try 1703 { 1704 __code = this->_M_hash_code(this->_M_extract()(__node->_M_v())); 1705 } 1706 __catch(...) 1707 { 1708 this->_M_deallocate_node(__node); 1709 __throw_exception_again; 1710 } 1711 1712 return _M_insert_multi_node(__hint._M_cur, __code, __node); 1713 } 1714 1715 template<typename _Key, typename _Value, 1716 typename _Alloc, typename _ExtractKey, typename _Equal, 1717 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 1718 typename _Traits> 1719 auto 1720 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, 1721 _H1, _H2, _Hash, _RehashPolicy, _Traits>:: 1722 _M_insert_unique_node(size_type __bkt, __hash_code __code, 1723 __node_type* __node, size_type __n_elt) 1724 -> iterator 1725 { 1726 const __rehash_state& __saved_state = _M_rehash_policy._M_state(); 1727 std::pair<bool, std::size_t> __do_rehash 1728 = _M_rehash_policy._M_need_rehash(_M_bucket_count, _M_element_count, 1729 __n_elt); 1730 1731 __try 1732 { 1733 if (__do_rehash.first) 1734 { 1735 _M_rehash(__do_rehash.second, __saved_state); 1736 __bkt = _M_bucket_index(this->_M_extract()(__node->_M_v()), __code); 1737 } 1738 1739 this->_M_store_code(__node, __code); 1740 1741 // Always insert at the beginning of the bucket. 1742 _M_insert_bucket_begin(__bkt, __node); 1743 ++_M_element_count; 1744 return iterator(__node); 1745 } 1746 __catch(...) 1747 { 1748 this->_M_deallocate_node(__node); 1749 __throw_exception_again; 1750 } 1751 } 1752 1753 // Insert node, in bucket bkt if no rehash (assumes no element with its key 1754 // already present). Take ownership of the node, deallocate it on exception. 1755 template<typename _Key, typename _Value, 1756 typename _Alloc, typename _ExtractKey, typename _Equal, 1757 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 1758 typename _Traits> 1759 auto 1760 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, 1761 _H1, _H2, _Hash, _RehashPolicy, _Traits>:: 1762 _M_insert_multi_node(__node_type* __hint, __hash_code __code, 1763 __node_type* __node) 1764 -> iterator 1765 { 1766 const __rehash_state& __saved_state = _M_rehash_policy._M_state(); 1767 std::pair<bool, std::size_t> __do_rehash 1768 = _M_rehash_policy._M_need_rehash(_M_bucket_count, _M_element_count, 1); 1769 1770 __try 1771 { 1772 if (__do_rehash.first) 1773 _M_rehash(__do_rehash.second, __saved_state); 1774 1775 this->_M_store_code(__node, __code); 1776 const key_type& __k = this->_M_extract()(__node->_M_v()); 1777 size_type __bkt = _M_bucket_index(__k, __code); 1778 1779 // Find the node before an equivalent one or use hint if it exists and 1780 // if it is equivalent. 1781 __node_base* __prev 1782 = __builtin_expect(__hint != nullptr, false) 1783 && this->_M_equals(__k, __code, __hint) 1784 ? __hint 1785 : _M_find_before_node(__bkt, __k, __code); 1786 if (__prev) 1787 { 1788 // Insert after the node before the equivalent one. 1789 __node->_M_nxt = __prev->_M_nxt; 1790 __prev->_M_nxt = __node; 1791 if (__builtin_expect(__prev == __hint, false)) 1792 // hint might be the last bucket node, in this case we need to 1793 // update next bucket. 1794 if (__node->_M_nxt 1795 && !this->_M_equals(__k, __code, __node->_M_next())) 1796 { 1797 size_type __next_bkt = _M_bucket_index(__node->_M_next()); 1798 if (__next_bkt != __bkt) 1799 _M_buckets[__next_bkt] = __node; 1800 } 1801 } 1802 else 1803 // The inserted node has no equivalent in the 1804 // hashtable. We must insert the new node at the 1805 // beginning of the bucket to preserve equivalent 1806 // elements' relative positions. 1807 _M_insert_bucket_begin(__bkt, __node); 1808 ++_M_element_count; 1809 return iterator(__node); 1810 } 1811 __catch(...) 1812 { 1813 this->_M_deallocate_node(__node); 1814 __throw_exception_again; 1815 } 1816 } 1817 1818 // Insert v if no element with its key is already present. 1819 template<typename _Key, typename _Value, 1820 typename _Alloc, typename _ExtractKey, typename _Equal, 1821 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 1822 typename _Traits> 1823 template<typename _Arg, typename _NodeGenerator> 1824 auto 1825 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, 1826 _H1, _H2, _Hash, _RehashPolicy, _Traits>:: 1827 _M_insert(_Arg&& __v, const _NodeGenerator& __node_gen, true_type, 1828 size_type __n_elt) 1829 -> pair<iterator, bool> 1830 { 1831 const key_type& __k = this->_M_extract()(__v); 1832 __hash_code __code = this->_M_hash_code(__k); 1833 size_type __bkt = _M_bucket_index(__k, __code); 1834 1835 __node_type* __n = _M_find_node(__bkt, __k, __code); 1836 if (__n) 1837 return std::make_pair(iterator(__n), false); 1838 1839 __n = __node_gen(std::forward<_Arg>(__v)); 1840 return { _M_insert_unique_node(__bkt, __code, __n, __n_elt), true }; 1841 } 1842 1843 // Insert v unconditionally. 1844 template<typename _Key, typename _Value, 1845 typename _Alloc, typename _ExtractKey, typename _Equal, 1846 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 1847 typename _Traits> 1848 template<typename _Arg, typename _NodeGenerator> 1849 auto 1850 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, 1851 _H1, _H2, _Hash, _RehashPolicy, _Traits>:: 1852 _M_insert(const_iterator __hint, _Arg&& __v, 1853 const _NodeGenerator& __node_gen, false_type) 1854 -> iterator 1855 { 1856 // First compute the hash code so that we don't do anything if it 1857 // throws. 1858 __hash_code __code = this->_M_hash_code(this->_M_extract()(__v)); 1859 1860 // Second allocate new node so that we don't rehash if it throws. 1861 __node_type* __node = __node_gen(std::forward<_Arg>(__v)); 1862 1863 return _M_insert_multi_node(__hint._M_cur, __code, __node); 1864 } 1865 1866 template<typename _Key, typename _Value, 1867 typename _Alloc, typename _ExtractKey, typename _Equal, 1868 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 1869 typename _Traits> 1870 auto 1871 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, 1872 _H1, _H2, _Hash, _RehashPolicy, _Traits>:: 1873 erase(const_iterator __it) 1874 -> iterator 1875 { 1876 __node_type* __n = __it._M_cur; 1877 std::size_t __bkt = _M_bucket_index(__n); 1878 1879 // Look for previous node to unlink it from the erased one, this 1880 // is why we need buckets to contain the before begin to make 1881 // this search fast. 1882 __node_base* __prev_n = _M_get_previous_node(__bkt, __n); 1883 return _M_erase(__bkt, __prev_n, __n); 1884 } 1885 1886 template<typename _Key, typename _Value, 1887 typename _Alloc, typename _ExtractKey, typename _Equal, 1888 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 1889 typename _Traits> 1890 auto 1891 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, 1892 _H1, _H2, _Hash, _RehashPolicy, _Traits>:: 1893 _M_erase(size_type __bkt, __node_base* __prev_n, __node_type* __n) 1894 -> iterator 1895 { 1896 if (__prev_n == _M_buckets[__bkt]) 1897 _M_remove_bucket_begin(__bkt, __n->_M_next(), 1898 __n->_M_nxt ? _M_bucket_index(__n->_M_next()) : 0); 1899 else if (__n->_M_nxt) 1900 { 1901 size_type __next_bkt = _M_bucket_index(__n->_M_next()); 1902 if (__next_bkt != __bkt) 1903 _M_buckets[__next_bkt] = __prev_n; 1904 } 1905 1906 __prev_n->_M_nxt = __n->_M_nxt; 1907 iterator __result(__n->_M_next()); 1908 this->_M_deallocate_node(__n); 1909 --_M_element_count; 1910 1911 return __result; 1912 } 1913 1914 template<typename _Key, typename _Value, 1915 typename _Alloc, typename _ExtractKey, typename _Equal, 1916 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 1917 typename _Traits> 1918 auto 1919 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, 1920 _H1, _H2, _Hash, _RehashPolicy, _Traits>:: 1921 _M_erase(std::true_type, const key_type& __k) 1922 -> size_type 1923 { 1924 __hash_code __code = this->_M_hash_code(__k); 1925 std::size_t __bkt = _M_bucket_index(__k, __code); 1926 1927 // Look for the node before the first matching node. 1928 __node_base* __prev_n = _M_find_before_node(__bkt, __k, __code); 1929 if (!__prev_n) 1930 return 0; 1931 1932 // We found a matching node, erase it. 1933 __node_type* __n = static_cast<__node_type*>(__prev_n->_M_nxt); 1934 _M_erase(__bkt, __prev_n, __n); 1935 return 1; 1936 } 1937 1938 template<typename _Key, typename _Value, 1939 typename _Alloc, typename _ExtractKey, typename _Equal, 1940 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 1941 typename _Traits> 1942 auto 1943 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, 1944 _H1, _H2, _Hash, _RehashPolicy, _Traits>:: 1945 _M_erase(std::false_type, const key_type& __k) 1946 -> size_type 1947 { 1948 __hash_code __code = this->_M_hash_code(__k); 1949 std::size_t __bkt = _M_bucket_index(__k, __code); 1950 1951 // Look for the node before the first matching node. 1952 __node_base* __prev_n = _M_find_before_node(__bkt, __k, __code); 1953 if (!__prev_n) 1954 return 0; 1955 1956 // _GLIBCXX_RESOLVE_LIB_DEFECTS 1957 // 526. Is it undefined if a function in the standard changes 1958 // in parameters? 1959 // We use one loop to find all matching nodes and another to deallocate 1960 // them so that the key stays valid during the first loop. It might be 1961 // invalidated indirectly when destroying nodes. 1962 __node_type* __n = static_cast<__node_type*>(__prev_n->_M_nxt); 1963 __node_type* __n_last = __n; 1964 std::size_t __n_last_bkt = __bkt; 1965 do 1966 { 1967 __n_last = __n_last->_M_next(); 1968 if (!__n_last) 1969 break; 1970 __n_last_bkt = _M_bucket_index(__n_last); 1971 } 1972 while (__n_last_bkt == __bkt && this->_M_equals(__k, __code, __n_last)); 1973 1974 // Deallocate nodes. 1975 size_type __result = 0; 1976 do 1977 { 1978 __node_type* __p = __n->_M_next(); 1979 this->_M_deallocate_node(__n); 1980 __n = __p; 1981 ++__result; 1982 --_M_element_count; 1983 } 1984 while (__n != __n_last); 1985 1986 if (__prev_n == _M_buckets[__bkt]) 1987 _M_remove_bucket_begin(__bkt, __n_last, __n_last_bkt); 1988 else if (__n_last && __n_last_bkt != __bkt) 1989 _M_buckets[__n_last_bkt] = __prev_n; 1990 __prev_n->_M_nxt = __n_last; 1991 return __result; 1992 } 1993 1994 template<typename _Key, typename _Value, 1995 typename _Alloc, typename _ExtractKey, typename _Equal, 1996 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 1997 typename _Traits> 1998 auto 1999 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, 2000 _H1, _H2, _Hash, _RehashPolicy, _Traits>:: 2001 erase(const_iterator __first, const_iterator __last) 2002 -> iterator 2003 { 2004 __node_type* __n = __first._M_cur; 2005 __node_type* __last_n = __last._M_cur; 2006 if (__n == __last_n) 2007 return iterator(__n); 2008 2009 std::size_t __bkt = _M_bucket_index(__n); 2010 2011 __node_base* __prev_n = _M_get_previous_node(__bkt, __n); 2012 bool __is_bucket_begin = __n == _M_bucket_begin(__bkt); 2013 std::size_t __n_bkt = __bkt; 2014 for (;;) 2015 { 2016 do 2017 { 2018 __node_type* __tmp = __n; 2019 __n = __n->_M_next(); 2020 this->_M_deallocate_node(__tmp); 2021 --_M_element_count; 2022 if (!__n) 2023 break; 2024 __n_bkt = _M_bucket_index(__n); 2025 } 2026 while (__n != __last_n && __n_bkt == __bkt); 2027 if (__is_bucket_begin) 2028 _M_remove_bucket_begin(__bkt, __n, __n_bkt); 2029 if (__n == __last_n) 2030 break; 2031 __is_bucket_begin = true; 2032 __bkt = __n_bkt; 2033 } 2034 2035 if (__n && (__n_bkt != __bkt || __is_bucket_begin)) 2036 _M_buckets[__n_bkt] = __prev_n; 2037 __prev_n->_M_nxt = __n; 2038 return iterator(__n); 2039 } 2040 2041 template<typename _Key, typename _Value, 2042 typename _Alloc, typename _ExtractKey, typename _Equal, 2043 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 2044 typename _Traits> 2045 void 2046 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, 2047 _H1, _H2, _Hash, _RehashPolicy, _Traits>:: 2048 clear() noexcept 2049 { 2050 this->_M_deallocate_nodes(_M_begin()); 2051 __builtin_memset(_M_buckets, 0, _M_bucket_count * sizeof(__bucket_type)); 2052 _M_element_count = 0; 2053 _M_before_begin._M_nxt = nullptr; 2054 } 2055 2056 template<typename _Key, typename _Value, 2057 typename _Alloc, typename _ExtractKey, typename _Equal, 2058 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 2059 typename _Traits> 2060 void 2061 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, 2062 _H1, _H2, _Hash, _RehashPolicy, _Traits>:: 2063 rehash(size_type __n) 2064 { 2065 const __rehash_state& __saved_state = _M_rehash_policy._M_state(); 2066 std::size_t __buckets 2067 = std::max(_M_rehash_policy._M_bkt_for_elements(_M_element_count + 1), 2068 __n); 2069 __buckets = _M_rehash_policy._M_next_bkt(__buckets); 2070 2071 if (__buckets != _M_bucket_count) 2072 _M_rehash(__buckets, __saved_state); 2073 else 2074 // No rehash, restore previous state to keep a consistent state. 2075 _M_rehash_policy._M_reset(__saved_state); 2076 } 2077 2078 template<typename _Key, typename _Value, 2079 typename _Alloc, typename _ExtractKey, typename _Equal, 2080 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 2081 typename _Traits> 2082 void 2083 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, 2084 _H1, _H2, _Hash, _RehashPolicy, _Traits>:: 2085 _M_rehash(size_type __n, const __rehash_state& __state) 2086 { 2087 __try 2088 { 2089 _M_rehash_aux(__n, __unique_keys()); 2090 } 2091 __catch(...) 2092 { 2093 // A failure here means that buckets allocation failed. We only 2094 // have to restore hash policy previous state. 2095 _M_rehash_policy._M_reset(__state); 2096 __throw_exception_again; 2097 } 2098 } 2099 2100 // Rehash when there is no equivalent elements. 2101 template<typename _Key, typename _Value, 2102 typename _Alloc, typename _ExtractKey, typename _Equal, 2103 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 2104 typename _Traits> 2105 void 2106 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, 2107 _H1, _H2, _Hash, _RehashPolicy, _Traits>:: 2108 _M_rehash_aux(size_type __n, std::true_type) 2109 { 2110 __bucket_type* __new_buckets = _M_allocate_buckets(__n); 2111 __node_type* __p = _M_begin(); 2112 _M_before_begin._M_nxt = nullptr; 2113 std::size_t __bbegin_bkt = 0; 2114 while (__p) 2115 { 2116 __node_type* __next = __p->_M_next(); 2117 std::size_t __bkt = __hash_code_base::_M_bucket_index(__p, __n); 2118 if (!__new_buckets[__bkt]) 2119 { 2120 __p->_M_nxt = _M_before_begin._M_nxt; 2121 _M_before_begin._M_nxt = __p; 2122 __new_buckets[__bkt] = &_M_before_begin; 2123 if (__p->_M_nxt) 2124 __new_buckets[__bbegin_bkt] = __p; 2125 __bbegin_bkt = __bkt; 2126 } 2127 else 2128 { 2129 __p->_M_nxt = __new_buckets[__bkt]->_M_nxt; 2130 __new_buckets[__bkt]->_M_nxt = __p; 2131 } 2132 __p = __next; 2133 } 2134 2135 _M_deallocate_buckets(); 2136 _M_bucket_count = __n; 2137 _M_buckets = __new_buckets; 2138 } 2139 2140 // Rehash when there can be equivalent elements, preserve their relative 2141 // order. 2142 template<typename _Key, typename _Value, 2143 typename _Alloc, typename _ExtractKey, typename _Equal, 2144 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 2145 typename _Traits> 2146 void 2147 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, 2148 _H1, _H2, _Hash, _RehashPolicy, _Traits>:: 2149 _M_rehash_aux(size_type __n, std::false_type) 2150 { 2151 __bucket_type* __new_buckets = _M_allocate_buckets(__n); 2152 2153 __node_type* __p = _M_begin(); 2154 _M_before_begin._M_nxt = nullptr; 2155 std::size_t __bbegin_bkt = 0; 2156 std::size_t __prev_bkt = 0; 2157 __node_type* __prev_p = nullptr; 2158 bool __check_bucket = false; 2159 2160 while (__p) 2161 { 2162 __node_type* __next = __p->_M_next(); 2163 std::size_t __bkt = __hash_code_base::_M_bucket_index(__p, __n); 2164 2165 if (__prev_p && __prev_bkt == __bkt) 2166 { 2167 // Previous insert was already in this bucket, we insert after 2168 // the previously inserted one to preserve equivalent elements 2169 // relative order. 2170 __p->_M_nxt = __prev_p->_M_nxt; 2171 __prev_p->_M_nxt = __p; 2172 2173 // Inserting after a node in a bucket require to check that we 2174 // haven't change the bucket last node, in this case next 2175 // bucket containing its before begin node must be updated. We 2176 // schedule a check as soon as we move out of the sequence of 2177 // equivalent nodes to limit the number of checks. 2178 __check_bucket = true; 2179 } 2180 else 2181 { 2182 if (__check_bucket) 2183 { 2184 // Check if we shall update the next bucket because of 2185 // insertions into __prev_bkt bucket. 2186 if (__prev_p->_M_nxt) 2187 { 2188 std::size_t __next_bkt 2189 = __hash_code_base::_M_bucket_index(__prev_p->_M_next(), 2190 __n); 2191 if (__next_bkt != __prev_bkt) 2192 __new_buckets[__next_bkt] = __prev_p; 2193 } 2194 __check_bucket = false; 2195 } 2196 2197 if (!__new_buckets[__bkt]) 2198 { 2199 __p->_M_nxt = _M_before_begin._M_nxt; 2200 _M_before_begin._M_nxt = __p; 2201 __new_buckets[__bkt] = &_M_before_begin; 2202 if (__p->_M_nxt) 2203 __new_buckets[__bbegin_bkt] = __p; 2204 __bbegin_bkt = __bkt; 2205 } 2206 else 2207 { 2208 __p->_M_nxt = __new_buckets[__bkt]->_M_nxt; 2209 __new_buckets[__bkt]->_M_nxt = __p; 2210 } 2211 } 2212 __prev_p = __p; 2213 __prev_bkt = __bkt; 2214 __p = __next; 2215 } 2216 2217 if (__check_bucket && __prev_p->_M_nxt) 2218 { 2219 std::size_t __next_bkt 2220 = __hash_code_base::_M_bucket_index(__prev_p->_M_next(), __n); 2221 if (__next_bkt != __prev_bkt) 2222 __new_buckets[__next_bkt] = __prev_p; 2223 } 2224 2225 _M_deallocate_buckets(); 2226 _M_bucket_count = __n; 2227 _M_buckets = __new_buckets; 2228 } 2229 2230 #if __cplusplus > 201402L 2231 template<typename, typename, typename> class _Hash_merge_helper { }; 2232 #endif // C++17 2233 2234 _GLIBCXX_END_NAMESPACE_VERSION 2235 } // namespace std 2236 2237 #endif // _HASHTABLE_H 2238