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