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

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