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