The C and C++ Include Header Files

/usr/include/c++/11/backward/hashtable.h

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

---

Contact us      |      About us      |      Term of use      |       Copyright © 2000-2024 MyWebUniversity.com ™