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 : _M_cur(0), _M_ht(0) { } 131 132 reference 133 operator*() const 134 { return _M_cur->_M_val; } 135 136 pointer 137 operator->() const 138 { return &(operator*()); } 139 140 iterator& 141 operator++(); 142 143 iterator 144 operator++(int); 145 146 bool 147 operator==(const iterator& __it) const 148 { return _M_cur == __it._M_cur; } 149 150 bool 151 operator!=(const iterator& __it) const 152 { return _M_cur != __it._M_cur; } 153 }; 154 155 template<class _Val, class _Key, class _HashFcn, 156 class _ExtractKey, class _EqualKey, class _Alloc> 157 struct _Hashtable_const_iterator 158 { 159 typedef hashtable<_Val, _Key, _HashFcn, _ExtractKey, _EqualKey, _Alloc> 160 _Hashtable; 161 typedef _Hashtable_iterator<_Val,_Key,_HashFcn, 162 _ExtractKey,_EqualKey,_Alloc> 163 iterator; 164 typedef _Hashtable_const_iterator<_Val, _Key, _HashFcn, 165 _ExtractKey, _EqualKey, _Alloc> 166 const_iterator; 167 typedef _Hashtable_node<_Val> _Node; 168 169 typedef forward_iterator_tag iterator_category; 170 typedef _Val value_type; 171 typedef ptrdiff_t difference_type; 172 typedef size_t size_type; 173 typedef const _Val& reference; 174 typedef const _Val* pointer; 175 176 const _Node* _M_cur; 177 const _Hashtable* _M_ht; 178 179 _Hashtable_const_iterator(const _Node* __n, const _Hashtable* __tab) 180 : _M_cur(__n), _M_ht(__tab) { } 181 182 _Hashtable_const_iterator() { } 183 184 _Hashtable_const_iterator(const iterator& __it) 185 : _M_cur(__it._M_cur), _M_ht(__it._M_ht) { } 186 187 reference 188 operator*() const 189 { return _M_cur->_M_val; } 190 191 pointer 192 operator->() const 193 { return &(operator*()); } 194 195 const_iterator& 196 operator++(); 197 198 const_iterator 199 operator++(int); 200 201 bool 202 operator==(const const_iterator& __it) const 203 { return _M_cur == __it._M_cur; } 204 205 bool 206 operator!=(const const_iterator& __it) const 207 { return _M_cur != __it._M_cur; } 208 }; 209 210 // Note: assumes long is at least 32 bits. 211 enum { _S_num_primes = 29 }; 212 213 template<typename _PrimeType> 214 struct _Hashtable_prime_list 215 { 216 static const _PrimeType __stl_prime_list[_S_num_primes]; 217 218 static const _PrimeType* 219 _S_get_prime_list(); 220 }; 221 222 template<typename _PrimeType> const _PrimeType 223 _Hashtable_prime_list<_PrimeType>::__stl_prime_list[_S_num_primes] = 224 { 225 5ul, 53ul, 97ul, 193ul, 389ul, 226 769ul, 1543ul, 3079ul, 6151ul, 12289ul, 227 24593ul, 49157ul, 98317ul, 196613ul, 393241ul, 228 786433ul, 1572869ul, 3145739ul, 6291469ul, 12582917ul, 229 25165843ul, 50331653ul, 100663319ul, 201326611ul, 402653189ul, 230 805306457ul, 1610612741ul, 3221225473ul, 4294967291ul 231 }; 232 233 template<class _PrimeType> inline const _PrimeType* 234 _Hashtable_prime_list<_PrimeType>::_S_get_prime_list() 235 { 236 return __stl_prime_list; 237 } 238 239 inline unsigned long 240 __stl_next_prime(unsigned long __n) 241 { 242 const unsigned long* __first = _Hashtable_prime_list<unsigned long>::_S_get_prime_list(); 243 const unsigned long* __last = __first + (int)_S_num_primes; 244 const unsigned long* pos = std::lower_bound(__first, __last, __n); 245 return pos == __last ? *(__last - 1) : *pos; 246 } 247 248 // Forward declaration of operator==. 249 template<class _Val, class _Key, class _HF, class _Ex, 250 class _Eq, class _All> 251 class hashtable; 252 253 template<class _Val, class _Key, class _HF, class _Ex, 254 class _Eq, class _All> 255 bool 256 operator==(const hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>& __ht1, 257 const hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>& __ht2); 258 259 // Hashtables handle allocators a bit differently than other 260 // containers do. If we're using standard-conforming allocators, then 261 // a hashtable unconditionally has a member variable to hold its 262 // allocator, even if it so happens that all instances of the 263 // allocator type are identical. This is because, for hashtables, 264 // this extra storage is negligible. Additionally, a base class 265 // wouldn't serve any other purposes; it wouldn't, for example, 266 // simplify the exception-handling code. 267 template<class _Val, class _Key, class _HashFcn, 268 class _ExtractKey, class _EqualKey, class _Alloc> 269 class hashtable 270 { 271 public: 272 typedef _Key key_type; 273 typedef _Val value_type; 274 typedef _HashFcn hasher; 275 typedef _EqualKey key_equal; 276 277 typedef size_t size_type; 278 typedef ptrdiff_t difference_type; 279 typedef value_type* pointer; 280 typedef const value_type* const_pointer; 281 typedef value_type& reference; 282 typedef const value_type& const_reference; 283 284 hasher 285 hash_funct() const 286 { return _M_hash; } 287 288 key_equal 289 key_eq() const 290 { return _M_equals; } 291 292 private: 293 typedef _Hashtable_node<_Val> _Node; 294 295 public: 296 typedef typename _Alloc::template rebind<value_type>::other allocator_type; 297 allocator_type 298 get_allocator() const 299 { return _M_node_allocator; } 300 301 private: 302 typedef typename _Alloc::template rebind<_Node>::other _Node_Alloc; 303 typedef typename _Alloc::template rebind<_Node*>::other _Nodeptr_Alloc; 304 typedef vector<_Node*, _Nodeptr_Alloc> _Vector_type; 305 306 _Node_Alloc _M_node_allocator; 307 308 _Node* 309 _M_get_node() 310 { return _M_node_allocator.allocate(1); } 311 312 void 313 _M_put_node(_Node* __p) 314 { _M_node_allocator.deallocate(__p, 1); } 315 316 private: 317 hasher _M_hash; 318 key_equal _M_equals; 319 _ExtractKey _M_get_key; 320 _Vector_type _M_buckets; 321 size_type _M_num_elements; 322 323 public: 324 typedef _Hashtable_iterator<_Val, _Key, _HashFcn, _ExtractKey, 325 _EqualKey, _Alloc> 326 iterator; 327 typedef _Hashtable_const_iterator<_Val, _Key, _HashFcn, _ExtractKey, 328 _EqualKey, _Alloc> 329 const_iterator; 330 331 friend struct 332 _Hashtable_iterator<_Val, _Key, _HashFcn, _ExtractKey, _EqualKey, _Alloc>; 333 334 friend struct 335 _Hashtable_const_iterator<_Val, _Key, _HashFcn, _ExtractKey, 336 _EqualKey, _Alloc>; 337 338 public: 339 hashtable(size_type __n, const _HashFcn& __hf, 340 const _EqualKey& __eql, const _ExtractKey& __ext, 341 const allocator_type& __a = allocator_type()) 342 : _M_node_allocator(__a), _M_hash(__hf), _M_equals(__eql), 343 _M_get_key(__ext), _M_buckets(__a), _M_num_elements(0) 344 { _M_initialize_buckets(__n); } 345 346 hashtable(size_type __n, const _HashFcn& __hf, 347 const _EqualKey& __eql, 348 const allocator_type& __a = allocator_type()) 349 : _M_node_allocator(__a), _M_hash(__hf), _M_equals(__eql), 350 _M_get_key(_ExtractKey()), _M_buckets(__a), _M_num_elements(0) 351 { _M_initialize_buckets(__n); } 352 353 hashtable(const hashtable& __ht) 354 : _M_node_allocator(__ht.get_allocator()), _M_hash(__ht._M_hash), 355 _M_equals(__ht._M_equals), _M_get_key(__ht._M_get_key), 356 _M_buckets(__ht.get_allocator()), _M_num_elements(0) 357 { _M_copy_from(__ht); } 358 359 hashtable& 360 operator= (const hashtable& __ht) 361 { 362 if (&__ht != this) 363 { 364 clear(); 365 _M_hash = __ht._M_hash; 366 _M_equals = __ht._M_equals; 367 _M_get_key = __ht._M_get_key; 368 _M_copy_from(__ht); 369 } 370 return *this; 371 } 372 373 ~hashtable() 374 { clear(); } 375 376 size_type 377 size() const 378 { return _M_num_elements; } 379 380 size_type 381 max_size() const 382 { return size_type(-1); } 383 384 bool 385 empty() const 386 { return size() == 0; } 387 388 void 389 swap(hashtable& __ht) 390 { 391 std::swap(_M_hash, __ht._M_hash); 392 std::swap(_M_equals, __ht._M_equals); 393 std::swap(_M_get_key, __ht._M_get_key); 394 _M_buckets.swap(__ht._M_buckets); 395 std::swap(_M_num_elements, __ht._M_num_elements); 396 } 397 398 iterator 399 begin() 400 { 401 for (size_type __n = 0; __n < _M_buckets.size(); ++__n) 402 if (_M_buckets[__n]) 403 return iterator(_M_buckets[__n], this); 404 return end(); 405 } 406 407 iterator 408 end() 409 { return iterator(0, this); } 410 411 const_iterator 412 begin() const 413 { 414 for (size_type __n = 0; __n < _M_buckets.size(); ++__n) 415 if (_M_buckets[__n]) 416 return const_iterator(_M_buckets[__n], this); 417 return end(); 418 } 419 420 const_iterator 421 end() const 422 { return const_iterator(0, this); } 423 424 template<class _Vl, class _Ky, class _HF, class _Ex, class _Eq, 425 class _Al> 426 friend bool 427 operator==(const hashtable<_Vl, _Ky, _HF, _Ex, _Eq, _Al>&, 428 const hashtable<_Vl, _Ky, _HF, _Ex, _Eq, _Al>&); 429 430 public: 431 size_type 432 bucket_count() const 433 { return _M_buckets.size(); } 434 435 size_type 436 max_bucket_count() const 437 { return _Hashtable_prime_list<unsigned long>:: 438 _S_get_prime_list()[(int)_S_num_primes - 1]; 439 } 440 441 size_type 442 elems_in_bucket(size_type __bucket) const 443 { 444 size_type __result = 0; 445 for (_Node* __n = _M_buckets[__bucket]; __n; __n = __n->_M_next) 446 __result += 1; 447 return __result; 448 } 449 450 pair<iterator, bool> 451 insert_unique(const value_type& __obj) 452 { 453 resize(_M_num_elements + 1); 454 return insert_unique_noresize(__obj); 455 } 456 457 iterator 458 insert_equal(const value_type& __obj) 459 { 460 resize(_M_num_elements + 1); 461 return insert_equal_noresize(__obj); 462 } 463 464 pair<iterator, bool> 465 insert_unique_noresize(const value_type& __obj); 466 467 iterator 468 insert_equal_noresize(const value_type& __obj); 469 470 template<class _InputIterator> 471 void 472 insert_unique(_InputIterator __f, _InputIterator __l) 473 { insert_unique(__f, __l, __iterator_category(__f)); } 474 475 template<class _InputIterator> 476 void 477 insert_equal(_InputIterator __f, _InputIterator __l) 478 { insert_equal(__f, __l, __iterator_category(__f)); } 479 480 template<class _InputIterator> 481 void 482 insert_unique(_InputIterator __f, _InputIterator __l, 483 input_iterator_tag) 484 { 485 for ( ; __f != __l; ++__f) 486 insert_unique(*__f); 487 } 488 489 template<class _InputIterator> 490 void 491 insert_equal(_InputIterator __f, _InputIterator __l, 492 input_iterator_tag) 493 { 494 for ( ; __f != __l; ++__f) 495 insert_equal(*__f); 496 } 497 498 template<class _ForwardIterator> 499 void 500 insert_unique(_ForwardIterator __f, _ForwardIterator __l, 501 forward_iterator_tag) 502 { 503 size_type __n = distance(__f, __l); 504 resize(_M_num_elements + __n); 505 for ( ; __n > 0; --__n, ++__f) 506 insert_unique_noresize(*__f); 507 } 508 509 template<class _ForwardIterator> 510 void 511 insert_equal(_ForwardIterator __f, _ForwardIterator __l, 512 forward_iterator_tag) 513 { 514 size_type __n = distance(__f, __l); 515 resize(_M_num_elements + __n); 516 for ( ; __n > 0; --__n, ++__f) 517 insert_equal_noresize(*__f); 518 } 519 520 reference 521 find_or_insert(const value_type& __obj); 522 523 iterator 524 find(const key_type& __key) 525 { 526 size_type __n = _M_bkt_num_key(__key); 527 _Node* __first; 528 for (__first = _M_buckets[__n]; 529 __first && !_M_equals(_M_get_key(__first->_M_val), __key); 530 __first = __first->_M_next) 531 { } 532 return iterator(__first, this); 533 } 534 535 const_iterator 536 find(const key_type& __key) const 537 { 538 size_type __n = _M_bkt_num_key(__key); 539 const _Node* __first; 540 for (__first = _M_buckets[__n]; 541 __first && !_M_equals(_M_get_key(__first->_M_val), __key); 542 __first = __first->_M_next) 543 { } 544 return const_iterator(__first, this); 545 } 546 547 size_type 548 count(const key_type& __key) const 549 { 550 const size_type __n = _M_bkt_num_key(__key); 551 size_type __result = 0; 552 553 for (const _Node* __cur = _M_buckets[__n]; __cur; 554 __cur = __cur->_M_next) 555 if (_M_equals(_M_get_key(__cur->_M_val), __key)) 556 ++__result; 557 return __result; 558 } 559 560 pair<iterator, iterator> 561 equal_range(const key_type& __key); 562 563 pair<const_iterator, const_iterator> 564 equal_range(const key_type& __key) const; 565 566 size_type 567 erase(const key_type& __key); 568 569 void 570 erase(const iterator& __it); 571 572 void 573 erase(iterator __first, iterator __last); 574 575 void 576 erase(const const_iterator& __it); 577 578 void 579 erase(const_iterator __first, const_iterator __last); 580 581 void 582 resize(size_type __num_elements_hint); 583 584 void 585 clear(); 586 587 private: 588 size_type 589 _M_next_size(size_type __n) const 590 { return __stl_next_prime(__n); } 591 592 void 593 _M_initialize_buckets(size_type __n) 594 { 595 const size_type __n_buckets = _M_next_size(__n); 596 _M_buckets.reserve(__n_buckets); 597 _M_buckets.insert(_M_buckets.end(), __n_buckets, (_Node*) 0); 598 _M_num_elements = 0; 599 } 600 601 size_type 602 _M_bkt_num_key(const key_type& __key) const 603 { return _M_bkt_num_key(__key, _M_buckets.size()); } 604 605 size_type 606 _M_bkt_num(const value_type& __obj) const 607 { return _M_bkt_num_key(_M_get_key(__obj)); } 608 609 size_type 610 _M_bkt_num_key(const key_type& __key, size_t __n) const 611 { return _M_hash(__key) % __n; } 612 613 size_type 614 _M_bkt_num(const value_type& __obj, size_t __n) const 615 { return _M_bkt_num_key(_M_get_key(__obj), __n); } 616 617 _Node* 618 _M_new_node(const value_type& __obj) 619 { 620 _Node* __n = _M_get_node(); 621 __n->_M_next = 0; 622 __try 623 { 624 this->get_allocator().construct(&__n->_M_val, __obj); 625 return __n; 626 } 627 __catch(...) 628 { 629 _M_put_node(__n); 630 __throw_exception_again; 631 } 632 } 633 634 void 635 _M_delete_node(_Node* __n) 636 { 637 this->get_allocator().destroy(&__n->_M_val); 638 _M_put_node(__n); 639 } 640 641 void 642 _M_erase_bucket(const size_type __n, _Node* __first, _Node* __last); 643 644 void 645 _M_erase_bucket(const size_type __n, _Node* __last); 646 647 void 648 _M_copy_from(const hashtable& __ht); 649 }; 650 651 template<class _Val, class _Key, class _HF, class _ExK, class _EqK, 652 class _All> 653 _Hashtable_iterator<_Val, _Key, _HF, _ExK, _EqK, _All>& 654 _Hashtable_iterator<_Val, _Key, _HF, _ExK, _EqK, _All>:: 655 operator++() 656 { 657 const _Node* __old = _M_cur; 658 _M_cur = _M_cur->_M_next; 659 if (!_M_cur) 660 { 661 size_type __bucket = _M_ht->_M_bkt_num(__old->_M_val); 662 while (!_M_cur && ++__bucket < _M_ht->_M_buckets.size()) 663 _M_cur = _M_ht->_M_buckets[__bucket]; 664 } 665 return *this; 666 } 667 668 template<class _Val, class _Key, class _HF, class _ExK, class _EqK, 669 class _All> 670 inline _Hashtable_iterator<_Val, _Key, _HF, _ExK, _EqK, _All> 671 _Hashtable_iterator<_Val, _Key, _HF, _ExK, _EqK, _All>:: 672 operator++(int) 673 { 674 iterator __tmp = *this; 675 ++*this; 676 return __tmp; 677 } 678 679 template<class _Val, class _Key, class _HF, class _ExK, class _EqK, 680 class _All> 681 _Hashtable_const_iterator<_Val, _Key, _HF, _ExK, _EqK, _All>& 682 _Hashtable_const_iterator<_Val, _Key, _HF, _ExK, _EqK, _All>:: 683 operator++() 684 { 685 const _Node* __old = _M_cur; 686 _M_cur = _M_cur->_M_next; 687 if (!_M_cur) 688 { 689 size_type __bucket = _M_ht->_M_bkt_num(__old->_M_val); 690 while (!_M_cur && ++__bucket < _M_ht->_M_buckets.size()) 691 _M_cur = _M_ht->_M_buckets[__bucket]; 692 } 693 return *this; 694 } 695 696 template<class _Val, class _Key, class _HF, class _ExK, class _EqK, 697 class _All> 698 inline _Hashtable_const_iterator<_Val, _Key, _HF, _ExK, _EqK, _All> 699 _Hashtable_const_iterator<_Val, _Key, _HF, _ExK, _EqK, _All>:: 700 operator++(int) 701 { 702 const_iterator __tmp = *this; 703 ++*this; 704 return __tmp; 705 } 706 707 template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All> 708 bool 709 operator==(const hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>& __ht1, 710 const hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>& __ht2) 711 { 712 typedef typename hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::_Node _Node; 713 714 if (__ht1._M_buckets.size() != __ht2._M_buckets.size()) 715 return false; 716 717 for (size_t __n = 0; __n < __ht1._M_buckets.size(); ++__n) 718 { 719 _Node* __cur1 = __ht1._M_buckets[__n]; 720 _Node* __cur2 = __ht2._M_buckets[__n]; 721 // Check same length of lists 722 for (; __cur1 && __cur2; 723 __cur1 = __cur1->_M_next, __cur2 = __cur2->_M_next) 724 { } 725 if (__cur1 || __cur2) 726 return false; 727 // Now check one's elements are in the other 728 for (__cur1 = __ht1._M_buckets[__n] ; __cur1; 729 __cur1 = __cur1->_M_next) 730 { 731 bool _found__cur1 = false; 732 for (__cur2 = __ht2._M_buckets[__n]; 733 __cur2; __cur2 = __cur2->_M_next) 734 { 735 if (__cur1->_M_val == __cur2->_M_val) 736 { 737 _found__cur1 = true; 738 break; 739 } 740 } 741 if (!_found__cur1) 742 return false; 743 } 744 } 745 return true; 746 } 747 748 template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All> 749 inline bool 750 operator!=(const hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>& __ht1, 751 const hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>& __ht2) 752 { return !(__ht1 == __ht2); } 753 754 template<class _Val, class _Key, class _HF, class _Extract, class _EqKey, 755 class _All> 756 inline void 757 swap(hashtable<_Val, _Key, _HF, _Extract, _EqKey, _All>& __ht1, 758 hashtable<_Val, _Key, _HF, _Extract, _EqKey, _All>& __ht2) 759 { __ht1.swap(__ht2); } 760 761 template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All> 762 pair<typename hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::iterator, bool> 763 hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>:: 764 insert_unique_noresize(const value_type& __obj) 765 { 766 const size_type __n = _M_bkt_num(__obj); 767 _Node* __first = _M_buckets[__n]; 768 769 for (_Node* __cur = __first; __cur; __cur = __cur->_M_next) 770 if (_M_equals(_M_get_key(__cur->_M_val), _M_get_key(__obj))) 771 return pair<iterator, bool>(iterator(__cur, this), false); 772 773 _Node* __tmp = _M_new_node(__obj); 774 __tmp->_M_next = __first; 775 _M_buckets[__n] = __tmp; 776 ++_M_num_elements; 777 return pair<iterator, bool>(iterator(__tmp, this), true); 778 } 779 780 template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All> 781 typename hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::iterator 782 hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>:: 783 insert_equal_noresize(const value_type& __obj) 784 { 785 const size_type __n = _M_bkt_num(__obj); 786 _Node* __first = _M_buckets[__n]; 787 788 for (_Node* __cur = __first; __cur; __cur = __cur->_M_next) 789 if (_M_equals(_M_get_key(__cur->_M_val), _M_get_key(__obj))) 790 { 791 _Node* __tmp = _M_new_node(__obj); 792 __tmp->_M_next = __cur->_M_next; 793 __cur->_M_next = __tmp; 794 ++_M_num_elements; 795 return iterator(__tmp, this); 796 } 797 798 _Node* __tmp = _M_new_node(__obj); 799 __tmp->_M_next = __first; 800 _M_buckets[__n] = __tmp; 801 ++_M_num_elements; 802 return iterator(__tmp, this); 803 } 804 805 template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All> 806 typename hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::reference 807 hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>:: 808 find_or_insert(const value_type& __obj) 809 { 810 resize(_M_num_elements + 1); 811 812 size_type __n = _M_bkt_num(__obj); 813 _Node* __first = _M_buckets[__n]; 814 815 for (_Node* __cur = __first; __cur; __cur = __cur->_M_next) 816 if (_M_equals(_M_get_key(__cur->_M_val), _M_get_key(__obj))) 817 return __cur->_M_val; 818 819 _Node* __tmp = _M_new_node(__obj); 820 __tmp->_M_next = __first; 821 _M_buckets[__n] = __tmp; 822 ++_M_num_elements; 823 return __tmp->_M_val; 824 } 825 826 template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All> 827 pair<typename hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::iterator, 828 typename hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::iterator> 829 hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>:: 830 equal_range(const key_type& __key) 831 { 832 typedef pair<iterator, iterator> _Pii; 833 const size_type __n = _M_bkt_num_key(__key); 834 835 for (_Node* __first = _M_buckets[__n]; __first; 836 __first = __first->_M_next) 837 if (_M_equals(_M_get_key(__first->_M_val), __key)) 838 { 839 for (_Node* __cur = __first->_M_next; __cur; 840 __cur = __cur->_M_next) 841 if (!_M_equals(_M_get_key(__cur->_M_val), __key)) 842 return _Pii(iterator(__first, this), iterator(__cur, this)); 843 for (size_type __m = __n + 1; __m < _M_buckets.size(); ++__m) 844 if (_M_buckets[__m]) 845 return _Pii(iterator(__first, this), 846 iterator(_M_buckets[__m], this)); 847 return _Pii(iterator(__first, this), end()); 848 } 849 return _Pii(end(), end()); 850 } 851 852 template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All> 853 pair<typename hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::const_iterator, 854 typename hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::const_iterator> 855 hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>:: 856 equal_range(const key_type& __key) const 857 { 858 typedef pair<const_iterator, const_iterator> _Pii; 859 const size_type __n = _M_bkt_num_key(__key); 860 861 for (const _Node* __first = _M_buckets[__n]; __first; 862 __first = __first->_M_next) 863 { 864 if (_M_equals(_M_get_key(__first->_M_val), __key)) 865 { 866 for (const _Node* __cur = __first->_M_next; __cur; 867 __cur = __cur->_M_next) 868 if (!_M_equals(_M_get_key(__cur->_M_val), __key)) 869 return _Pii(const_iterator(__first, this), 870 const_iterator(__cur, this)); 871 for (size_type __m = __n + 1; __m < _M_buckets.size(); ++__m) 872 if (_M_buckets[__m]) 873 return _Pii(const_iterator(__first, this), 874 const_iterator(_M_buckets[__m], this)); 875 return _Pii(const_iterator(__first, this), end()); 876 } 877 } 878 return _Pii(end(), end()); 879 } 880 881 template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All> 882 typename hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::size_type 883 hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>:: 884 erase(const key_type& __key) 885 { 886 const size_type __n = _M_bkt_num_key(__key); 887 _Node* __first = _M_buckets[__n]; 888 _Node* __saved_slot = 0; 889 size_type __erased = 0; 890 891 if (__first) 892 { 893 _Node* __cur = __first; 894 _Node* __next = __cur->_M_next; 895 while (__next) 896 { 897 if (_M_equals(_M_get_key(__next->_M_val), __key)) 898 { 899 if (&_M_get_key(__next->_M_val) != &__key) 900 { 901 __cur->_M_next = __next->_M_next; 902 _M_delete_node(__next); 903 __next = __cur->_M_next; 904 ++__erased; 905 --_M_num_elements; 906 } 907 else 908 { 909 __saved_slot = __cur; 910 __cur = __next; 911 __next = __cur->_M_next; 912 } 913 } 914 else 915 { 916 __cur = __next; 917 __next = __cur->_M_next; 918 } 919 } 920 if (_M_equals(_M_get_key(__first->_M_val), __key)) 921 { 922 _M_buckets[__n] = __first->_M_next; 923 _M_delete_node(__first); 924 ++__erased; 925 --_M_num_elements; 926 } 927 if (__saved_slot) 928 { 929 __next = __saved_slot->_M_next; 930 __saved_slot->_M_next = __next->_M_next; 931 _M_delete_node(__next); 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
