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