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

   1 // Hashtable implementation used by containers -*- C++ -*-
   2
   3 // Copyright (C) 2001, 2002, 2003 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::_Alloc_traits;
  81 using std::_Construct;
  82 using std::_Destroy;
  83 using std::distance;
  84 using std::vector;
  85 using std::pair;
  86 using std::__iterator_category;
  87
  88 template <class _Val>
  89 struct _Hashtable_node
  90 {
  91   _Hashtable_node* _M_next;
  92   _Val _M_val;
  93 };
  94
  95 template <class _Val, class _Key, class _HashFcn,
  96           class _ExtractKey, class _EqualKey, class _Alloc = std::__alloc>
  97 class hashtable;
  98
  99 template <class _Val, class _Key, class _HashFcn,
 100           class _ExtractKey, class _EqualKey, class _Alloc>
 101 struct _Hashtable_iterator;
 102
 103 template <class _Val, class _Key, class _HashFcn,
 104           class _ExtractKey, class _EqualKey, class _Alloc>
 105 struct _Hashtable_const_iterator;
 106
 107 template <class _Val, class _Key, class _HashFcn,
 108           class _ExtractKey, class _EqualKey, class _Alloc>
 109 struct _Hashtable_iterator {
 110   typedef hashtable<_Val,_Key,_HashFcn,_ExtractKey,_EqualKey,_Alloc>
 111           _Hashtable;
 112   typedef _Hashtable_iterator<_Val, _Key, _HashFcn,
 113                               _ExtractKey, _EqualKey, _Alloc>
 114           iterator;
 115   typedef _Hashtable_const_iterator<_Val, _Key, _HashFcn,
 116                                     _ExtractKey, _EqualKey, _Alloc>
 117           const_iterator;
 118   typedef _Hashtable_node<_Val> _Node;
 119
 120   typedef forward_iterator_tag iterator_category;
 121   typedef _Val value_type;
 122   typedef ptrdiff_t difference_type;
 123   typedef size_t size_type;
 124   typedef _Val& reference;
 125   typedef _Val* pointer;
 126
 127   _Node* _M_cur;
 128   _Hashtable* _M_ht;
 129
 130   _Hashtable_iterator(_Node* __n, _Hashtable* __tab)
 131     : _M_cur(__n), _M_ht(__tab) {}
 132   _Hashtable_iterator() {}
 133   reference operator*() const { return _M_cur->_M_val; }
 134   pointer operator->() const { return &(operator*()); }
 135   iterator& operator++();
 136   iterator operator++(int);
 137   bool operator==(const iterator& __it) const
 138     { return _M_cur == __it._M_cur; }
 139   bool operator!=(const iterator& __it) const
 140     { return _M_cur != __it._M_cur; }
 141 };
 142
 143
 144 template <class _Val, class _Key, class _HashFcn,
 145           class _ExtractKey, class _EqualKey, class _Alloc>
 146 struct _Hashtable_const_iterator {
 147   typedef hashtable<_Val,_Key,_HashFcn,_ExtractKey,_EqualKey,_Alloc>
 148           _Hashtable;
 149   typedef _Hashtable_iterator<_Val,_Key,_HashFcn,
 150                               _ExtractKey,_EqualKey,_Alloc>
 151           iterator;
 152   typedef _Hashtable_const_iterator<_Val, _Key, _HashFcn,
 153                                     _ExtractKey, _EqualKey, _Alloc>
 154           const_iterator;
 155   typedef _Hashtable_node<_Val> _Node;
 156
 157   typedef forward_iterator_tag iterator_category;
 158   typedef _Val value_type;
 159   typedef ptrdiff_t difference_type;
 160   typedef size_t size_type;
 161   typedef const _Val& reference;
 162   typedef const _Val* pointer;
 163
 164   const _Node* _M_cur;
 165   const _Hashtable* _M_ht;
 166
 167   _Hashtable_const_iterator(const _Node* __n, const _Hashtable* __tab)
 168     : _M_cur(__n), _M_ht(__tab) {}
 169   _Hashtable_const_iterator() {}
 170   _Hashtable_const_iterator(const iterator& __it)
 171     : _M_cur(__it._M_cur), _M_ht(__it._M_ht) {}
 172   reference operator*() const { return _M_cur->_M_val; }
 173   pointer operator->() const { return &(operator*()); }
 174   const_iterator& operator++();
 175   const_iterator operator++(int);
 176   bool operator==(const const_iterator& __it) const
 177     { return _M_cur == __it._M_cur; }
 178   bool operator!=(const const_iterator& __it) const
 179     { return _M_cur != __it._M_cur; }
 180 };
 181
 182 // Note: assumes long is at least 32 bits.
 183 enum { _S_num_primes = 28 };
 184
 185 static const unsigned long __stl_prime_list[_S_num_primes] =
 186 {
 187   53ul,         97ul,         193ul,       389ul,       769ul,
 188   1543ul,       3079ul,       6151ul,      12289ul,     24593ul,
 189   49157ul,      98317ul,      196613ul,    393241ul,    786433ul,
 190   1572869ul,    3145739ul,    6291469ul,   12582917ul,  25165843ul,
 191   50331653ul,   100663319ul,  201326611ul, 402653189ul, 805306457ul,
 192   1610612741ul, 3221225473ul, 4294967291ul
 193 };
 194
 195 inline unsigned long __stl_next_prime(unsigned long __n)
 196 {
 197   const unsigned long* __first = __stl_prime_list;
 198   const unsigned long* __last = __stl_prime_list + (int)_S_num_primes;
 199   const unsigned long* pos = std::lower_bound(__first, __last, __n);
 200   return pos == __last ? *(__last - 1) : *pos;
 201 }
 202
 203 // Forward declaration of operator==.
 204
 205 template <class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
 206 class hashtable;
 207
 208 template <class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
 209 bool operator==(const hashtable<_Val,_Key,_HF,_Ex,_Eq,_All>& __ht1,
 210                 const hashtable<_Val,_Key,_HF,_Ex,_Eq,_All>& __ht2);
 211
 212
 213 // Hashtables handle allocators a bit differently than other
 214 // containers do.  If we're using standard-conforming allocators, then
 215 // a hashtable unconditionally has a member variable to hold its
 216 // allocator, even if it so happens that all instances of the
 217 // allocator type are identical.  This is because, for hashtables,
 218 // this extra storage is negligible.  Additionally, a base class
 219 // wouldn't serve any other purposes; it wouldn't, for example,
 220 // 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)_S_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     // Check same length of lists
 612     for ( ; __cur1 && __cur2;
 613           __cur1 = __cur1->_M_next, __cur2 = __cur2->_M_next)
 614       {}
 615     if (__cur1 || __cur2)
 616       return false;
 617     // Now check one's elements are in the other
 618     for (__cur1 = __ht1._M_buckets[__n] ; __cur1; __cur1 = __cur1->_M_next)
 619     {
 620       bool _found__cur1 = false;
 621       for (_Node* __cur2 = __ht2._M_buckets[__n];
 622            __cur2; __cur2 = __cur2->_M_next)
 623       {
 624         if (__cur1->_M_val == __cur2->_M_val)
 625         {
 626           _found__cur1 = true;
 627           break;
 628         }
 629       }
 630       if (!_found__cur1)
 631         return false;
 632     }
 633   }
 634   return true;
 635 }
 636
 637 template <class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
 638 inline bool operator!=(const hashtable<_Val,_Key,_HF,_Ex,_Eq,_All>& __ht1,
 639                        const hashtable<_Val,_Key,_HF,_Ex,_Eq,_All>& __ht2) {
 640   return !(__ht1 == __ht2);
 641 }
 642
 643 template <class _Val, class _Key, class _HF, class _Extract, class _EqKey,
 644           class _All>
 645 inline void swap(hashtable<_Val, _Key, _HF, _Extract, _EqKey, _All>& __ht1,
 646                  hashtable<_Val, _Key, _HF, _Extract, _EqKey, _All>& __ht2) {
 647   __ht1.swap(__ht2);
 648 }
 649
 650
 651 template <class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
 652 pair<typename hashtable<_Val,_Key,_HF,_Ex,_Eq,_All>::iterator, bool>
 653 hashtable<_Val,_Key,_HF,_Ex,_Eq,_All>
 654   ::insert_unique_noresize(const value_type& __obj)
 655 {
 656   const size_type __n = _M_bkt_num(__obj);
 657   _Node* __first = _M_buckets[__n];
 658
 659   for (_Node* __cur = __first; __cur; __cur = __cur->_M_next)
 660     if (_M_equals(_M_get_key(__cur->_M_val), _M_get_key(__obj)))
 661       return pair<iterator, bool>(iterator(__cur, this), false);
 662
 663   _Node* __tmp = _M_new_node(__obj);
 664   __tmp->_M_next = __first;
 665   _M_buckets[__n] = __tmp;
 666   ++_M_num_elements;
 667   return pair<iterator, bool>(iterator(__tmp, this), true);
 668 }
 669
 670 template <class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
 671 typename hashtable<_Val,_Key,_HF,_Ex,_Eq,_All>::iterator
 672 hashtable<_Val,_Key,_HF,_Ex,_Eq,_All>
 673   ::insert_equal_noresize(const value_type& __obj)
 674 {
 675   const size_type __n = _M_bkt_num(__obj);
 676   _Node* __first = _M_buckets[__n];
 677
 678   for (_Node* __cur = __first; __cur; __cur = __cur->_M_next)
 679     if (_M_equals(_M_get_key(__cur->_M_val), _M_get_key(__obj))) {
 680       _Node* __tmp = _M_new_node(__obj);
 681       __tmp->_M_next = __cur->_M_next;
 682       __cur->_M_next = __tmp;
 683       ++_M_num_elements;
 684       return iterator(__tmp, this);
 685     }
 686
 687   _Node* __tmp = _M_new_node(__obj);
 688   __tmp->_M_next = __first;
 689   _M_buckets[__n] = __tmp;
 690   ++_M_num_elements;
 691   return iterator(__tmp, this);
 692 }
 693
 694 template <class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
 695 typename hashtable<_Val,_Key,_HF,_Ex,_Eq,_All>::reference
 696 hashtable<_Val,_Key,_HF,_Ex,_Eq,_All>::find_or_insert(const value_type& __obj)
 697 {
 698   resize(_M_num_elements + 1);
 699
 700   size_type __n = _M_bkt_num(__obj);
 701   _Node* __first = _M_buckets[__n];
 702
 703   for (_Node* __cur = __first; __cur; __cur = __cur->_M_next)
 704     if (_M_equals(_M_get_key(__cur->_M_val), _M_get_key(__obj)))
 705       return __cur->_M_val;
 706
 707   _Node* __tmp = _M_new_node(__obj);
 708   __tmp->_M_next = __first;
 709   _M_buckets[__n] = __tmp;
 710   ++_M_num_elements;
 711   return __tmp->_M_val;
 712 }
 713
 714 template <class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
 715 pair<typename hashtable<_Val,_Key,_HF,_Ex,_Eq,_All>::iterator,
 716      typename hashtable<_Val,_Key,_HF,_Ex,_Eq,_All>::iterator>
 717 hashtable<_Val,_Key,_HF,_Ex,_Eq,_All>::equal_range(const key_type& __key)
 718 {
 719   typedef pair<iterator, iterator> _Pii;
 720   const size_type __n = _M_bkt_num_key(__key);
 721
 722   for (_Node* __first = _M_buckets[__n]; __first; __first = __first->_M_next)
 723     if (_M_equals(_M_get_key(__first->_M_val), __key)) {
 724       for (_Node* __cur = __first->_M_next; __cur; __cur = __cur->_M_next)
 725         if (!_M_equals(_M_get_key(__cur->_M_val), __key))
 726           return _Pii(iterator(__first, this), iterator(__cur, this));
 727       for (size_type __m = __n + 1; __m < _M_buckets.size(); ++__m)
 728         if (_M_buckets[__m])
 729           return _Pii(iterator(__first, this),
 730                      iterator(_M_buckets[__m], this));
 731       return _Pii(iterator(__first, this), end());
 732     }
 733   return _Pii(end(), end());
 734 }
 735
 736 template <class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
 737 pair<typename hashtable<_Val,_Key,_HF,_Ex,_Eq,_All>::const_iterator,
 738      typename hashtable<_Val,_Key,_HF,_Ex,_Eq,_All>::const_iterator>
 739 hashtable<_Val,_Key,_HF,_Ex,_Eq,_All>
 740   ::equal_range(const key_type& __key) const
 741 {
 742   typedef pair<const_iterator, const_iterator> _Pii;
 743   const size_type __n = _M_bkt_num_key(__key);
 744
 745   for (const _Node* __first = _M_buckets[__n] ;
 746        __first;
 747        __first = __first->_M_next) {
 748     if (_M_equals(_M_get_key(__first->_M_val), __key)) {
 749       for (const _Node* __cur = __first->_M_next;
 750            __cur;
 751            __cur = __cur->_M_next)
 752         if (!_M_equals(_M_get_key(__cur->_M_val), __key))
 753           return _Pii(const_iterator(__first, this),
 754                       const_iterator(__cur, this));
 755       for (size_type __m = __n + 1; __m < _M_buckets.size(); ++__m)
 756         if (_M_buckets[__m])
 757           return _Pii(const_iterator(__first, this),
 758                       const_iterator(_M_buckets[__m], this));
 759       return _Pii(const_iterator(__first, this), end());
 760     }
 761   }
 762   return _Pii(end(), end());
 763 }
 764
 765 template <class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
 766 typename hashtable<_Val,_Key,_HF,_Ex,_Eq,_All>::size_type
 767 hashtable<_Val,_Key,_HF,_Ex,_Eq,_All>::erase(const key_type& __key)
 768 {
 769   const size_type __n = _M_bkt_num_key(__key);
 770   _Node* __first = _M_buckets[__n];
 771   size_type __erased = 0;
 772
 773   if (__first) {
 774     _Node* __cur = __first;
 775     _Node* __next = __cur->_M_next;
 776     while (__next) {
 777       if (_M_equals(_M_get_key(__next->_M_val), __key)) {
 778         __cur->_M_next = __next->_M_next;
 779         _M_delete_node(__next);
 780         __next = __cur->_M_next;
 781         ++__erased;
 782         --_M_num_elements;
 783       }
 784       else {
 785         __cur = __next;
 786         __next = __cur->_M_next;
 787       }
 788     }
 789     if (_M_equals(_M_get_key(__first->_M_val), __key)) {
 790       _M_buckets[__n] = __first->_M_next;
 791       _M_delete_node(__first);
 792       ++__erased;
 793       --_M_num_elements;
 794     }
 795   }
 796   return __erased;
 797 }
 798
 799 template <class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
 800 void hashtable<_Val,_Key,_HF,_Ex,_Eq,_All>::erase(const iterator& __it)
 801 {
 802   _Node* __p = __it._M_cur;
 803   if (__p) {
 804     const size_type __n = _M_bkt_num(__p->_M_val);
 805     _Node* __cur = _M_buckets[__n];
 806
 807     if (__cur == __p) {
 808       _M_buckets[__n] = __cur->_M_next;
 809       _M_delete_node(__cur);
 810       --_M_num_elements;
 811     }
 812     else {
 813       _Node* __next = __cur->_M_next;
 814       while (__next) {
 815         if (__next == __p) {
 816           __cur->_M_next = __next->_M_next;
 817           _M_delete_node(__next);
 818           --_M_num_elements;
 819           break;
 820         }
 821         else {
 822           __cur = __next;
 823           __next = __cur->_M_next;
 824         }
 825       }
 826     }
 827   }
 828 }
 829
 830 template <class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
 831 void hashtable<_Val,_Key,_HF,_Ex,_Eq,_All>
 832   ::erase(iterator __first, iterator __last)
 833 {
 834   size_type __f_bucket = __first._M_cur ?
 835     _M_bkt_num(__first._M_cur->_M_val) : _M_buckets.size();
 836   size_type __l_bucket = __last._M_cur ?
 837     _M_bkt_num(__last._M_cur->_M_val) : _M_buckets.size();
 838
 839   if (__first._M_cur == __last._M_cur)
 840     return;
 841   else if (__f_bucket == __l_bucket)
 842     _M_erase_bucket(__f_bucket, __first._M_cur, __last._M_cur);
 843   else {
 844     _M_erase_bucket(__f_bucket, __first._M_cur, 0);
 845     for (size_type __n = __f_bucket + 1; __n < __l_bucket; ++__n)
 846       _M_erase_bucket(__n, 0);
 847     if (__l_bucket != _M_buckets.size())
 848       _M_erase_bucket(__l_bucket, __last._M_cur);
 849   }
 850 }
 851
 852 template <class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
 853 inline void
 854 hashtable<_Val,_Key,_HF,_Ex,_Eq,_All>::erase(const_iterator __first,
 855                                              const_iterator __last)
 856 {
 857   erase(iterator(const_cast<_Node*>(__first._M_cur),
 858                  const_cast<hashtable*>(__first._M_ht)),
 859         iterator(const_cast<_Node*>(__last._M_cur),
 860                  const_cast<hashtable*>(__last._M_ht)));
 861 }
 862
 863 template <class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
 864 inline void
 865 hashtable<_Val,_Key,_HF,_Ex,_Eq,_All>::erase(const const_iterator& __it)
 866 {
 867   erase(iterator(const_cast<_Node*>(__it._M_cur),
 868                  const_cast<hashtable*>(__it._M_ht)));
 869 }
 870
 871 template <class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
 872 void hashtable<_Val,_Key,_HF,_Ex,_Eq,_All>
 873   ::resize(size_type __num_elements_hint)
 874 {
 875   const size_type __old_n = _M_buckets.size();
 876   if (__num_elements_hint > __old_n) {
 877     const size_type __n = _M_next_size(__num_elements_hint);
 878     if (__n > __old_n) {
 879       vector<_Node*, _All> __tmp(__n, (_Node*)(0),
 880                                  _M_buckets.get_allocator());
 881       try {
 882         for (size_type __bucket = 0; __bucket < __old_n; ++__bucket) {
 883           _Node* __first = _M_buckets[__bucket];
 884           while (__first) {
 885             size_type __new_bucket = _M_bkt_num(__first->_M_val, __n);
 886             _M_buckets[__bucket] = __first->_M_next;
 887             __first->_M_next = __tmp[__new_bucket];
 888             __tmp[__new_bucket] = __first;
 889             __first = _M_buckets[__bucket];
 890           }
 891         }
 892         _M_buckets.swap(__tmp);
 893       }
 894       catch(...) {
 895         for (size_type __bucket = 0; __bucket < __tmp.size(); ++__bucket) {
 896           while (__tmp[__bucket]) {
 897             _Node* __next = __tmp[__bucket]->_M_next;
 898             _M_delete_node(__tmp[__bucket]);
 899             __tmp[__bucket] = __next;
 900           }
 901         }
 902         __throw_exception_again;
 903       }
 904     }
 905   }
 906 }
 907
 908 template <class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
 909 void hashtable<_Val,_Key,_HF,_Ex,_Eq,_All>
 910   ::_M_erase_bucket(const size_type __n, _Node* __first, _Node* __last)
 911 {
 912   _Node* __cur = _M_buckets[__n];
 913   if (__cur == __first)
 914     _M_erase_bucket(__n, __last);
 915   else {
 916     _Node* __next;
 917     for (__next = __cur->_M_next;
 918          __next != __first;
 919          __cur = __next, __next = __cur->_M_next)
 920       ;
 921     while (__next != __last) {
 922       __cur->_M_next = __next->_M_next;
 923       _M_delete_node(__next);
 924       __next = __cur->_M_next;
 925       --_M_num_elements;
 926     }
 927   }
 928 }
 929
 930 template <class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
 931 void hashtable<_Val,_Key,_HF,_Ex,_Eq,_All>
 932   ::_M_erase_bucket(const size_type __n, _Node* __last)
 933 {
 934   _Node* __cur = _M_buckets[__n];
 935   while (__cur != __last) {
 936     _Node* __next = __cur->_M_next;
 937     _M_delete_node(__cur);
 938     __cur = __next;
 939     _M_buckets[__n] = __cur;
 940     --_M_num_elements;
 941   }
 942 }
 943
 944 template <class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
 945 void hashtable<_Val,_Key,_HF,_Ex,_Eq,_All>::clear()
 946 {
 947   for (size_type __i = 0; __i < _M_buckets.size(); ++__i) {
 948     _Node* __cur = _M_buckets[__i];
 949     while (__cur != 0) {
 950       _Node* __next = __cur->_M_next;
 951       _M_delete_node(__cur);
 952       __cur = __next;
 953     }
 954     _M_buckets[__i] = 0;
 955   }
 956   _M_num_elements = 0;
 957 }
 958
 959
 960 template <class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
 961 void hashtable<_Val,_Key,_HF,_Ex,_Eq,_All>
 962   ::_M_copy_from(const hashtable& __ht)
 963 {
 964   _M_buckets.clear();
 965   _M_buckets.reserve(__ht._M_buckets.size());
 966   _M_buckets.insert(_M_buckets.end(), __ht._M_buckets.size(), (_Node*) 0);
 967   try {
 968     for (size_type __i = 0; __i < __ht._M_buckets.size(); ++__i) {
 969       const _Node* __cur = __ht._M_buckets[__i];
 970       if (__cur) {
 971         _Node* __local_copy = _M_new_node(__cur->_M_val);
 972         _M_buckets[__i] = __local_copy;
 973
 974         for (_Node* __next = __cur->_M_next;
 975              __next;
 976              __cur = __next, __next = __cur->_M_next) {
 977           __local_copy->_M_next = _M_new_node(__next->_M_val);
 978           __local_copy = __local_copy->_M_next;
 979         }
 980       }
 981     }
 982     _M_num_elements = __ht._M_num_elements;
 983   }
 984   catch(...)
 985     {
 986       clear();
 987       __throw_exception_again;
 988     }
 989 }
 990 } // namespace __gnu_cxx
 991
 992 #endif