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