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