1 // Hashtable implementation used by containers -*- C++ -*- 2 3 // Copyright (C) 2001-2018 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 /* 26 * Copyright (c) 1996,1997 27 * Silicon Graphics Computer Systems, Inc. 28 * 29 * Permission to use, copy, modify, distribute and sell this software 30 * and its documentation for any purpose is hereby granted without fee, 31 * provided that the above copyright notice appear in all copies and 32 * that both that copyright notice and this permission notice appear 33 * in supporting documentation. Silicon Graphics makes no 34 * representations about the suitability of this software for any 35 * purpose. It is provided "as is" without express or implied warranty. 36 * 37 * 38 * Copyright (c) 1994 39 * Hewlett-Packard Company 40 * 41 * Permission to use, copy, modify, distribute and sell this software 42 * and its documentation for any purpose is hereby granted without fee, 43 * provided that the above copyright notice appear in all copies and 44 * that both that copyright notice and this permission notice appear 45 * in supporting documentation. Hewlett-Packard Company makes no 46 * representations about the suitability of this software for any 47 * purpose. It is provided "as is" without express or implied warranty. 48 * 49 */ 50 51 /** @file backward/hashtable.h 52 * This file is a GNU extension to the Standard C++ Library (possibly 53 * containing extensions from the HP/SGI STL subset). 54 */ 55 56 #ifndef _BACKWARD_HASHTABLE_H 57 #define _BACKWARD_HASHTABLE_H 1 58 59 // Hashtable class, used to implement the hashed associative containers 60 // hash_set, hash_map, hash_multiset, and hash_multimap. 61 62 #include <vector> 63 #include <iterator> 64 #include <algorithm> 65 #include <bits/stl_function.h> 66 #include <backward/hash_fun.h> 67 68 namespace __gnu_cxx _GLIBCXX_VISIBILITY(default) 69 { 70 _GLIBCXX_BEGIN_NAMESPACE_VERSION 71 72 using std::size_t; 73 using std::ptrdiff_t; 74 using std::forward_iterator_tag; 75 using std::input_iterator_tag; 76 using std::_Construct; 77 using std::_Destroy; 78 using std::distance; 79 using std::vector; 80 using std::pair; 81 using std::__iterator_category; 82 83 template<class _Val> 84 struct _Hashtable_node 85 { 86 _Hashtable_node* _M_next; 87 _Val _M_val; 88 }; 89 90 template<class _Val, class _Key, class _HashFcn, class _ExtractKey, 91 class _EqualKey, class _Alloc = std::allocator<_Val> > 92 class hashtable; 93 94 template<class _Val, class _Key, class _HashFcn, 95 class _ExtractKey, class _EqualKey, class _Alloc> 96 struct _Hashtable_iterator; 97 98 template<class _Val, class _Key, class _HashFcn, 99 class _ExtractKey, class _EqualKey, class _Alloc> 100 struct _Hashtable_const_iterator; 101 102 template<class _Val, class _Key, class _HashFcn, 103 class _ExtractKey, class _EqualKey, class _Alloc> 104 struct _Hashtable_iterator 105 { 106 typedef hashtable<_Val, _Key, _HashFcn, _ExtractKey, _EqualKey, _Alloc> 107 _Hashtable; 108 typedef _Hashtable_iterator<_Val, _Key, _HashFcn, 109 _ExtractKey, _EqualKey, _Alloc> 110 iterator; 111 typedef _Hashtable_const_iterator<_Val, _Key, _HashFcn, 112 _ExtractKey, _EqualKey, _Alloc> 113 const_iterator; 114 typedef _Hashtable_node<_Val> _Node; 115 typedef forward_iterator_tag iterator_category; 116 typedef _Val value_type; 117 typedef ptrdiff_t difference_type; 118 typedef size_t size_type; 119 typedef _Val& reference; 120 typedef _Val* pointer; 121 122 _Node* _M_cur; 123 _Hashtable* _M_ht; 124 125 _Hashtable_iterator(_Node* __n, _Hashtable* __tab) 126 : _M_cur(__n), _M_ht(__tab) { } 127 128 _Hashtable_iterator() { } 129 130 reference 131 operator*() const 132 { return _M_cur->_M_val; } 133 134 pointer 135 operator->() const 136 { return &(operator*()); } 137 138 iterator& 139 operator++(); 140 141 iterator 142 operator++(int); 143 144 bool 145 operator==(const iterator& __it) const 146 { return _M_cur == __it._M_cur; } 147 148 bool 149 operator!=(const iterator& __it) const 150 { return _M_cur != __it._M_cur; } 151 }; 152 153 template<class _Val, class _Key, class _HashFcn, 154 class _ExtractKey, class _EqualKey, class _Alloc> 155 struct _Hashtable_const_iterator 156 { 157 typedef hashtable<_Val, _Key, _HashFcn, _ExtractKey, _EqualKey, _Alloc> 158 _Hashtable; 159 typedef _Hashtable_iterator<_Val,_Key,_HashFcn, 160 _ExtractKey,_EqualKey,_Alloc> 161 iterator; 162 typedef _Hashtable_const_iterator<_Val, _Key, _HashFcn, 163 _ExtractKey, _EqualKey, _Alloc> 164 const_iterator; 165 typedef _Hashtable_node<_Val> _Node; 166 167 typedef forward_iterator_tag iterator_category; 168 typedef _Val value_type; 169 typedef ptrdiff_t difference_type; 170 typedef size_t size_type; 171 typedef const _Val& reference; 172 typedef const _Val* pointer; 173 174 const _Node* _M_cur; 175 const _Hashtable* _M_ht; 176 177 _Hashtable_const_iterator(const _Node* __n, const _Hashtable* __tab) 178 : _M_cur(__n), _M_ht(__tab) { } 179 180 _Hashtable_const_iterator() { } 181 182 _Hashtable_const_iterator(const iterator& __it) 183 : _M_cur(__it._M_cur), _M_ht(__it._M_ht) { } 184 185 reference 186 operator*() const 187 { return _M_cur->_M_val; } 188 189 pointer 190 operator->() const 191 { return &(operator*()); } 192 193 const_iterator& 194 operator++(); 195 196 const_iterator 197 operator++(int); 198 199 bool 200 operator==(const const_iterator& __it) const 201 { return _M_cur == __it._M_cur; } 202 203 bool 204 operator!=(const const_iterator& __it) const 205 { return _M_cur != __it._M_cur; } 206 }; 207 208 // Note: assumes long is at least 32 bits. 209 enum { _S_num_primes = 29 }; 210 211 template<typename _PrimeType> 212 struct _Hashtable_prime_list 213 { 214 static const _PrimeType __stl_prime_list[_S_num_primes]; 215 216 static const _PrimeType* 217 _S_get_prime_list(); 218 }; 219 220 template<typename _PrimeType> const _PrimeType 221 _Hashtable_prime_list<_PrimeType>::__stl_prime_list[_S_num_primes] = 222 { 223 5ul, 53ul, 97ul, 193ul, 389ul, 224 769ul, 1543ul, 3079ul, 6151ul, 12289ul, 225 24593ul, 49157ul, 98317ul, 196613ul, 393241ul, 226 786433ul, 1572869ul, 3145739ul, 6291469ul, 12582917ul, 227 25165843ul, 50331653ul, 100663319ul, 201326611ul, 402653189ul, 228 805306457ul, 1610612741ul, 3221225473ul, 4294967291ul 229 }; 230 231 template<class _PrimeType> inline const _PrimeType* 232 _Hashtable_prime_list<_PrimeType>::_S_get_prime_list() 233 { 234 return __stl_prime_list; 235 } 236 237 inline unsigned long 238 __stl_next_prime(unsigned long __n) 239 { 240 const unsigned long* __first = _Hashtable_prime_list<unsigned long>::_S_get_prime_list(); 241 const unsigned long* __last = __first + (int)_S_num_primes; 242 const unsigned long* pos = std::lower_bound(__first, __last, __n); 243 return pos == __last ? *(__last - 1) : *pos; 244 } 245 246 // Forward declaration of operator==. 247 template<class _Val, class _Key, class _HF, class _Ex, 248 class _Eq, class _All> 249 class hashtable; 250 251 template<class _Val, class _Key, class _HF, class _Ex, 252 class _Eq, class _All> 253 bool 254 operator==(const hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>& __ht1, 255 const hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>& __ht2); 256 257 // Hashtables handle allocators a bit differently than other 258 // containers do. If we're using standard-conforming allocators, then 259 // a hashtable unconditionally has a member variable to hold its 260 // allocator, even if it so happens that all instances of the 261 // allocator type are identical. This is because, for hashtables, 262 // this extra storage is negligible. Additionally, a base class 263 // wouldn't serve any other purposes; it wouldn't, for example, 264 // simplify the exception-handling code. 265 template<class _Val, class _Key, class _HashFcn, 266 class _ExtractKey, class _EqualKey, class _Alloc> 267 class hashtable 268 { 269 public: 270 typedef _Key key_type; 271 typedef _Val value_type; 272 typedef _HashFcn hasher; 273 typedef _EqualKey key_equal; 274 275 typedef size_t size_type; 276 typedef ptrdiff_t difference_type; 277 typedef value_type* pointer; 278 typedef const value_type* const_pointer; 279 typedef value_type& reference; 280 typedef const value_type& const_reference; 281 282 hasher 283 hash_funct() const 284 { return _M_hash; } 285 286 key_equal 287 key_eq() const 288 { return _M_equals; } 289 290 private: 291 typedef _Hashtable_node<_Val> _Node; 292 293 public: 294 typedef typename _Alloc::template rebind<value_type>::other allocator_type; 295 allocator_type 296 get_allocator() const 297 { return _M_node_allocator; } 298 299 private: 300 typedef typename _Alloc::template rebind<_Node>::other _Node_Alloc; 301 typedef typename _Alloc::template rebind<_Node*>::other _Nodeptr_Alloc; 302 typedef vector<_Node*, _Nodeptr_Alloc> _Vector_type; 303 304 _Node_Alloc _M_node_allocator; 305 306 _Node* 307 _M_get_node() 308 { return _M_node_allocator.allocate(1); } 309 310 void 311 _M_put_node(_Node* __p) 312 { _M_node_allocator.deallocate(__p, 1); } 313 314 private: 315 hasher _M_hash; 316 key_equal _M_equals; 317 _ExtractKey _M_get_key; 318 _Vector_type _M_buckets; 319 size_type _M_num_elements; 320 321 public: 322 typedef _Hashtable_iterator<_Val, _Key, _HashFcn, _ExtractKey, 323 _EqualKey, _Alloc> 324 iterator; 325 typedef _Hashtable_const_iterator<_Val, _Key, _HashFcn, _ExtractKey, 326 _EqualKey, _Alloc> 327 const_iterator; 328 329 friend struct 330 _Hashtable_iterator<_Val, _Key, _HashFcn, _ExtractKey, _EqualKey, _Alloc>; 331 332 friend struct 333 _Hashtable_const_iterator<_Val, _Key, _HashFcn, _ExtractKey, 334 _EqualKey, _Alloc>; 335 336 public: 337 hashtable(size_type __n, const _HashFcn& __hf, 338 const _EqualKey& __eql, const _ExtractKey& __ext, 339 const allocator_type& __a = allocator_type()) 340 : _M_node_allocator(__a), _M_hash(__hf), _M_equals(__eql), 341 _M_get_key(__ext), _M_buckets(__a), _M_num_elements(0) 342 { _M_initialize_buckets(__n); } 343 344 hashtable(size_type __n, const _HashFcn& __hf, 345 const _EqualKey& __eql, 346 const allocator_type& __a = allocator_type()) 347 : _M_node_allocator(__a), _M_hash(__hf), _M_equals(__eql), 348 _M_get_key(_ExtractKey()), _M_buckets(__a), _M_num_elements(0) 349 { _M_initialize_buckets(__n); } 350 351 hashtable(const hashtable& __ht) 352 : _M_node_allocator(__ht.get_allocator()), _M_hash(__ht._M_hash), 353 _M_equals(__ht._M_equals), _M_get_key(__ht._M_get_key), 354 _M_buckets(__ht.get_allocator()), _M_num_elements(0) 355 { _M_copy_from(__ht); } 356 357 hashtable& 358 operator= (const hashtable& __ht) 359 { 360 if (&__ht != this) 361 { 362 clear(); 363 _M_hash = __ht._M_hash; 364 _M_equals = __ht._M_equals; 365 _M_get_key = __ht._M_get_key; 366 _M_copy_from(__ht); 367 } 368 return *this; 369 } 370 371 ~hashtable() 372 { clear(); } 373 374 size_type 375 size() const 376 { return _M_num_elements; } 377 378 size_type 379 max_size() const 380 { return size_type(-1); } 381 382 bool 383 empty() const 384 { return size() == 0; } 385 386 void 387 swap(hashtable& __ht) 388 { 389 std::swap(_M_hash, __ht._M_hash); 390 std::swap(_M_equals, __ht._M_equals); 391 std::swap(_M_get_key, __ht._M_get_key); 392 _M_buckets.swap(__ht._M_buckets); 393 std::swap(_M_num_elements, __ht._M_num_elements); 394 } 395 396 iterator 397 begin() 398 { 399 for (size_type __n = 0; __n < _M_buckets.size(); ++__n) 400 if (_M_buckets[__n]) 401 return iterator(_M_buckets[__n], this); 402 return end(); 403 } 404 405 iterator 406 end() 407 { return iterator(0, this); } 408 409 const_iterator 410 begin() const 411 { 412 for (size_type __n = 0; __n < _M_buckets.size(); ++__n) 413 if (_M_buckets[__n]) 414 return const_iterator(_M_buckets[__n], this); 415 return end(); 416 } 417 418 const_iterator 419 end() const 420 { return const_iterator(0, this); } 421 422 template<class _Vl, class _Ky, class _HF, class _Ex, class _Eq, 423 class _Al> 424 friend bool 425 operator==(const hashtable<_Vl, _Ky, _HF, _Ex, _Eq, _Al>&, 426 const hashtable<_Vl, _Ky, _HF, _Ex, _Eq, _Al>&); 427 428 public: 429 size_type 430 bucket_count() const 431 { return _M_buckets.size(); } 432 433 size_type 434 max_bucket_count() const 435 { return _Hashtable_prime_list<unsigned long>:: 436 _S_get_prime_list()[(int)_S_num_primes - 1]; 437 } 438 439 size_type 440 elems_in_bucket(size_type __bucket) const 441 { 442 size_type __result = 0; 443 for (_Node* __n = _M_buckets[__bucket]; __n; __n = __n->_M_next) 444 __result += 1; 445 return __result; 446 } 447 448 pair<iterator, bool> 449 insert_unique(const value_type& __obj) 450 { 451 resize(_M_num_elements + 1); 452 return insert_unique_noresize(__obj); 453 } 454 455 iterator 456 insert_equal(const value_type& __obj) 457 { 458 resize(_M_num_elements + 1); 459 return insert_equal_noresize(__obj); 460 } 461 462 pair<iterator, bool> 463 insert_unique_noresize(const value_type& __obj); 464 465 iterator 466 insert_equal_noresize(const value_type& __obj); 467 468 template<class _InputIterator> 469 void 470 insert_unique(_InputIterator __f, _InputIterator __l) 471 { insert_unique(__f, __l, __iterator_category(__f)); } 472 473 template<class _InputIterator> 474 void 475 insert_equal(_InputIterator __f, _InputIterator __l) 476 { insert_equal(__f, __l, __iterator_category(__f)); } 477 478 template<class _InputIterator> 479 void 480 insert_unique(_InputIterator __f, _InputIterator __l, 481 input_iterator_tag) 482 { 483 for ( ; __f != __l; ++__f) 484 insert_unique(*__f); 485 } 486 487 template<class _InputIterator> 488 void 489 insert_equal(_InputIterator __f, _InputIterator __l, 490 input_iterator_tag) 491 { 492 for ( ; __f != __l; ++__f) 493 insert_equal(*__f); 494 } 495 496 template<class _ForwardIterator> 497 void 498 insert_unique(_ForwardIterator __f, _ForwardIterator __l, 499 forward_iterator_tag) 500 { 501 size_type __n = distance(__f, __l); 502 resize(_M_num_elements + __n); 503 for ( ; __n > 0; --__n, ++__f) 504 insert_unique_noresize(*__f); 505 } 506 507 template<class _ForwardIterator> 508 void 509 insert_equal(_ForwardIterator __f, _ForwardIterator __l, 510 forward_iterator_tag) 511 { 512 size_type __n = distance(__f, __l); 513 resize(_M_num_elements + __n); 514 for ( ; __n > 0; --__n, ++__f) 515 insert_equal_noresize(*__f); 516 } 517 518 reference 519 find_or_insert(const value_type& __obj); 520 521 iterator 522 find(const key_type& __key) 523 { 524 size_type __n = _M_bkt_num_key(__key); 525 _Node* __first; 526 for (__first = _M_buckets[__n]; 527 __first && !_M_equals(_M_get_key(__first->_M_val), __key); 528 __first = __first->_M_next) 529 { } 530 return iterator(__first, this); 531 } 532 533 const_iterator 534 find(const key_type& __key) const 535 { 536 size_type __n = _M_bkt_num_key(__key); 537 const _Node* __first; 538 for (__first = _M_buckets[__n]; 539 __first && !_M_equals(_M_get_key(__first->_M_val), __key); 540 __first = __first->_M_next) 541 { } 542 return const_iterator(__first, this); 543 } 544 545 size_type 546 count(const key_type& __key) const 547 { 548 const size_type __n = _M_bkt_num_key(__key); 549 size_type __result = 0; 550 551 for (const _Node* __cur = _M_buckets[__n]; __cur; 552 __cur = __cur->_M_next) 553 if (_M_equals(_M_get_key(__cur->_M_val), __key)) 554 ++__result; 555 return __result; 556 } 557 558 pair<iterator, iterator> 559 equal_range(const key_type& __key); 560 561 pair<const_iterator, const_iterator> 562 equal_range(const key_type& __key) const; 563 564 size_type 565 erase(const key_type& __key); 566 567 void 568 erase(const iterator& __it); 569 570 void 571 erase(iterator __first, iterator __last); 572 573 void 574 erase(const const_iterator& __it); 575 576 void 577 erase(const_iterator __first, const_iterator __last); 578 579 void 580 resize(size_type __num_elements_hint); 581 582 void 583 clear(); 584 585 private: 586 size_type 587 _M_next_size(size_type __n) const 588 { return __stl_next_prime(__n); } 589 590 void 591 _M_initialize_buckets(size_type __n) 592 { 593 const size_type __n_buckets = _M_next_size(__n); 594 _M_buckets.reserve(__n_buckets); 595 _M_buckets.insert(_M_buckets.end(), __n_buckets, (_Node*) 0); 596 _M_num_elements = 0; 597 } 598 599 size_type 600 _M_bkt_num_key(const key_type& __key) const 601 { return _M_bkt_num_key(__key, _M_buckets.size()); } 602 603 size_type 604 _M_bkt_num(const value_type& __obj) const 605 { return _M_bkt_num_key(_M_get_key(__obj)); } 606 607 size_type 608 _M_bkt_num_key(const key_type& __key, size_t __n) const 609 { return _M_hash(__key) % __n; } 610 611 size_type 612 _M_bkt_num(const value_type& __obj, size_t __n) const 613 { return _M_bkt_num_key(_M_get_key(__obj), __n); } 614 615 _Node* 616 _M_new_node(const value_type& __obj) 617 { 618 _Node* __n = _M_get_node(); 619 __n->_M_next = 0; 620 __try 621 { 622 this->get_allocator().construct(&__n->_M_val, __obj); 623 return __n; 624 } 625 __catch(...) 626 { 627 _M_put_node(__n); 628 __throw_exception_again; 629 } 630 } 631 632 void 633 _M_delete_node(_Node* __n) 634 { 635 this->get_allocator().destroy(&__n->_M_val); 636 _M_put_node(__n); 637 } 638 639 void 640 _M_erase_bucket(const size_type __n, _Node* __first, _Node* __last); 641 642 void 643 _M_erase_bucket(const size_type __n, _Node* __last); 644 645 void 646 _M_copy_from(const hashtable& __ht); 647 }; 648 649 template<class _Val, class _Key, class _HF, class _ExK, class _EqK, 650 class _All> 651 _Hashtable_iterator<_Val, _Key, _HF, _ExK, _EqK, _All>& 652 _Hashtable_iterator<_Val, _Key, _HF, _ExK, _EqK, _All>:: 653 operator++() 654 { 655 const _Node* __old = _M_cur; 656 _M_cur = _M_cur->_M_next; 657 if (!_M_cur) 658 { 659 size_type __bucket = _M_ht->_M_bkt_num(__old->_M_val); 660 while (!_M_cur && ++__bucket < _M_ht->_M_buckets.size()) 661 _M_cur = _M_ht->_M_buckets[__bucket]; 662 } 663 return *this; 664 } 665 666 template<class _Val, class _Key, class _HF, class _ExK, class _EqK, 667 class _All> 668 inline _Hashtable_iterator<_Val, _Key, _HF, _ExK, _EqK, _All> 669 _Hashtable_iterator<_Val, _Key, _HF, _ExK, _EqK, _All>:: 670 operator++(int) 671 { 672 iterator __tmp = *this; 673 ++*this; 674 return __tmp; 675 } 676 677 template<class _Val, class _Key, class _HF, class _ExK, class _EqK, 678 class _All> 679 _Hashtable_const_iterator<_Val, _Key, _HF, _ExK, _EqK, _All>& 680 _Hashtable_const_iterator<_Val, _Key, _HF, _ExK, _EqK, _All>:: 681 operator++() 682 { 683 const _Node* __old = _M_cur; 684 _M_cur = _M_cur->_M_next; 685 if (!_M_cur) 686 { 687 size_type __bucket = _M_ht->_M_bkt_num(__old->_M_val); 688 while (!_M_cur && ++__bucket < _M_ht->_M_buckets.size()) 689 _M_cur = _M_ht->_M_buckets[__bucket]; 690 } 691 return *this; 692 } 693 694 template<class _Val, class _Key, class _HF, class _ExK, class _EqK, 695 class _All> 696 inline _Hashtable_const_iterator<_Val, _Key, _HF, _ExK, _EqK, _All> 697 _Hashtable_const_iterator<_Val, _Key, _HF, _ExK, _EqK, _All>:: 698 operator++(int) 699 { 700 const_iterator __tmp = *this; 701 ++*this; 702 return __tmp; 703 } 704 705 template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All> 706 bool 707 operator==(const hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>& __ht1, 708 const hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>& __ht2) 709 { 710 typedef typename hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::_Node _Node; 711 712 if (__ht1._M_buckets.size() != __ht2._M_buckets.size()) 713 return false; 714 715 for (size_t __n = 0; __n < __ht1._M_buckets.size(); ++__n) 716 { 717 _Node* __cur1 = __ht1._M_buckets[__n]; 718 _Node* __cur2 = __ht2._M_buckets[__n]; 719 // Check same length of lists 720 for (; __cur1 && __cur2; 721 __cur1 = __cur1->_M_next, __cur2 = __cur2->_M_next) 722 { } 723 if (__cur1 || __cur2) 724 return false; 725 // Now check one's elements are in the other 726 for (__cur1 = __ht1._M_buckets[__n] ; __cur1; 727 __cur1 = __cur1->_M_next) 728 { 729 bool _found__cur1 = false; 730 for (__cur2 = __ht2._M_buckets[__n]; 731 __cur2; __cur2 = __cur2->_M_next) 732 { 733 if (__cur1->_M_val == __cur2->_M_val) 734 { 735 _found__cur1 = true; 736 break; 737 } 738 } 739 if (!_found__cur1) 740 return false; 741 } 742 } 743 return true; 744 } 745 746 template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All> 747 inline bool 748 operator!=(const hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>& __ht1, 749 const hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>& __ht2) 750 { return !(__ht1 == __ht2); } 751 752 template<class _Val, class _Key, class _HF, class _Extract, class _EqKey, 753 class _All> 754 inline void 755 swap(hashtable<_Val, _Key, _HF, _Extract, _EqKey, _All>& __ht1, 756 hashtable<_Val, _Key, _HF, _Extract, _EqKey, _All>& __ht2) 757 { __ht1.swap(__ht2); } 758 759 template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All> 760 pair<typename hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::iterator, bool> 761 hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>:: 762 insert_unique_noresize(const value_type& __obj) 763 { 764 const size_type __n = _M_bkt_num(__obj); 765 _Node* __first = _M_buckets[__n]; 766 767 for (_Node* __cur = __first; __cur; __cur = __cur->_M_next) 768 if (_M_equals(_M_get_key(__cur->_M_val), _M_get_key(__obj))) 769 return pair<iterator, bool>(iterator(__cur, this), false); 770 771 _Node* __tmp = _M_new_node(__obj); 772 __tmp->_M_next = __first; 773 _M_buckets[__n] = __tmp; 774 ++_M_num_elements; 775 return pair<iterator, bool>(iterator(__tmp, this), true); 776 } 777 778 template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All> 779 typename hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::iterator 780 hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>:: 781 insert_equal_noresize(const value_type& __obj) 782 { 783 const size_type __n = _M_bkt_num(__obj); 784 _Node* __first = _M_buckets[__n]; 785 786 for (_Node* __cur = __first; __cur; __cur = __cur->_M_next) 787 if (_M_equals(_M_get_key(__cur->_M_val), _M_get_key(__obj))) 788 { 789 _Node* __tmp = _M_new_node(__obj); 790 __tmp->_M_next = __cur->_M_next; 791 __cur->_M_next = __tmp; 792 ++_M_num_elements; 793 return iterator(__tmp, this); 794 } 795 796 _Node* __tmp = _M_new_node(__obj); 797 __tmp->_M_next = __first; 798 _M_buckets[__n] = __tmp; 799 ++_M_num_elements; 800 return iterator(__tmp, this); 801 } 802 803 template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All> 804 typename hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::reference 805 hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>:: 806 find_or_insert(const value_type& __obj) 807 { 808 resize(_M_num_elements + 1); 809 810 size_type __n = _M_bkt_num(__obj); 811 _Node* __first = _M_buckets[__n]; 812 813 for (_Node* __cur = __first; __cur; __cur = __cur->_M_next) 814 if (_M_equals(_M_get_key(__cur->_M_val), _M_get_key(__obj))) 815 return __cur->_M_val; 816 817 _Node* __tmp = _M_new_node(__obj); 818 __tmp->_M_next = __first; 819 _M_buckets[__n] = __tmp; 820 ++_M_num_elements; 821 return __tmp->_M_val; 822 } 823 824 template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All> 825 pair<typename hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::iterator, 826 typename hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::iterator> 827 hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>:: 828 equal_range(const key_type& __key) 829 { 830 typedef pair<iterator, iterator> _Pii; 831 const size_type __n = _M_bkt_num_key(__key); 832 833 for (_Node* __first = _M_buckets[__n]; __first; 834 __first = __first->_M_next) 835 if (_M_equals(_M_get_key(__first->_M_val), __key)) 836 { 837 for (_Node* __cur = __first->_M_next; __cur; 838 __cur = __cur->_M_next) 839 if (!_M_equals(_M_get_key(__cur->_M_val), __key)) 840 return _Pii(iterator(__first, this), iterator(__cur, this)); 841 for (size_type __m = __n + 1; __m < _M_buckets.size(); ++__m) 842 if (_M_buckets[__m]) 843 return _Pii(iterator(__first, this), 844 iterator(_M_buckets[__m], this)); 845 return _Pii(iterator(__first, this), end()); 846 } 847 return _Pii(end(), end()); 848 } 849 850 template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All> 851 pair<typename hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::const_iterator, 852 typename hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::const_iterator> 853 hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>:: 854 equal_range(const key_type& __key) const 855 { 856 typedef pair<const_iterator, const_iterator> _Pii; 857 const size_type __n = _M_bkt_num_key(__key); 858 859 for (const _Node* __first = _M_buckets[__n]; __first; 860 __first = __first->_M_next) 861 { 862 if (_M_equals(_M_get_key(__first->_M_val), __key)) 863 { 864 for (const _Node* __cur = __first->_M_next; __cur; 865 __cur = __cur->_M_next) 866 if (!_M_equals(_M_get_key(__cur->_M_val), __key)) 867 return _Pii(const_iterator(__first, this), 868 const_iterator(__cur, this)); 869 for (size_type __m = __n + 1; __m < _M_buckets.size(); ++__m) 870 if (_M_buckets[__m]) 871 return _Pii(const_iterator(__first, this), 872 const_iterator(_M_buckets[__m], this)); 873 return _Pii(const_iterator(__first, this), end()); 874 } 875 } 876 return _Pii(end(), end()); 877 } 878 879 template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All> 880 typename hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::size_type 881 hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>:: 882 erase(const key_type& __key) 883 { 884 const size_type __n = _M_bkt_num_key(__key); 885 _Node* __first = _M_buckets[__n]; 886 _Node* __saved_slot = 0; 887 size_type __erased = 0; 888 889 if (__first) 890 { 891 _Node* __cur = __first; 892 _Node* __next = __cur->_M_next; 893 while (__next) 894 { 895 if (_M_equals(_M_get_key(__next->_M_val), __key)) 896 { 897 if (&_M_get_key(__next->_M_val) != &__key) 898 { 899 __cur->_M_next = __next->_M_next; 900 _M_delete_node(__next); 901 __next = __cur->_M_next; 902 ++__erased; 903 --_M_num_elements; 904 } 905 else 906 { 907 __saved_slot = __cur; 908 __cur = __next; 909 __next = __cur->_M_next; 910 } 911 } 912 else 913 { 914 __cur = __next; 915 __next = __cur->_M_next; 916 } 917 } 918 bool __delete_first = _M_equals(_M_get_key(__first->_M_val), __key); 919 if (__saved_slot) 920 { 921 __next = __saved_slot->_M_next; 922 __saved_slot->_M_next = __next->_M_next; 923 _M_delete_node(__next); 924 ++__erased; 925 --_M_num_elements; 926 } 927 if (__delete_first) 928 { 929 _M_buckets[__n] = __first->_M_next; 930 _M_delete_node(__first); 931 ++__erased; 932 --_M_num_elements; 933 } 934 } 935 return __erased; 936 } 937 938 template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All> 939 void hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>:: 940 erase(const iterator& __it) 941 { 942 _Node* __p = __it._M_cur; 943 if (__p) 944 { 945 const size_type __n = _M_bkt_num(__p->_M_val); 946 _Node* __cur = _M_buckets[__n]; 947 948 if (__cur == __p) 949 { 950 _M_buckets[__n] = __cur->_M_next; 951 _M_delete_node(__cur); 952 --_M_num_elements; 953 } 954 else 955 { 956 _Node* __next = __cur->_M_next; 957 while (__next) 958 { 959 if (__next == __p) 960 { 961 __cur->_M_next = __next->_M_next; 962 _M_delete_node(__next); 963 --_M_num_elements; 964 break; 965 } 966 else 967 { 968 __cur = __next; 969 __next = __cur->_M_next; 970 } 971 } 972 } 973 } 974 } 975 976 template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All> 977 void 978 hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>:: 979 erase(iterator __first, iterator __last) 980 { 981 size_type __f_bucket = __first._M_cur ? _M_bkt_num(__first._M_cur->_M_val) 982 : _M_buckets.size(); 983 984 size_type __l_bucket = __last._M_cur ? _M_bkt_num(__last._M_cur->_M_val) 985 : _M_buckets.size(); 986 987 if (__first._M_cur == __last._M_cur) 988 return; 989 else if (__f_bucket == __l_bucket) 990 _M_erase_bucket(__f_bucket, __first._M_cur, __last._M_cur); 991 else 992 { 993 _M_erase_bucket(__f_bucket, __first._M_cur, 0); 994 for (size_type __n = __f_bucket + 1; __n < __l_bucket; ++__n) 995 _M_erase_bucket(__n, 0); 996 if (__l_bucket != _M_buckets.size()) 997 _M_erase_bucket(__l_bucket, __last._M_cur); 998 } 999 } 1000 1001 template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All> 1002 inline void 1003 hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>:: 1004 erase(const_iterator __first, const_iterator __last) 1005 { 1006 erase(iterator(const_cast<_Node*>(__first._M_cur), 1007 const_cast<hashtable*>(__first._M_ht)), 1008 iterator(const_cast<_Node*>(__last._M_cur), 1009 const_cast<hashtable*>(__last._M_ht))); 1010 } 1011 1012 template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All> 1013 inline void 1014 hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>:: 1015 erase(const const_iterator& __it) 1016 { erase(iterator(const_cast<_Node*>(__it._M_cur), 1017 const_cast<hashtable*>(__it._M_ht))); } 1018 1019 template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All> 1020 void 1021 hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>:: 1022 resize(size_type __num_elements_hint) 1023 { 1024 const size_type __old_n = _M_buckets.size(); 1025 if (__num_elements_hint > __old_n) 1026 { 1027 const size_type __n = _M_next_size(__num_elements_hint); 1028 if (__n > __old_n) 1029 { 1030 _Vector_type __tmp(__n, (_Node*)(0), _M_buckets.get_allocator()); 1031 __try 1032 { 1033 for (size_type __bucket = 0; __bucket < __old_n; ++__bucket) 1034 { 1035 _Node* __first = _M_buckets[__bucket]; 1036 while (__first) 1037 { 1038 size_type __new_bucket = _M_bkt_num(__first->_M_val, 1039 __n); 1040 _M_buckets[__bucket] = __first->_M_next; 1041 __first->_M_next = __tmp[__new_bucket]; 1042 __tmp[__new_bucket] = __first; 1043 __first = _M_buckets[__bucket]; 1044 } 1045 } 1046 _M_buckets.swap(__tmp); 1047 } 1048 __catch(...) 1049 { 1050 for (size_type __bucket = 0; __bucket < __tmp.size(); 1051 ++__bucket) 1052 { 1053 while (__tmp[__bucket]) 1054 { 1055 _Node* __next = __tmp[__bucket]->_M_next; 1056 _M_delete_node(__tmp[__bucket]); 1057 __tmp[__bucket] = __next; 1058 } 1059 } 1060 __throw_exception_again; 1061 } 1062 } 1063 } 1064 } 1065 1066 template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All> 1067 void 1068 hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>:: 1069 _M_erase_bucket(const size_type __n, _Node* __first, _Node* __last) 1070 { 1071 _Node* __cur = _M_buckets[__n]; 1072 if (__cur == __first) 1073 _M_erase_bucket(__n, __last); 1074 else 1075 { 1076 _Node* __next; 1077 for (__next = __cur->_M_next; 1078 __next != __first; 1079 __cur = __next, __next = __cur->_M_next) 1080 ; 1081 while (__next != __last) 1082 { 1083 __cur->_M_next = __next->_M_next; 1084 _M_delete_node(__next); 1085 __next = __cur->_M_next; 1086 --_M_num_elements; 1087 } 1088 } 1089 } 1090 1091 template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All> 1092 void 1093 hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>:: 1094 _M_erase_bucket(const size_type __n, _Node* __last) 1095 { 1096 _Node* __cur = _M_buckets[__n]; 1097 while (__cur != __last) 1098 { 1099 _Node* __next = __cur->_M_next; 1100 _M_delete_node(__cur); 1101 __cur = __next; 1102 _M_buckets[__n] = __cur; 1103 --_M_num_elements; 1104 } 1105 } 1106 1107 template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All> 1108 void 1109 hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>:: 1110 clear() 1111 { 1112 if (_M_num_elements == 0) 1113 return; 1114 1115 for (size_type __i = 0; __i < _M_buckets.size(); ++__i) 1116 { 1117 _Node* __cur = _M_buckets[__i]; 1118 while (__cur != 0) 1119 { 1120 _Node* __next = __cur->_M_next; 1121 _M_delete_node(__cur); 1122 __cur = __next; 1123 } 1124 _M_buckets[__i] = 0; 1125 } 1126 _M_num_elements = 0; 1127 } 1128 1129 template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All> 1130 void 1131 hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>:: 1132 _M_copy_from(const hashtable& __ht) 1133 { 1134 _M_buckets.clear(); 1135 _M_buckets.reserve(__ht._M_buckets.size()); 1136 _M_buckets.insert(_M_buckets.end(), __ht._M_buckets.size(), (_Node*) 0); 1137 __try 1138 { 1139 for (size_type __i = 0; __i < __ht._M_buckets.size(); ++__i) { 1140 const _Node* __cur = __ht._M_buckets[__i]; 1141 if (__cur) 1142 { 1143 _Node* __local_copy = _M_new_node(__cur->_M_val); 1144 _M_buckets[__i] = __local_copy; 1145 1146 for (_Node* __next = __cur->_M_next; 1147 __next; 1148 __cur = __next, __next = __cur->_M_next) 1149 { 1150 __local_copy->_M_next = _M_new_node(__next->_M_val); 1151 __local_copy = __local_copy->_M_next; 1152 } 1153 } 1154 } 1155 _M_num_elements = __ht._M_num_elements; 1156 } 1157 __catch(...) 1158 { 1159 clear(); 1160 __throw_exception_again; 1161 } 1162 } 1163 1164 _GLIBCXX_END_NAMESPACE_VERSION 1165 } // namespace 1166 1167 #endif 1168