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