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