libstdc++-v3/include/ext/stl_hashtable.h

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