1 // hashtable.h header -*- C++ -*- 2 3 // Copyright (C) 2007, 2008, 2009, 2010, 2011 Free Software Foundation, Inc. 4 // 5 // This file is part of the GNU ISO C++ Library. This library is free 6 // software; you can redistribute it and/or modify it under the 7 // terms of the GNU General Public License as published by the 8 // Free Software Foundation; either version 3, or (at your option) 9 // any later version. 10 11 // This library is distributed in the hope that it will be useful, 12 // but WITHOUT ANY WARRANTY; without even the implied warranty of 13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 14 // GNU General Public License for more details. 15 16 // Under Section 7 of GPL version 3, you are granted additional 17 // permissions described in the GCC Runtime Library Exception, version 18 // 3.1, as published by the Free Software Foundation. 19 20 // You should have received a copy of the GNU General Public License and 21 // a copy of the GCC Runtime Library Exception along with this program; 22 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see 23 // <http://www.gnu.org/licenses/>. 24 25 /** @file bits/hashtable.h 26 * This is an internal header file, included by other library headers. 27 * Do not attempt to use it directly. @headername{unordered_map, unordered_set} 28 */ 29 30 #ifndef _HASHTABLE_H 31 #define _HASHTABLE_H 1 32 33 #pragma GCC system_header 34 35 #include <bits/hashtable_policy.h> 36 37 namespace std _GLIBCXX_VISIBILITY(default) 38 { 39 _GLIBCXX_BEGIN_NAMESPACE_VERSION 40 41 // Class template _Hashtable, class definition. 42 43 // Meaning of class template _Hashtable's template parameters 44 45 // _Key and _Value: arbitrary CopyConstructible types. 46 47 // _Allocator: an allocator type ([lib.allocator.requirements]) whose 48 // value type is Value. As a conforming extension, we allow for 49 // value type != Value. 50 51 // _ExtractKey: function object that takes a object of type Value 52 // and returns a value of type _Key. 53 54 // _Equal: function object that takes two objects of type k and returns 55 // a bool-like value that is true if the two objects are considered equal. 56 57 // _H1: the hash function. A unary function object with argument type 58 // Key and result type size_t. Return values should be distributed 59 // over the entire range [0, numeric_limits<size_t>:::max()]. 60 61 // _H2: the range-hashing function (in the terminology of Tavori and 62 // Dreizin). A binary function object whose argument types and result 63 // type are all size_t. Given arguments r and N, the return value is 64 // in the range [0, N). 65 66 // _Hash: the ranged hash function (Tavori and Dreizin). A binary function 67 // whose argument types are _Key and size_t and whose result type is 68 // size_t. Given arguments k and N, the return value is in the range 69 // [0, N). Default: hash(k, N) = h2(h1(k), N). If _Hash is anything other 70 // than the default, _H1 and _H2 are ignored. 71 72 // _RehashPolicy: Policy class with three members, all of which govern 73 // the bucket count. _M_next_bkt(n) returns a bucket count no smaller 74 // than n. _M_bkt_for_elements(n) returns a bucket count appropriate 75 // for an element count of n. _M_need_rehash(n_bkt, n_elt, n_ins) 76 // determines whether, if the current bucket count is n_bkt and the 77 // current element count is n_elt, we need to increase the bucket 78 // count. If so, returns make_pair(true, n), where n is the new 79 // bucket count. If not, returns make_pair(false, <anything>). 80 81 // ??? Right now it is hard-wired that the number of buckets never 82 // shrinks. Should we allow _RehashPolicy to change that? 83 84 // __cache_hash_code: bool. true if we store the value of the hash 85 // function along with the value. This is a time-space tradeoff. 86 // Storing it may improve lookup speed by reducing the number of times 87 // we need to call the Equal function. 88 89 // __constant_iterators: bool. true if iterator and const_iterator are 90 // both constant iterator types. This is true for unordered_set and 91 // unordered_multiset, false for unordered_map and unordered_multimap. 92 93 // __unique_keys: bool. true if the return value of _Hashtable::count(k) 94 // is always at most one, false if it may be an arbitrary number. This 95 // true for unordered_set and unordered_map, false for unordered_multiset 96 // and unordered_multimap. 97 98 template<typename _Key, typename _Value, typename _Allocator, 99 typename _ExtractKey, typename _Equal, 100 typename _H1, typename _H2, typename _Hash, 101 typename _RehashPolicy, 102 bool __cache_hash_code, 103 bool __constant_iterators, 104 bool __unique_keys> 105 class _Hashtable 106 : public __detail::_Rehash_base<_RehashPolicy, 107 _Hashtable<_Key, _Value, _Allocator, 108 _ExtractKey, 109 _Equal, _H1, _H2, _Hash, 110 _RehashPolicy, 111 __cache_hash_code, 112 __constant_iterators, 113 __unique_keys> >, 114 public __detail::_Hash_code_base<_Key, _Value, _ExtractKey, _Equal, 115 _H1, _H2, _Hash, __cache_hash_code>, 116 public __detail::_Map_base<_Key, _Value, _ExtractKey, __unique_keys, 117 _Hashtable<_Key, _Value, _Allocator, 118 _ExtractKey, 119 _Equal, _H1, _H2, _Hash, 120 _RehashPolicy, 121 __cache_hash_code, 122 __constant_iterators, 123 __unique_keys> >, 124 public __detail::_Equality_base<_ExtractKey, __unique_keys, 125 _Hashtable<_Key, _Value, _Allocator, 126 _ExtractKey, 127 _Equal, _H1, _H2, _Hash, 128 _RehashPolicy, 129 __cache_hash_code, 130 __constant_iterators, 131 __unique_keys> > 132 { 133 public: 134 typedef _Allocator allocator_type; 135 typedef _Value value_type; 136 typedef _Key key_type; 137 typedef _Equal key_equal; 138 // mapped_type, if present, comes from _Map_base. 139 // hasher, if present, comes from _Hash_code_base. 140 typedef typename _Allocator::pointer pointer; 141 typedef typename _Allocator::const_pointer const_pointer; 142 typedef typename _Allocator::reference reference; 143 typedef typename _Allocator::const_reference const_reference; 144 145 typedef std::size_t size_type; 146 typedef std::ptrdiff_t difference_type; 147 typedef __detail::_Node_iterator<value_type, __constant_iterators, 148 __cache_hash_code> 149 local_iterator; 150 typedef __detail::_Node_const_iterator<value_type, 151 __constant_iterators, 152 __cache_hash_code> 153 const_local_iterator; 154 155 typedef __detail::_Hashtable_iterator<value_type, __constant_iterators, 156 __cache_hash_code> 157 iterator; 158 typedef __detail::_Hashtable_const_iterator<value_type, 159 __constant_iterators, 160 __cache_hash_code> 161 const_iterator; 162 163 template<typename _Key2, typename _Value2, typename _Ex2, bool __unique2, 164 typename _Hashtable2> 165 friend struct __detail::_Map_base; 166 167 private: 168 typedef __detail::_Hash_node<_Value, __cache_hash_code> _Node; 169 typedef typename _Allocator::template rebind<_Node>::other 170 _Node_allocator_type; 171 typedef typename _Allocator::template rebind<_Node*>::other 172 _Bucket_allocator_type; 173 174 typedef typename _Allocator::template rebind<_Value>::other 175 _Value_allocator_type; 176 177 _Node_allocator_type _M_node_allocator; 178 _Node** _M_buckets; 179 size_type _M_bucket_count; 180 size_type _M_begin_bucket_index; // First non-empty bucket. 181 size_type _M_element_count; 182 _RehashPolicy _M_rehash_policy; 183 184 template<typename... _Args> 185 _Node* 186 _M_allocate_node(_Args&&... __args); 187 188 void 189 _M_deallocate_node(_Node* __n); 190 191 void 192 _M_deallocate_nodes(_Node**, size_type); 193 194 _Node** 195 _M_allocate_buckets(size_type __n); 196 197 void 198 _M_deallocate_buckets(_Node**, size_type __n); 199 200 public: 201 // Constructor, destructor, assignment, swap 202 _Hashtable(size_type __bucket_hint, 203 const _H1&, const _H2&, const _Hash&, 204 const _Equal&, const _ExtractKey&, 205 const allocator_type&); 206 207 template<typename _InputIterator> 208 _Hashtable(_InputIterator __first, _InputIterator __last, 209 size_type __bucket_hint, 210 const _H1&, const _H2&, const _Hash&, 211 const _Equal&, const _ExtractKey&, 212 const allocator_type&); 213 214 _Hashtable(const _Hashtable&); 215 216 _Hashtable(_Hashtable&&); 217 218 _Hashtable& 219 operator=(const _Hashtable& __ht) 220 { 221 _Hashtable __tmp(__ht); 222 this->swap(__tmp); 223 return *this; 224 } 225 226 _Hashtable& 227 operator=(_Hashtable&& __ht) 228 { 229 // NB: DR 1204. 230 // NB: DR 675. 231 this->clear(); 232 this->swap(__ht); 233 return *this; 234 } 235 236 ~_Hashtable(); 237 238 void swap(_Hashtable&); 239 240 // Basic container operations 241 iterator 242 begin() 243 { return iterator(_M_buckets + _M_begin_bucket_index); } 244 245 const_iterator 246 begin() const 247 { return const_iterator(_M_buckets + _M_begin_bucket_index); } 248 249 iterator 250 end() 251 { return iterator(_M_buckets + _M_bucket_count); } 252 253 const_iterator 254 end() const 255 { return const_iterator(_M_buckets + _M_bucket_count); } 256 257 const_iterator 258 cbegin() const 259 { return const_iterator(_M_buckets + _M_begin_bucket_index); } 260 261 const_iterator 262 cend() const 263 { return const_iterator(_M_buckets + _M_bucket_count); } 264 265 size_type 266 size() const 267 { return _M_element_count; } 268 269 bool 270 empty() const 271 { return size() == 0; } 272 273 allocator_type 274 get_allocator() const 275 { return allocator_type(_M_node_allocator); } 276 277 size_type 278 max_size() const 279 { return _M_node_allocator.max_size(); } 280 281 // Observers 282 key_equal 283 key_eq() const 284 { return this->_M_eq; } 285 286 // hash_function, if present, comes from _Hash_code_base. 287 288 // Bucket operations 289 size_type 290 bucket_count() const 291 { return _M_bucket_count; } 292 293 size_type 294 max_bucket_count() const 295 { return max_size(); } 296 297 size_type 298 bucket_size(size_type __n) const 299 { return std::distance(begin(__n), end(__n)); } 300 301 size_type 302 bucket(const key_type& __k) const 303 { 304 return this->_M_bucket_index(__k, this->_M_hash_code(__k), 305 bucket_count()); 306 } 307 308 local_iterator 309 begin(size_type __n) 310 { return local_iterator(_M_buckets[__n]); } 311 312 local_iterator 313 end(size_type) 314 { return local_iterator(0); } 315 316 const_local_iterator 317 begin(size_type __n) const 318 { return const_local_iterator(_M_buckets[__n]); } 319 320 const_local_iterator 321 end(size_type) const 322 { return const_local_iterator(0); } 323 324 // DR 691. 325 const_local_iterator 326 cbegin(size_type __n) const 327 { return const_local_iterator(_M_buckets[__n]); } 328 329 const_local_iterator 330 cend(size_type) const 331 { return const_local_iterator(0); } 332 333 float 334 load_factor() const 335 { 336 return static_cast<float>(size()) / static_cast<float>(bucket_count()); 337 } 338 339 // max_load_factor, if present, comes from _Rehash_base. 340 341 // Generalization of max_load_factor. Extension, not found in TR1. Only 342 // useful if _RehashPolicy is something other than the default. 343 const _RehashPolicy& 344 __rehash_policy() const 345 { return _M_rehash_policy; } 346 347 void 348 __rehash_policy(const _RehashPolicy&); 349 350 // Lookup. 351 iterator 352 find(const key_type& __k); 353 354 const_iterator 355 find(const key_type& __k) const; 356 357 size_type 358 count(const key_type& __k) const; 359 360 std::pair<iterator, iterator> 361 equal_range(const key_type& __k); 362 363 std::pair<const_iterator, const_iterator> 364 equal_range(const key_type& __k) const; 365 366 private: 367 // Find and insert helper functions and types 368 _Node* 369 _M_find_node(_Node*, const key_type&, 370 typename _Hashtable::_Hash_code_type) const; 371 372 template<typename _Arg> 373 iterator 374 _M_insert_bucket(_Arg&&, size_type, 375 typename _Hashtable::_Hash_code_type); 376 377 template<typename _Arg> 378 std::pair<iterator, bool> 379 _M_insert(_Arg&&, std::true_type); 380 381 template<typename _Arg> 382 iterator 383 _M_insert(_Arg&&, std::false_type); 384 385 typedef typename std::conditional<__unique_keys, 386 std::pair<iterator, bool>, 387 iterator>::type 388 _Insert_Return_Type; 389 390 typedef typename std::conditional<__unique_keys, 391 std::_Select1st<_Insert_Return_Type>, 392 std::_Identity<_Insert_Return_Type> 393 >::type 394 _Insert_Conv_Type; 395 396 public: 397 // Insert and erase 398 _Insert_Return_Type 399 insert(const value_type& __v) 400 { return _M_insert(__v, std::integral_constant<bool, __unique_keys>()); } 401 402 iterator 403 insert(const_iterator, const value_type& __v) 404 { return _Insert_Conv_Type()(insert(__v)); } 405 406 _Insert_Return_Type 407 insert(value_type&& __v) 408 { return _M_insert(std::move(__v), 409 std::integral_constant<bool, __unique_keys>()); } 410 411 iterator 412 insert(const_iterator, value_type&& __v) 413 { return _Insert_Conv_Type()(insert(std::move(__v))); } 414 415 template<typename _Pair, typename = typename 416 std::enable_if<!__constant_iterators 417 && std::is_convertible<_Pair, 418 value_type>::value>::type> 419 _Insert_Return_Type 420 insert(_Pair&& __v) 421 { return _M_insert(std::forward<_Pair>(__v), 422 std::integral_constant<bool, __unique_keys>()); } 423 424 template<typename _Pair, typename = typename 425 std::enable_if<!__constant_iterators 426 && std::is_convertible<_Pair, 427 value_type>::value>::type> 428 iterator 429 insert(const_iterator, _Pair&& __v) 430 { return _Insert_Conv_Type()(insert(std::forward<_Pair>(__v))); } 431 432 template<typename _InputIterator> 433 void 434 insert(_InputIterator __first, _InputIterator __last); 435 436 void 437 insert(initializer_list<value_type> __l) 438 { this->insert(__l.begin(), __l.end()); } 439 440 iterator 441 erase(const_iterator); 442 443 // LWG 2059. 444 iterator 445 erase(iterator __it) 446 { return erase(const_iterator(__it)); } 447 448 size_type 449 erase(const key_type&); 450 451 iterator 452 erase(const_iterator, const_iterator); 453 454 void 455 clear(); 456 457 // Set number of buckets to be appropriate for container of n element. 458 void rehash(size_type __n); 459 460 // DR 1189. 461 // reserve, if present, comes from _Rehash_base. 462 463 private: 464 // Unconditionally change size of bucket array to n. 465 void _M_rehash(size_type __n); 466 }; 467 468 469 // Definitions of class template _Hashtable's out-of-line member functions. 470 template<typename _Key, typename _Value, 471 typename _Allocator, typename _ExtractKey, typename _Equal, 472 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 473 bool __chc, bool __cit, bool __uk> 474 template<typename... _Args> 475 typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 476 _H1, _H2, _Hash, _RehashPolicy, 477 __chc, __cit, __uk>::_Node* 478 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 479 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 480 _M_allocate_node(_Args&&... __args) 481 { 482 _Node* __n = _M_node_allocator.allocate(1); 483 __try 484 { 485 _M_node_allocator.construct(__n, std::forward<_Args>(__args)...); 486 __n->_M_next = 0; 487 return __n; 488 } 489 __catch(...) 490 { 491 _M_node_allocator.deallocate(__n, 1); 492 __throw_exception_again; 493 } 494 } 495 496 template<typename _Key, typename _Value, 497 typename _Allocator, typename _ExtractKey, typename _Equal, 498 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 499 bool __chc, bool __cit, bool __uk> 500 void 501 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 502 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 503 _M_deallocate_node(_Node* __n) 504 { 505 _M_node_allocator.destroy(__n); 506 _M_node_allocator.deallocate(__n, 1); 507 } 508 509 template<typename _Key, typename _Value, 510 typename _Allocator, typename _ExtractKey, typename _Equal, 511 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 512 bool __chc, bool __cit, bool __uk> 513 void 514 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 515 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 516 _M_deallocate_nodes(_Node** __array, size_type __n) 517 { 518 for (size_type __i = 0; __i < __n; ++__i) 519 { 520 _Node* __p = __array[__i]; 521 while (__p) 522 { 523 _Node* __tmp = __p; 524 __p = __p->_M_next; 525 _M_deallocate_node(__tmp); 526 } 527 __array[__i] = 0; 528 } 529 } 530 531 template<typename _Key, typename _Value, 532 typename _Allocator, typename _ExtractKey, typename _Equal, 533 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 534 bool __chc, bool __cit, bool __uk> 535 typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 536 _H1, _H2, _Hash, _RehashPolicy, 537 __chc, __cit, __uk>::_Node** 538 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 539 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 540 _M_allocate_buckets(size_type __n) 541 { 542 _Bucket_allocator_type __alloc(_M_node_allocator); 543 544 // We allocate one extra bucket to hold a sentinel, an arbitrary 545 // non-null pointer. Iterator increment relies on this. 546 _Node** __p = __alloc.allocate(__n + 1); 547 std::fill(__p, __p + __n, (_Node*) 0); 548 __p[__n] = reinterpret_cast<_Node*>(0x1000); 549 return __p; 550 } 551 552 template<typename _Key, typename _Value, 553 typename _Allocator, typename _ExtractKey, typename _Equal, 554 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 555 bool __chc, bool __cit, bool __uk> 556 void 557 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 558 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 559 _M_deallocate_buckets(_Node** __p, size_type __n) 560 { 561 _Bucket_allocator_type __alloc(_M_node_allocator); 562 __alloc.deallocate(__p, __n + 1); 563 } 564 565 template<typename _Key, typename _Value, 566 typename _Allocator, typename _ExtractKey, typename _Equal, 567 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 568 bool __chc, bool __cit, bool __uk> 569 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 570 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 571 _Hashtable(size_type __bucket_hint, 572 const _H1& __h1, const _H2& __h2, const _Hash& __h, 573 const _Equal& __eq, const _ExtractKey& __exk, 574 const allocator_type& __a) 575 : __detail::_Rehash_base<_RehashPolicy, _Hashtable>(), 576 __detail::_Hash_code_base<_Key, _Value, _ExtractKey, _Equal, 577 _H1, _H2, _Hash, __chc>(__exk, __eq, 578 __h1, __h2, __h), 579 __detail::_Map_base<_Key, _Value, _ExtractKey, __uk, _Hashtable>(), 580 _M_node_allocator(__a), 581 _M_bucket_count(0), 582 _M_element_count(0), 583 _M_rehash_policy() 584 { 585 _M_bucket_count = _M_rehash_policy._M_next_bkt(__bucket_hint); 586 _M_buckets = _M_allocate_buckets(_M_bucket_count); 587 _M_begin_bucket_index = _M_bucket_count; 588 } 589 590 template<typename _Key, typename _Value, 591 typename _Allocator, typename _ExtractKey, typename _Equal, 592 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 593 bool __chc, bool __cit, bool __uk> 594 template<typename _InputIterator> 595 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 596 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 597 _Hashtable(_InputIterator __f, _InputIterator __l, 598 size_type __bucket_hint, 599 const _H1& __h1, const _H2& __h2, const _Hash& __h, 600 const _Equal& __eq, const _ExtractKey& __exk, 601 const allocator_type& __a) 602 : __detail::_Rehash_base<_RehashPolicy, _Hashtable>(), 603 __detail::_Hash_code_base<_Key, _Value, _ExtractKey, _Equal, 604 _H1, _H2, _Hash, __chc>(__exk, __eq, 605 __h1, __h2, __h), 606 __detail::_Map_base<_Key, _Value, _ExtractKey, __uk, _Hashtable>(), 607 _M_node_allocator(__a), 608 _M_bucket_count(0), 609 _M_element_count(0), 610 _M_rehash_policy() 611 { 612 _M_bucket_count = std::max(_M_rehash_policy._M_next_bkt(__bucket_hint), 613 _M_rehash_policy. 614 _M_bkt_for_elements(__detail:: 615 __distance_fw(__f, 616 __l))); 617 _M_buckets = _M_allocate_buckets(_M_bucket_count); 618 _M_begin_bucket_index = _M_bucket_count; 619 __try 620 { 621 for (; __f != __l; ++__f) 622 this->insert(*__f); 623 } 624 __catch(...) 625 { 626 clear(); 627 _M_deallocate_buckets(_M_buckets, _M_bucket_count); 628 __throw_exception_again; 629 } 630 } 631 632 template<typename _Key, typename _Value, 633 typename _Allocator, typename _ExtractKey, typename _Equal, 634 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 635 bool __chc, bool __cit, bool __uk> 636 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 637 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 638 _Hashtable(const _Hashtable& __ht) 639 : __detail::_Rehash_base<_RehashPolicy, _Hashtable>(__ht), 640 __detail::_Hash_code_base<_Key, _Value, _ExtractKey, _Equal, 641 _H1, _H2, _Hash, __chc>(__ht), 642 __detail::_Map_base<_Key, _Value, _ExtractKey, __uk, _Hashtable>(__ht), 643 _M_node_allocator(__ht._M_node_allocator), 644 _M_bucket_count(__ht._M_bucket_count), 645 _M_begin_bucket_index(__ht._M_begin_bucket_index), 646 _M_element_count(__ht._M_element_count), 647 _M_rehash_policy(__ht._M_rehash_policy) 648 { 649 _M_buckets = _M_allocate_buckets(_M_bucket_count); 650 __try 651 { 652 for (size_type __i = 0; __i < __ht._M_bucket_count; ++__i) 653 { 654 _Node* __n = __ht._M_buckets[__i]; 655 _Node** __tail = _M_buckets + __i; 656 while (__n) 657 { 658 *__tail = _M_allocate_node(__n->_M_v); 659 this->_M_copy_code(*__tail, __n); 660 __tail = &((*__tail)->_M_next); 661 __n = __n->_M_next; 662 } 663 } 664 } 665 __catch(...) 666 { 667 clear(); 668 _M_deallocate_buckets(_M_buckets, _M_bucket_count); 669 __throw_exception_again; 670 } 671 } 672 673 template<typename _Key, typename _Value, 674 typename _Allocator, typename _ExtractKey, typename _Equal, 675 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 676 bool __chc, bool __cit, bool __uk> 677 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 678 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 679 _Hashtable(_Hashtable&& __ht) 680 : __detail::_Rehash_base<_RehashPolicy, _Hashtable>(__ht), 681 __detail::_Hash_code_base<_Key, _Value, _ExtractKey, _Equal, 682 _H1, _H2, _Hash, __chc>(__ht), 683 __detail::_Map_base<_Key, _Value, _ExtractKey, __uk, _Hashtable>(__ht), 684 _M_node_allocator(__ht._M_node_allocator), 685 _M_buckets(__ht._M_buckets), 686 _M_bucket_count(__ht._M_bucket_count), 687 _M_begin_bucket_index(__ht._M_begin_bucket_index), 688 _M_element_count(__ht._M_element_count), 689 _M_rehash_policy(__ht._M_rehash_policy) 690 { 691 __ht._M_rehash_policy = _RehashPolicy(); 692 __ht._M_bucket_count = __ht._M_rehash_policy._M_next_bkt(0); 693 __ht._M_buckets = __ht._M_allocate_buckets(__ht._M_bucket_count); 694 __ht._M_begin_bucket_index = __ht._M_bucket_count; 695 __ht._M_element_count = 0; 696 } 697 698 template<typename _Key, typename _Value, 699 typename _Allocator, typename _ExtractKey, typename _Equal, 700 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 701 bool __chc, bool __cit, bool __uk> 702 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 703 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 704 ~_Hashtable() 705 { 706 clear(); 707 _M_deallocate_buckets(_M_buckets, _M_bucket_count); 708 } 709 710 template<typename _Key, typename _Value, 711 typename _Allocator, typename _ExtractKey, typename _Equal, 712 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 713 bool __chc, bool __cit, bool __uk> 714 void 715 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 716 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 717 swap(_Hashtable& __x) 718 { 719 // The only base class with member variables is hash_code_base. We 720 // define _Hash_code_base::_M_swap because different specializations 721 // have different members. 722 __detail::_Hash_code_base<_Key, _Value, _ExtractKey, _Equal, 723 _H1, _H2, _Hash, __chc>::_M_swap(__x); 724 725 // _GLIBCXX_RESOLVE_LIB_DEFECTS 726 // 431. Swapping containers with unequal allocators. 727 std::__alloc_swap<_Node_allocator_type>::_S_do_it(_M_node_allocator, 728 __x._M_node_allocator); 729 730 std::swap(_M_rehash_policy, __x._M_rehash_policy); 731 std::swap(_M_buckets, __x._M_buckets); 732 std::swap(_M_bucket_count, __x._M_bucket_count); 733 std::swap(_M_begin_bucket_index, __x._M_begin_bucket_index); 734 std::swap(_M_element_count, __x._M_element_count); 735 } 736 737 template<typename _Key, typename _Value, 738 typename _Allocator, typename _ExtractKey, typename _Equal, 739 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 740 bool __chc, bool __cit, bool __uk> 741 void 742 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 743 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 744 __rehash_policy(const _RehashPolicy& __pol) 745 { 746 _M_rehash_policy = __pol; 747 size_type __n_bkt = __pol._M_bkt_for_elements(_M_element_count); 748 if (__n_bkt > _M_bucket_count) 749 _M_rehash(__n_bkt); 750 } 751 752 template<typename _Key, typename _Value, 753 typename _Allocator, typename _ExtractKey, typename _Equal, 754 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 755 bool __chc, bool __cit, bool __uk> 756 typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 757 _H1, _H2, _Hash, _RehashPolicy, 758 __chc, __cit, __uk>::iterator 759 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 760 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 761 find(const key_type& __k) 762 { 763 typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k); 764 std::size_t __n = this->_M_bucket_index(__k, __code, _M_bucket_count); 765 _Node* __p = _M_find_node(_M_buckets[__n], __k, __code); 766 return __p ? iterator(__p, _M_buckets + __n) : this->end(); 767 } 768 769 template<typename _Key, typename _Value, 770 typename _Allocator, typename _ExtractKey, typename _Equal, 771 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 772 bool __chc, bool __cit, bool __uk> 773 typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 774 _H1, _H2, _Hash, _RehashPolicy, 775 __chc, __cit, __uk>::const_iterator 776 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 777 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 778 find(const key_type& __k) const 779 { 780 typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k); 781 std::size_t __n = this->_M_bucket_index(__k, __code, _M_bucket_count); 782 _Node* __p = _M_find_node(_M_buckets[__n], __k, __code); 783 return __p ? const_iterator(__p, _M_buckets + __n) : this->end(); 784 } 785 786 template<typename _Key, typename _Value, 787 typename _Allocator, typename _ExtractKey, typename _Equal, 788 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 789 bool __chc, bool __cit, bool __uk> 790 typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 791 _H1, _H2, _Hash, _RehashPolicy, 792 __chc, __cit, __uk>::size_type 793 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 794 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 795 count(const key_type& __k) const 796 { 797 typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k); 798 std::size_t __n = this->_M_bucket_index(__k, __code, _M_bucket_count); 799 std::size_t __result = 0; 800 for (_Node* __p = _M_buckets[__n]; __p; __p = __p->_M_next) 801 if (this->_M_compare(__k, __code, __p)) 802 ++__result; 803 return __result; 804 } 805 806 template<typename _Key, typename _Value, 807 typename _Allocator, typename _ExtractKey, typename _Equal, 808 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 809 bool __chc, bool __cit, bool __uk> 810 std::pair<typename _Hashtable<_Key, _Value, _Allocator, 811 _ExtractKey, _Equal, _H1, 812 _H2, _Hash, _RehashPolicy, 813 __chc, __cit, __uk>::iterator, 814 typename _Hashtable<_Key, _Value, _Allocator, 815 _ExtractKey, _Equal, _H1, 816 _H2, _Hash, _RehashPolicy, 817 __chc, __cit, __uk>::iterator> 818 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 819 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 820 equal_range(const key_type& __k) 821 { 822 typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k); 823 std::size_t __n = this->_M_bucket_index(__k, __code, _M_bucket_count); 824 _Node** __head = _M_buckets + __n; 825 _Node* __p = _M_find_node(*__head, __k, __code); 826 827 if (__p) 828 { 829 _Node* __p1 = __p->_M_next; 830 for (; __p1; __p1 = __p1->_M_next) 831 if (!this->_M_compare(__k, __code, __p1)) 832 break; 833 834 iterator __first(__p, __head); 835 iterator __last(__p1, __head); 836 if (!__p1) 837 __last._M_incr_bucket(); 838 return std::make_pair(__first, __last); 839 } 840 else 841 return std::make_pair(this->end(), this->end()); 842 } 843 844 template<typename _Key, typename _Value, 845 typename _Allocator, typename _ExtractKey, typename _Equal, 846 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 847 bool __chc, bool __cit, bool __uk> 848 std::pair<typename _Hashtable<_Key, _Value, _Allocator, 849 _ExtractKey, _Equal, _H1, 850 _H2, _Hash, _RehashPolicy, 851 __chc, __cit, __uk>::const_iterator, 852 typename _Hashtable<_Key, _Value, _Allocator, 853 _ExtractKey, _Equal, _H1, 854 _H2, _Hash, _RehashPolicy, 855 __chc, __cit, __uk>::const_iterator> 856 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 857 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 858 equal_range(const key_type& __k) const 859 { 860 typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k); 861 std::size_t __n = this->_M_bucket_index(__k, __code, _M_bucket_count); 862 _Node** __head = _M_buckets + __n; 863 _Node* __p = _M_find_node(*__head, __k, __code); 864 865 if (__p) 866 { 867 _Node* __p1 = __p->_M_next; 868 for (; __p1; __p1 = __p1->_M_next) 869 if (!this->_M_compare(__k, __code, __p1)) 870 break; 871 872 const_iterator __first(__p, __head); 873 const_iterator __last(__p1, __head); 874 if (!__p1) 875 __last._M_incr_bucket(); 876 return std::make_pair(__first, __last); 877 } 878 else 879 return std::make_pair(this->end(), this->end()); 880 } 881 882 // Find the node whose key compares equal to k, beginning the search 883 // at p (usually the head of a bucket). Return nil if no node is found. 884 template<typename _Key, typename _Value, 885 typename _Allocator, typename _ExtractKey, typename _Equal, 886 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 887 bool __chc, bool __cit, bool __uk> 888 typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, 889 _Equal, _H1, _H2, _Hash, _RehashPolicy, 890 __chc, __cit, __uk>::_Node* 891 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 892 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 893 _M_find_node(_Node* __p, const key_type& __k, 894 typename _Hashtable::_Hash_code_type __code) const 895 { 896 for (; __p; __p = __p->_M_next) 897 if (this->_M_compare(__k, __code, __p)) 898 return __p; 899 return false; 900 } 901 902 // Insert v in bucket n (assumes no element with its key already present). 903 template<typename _Key, typename _Value, 904 typename _Allocator, typename _ExtractKey, typename _Equal, 905 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 906 bool __chc, bool __cit, bool __uk> 907 template<typename _Arg> 908 typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 909 _H1, _H2, _Hash, _RehashPolicy, 910 __chc, __cit, __uk>::iterator 911 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 912 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 913 _M_insert_bucket(_Arg&& __v, size_type __n, 914 typename _Hashtable::_Hash_code_type __code) 915 { 916 std::pair<bool, std::size_t> __do_rehash 917 = _M_rehash_policy._M_need_rehash(_M_bucket_count, 918 _M_element_count, 1); 919 920 if (__do_rehash.first) 921 { 922 const key_type& __k = this->_M_extract(__v); 923 __n = this->_M_bucket_index(__k, __code, __do_rehash.second); 924 } 925 926 // Allocate the new node before doing the rehash so that we don't 927 // do a rehash if the allocation throws. 928 _Node* __new_node = _M_allocate_node(std::forward<_Arg>(__v)); 929 930 __try 931 { 932 if (__do_rehash.first) 933 _M_rehash(__do_rehash.second); 934 935 __new_node->_M_next = _M_buckets[__n]; 936 this->_M_store_code(__new_node, __code); 937 _M_buckets[__n] = __new_node; 938 ++_M_element_count; 939 if (__n < _M_begin_bucket_index) 940 _M_begin_bucket_index = __n; 941 return iterator(__new_node, _M_buckets + __n); 942 } 943 __catch(...) 944 { 945 _M_deallocate_node(__new_node); 946 __throw_exception_again; 947 } 948 } 949 950 // Insert v if no element with its key is already present. 951 template<typename _Key, typename _Value, 952 typename _Allocator, typename _ExtractKey, typename _Equal, 953 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 954 bool __chc, bool __cit, bool __uk> 955 template<typename _Arg> 956 std::pair<typename _Hashtable<_Key, _Value, _Allocator, 957 _ExtractKey, _Equal, _H1, 958 _H2, _Hash, _RehashPolicy, 959 __chc, __cit, __uk>::iterator, bool> 960 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 961 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 962 _M_insert(_Arg&& __v, std::true_type) 963 { 964 const key_type& __k = this->_M_extract(__v); 965 typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k); 966 size_type __n = this->_M_bucket_index(__k, __code, _M_bucket_count); 967 968 if (_Node* __p = _M_find_node(_M_buckets[__n], __k, __code)) 969 return std::make_pair(iterator(__p, _M_buckets + __n), false); 970 return std::make_pair(_M_insert_bucket(std::forward<_Arg>(__v), 971 __n, __code), true); 972 } 973 974 // Insert v unconditionally. 975 template<typename _Key, typename _Value, 976 typename _Allocator, typename _ExtractKey, typename _Equal, 977 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 978 bool __chc, bool __cit, bool __uk> 979 template<typename _Arg> 980 typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 981 _H1, _H2, _Hash, _RehashPolicy, 982 __chc, __cit, __uk>::iterator 983 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 984 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 985 _M_insert(_Arg&& __v, std::false_type) 986 { 987 std::pair<bool, std::size_t> __do_rehash 988 = _M_rehash_policy._M_need_rehash(_M_bucket_count, 989 _M_element_count, 1); 990 if (__do_rehash.first) 991 _M_rehash(__do_rehash.second); 992 993 const key_type& __k = this->_M_extract(__v); 994 typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k); 995 size_type __n = this->_M_bucket_index(__k, __code, _M_bucket_count); 996 997 // First find the node, avoid leaking new_node if compare throws. 998 _Node* __prev = _M_find_node(_M_buckets[__n], __k, __code); 999 _Node* __new_node = _M_allocate_node(std::forward<_Arg>(__v)); 1000 1001 if (__prev) 1002 { 1003 __new_node->_M_next = __prev->_M_next; 1004 __prev->_M_next = __new_node; 1005 } 1006 else 1007 { 1008 __new_node->_M_next = _M_buckets[__n]; 1009 _M_buckets[__n] = __new_node; 1010 if (__n < _M_begin_bucket_index) 1011 _M_begin_bucket_index = __n; 1012 } 1013 this->_M_store_code(__new_node, __code); 1014 1015 ++_M_element_count; 1016 return iterator(__new_node, _M_buckets + __n); 1017 } 1018 1019 template<typename _Key, typename _Value, 1020 typename _Allocator, typename _ExtractKey, typename _Equal, 1021 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 1022 bool __chc, bool __cit, bool __uk> 1023 template<typename _InputIterator> 1024 void 1025 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 1026 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 1027 insert(_InputIterator __first, _InputIterator __last) 1028 { 1029 size_type __n_elt = __detail::__distance_fw(__first, __last); 1030 std::pair<bool, std::size_t> __do_rehash 1031 = _M_rehash_policy._M_need_rehash(_M_bucket_count, 1032 _M_element_count, __n_elt); 1033 if (__do_rehash.first) 1034 _M_rehash(__do_rehash.second); 1035 1036 for (; __first != __last; ++__first) 1037 this->insert(*__first); 1038 } 1039 1040 template<typename _Key, typename _Value, 1041 typename _Allocator, typename _ExtractKey, typename _Equal, 1042 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 1043 bool __chc, bool __cit, bool __uk> 1044 typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 1045 _H1, _H2, _Hash, _RehashPolicy, 1046 __chc, __cit, __uk>::iterator 1047 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 1048 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 1049 erase(const_iterator __it) 1050 { 1051 iterator __result(__it._M_cur_node, __it._M_cur_bucket); 1052 ++__result; 1053 1054 _Node* __cur = *__it._M_cur_bucket; 1055 if (__cur == __it._M_cur_node) 1056 { 1057 *__it._M_cur_bucket = __cur->_M_next; 1058 1059 // If _M_begin_bucket_index no longer indexes the first non-empty 1060 // bucket - its single node is being erased - update it. 1061 if (!_M_buckets[_M_begin_bucket_index]) 1062 _M_begin_bucket_index = __result._M_cur_bucket - _M_buckets; 1063 } 1064 else 1065 { 1066 _Node* __next = __cur->_M_next; 1067 while (__next != __it._M_cur_node) 1068 { 1069 __cur = __next; 1070 __next = __cur->_M_next; 1071 } 1072 __cur->_M_next = __next->_M_next; 1073 } 1074 1075 _M_deallocate_node(__it._M_cur_node); 1076 --_M_element_count; 1077 1078 return __result; 1079 } 1080 1081 template<typename _Key, typename _Value, 1082 typename _Allocator, typename _ExtractKey, typename _Equal, 1083 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 1084 bool __chc, bool __cit, bool __uk> 1085 typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 1086 _H1, _H2, _Hash, _RehashPolicy, 1087 __chc, __cit, __uk>::size_type 1088 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 1089 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 1090 erase(const key_type& __k) 1091 { 1092 typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k); 1093 std::size_t __n = this->_M_bucket_index(__k, __code, _M_bucket_count); 1094 size_type __result = 0; 1095 1096 _Node** __slot = _M_buckets + __n; 1097 while (*__slot && !this->_M_compare(__k, __code, *__slot)) 1098 __slot = &((*__slot)->_M_next); 1099 1100 _Node** __saved_slot = 0; 1101 while (*__slot && this->_M_compare(__k, __code, *__slot)) 1102 { 1103 // _GLIBCXX_RESOLVE_LIB_DEFECTS 1104 // 526. Is it undefined if a function in the standard changes 1105 // in parameters? 1106 if (std::__addressof(this->_M_extract((*__slot)->_M_v)) 1107 != std::__addressof(__k)) 1108 { 1109 _Node* __p = *__slot; 1110 *__slot = __p->_M_next; 1111 _M_deallocate_node(__p); 1112 --_M_element_count; 1113 ++__result; 1114 } 1115 else 1116 { 1117 __saved_slot = __slot; 1118 __slot = &((*__slot)->_M_next); 1119 } 1120 } 1121 1122 if (__saved_slot) 1123 { 1124 _Node* __p = *__saved_slot; 1125 *__saved_slot = __p->_M_next; 1126 _M_deallocate_node(__p); 1127 --_M_element_count; 1128 ++__result; 1129 } 1130 1131 // If the entire bucket indexed by _M_begin_bucket_index has been 1132 // erased look forward for the first non-empty bucket. 1133 if (!_M_buckets[_M_begin_bucket_index]) 1134 { 1135 if (!_M_element_count) 1136 _M_begin_bucket_index = _M_bucket_count; 1137 else 1138 { 1139 ++_M_begin_bucket_index; 1140 while (!_M_buckets[_M_begin_bucket_index]) 1141 ++_M_begin_bucket_index; 1142 } 1143 } 1144 1145 return __result; 1146 } 1147 1148 // ??? This could be optimized by taking advantage of the bucket 1149 // structure, but it's not clear that it's worth doing. It probably 1150 // wouldn't even be an optimization unless the load factor is large. 1151 template<typename _Key, typename _Value, 1152 typename _Allocator, typename _ExtractKey, typename _Equal, 1153 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 1154 bool __chc, bool __cit, bool __uk> 1155 typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 1156 _H1, _H2, _Hash, _RehashPolicy, 1157 __chc, __cit, __uk>::iterator 1158 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 1159 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 1160 erase(const_iterator __first, const_iterator __last) 1161 { 1162 while (__first != __last) 1163 __first = this->erase(__first); 1164 return iterator(__last._M_cur_node, __last._M_cur_bucket); 1165 } 1166 1167 template<typename _Key, typename _Value, 1168 typename _Allocator, typename _ExtractKey, typename _Equal, 1169 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 1170 bool __chc, bool __cit, bool __uk> 1171 void 1172 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 1173 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 1174 clear() 1175 { 1176 _M_deallocate_nodes(_M_buckets, _M_bucket_count); 1177 _M_element_count = 0; 1178 _M_begin_bucket_index = _M_bucket_count; 1179 } 1180 1181 template<typename _Key, typename _Value, 1182 typename _Allocator, typename _ExtractKey, typename _Equal, 1183 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 1184 bool __chc, bool __cit, bool __uk> 1185 void 1186 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 1187 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 1188 rehash(size_type __n) 1189 { 1190 _M_rehash(std::max(_M_rehash_policy._M_next_bkt(__n), 1191 _M_rehash_policy._M_bkt_for_elements(_M_element_count 1192 + 1))); 1193 } 1194 1195 template<typename _Key, typename _Value, 1196 typename _Allocator, typename _ExtractKey, typename _Equal, 1197 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 1198 bool __chc, bool __cit, bool __uk> 1199 void 1200 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 1201 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 1202 _M_rehash(size_type __n) 1203 { 1204 _Node** __new_array = _M_allocate_buckets(__n); 1205 __try 1206 { 1207 _M_begin_bucket_index = __n; 1208 for (size_type __i = 0; __i < _M_bucket_count; ++__i) 1209 while (_Node* __p = _M_buckets[__i]) 1210 { 1211 std::size_t __new_index = this->_M_bucket_index(__p, __n); 1212 _M_buckets[__i] = __p->_M_next; 1213 __p->_M_next = __new_array[__new_index]; 1214 __new_array[__new_index] = __p; 1215 if (__new_index < _M_begin_bucket_index) 1216 _M_begin_bucket_index = __new_index; 1217 } 1218 _M_deallocate_buckets(_M_buckets, _M_bucket_count); 1219 _M_bucket_count = __n; 1220 _M_buckets = __new_array; 1221 } 1222 __catch(...) 1223 { 1224 // A failure here means that a hash function threw an exception. 1225 // We can't restore the previous state without calling the hash 1226 // function again, so the only sensible recovery is to delete 1227 // everything. 1228 _M_deallocate_nodes(__new_array, __n); 1229 _M_deallocate_buckets(__new_array, __n); 1230 _M_deallocate_nodes(_M_buckets, _M_bucket_count); 1231 _M_element_count = 0; 1232 _M_begin_bucket_index = _M_bucket_count; 1233 __throw_exception_again; 1234 } 1235 } 1236 1237 _GLIBCXX_END_NAMESPACE_VERSION 1238 } // namespace std 1239 1240 #endif // _HASHTABLE_H 1241
