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