1 // hashtable.h header -*- C++ -*- 2 3 // Copyright (C) 2007, 2008, 2009, 2010, 2011, 2012, 2013 4 // Free Software Foundation, Inc. 5 // 6 // This file is part of the GNU ISO C++ Library. This library is free 7 // software; you can redistribute it and/or modify it under the 8 // terms of the GNU General Public License as published by the 9 // Free Software Foundation; either version 3, or (at your option) 10 // any later version. 11 12 // This library is distributed in the hope that it will be useful, 13 // but WITHOUT ANY WARRANTY; without even the implied warranty of 14 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 15 // GNU General Public License for more details. 16 17 // Under Section 7 of GPL version 3, you are granted additional 18 // permissions described in the GCC Runtime Library Exception, version 19 // 3.1, as published by the Free Software Foundation. 20 21 // You should have received a copy of the GNU General Public License and 22 // a copy of the GCC Runtime Library Exception along with this program; 23 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see 24 // <http://www.gnu.org/licenses/>. 25 26 /** @file bits/hashtable.h 27 * This is an internal header file, included by other library headers. 28 * Do not attempt to use it directly. @headername{unordered_map, unordered_set} 29 */ 30 31 #ifndef _HASHTABLE_H 32 #define _HASHTABLE_H 1 33 34 #pragma GCC system_header 35 36 #include <bits/hashtable_policy.h> 37 38 namespace std _GLIBCXX_VISIBILITY(default) 39 { 40 _GLIBCXX_BEGIN_NAMESPACE_VERSION 41 42 // Class template _Hashtable, class definition. 43 44 // Meaning of class template _Hashtable's template parameters 45 46 // _Key and _Value: arbitrary CopyConstructible types. 47 48 // _Allocator: an allocator type ([lib.allocator.requirements]) whose 49 // value type is Value. As a conforming extension, we allow for 50 // value type != Value. 51 52 // _ExtractKey: function object that takes an object of type Value 53 // and returns a value of type _Key. 54 55 // _Equal: function object that takes two objects of type k and returns 56 // a bool-like value that is true if the two objects are considered equal. 57 58 // _H1: the hash function. A unary function object with argument type 59 // Key and result type size_t. Return values should be distributed 60 // over the entire range [0, numeric_limits<size_t>:::max()]. 61 62 // _H2: the range-hashing function (in the terminology of Tavori and 63 // Dreizin). A binary function object whose argument types and result 64 // type are all size_t. Given arguments r and N, the return value is 65 // in the range [0, N). 66 67 // _Hash: the ranged hash function (Tavori and Dreizin). A binary function 68 // whose argument types are _Key and size_t and whose result type is 69 // size_t. Given arguments k and N, the return value is in the range 70 // [0, N). Default: hash(k, N) = h2(h1(k), N). If _Hash is anything other 71 // than the default, _H1 and _H2 are ignored. 72 73 // _RehashPolicy: Policy class with three members, all of which govern 74 // the bucket count. _M_next_bkt(n) returns a bucket count no smaller 75 // than n. _M_bkt_for_elements(n) returns a bucket count appropriate 76 // for an element count of n. _M_need_rehash(n_bkt, n_elt, n_ins) 77 // determines whether, if the current bucket count is n_bkt and the 78 // current element count is n_elt, we need to increase the bucket 79 // count. If so, returns make_pair(true, n), where n is the new 80 // bucket count. If not, returns make_pair(false, <anything>). 81 82 // __cache_hash_code: bool. true if we store the value of the hash 83 // function along with the value. This is a time-space tradeoff. 84 // Storing it may improve lookup speed by reducing the number of times 85 // we need to call the Equal function. 86 87 // __constant_iterators: bool. true if iterator and const_iterator are 88 // both constant iterator types. This is true for unordered_set and 89 // unordered_multiset, false for unordered_map and unordered_multimap. 90 91 // __unique_keys: bool. true if the return value of _Hashtable::count(k) 92 // is always at most one, false if it may be an arbitrary number. This 93 // true for unordered_set and unordered_map, false for unordered_multiset 94 // and unordered_multimap. 95 /** 96 * Here's _Hashtable data structure, each _Hashtable has: 97 * - _Bucket[] _M_buckets 98 * - _Hash_node_base _M_before_begin 99 * - size_type _M_bucket_count 100 * - size_type _M_element_count 101 * 102 * with _Bucket being _Hash_node* and _Hash_node containing: 103 * - _Hash_node* _M_next 104 * - Tp _M_value 105 * - size_t _M_hash_code if cache_hash_code is true 106 * 107 * In terms of Standard containers the hashtable is like the aggregation of: 108 * - std::forward_list<_Node> containing the elements 109 * - std::vector<std::forward_list<_Node>::iterator> representing the buckets 110 * 111 * The non-empty buckets contain the node before the first node in the 112 * bucket. This design makes it possible to implement something like a 113 * std::forward_list::insert_after on container insertion and 114 * std::forward_list::erase_after on container erase calls. 115 * _M_before_begin is equivalent to std::foward_list::before_begin. 116 * Empty buckets contain nullptr. 117 * Note that one of the non-empty buckets contains &_M_before_begin which is 118 * not a dereferenceable node so the node pointer in a bucket shall never be 119 * dereferenced, only its next node can be. 120 * 121 * Walking through a bucket's nodes requires a check on the hash code to see 122 * if each node is still in the bucket. Such a design assumes a quite 123 * efficient hash functor and is one of the reasons it is 124 * highly advisable to set __cache_hash_code to true. 125 * 126 * The container iterators are simply built from nodes. This way incrementing 127 * the iterator is perfectly efficient independent of how many empty buckets 128 * there are in the container. 129 * 130 * On insert we compute the element's hash code and use it to it find the 131 * bucket index. If the element must be inserted in an empty bucket we add 132 * it at the beginning of the singly linked list and make the bucket point to 133 * _M_before_begin. The bucket that used to point to _M_before_begin, if any, 134 * is updated to point to its new before begin node. 135 * 136 * On erase, the simple iterator design requires using the hash functor to 137 * get the index of the bucket to update. For this reason, when 138 * __cache_hash_code is set to false, the hash functor must not throw 139 * and this is enforced by a statied assertion. 140 */ 141 142 template<typename _Key, typename _Value, typename _Allocator, 143 typename _ExtractKey, typename _Equal, 144 typename _H1, typename _H2, typename _Hash, 145 typename _RehashPolicy, 146 bool __cache_hash_code, 147 bool __constant_iterators, 148 bool __unique_keys> 149 class _Hashtable 150 : public __detail::_Rehash_base<_RehashPolicy, 151 _Hashtable<_Key, _Value, _Allocator, 152 _ExtractKey, 153 _Equal, _H1, _H2, _Hash, 154 _RehashPolicy, 155 __cache_hash_code, 156 __constant_iterators, 157 __unique_keys> >, 158 public __detail::_Hashtable_base<_Key, _Value, _ExtractKey, _Equal, 159 _H1, _H2, _Hash, __cache_hash_code>, 160 public __detail::_Map_base<_Key, _Value, _ExtractKey, __unique_keys, 161 _Hashtable<_Key, _Value, _Allocator, 162 _ExtractKey, 163 _Equal, _H1, _H2, _Hash, 164 _RehashPolicy, 165 __cache_hash_code, 166 __constant_iterators, 167 __unique_keys> >, 168 public __detail::_Equality_base<_ExtractKey, __unique_keys, 169 _Hashtable<_Key, _Value, _Allocator, 170 _ExtractKey, 171 _Equal, _H1, _H2, _Hash, 172 _RehashPolicy, 173 __cache_hash_code, 174 __constant_iterators, 175 __unique_keys> > 176 { 177 template<typename _Cond> 178 using __if_hash_code_cached 179 = __or_<__not_<integral_constant<bool, __cache_hash_code>>, _Cond>; 180 181 template<typename _Cond> 182 using __if_hash_code_not_cached 183 = __or_<integral_constant<bool, __cache_hash_code>, _Cond>; 184 185 // When hash codes are not cached the hash functor shall not throw 186 // because it is used in methods (erase, swap...) that shall not throw. 187 static_assert(__if_hash_code_not_cached<__detail::__is_noexcept_hash<_Key, 188 _H1>>::value, 189 "Cache the hash code or qualify your hash functor with noexcept"); 190 191 // Following two static assertions are necessary to guarantee that 192 // swapping two hashtable instances won't invalidate associated local 193 // iterators. 194 195 // When hash codes are cached local iterator only uses H2 which must then 196 // be empty. 197 static_assert(__if_hash_code_cached<is_empty<_H2>>::value, 198 "Functor used to map hash code to bucket index must be empty"); 199 200 typedef __detail::_Hash_code_base<_Key, _Value, _ExtractKey, 201 _H1, _H2, _Hash, 202 __cache_hash_code> _HCBase; 203 204 // When hash codes are not cached local iterator is going to use _HCBase 205 // above to compute node bucket index so it has to be empty. 206 static_assert(__if_hash_code_not_cached<is_empty<_HCBase>>::value, 207 "Cache the hash code or make functors involved in hash code" 208 " and bucket index computation empty"); 209 210 public: 211 typedef _Allocator allocator_type; 212 typedef _Value value_type; 213 typedef _Key key_type; 214 typedef _Equal key_equal; 215 // mapped_type, if present, comes from _Map_base. 216 // hasher, if present, comes from _Hash_code_base. 217 typedef typename _Allocator::pointer pointer; 218 typedef typename _Allocator::const_pointer const_pointer; 219 typedef typename _Allocator::reference reference; 220 typedef typename _Allocator::const_reference const_reference; 221 222 typedef std::size_t size_type; 223 typedef std::ptrdiff_t difference_type; 224 typedef __detail::_Local_iterator<key_type, value_type, _ExtractKey, 225 _H1, _H2, _Hash, 226 __constant_iterators, 227 __cache_hash_code> 228 local_iterator; 229 typedef __detail::_Local_const_iterator<key_type, value_type, _ExtractKey, 230 _H1, _H2, _Hash, 231 __constant_iterators, 232 __cache_hash_code> 233 const_local_iterator; 234 typedef __detail::_Node_iterator<value_type, __constant_iterators, 235 __cache_hash_code> 236 iterator; 237 typedef __detail::_Node_const_iterator<value_type, 238 __constant_iterators, 239 __cache_hash_code> 240 const_iterator; 241 242 template<typename _Key2, typename _Value2, typename _Ex2, bool __unique2, 243 typename _Hashtable2> 244 friend struct __detail::_Map_base; 245 246 private: 247 typedef typename _RehashPolicy::_State _RehashPolicyState; 248 typedef __detail::_Hash_node<_Value, __cache_hash_code> _Node; 249 typedef typename _Allocator::template rebind<_Node>::other 250 _Node_allocator_type; 251 typedef __detail::_Hash_node_base _BaseNode; 252 typedef _BaseNode* _Bucket; 253 typedef typename _Allocator::template rebind<_Bucket>::other 254 _Bucket_allocator_type; 255 256 typedef typename _Allocator::template rebind<_Value>::other 257 _Value_allocator_type; 258 259 _Node_allocator_type _M_node_allocator; 260 _Bucket* _M_buckets; 261 size_type _M_bucket_count; 262 _BaseNode _M_before_begin; 263 size_type _M_element_count; 264 _RehashPolicy _M_rehash_policy; 265 266 template<typename... _Args> 267 _Node* 268 _M_allocate_node(_Args&&... __args); 269 270 void 271 _M_deallocate_node(_Node* __n); 272 273 // Deallocate the linked list of nodes pointed to by __n 274 void 275 _M_deallocate_nodes(_Node* __n); 276 277 _Bucket* 278 _M_allocate_buckets(size_type __n); 279 280 void 281 _M_deallocate_buckets(_Bucket*, size_type __n); 282 283 // Gets bucket begin, deals with the fact that non-empty buckets contain 284 // their before begin node. 285 _Node* 286 _M_bucket_begin(size_type __bkt) const; 287 288 _Node* 289 _M_begin() const 290 { return static_cast<_Node*>(_M_before_begin._M_nxt); } 291 292 public: 293 // Constructor, destructor, assignment, swap 294 _Hashtable(size_type __bucket_hint, 295 const _H1&, const _H2&, const _Hash&, 296 const _Equal&, const _ExtractKey&, 297 const allocator_type&); 298 299 template<typename _InputIterator> 300 _Hashtable(_InputIterator __first, _InputIterator __last, 301 size_type __bucket_hint, 302 const _H1&, const _H2&, const _Hash&, 303 const _Equal&, const _ExtractKey&, 304 const allocator_type&); 305 306 _Hashtable(const _Hashtable&); 307 308 _Hashtable(_Hashtable&&); 309 310 _Hashtable& 311 operator=(const _Hashtable& __ht) 312 { 313 _Hashtable __tmp(__ht); 314 this->swap(__tmp); 315 return *this; 316 } 317 318 _Hashtable& 319 operator=(_Hashtable&& __ht) 320 { 321 // NB: DR 1204. 322 // NB: DR 675. 323 this->clear(); 324 this->swap(__ht); 325 return *this; 326 } 327 328 ~_Hashtable() noexcept; 329 330 void swap(_Hashtable&); 331 332 // Basic container operations 333 iterator 334 begin() noexcept 335 { return iterator(_M_begin()); } 336 337 const_iterator 338 begin() const noexcept 339 { return const_iterator(_M_begin()); } 340 341 iterator 342 end() noexcept 343 { return iterator(nullptr); } 344 345 const_iterator 346 end() const noexcept 347 { return const_iterator(nullptr); } 348 349 const_iterator 350 cbegin() const noexcept 351 { return const_iterator(_M_begin()); } 352 353 const_iterator 354 cend() const noexcept 355 { return const_iterator(nullptr); } 356 357 size_type 358 size() const noexcept 359 { return _M_element_count; } 360 361 bool 362 empty() const noexcept 363 { return size() == 0; } 364 365 allocator_type 366 get_allocator() const noexcept 367 { return allocator_type(_M_node_allocator); } 368 369 size_type 370 max_size() const noexcept 371 { return _M_node_allocator.max_size(); } 372 373 // Observers 374 key_equal 375 key_eq() const 376 { return this->_M_eq(); } 377 378 // hash_function, if present, comes from _Hash_code_base. 379 380 // Bucket operations 381 size_type 382 bucket_count() const noexcept 383 { return _M_bucket_count; } 384 385 size_type 386 max_bucket_count() const noexcept 387 { return max_size(); } 388 389 size_type 390 bucket_size(size_type __n) const 391 { return std::distance(begin(__n), end(__n)); } 392 393 size_type 394 bucket(const key_type& __k) const 395 { return _M_bucket_index(__k, this->_M_hash_code(__k)); } 396 397 local_iterator 398 begin(size_type __n) 399 { return local_iterator(_M_bucket_begin(__n), __n, 400 _M_bucket_count); } 401 402 local_iterator 403 end(size_type __n) 404 { return local_iterator(nullptr, __n, _M_bucket_count); } 405 406 const_local_iterator 407 begin(size_type __n) const 408 { return const_local_iterator(_M_bucket_begin(__n), __n, 409 _M_bucket_count); } 410 411 const_local_iterator 412 end(size_type __n) const 413 { return const_local_iterator(nullptr, __n, _M_bucket_count); } 414 415 // DR 691. 416 const_local_iterator 417 cbegin(size_type __n) const 418 { return const_local_iterator(_M_bucket_begin(__n), __n, 419 _M_bucket_count); } 420 421 const_local_iterator 422 cend(size_type __n) const 423 { return const_local_iterator(nullptr, __n, _M_bucket_count); } 424 425 float 426 load_factor() const noexcept 427 { 428 return static_cast<float>(size()) / static_cast<float>(bucket_count()); 429 } 430 431 // max_load_factor, if present, comes from _Rehash_base. 432 433 // Generalization of max_load_factor. Extension, not found in TR1. Only 434 // useful if _RehashPolicy is something other than the default. 435 const _RehashPolicy& 436 __rehash_policy() const 437 { return _M_rehash_policy; } 438 439 void 440 __rehash_policy(const _RehashPolicy&); 441 442 // Lookup. 443 iterator 444 find(const key_type& __k); 445 446 const_iterator 447 find(const key_type& __k) const; 448 449 size_type 450 count(const key_type& __k) const; 451 452 std::pair<iterator, iterator> 453 equal_range(const key_type& __k); 454 455 std::pair<const_iterator, const_iterator> 456 equal_range(const key_type& __k) const; 457 458 private: 459 // Bucket index computation helpers. 460 size_type 461 _M_bucket_index(_Node* __n) const 462 { return _HCBase::_M_bucket_index(__n, _M_bucket_count); } 463 464 size_type 465 _M_bucket_index(const key_type& __k, 466 typename _Hashtable::_Hash_code_type __c) const 467 { return _HCBase::_M_bucket_index(__k, __c, _M_bucket_count); } 468 469 // Find and insert helper functions and types 470 // Find the node before the one matching the criteria. 471 _BaseNode* 472 _M_find_before_node(size_type, const key_type&, 473 typename _Hashtable::_Hash_code_type) const; 474 475 _Node* 476 _M_find_node(size_type __bkt, const key_type& __key, 477 typename _Hashtable::_Hash_code_type __c) const 478 { 479 _BaseNode* __before_n = _M_find_before_node(__bkt, __key, __c); 480 if (__before_n) 481 return static_cast<_Node*>(__before_n->_M_nxt); 482 return nullptr; 483 } 484 485 // Insert a node at the beginning of a bucket. 486 void 487 _M_insert_bucket_begin(size_type, _Node*); 488 489 // Remove the bucket first node 490 void 491 _M_remove_bucket_begin(size_type __bkt, _Node* __next_n, 492 size_type __next_bkt); 493 494 // Get the node before __n in the bucket __bkt 495 _BaseNode* 496 _M_get_previous_node(size_type __bkt, _BaseNode* __n); 497 498 template<typename _Arg> 499 iterator 500 _M_insert_bucket(_Arg&&, size_type, 501 typename _Hashtable::_Hash_code_type); 502 503 typedef typename std::conditional<__unique_keys, 504 std::pair<iterator, bool>, 505 iterator>::type 506 _Insert_Return_Type; 507 508 typedef typename std::conditional<__unique_keys, 509 std::_Select1st<_Insert_Return_Type>, 510 std::_Identity<_Insert_Return_Type> 511 >::type 512 _Insert_Conv_Type; 513 514 protected: 515 template<typename... _Args> 516 std::pair<iterator, bool> 517 _M_emplace(std::true_type, _Args&&... __args); 518 519 template<typename... _Args> 520 iterator 521 _M_emplace(std::false_type, _Args&&... __args); 522 523 template<typename _Arg> 524 std::pair<iterator, bool> 525 _M_insert(_Arg&&, std::true_type); 526 527 template<typename _Arg> 528 iterator 529 _M_insert(_Arg&&, std::false_type); 530 531 public: 532 // Emplace, insert and erase 533 template<typename... _Args> 534 _Insert_Return_Type 535 emplace(_Args&&... __args) 536 { return _M_emplace(integral_constant<bool, __unique_keys>(), 537 std::forward<_Args>(__args)...); } 538 539 template<typename... _Args> 540 iterator 541 emplace_hint(const_iterator, _Args&&... __args) 542 { return _Insert_Conv_Type()(emplace(std::forward<_Args>(__args)...)); } 543 544 _Insert_Return_Type 545 insert(const value_type& __v) 546 { return _M_insert(__v, integral_constant<bool, __unique_keys>()); } 547 548 iterator 549 insert(const_iterator, const value_type& __v) 550 { return _Insert_Conv_Type()(insert(__v)); } 551 552 template<typename _Pair, typename = typename 553 std::enable_if<__and_<integral_constant<bool, !__constant_iterators>, 554 std::is_constructible<value_type, 555 _Pair&&>>::value>::type> 556 _Insert_Return_Type 557 insert(_Pair&& __v) 558 { return _M_insert(std::forward<_Pair>(__v), 559 integral_constant<bool, __unique_keys>()); } 560 561 template<typename _Pair, typename = typename 562 std::enable_if<__and_<integral_constant<bool, !__constant_iterators>, 563 std::is_constructible<value_type, 564 _Pair&&>>::value>::type> 565 iterator 566 insert(const_iterator, _Pair&& __v) 567 { return _Insert_Conv_Type()(insert(std::forward<_Pair>(__v))); } 568 569 template<typename _InputIterator> 570 void 571 insert(_InputIterator __first, _InputIterator __last); 572 573 void 574 insert(initializer_list<value_type> __l) 575 { this->insert(__l.begin(), __l.end()); } 576 577 iterator 578 erase(const_iterator); 579 580 // LWG 2059. 581 iterator 582 erase(iterator __it) 583 { return erase(const_iterator(__it)); } 584 585 size_type 586 erase(const key_type&); 587 588 iterator 589 erase(const_iterator, const_iterator); 590 591 void 592 clear() noexcept; 593 594 // Set number of buckets to be appropriate for container of n element. 595 void rehash(size_type __n); 596 597 // DR 1189. 598 // reserve, if present, comes from _Rehash_base. 599 600 private: 601 // Helper rehash method used when keys are unique. 602 void _M_rehash_aux(size_type __n, std::true_type); 603 604 // Helper rehash method used when keys can be non-unique. 605 void _M_rehash_aux(size_type __n, std::false_type); 606 607 // Unconditionally change size of bucket array to n, restore hash policy 608 // state to __state on exception. 609 void _M_rehash(size_type __n, const _RehashPolicyState& __state); 610 }; 611 612 613 // Definitions of class template _Hashtable's out-of-line member functions. 614 template<typename _Key, typename _Value, 615 typename _Allocator, typename _ExtractKey, typename _Equal, 616 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 617 bool __chc, bool __cit, bool __uk> 618 template<typename... _Args> 619 typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 620 _H1, _H2, _Hash, _RehashPolicy, 621 __chc, __cit, __uk>::_Node* 622 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 623 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 624 _M_allocate_node(_Args&&... __args) 625 { 626 _Node* __n = _M_node_allocator.allocate(1); 627 __try 628 { 629 _M_node_allocator.construct(__n, std::forward<_Args>(__args)...); 630 return __n; 631 } 632 __catch(...) 633 { 634 _M_node_allocator.deallocate(__n, 1); 635 __throw_exception_again; 636 } 637 } 638 639 template<typename _Key, typename _Value, 640 typename _Allocator, typename _ExtractKey, typename _Equal, 641 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 642 bool __chc, bool __cit, bool __uk> 643 void 644 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 645 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 646 _M_deallocate_node(_Node* __n) 647 { 648 _M_node_allocator.destroy(__n); 649 _M_node_allocator.deallocate(__n, 1); 650 } 651 652 template<typename _Key, typename _Value, 653 typename _Allocator, typename _ExtractKey, typename _Equal, 654 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 655 bool __chc, bool __cit, bool __uk> 656 void 657 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 658 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 659 _M_deallocate_nodes(_Node* __n) 660 { 661 while (__n) 662 { 663 _Node* __tmp = __n; 664 __n = __n->_M_next(); 665 _M_deallocate_node(__tmp); 666 } 667 } 668 669 template<typename _Key, typename _Value, 670 typename _Allocator, typename _ExtractKey, typename _Equal, 671 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 672 bool __chc, bool __cit, bool __uk> 673 typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 674 _H1, _H2, _Hash, _RehashPolicy, 675 __chc, __cit, __uk>::_Bucket* 676 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 677 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 678 _M_allocate_buckets(size_type __n) 679 { 680 _Bucket_allocator_type __alloc(_M_node_allocator); 681 682 _Bucket* __p = __alloc.allocate(__n); 683 __builtin_memset(__p, 0, __n * sizeof(_Bucket)); 684 return __p; 685 } 686 687 template<typename _Key, typename _Value, 688 typename _Allocator, typename _ExtractKey, typename _Equal, 689 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 690 bool __chc, bool __cit, bool __uk> 691 void 692 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 693 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 694 _M_deallocate_buckets(_Bucket* __p, size_type __n) 695 { 696 _Bucket_allocator_type __alloc(_M_node_allocator); 697 __alloc.deallocate(__p, __n); 698 } 699 700 template<typename _Key, typename _Value, 701 typename _Allocator, typename _ExtractKey, typename _Equal, 702 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 703 bool __chc, bool __cit, bool __uk> 704 typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, 705 _Equal, _H1, _H2, _Hash, _RehashPolicy, 706 __chc, __cit, __uk>::_Node* 707 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 708 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 709 _M_bucket_begin(size_type __bkt) const 710 { 711 _BaseNode* __n = _M_buckets[__bkt]; 712 return __n ? static_cast<_Node*>(__n->_M_nxt) : nullptr; 713 } 714 715 template<typename _Key, typename _Value, 716 typename _Allocator, typename _ExtractKey, typename _Equal, 717 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 718 bool __chc, bool __cit, bool __uk> 719 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 720 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 721 _Hashtable(size_type __bucket_hint, 722 const _H1& __h1, const _H2& __h2, const _Hash& __h, 723 const _Equal& __eq, const _ExtractKey& __exk, 724 const allocator_type& __a) 725 : __detail::_Rehash_base<_RehashPolicy, _Hashtable>(), 726 __detail::_Hashtable_base<_Key, _Value, _ExtractKey, _Equal, 727 _H1, _H2, _Hash, __chc>(__exk, __h1, __h2, __h, 728 __eq), 729 __detail::_Map_base<_Key, _Value, _ExtractKey, __uk, _Hashtable>(), 730 _M_node_allocator(__a), 731 _M_bucket_count(0), 732 _M_element_count(0), 733 _M_rehash_policy() 734 { 735 _M_bucket_count = _M_rehash_policy._M_next_bkt(__bucket_hint); 736 // We don't want the rehash policy to ask for the hashtable to shrink 737 // on the first insertion so we need to reset its previous resize level. 738 _M_rehash_policy._M_prev_resize = 0; 739 _M_buckets = _M_allocate_buckets(_M_bucket_count); 740 } 741 742 template<typename _Key, typename _Value, 743 typename _Allocator, typename _ExtractKey, typename _Equal, 744 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 745 bool __chc, bool __cit, bool __uk> 746 template<typename _InputIterator> 747 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 748 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 749 _Hashtable(_InputIterator __f, _InputIterator __l, 750 size_type __bucket_hint, 751 const _H1& __h1, const _H2& __h2, const _Hash& __h, 752 const _Equal& __eq, const _ExtractKey& __exk, 753 const allocator_type& __a) 754 : __detail::_Rehash_base<_RehashPolicy, _Hashtable>(), 755 __detail::_Hashtable_base<_Key, _Value, _ExtractKey, _Equal, 756 _H1, _H2, _Hash, __chc>(__exk, __h1, __h2, __h, 757 __eq), 758 __detail::_Map_base<_Key, _Value, _ExtractKey, __uk, _Hashtable>(), 759 _M_node_allocator(__a), 760 _M_bucket_count(0), 761 _M_element_count(0), 762 _M_rehash_policy() 763 { 764 _M_bucket_count = 765 _M_rehash_policy._M_bkt_for_elements(__detail::__distance_fw(__f, 766 __l)); 767 if (_M_bucket_count <= __bucket_hint) 768 _M_bucket_count = _M_rehash_policy._M_next_bkt(__bucket_hint); 769 770 // We don't want the rehash policy to ask for the hashtable to shrink 771 // on the first insertion so we need to reset its previous resize 772 // level. 773 _M_rehash_policy._M_prev_resize = 0; 774 _M_buckets = _M_allocate_buckets(_M_bucket_count); 775 __try 776 { 777 for (; __f != __l; ++__f) 778 this->insert(*__f); 779 } 780 __catch(...) 781 { 782 clear(); 783 _M_deallocate_buckets(_M_buckets, _M_bucket_count); 784 __throw_exception_again; 785 } 786 } 787 788 template<typename _Key, typename _Value, 789 typename _Allocator, typename _ExtractKey, typename _Equal, 790 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 791 bool __chc, bool __cit, bool __uk> 792 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 793 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 794 _Hashtable(const _Hashtable& __ht) 795 : __detail::_Rehash_base<_RehashPolicy, _Hashtable>(__ht), 796 __detail::_Hashtable_base<_Key, _Value, _ExtractKey, _Equal, 797 _H1, _H2, _Hash, __chc>(__ht), 798 __detail::_Map_base<_Key, _Value, _ExtractKey, __uk, _Hashtable>(__ht), 799 _M_node_allocator(__ht._M_node_allocator), 800 _M_bucket_count(__ht._M_bucket_count), 801 _M_element_count(__ht._M_element_count), 802 _M_rehash_policy(__ht._M_rehash_policy) 803 { 804 _M_buckets = _M_allocate_buckets(_M_bucket_count); 805 __try 806 { 807 if (!__ht._M_before_begin._M_nxt) 808 return; 809 810 // First deal with the special first node pointed to by 811 // _M_before_begin. 812 const _Node* __ht_n = __ht._M_begin(); 813 _Node* __this_n = _M_allocate_node(__ht_n->_M_v); 814 this->_M_copy_code(__this_n, __ht_n); 815 _M_before_begin._M_nxt = __this_n; 816 _M_buckets[_M_bucket_index(__this_n)] = &_M_before_begin; 817 818 // Then deal with other nodes. 819 _BaseNode* __prev_n = __this_n; 820 for (__ht_n = __ht_n->_M_next(); __ht_n; __ht_n = __ht_n->_M_next()) 821 { 822 __this_n = _M_allocate_node(__ht_n->_M_v); 823 __prev_n->_M_nxt = __this_n; 824 this->_M_copy_code(__this_n, __ht_n); 825 size_type __bkt = _M_bucket_index(__this_n); 826 if (!_M_buckets[__bkt]) 827 _M_buckets[__bkt] = __prev_n; 828 __prev_n = __this_n; 829 } 830 } 831 __catch(...) 832 { 833 clear(); 834 _M_deallocate_buckets(_M_buckets, _M_bucket_count); 835 __throw_exception_again; 836 } 837 } 838 839 template<typename _Key, typename _Value, 840 typename _Allocator, typename _ExtractKey, typename _Equal, 841 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 842 bool __chc, bool __cit, bool __uk> 843 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 844 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 845 _Hashtable(_Hashtable&& __ht) 846 : __detail::_Rehash_base<_RehashPolicy, _Hashtable>(__ht), 847 __detail::_Hashtable_base<_Key, _Value, _ExtractKey, _Equal, 848 _H1, _H2, _Hash, __chc>(__ht), 849 __detail::_Map_base<_Key, _Value, _ExtractKey, __uk, _Hashtable>(__ht), 850 _M_node_allocator(std::move(__ht._M_node_allocator)), 851 _M_buckets(__ht._M_buckets), 852 _M_bucket_count(__ht._M_bucket_count), 853 _M_before_begin(__ht._M_before_begin._M_nxt), 854 _M_element_count(__ht._M_element_count), 855 _M_rehash_policy(__ht._M_rehash_policy) 856 { 857 // Update, if necessary, bucket pointing to before begin that hasn't move. 858 if (_M_begin()) 859 _M_buckets[_M_bucket_index(_M_begin())] = &_M_before_begin; 860 __ht._M_rehash_policy = _RehashPolicy(); 861 __ht._M_bucket_count = __ht._M_rehash_policy._M_next_bkt(0); 862 __ht._M_buckets = __ht._M_allocate_buckets(__ht._M_bucket_count); 863 __ht._M_before_begin._M_nxt = nullptr; 864 __ht._M_element_count = 0; 865 } 866 867 template<typename _Key, typename _Value, 868 typename _Allocator, typename _ExtractKey, typename _Equal, 869 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 870 bool __chc, bool __cit, bool __uk> 871 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 872 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 873 ~_Hashtable() noexcept 874 { 875 clear(); 876 _M_deallocate_buckets(_M_buckets, _M_bucket_count); 877 } 878 879 template<typename _Key, typename _Value, 880 typename _Allocator, typename _ExtractKey, typename _Equal, 881 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 882 bool __chc, bool __cit, bool __uk> 883 void 884 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 885 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 886 swap(_Hashtable& __x) 887 { 888 // The only base class with member variables is hash_code_base. We 889 // define _Hash_code_base::_M_swap because different specializations 890 // have different members. 891 this->_M_swap(__x); 892 893 // _GLIBCXX_RESOLVE_LIB_DEFECTS 894 // 431. Swapping containers with unequal allocators. 895 std::__alloc_swap<_Node_allocator_type>::_S_do_it(_M_node_allocator, 896 __x._M_node_allocator); 897 898 std::swap(_M_rehash_policy, __x._M_rehash_policy); 899 std::swap(_M_buckets, __x._M_buckets); 900 std::swap(_M_bucket_count, __x._M_bucket_count); 901 std::swap(_M_before_begin._M_nxt, __x._M_before_begin._M_nxt); 902 std::swap(_M_element_count, __x._M_element_count); 903 // Fix buckets containing the _M_before_begin pointers that can't be 904 // swapped. 905 if (_M_begin()) 906 _M_buckets[_M_bucket_index(_M_begin())] = &_M_before_begin; 907 if (__x._M_begin()) 908 __x._M_buckets[__x._M_bucket_index(__x._M_begin())] 909 = &(__x._M_before_begin); 910 } 911 912 template<typename _Key, typename _Value, 913 typename _Allocator, typename _ExtractKey, typename _Equal, 914 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 915 bool __chc, bool __cit, bool __uk> 916 void 917 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 918 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 919 __rehash_policy(const _RehashPolicy& __pol) 920 { 921 size_type __n_bkt = __pol._M_bkt_for_elements(_M_element_count); 922 if (__n_bkt != _M_bucket_count) 923 _M_rehash(__n_bkt, _M_rehash_policy._M_state()); 924 _M_rehash_policy = __pol; 925 } 926 927 template<typename _Key, typename _Value, 928 typename _Allocator, typename _ExtractKey, typename _Equal, 929 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 930 bool __chc, bool __cit, bool __uk> 931 typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 932 _H1, _H2, _Hash, _RehashPolicy, 933 __chc, __cit, __uk>::iterator 934 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 935 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 936 find(const key_type& __k) 937 { 938 typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k); 939 std::size_t __n = _M_bucket_index(__k, __code); 940 _Node* __p = _M_find_node(__n, __k, __code); 941 return __p ? iterator(__p) : this->end(); 942 } 943 944 template<typename _Key, typename _Value, 945 typename _Allocator, typename _ExtractKey, typename _Equal, 946 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 947 bool __chc, bool __cit, bool __uk> 948 typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 949 _H1, _H2, _Hash, _RehashPolicy, 950 __chc, __cit, __uk>::const_iterator 951 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 952 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 953 find(const key_type& __k) const 954 { 955 typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k); 956 std::size_t __n = _M_bucket_index(__k, __code); 957 _Node* __p = _M_find_node(__n, __k, __code); 958 return __p ? const_iterator(__p) : this->end(); 959 } 960 961 template<typename _Key, typename _Value, 962 typename _Allocator, typename _ExtractKey, typename _Equal, 963 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 964 bool __chc, bool __cit, bool __uk> 965 typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 966 _H1, _H2, _Hash, _RehashPolicy, 967 __chc, __cit, __uk>::size_type 968 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 969 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 970 count(const key_type& __k) const 971 { 972 typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k); 973 std::size_t __n = _M_bucket_index(__k, __code); 974 _Node* __p = _M_bucket_begin(__n); 975 if (!__p) 976 return 0; 977 978 std::size_t __result = 0; 979 for (;; __p = __p->_M_next()) 980 { 981 if (this->_M_equals(__k, __code, __p)) 982 ++__result; 983 else if (__result) 984 // All equivalent values are next to each other, if we found a not 985 // equivalent value after an equivalent one it means that we won't 986 // find any more equivalent values. 987 break; 988 if (!__p->_M_nxt || _M_bucket_index(__p->_M_next()) != __n) 989 break; 990 } 991 return __result; 992 } 993 994 template<typename _Key, typename _Value, 995 typename _Allocator, typename _ExtractKey, typename _Equal, 996 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 997 bool __chc, bool __cit, bool __uk> 998 std::pair<typename _Hashtable<_Key, _Value, _Allocator, 999 _ExtractKey, _Equal, _H1, 1000 _H2, _Hash, _RehashPolicy, 1001 __chc, __cit, __uk>::iterator, 1002 typename _Hashtable<_Key, _Value, _Allocator, 1003 _ExtractKey, _Equal, _H1, 1004 _H2, _Hash, _RehashPolicy, 1005 __chc, __cit, __uk>::iterator> 1006 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 1007 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 1008 equal_range(const key_type& __k) 1009 { 1010 typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k); 1011 std::size_t __n = _M_bucket_index(__k, __code); 1012 _Node* __p = _M_find_node(__n, __k, __code); 1013 1014 if (__p) 1015 { 1016 _Node* __p1 = __p->_M_next(); 1017 while (__p1 && _M_bucket_index(__p1) == __n 1018 && this->_M_equals(__k, __code, __p1)) 1019 __p1 = __p1->_M_next(); 1020 1021 return std::make_pair(iterator(__p), iterator(__p1)); 1022 } 1023 else 1024 return std::make_pair(this->end(), this->end()); 1025 } 1026 1027 template<typename _Key, typename _Value, 1028 typename _Allocator, typename _ExtractKey, typename _Equal, 1029 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 1030 bool __chc, bool __cit, bool __uk> 1031 std::pair<typename _Hashtable<_Key, _Value, _Allocator, 1032 _ExtractKey, _Equal, _H1, 1033 _H2, _Hash, _RehashPolicy, 1034 __chc, __cit, __uk>::const_iterator, 1035 typename _Hashtable<_Key, _Value, _Allocator, 1036 _ExtractKey, _Equal, _H1, 1037 _H2, _Hash, _RehashPolicy, 1038 __chc, __cit, __uk>::const_iterator> 1039 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 1040 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 1041 equal_range(const key_type& __k) const 1042 { 1043 typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k); 1044 std::size_t __n = _M_bucket_index(__k, __code); 1045 _Node* __p = _M_find_node(__n, __k, __code); 1046 1047 if (__p) 1048 { 1049 _Node* __p1 = __p->_M_next(); 1050 while (__p1 && _M_bucket_index(__p1) == __n 1051 && this->_M_equals(__k, __code, __p1)) 1052 __p1 = __p1->_M_next(); 1053 1054 return std::make_pair(const_iterator(__p), const_iterator(__p1)); 1055 } 1056 else 1057 return std::make_pair(this->end(), this->end()); 1058 } 1059 1060 // Find the node whose key compares equal to k in the bucket n. Return nullptr 1061 // if no node is found. 1062 template<typename _Key, typename _Value, 1063 typename _Allocator, typename _ExtractKey, typename _Equal, 1064 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 1065 bool __chc, bool __cit, bool __uk> 1066 typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, 1067 _Equal, _H1, _H2, _Hash, _RehashPolicy, 1068 __chc, __cit, __uk>::_BaseNode* 1069 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 1070 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 1071 _M_find_before_node(size_type __n, const key_type& __k, 1072 typename _Hashtable::_Hash_code_type __code) const 1073 { 1074 _BaseNode* __prev_p = _M_buckets[__n]; 1075 if (!__prev_p) 1076 return nullptr; 1077 _Node* __p = static_cast<_Node*>(__prev_p->_M_nxt); 1078 for (;; __p = __p->_M_next()) 1079 { 1080 if (this->_M_equals(__k, __code, __p)) 1081 return __prev_p; 1082 if (!(__p->_M_nxt) || _M_bucket_index(__p->_M_next()) != __n) 1083 break; 1084 __prev_p = __p; 1085 } 1086 return nullptr; 1087 } 1088 1089 template<typename _Key, typename _Value, 1090 typename _Allocator, typename _ExtractKey, typename _Equal, 1091 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 1092 bool __chc, bool __cit, bool __uk> 1093 void 1094 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 1095 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 1096 _M_insert_bucket_begin(size_type __bkt, _Node* __new_node) 1097 { 1098 if (_M_buckets[__bkt]) 1099 { 1100 // Bucket is not empty, we just need to insert the new node after the 1101 // bucket before begin. 1102 __new_node->_M_nxt = _M_buckets[__bkt]->_M_nxt; 1103 _M_buckets[__bkt]->_M_nxt = __new_node; 1104 } 1105 else 1106 { 1107 // The bucket is empty, the new node is inserted at the beginning of 1108 // the singly-linked list and the bucket will contain _M_before_begin 1109 // pointer. 1110 __new_node->_M_nxt = _M_before_begin._M_nxt; 1111 _M_before_begin._M_nxt = __new_node; 1112 if (__new_node->_M_nxt) 1113 // We must update former begin bucket that is pointing to 1114 // _M_before_begin. 1115 _M_buckets[_M_bucket_index(__new_node->_M_next())] = __new_node; 1116 _M_buckets[__bkt] = &_M_before_begin; 1117 } 1118 } 1119 1120 template<typename _Key, typename _Value, 1121 typename _Allocator, typename _ExtractKey, typename _Equal, 1122 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 1123 bool __chc, bool __cit, bool __uk> 1124 void 1125 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 1126 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 1127 _M_remove_bucket_begin(size_type __bkt, _Node* __next, size_type __next_bkt) 1128 { 1129 if (!__next || __next_bkt != __bkt) 1130 { 1131 // Bucket is now empty 1132 // First update next bucket if any 1133 if (__next) 1134 _M_buckets[__next_bkt] = _M_buckets[__bkt]; 1135 // Second update before begin node if necessary 1136 if (&_M_before_begin == _M_buckets[__bkt]) 1137 _M_before_begin._M_nxt = __next; 1138 _M_buckets[__bkt] = nullptr; 1139 } 1140 } 1141 1142 template<typename _Key, typename _Value, 1143 typename _Allocator, typename _ExtractKey, typename _Equal, 1144 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 1145 bool __chc, bool __cit, bool __uk> 1146 typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, 1147 _Equal, _H1, _H2, _Hash, _RehashPolicy, 1148 __chc, __cit, __uk>::_BaseNode* 1149 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 1150 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 1151 _M_get_previous_node(size_type __bkt, _BaseNode* __n) 1152 { 1153 _BaseNode* __prev_n = _M_buckets[__bkt]; 1154 while (__prev_n->_M_nxt != __n) 1155 __prev_n = __prev_n->_M_nxt; 1156 return __prev_n; 1157 } 1158 1159 template<typename _Key, typename _Value, 1160 typename _Allocator, typename _ExtractKey, typename _Equal, 1161 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 1162 bool __chc, bool __cit, bool __uk> 1163 template<typename... _Args> 1164 std::pair<typename _Hashtable<_Key, _Value, _Allocator, 1165 _ExtractKey, _Equal, _H1, 1166 _H2, _Hash, _RehashPolicy, 1167 __chc, __cit, __uk>::iterator, bool> 1168 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 1169 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 1170 _M_emplace(std::true_type, _Args&&... __args) 1171 { 1172 // First build the node to get access to the hash code 1173 _Node* __new_node = _M_allocate_node(std::forward<_Args>(__args)...); 1174 __try 1175 { 1176 const key_type& __k = this->_M_extract()(__new_node->_M_v); 1177 typename _Hashtable::_Hash_code_type __code 1178 = this->_M_hash_code(__k); 1179 size_type __bkt = _M_bucket_index(__k, __code); 1180 1181 if (_Node* __p = _M_find_node(__bkt, __k, __code)) 1182 { 1183 // There is already an equivalent node, no insertion 1184 _M_deallocate_node(__new_node); 1185 return std::make_pair(iterator(__p), false); 1186 } 1187 1188 // We are going to insert this node 1189 this->_M_store_code(__new_node, __code); 1190 const _RehashPolicyState& __saved_state 1191 = _M_rehash_policy._M_state(); 1192 std::pair<bool, std::size_t> __do_rehash 1193 = _M_rehash_policy._M_need_rehash(_M_bucket_count, 1194 _M_element_count, 1); 1195 1196 if (__do_rehash.first) 1197 { 1198 _M_rehash(__do_rehash.second, __saved_state); 1199 __bkt = _M_bucket_index(__k, __code); 1200 } 1201 1202 _M_insert_bucket_begin(__bkt, __new_node); 1203 ++_M_element_count; 1204 return std::make_pair(iterator(__new_node), true); 1205 } 1206 __catch(...) 1207 { 1208 _M_deallocate_node(__new_node); 1209 __throw_exception_again; 1210 } 1211 } 1212 1213 template<typename _Key, typename _Value, 1214 typename _Allocator, typename _ExtractKey, typename _Equal, 1215 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 1216 bool __chc, bool __cit, bool __uk> 1217 template<typename... _Args> 1218 typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 1219 _H1, _H2, _Hash, _RehashPolicy, 1220 __chc, __cit, __uk>::iterator 1221 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 1222 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 1223 _M_emplace(std::false_type, _Args&&... __args) 1224 { 1225 const _RehashPolicyState& __saved_state = _M_rehash_policy._M_state(); 1226 std::pair<bool, std::size_t> __do_rehash 1227 = _M_rehash_policy._M_need_rehash(_M_bucket_count, 1228 _M_element_count, 1); 1229 1230 // First build the node to get its hash code. 1231 _Node* __new_node = _M_allocate_node(std::forward<_Args>(__args)...); 1232 __try 1233 { 1234 const key_type& __k = this->_M_extract()(__new_node->_M_v); 1235 typename _Hashtable::_Hash_code_type __code 1236 = this->_M_hash_code(__k); 1237 this->_M_store_code(__new_node, __code); 1238 1239 // Second, do rehash if necessary. 1240 if (__do_rehash.first) 1241 _M_rehash(__do_rehash.second, __saved_state); 1242 1243 // Third, find the node before an equivalent one. 1244 size_type __bkt = _M_bucket_index(__k, __code); 1245 _BaseNode* __prev = _M_find_before_node(__bkt, __k, __code); 1246 1247 if (__prev) 1248 { 1249 // Insert after the node before the equivalent one. 1250 __new_node->_M_nxt = __prev->_M_nxt; 1251 __prev->_M_nxt = __new_node; 1252 } 1253 else 1254 // The inserted node has no equivalent in the hashtable. We must 1255 // insert the new node at the beginning of the bucket to preserve 1256 // equivalent elements' relative positions. 1257 _M_insert_bucket_begin(__bkt, __new_node); 1258 ++_M_element_count; 1259 return iterator(__new_node); 1260 } 1261 __catch(...) 1262 { 1263 _M_deallocate_node(__new_node); 1264 __throw_exception_again; 1265 } 1266 } 1267 1268 // Insert v in bucket n (assumes no element with its key already present). 1269 template<typename _Key, typename _Value, 1270 typename _Allocator, typename _ExtractKey, typename _Equal, 1271 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 1272 bool __chc, bool __cit, bool __uk> 1273 template<typename _Arg> 1274 typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 1275 _H1, _H2, _Hash, _RehashPolicy, 1276 __chc, __cit, __uk>::iterator 1277 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 1278 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 1279 _M_insert_bucket(_Arg&& __v, size_type __n, 1280 typename _Hashtable::_Hash_code_type __code) 1281 { 1282 const _RehashPolicyState& __saved_state = _M_rehash_policy._M_state(); 1283 std::pair<bool, std::size_t> __do_rehash 1284 = _M_rehash_policy._M_need_rehash(_M_bucket_count, 1285 _M_element_count, 1); 1286 1287 if (__do_rehash.first) 1288 { 1289 const key_type& __k = this->_M_extract()(__v); 1290 __n = _HCBase::_M_bucket_index(__k, __code, __do_rehash.second); 1291 } 1292 1293 _Node* __new_node = nullptr; 1294 __try 1295 { 1296 // Allocate the new node before doing the rehash so that we 1297 // don't do a rehash if the allocation throws. 1298 __new_node = _M_allocate_node(std::forward<_Arg>(__v)); 1299 this->_M_store_code(__new_node, __code); 1300 if (__do_rehash.first) 1301 _M_rehash(__do_rehash.second, __saved_state); 1302 1303 _M_insert_bucket_begin(__n, __new_node); 1304 ++_M_element_count; 1305 return iterator(__new_node); 1306 } 1307 __catch(...) 1308 { 1309 if (!__new_node) 1310 _M_rehash_policy._M_reset(__saved_state); 1311 else 1312 _M_deallocate_node(__new_node); 1313 __throw_exception_again; 1314 } 1315 } 1316 1317 // Insert v if no element with its key is already present. 1318 template<typename _Key, typename _Value, 1319 typename _Allocator, typename _ExtractKey, typename _Equal, 1320 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 1321 bool __chc, bool __cit, bool __uk> 1322 template<typename _Arg> 1323 std::pair<typename _Hashtable<_Key, _Value, _Allocator, 1324 _ExtractKey, _Equal, _H1, 1325 _H2, _Hash, _RehashPolicy, 1326 __chc, __cit, __uk>::iterator, bool> 1327 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 1328 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 1329 _M_insert(_Arg&& __v, std::true_type) 1330 { 1331 const key_type& __k = this->_M_extract()(__v); 1332 typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k); 1333 size_type __n = _M_bucket_index(__k, __code); 1334 1335 if (_Node* __p = _M_find_node(__n, __k, __code)) 1336 return std::make_pair(iterator(__p), false); 1337 return std::make_pair(_M_insert_bucket(std::forward<_Arg>(__v), 1338 __n, __code), true); 1339 } 1340 1341 // Insert v unconditionally. 1342 template<typename _Key, typename _Value, 1343 typename _Allocator, typename _ExtractKey, typename _Equal, 1344 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 1345 bool __chc, bool __cit, bool __uk> 1346 template<typename _Arg> 1347 typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 1348 _H1, _H2, _Hash, _RehashPolicy, 1349 __chc, __cit, __uk>::iterator 1350 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 1351 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 1352 _M_insert(_Arg&& __v, std::false_type) 1353 { 1354 const _RehashPolicyState& __saved_state = _M_rehash_policy._M_state(); 1355 std::pair<bool, std::size_t> __do_rehash 1356 = _M_rehash_policy._M_need_rehash(_M_bucket_count, 1357 _M_element_count, 1); 1358 1359 // First compute the hash code so that we don't do anything if it throws. 1360 typename _Hashtable::_Hash_code_type __code 1361 = this->_M_hash_code(this->_M_extract()(__v)); 1362 1363 _Node* __new_node = nullptr; 1364 __try 1365 { 1366 // Second allocate new node so that we don't rehash if it throws. 1367 __new_node = _M_allocate_node(std::forward<_Arg>(__v)); 1368 this->_M_store_code(__new_node, __code); 1369 if (__do_rehash.first) 1370 _M_rehash(__do_rehash.second, __saved_state); 1371 1372 // Third, find the node before an equivalent one. 1373 size_type __bkt = _M_bucket_index(__new_node); 1374 _BaseNode* __prev 1375 = _M_find_before_node(__bkt, this->_M_extract()(__new_node->_M_v), 1376 __code); 1377 if (__prev) 1378 { 1379 // Insert after the node before the equivalent one. 1380 __new_node->_M_nxt = __prev->_M_nxt; 1381 __prev->_M_nxt = __new_node; 1382 } 1383 else 1384 // The inserted node has no equivalent in the hashtable. We must 1385 // insert the new node at the beginning of the bucket to preserve 1386 // equivalent elements relative positions. 1387 _M_insert_bucket_begin(__bkt, __new_node); 1388 ++_M_element_count; 1389 return iterator(__new_node); 1390 } 1391 __catch(...) 1392 { 1393 if (!__new_node) 1394 _M_rehash_policy._M_reset(__saved_state); 1395 else 1396 _M_deallocate_node(__new_node); 1397 __throw_exception_again; 1398 } 1399 } 1400 1401 template<typename _Key, typename _Value, 1402 typename _Allocator, typename _ExtractKey, typename _Equal, 1403 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 1404 bool __chc, bool __cit, bool __uk> 1405 template<typename _InputIterator> 1406 void 1407 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 1408 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 1409 insert(_InputIterator __first, _InputIterator __last) 1410 { 1411 size_type __n_elt = __detail::__distance_fw(__first, __last); 1412 const _RehashPolicyState& __saved_state = _M_rehash_policy._M_state(); 1413 std::pair<bool, std::size_t> __do_rehash 1414 = _M_rehash_policy._M_need_rehash(_M_bucket_count, 1415 _M_element_count, __n_elt); 1416 if (__do_rehash.first) 1417 _M_rehash(__do_rehash.second, __saved_state); 1418 1419 for (; __first != __last; ++__first) 1420 this->insert(*__first); 1421 } 1422 1423 template<typename _Key, typename _Value, 1424 typename _Allocator, typename _ExtractKey, typename _Equal, 1425 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 1426 bool __chc, bool __cit, bool __uk> 1427 typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 1428 _H1, _H2, _Hash, _RehashPolicy, 1429 __chc, __cit, __uk>::iterator 1430 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 1431 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 1432 erase(const_iterator __it) 1433 { 1434 _Node* __n = __it._M_cur; 1435 std::size_t __bkt = _M_bucket_index(__n); 1436 1437 // Look for previous node to unlink it from the erased one, this is why 1438 // we need buckets to contain the before begin to make this search fast. 1439 _BaseNode* __prev_n = _M_get_previous_node(__bkt, __n); 1440 if (__n == _M_bucket_begin(__bkt)) 1441 _M_remove_bucket_begin(__bkt, __n->_M_next(), 1442 __n->_M_nxt ? _M_bucket_index(__n->_M_next()) : 0); 1443 else if (__n->_M_nxt) 1444 { 1445 size_type __next_bkt = _M_bucket_index(__n->_M_next()); 1446 if (__next_bkt != __bkt) 1447 _M_buckets[__next_bkt] = __prev_n; 1448 } 1449 1450 __prev_n->_M_nxt = __n->_M_nxt; 1451 iterator __result(__n->_M_next()); 1452 _M_deallocate_node(__n); 1453 --_M_element_count; 1454 1455 return __result; 1456 } 1457 1458 template<typename _Key, typename _Value, 1459 typename _Allocator, typename _ExtractKey, typename _Equal, 1460 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 1461 bool __chc, bool __cit, bool __uk> 1462 typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 1463 _H1, _H2, _Hash, _RehashPolicy, 1464 __chc, __cit, __uk>::size_type 1465 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 1466 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 1467 erase(const key_type& __k) 1468 { 1469 typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k); 1470 std::size_t __bkt = _M_bucket_index(__k, __code); 1471 // Look for the node before the first matching node. 1472 _BaseNode* __prev_n = _M_find_before_node(__bkt, __k, __code); 1473 if (!__prev_n) 1474 return 0; 1475 _Node* __n = static_cast<_Node*>(__prev_n->_M_nxt); 1476 bool __is_bucket_begin = _M_buckets[__bkt] == __prev_n; 1477 1478 // We found a matching node, start deallocation loop from it 1479 std::size_t __next_bkt = __bkt; 1480 _Node* __next_n = __n; 1481 size_type __result = 0; 1482 _Node* __saved_n = nullptr; 1483 do 1484 { 1485 _Node* __p = __next_n; 1486 __next_n = __p->_M_next(); 1487 // _GLIBCXX_RESOLVE_LIB_DEFECTS 1488 // 526. Is it undefined if a function in the standard changes 1489 // in parameters? 1490 if (std::__addressof(this->_M_extract()(__p->_M_v)) 1491 != std::__addressof(__k)) 1492 _M_deallocate_node(__p); 1493 else 1494 __saved_n = __p; 1495 --_M_element_count; 1496 ++__result; 1497 if (!__next_n) 1498 break; 1499 __next_bkt = _M_bucket_index(__next_n); 1500 } 1501 while (__next_bkt == __bkt && this->_M_equals(__k, __code, __next_n)); 1502 1503 if (__saved_n) 1504 _M_deallocate_node(__saved_n); 1505 if (__is_bucket_begin) 1506 _M_remove_bucket_begin(__bkt, __next_n, __next_bkt); 1507 else if (__next_n && __next_bkt != __bkt) 1508 _M_buckets[__next_bkt] = __prev_n; 1509 if (__prev_n) 1510 __prev_n->_M_nxt = __next_n; 1511 return __result; 1512 } 1513 1514 template<typename _Key, typename _Value, 1515 typename _Allocator, typename _ExtractKey, typename _Equal, 1516 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 1517 bool __chc, bool __cit, bool __uk> 1518 typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 1519 _H1, _H2, _Hash, _RehashPolicy, 1520 __chc, __cit, __uk>::iterator 1521 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 1522 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 1523 erase(const_iterator __first, const_iterator __last) 1524 { 1525 _Node* __n = __first._M_cur; 1526 _Node* __last_n = __last._M_cur; 1527 if (__n == __last_n) 1528 return iterator(__n); 1529 1530 std::size_t __bkt = _M_bucket_index(__n); 1531 1532 _BaseNode* __prev_n = _M_get_previous_node(__bkt, __n); 1533 bool __is_bucket_begin = __n == _M_bucket_begin(__bkt); 1534 std::size_t __n_bkt = __bkt; 1535 for (;;) 1536 { 1537 do 1538 { 1539 _Node* __tmp = __n; 1540 __n = __n->_M_next(); 1541 _M_deallocate_node(__tmp); 1542 --_M_element_count; 1543 if (!__n) 1544 break; 1545 __n_bkt = _M_bucket_index(__n); 1546 } 1547 while (__n != __last_n && __n_bkt == __bkt); 1548 if (__is_bucket_begin) 1549 _M_remove_bucket_begin(__bkt, __n, __n_bkt); 1550 if (__n == __last_n) 1551 break; 1552 __is_bucket_begin = true; 1553 __bkt = __n_bkt; 1554 } 1555 1556 if (__n && (__n_bkt != __bkt || __is_bucket_begin)) 1557 _M_buckets[__n_bkt] = __prev_n; 1558 __prev_n->_M_nxt = __n; 1559 return iterator(__n); 1560 } 1561 1562 template<typename _Key, typename _Value, 1563 typename _Allocator, typename _ExtractKey, typename _Equal, 1564 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 1565 bool __chc, bool __cit, bool __uk> 1566 void 1567 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 1568 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 1569 clear() noexcept 1570 { 1571 _M_deallocate_nodes(_M_begin()); 1572 __builtin_memset(_M_buckets, 0, _M_bucket_count * sizeof(_Bucket)); 1573 _M_element_count = 0; 1574 _M_before_begin._M_nxt = nullptr; 1575 } 1576 1577 template<typename _Key, typename _Value, 1578 typename _Allocator, typename _ExtractKey, typename _Equal, 1579 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 1580 bool __chc, bool __cit, bool __uk> 1581 void 1582 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 1583 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 1584 rehash(size_type __n) 1585 { 1586 const _RehashPolicyState& __saved_state = _M_rehash_policy._M_state(); 1587 std::size_t __buckets 1588 = _M_rehash_policy._M_bkt_for_elements(_M_element_count + 1); 1589 if (__buckets <= __n) 1590 __buckets = _M_rehash_policy._M_next_bkt(__n); 1591 1592 if (__buckets != _M_bucket_count) 1593 { 1594 _M_rehash(__buckets, __saved_state); 1595 1596 // We don't want the rehash policy to ask for the hashtable to shrink 1597 // on the next insertion so we need to reset its previous resize 1598 // level. 1599 _M_rehash_policy._M_prev_resize = 0; 1600 } 1601 else 1602 // No rehash, restore previous state to keep a consistent state. 1603 _M_rehash_policy._M_reset(__saved_state); 1604 } 1605 1606 template<typename _Key, typename _Value, 1607 typename _Allocator, typename _ExtractKey, typename _Equal, 1608 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 1609 bool __chc, bool __cit, bool __uk> 1610 void 1611 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 1612 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 1613 _M_rehash(size_type __n, const _RehashPolicyState& __state) 1614 { 1615 __try 1616 { 1617 _M_rehash_aux(__n, integral_constant<bool, __uk>()); 1618 } 1619 __catch(...) 1620 { 1621 // A failure here means that buckets allocation failed. We only 1622 // have to restore hash policy previous state. 1623 _M_rehash_policy._M_reset(__state); 1624 __throw_exception_again; 1625 } 1626 } 1627 1628 // Rehash when there is no equivalent elements. 1629 template<typename _Key, typename _Value, 1630 typename _Allocator, typename _ExtractKey, typename _Equal, 1631 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 1632 bool __chc, bool __cit, bool __uk> 1633 void 1634 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 1635 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 1636 _M_rehash_aux(size_type __n, std::true_type) 1637 { 1638 _Bucket* __new_buckets = _M_allocate_buckets(__n); 1639 _Node* __p = _M_begin(); 1640 _M_before_begin._M_nxt = nullptr; 1641 std::size_t __bbegin_bkt = 0; 1642 while (__p) 1643 { 1644 _Node* __next = __p->_M_next(); 1645 std::size_t __bkt = _HCBase::_M_bucket_index(__p, __n); 1646 if (!__new_buckets[__bkt]) 1647 { 1648 __p->_M_nxt = _M_before_begin._M_nxt; 1649 _M_before_begin._M_nxt = __p; 1650 __new_buckets[__bkt] = &_M_before_begin; 1651 if (__p->_M_nxt) 1652 __new_buckets[__bbegin_bkt] = __p; 1653 __bbegin_bkt = __bkt; 1654 } 1655 else 1656 { 1657 __p->_M_nxt = __new_buckets[__bkt]->_M_nxt; 1658 __new_buckets[__bkt]->_M_nxt = __p; 1659 } 1660 __p = __next; 1661 } 1662 _M_deallocate_buckets(_M_buckets, _M_bucket_count); 1663 _M_bucket_count = __n; 1664 _M_buckets = __new_buckets; 1665 } 1666 1667 // Rehash when there can be equivalent elements, preserve their relative 1668 // order. 1669 template<typename _Key, typename _Value, 1670 typename _Allocator, typename _ExtractKey, typename _Equal, 1671 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 1672 bool __chc, bool __cit, bool __uk> 1673 void 1674 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 1675 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 1676 _M_rehash_aux(size_type __n, std::false_type) 1677 { 1678 _Bucket* __new_buckets = _M_allocate_buckets(__n); 1679 1680 _Node* __p = _M_begin(); 1681 _M_before_begin._M_nxt = nullptr; 1682 std::size_t __bbegin_bkt = 0; 1683 std::size_t __prev_bkt = 0; 1684 _Node* __prev_p = nullptr; 1685 bool __check_bucket = false; 1686 1687 while (__p) 1688 { 1689 _Node* __next = __p->_M_next(); 1690 std::size_t __bkt = _HCBase::_M_bucket_index(__p, __n); 1691 1692 if (__prev_p && __prev_bkt == __bkt) 1693 { 1694 // Previous insert was already in this bucket, we insert after 1695 // the previously inserted one to preserve equivalent elements 1696 // relative order. 1697 __p->_M_nxt = __prev_p->_M_nxt; 1698 __prev_p->_M_nxt = __p; 1699 1700 // Inserting after a node in a bucket require to check that we 1701 // haven't change the bucket last node, in this case next 1702 // bucket containing its before begin node must be updated. We 1703 // schedule a check as soon as we move out of the sequence of 1704 // equivalent nodes to limit the number of checks. 1705 __check_bucket = true; 1706 } 1707 else 1708 { 1709 if (__check_bucket) 1710 { 1711 // Check if we shall update the next bucket because of 1712 // insertions into __prev_bkt bucket. 1713 if (__prev_p->_M_nxt) 1714 { 1715 std::size_t __next_bkt 1716 = _HCBase::_M_bucket_index(__prev_p->_M_next(), __n); 1717 if (__next_bkt != __prev_bkt) 1718 __new_buckets[__next_bkt] = __prev_p; 1719 } 1720 __check_bucket = false; 1721 } 1722 if (!__new_buckets[__bkt]) 1723 { 1724 __p->_M_nxt = _M_before_begin._M_nxt; 1725 _M_before_begin._M_nxt = __p; 1726 __new_buckets[__bkt] = &_M_before_begin; 1727 if (__p->_M_nxt) 1728 __new_buckets[__bbegin_bkt] = __p; 1729 __bbegin_bkt = __bkt; 1730 } 1731 else 1732 { 1733 __p->_M_nxt = __new_buckets[__bkt]->_M_nxt; 1734 __new_buckets[__bkt]->_M_nxt = __p; 1735 } 1736 } 1737 1738 __prev_p = __p; 1739 __prev_bkt = __bkt; 1740 __p = __next; 1741 } 1742 1743 if (__check_bucket && __prev_p->_M_nxt) 1744 { 1745 std::size_t __next_bkt 1746 = _HCBase::_M_bucket_index(__prev_p->_M_next(), __n); 1747 if (__next_bkt != __prev_bkt) 1748 __new_buckets[__next_bkt] = __prev_p; 1749 } 1750 1751 _M_deallocate_buckets(_M_buckets, _M_bucket_count); 1752 _M_bucket_count = __n; 1753 _M_buckets = __new_buckets; 1754 } 1755 1756 _GLIBCXX_END_NAMESPACE_VERSION 1757 } // namespace std 1758 1759 #endif // _HASHTABLE_H 1760