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 void swap(_Hashtable&); 229 230 // Basic container operations 231 iterator 232 begin() 233 { 234 iterator __i(_M_buckets); 235 if (!__i._M_cur_node) 236 __i._M_incr_bucket(); 237 return __i; 238 } 239 240 const_iterator 241 begin() const 242 { 243 const_iterator __i(_M_buckets); 244 if (!__i._M_cur_node) 245 __i._M_incr_bucket(); 246 return __i; 247 } 248 249 iterator 250 end() 251 { return iterator(_M_buckets + _M_bucket_count); } 252 253 const_iterator 254 end() const 255 { return const_iterator(_M_buckets + _M_bucket_count); } 256 257 #ifdef _GLIBCXX_INCLUDE_AS_CXX0X 258 const_iterator 259 cbegin() const 260 { 261 const_iterator __i(_M_buckets); 262 if (!__i._M_cur_node) 263 __i._M_incr_bucket(); 264 return __i; 265 } 266 267 const_iterator 268 cend() const 269 { return const_iterator(_M_buckets + _M_bucket_count); } 270 #endif 271 272 size_type 273 size() const 274 { return _M_element_count; } 275 276 bool 277 empty() const 278 { return size() == 0; } 279 280 allocator_type 281 get_allocator() const 282 { return allocator_type(_M_node_allocator); } 283 284 _Value_allocator_type 285 _M_get_Value_allocator() const 286 { return _Value_allocator_type(_M_node_allocator); } 287 288 size_type 289 max_size() const 290 { return _M_node_allocator.max_size(); } 291 292 // Observers 293 key_equal 294 key_eq() const 295 { return this->_M_eq; } 296 297 // hash_function, if present, comes from _Hash_code_base. 298 299 // Bucket operations 300 size_type 301 bucket_count() const 302 { return _M_bucket_count; } 303 304 size_type 305 max_bucket_count() const 306 { return max_size(); } 307 308 size_type 309 bucket_size(size_type __n) const 310 { return std::distance(begin(__n), end(__n)); } 311 312 size_type 313 bucket(const key_type& __k) const 314 { 315 return this->_M_bucket_index(__k, this->_M_hash_code(__k), 316 bucket_count()); 317 } 318 319 local_iterator 320 begin(size_type __n) 321 { return local_iterator(_M_buckets[__n]); } 322 323 local_iterator 324 end(size_type) 325 { return local_iterator(0); } 326 327 const_local_iterator 328 begin(size_type __n) const 329 { return const_local_iterator(_M_buckets[__n]); } 330 331 const_local_iterator 332 end(size_type) const 333 { return const_local_iterator(0); } 334 335 #ifdef _GLIBCXX_INCLUDE_AS_CXX0X 336 // DR 691. 337 const_local_iterator 338 cbegin(size_type __n) const 339 { return const_local_iterator(_M_buckets[__n]); } 340 341 const_local_iterator 342 cend(size_type) const 343 { return const_local_iterator(0); } 344 #endif 345 346 float 347 load_factor() const 348 { 349 return static_cast<float>(size()) / static_cast<float>(bucket_count()); 350 } 351 352 // max_load_factor, if present, comes from _Rehash_base. 353 354 // Generalization of max_load_factor. Extension, not found in TR1. Only 355 // useful if _RehashPolicy is something other than the default. 356 const _RehashPolicy& 357 __rehash_policy() const 358 { return _M_rehash_policy; } 359 360 void 361 __rehash_policy(const _RehashPolicy&); 362 363 // Lookup. 364 iterator 365 find(const key_type& __k); 366 367 const_iterator 368 find(const key_type& __k) const; 369 370 size_type 371 count(const key_type& __k) const; 372 373 std::pair<iterator, iterator> 374 equal_range(const key_type& __k); 375 376 std::pair<const_iterator, const_iterator> 377 equal_range(const key_type& __k) const; 378 379 private: // Find, insert and erase helper functions 380 // ??? This dispatching is a workaround for the fact that we don't 381 // have partial specialization of member templates; it would be 382 // better to just specialize insert on __unique_keys. There may be a 383 // cleaner workaround. 384 typedef typename __gnu_cxx::__conditional_type<__unique_keys, 385 std::pair<iterator, bool>, iterator>::__type 386 _Insert_Return_Type; 387 388 typedef typename __gnu_cxx::__conditional_type<__unique_keys, 389 std::_Select1st<_Insert_Return_Type>, 390 std::_Identity<_Insert_Return_Type> 391 >::__type 392 _Insert_Conv_Type; 393 394 _Node* 395 _M_find_node(_Node*, const key_type&, 396 typename _Hashtable::_Hash_code_type) const; 397 398 iterator 399 _M_insert_bucket(const value_type&, size_type, 400 typename _Hashtable::_Hash_code_type); 401 402 std::pair<iterator, bool> 403 _M_insert(const value_type&, std::_GLIBCXX_TR1 true_type); 404 405 iterator 406 _M_insert(const value_type&, std::_GLIBCXX_TR1 false_type); 407 408 void 409 _M_erase_node(_Node*, _Node**); 410 411 public: 412 // Insert and erase 413 _Insert_Return_Type 414 insert(const value_type& __v) 415 { return _M_insert(__v, std::_GLIBCXX_TR1 integral_constant<bool, 416 __unique_keys>()); } 417 418 iterator 419 insert(iterator, const value_type& __v) 420 { return iterator(_Insert_Conv_Type()(this->insert(__v))); } 421 422 const_iterator 423 insert(const_iterator, const value_type& __v) 424 { return const_iterator(_Insert_Conv_Type()(this->insert(__v))); } 425 426 template<typename _InputIterator> 427 void 428 insert(_InputIterator __first, _InputIterator __last); 429 430 #ifdef _GLIBCXX_INCLUDE_AS_CXX0X 431 void 432 insert(initializer_list<value_type> __l) 433 { this->insert(__l.begin(), __l.end()); } 434 #endif 435 436 iterator 437 erase(iterator); 438 439 const_iterator 440 erase(const_iterator); 441 442 size_type 443 erase(const key_type&); 444 445 iterator 446 erase(iterator, iterator); 447 448 const_iterator 449 erase(const_iterator, const_iterator); 450 451 void 452 clear(); 453 454 // Set number of buckets to be appropriate for container of n element. 455 void rehash(size_type __n); 456 457 private: 458 // Unconditionally change size of bucket array to n. 459 void _M_rehash(size_type __n); 460 }; 461 462 463 // Definitions of class template _Hashtable's out-of-line member functions. 464 template<typename _Key, typename _Value, 465 typename _Allocator, typename _ExtractKey, typename _Equal, 466 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 467 bool __chc, bool __cit, bool __uk> 468 typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 469 _H1, _H2, _Hash, _RehashPolicy, 470 __chc, __cit, __uk>::_Node* 471 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 472 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 473 _M_allocate_node(const value_type& __v) 474 { 475 _Node* __n = _M_node_allocator.allocate(1); 476 __try 477 { 478 #ifdef _GLIBCXX_INCLUDE_AS_CXX0X 479 _M_node_allocator.construct(__n, __v); 480 #else 481 _M_get_Value_allocator().construct(&__n->_M_v, __v); 482 #endif 483 __n->_M_next = 0; 484 return __n; 485 } 486 __catch(...) 487 { 488 _M_node_allocator.deallocate(__n, 1); 489 __throw_exception_again; 490 } 491 } 492 493 template<typename _Key, typename _Value, 494 typename _Allocator, typename _ExtractKey, typename _Equal, 495 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 496 bool __chc, bool __cit, bool __uk> 497 void 498 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 499 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 500 _M_deallocate_node(_Node* __n) 501 { 502 #ifdef _GLIBCXX_INCLUDE_AS_CXX0X 503 _M_node_allocator.destroy(__n); 504 #else 505 _M_get_Value_allocator().destroy(&__n->_M_v); 506 #endif 507 _M_node_allocator.deallocate(__n, 1); 508 } 509 510 template<typename _Key, typename _Value, 511 typename _Allocator, typename _ExtractKey, typename _Equal, 512 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 513 bool __chc, bool __cit, bool __uk> 514 void 515 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 516 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 517 _M_deallocate_nodes(_Node** __array, size_type __n) 518 { 519 for (size_type __i = 0; __i < __n; ++__i) 520 { 521 _Node* __p = __array[__i]; 522 while (__p) 523 { 524 _Node* __tmp = __p; 525 __p = __p->_M_next; 526 _M_deallocate_node(__tmp); 527 } 528 __array[__i] = 0; 529 } 530 } 531 532 template<typename _Key, typename _Value, 533 typename _Allocator, typename _ExtractKey, typename _Equal, 534 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 535 bool __chc, bool __cit, bool __uk> 536 typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 537 _H1, _H2, _Hash, _RehashPolicy, 538 __chc, __cit, __uk>::_Node** 539 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 540 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 541 _M_allocate_buckets(size_type __n) 542 { 543 _Bucket_allocator_type __alloc(_M_node_allocator); 544 545 // We allocate one extra bucket to hold a sentinel, an arbitrary 546 // non-null pointer. Iterator increment relies on this. 547 _Node** __p = __alloc.allocate(__n + 1); 548 std::fill(__p, __p + __n, (_Node*) 0); 549 __p[__n] = reinterpret_cast<_Node*>(0x1000); 550 return __p; 551 } 552 553 template<typename _Key, typename _Value, 554 typename _Allocator, typename _ExtractKey, typename _Equal, 555 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 556 bool __chc, bool __cit, bool __uk> 557 void 558 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 559 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 560 _M_deallocate_buckets(_Node** __p, size_type __n) 561 { 562 _Bucket_allocator_type __alloc(_M_node_allocator); 563 __alloc.deallocate(__p, __n + 1); 564 } 565 566 template<typename _Key, typename _Value, 567 typename _Allocator, typename _ExtractKey, typename _Equal, 568 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 569 bool __chc, bool __cit, bool __uk> 570 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 571 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 572 _Hashtable(size_type __bucket_hint, 573 const _H1& __h1, const _H2& __h2, const _Hash& __h, 574 const _Equal& __eq, const _ExtractKey& __exk, 575 const allocator_type& __a) 576 : __detail::_Rehash_base<_RehashPolicy, _Hashtable>(), 577 __detail::_Hash_code_base<_Key, _Value, _ExtractKey, _Equal, 578 _H1, _H2, _Hash, __chc>(__exk, __eq, 579 __h1, __h2, __h), 580 __detail::_Map_base<_Key, _Value, _ExtractKey, __uk, _Hashtable>(), 581 _M_node_allocator(__a), 582 _M_bucket_count(0), 583 _M_element_count(0), 584 _M_rehash_policy() 585 { 586 _M_bucket_count = _M_rehash_policy._M_next_bkt(__bucket_hint); 587 _M_buckets = _M_allocate_buckets(_M_bucket_count); 588 } 589 590 template<typename _Key, typename _Value, 591 typename _Allocator, typename _ExtractKey, typename _Equal, 592 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 593 bool __chc, bool __cit, bool __uk> 594 template<typename _InputIterator> 595 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 596 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 597 _Hashtable(_InputIterator __f, _InputIterator __l, 598 size_type __bucket_hint, 599 const _H1& __h1, const _H2& __h2, const _Hash& __h, 600 const _Equal& __eq, const _ExtractKey& __exk, 601 const allocator_type& __a) 602 : __detail::_Rehash_base<_RehashPolicy, _Hashtable>(), 603 __detail::_Hash_code_base<_Key, _Value, _ExtractKey, _Equal, 604 _H1, _H2, _Hash, __chc>(__exk, __eq, 605 __h1, __h2, __h), 606 __detail::_Map_base<_Key, _Value, _ExtractKey, __uk, _Hashtable>(), 607 _M_node_allocator(__a), 608 _M_bucket_count(0), 609 _M_element_count(0), 610 _M_rehash_policy() 611 { 612 _M_bucket_count = std::max(_M_rehash_policy._M_next_bkt(__bucket_hint), 613 _M_rehash_policy. 614 _M_bkt_for_elements(__detail:: 615 __distance_fw(__f, 616 __l))); 617 _M_buckets = _M_allocate_buckets(_M_bucket_count); 618 __try 619 { 620 for (; __f != __l; ++__f) 621 this->insert(*__f); 622 } 623 __catch(...) 624 { 625 clear(); 626 _M_deallocate_buckets(_M_buckets, _M_bucket_count); 627 __throw_exception_again; 628 } 629 } 630 631 template<typename _Key, typename _Value, 632 typename _Allocator, typename _ExtractKey, typename _Equal, 633 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 634 bool __chc, bool __cit, bool __uk> 635 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 636 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 637 _Hashtable(const _Hashtable& __ht) 638 : __detail::_Rehash_base<_RehashPolicy, _Hashtable>(__ht), 639 __detail::_Hash_code_base<_Key, _Value, _ExtractKey, _Equal, 640 _H1, _H2, _Hash, __chc>(__ht), 641 __detail::_Map_base<_Key, _Value, _ExtractKey, __uk, _Hashtable>(__ht), 642 _M_node_allocator(__ht._M_node_allocator), 643 _M_bucket_count(__ht._M_bucket_count), 644 _M_element_count(__ht._M_element_count), 645 _M_rehash_policy(__ht._M_rehash_policy) 646 { 647 _M_buckets = _M_allocate_buckets(_M_bucket_count); 648 __try 649 { 650 for (size_type __i = 0; __i < __ht._M_bucket_count; ++__i) 651 { 652 _Node* __n = __ht._M_buckets[__i]; 653 _Node** __tail = _M_buckets + __i; 654 while (__n) 655 { 656 *__tail = _M_allocate_node(__n->_M_v); 657 this->_M_copy_code(*__tail, __n); 658 __tail = &((*__tail)->_M_next); 659 __n = __n->_M_next; 660 } 661 } 662 } 663 __catch(...) 664 { 665 clear(); 666 _M_deallocate_buckets(_M_buckets, _M_bucket_count); 667 __throw_exception_again; 668 } 669 } 670 671 #ifdef _GLIBCXX_INCLUDE_AS_CXX0X 672 template<typename _Key, typename _Value, 673 typename _Allocator, typename _ExtractKey, typename _Equal, 674 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 675 bool __chc, bool __cit, bool __uk> 676 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 677 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 678 _Hashtable(_Hashtable&& __ht) 679 : __detail::_Rehash_base<_RehashPolicy, _Hashtable>(__ht), 680 __detail::_Hash_code_base<_Key, _Value, _ExtractKey, _Equal, 681 _H1, _H2, _Hash, __chc>(__ht), 682 __detail::_Map_base<_Key, _Value, _ExtractKey, __uk, _Hashtable>(__ht), 683 _M_node_allocator(__ht._M_node_allocator), 684 _M_bucket_count(__ht._M_bucket_count), 685 _M_element_count(__ht._M_element_count), 686 _M_rehash_policy(__ht._M_rehash_policy), 687 _M_buckets(__ht._M_buckets) 688 { 689 size_type __n_bkt = __ht._M_rehash_policy._M_next_bkt(0); 690 __ht._M_buckets = __ht._M_allocate_buckets(__n_bkt); 691 __ht._M_bucket_count = __n_bkt; 692 __ht._M_element_count = 0; 693 __ht._M_rehash_policy = _RehashPolicy(); 694 } 695 #endif 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 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 702 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>& 703 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 704 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 705 operator=(const _Hashtable& __ht) 706 { 707 _Hashtable __tmp(__ht); 708 this->swap(__tmp); 709 return *this; 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 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 717 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 718 ~_Hashtable() 719 { 720 clear(); 721 _M_deallocate_buckets(_M_buckets, _M_bucket_count); 722 } 723 724 template<typename _Key, typename _Value, 725 typename _Allocator, typename _ExtractKey, typename _Equal, 726 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 727 bool __chc, bool __cit, bool __uk> 728 void 729 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 730 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 731 swap(_Hashtable& __x) 732 { 733 // The only base class with member variables is hash_code_base. We 734 // define _Hash_code_base::_M_swap because different specializations 735 // have different members. 736 __detail::_Hash_code_base<_Key, _Value, _ExtractKey, _Equal, 737 _H1, _H2, _Hash, __chc>::_M_swap(__x); 738 739 // _GLIBCXX_RESOLVE_LIB_DEFECTS 740 // 431. Swapping containers with unequal allocators. 741 std::__alloc_swap<_Node_allocator_type>::_S_do_it(_M_node_allocator, 742 __x._M_node_allocator); 743 744 std::swap(_M_rehash_policy, __x._M_rehash_policy); 745 std::swap(_M_buckets, __x._M_buckets); 746 std::swap(_M_bucket_count, __x._M_bucket_count); 747 std::swap(_M_element_count, __x._M_element_count); 748 } 749 750 template<typename _Key, typename _Value, 751 typename _Allocator, typename _ExtractKey, typename _Equal, 752 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 753 bool __chc, bool __cit, bool __uk> 754 void 755 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 756 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 757 __rehash_policy(const _RehashPolicy& __pol) 758 { 759 _M_rehash_policy = __pol; 760 size_type __n_bkt = __pol._M_bkt_for_elements(_M_element_count); 761 if (__n_bkt > _M_bucket_count) 762 _M_rehash(__n_bkt); 763 } 764 765 template<typename _Key, typename _Value, 766 typename _Allocator, typename _ExtractKey, typename _Equal, 767 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 768 bool __chc, bool __cit, bool __uk> 769 typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 770 _H1, _H2, _Hash, _RehashPolicy, 771 __chc, __cit, __uk>::iterator 772 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 773 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 774 find(const key_type& __k) 775 { 776 typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k); 777 std::size_t __n = this->_M_bucket_index(__k, __code, _M_bucket_count); 778 _Node* __p = _M_find_node(_M_buckets[__n], __k, __code); 779 return __p ? iterator(__p, _M_buckets + __n) : this->end(); 780 } 781 782 template<typename _Key, typename _Value, 783 typename _Allocator, typename _ExtractKey, typename _Equal, 784 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 785 bool __chc, bool __cit, bool __uk> 786 typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 787 _H1, _H2, _Hash, _RehashPolicy, 788 __chc, __cit, __uk>::const_iterator 789 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 790 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 791 find(const key_type& __k) const 792 { 793 typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k); 794 std::size_t __n = this->_M_bucket_index(__k, __code, _M_bucket_count); 795 _Node* __p = _M_find_node(_M_buckets[__n], __k, __code); 796 return __p ? const_iterator(__p, _M_buckets + __n) : this->end(); 797 } 798 799 template<typename _Key, typename _Value, 800 typename _Allocator, typename _ExtractKey, typename _Equal, 801 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 802 bool __chc, bool __cit, bool __uk> 803 typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 804 _H1, _H2, _Hash, _RehashPolicy, 805 __chc, __cit, __uk>::size_type 806 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 807 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 808 count(const key_type& __k) const 809 { 810 typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k); 811 std::size_t __n = this->_M_bucket_index(__k, __code, _M_bucket_count); 812 std::size_t __result = 0; 813 for (_Node* __p = _M_buckets[__n]; __p; __p = __p->_M_next) 814 if (this->_M_compare(__k, __code, __p)) 815 ++__result; 816 return __result; 817 } 818 819 template<typename _Key, typename _Value, 820 typename _Allocator, typename _ExtractKey, typename _Equal, 821 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 822 bool __chc, bool __cit, bool __uk> 823 std::pair<typename _Hashtable<_Key, _Value, _Allocator, 824 _ExtractKey, _Equal, _H1, 825 _H2, _Hash, _RehashPolicy, 826 __chc, __cit, __uk>::iterator, 827 typename _Hashtable<_Key, _Value, _Allocator, 828 _ExtractKey, _Equal, _H1, 829 _H2, _Hash, _RehashPolicy, 830 __chc, __cit, __uk>::iterator> 831 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 832 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 833 equal_range(const key_type& __k) 834 { 835 typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k); 836 std::size_t __n = this->_M_bucket_index(__k, __code, _M_bucket_count); 837 _Node** __head = _M_buckets + __n; 838 _Node* __p = _M_find_node(*__head, __k, __code); 839 840 if (__p) 841 { 842 _Node* __p1 = __p->_M_next; 843 for (; __p1; __p1 = __p1->_M_next) 844 if (!this->_M_compare(__k, __code, __p1)) 845 break; 846 847 iterator __first(__p, __head); 848 iterator __last(__p1, __head); 849 if (!__p1) 850 __last._M_incr_bucket(); 851 return std::make_pair(__first, __last); 852 } 853 else 854 return std::make_pair(this->end(), this->end()); 855 } 856 857 template<typename _Key, typename _Value, 858 typename _Allocator, typename _ExtractKey, typename _Equal, 859 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 860 bool __chc, bool __cit, bool __uk> 861 std::pair<typename _Hashtable<_Key, _Value, _Allocator, 862 _ExtractKey, _Equal, _H1, 863 _H2, _Hash, _RehashPolicy, 864 __chc, __cit, __uk>::const_iterator, 865 typename _Hashtable<_Key, _Value, _Allocator, 866 _ExtractKey, _Equal, _H1, 867 _H2, _Hash, _RehashPolicy, 868 __chc, __cit, __uk>::const_iterator> 869 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 870 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 871 equal_range(const key_type& __k) const 872 { 873 typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k); 874 std::size_t __n = this->_M_bucket_index(__k, __code, _M_bucket_count); 875 _Node** __head = _M_buckets + __n; 876 _Node* __p = _M_find_node(*__head, __k, __code); 877 878 if (__p) 879 { 880 _Node* __p1 = __p->_M_next; 881 for (; __p1; __p1 = __p1->_M_next) 882 if (!this->_M_compare(__k, __code, __p1)) 883 break; 884 885 const_iterator __first(__p, __head); 886 const_iterator __last(__p1, __head); 887 if (!__p1) 888 __last._M_incr_bucket(); 889 return std::make_pair(__first, __last); 890 } 891 else 892 return std::make_pair(this->end(), this->end()); 893 } 894 895 // Find the node whose key compares equal to k, beginning the search 896 // at p (usually the head of a bucket). Return nil if no node is found. 897 template<typename _Key, typename _Value, 898 typename _Allocator, typename _ExtractKey, typename _Equal, 899 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 900 bool __chc, bool __cit, bool __uk> 901 typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, 902 _Equal, _H1, _H2, _Hash, _RehashPolicy, 903 __chc, __cit, __uk>::_Node* 904 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 905 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 906 _M_find_node(_Node* __p, const key_type& __k, 907 typename _Hashtable::_Hash_code_type __code) const 908 { 909 for (; __p; __p = __p->_M_next) 910 if (this->_M_compare(__k, __code, __p)) 911 return __p; 912 return false; 913 } 914 915 // Insert v in bucket n (assumes no element with its key already present). 916 template<typename _Key, typename _Value, 917 typename _Allocator, typename _ExtractKey, typename _Equal, 918 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 919 bool __chc, bool __cit, bool __uk> 920 typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 921 _H1, _H2, _Hash, _RehashPolicy, 922 __chc, __cit, __uk>::iterator 923 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 924 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 925 _M_insert_bucket(const value_type& __v, size_type __n, 926 typename _Hashtable::_Hash_code_type __code) 927 { 928 std::pair<bool, std::size_t> __do_rehash 929 = _M_rehash_policy._M_need_rehash(_M_bucket_count, 930 _M_element_count, 1); 931 932 // Allocate the new node before doing the rehash so that we don't 933 // do a rehash if the allocation throws. 934 _Node* __new_node = _M_allocate_node(__v); 935 936 __try 937 { 938 if (__do_rehash.first) 939 { 940 const key_type& __k = this->_M_extract(__v); 941 __n = this->_M_bucket_index(__k, __code, __do_rehash.second); 942 _M_rehash(__do_rehash.second); 943 } 944 945 __new_node->_M_next = _M_buckets[__n]; 946 this->_M_store_code(__new_node, __code); 947 _M_buckets[__n] = __new_node; 948 ++_M_element_count; 949 return iterator(__new_node, _M_buckets + __n); 950 } 951 __catch(...) 952 { 953 _M_deallocate_node(__new_node); 954 __throw_exception_again; 955 } 956 } 957 958 // Insert v if no element with its key is already present. 959 template<typename _Key, typename _Value, 960 typename _Allocator, typename _ExtractKey, typename _Equal, 961 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 962 bool __chc, bool __cit, bool __uk> 963 std::pair<typename _Hashtable<_Key, _Value, _Allocator, 964 _ExtractKey, _Equal, _H1, 965 _H2, _Hash, _RehashPolicy, 966 __chc, __cit, __uk>::iterator, bool> 967 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 968 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 969 _M_insert(const value_type& __v, std::_GLIBCXX_TR1 true_type) 970 { 971 const key_type& __k = this->_M_extract(__v); 972 typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k); 973 size_type __n = this->_M_bucket_index(__k, __code, _M_bucket_count); 974 975 if (_Node* __p = _M_find_node(_M_buckets[__n], __k, __code)) 976 return std::make_pair(iterator(__p, _M_buckets + __n), false); 977 return std::make_pair(_M_insert_bucket(__v, __n, __code), true); 978 } 979 980 // Insert v unconditionally. 981 template<typename _Key, typename _Value, 982 typename _Allocator, typename _ExtractKey, typename _Equal, 983 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 984 bool __chc, bool __cit, bool __uk> 985 typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 986 _H1, _H2, _Hash, _RehashPolicy, 987 __chc, __cit, __uk>::iterator 988 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 989 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 990 _M_insert(const value_type& __v, std::_GLIBCXX_TR1 false_type) 991 { 992 std::pair<bool, std::size_t> __do_rehash 993 = _M_rehash_policy._M_need_rehash(_M_bucket_count, 994 _M_element_count, 1); 995 if (__do_rehash.first) 996 _M_rehash(__do_rehash.second); 997 998 const key_type& __k = this->_M_extract(__v); 999 typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k); 1000 size_type __n = this->_M_bucket_index(__k, __code, _M_bucket_count); 1001 1002 // First find the node, avoid leaking new_node if compare throws. 1003 _Node* __prev = _M_find_node(_M_buckets[__n], __k, __code); 1004 _Node* __new_node = _M_allocate_node(__v); 1005 1006 if (__prev) 1007 { 1008 __new_node->_M_next = __prev->_M_next; 1009 __prev->_M_next = __new_node; 1010 } 1011 else 1012 { 1013 __new_node->_M_next = _M_buckets[__n]; 1014 _M_buckets[__n] = __new_node; 1015 } 1016 this->_M_store_code(__new_node, __code); 1017 1018 ++_M_element_count; 1019 return iterator(__new_node, _M_buckets + __n); 1020 } 1021 1022 // For erase(iterator) and erase(const_iterator). 1023 template<typename _Key, typename _Value, 1024 typename _Allocator, typename _ExtractKey, typename _Equal, 1025 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 1026 bool __chc, bool __cit, bool __uk> 1027 void 1028 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 1029 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 1030 _M_erase_node(_Node* __p, _Node** __b) 1031 { 1032 _Node* __cur = *__b; 1033 if (__cur == __p) 1034 *__b = __cur->_M_next; 1035 else 1036 { 1037 _Node* __next = __cur->_M_next; 1038 while (__next != __p) 1039 { 1040 __cur = __next; 1041 __next = __cur->_M_next; 1042 } 1043 __cur->_M_next = __next->_M_next; 1044 } 1045 1046 _M_deallocate_node(__p); 1047 --_M_element_count; 1048 } 1049 1050 template<typename _Key, typename _Value, 1051 typename _Allocator, typename _ExtractKey, typename _Equal, 1052 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 1053 bool __chc, bool __cit, bool __uk> 1054 template<typename _InputIterator> 1055 void 1056 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 1057 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 1058 insert(_InputIterator __first, _InputIterator __last) 1059 { 1060 size_type __n_elt = __detail::__distance_fw(__first, __last); 1061 std::pair<bool, std::size_t> __do_rehash 1062 = _M_rehash_policy._M_need_rehash(_M_bucket_count, 1063 _M_element_count, __n_elt); 1064 if (__do_rehash.first) 1065 _M_rehash(__do_rehash.second); 1066 1067 for (; __first != __last; ++__first) 1068 this->insert(*__first); 1069 } 1070 1071 template<typename _Key, typename _Value, 1072 typename _Allocator, typename _ExtractKey, typename _Equal, 1073 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 1074 bool __chc, bool __cit, bool __uk> 1075 typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 1076 _H1, _H2, _Hash, _RehashPolicy, 1077 __chc, __cit, __uk>::iterator 1078 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 1079 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 1080 erase(iterator __it) 1081 { 1082 iterator __result = __it; 1083 ++__result; 1084 _M_erase_node(__it._M_cur_node, __it._M_cur_bucket); 1085 return __result; 1086 } 1087 1088 template<typename _Key, typename _Value, 1089 typename _Allocator, typename _ExtractKey, typename _Equal, 1090 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 1091 bool __chc, bool __cit, bool __uk> 1092 typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 1093 _H1, _H2, _Hash, _RehashPolicy, 1094 __chc, __cit, __uk>::const_iterator 1095 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 1096 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 1097 erase(const_iterator __it) 1098 { 1099 const_iterator __result = __it; 1100 ++__result; 1101 _M_erase_node(__it._M_cur_node, __it._M_cur_bucket); 1102 return __result; 1103 } 1104 1105 template<typename _Key, typename _Value, 1106 typename _Allocator, typename _ExtractKey, typename _Equal, 1107 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 1108 bool __chc, bool __cit, bool __uk> 1109 typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 1110 _H1, _H2, _Hash, _RehashPolicy, 1111 __chc, __cit, __uk>::size_type 1112 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 1113 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 1114 erase(const key_type& __k) 1115 { 1116 typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k); 1117 std::size_t __n = this->_M_bucket_index(__k, __code, _M_bucket_count); 1118 size_type __result = 0; 1119 1120 _Node** __slot = _M_buckets + __n; 1121 while (*__slot && !this->_M_compare(__k, __code, *__slot)) 1122 __slot = &((*__slot)->_M_next); 1123 1124 _Node** __saved_slot = 0; 1125 while (*__slot && this->_M_compare(__k, __code, *__slot)) 1126 { 1127 // _GLIBCXX_RESOLVE_LIB_DEFECTS 1128 // 526. Is it undefined if a function in the standard changes 1129 // in parameters? 1130 if (&this->_M_extract((*__slot)->_M_v) != &__k) 1131 { 1132 _Node* __p = *__slot; 1133 *__slot = __p->_M_next; 1134 _M_deallocate_node(__p); 1135 --_M_element_count; 1136 ++__result; 1137 } 1138 else 1139 { 1140 __saved_slot = __slot; 1141 __slot = &((*__slot)->_M_next); 1142 } 1143 } 1144 1145 if (__saved_slot) 1146 { 1147 _Node* __p = *__saved_slot; 1148 *__saved_slot = __p->_M_next; 1149 _M_deallocate_node(__p); 1150 --_M_element_count; 1151 ++__result; 1152 } 1153 1154 return __result; 1155 } 1156 1157 // ??? This could be optimized by taking advantage of the bucket 1158 // structure, but it's not clear that it's worth doing. It probably 1159 // wouldn't even be an optimization unless the load factor is large. 1160 template<typename _Key, typename _Value, 1161 typename _Allocator, typename _ExtractKey, typename _Equal, 1162 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 1163 bool __chc, bool __cit, bool __uk> 1164 typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 1165 _H1, _H2, _Hash, _RehashPolicy, 1166 __chc, __cit, __uk>::iterator 1167 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 1168 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 1169 erase(iterator __first, iterator __last) 1170 { 1171 while (__first != __last) 1172 __first = this->erase(__first); 1173 return __last; 1174 } 1175 1176 template<typename _Key, typename _Value, 1177 typename _Allocator, typename _ExtractKey, typename _Equal, 1178 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 1179 bool __chc, bool __cit, bool __uk> 1180 typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 1181 _H1, _H2, _Hash, _RehashPolicy, 1182 __chc, __cit, __uk>::const_iterator 1183 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 1184 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 1185 erase(const_iterator __first, const_iterator __last) 1186 { 1187 while (__first != __last) 1188 __first = this->erase(__first); 1189 return __last; 1190 } 1191 1192 template<typename _Key, typename _Value, 1193 typename _Allocator, typename _ExtractKey, typename _Equal, 1194 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 1195 bool __chc, bool __cit, bool __uk> 1196 void 1197 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 1198 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 1199 clear() 1200 { 1201 _M_deallocate_nodes(_M_buckets, _M_bucket_count); 1202 _M_element_count = 0; 1203 } 1204 1205 template<typename _Key, typename _Value, 1206 typename _Allocator, typename _ExtractKey, typename _Equal, 1207 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 1208 bool __chc, bool __cit, bool __uk> 1209 void 1210 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 1211 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 1212 rehash(size_type __n) 1213 { 1214 _M_rehash(std::max(_M_rehash_policy._M_next_bkt(__n), 1215 _M_rehash_policy._M_bkt_for_elements(_M_element_count 1216 + 1))); 1217 } 1218 1219 template<typename _Key, typename _Value, 1220 typename _Allocator, typename _ExtractKey, typename _Equal, 1221 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, 1222 bool __chc, bool __cit, bool __uk> 1223 void 1224 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, 1225 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: 1226 _M_rehash(size_type __n) 1227 { 1228 _Node** __new_array = _M_allocate_buckets(__n); 1229 __try 1230 { 1231 for (size_type __i = 0; __i < _M_bucket_count; ++__i) 1232 while (_Node* __p = _M_buckets[__i]) 1233 { 1234 std::size_t __new_index = this->_M_bucket_index(__p, __n); 1235 _M_buckets[__i] = __p->_M_next; 1236 __p->_M_next = __new_array[__new_index]; 1237 __new_array[__new_index] = __p; 1238 } 1239 _M_deallocate_buckets(_M_buckets, _M_bucket_count); 1240 _M_bucket_count = __n; 1241 _M_buckets = __new_array; 1242 } 1243 __catch(...) 1244 { 1245 // A failure here means that a hash function threw an exception. 1246 // We can't restore the previous state without calling the hash 1247 // function again, so the only sensible recovery is to delete 1248 // everything. 1249 _M_deallocate_nodes(__new_array, __n); 1250 _M_deallocate_buckets(__new_array, __n); 1251 _M_deallocate_nodes(_M_buckets, _M_bucket_count); 1252 _M_element_count = 0; 1253 __throw_exception_again; 1254 } 1255 } 1256 1257 _GLIBCXX_END_NAMESPACE_TR1 1258 } 1259
