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