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