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