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