headers/cpp/stl_hashtable.h

   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
  49 template <class _Val>
  50 struct _Hashtable_node
  51 {
  52   _Hashtable_node* _M_next;
  53   _Val _M_val;
  54 };
  55
  56 template <class _Val, class _Key, class _HashFcn,
  57           class _ExtractKey, class _EqualKey, class _Alloc = alloc>
  58 class hashtable;
  59
  60 template <class _Val, class _Key, class _HashFcn,
  61           class _ExtractKey, class _EqualKey, class _Alloc>
  62 struct _Hashtable_iterator;
  63
  64 template <class _Val, class _Key, class _HashFcn,
  65           class _ExtractKey, class _EqualKey, class _Alloc>
  66 struct _Hashtable_const_iterator;
  67
  68 template <class _Val, class _Key, class _HashFcn,
  69           class _ExtractKey, class _EqualKey, class _Alloc>
  70 struct _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
 107 template <class _Val, class _Key, class _HashFcn,
 108           class _ExtractKey, class _EqualKey, class _Alloc>
 109 struct _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.
 148 static const int __stl_num_primes = 28;
 149 static 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
 159 inline 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
 169 template <class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
 170 class hashtable;
 171
 172 template <class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
 173 bool 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
 185 template <class _Val, class _Key, class _HashFcn,
 186           class _ExtractKey, class _EqualKey, class _Alloc>
 187 class hashtable {
 188 public:
 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
 204 private:
 205   typedef _Hashtable_node<_Val> _Node;
 206
 207 #ifdef __STL_USE_STD_ALLOCATORS
 208 public:
 209   typedef typename _Alloc_traits<_Val,_Alloc>::allocator_type allocator_type;
 210   allocator_type get_allocator() const { return _M_node_allocator; }
 211 private:
 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 */
 217 public:
 218   typedef _Alloc allocator_type;
 219   allocator_type get_allocator() const { return allocator_type(); }
 220 private:
 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
 227 private:
 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
 234 public:
 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
 246 public:
 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
 339 public:
 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
 507 private:
 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
 563 template <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
 578 template <class _Val, class _Key, class _HF, class _ExK, class _EqK,
 579           class _All>
 580 inline _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
 588 template <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
 603 template <class _Val, class _Key, class _HF, class _ExK, class _EqK,
 604           class _All>
 605 inline _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
 615 template <class _Val, class _Key, class _HF, class _ExK, class _EqK,
 616           class _All>
 617 inline forward_iterator_tag
 618 iterator_category(const _Hashtable_iterator<_Val,_Key,_HF,_ExK,_EqK,_All>&)
 619 {
 620   return forward_iterator_tag();
 621 }
 622
 623 template <class _Val, class _Key, class _HF, class _ExK, class _EqK,
 624           class _All>
 625 inline _Val*
 626 value_type(const _Hashtable_iterator<_Val,_Key,_HF,_ExK,_EqK,_All>&)
 627 {
 628   return (_Val*) 0;
 629 }
 630
 631 template <class _Val, class _Key, class _HF, class _ExK, class _EqK,
 632           class _All>
 633 inline hashtable<_Val,_Key,_HF,_ExK,_EqK,_All>::difference_type*
 634 distance_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
 639 template <class _Val, class _Key, class _HF, class _ExK, class _EqK,
 640           class _All>
 641 inline forward_iterator_tag
 642 iterator_category(const _Hashtable_const_iterator<_Val,_Key,_HF,
 643                                                   _ExK,_EqK,_All>&)
 644 {
 645   return forward_iterator_tag();
 646 }
 647
 648 template <class _Val, class _Key, class _HF, class _ExK, class _EqK,
 649           class _All>
 650 inline _Val*
 651 value_type(const _Hashtable_const_iterator<_Val,_Key,_HF,_ExK,_EqK,_All>&)
 652 {
 653   return (_Val*) 0;
 654 }
 655
 656 template <class _Val, class _Key, class _HF, class _ExK, class _EqK,
 657           class _All>
 658 inline hashtable<_Val,_Key,_HF,_ExK,_EqK,_All>::difference_type*
 659 distance_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
 666 template <class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
 667 inline 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
 687 template <class _Val, class _Key, class _HF, class _Extract, class _EqKey,
 688           class _All>
 689 inline 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
 697 template <class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
 698 pair<typename hashtable<_Val,_Key,_HF,_Ex,_Eq,_All>::iterator, bool>
 699 hashtable<_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
 716 template <class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
 717 typename hashtable<_Val,_Key,_HF,_Ex,_Eq,_All>::iterator
 718 hashtable<_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
 740 template <class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
 741 typename hashtable<_Val,_Key,_HF,_Ex,_Eq,_All>::reference
 742 hashtable<_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
 760 template <class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
 761 pair<typename hashtable<_Val,_Key,_HF,_Ex,_Eq,_All>::iterator,
 762      typename hashtable<_Val,_Key,_HF,_Ex,_Eq,_All>::iterator>
 763 hashtable<_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
 782 template <class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
 783 pair<typename hashtable<_Val,_Key,_HF,_Ex,_Eq,_All>::const_iterator,
 784      typename hashtable<_Val,_Key,_HF,_Ex,_Eq,_All>::const_iterator>
 785 hashtable<_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
 811 template <class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
 812 typename hashtable<_Val,_Key,_HF,_Ex,_Eq,_All>::size_type
 813 hashtable<_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
 845 template <class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
 846 void 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
 875 template <class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
 876 void 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
 897 template <class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
 898 inline void
 899 hashtable<_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
 908 template <class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
 909 inline void
 910 hashtable<_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
 916 template <class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
 917 void 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
 955 template <class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
 956 void 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
 977 template <class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
 978 void 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
 991 template <class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
 992 void 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
1007 template <class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
1008 void 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: