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