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