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