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