contrib/gcc-3.4/libstdc++-v3/include/ext/hashtable.h

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