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 __hashtable_alloc& 320 _M_base_alloc() { return *this; } 321 322 using __hashtable_alloc::_M_deallocate_buckets; 323 324 void 325 _M_deallocate_buckets() 326 { this->_M_deallocate_buckets(_M_buckets, _M_bucket_count); } 327 328 // Gets bucket begin, deals with the fact that non-empty buckets contain 329 // their before begin node. 330 __node_type* 331 _M_bucket_begin(size_type __bkt) const; 332 333 __node_type* 334 _M_begin() const 335 { return static_cast<__node_type*>(_M_before_begin._M_nxt); } 336 337 template<typename _NodeGenerator> 338 void 339 _M_assign(const _Hashtable&, const _NodeGenerator&); 340 341 void 342 _M_move_assign(_Hashtable&&, std::true_type); 343 344 void 345 _M_move_assign(_Hashtable&&, std::false_type); 346 347 void 348 _M_reset() noexcept; 349 350 public: 351 // Constructor, destructor, assignment, swap 352 _Hashtable(size_type __bucket_hint, 353 const _H1&, const _H2&, const _Hash&, 354 const _Equal&, const _ExtractKey&, 355 const allocator_type&); 356 357 template<typename _InputIterator> 358 _Hashtable(_InputIterator __first, _InputIterator __last, 359 size_type __bucket_hint, 360 const _H1&, const _H2&, const _Hash&, 361 const _Equal&, const _ExtractKey&, 362 const allocator_type&); 363 364 _Hashtable(const _Hashtable&); 365 366 _Hashtable(_Hashtable&&) noexcept; 367 368 _Hashtable(const _Hashtable&, const allocator_type&); 369 370 _Hashtable(_Hashtable&&, const allocator_type&); 371 372 // Use delegating constructors. 373 explicit 374 _Hashtable(const allocator_type& __a) 375 : _Hashtable(10, _H1(), _H2(), _Hash(), key_equal(), 376 __key_extract(), __a) 377 { } 378 379 explicit 380 _Hashtable(size_type __n = 10, 381 const _H1& __hf = _H1(), 382 const key_equal& __eql = key_equal(), 383 const allocator_type& __a = allocator_type()) 384 : _Hashtable(__n, __hf, _H2(), _Hash(), __eql, 385 __key_extract(), __a) 386 { } 387 388 template<typename _InputIterator> 389 _Hashtable(_InputIterator __f, _InputIterator __l, 390 size_type __n = 0, 391 const _H1& __hf = _H1(), 392 const key_equal& __eql = key_equal(), 393 const allocator_type& __a = allocator_type()) 394 : _Hashtable(__f, __l, __n, __hf, _H2(), _Hash(), __eql, 395 __key_extract(), __a) 396 { } 397 398 _Hashtable(initializer_list<value_type> __l, 399 size_type __n = 0, 400 const _H1& __hf = _H1(), 401 const key_equal& __eql = key_equal(), 402 const allocator_type& __a = allocator_type()) 403 : _Hashtable(__l.begin(), __l.end(), __n, __hf, _H2(), _Hash(), __eql, 404 __key_extract(), __a) 405 { } 406 407 _Hashtable& 408 operator=(const _Hashtable& __ht); 409 410 _Hashtable& 411 operator=(_Hashtable&& __ht) 412 noexcept(__node_alloc_traits::_S_nothrow_move()) 413 { 414 constexpr bool __move_storage = 415 __node_alloc_traits::_S_propagate_on_move_assign() 416 || __node_alloc_traits::_S_always_equal(); 417 _M_move_assign(std::move(__ht), 418 integral_constant<bool, __move_storage>()); 419 return *this; 420 } 421 422 _Hashtable& 423 operator=(initializer_list<value_type> __l) 424 { 425 __reuse_or_alloc_node_type __roan(_M_begin(), *this); 426 _M_before_begin._M_nxt = nullptr; 427 clear(); 428 this->_M_insert_range(__l.begin(), __l.end(), __roan); 429 return *this; 430 } 431 432 ~_Hashtable() noexcept; 433 434 void 435 swap(_Hashtable&) 436 noexcept(__node_alloc_traits::_S_nothrow_swap()); 437 438 // Basic container operations 439 iterator 440 begin() noexcept 441 { return iterator(_M_begin()); } 442 443 const_iterator 444 begin() const noexcept 445 { return const_iterator(_M_begin()); } 446 447 iterator 448 end() noexcept 449 { return iterator(nullptr); } 450 451 const_iterator 452 end() const noexcept 453 { return const_iterator(nullptr); } 454 455 const_iterator 456 cbegin() const noexcept 457 { return const_iterator(_M_begin()); } 458 459 const_iterator 460 cend() const noexcept 461 { return const_iterator(nullptr); } 462 463 size_type 464 size() const noexcept 465 { return _M_element_count; } 466 467 bool 468 empty() const noexcept 469 { return size() == 0; } 470 471 allocator_type 472 get_allocator() const noexcept 473 { return allocator_type(this->_M_node_allocator()); } 474 475 size_type 476 max_size() const noexcept 477 { return __node_alloc_traits::max_size(this->_M_node_allocator()); } 478 479 // Observers 480 key_equal 481 key_eq() const 482 { return this->_M_eq(); } 483 484 // hash_function, if present, comes from _Hash_code_base. 485 486 // Bucket operations 487 size_type 488 bucket_count() const noexcept 489 { return _M_bucket_count; } 490 491 size_type 492 max_bucket_count() const noexcept 493 { return max_size(); } 494 495 size_type 496 bucket_size(size_type __n) const 497 { return std::distance(begin(__n), end(__n)); } 498 499 size_type 500 bucket(const key_type& __k) const 501 { return _M_bucket_index(__k, this->_M_hash_code(__k)); } 502 503 local_iterator 504 begin(size_type __n) 505 { 506 return local_iterator(*this, _M_bucket_begin(__n), 507 __n, _M_bucket_count); 508 } 509 510 local_iterator 511 end(size_type __n) 512 { return local_iterator(*this, nullptr, __n, _M_bucket_count); } 513 514 const_local_iterator 515 begin(size_type __n) const 516 { 517 return const_local_iterator(*this, _M_bucket_begin(__n), 518 __n, _M_bucket_count); 519 } 520 521 const_local_iterator 522 end(size_type __n) const 523 { return const_local_iterator(*this, nullptr, __n, _M_bucket_count); } 524 525 // DR 691. 526 const_local_iterator 527 cbegin(size_type __n) const 528 { 529 return const_local_iterator(*this, _M_bucket_begin(__n), 530 __n, _M_bucket_count); 531 } 532 533 const_local_iterator 534 cend(size_type __n) const 535 { return const_local_iterator(*this, nullptr, __n, _M_bucket_count); } 536 537 float 538 load_factor() const noexcept 539 { 540 return static_cast<float>(size()) / static_cast<float>(bucket_count()); 541 } 542 543 // max_load_factor, if present, comes from _Rehash_base. 544 545 // Generalization of max_load_factor. Extension, not found in 546 // TR1. Only useful if _RehashPolicy is something other than 547 // the default. 548 const _RehashPolicy& 549 __rehash_policy() const 550 { return _M_rehash_policy; } 551 552 void 553 __rehash_policy(const _RehashPolicy&); 554 555 // Lookup. 556 iterator 557 find(const key_type& __k); 558 559 const_iterator 560 find(const key_type& __k) const; 561 562 size_type 563 count(const key_type& __k) const; 564 565 std::pair<iterator, iterator> 566 equal_range(const key_type& __k); 567 568 std::pair<const_iterator, const_iterator> 569 equal_range(const key_type& __k) const; 570 571 protected: 572 // Bucket index computation helpers. 573 size_type 574 _M_bucket_index(__node_type* __n) const noexcept 575 { return __hash_code_base::_M_bucket_index(__n, _M_bucket_count); } 576 577 size_type 578 _M_bucket_index(const key_type& __k, __hash_code __c) const 579 { return __hash_code_base::_M_bucket_index(__k, __c, _M_bucket_count); } 580 581 // Find and insert helper functions and types 582 // Find the node before the one matching the criteria. 583 __node_base* 584 _M_find_before_node(size_type, const key_type&, __hash_code) const; 585 586 __node_type* 587 _M_find_node(size_type __bkt, const key_type& __key, 588 __hash_code __c) const 589 { 590 __node_base* __before_n = _M_find_before_node(__bkt, __key, __c); 591 if (__before_n) 592 return static_cast<__node_type*>(__before_n->_M_nxt); 593 return nullptr; 594 } 595 596 // Insert a node at the beginning of a bucket. 597 void 598 _M_insert_bucket_begin(size_type, __node_type*); 599 600 // Remove the bucket first node 601 void 602 _M_remove_bucket_begin(size_type __bkt, __node_type* __next_n, 603 size_type __next_bkt); 604 605 // Get the node before __n in the bucket __bkt 606 __node_base* 607 _M_get_previous_node(size_type __bkt, __node_base* __n); 608 609 // Insert node with hash code __code, in bucket bkt if no rehash (assumes 610 // no element with its key already present). Take ownership of the node, 611 // deallocate it on exception. 612 iterator 613 _M_insert_unique_node(size_type __bkt, __hash_code __code, 614 __node_type* __n); 615 616 // Insert node with hash code __code. Take ownership of the node, 617 // deallocate it on exception. 618 iterator 619 _M_insert_multi_node(__node_type* __hint, 620 __hash_code __code, __node_type* __n); 621 622 template<typename... _Args> 623 std::pair<iterator, bool> 624 _M_emplace(std::true_type, _Args&&... __args); 625 626 template<typename... _Args> 627 iterator 628 _M_emplace(std::false_type __uk, _Args&&... __args) 629 { return _M_emplace(cend(), __uk, std::forward<_Args>(__args)...); } 630 631 // Emplace with hint, useless when keys are unique. 632 template<typename... _Args> 633 iterator 634 _M_emplace(const_iterator, std::true_type __uk, _Args&&... __args) 635 { return _M_emplace(__uk, std::forward<_Args>(__args)...).first; } 636 637 template<typename... _Args> 638 iterator 639 _M_emplace(const_iterator, std::false_type, _Args&&... __args); 640 641 template<typename _Arg, typename _NodeGenerator> 642 std::pair<iterator, bool> 643 _M_insert(_Arg&&, const _NodeGenerator&, std::true_type); 644 645 template<typename _Arg, typename _NodeGenerator> 646 iterator 647 _M_insert(_Arg&& __arg, const _NodeGenerator& __node_gen, 648 std::false_type __uk) 649 { 650 return _M_insert(cend(), std::forward<_Arg>(__arg), __node_gen, 651 __uk); 652 } 653 654 // Insert with hint, not used when keys are unique. 655 template<typename _Arg, typename _NodeGenerator> 656 iterator 657 _M_insert(const_iterator, _Arg&& __arg, const _NodeGenerator& __node_gen, 658 std::true_type __uk) 659 { 660 return 661 _M_insert(std::forward<_Arg>(__arg), __node_gen, __uk).first; 662 } 663 664 // Insert with hint when keys are not unique. 665 template<typename _Arg, typename _NodeGenerator> 666 iterator 667 _M_insert(const_iterator, _Arg&&, const _NodeGenerator&, std::false_type); 668 669 size_type 670 _M_erase(std::true_type, const key_type&); 671 672 size_type 673 _M_erase(std::false_type, const key_type&); 674 675 iterator 676 _M_erase(size_type __bkt, __node_base* __prev_n, __node_type* __n); 677 678 public: 679 // Emplace 680 template<typename... _Args> 681 __ireturn_type 682 emplace(_Args&&... __args) 683 { return _M_emplace(__unique_keys(), std::forward<_Args>(__args)...); } 684 685 template<typename... _Args> 686 iterator 687 emplace_hint(const_iterator __hint, _Args&&... __args) 688 { 689 return _M_emplace(__hint, __unique_keys(), 690 std::forward<_Args>(__args)...); 691 } 692 693 // Insert member functions via inheritance. 694 695 // Erase 696 iterator 697 erase(const_iterator); 698 699 // LWG 2059. 700 iterator 701 erase(iterator __it) 702 { return erase(const_iterator(__it)); } 703 704 size_type 705 erase(const key_type& __k) 706 { 707 if (__builtin_expect(_M_bucket_count == 0, false)) 708 return 0; 709 return _M_erase(__unique_keys(), __k); 710 } 711 712 iterator 713 erase(const_iterator, const_iterator); 714 715 void 716 clear() noexcept; 717 718 // Set number of buckets to be appropriate for container of n element. 719 void rehash(size_type __n); 720 721 // DR 1189. 722 // reserve, if present, comes from _Rehash_base. 723 724 private: 725 // Helper rehash method used when keys are unique. 726 void _M_rehash_aux(size_type __n, std::true_type); 727 728 // Helper rehash method used when keys can be non-unique. 729 void _M_rehash_aux(size_type __n, std::false_type); 730 731 // Unconditionally change size of bucket array to n, restore 732 // hash policy state to __state on exception. 733 void _M_rehash(size_type __n, const __rehash_state& __state); 734 }; 735 736 737 // Definitions of class template _Hashtable's out-of-line member functions. 738 template<typename _Key, typename _Value, 739 typename _Alloc, typename _ExtractKey, typename _Equal, 740 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 741 typename _Traits> 742 typename _Hashtable<_Key, _Value, _Alloc, _ExtractKey, 743 _Equal, _H1, _H2, _Hash, _RehashPolicy, 744 _Traits>::__node_type* 745 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, 746 _H1, _H2, _Hash, _RehashPolicy, _Traits>:: 747 _M_bucket_begin(size_type __bkt) const 748 { 749 __node_base* __n = _M_buckets[__bkt]; 750 return __n ? static_cast<__node_type*>(__n->_M_nxt) : nullptr; 751 } 752 753 template<typename _Key, typename _Value, 754 typename _Alloc, typename _ExtractKey, typename _Equal, 755 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 756 typename _Traits> 757 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, 758 _H1, _H2, _Hash, _RehashPolicy, _Traits>:: 759 _Hashtable(size_type __bucket_hint, 760 const _H1& __h1, const _H2& __h2, const _Hash& __h, 761 const _Equal& __eq, const _ExtractKey& __exk, 762 const allocator_type& __a) 763 : __hashtable_base(__exk, __h1, __h2, __h, __eq), 764 __map_base(), 765 __rehash_base(), 766 __hashtable_alloc(__node_alloc_type(__a)), 767 _M_element_count(0), 768 _M_rehash_policy() 769 { 770 _M_bucket_count = _M_rehash_policy._M_next_bkt(__bucket_hint); 771 _M_buckets = this->_M_allocate_buckets(_M_bucket_count); 772 } 773 774 template<typename _Key, typename _Value, 775 typename _Alloc, typename _ExtractKey, typename _Equal, 776 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 777 typename _Traits> 778 template<typename _InputIterator> 779 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, 780 _H1, _H2, _Hash, _RehashPolicy, _Traits>:: 781 _Hashtable(_InputIterator __f, _InputIterator __l, 782 size_type __bucket_hint, 783 const _H1& __h1, const _H2& __h2, const _Hash& __h, 784 const _Equal& __eq, const _ExtractKey& __exk, 785 const allocator_type& __a) 786 : __hashtable_base(__exk, __h1, __h2, __h, __eq), 787 __map_base(), 788 __rehash_base(), 789 __hashtable_alloc(__node_alloc_type(__a)), 790 _M_element_count(0), 791 _M_rehash_policy() 792 { 793 auto __nb_elems = __detail::__distance_fw(__f, __l); 794 _M_bucket_count = 795 _M_rehash_policy._M_next_bkt( 796 std::max(_M_rehash_policy._M_bkt_for_elements(__nb_elems), 797 __bucket_hint)); 798 799 _M_buckets = this->_M_allocate_buckets(_M_bucket_count); 800 __try 801 { 802 for (; __f != __l; ++__f) 803 this->insert(*__f); 804 } 805 __catch(...) 806 { 807 clear(); 808 _M_deallocate_buckets(); 809 __throw_exception_again; 810 } 811 } 812 813 template<typename _Key, typename _Value, 814 typename _Alloc, typename _ExtractKey, typename _Equal, 815 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 816 typename _Traits> 817 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, 818 _H1, _H2, _Hash, _RehashPolicy, _Traits>& 819 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, 820 _H1, _H2, _Hash, _RehashPolicy, _Traits>::operator=( 821 const _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, 822 _H1, _H2, _Hash, _RehashPolicy, _Traits>& __ht) 823 { 824 if (&__ht == this) 825 return *this; 826 827 if (__node_alloc_traits::_S_propagate_on_copy_assign()) 828 { 829 auto& __this_alloc = this->_M_node_allocator(); 830 auto& __that_alloc = __ht._M_node_allocator(); 831 if (!__node_alloc_traits::_S_always_equal() 832 && __this_alloc != __that_alloc) 833 { 834 // Replacement allocator cannot free existing storage. 835 this->_M_deallocate_nodes(_M_begin()); 836 if (__builtin_expect(_M_bucket_count != 0, true)) 837 _M_deallocate_buckets(); 838 _M_reset(); 839 std::__alloc_on_copy(__this_alloc, __that_alloc); 840 __hashtable_base::operator=(__ht); 841 _M_bucket_count = __ht._M_bucket_count; 842 _M_element_count = __ht._M_element_count; 843 _M_rehash_policy = __ht._M_rehash_policy; 844 __try 845 { 846 _M_assign(__ht, 847 [this](const __node_type* __n) 848 { return this->_M_allocate_node(__n->_M_v()); }); 849 } 850 __catch(...) 851 { 852 // _M_assign took care of deallocating all memory. Now we 853 // must make sure this instance remains in a usable state. 854 _M_reset(); 855 __throw_exception_again; 856 } 857 return *this; 858 } 859 std::__alloc_on_copy(__this_alloc, __that_alloc); 860 } 861 862 // Reuse allocated buckets and nodes. 863 __bucket_type* __former_buckets = nullptr; 864 std::size_t __former_bucket_count = _M_bucket_count; 865 const __rehash_state& __former_state = _M_rehash_policy._M_state(); 866 867 if (_M_bucket_count != __ht._M_bucket_count) 868 { 869 __former_buckets = _M_buckets; 870 _M_buckets = this->_M_allocate_buckets(__ht._M_bucket_count); 871 _M_bucket_count = __ht._M_bucket_count; 872 } 873 else 874 __builtin_memset(_M_buckets, 0, 875 _M_bucket_count * sizeof(__bucket_type)); 876 877 __try 878 { 879 __hashtable_base::operator=(__ht); 880 _M_element_count = __ht._M_element_count; 881 _M_rehash_policy = __ht._M_rehash_policy; 882 __reuse_or_alloc_node_type __roan(_M_begin(), *this); 883 _M_before_begin._M_nxt = nullptr; 884 _M_assign(__ht, 885 [&__roan](const __node_type* __n) 886 { return __roan(__n->_M_v()); }); 887 if (__former_buckets) 888 this->_M_deallocate_buckets(__former_buckets, 889 __former_bucket_count); 890 } 891 __catch(...) 892 { 893 if (__former_buckets) 894 { 895 // Restore previous buckets. 896 _M_deallocate_buckets(); 897 _M_rehash_policy._M_reset(__former_state); 898 _M_buckets = __former_buckets; 899 _M_bucket_count = __former_bucket_count; 900 } 901 __builtin_memset(_M_buckets, 0, 902 _M_bucket_count * sizeof(__bucket_type)); 903 __throw_exception_again; 904 } 905 return *this; 906 } 907 908 template<typename _Key, typename _Value, 909 typename _Alloc, typename _ExtractKey, typename _Equal, 910 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 911 typename _Traits> 912 template<typename _NodeGenerator> 913 void 914 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, 915 _H1, _H2, _Hash, _RehashPolicy, _Traits>:: 916 _M_assign(const _Hashtable& __ht, const _NodeGenerator& __node_gen) 917 { 918 __bucket_type* __buckets = nullptr; 919 if (!_M_buckets) 920 _M_buckets = __buckets = this->_M_allocate_buckets(_M_bucket_count); 921 922 __try 923 { 924 if (!__ht._M_before_begin._M_nxt) 925 return; 926 927 // First deal with the special first node pointed to by 928 // _M_before_begin. 929 __node_type* __ht_n = __ht._M_begin(); 930 __node_type* __this_n = __node_gen(__ht_n); 931 this->_M_copy_code(__this_n, __ht_n); 932 _M_before_begin._M_nxt = __this_n; 933 _M_buckets[_M_bucket_index(__this_n)] = &_M_before_begin; 934 935 // Then deal with other nodes. 936 __node_base* __prev_n = __this_n; 937 for (__ht_n = __ht_n->_M_next(); __ht_n; __ht_n = __ht_n->_M_next()) 938 { 939 __this_n = __node_gen(__ht_n); 940 __prev_n->_M_nxt = __this_n; 941 this->_M_copy_code(__this_n, __ht_n); 942 size_type __bkt = _M_bucket_index(__this_n); 943 if (!_M_buckets[__bkt]) 944 _M_buckets[__bkt] = __prev_n; 945 __prev_n = __this_n; 946 } 947 } 948 __catch(...) 949 { 950 clear(); 951 if (__buckets) 952 _M_deallocate_buckets(); 953 __throw_exception_again; 954 } 955 } 956 957 template<typename _Key, typename _Value, 958 typename _Alloc, typename _ExtractKey, typename _Equal, 959 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 960 typename _Traits> 961 void 962 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, 963 _H1, _H2, _Hash, _RehashPolicy, _Traits>:: 964 _M_reset() noexcept 965 { 966 _M_rehash_policy._M_reset(); 967 _M_bucket_count = 0; 968 _M_buckets = nullptr; 969 _M_before_begin._M_nxt = nullptr; 970 _M_element_count = 0; 971 } 972 973 template<typename _Key, typename _Value, 974 typename _Alloc, typename _ExtractKey, typename _Equal, 975 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 976 typename _Traits> 977 void 978 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, 979 _H1, _H2, _Hash, _RehashPolicy, _Traits>:: 980 _M_move_assign(_Hashtable&& __ht, std::true_type) 981 { 982 this->_M_deallocate_nodes(_M_begin()); 983 if (__builtin_expect(_M_bucket_count != 0, true)) 984 _M_deallocate_buckets(); 985 986 __hashtable_base::operator=(std::move(__ht)); 987 _M_rehash_policy = __ht._M_rehash_policy; 988 _M_buckets = __ht._M_buckets; 989 _M_bucket_count = __ht._M_bucket_count; 990 _M_before_begin._M_nxt = __ht._M_before_begin._M_nxt; 991 _M_element_count = __ht._M_element_count; 992 std::__alloc_on_move(this->_M_node_allocator(), __ht._M_node_allocator()); 993 994 // Fix buckets containing the _M_before_begin pointers that can't be 995 // moved. 996 if (_M_begin()) 997 _M_buckets[_M_bucket_index(_M_begin())] = &_M_before_begin; 998 __ht._M_reset(); 999 } 1000 1001 template<typename _Key, typename _Value, 1002 typename _Alloc, typename _ExtractKey, typename _Equal, 1003 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 1004 typename _Traits> 1005 void 1006 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, 1007 _H1, _H2, _Hash, _RehashPolicy, _Traits>:: 1008 _M_move_assign(_Hashtable&& __ht, std::false_type) 1009 { 1010 if (__ht._M_node_allocator() == this->_M_node_allocator()) 1011 _M_move_assign(std::move(__ht), std::true_type()); 1012 else 1013 { 1014 // Can't move memory, move elements then. 1015 __bucket_type* __former_buckets = nullptr; 1016 size_type __former_bucket_count = _M_bucket_count; 1017 const __rehash_state& __former_state = _M_rehash_policy._M_state(); 1018 1019 if (_M_bucket_count != __ht._M_bucket_count) 1020 { 1021 __former_buckets = _M_buckets; 1022 _M_buckets = this->_M_allocate_buckets(__ht._M_bucket_count); 1023 _M_bucket_count = __ht._M_bucket_count; 1024 } 1025 else 1026 __builtin_memset(_M_buckets, 0, 1027 _M_bucket_count * sizeof(__bucket_type)); 1028 1029 __try 1030 { 1031 __hashtable_base::operator=(std::move(__ht)); 1032 _M_element_count = __ht._M_element_count; 1033 _M_rehash_policy = __ht._M_rehash_policy; 1034 __reuse_or_alloc_node_type __roan(_M_begin(), *this); 1035 _M_before_begin._M_nxt = nullptr; 1036 _M_assign(__ht, 1037 [&__roan](__node_type* __n) 1038 { return __roan(std::move_if_noexcept(__n->_M_v())); }); 1039 __ht.clear(); 1040 } 1041 __catch(...) 1042 { 1043 if (__former_buckets) 1044 { 1045 _M_deallocate_buckets(); 1046 _M_rehash_policy._M_reset(__former_state); 1047 _M_buckets = __former_buckets; 1048 _M_bucket_count = __former_bucket_count; 1049 } 1050 __builtin_memset(_M_buckets, 0, 1051 _M_bucket_count * sizeof(__bucket_type)); 1052 __throw_exception_again; 1053 } 1054 } 1055 } 1056 1057 template<typename _Key, typename _Value, 1058 typename _Alloc, typename _ExtractKey, typename _Equal, 1059 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 1060 typename _Traits> 1061 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, 1062 _H1, _H2, _Hash, _RehashPolicy, _Traits>:: 1063 _Hashtable(const _Hashtable& __ht) 1064 : __hashtable_base(__ht), 1065 __map_base(__ht), 1066 __rehash_base(__ht), 1067 __hashtable_alloc( 1068 __node_alloc_traits::_S_select_on_copy(__ht._M_node_allocator())), 1069 _M_buckets(), 1070 _M_bucket_count(__ht._M_bucket_count), 1071 _M_element_count(__ht._M_element_count), 1072 _M_rehash_policy(__ht._M_rehash_policy) 1073 { 1074 _M_assign(__ht, 1075 [this](const __node_type* __n) 1076 { return this->_M_allocate_node(__n->_M_v()); }); 1077 } 1078 1079 template<typename _Key, typename _Value, 1080 typename _Alloc, typename _ExtractKey, typename _Equal, 1081 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 1082 typename _Traits> 1083 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, 1084 _H1, _H2, _Hash, _RehashPolicy, _Traits>:: 1085 _Hashtable(_Hashtable&& __ht) noexcept 1086 : __hashtable_base(__ht), 1087 __map_base(__ht), 1088 __rehash_base(__ht), 1089 __hashtable_alloc(std::move(__ht._M_base_alloc())), 1090 _M_buckets(__ht._M_buckets), 1091 _M_bucket_count(__ht._M_bucket_count), 1092 _M_before_begin(__ht._M_before_begin._M_nxt), 1093 _M_element_count(__ht._M_element_count), 1094 _M_rehash_policy(__ht._M_rehash_policy) 1095 { 1096 // Update, if necessary, bucket pointing to before begin that hasn't 1097 // moved. 1098 if (_M_begin()) 1099 _M_buckets[_M_bucket_index(_M_begin())] = &_M_before_begin; 1100 __ht._M_reset(); 1101 } 1102 1103 template<typename _Key, typename _Value, 1104 typename _Alloc, typename _ExtractKey, typename _Equal, 1105 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 1106 typename _Traits> 1107 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, 1108 _H1, _H2, _Hash, _RehashPolicy, _Traits>:: 1109 _Hashtable(const _Hashtable& __ht, const allocator_type& __a) 1110 : __hashtable_base(__ht), 1111 __map_base(__ht), 1112 __rehash_base(__ht), 1113 __hashtable_alloc(__node_alloc_type(__a)), 1114 _M_buckets(), 1115 _M_bucket_count(__ht._M_bucket_count), 1116 _M_element_count(__ht._M_element_count), 1117 _M_rehash_policy(__ht._M_rehash_policy) 1118 { 1119 _M_assign(__ht, 1120 [this](const __node_type* __n) 1121 { return this->_M_allocate_node(__n->_M_v()); }); 1122 } 1123 1124 template<typename _Key, typename _Value, 1125 typename _Alloc, typename _ExtractKey, typename _Equal, 1126 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 1127 typename _Traits> 1128 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, 1129 _H1, _H2, _Hash, _RehashPolicy, _Traits>:: 1130 _Hashtable(_Hashtable&& __ht, const allocator_type& __a) 1131 : __hashtable_base(__ht), 1132 __map_base(__ht), 1133 __rehash_base(__ht), 1134 __hashtable_alloc(__node_alloc_type(__a)), 1135 _M_buckets(), 1136 _M_bucket_count(__ht._M_bucket_count), 1137 _M_element_count(__ht._M_element_count), 1138 _M_rehash_policy(__ht._M_rehash_policy) 1139 { 1140 if (__ht._M_node_allocator() == this->_M_node_allocator()) 1141 { 1142 _M_buckets = __ht._M_buckets; 1143 _M_before_begin._M_nxt = __ht._M_before_begin._M_nxt; 1144 // Update, if necessary, bucket pointing to before begin that hasn't 1145 // moved. 1146 if (_M_begin()) 1147 _M_buckets[_M_bucket_index(_M_begin())] = &_M_before_begin; 1148 __ht._M_reset(); 1149 } 1150 else 1151 { 1152 _M_assign(__ht, 1153 [this](__node_type* __n) 1154 { 1155 return this->_M_allocate_node( 1156 std::move_if_noexcept(__n->_M_v())); 1157 }); 1158 __ht.clear(); 1159 } 1160 } 1161 1162 template<typename _Key, typename _Value, 1163 typename _Alloc, typename _ExtractKey, typename _Equal, 1164 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 1165 typename _Traits> 1166 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, 1167 _H1, _H2, _Hash, _RehashPolicy, _Traits>:: 1168 ~_Hashtable() noexcept 1169 { 1170 clear(); 1171 if (_M_buckets) 1172 _M_deallocate_buckets(); 1173 } 1174 1175 template<typename _Key, typename _Value, 1176 typename _Alloc, typename _ExtractKey, typename _Equal, 1177 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 1178 typename _Traits> 1179 void 1180 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, 1181 _H1, _H2, _Hash, _RehashPolicy, _Traits>:: 1182 swap(_Hashtable& __x) 1183 noexcept(__node_alloc_traits::_S_nothrow_swap()) 1184 { 1185 // The only base class with member variables is hash_code_base. 1186 // We define _Hash_code_base::_M_swap because different 1187 // specializations have different members. 1188 this->_M_swap(__x); 1189 1190 std::__alloc_on_swap(this->_M_node_allocator(), __x._M_node_allocator()); 1191 std::swap(_M_rehash_policy, __x._M_rehash_policy); 1192 std::swap(_M_buckets, __x._M_buckets); 1193 std::swap(_M_bucket_count, __x._M_bucket_count); 1194 std::swap(_M_before_begin._M_nxt, __x._M_before_begin._M_nxt); 1195 std::swap(_M_element_count, __x._M_element_count); 1196 1197 // Fix buckets containing the _M_before_begin pointers that can't be 1198 // swapped. 1199 if (_M_begin()) 1200 _M_buckets[_M_bucket_index(_M_begin())] = &_M_before_begin; 1201 if (__x._M_begin()) 1202 __x._M_buckets[__x._M_bucket_index(__x._M_begin())] 1203 = &__x._M_before_begin; 1204 } 1205 1206 template<typename _Key, typename _Value, 1207 typename _Alloc, typename _ExtractKey, typename _Equal, 1208 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 1209 typename _Traits> 1210 void 1211 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, 1212 _H1, _H2, _Hash, _RehashPolicy, _Traits>:: 1213 __rehash_policy(const _RehashPolicy& __pol) 1214 { 1215 size_type __n_bkt = __pol._M_bkt_for_elements(_M_element_count); 1216 __n_bkt = __pol._M_next_bkt(__n_bkt); 1217 if (__n_bkt != _M_bucket_count) 1218 _M_rehash(__n_bkt, _M_rehash_policy._M_state()); 1219 _M_rehash_policy = __pol; 1220 } 1221 1222 template<typename _Key, typename _Value, 1223 typename _Alloc, typename _ExtractKey, typename _Equal, 1224 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 1225 typename _Traits> 1226 typename _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, 1227 _H1, _H2, _Hash, _RehashPolicy, 1228 _Traits>::iterator 1229 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, 1230 _H1, _H2, _Hash, _RehashPolicy, _Traits>:: 1231 find(const key_type& __k) 1232 { 1233 if (__builtin_expect(_M_bucket_count == 0, false)) 1234 return end(); 1235 1236 __hash_code __code = this->_M_hash_code(__k); 1237 std::size_t __n = _M_bucket_index(__k, __code); 1238 __node_type* __p = _M_find_node(__n, __k, __code); 1239 return __p ? iterator(__p) : end(); 1240 } 1241 1242 template<typename _Key, typename _Value, 1243 typename _Alloc, typename _ExtractKey, typename _Equal, 1244 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 1245 typename _Traits> 1246 typename _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, 1247 _H1, _H2, _Hash, _RehashPolicy, 1248 _Traits>::const_iterator 1249 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, 1250 _H1, _H2, _Hash, _RehashPolicy, _Traits>:: 1251 find(const key_type& __k) const 1252 { 1253 if (__builtin_expect(_M_bucket_count == 0, false)) 1254 return end(); 1255 1256 __hash_code __code = this->_M_hash_code(__k); 1257 std::size_t __n = _M_bucket_index(__k, __code); 1258 __node_type* __p = _M_find_node(__n, __k, __code); 1259 return __p ? const_iterator(__p) : end(); 1260 } 1261 1262 template<typename _Key, typename _Value, 1263 typename _Alloc, typename _ExtractKey, typename _Equal, 1264 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 1265 typename _Traits> 1266 typename _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, 1267 _H1, _H2, _Hash, _RehashPolicy, 1268 _Traits>::size_type 1269 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, 1270 _H1, _H2, _Hash, _RehashPolicy, _Traits>:: 1271 count(const key_type& __k) const 1272 { 1273 if (__builtin_expect(_M_bucket_count == 0, false)) 1274 return 0; 1275 1276 __hash_code __code = this->_M_hash_code(__k); 1277 std::size_t __n = _M_bucket_index(__k, __code); 1278 __node_type* __p = _M_bucket_begin(__n); 1279 if (!__p) 1280 return 0; 1281 1282 std::size_t __result = 0; 1283 for (;; __p = __p->_M_next()) 1284 { 1285 if (this->_M_equals(__k, __code, __p)) 1286 ++__result; 1287 else if (__result) 1288 // All equivalent values are next to each other, if we 1289 // found a non-equivalent value after an equivalent one it 1290 // means that we won't find any more equivalent values. 1291 break; 1292 if (!__p->_M_nxt || _M_bucket_index(__p->_M_next()) != __n) 1293 break; 1294 } 1295 return __result; 1296 } 1297 1298 template<typename _Key, typename _Value, 1299 typename _Alloc, typename _ExtractKey, typename _Equal, 1300 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 1301 typename _Traits> 1302 std::pair<typename _Hashtable<_Key, _Value, _Alloc, 1303 _ExtractKey, _Equal, _H1, 1304 _H2, _Hash, _RehashPolicy, 1305 _Traits>::iterator, 1306 typename _Hashtable<_Key, _Value, _Alloc, 1307 _ExtractKey, _Equal, _H1, 1308 _H2, _Hash, _RehashPolicy, 1309 _Traits>::iterator> 1310 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, 1311 _H1, _H2, _Hash, _RehashPolicy, _Traits>:: 1312 equal_range(const key_type& __k) 1313 { 1314 if (__builtin_expect(_M_bucket_count == 0, false)) 1315 return std::make_pair(end(), end()); 1316 1317 __hash_code __code = this->_M_hash_code(__k); 1318 std::size_t __n = _M_bucket_index(__k, __code); 1319 __node_type* __p = _M_find_node(__n, __k, __code); 1320 1321 if (__p) 1322 { 1323 __node_type* __p1 = __p->_M_next(); 1324 while (__p1 && _M_bucket_index(__p1) == __n 1325 && this->_M_equals(__k, __code, __p1)) 1326 __p1 = __p1->_M_next(); 1327 1328 return std::make_pair(iterator(__p), iterator(__p1)); 1329 } 1330 else 1331 return std::make_pair(end(), end()); 1332 } 1333 1334 template<typename _Key, typename _Value, 1335 typename _Alloc, typename _ExtractKey, typename _Equal, 1336 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 1337 typename _Traits> 1338 std::pair<typename _Hashtable<_Key, _Value, _Alloc, 1339 _ExtractKey, _Equal, _H1, 1340 _H2, _Hash, _RehashPolicy, 1341 _Traits>::const_iterator, 1342 typename _Hashtable<_Key, _Value, _Alloc, 1343 _ExtractKey, _Equal, _H1, 1344 _H2, _Hash, _RehashPolicy, 1345 _Traits>::const_iterator> 1346 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, 1347 _H1, _H2, _Hash, _RehashPolicy, _Traits>:: 1348 equal_range(const key_type& __k) const 1349 { 1350 if (__builtin_expect(_M_bucket_count == 0, false)) 1351 return std::make_pair(end(), end()); 1352 1353 __hash_code __code = this->_M_hash_code(__k); 1354 std::size_t __n = _M_bucket_index(__k, __code); 1355 __node_type* __p = _M_find_node(__n, __k, __code); 1356 1357 if (__p) 1358 { 1359 __node_type* __p1 = __p->_M_next(); 1360 while (__p1 && _M_bucket_index(__p1) == __n 1361 && this->_M_equals(__k, __code, __p1)) 1362 __p1 = __p1->_M_next(); 1363 1364 return std::make_pair(const_iterator(__p), const_iterator(__p1)); 1365 } 1366 else 1367 return std::make_pair(end(), end()); 1368 } 1369 1370 // Find the node whose key compares equal to k in the bucket n. 1371 // Return nullptr if no node is found. 1372 template<typename _Key, typename _Value, 1373 typename _Alloc, typename _ExtractKey, typename _Equal, 1374 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 1375 typename _Traits> 1376 typename _Hashtable<_Key, _Value, _Alloc, _ExtractKey, 1377 _Equal, _H1, _H2, _Hash, _RehashPolicy, 1378 _Traits>::__node_base* 1379 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, 1380 _H1, _H2, _Hash, _RehashPolicy, _Traits>:: 1381 _M_find_before_node(size_type __n, const key_type& __k, 1382 __hash_code __code) const 1383 { 1384 __node_base* __prev_p = _M_buckets[__n]; 1385 if (!__prev_p) 1386 return nullptr; 1387 1388 for (__node_type* __p = static_cast<__node_type*>(__prev_p->_M_nxt);; 1389 __p = __p->_M_next()) 1390 { 1391 if (this->_M_equals(__k, __code, __p)) 1392 return __prev_p; 1393 1394 if (!__p->_M_nxt || _M_bucket_index(__p->_M_next()) != __n) 1395 break; 1396 __prev_p = __p; 1397 } 1398 return nullptr; 1399 } 1400 1401 template<typename _Key, typename _Value, 1402 typename _Alloc, typename _ExtractKey, typename _Equal, 1403 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 1404 typename _Traits> 1405 void 1406 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, 1407 _H1, _H2, _Hash, _RehashPolicy, _Traits>:: 1408 _M_insert_bucket_begin(size_type __bkt, __node_type* __node) 1409 { 1410 if (_M_buckets[__bkt]) 1411 { 1412 // Bucket is not empty, we just need to insert the new node 1413 // after the bucket before begin. 1414 __node->_M_nxt = _M_buckets[__bkt]->_M_nxt; 1415 _M_buckets[__bkt]->_M_nxt = __node; 1416 } 1417 else 1418 { 1419 // The bucket is empty, the new node is inserted at the 1420 // beginning of the singly-linked list and the bucket will 1421 // contain _M_before_begin pointer. 1422 __node->_M_nxt = _M_before_begin._M_nxt; 1423 _M_before_begin._M_nxt = __node; 1424 if (__node->_M_nxt) 1425 // We must update former begin bucket that is pointing to 1426 // _M_before_begin. 1427 _M_buckets[_M_bucket_index(__node->_M_next())] = __node; 1428 _M_buckets[__bkt] = &_M_before_begin; 1429 } 1430 } 1431 1432 template<typename _Key, typename _Value, 1433 typename _Alloc, typename _ExtractKey, typename _Equal, 1434 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 1435 typename _Traits> 1436 void 1437 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, 1438 _H1, _H2, _Hash, _RehashPolicy, _Traits>:: 1439 _M_remove_bucket_begin(size_type __bkt, __node_type* __next, 1440 size_type __next_bkt) 1441 { 1442 if (!__next || __next_bkt != __bkt) 1443 { 1444 // Bucket is now empty 1445 // First update next bucket if any 1446 if (__next) 1447 _M_buckets[__next_bkt] = _M_buckets[__bkt]; 1448 1449 // Second update before begin node if necessary 1450 if (&_M_before_begin == _M_buckets[__bkt]) 1451 _M_before_begin._M_nxt = __next; 1452 _M_buckets[__bkt] = nullptr; 1453 } 1454 } 1455 1456 template<typename _Key, typename _Value, 1457 typename _Alloc, typename _ExtractKey, typename _Equal, 1458 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 1459 typename _Traits> 1460 typename _Hashtable<_Key, _Value, _Alloc, _ExtractKey, 1461 _Equal, _H1, _H2, _Hash, _RehashPolicy, 1462 _Traits>::__node_base* 1463 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, 1464 _H1, _H2, _Hash, _RehashPolicy, _Traits>:: 1465 _M_get_previous_node(size_type __bkt, __node_base* __n) 1466 { 1467 __node_base* __prev_n = _M_buckets[__bkt]; 1468 while (__prev_n->_M_nxt != __n) 1469 __prev_n = __prev_n->_M_nxt; 1470 return __prev_n; 1471 } 1472 1473 template<typename _Key, typename _Value, 1474 typename _Alloc, typename _ExtractKey, typename _Equal, 1475 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 1476 typename _Traits> 1477 template<typename... _Args> 1478 std::pair<typename _Hashtable<_Key, _Value, _Alloc, 1479 _ExtractKey, _Equal, _H1, 1480 _H2, _Hash, _RehashPolicy, 1481 _Traits>::iterator, bool> 1482 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, 1483 _H1, _H2, _Hash, _RehashPolicy, _Traits>:: 1484 _M_emplace(std::true_type, _Args&&... __args) 1485 { 1486 // First build the node to get access to the hash code 1487 __node_type* __node = this->_M_allocate_node(std::forward<_Args>(__args)...); 1488 const key_type& __k = this->_M_extract()(__node->_M_v()); 1489 __hash_code __code; 1490 __try 1491 { 1492 __code = this->_M_hash_code(__k); 1493 } 1494 __catch(...) 1495 { 1496 this->_M_deallocate_node(__node); 1497 __throw_exception_again; 1498 } 1499 1500 size_type __bkt = _M_bucket_index(__k, __code); 1501 if (__node_type* __p = _M_find_node(__bkt, __k, __code)) 1502 { 1503 // There is already an equivalent node, no insertion 1504 this->_M_deallocate_node(__node); 1505 return std::make_pair(iterator(__p), false); 1506 } 1507 1508 // Insert the node 1509 return std::make_pair(_M_insert_unique_node(__bkt, __code, __node), 1510 true); 1511 } 1512 1513 template<typename _Key, typename _Value, 1514 typename _Alloc, typename _ExtractKey, typename _Equal, 1515 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 1516 typename _Traits> 1517 template<typename... _Args> 1518 typename _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, 1519 _H1, _H2, _Hash, _RehashPolicy, 1520 _Traits>::iterator 1521 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, 1522 _H1, _H2, _Hash, _RehashPolicy, _Traits>:: 1523 _M_emplace(const_iterator __hint, std::false_type, _Args&&... __args) 1524 { 1525 // First build the node to get its hash code. 1526 __node_type* __node = 1527 this->_M_allocate_node(std::forward<_Args>(__args)...); 1528 1529 __hash_code __code; 1530 __try 1531 { 1532 __code = this->_M_hash_code(this->_M_extract()(__node->_M_v())); 1533 } 1534 __catch(...) 1535 { 1536 this->_M_deallocate_node(__node); 1537 __throw_exception_again; 1538 } 1539 1540 return _M_insert_multi_node(__hint._M_cur, __code, __node); 1541 } 1542 1543 template<typename _Key, typename _Value, 1544 typename _Alloc, typename _ExtractKey, typename _Equal, 1545 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 1546 typename _Traits> 1547 typename _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, 1548 _H1, _H2, _Hash, _RehashPolicy, 1549 _Traits>::iterator 1550 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, 1551 _H1, _H2, _Hash, _RehashPolicy, _Traits>:: 1552 _M_insert_unique_node(size_type __bkt, __hash_code __code, 1553 __node_type* __node) 1554 { 1555 const __rehash_state& __saved_state = _M_rehash_policy._M_state(); 1556 std::pair<bool, std::size_t> __do_rehash 1557 = _M_rehash_policy._M_need_rehash(_M_bucket_count, _M_element_count, 1); 1558 1559 __try 1560 { 1561 if (__do_rehash.first) 1562 { 1563 _M_rehash(__do_rehash.second, __saved_state); 1564 __bkt = _M_bucket_index(this->_M_extract()(__node->_M_v()), __code); 1565 } 1566 1567 this->_M_store_code(__node, __code); 1568 1569 // Always insert at the beginning of the bucket. 1570 _M_insert_bucket_begin(__bkt, __node); 1571 ++_M_element_count; 1572 return iterator(__node); 1573 } 1574 __catch(...) 1575 { 1576 this->_M_deallocate_node(__node); 1577 __throw_exception_again; 1578 } 1579 } 1580 1581 // Insert node, in bucket bkt if no rehash (assumes no element with its key 1582 // already present). Take ownership of the node, deallocate it on exception. 1583 template<typename _Key, typename _Value, 1584 typename _Alloc, typename _ExtractKey, typename _Equal, 1585 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 1586 typename _Traits> 1587 typename _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, 1588 _H1, _H2, _Hash, _RehashPolicy, 1589 _Traits>::iterator 1590 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, 1591 _H1, _H2, _Hash, _RehashPolicy, _Traits>:: 1592 _M_insert_multi_node(__node_type* __hint, __hash_code __code, 1593 __node_type* __node) 1594 { 1595 const __rehash_state& __saved_state = _M_rehash_policy._M_state(); 1596 std::pair<bool, std::size_t> __do_rehash 1597 = _M_rehash_policy._M_need_rehash(_M_bucket_count, _M_element_count, 1); 1598 1599 __try 1600 { 1601 if (__do_rehash.first) 1602 _M_rehash(__do_rehash.second, __saved_state); 1603 1604 this->_M_store_code(__node, __code); 1605 const key_type& __k = this->_M_extract()(__node->_M_v()); 1606 size_type __bkt = _M_bucket_index(__k, __code); 1607 1608 // Find the node before an equivalent one or use hint if it exists and 1609 // if it is equivalent. 1610 __node_base* __prev 1611 = __builtin_expect(__hint != nullptr, false) 1612 && this->_M_equals(__k, __code, __hint) 1613 ? __hint 1614 : _M_find_before_node(__bkt, __k, __code); 1615 if (__prev) 1616 { 1617 // Insert after the node before the equivalent one. 1618 __node->_M_nxt = __prev->_M_nxt; 1619 __prev->_M_nxt = __node; 1620 if (__builtin_expect(__prev == __hint, false)) 1621 // hint might be the last bucket node, in this case we need to 1622 // update next bucket. 1623 if (__node->_M_nxt 1624 && !this->_M_equals(__k, __code, __node->_M_next())) 1625 { 1626 size_type __next_bkt = _M_bucket_index(__node->_M_next()); 1627 if (__next_bkt != __bkt) 1628 _M_buckets[__next_bkt] = __node; 1629 } 1630 } 1631 else 1632 // The inserted node has no equivalent in the 1633 // hashtable. We must insert the new node at the 1634 // beginning of the bucket to preserve equivalent 1635 // elements' relative positions. 1636 _M_insert_bucket_begin(__bkt, __node); 1637 ++_M_element_count; 1638 return iterator(__node); 1639 } 1640 __catch(...) 1641 { 1642 this->_M_deallocate_node(__node); 1643 __throw_exception_again; 1644 } 1645 } 1646 1647 // Insert v if no element with its key is already present. 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 _Arg, typename _NodeGenerator> 1653 std::pair<typename _Hashtable<_Key, _Value, _Alloc, 1654 _ExtractKey, _Equal, _H1, 1655 _H2, _Hash, _RehashPolicy, 1656 _Traits>::iterator, bool> 1657 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, 1658 _H1, _H2, _Hash, _RehashPolicy, _Traits>:: 1659 _M_insert(_Arg&& __v, const _NodeGenerator& __node_gen, std::true_type) 1660 { 1661 const key_type& __k = this->_M_extract()(__v); 1662 __hash_code __code = this->_M_hash_code(__k); 1663 size_type __bkt = _M_bucket_index(__k, __code); 1664 1665 __node_type* __n = _M_find_node(__bkt, __k, __code); 1666 if (__n) 1667 return std::make_pair(iterator(__n), false); 1668 1669 __n = __node_gen(std::forward<_Arg>(__v)); 1670 return std::make_pair(_M_insert_unique_node(__bkt, __code, __n), true); 1671 } 1672 1673 // Insert v unconditionally. 1674 template<typename _Key, typename _Value, 1675 typename _Alloc, typename _ExtractKey, typename _Equal, 1676 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 1677 typename _Traits> 1678 template<typename _Arg, typename _NodeGenerator> 1679 typename _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, 1680 _H1, _H2, _Hash, _RehashPolicy, 1681 _Traits>::iterator 1682 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, 1683 _H1, _H2, _Hash, _RehashPolicy, _Traits>:: 1684 _M_insert(const_iterator __hint, _Arg&& __v, 1685 const _NodeGenerator& __node_gen, 1686 std::false_type) 1687 { 1688 // First compute the hash code so that we don't do anything if it 1689 // throws. 1690 __hash_code __code = this->_M_hash_code(this->_M_extract()(__v)); 1691 1692 // Second allocate new node so that we don't rehash if it throws. 1693 __node_type* __node = __node_gen(std::forward<_Arg>(__v)); 1694 1695 return _M_insert_multi_node(__hint._M_cur, __code, __node); 1696 } 1697 1698 template<typename _Key, typename _Value, 1699 typename _Alloc, typename _ExtractKey, typename _Equal, 1700 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 1701 typename _Traits> 1702 typename _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, 1703 _H1, _H2, _Hash, _RehashPolicy, 1704 _Traits>::iterator 1705 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, 1706 _H1, _H2, _Hash, _RehashPolicy, _Traits>:: 1707 erase(const_iterator __it) 1708 { 1709 __node_type* __n = __it._M_cur; 1710 std::size_t __bkt = _M_bucket_index(__n); 1711 1712 // Look for previous node to unlink it from the erased one, this 1713 // is why we need buckets to contain the before begin to make 1714 // this search fast. 1715 __node_base* __prev_n = _M_get_previous_node(__bkt, __n); 1716 return _M_erase(__bkt, __prev_n, __n); 1717 } 1718 1719 template<typename _Key, typename _Value, 1720 typename _Alloc, typename _ExtractKey, typename _Equal, 1721 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 1722 typename _Traits> 1723 typename _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, 1724 _H1, _H2, _Hash, _RehashPolicy, 1725 _Traits>::iterator 1726 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, 1727 _H1, _H2, _Hash, _RehashPolicy, _Traits>:: 1728 _M_erase(size_type __bkt, __node_base* __prev_n, __node_type* __n) 1729 { 1730 if (__prev_n == _M_buckets[__bkt]) 1731 _M_remove_bucket_begin(__bkt, __n->_M_next(), 1732 __n->_M_nxt ? _M_bucket_index(__n->_M_next()) : 0); 1733 else if (__n->_M_nxt) 1734 { 1735 size_type __next_bkt = _M_bucket_index(__n->_M_next()); 1736 if (__next_bkt != __bkt) 1737 _M_buckets[__next_bkt] = __prev_n; 1738 } 1739 1740 __prev_n->_M_nxt = __n->_M_nxt; 1741 iterator __result(__n->_M_next()); 1742 this->_M_deallocate_node(__n); 1743 --_M_element_count; 1744 1745 return __result; 1746 } 1747 1748 template<typename _Key, typename _Value, 1749 typename _Alloc, typename _ExtractKey, typename _Equal, 1750 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 1751 typename _Traits> 1752 typename _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, 1753 _H1, _H2, _Hash, _RehashPolicy, 1754 _Traits>::size_type 1755 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, 1756 _H1, _H2, _Hash, _RehashPolicy, _Traits>:: 1757 _M_erase(std::true_type, const key_type& __k) 1758 { 1759 __hash_code __code = this->_M_hash_code(__k); 1760 std::size_t __bkt = _M_bucket_index(__k, __code); 1761 1762 // Look for the node before the first matching node. 1763 __node_base* __prev_n = _M_find_before_node(__bkt, __k, __code); 1764 if (!__prev_n) 1765 return 0; 1766 1767 // We found a matching node, erase it. 1768 __node_type* __n = static_cast<__node_type*>(__prev_n->_M_nxt); 1769 _M_erase(__bkt, __prev_n, __n); 1770 return 1; 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>::size_type 1780 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, 1781 _H1, _H2, _Hash, _RehashPolicy, _Traits>:: 1782 _M_erase(std::false_type, const key_type& __k) 1783 { 1784 __hash_code __code = this->_M_hash_code(__k); 1785 std::size_t __bkt = _M_bucket_index(__k, __code); 1786 1787 // Look for the node before the first matching node. 1788 __node_base* __prev_n = _M_find_before_node(__bkt, __k, __code); 1789 if (!__prev_n) 1790 return 0; 1791 1792 // _GLIBCXX_RESOLVE_LIB_DEFECTS 1793 // 526. Is it undefined if a function in the standard changes 1794 // in parameters? 1795 // We use one loop to find all matching nodes and another to deallocate 1796 // them so that the key stays valid during the first loop. It might be 1797 // invalidated indirectly when destroying nodes. 1798 __node_type* __n = static_cast<__node_type*>(__prev_n->_M_nxt); 1799 __node_type* __n_last = __n; 1800 std::size_t __n_last_bkt = __bkt; 1801 do 1802 { 1803 __n_last = __n_last->_M_next(); 1804 if (!__n_last) 1805 break; 1806 __n_last_bkt = _M_bucket_index(__n_last); 1807 } 1808 while (__n_last_bkt == __bkt && this->_M_equals(__k, __code, __n_last)); 1809 1810 // Deallocate nodes. 1811 size_type __result = 0; 1812 do 1813 { 1814 __node_type* __p = __n->_M_next(); 1815 this->_M_deallocate_node(__n); 1816 __n = __p; 1817 ++__result; 1818 --_M_element_count; 1819 } 1820 while (__n != __n_last); 1821 1822 if (__prev_n == _M_buckets[__bkt]) 1823 _M_remove_bucket_begin(__bkt, __n_last, __n_last_bkt); 1824 else if (__n_last && __n_last_bkt != __bkt) 1825 _M_buckets[__n_last_bkt] = __prev_n; 1826 __prev_n->_M_nxt = __n_last; 1827 return __result; 1828 } 1829 1830 template<typename _Key, typename _Value, 1831 typename _Alloc, typename _ExtractKey, typename _Equal, 1832 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 1833 typename _Traits> 1834 typename _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, 1835 _H1, _H2, _Hash, _RehashPolicy, 1836 _Traits>::iterator 1837 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, 1838 _H1, _H2, _Hash, _RehashPolicy, _Traits>:: 1839 erase(const_iterator __first, const_iterator __last) 1840 { 1841 __node_type* __n = __first._M_cur; 1842 __node_type* __last_n = __last._M_cur; 1843 if (__n == __last_n) 1844 return iterator(__n); 1845 1846 std::size_t __bkt = _M_bucket_index(__n); 1847 1848 __node_base* __prev_n = _M_get_previous_node(__bkt, __n); 1849 bool __is_bucket_begin = __n == _M_bucket_begin(__bkt); 1850 std::size_t __n_bkt = __bkt; 1851 for (;;) 1852 { 1853 do 1854 { 1855 __node_type* __tmp = __n; 1856 __n = __n->_M_next(); 1857 this->_M_deallocate_node(__tmp); 1858 --_M_element_count; 1859 if (!__n) 1860 break; 1861 __n_bkt = _M_bucket_index(__n); 1862 } 1863 while (__n != __last_n && __n_bkt == __bkt); 1864 if (__is_bucket_begin) 1865 _M_remove_bucket_begin(__bkt, __n, __n_bkt); 1866 if (__n == __last_n) 1867 break; 1868 __is_bucket_begin = true; 1869 __bkt = __n_bkt; 1870 } 1871 1872 if (__n && (__n_bkt != __bkt || __is_bucket_begin)) 1873 _M_buckets[__n_bkt] = __prev_n; 1874 __prev_n->_M_nxt = __n; 1875 return iterator(__n); 1876 } 1877 1878 template<typename _Key, typename _Value, 1879 typename _Alloc, typename _ExtractKey, typename _Equal, 1880 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 1881 typename _Traits> 1882 void 1883 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, 1884 _H1, _H2, _Hash, _RehashPolicy, _Traits>:: 1885 clear() noexcept 1886 { 1887 this->_M_deallocate_nodes(_M_begin()); 1888 __builtin_memset(_M_buckets, 0, _M_bucket_count * sizeof(__bucket_type)); 1889 _M_element_count = 0; 1890 _M_before_begin._M_nxt = nullptr; 1891 } 1892 1893 template<typename _Key, typename _Value, 1894 typename _Alloc, typename _ExtractKey, typename _Equal, 1895 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 1896 typename _Traits> 1897 void 1898 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, 1899 _H1, _H2, _Hash, _RehashPolicy, _Traits>:: 1900 rehash(size_type __n) 1901 { 1902 const __rehash_state& __saved_state = _M_rehash_policy._M_state(); 1903 std::size_t __buckets 1904 = std::max(_M_rehash_policy._M_bkt_for_elements(_M_element_count + 1), 1905 __n); 1906 __buckets = _M_rehash_policy._M_next_bkt(__buckets); 1907 1908 if (__buckets != _M_bucket_count) 1909 _M_rehash(__buckets, __saved_state); 1910 else 1911 // No rehash, restore previous state to keep a consistent state. 1912 _M_rehash_policy._M_reset(__saved_state); 1913 } 1914 1915 template<typename _Key, typename _Value, 1916 typename _Alloc, typename _ExtractKey, typename _Equal, 1917 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 1918 typename _Traits> 1919 void 1920 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, 1921 _H1, _H2, _Hash, _RehashPolicy, _Traits>:: 1922 _M_rehash(size_type __n, const __rehash_state& __state) 1923 { 1924 __try 1925 { 1926 _M_rehash_aux(__n, __unique_keys()); 1927 } 1928 __catch(...) 1929 { 1930 // A failure here means that buckets allocation failed. We only 1931 // have to restore hash policy previous state. 1932 _M_rehash_policy._M_reset(__state); 1933 __throw_exception_again; 1934 } 1935 } 1936 1937 // Rehash when there is no equivalent elements. 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 void 1943 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, 1944 _H1, _H2, _Hash, _RehashPolicy, _Traits>:: 1945 _M_rehash_aux(size_type __n, std::true_type) 1946 { 1947 __bucket_type* __new_buckets = this->_M_allocate_buckets(__n); 1948 __node_type* __p = _M_begin(); 1949 _M_before_begin._M_nxt = nullptr; 1950 std::size_t __bbegin_bkt = 0; 1951 while (__p) 1952 { 1953 __node_type* __next = __p->_M_next(); 1954 std::size_t __bkt = __hash_code_base::_M_bucket_index(__p, __n); 1955 if (!__new_buckets[__bkt]) 1956 { 1957 __p->_M_nxt = _M_before_begin._M_nxt; 1958 _M_before_begin._M_nxt = __p; 1959 __new_buckets[__bkt] = &_M_before_begin; 1960 if (__p->_M_nxt) 1961 __new_buckets[__bbegin_bkt] = __p; 1962 __bbegin_bkt = __bkt; 1963 } 1964 else 1965 { 1966 __p->_M_nxt = __new_buckets[__bkt]->_M_nxt; 1967 __new_buckets[__bkt]->_M_nxt = __p; 1968 } 1969 __p = __next; 1970 } 1971 1972 if (__builtin_expect(_M_bucket_count != 0, true)) 1973 _M_deallocate_buckets(); 1974 _M_bucket_count = __n; 1975 _M_buckets = __new_buckets; 1976 } 1977 1978 // Rehash when there can be equivalent elements, preserve their relative 1979 // order. 1980 template<typename _Key, typename _Value, 1981 typename _Alloc, typename _ExtractKey, typename _Equal, 1982 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 1983 typename _Traits> 1984 void 1985 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, 1986 _H1, _H2, _Hash, _RehashPolicy, _Traits>:: 1987 _M_rehash_aux(size_type __n, std::false_type) 1988 { 1989 __bucket_type* __new_buckets = this->_M_allocate_buckets(__n); 1990 1991 __node_type* __p = _M_begin(); 1992 _M_before_begin._M_nxt = nullptr; 1993 std::size_t __bbegin_bkt = 0; 1994 std::size_t __prev_bkt = 0; 1995 __node_type* __prev_p = nullptr; 1996 bool __check_bucket = false; 1997 1998 while (__p) 1999 { 2000 __node_type* __next = __p->_M_next(); 2001 std::size_t __bkt = __hash_code_base::_M_bucket_index(__p, __n); 2002 2003 if (__prev_p && __prev_bkt == __bkt) 2004 { 2005 // Previous insert was already in this bucket, we insert after 2006 // the previously inserted one to preserve equivalent elements 2007 // relative order. 2008 __p->_M_nxt = __prev_p->_M_nxt; 2009 __prev_p->_M_nxt = __p; 2010 2011 // Inserting after a node in a bucket require to check that we 2012 // haven't change the bucket last node, in this case next 2013 // bucket containing its before begin node must be updated. We 2014 // schedule a check as soon as we move out of the sequence of 2015 // equivalent nodes to limit the number of checks. 2016 __check_bucket = true; 2017 } 2018 else 2019 { 2020 if (__check_bucket) 2021 { 2022 // Check if we shall update the next bucket because of 2023 // insertions into __prev_bkt bucket. 2024 if (__prev_p->_M_nxt) 2025 { 2026 std::size_t __next_bkt 2027 = __hash_code_base::_M_bucket_index(__prev_p->_M_next(), 2028 __n); 2029 if (__next_bkt != __prev_bkt) 2030 __new_buckets[__next_bkt] = __prev_p; 2031 } 2032 __check_bucket = false; 2033 } 2034 2035 if (!__new_buckets[__bkt]) 2036 { 2037 __p->_M_nxt = _M_before_begin._M_nxt; 2038 _M_before_begin._M_nxt = __p; 2039 __new_buckets[__bkt] = &_M_before_begin; 2040 if (__p->_M_nxt) 2041 __new_buckets[__bbegin_bkt] = __p; 2042 __bbegin_bkt = __bkt; 2043 } 2044 else 2045 { 2046 __p->_M_nxt = __new_buckets[__bkt]->_M_nxt; 2047 __new_buckets[__bkt]->_M_nxt = __p; 2048 } 2049 } 2050 __prev_p = __p; 2051 __prev_bkt = __bkt; 2052 __p = __next; 2053 } 2054 2055 if (__check_bucket && __prev_p->_M_nxt) 2056 { 2057 std::size_t __next_bkt 2058 = __hash_code_base::_M_bucket_index(__prev_p->_M_next(), __n); 2059 if (__next_bkt != __prev_bkt) 2060 __new_buckets[__next_bkt] = __prev_p; 2061 } 2062 2063 if (__builtin_expect(_M_bucket_count != 0, true)) 2064 _M_deallocate_buckets(); 2065 _M_bucket_count = __n; 2066 _M_buckets = __new_buckets; 2067 } 2068 2069 _GLIBCXX_END_NAMESPACE_VERSION 2070 } // namespace std 2071 2072 #endif // _HASHTABLE_H 2073
