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

   1 // Hashtable implementation used by containers -*- C++ -*-
   2
   3 // Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009
   4 // Free Software Foundation, Inc.
   5 //
   6 // This file is part of the GNU ISO C++ Library.  This library is free
   7 // software; you can redistribute it and/or modify it under the
   8 // terms of the GNU General Public License as published by the
   9 // Free Software Foundation; either version 2, or (at your option)
  10 // any later version.
  11
  12 // This library is distributed in the hope that it will be useful,
  13 // but WITHOUT ANY WARRANTY; without even the implied warranty of
  14 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15 // GNU General Public License for more details.
  16
  17 // You should have received a copy of the GNU General Public License along
  18 // with this library; see the file COPYING.  If not, write to the Free
  19 // Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,
  20 // USA.
  21
  22 // As a special exception, you may use this file as part of a free software
  23 // library without restriction.  Specifically, if other files instantiate
  24 // templates or use macros or inline functions from this file, or you compile
  25 // this file and link it with other files to produce an executable, this
  26 // file does not by itself cause the resulting executable to be covered by
  27 // the GNU General Public License.  This exception does not however
  28 // invalidate any other reasons why the executable file might be covered by
  29 // the GNU General Public License.
  30
  31 /*
  32  * Copyright (c) 1996,1997
  33  * Silicon Graphics Computer Systems, Inc.
  34  *
  35  * Permission to use, copy, modify, distribute and sell this software
  36  * and its documentation for any purpose is hereby granted without fee,
  37  * provided that the above copyright notice appear in all copies and
  38  * that both that copyright notice and this permission notice appear
  39  * in supporting documentation.  Silicon Graphics makes no
  40  * representations about the suitability of this software for any
  41  * purpose.  It is provided "as is" without express or implied warranty.
  42  *
  43  *
  44  * Copyright (c) 1994
  45  * Hewlett-Packard Company
  46  *
  47  * Permission to use, copy, modify, distribute and sell this software
  48  * and its documentation for any purpose is hereby granted without fee,
  49  * provided that the above copyright notice appear in all copies and
  50  * that both that copyright notice and this permission notice appear
  51  * in supporting documentation.  Hewlett-Packard Company makes no
  52  * representations about the suitability of this software for any
  53  * purpose.  It is provided "as is" without express or implied warranty.
  54  *
  55  */
  56
  57 /** @file backward/hashtable.h
  58  *  This file is a GNU extension to the Standard C++ Library (possibly
  59  *  containing extensions from the HP/SGI STL subset).
  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 <algorithm>
  71 #include <bits/stl_function.h>
  72 #include <backward/hash_fun.h>
  73
  74 _GLIBCXX_BEGIN_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     {
 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       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
 132       _Hashtable_iterator() { }
 133
 134       reference
 135       operator*() const
 136       { return _M_cur->_M_val; }
 137
 138       pointer
 139       operator->() const
 140       { return &(operator*()); }
 141
 142       iterator&
 143       operator++();
 144
 145       iterator
 146       operator++(int);
 147
 148       bool
 149       operator==(const iterator& __it) const
 150       { return _M_cur == __it._M_cur; }
 151
 152       bool
 153       operator!=(const iterator& __it) const
 154       { return _M_cur != __it._M_cur; }
 155     };
 156
 157   template<class _Val, class _Key, class _HashFcn,
 158            class _ExtractKey, class _EqualKey, class _Alloc>
 159     struct _Hashtable_const_iterator
 160     {
 161       typedef hashtable<_Val, _Key, _HashFcn, _ExtractKey, _EqualKey, _Alloc>
 162         _Hashtable;
 163       typedef _Hashtable_iterator<_Val,_Key,_HashFcn,
 164                                   _ExtractKey,_EqualKey,_Alloc>
 165         iterator;
 166       typedef _Hashtable_const_iterator<_Val, _Key, _HashFcn,
 167                                         _ExtractKey, _EqualKey, _Alloc>
 168         const_iterator;
 169       typedef _Hashtable_node<_Val> _Node;
 170
 171       typedef forward_iterator_tag iterator_category;
 172       typedef _Val value_type;
 173       typedef ptrdiff_t difference_type;
 174       typedef size_t size_type;
 175       typedef const _Val& reference;
 176       typedef const _Val* pointer;
 177
 178       const _Node* _M_cur;
 179       const _Hashtable* _M_ht;
 180
 181       _Hashtable_const_iterator(const _Node* __n, const _Hashtable* __tab)
 182       : _M_cur(__n), _M_ht(__tab) { }
 183
 184       _Hashtable_const_iterator() { }
 185
 186       _Hashtable_const_iterator(const iterator& __it)
 187       : _M_cur(__it._M_cur), _M_ht(__it._M_ht) { }
 188
 189       reference
 190       operator*() const
 191       { return _M_cur->_M_val; }
 192
 193       pointer
 194       operator->() const
 195       { return &(operator*()); }
 196
 197       const_iterator&
 198       operator++();
 199
 200       const_iterator
 201       operator++(int);
 202
 203       bool
 204       operator==(const const_iterator& __it) const
 205       { return _M_cur == __it._M_cur; }
 206
 207       bool
 208       operator!=(const const_iterator& __it) const
 209       { return _M_cur != __it._M_cur; }
 210     };
 211
 212   // Note: assumes long is at least 32 bits.
 213   enum { _S_num_primes = 28 };
 214
 215   static const unsigned long __stl_prime_list[_S_num_primes] =
 216     {
 217       53ul,         97ul,         193ul,       389ul,       769ul,
 218       1543ul,       3079ul,       6151ul,      12289ul,     24593ul,
 219       49157ul,      98317ul,      196613ul,    393241ul,    786433ul,
 220       1572869ul,    3145739ul,    6291469ul,   12582917ul,  25165843ul,
 221       50331653ul,   100663319ul,  201326611ul, 402653189ul, 805306457ul,
 222       1610612741ul, 3221225473ul, 4294967291ul
 223     };
 224
 225   inline unsigned long
 226   __stl_next_prime(unsigned long __n)
 227   {
 228     const unsigned long* __first = __stl_prime_list;
 229     const unsigned long* __last = __stl_prime_list + (int)_S_num_primes;
 230     const unsigned long* pos = std::lower_bound(__first, __last, __n);
 231     return pos == __last ? *(__last - 1) : *pos;
 232   }
 233
 234   // Forward declaration of operator==.
 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   template<class _Val, class _Key, class _HashFcn,
 254            class _ExtractKey, class _EqualKey, class _Alloc>
 255     class hashtable
 256     {
 257     public:
 258       typedef _Key key_type;
 259       typedef _Val value_type;
 260       typedef _HashFcn hasher;
 261       typedef _EqualKey key_equal;
 262
 263       typedef size_t            size_type;
 264       typedef ptrdiff_t         difference_type;
 265       typedef value_type*       pointer;
 266       typedef const value_type* const_pointer;
 267       typedef value_type&       reference;
 268       typedef const value_type& const_reference;
 269
 270       hasher
 271       hash_funct() const
 272       { return _M_hash; }
 273
 274       key_equal
 275       key_eq() const
 276       { return _M_equals; }
 277
 278     private:
 279       typedef _Hashtable_node<_Val> _Node;
 280
 281     public:
 282       typedef typename _Alloc::template rebind<value_type>::other allocator_type;
 283       allocator_type
 284       get_allocator() const
 285       { return _M_node_allocator; }
 286
 287     private:
 288       typedef typename _Alloc::template rebind<_Node>::other _Node_Alloc;
 289       typedef typename _Alloc::template rebind<_Node*>::other _Nodeptr_Alloc;
 290       typedef vector<_Node*, _Nodeptr_Alloc> _Vector_type;
 291
 292       _Node_Alloc _M_node_allocator;
 293
 294       _Node*
 295       _M_get_node()
 296       { return _M_node_allocator.allocate(1); }
 297
 298       void
 299       _M_put_node(_Node* __p)
 300       { _M_node_allocator.deallocate(__p, 1); }
 301
 302     private:
 303       hasher                _M_hash;
 304       key_equal             _M_equals;
 305       _ExtractKey           _M_get_key;
 306       _Vector_type          _M_buckets;
 307       size_type             _M_num_elements;
 308
 309     public:
 310       typedef _Hashtable_iterator<_Val, _Key, _HashFcn, _ExtractKey,
 311                                   _EqualKey, _Alloc>
 312         iterator;
 313       typedef _Hashtable_const_iterator<_Val, _Key, _HashFcn, _ExtractKey,
 314                                         _EqualKey, _Alloc>
 315         const_iterator;
 316
 317       friend struct
 318       _Hashtable_iterator<_Val, _Key, _HashFcn, _ExtractKey, _EqualKey, _Alloc>;
 319
 320       friend struct
 321       _Hashtable_const_iterator<_Val, _Key, _HashFcn, _ExtractKey,
 322                                 _EqualKey, _Alloc>;
 323
 324     public:
 325       hashtable(size_type __n, const _HashFcn& __hf,
 326                 const _EqualKey& __eql, const _ExtractKey& __ext,
 327                 const allocator_type& __a = allocator_type())
 328       : _M_node_allocator(__a), _M_hash(__hf), _M_equals(__eql),
 329         _M_get_key(__ext), _M_buckets(__a), _M_num_elements(0)
 330       { _M_initialize_buckets(__n); }
 331
 332       hashtable(size_type __n, const _HashFcn& __hf,
 333                 const _EqualKey& __eql,
 334                 const allocator_type& __a = allocator_type())
 335       : _M_node_allocator(__a), _M_hash(__hf), _M_equals(__eql),
 336         _M_get_key(_ExtractKey()), _M_buckets(__a), _M_num_elements(0)
 337       { _M_initialize_buckets(__n); }
 338
 339       hashtable(const hashtable& __ht)
 340       : _M_node_allocator(__ht.get_allocator()), _M_hash(__ht._M_hash),
 341       _M_equals(__ht._M_equals), _M_get_key(__ht._M_get_key),
 342       _M_buckets(__ht.get_allocator()), _M_num_elements(0)
 343       { _M_copy_from(__ht); }
 344
 345       hashtable&
 346       operator= (const hashtable& __ht)
 347       {
 348         if (&__ht != this)
 349           {
 350             clear();
 351             _M_hash = __ht._M_hash;
 352             _M_equals = __ht._M_equals;
 353             _M_get_key = __ht._M_get_key;
 354             _M_copy_from(__ht);
 355           }
 356         return *this;
 357       }
 358
 359       ~hashtable()
 360       { clear(); }
 361
 362       size_type
 363       size() const
 364       { return _M_num_elements; }
 365
 366       size_type
 367       max_size() const
 368       { return size_type(-1); }
 369
 370       bool
 371       empty() const
 372       { return size() == 0; }
 373
 374       void
 375       swap(hashtable& __ht)
 376       {
 377         std::swap(_M_hash, __ht._M_hash);
 378         std::swap(_M_equals, __ht._M_equals);
 379         std::swap(_M_get_key, __ht._M_get_key);
 380         _M_buckets.swap(__ht._M_buckets);
 381         std::swap(_M_num_elements, __ht._M_num_elements);
 382       }
 383
 384       iterator
 385       begin()
 386       {
 387         for (size_type __n = 0; __n < _M_buckets.size(); ++__n)
 388           if (_M_buckets[__n])
 389             return iterator(_M_buckets[__n], this);
 390         return end();
 391       }
 392
 393       iterator
 394       end()
 395       { return iterator(0, this); }
 396
 397       const_iterator
 398       begin() const
 399       {
 400         for (size_type __n = 0; __n < _M_buckets.size(); ++__n)
 401           if (_M_buckets[__n])
 402             return const_iterator(_M_buckets[__n], this);
 403         return end();
 404       }
 405
 406       const_iterator
 407       end() const
 408       { return const_iterator(0, this); }
 409
 410       template<class _Vl, class _Ky, class _HF, class _Ex, class _Eq,
 411                 class _Al>
 412         friend bool
 413         operator==(const hashtable<_Vl, _Ky, _HF, _Ex, _Eq, _Al>&,
 414                    const hashtable<_Vl, _Ky, _HF, _Ex, _Eq, _Al>&);
 415
 416     public:
 417       size_type
 418       bucket_count() const
 419       { return _M_buckets.size(); }
 420
 421       size_type
 422       max_bucket_count() const
 423       { return __stl_prime_list[(int)_S_num_primes - 1]; }
 424
 425       size_type
 426       elems_in_bucket(size_type __bucket) const
 427       {
 428         size_type __result = 0;
 429         for (_Node* __n = _M_buckets[__bucket]; __n; __n = __n->_M_next)
 430           __result += 1;
 431         return __result;
 432       }
 433
 434       pair<iterator, bool>
 435       insert_unique(const value_type& __obj)
 436       {
 437         resize(_M_num_elements + 1);
 438         return insert_unique_noresize(__obj);
 439       }
 440
 441       iterator
 442       insert_equal(const value_type& __obj)
 443       {
 444         resize(_M_num_elements + 1);
 445         return insert_equal_noresize(__obj);
 446       }
 447
 448       pair<iterator, bool>
 449       insert_unique_noresize(const value_type& __obj);
 450
 451       iterator
 452       insert_equal_noresize(const value_type& __obj);
 453
 454       template<class _InputIterator>
 455         void
 456         insert_unique(_InputIterator __f, _InputIterator __l)
 457         { insert_unique(__f, __l, __iterator_category(__f)); }
 458
 459       template<class _InputIterator>
 460         void
 461         insert_equal(_InputIterator __f, _InputIterator __l)
 462         { insert_equal(__f, __l, __iterator_category(__f)); }
 463
 464       template<class _InputIterator>
 465         void
 466         insert_unique(_InputIterator __f, _InputIterator __l,
 467                       input_iterator_tag)
 468         {
 469           for ( ; __f != __l; ++__f)
 470             insert_unique(*__f);
 471         }
 472
 473       template<class _InputIterator>
 474         void
 475         insert_equal(_InputIterator __f, _InputIterator __l,
 476                      input_iterator_tag)
 477         {
 478           for ( ; __f != __l; ++__f)
 479             insert_equal(*__f);
 480         }
 481
 482       template<class _ForwardIterator>
 483         void
 484         insert_unique(_ForwardIterator __f, _ForwardIterator __l,
 485                       forward_iterator_tag)
 486         {
 487           size_type __n = distance(__f, __l);
 488           resize(_M_num_elements + __n);
 489           for ( ; __n > 0; --__n, ++__f)
 490             insert_unique_noresize(*__f);
 491         }
 492
 493       template<class _ForwardIterator>
 494         void
 495         insert_equal(_ForwardIterator __f, _ForwardIterator __l,
 496                      forward_iterator_tag)
 497         {
 498           size_type __n = distance(__f, __l);
 499           resize(_M_num_elements + __n);
 500           for ( ; __n > 0; --__n, ++__f)
 501             insert_equal_noresize(*__f);
 502         }
 503
 504       reference
 505       find_or_insert(const value_type& __obj);
 506
 507       iterator
 508       find(const key_type& __key)
 509       {
 510         size_type __n = _M_bkt_num_key(__key);
 511         _Node* __first;
 512         for (__first = _M_buckets[__n];
 513              __first && !_M_equals(_M_get_key(__first->_M_val), __key);
 514              __first = __first->_M_next)
 515           { }
 516         return iterator(__first, this);
 517       }
 518
 519       const_iterator
 520       find(const key_type& __key) const
 521       {
 522         size_type __n = _M_bkt_num_key(__key);
 523         const _Node* __first;
 524         for (__first = _M_buckets[__n];
 525              __first && !_M_equals(_M_get_key(__first->_M_val), __key);
 526              __first = __first->_M_next)
 527           { }
 528         return const_iterator(__first, this);
 529       }
 530
 531       size_type
 532       count(const key_type& __key) const
 533       {
 534         const size_type __n = _M_bkt_num_key(__key);
 535         size_type __result = 0;
 536
 537         for (const _Node* __cur = _M_buckets[__n]; __cur;
 538              __cur = __cur->_M_next)
 539           if (_M_equals(_M_get_key(__cur->_M_val), __key))
 540             ++__result;
 541         return __result;
 542       }
 543
 544       pair<iterator, iterator>
 545       equal_range(const key_type& __key);
 546
 547       pair<const_iterator, const_iterator>
 548       equal_range(const key_type& __key) const;
 549
 550       size_type
 551       erase(const key_type& __key);
 552
 553       void
 554       erase(const iterator& __it);
 555
 556       void
 557       erase(iterator __first, iterator __last);
 558
 559       void
 560       erase(const const_iterator& __it);
 561
 562       void
 563       erase(const_iterator __first, const_iterator __last);
 564
 565       void
 566       resize(size_type __num_elements_hint);
 567
 568       void
 569       clear();
 570
 571     private:
 572       size_type
 573       _M_next_size(size_type __n) const
 574       { return __stl_next_prime(__n); }
 575
 576       void
 577       _M_initialize_buckets(size_type __n)
 578       {
 579         const size_type __n_buckets = _M_next_size(__n);
 580         _M_buckets.reserve(__n_buckets);
 581         _M_buckets.insert(_M_buckets.end(), __n_buckets, (_Node*) 0);
 582         _M_num_elements = 0;
 583       }
 584
 585       size_type
 586       _M_bkt_num_key(const key_type& __key) const
 587       { return _M_bkt_num_key(__key, _M_buckets.size()); }
 588
 589       size_type
 590       _M_bkt_num(const value_type& __obj) const
 591       { return _M_bkt_num_key(_M_get_key(__obj)); }
 592
 593       size_type
 594       _M_bkt_num_key(const key_type& __key, size_t __n) const
 595       { return _M_hash(__key) % __n; }
 596
 597       size_type
 598       _M_bkt_num(const value_type& __obj, size_t __n) const
 599       { return _M_bkt_num_key(_M_get_key(__obj), __n); }
 600
 601       _Node*
 602       _M_new_node(const value_type& __obj)
 603       {
 604         _Node* __n = _M_get_node();
 605         __n->_M_next = 0;
 606         __try
 607           {
 608             this->get_allocator().construct(&__n->_M_val, __obj);
 609             return __n;
 610           }
 611         __catch(...)
 612           {
 613             _M_put_node(__n);
 614             __throw_exception_again;
 615           }
 616       }
 617
 618       void
 619       _M_delete_node(_Node* __n)
 620       {
 621         this->get_allocator().destroy(&__n->_M_val);
 622         _M_put_node(__n);
 623       }
 624
 625       void
 626       _M_erase_bucket(const size_type __n, _Node* __first, _Node* __last);
 627
 628       void
 629       _M_erase_bucket(const size_type __n, _Node* __last);
 630
 631       void
 632       _M_copy_from(const hashtable& __ht);
 633     };
 634
 635   template<class _Val, class _Key, class _HF, class _ExK, class _EqK,
 636             class _All>
 637     _Hashtable_iterator<_Val, _Key, _HF, _ExK, _EqK, _All>&
 638     _Hashtable_iterator<_Val, _Key, _HF, _ExK, _EqK, _All>::
 639     operator++()
 640     {
 641       const _Node* __old = _M_cur;
 642       _M_cur = _M_cur->_M_next;
 643       if (!_M_cur)
 644         {
 645           size_type __bucket = _M_ht->_M_bkt_num(__old->_M_val);
 646           while (!_M_cur && ++__bucket < _M_ht->_M_buckets.size())
 647             _M_cur = _M_ht->_M_buckets[__bucket];
 648         }
 649       return *this;
 650     }
 651
 652   template<class _Val, class _Key, class _HF, class _ExK, class _EqK,
 653             class _All>
 654     inline _Hashtable_iterator<_Val, _Key, _HF, _ExK, _EqK, _All>
 655     _Hashtable_iterator<_Val, _Key, _HF, _ExK, _EqK, _All>::
 656     operator++(int)
 657     {
 658       iterator __tmp = *this;
 659       ++*this;
 660       return __tmp;
 661     }
 662
 663   template<class _Val, class _Key, class _HF, class _ExK, class _EqK,
 664             class _All>
 665     _Hashtable_const_iterator<_Val, _Key, _HF, _ExK, _EqK, _All>&
 666     _Hashtable_const_iterator<_Val, _Key, _HF, _ExK, _EqK, _All>::
 667     operator++()
 668     {
 669       const _Node* __old = _M_cur;
 670       _M_cur = _M_cur->_M_next;
 671       if (!_M_cur)
 672         {
 673           size_type __bucket = _M_ht->_M_bkt_num(__old->_M_val);
 674           while (!_M_cur && ++__bucket < _M_ht->_M_buckets.size())
 675             _M_cur = _M_ht->_M_buckets[__bucket];
 676         }
 677       return *this;
 678     }
 679
 680   template<class _Val, class _Key, class _HF, class _ExK, class _EqK,
 681             class _All>
 682     inline _Hashtable_const_iterator<_Val, _Key, _HF, _ExK, _EqK, _All>
 683     _Hashtable_const_iterator<_Val, _Key, _HF, _ExK, _EqK, _All>::
 684     operator++(int)
 685     {
 686       const_iterator __tmp = *this;
 687       ++*this;
 688       return __tmp;
 689     }
 690
 691   template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
 692     bool
 693     operator==(const hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>& __ht1,
 694                const hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>& __ht2)
 695     {
 696       typedef typename hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::_Node _Node;
 697
 698       if (__ht1._M_buckets.size() != __ht2._M_buckets.size())
 699         return false;
 700
 701       for (size_t __n = 0; __n < __ht1._M_buckets.size(); ++__n)
 702         {
 703           _Node* __cur1 = __ht1._M_buckets[__n];
 704           _Node* __cur2 = __ht2._M_buckets[__n];
 705           // Check same length of lists
 706           for (; __cur1 && __cur2;
 707                __cur1 = __cur1->_M_next, __cur2 = __cur2->_M_next)
 708             { }
 709           if (__cur1 || __cur2)
 710             return false;
 711           // Now check one's elements are in the other
 712           for (__cur1 = __ht1._M_buckets[__n] ; __cur1;
 713                __cur1 = __cur1->_M_next)
 714             {
 715               bool _found__cur1 = false;
 716               for (__cur2 = __ht2._M_buckets[__n];
 717                    __cur2; __cur2 = __cur2->_M_next)
 718                 {
 719                   if (__cur1->_M_val == __cur2->_M_val)
 720                     {
 721                       _found__cur1 = true;
 722                       break;
 723                     }
 724                 }
 725               if (!_found__cur1)
 726                 return false;
 727             }
 728         }
 729       return true;
 730     }
 731
 732   template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
 733     inline bool
 734     operator!=(const hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>& __ht1,
 735                const hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>& __ht2)
 736     { return !(__ht1 == __ht2); }
 737
 738   template<class _Val, class _Key, class _HF, class _Extract, class _EqKey,
 739             class _All>
 740     inline void
 741     swap(hashtable<_Val, _Key, _HF, _Extract, _EqKey, _All>& __ht1,
 742          hashtable<_Val, _Key, _HF, _Extract, _EqKey, _All>& __ht2)
 743     { __ht1.swap(__ht2); }
 744
 745   template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
 746     pair<typename hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::iterator, bool>
 747     hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::
 748     insert_unique_noresize(const value_type& __obj)
 749     {
 750       const size_type __n = _M_bkt_num(__obj);
 751       _Node* __first = _M_buckets[__n];
 752
 753       for (_Node* __cur = __first; __cur; __cur = __cur->_M_next)
 754         if (_M_equals(_M_get_key(__cur->_M_val), _M_get_key(__obj)))
 755           return pair<iterator, bool>(iterator(__cur, this), false);
 756
 757       _Node* __tmp = _M_new_node(__obj);
 758       __tmp->_M_next = __first;
 759       _M_buckets[__n] = __tmp;
 760       ++_M_num_elements;
 761       return pair<iterator, bool>(iterator(__tmp, this), true);
 762     }
 763
 764   template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
 765     typename hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::iterator
 766     hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::
 767     insert_equal_noresize(const value_type& __obj)
 768     {
 769       const size_type __n = _M_bkt_num(__obj);
 770       _Node* __first = _M_buckets[__n];
 771
 772       for (_Node* __cur = __first; __cur; __cur = __cur->_M_next)
 773         if (_M_equals(_M_get_key(__cur->_M_val), _M_get_key(__obj)))
 774           {
 775             _Node* __tmp = _M_new_node(__obj);
 776             __tmp->_M_next = __cur->_M_next;
 777             __cur->_M_next = __tmp;
 778             ++_M_num_elements;
 779             return iterator(__tmp, this);
 780           }
 781
 782       _Node* __tmp = _M_new_node(__obj);
 783       __tmp->_M_next = __first;
 784       _M_buckets[__n] = __tmp;
 785       ++_M_num_elements;
 786       return iterator(__tmp, this);
 787     }
 788
 789   template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
 790     typename hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::reference
 791     hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::
 792     find_or_insert(const value_type& __obj)
 793     {
 794       resize(_M_num_elements + 1);
 795
 796       size_type __n = _M_bkt_num(__obj);
 797       _Node* __first = _M_buckets[__n];
 798
 799       for (_Node* __cur = __first; __cur; __cur = __cur->_M_next)
 800         if (_M_equals(_M_get_key(__cur->_M_val), _M_get_key(__obj)))
 801           return __cur->_M_val;
 802
 803       _Node* __tmp = _M_new_node(__obj);
 804       __tmp->_M_next = __first;
 805       _M_buckets[__n] = __tmp;
 806       ++_M_num_elements;
 807       return __tmp->_M_val;
 808     }
 809
 810   template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
 811     pair<typename hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::iterator,
 812          typename hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::iterator>
 813     hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::
 814     equal_range(const key_type& __key)
 815     {
 816       typedef pair<iterator, iterator> _Pii;
 817       const size_type __n = _M_bkt_num_key(__key);
 818
 819       for (_Node* __first = _M_buckets[__n]; __first;
 820            __first = __first->_M_next)
 821         if (_M_equals(_M_get_key(__first->_M_val), __key))
 822           {
 823             for (_Node* __cur = __first->_M_next; __cur;
 824                  __cur = __cur->_M_next)
 825               if (!_M_equals(_M_get_key(__cur->_M_val), __key))
 826                 return _Pii(iterator(__first, this), iterator(__cur, this));
 827             for (size_type __m = __n + 1; __m < _M_buckets.size(); ++__m)
 828               if (_M_buckets[__m])
 829                 return _Pii(iterator(__first, this),
 830                             iterator(_M_buckets[__m], this));
 831             return _Pii(iterator(__first, this), end());
 832           }
 833       return _Pii(end(), end());
 834     }
 835
 836   template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
 837     pair<typename hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::const_iterator,
 838          typename hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::const_iterator>
 839     hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::
 840     equal_range(const key_type& __key) const
 841     {
 842       typedef pair<const_iterator, const_iterator> _Pii;
 843       const size_type __n = _M_bkt_num_key(__key);
 844
 845       for (const _Node* __first = _M_buckets[__n]; __first;
 846            __first = __first->_M_next)
 847         {
 848           if (_M_equals(_M_get_key(__first->_M_val), __key))
 849             {
 850               for (const _Node* __cur = __first->_M_next; __cur;
 851                    __cur = __cur->_M_next)
 852                 if (!_M_equals(_M_get_key(__cur->_M_val), __key))
 853                   return _Pii(const_iterator(__first, this),
 854                               const_iterator(__cur, this));
 855               for (size_type __m = __n + 1; __m < _M_buckets.size(); ++__m)
 856                 if (_M_buckets[__m])
 857                   return _Pii(const_iterator(__first, this),
 858                               const_iterator(_M_buckets[__m], this));
 859               return _Pii(const_iterator(__first, this), end());
 860             }
 861         }
 862       return _Pii(end(), end());
 863     }
 864
 865   template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
 866     typename hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::size_type
 867     hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::
 868     erase(const key_type& __key)
 869     {
 870       const size_type __n = _M_bkt_num_key(__key);
 871       _Node* __first = _M_buckets[__n];
 872       size_type __erased = 0;
 873
 874       if (__first)
 875         {
 876           _Node* __cur = __first;
 877           _Node* __next = __cur->_M_next;
 878           while (__next)
 879             {
 880               if (_M_equals(_M_get_key(__next->_M_val), __key))
 881                 {
 882                   __cur->_M_next = __next->_M_next;
 883                   _M_delete_node(__next);
 884                   __next = __cur->_M_next;
 885                   ++__erased;
 886                   --_M_num_elements;
 887                 }
 888               else
 889                 {
 890                   __cur = __next;
 891                   __next = __cur->_M_next;
 892                 }
 893             }
 894           if (_M_equals(_M_get_key(__first->_M_val), __key))
 895             {
 896               _M_buckets[__n] = __first->_M_next;
 897               _M_delete_node(__first);
 898               ++__erased;
 899               --_M_num_elements;
 900             }
 901         }
 902       return __erased;
 903     }
 904
 905   template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
 906     void hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::
 907     erase(const iterator& __it)
 908     {
 909       _Node* __p = __it._M_cur;
 910       if (__p)
 911         {
 912           const size_type __n = _M_bkt_num(__p->_M_val);
 913           _Node* __cur = _M_buckets[__n];
 914
 915           if (__cur == __p)
 916             {
 917               _M_buckets[__n] = __cur->_M_next;
 918               _M_delete_node(__cur);
 919               --_M_num_elements;
 920             }
 921           else
 922             {
 923               _Node* __next = __cur->_M_next;
 924               while (__next)
 925                 {
 926                   if (__next == __p)
 927                     {
 928                       __cur->_M_next = __next->_M_next;
 929                       _M_delete_node(__next);
 930                       --_M_num_elements;
 931                       break;
 932                     }
 933                   else
 934                     {
 935                       __cur = __next;
 936                       __next = __cur->_M_next;
 937                     }
 938                 }
 939             }
 940         }
 941     }
 942
 943   template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
 944     void
 945     hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::
 946     erase(iterator __first, iterator __last)
 947     {
 948       size_type __f_bucket = __first._M_cur ? _M_bkt_num(__first._M_cur->_M_val)
 949                                             : _M_buckets.size();
 950
 951       size_type __l_bucket = __last._M_cur ? _M_bkt_num(__last._M_cur->_M_val)
 952                                            : _M_buckets.size();
 953
 954       if (__first._M_cur == __last._M_cur)
 955         return;
 956       else if (__f_bucket == __l_bucket)
 957         _M_erase_bucket(__f_bucket, __first._M_cur, __last._M_cur);
 958       else
 959         {
 960           _M_erase_bucket(__f_bucket, __first._M_cur, 0);
 961           for (size_type __n = __f_bucket + 1; __n < __l_bucket; ++__n)
 962             _M_erase_bucket(__n, 0);
 963           if (__l_bucket != _M_buckets.size())
 964             _M_erase_bucket(__l_bucket, __last._M_cur);
 965         }
 966     }
 967
 968   template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
 969     inline void
 970     hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::
 971     erase(const_iterator __first, const_iterator __last)
 972     {
 973       erase(iterator(const_cast<_Node*>(__first._M_cur),
 974                      const_cast<hashtable*>(__first._M_ht)),
 975             iterator(const_cast<_Node*>(__last._M_cur),
 976                      const_cast<hashtable*>(__last._M_ht)));
 977     }
 978
 979   template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
 980     inline void
 981     hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::
 982     erase(const const_iterator& __it)
 983     { erase(iterator(const_cast<_Node*>(__it._M_cur),
 984                      const_cast<hashtable*>(__it._M_ht))); }
 985
 986   template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
 987     void
 988     hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::
 989     resize(size_type __num_elements_hint)
 990     {
 991       const size_type __old_n = _M_buckets.size();
 992       if (__num_elements_hint > __old_n)
 993         {
 994           const size_type __n = _M_next_size(__num_elements_hint);
 995           if (__n > __old_n)
 996             {
 997               _Vector_type __tmp(__n, (_Node*)(0), _M_buckets.get_allocator());
 998               __try
 999                 {
1000                   for (size_type __bucket = 0; __bucket < __old_n; ++__bucket)
1001                     {
1002                       _Node* __first = _M_buckets[__bucket];
1003                       while (__first)
1004                         {
1005                           size_type __new_bucket = _M_bkt_num(__first->_M_val,
1006                                                               __n);
1007                           _M_buckets[__bucket] = __first->_M_next;
1008                           __first->_M_next = __tmp[__new_bucket];
1009                           __tmp[__new_bucket] = __first;
1010                           __first = _M_buckets[__bucket];
1011                         }
1012                     }
1013                   _M_buckets.swap(__tmp);
1014                 }
1015               __catch(...)
1016                 {
1017                   for (size_type __bucket = 0; __bucket < __tmp.size();
1018                        ++__bucket)
1019                     {
1020                       while (__tmp[__bucket])
1021                         {
1022                           _Node* __next = __tmp[__bucket]->_M_next;
1023                           _M_delete_node(__tmp[__bucket]);
1024                           __tmp[__bucket] = __next;
1025                         }
1026                     }
1027                   __throw_exception_again;
1028                 }
1029             }
1030         }
1031     }
1032
1033   template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
1034     void
1035     hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::
1036     _M_erase_bucket(const size_type __n, _Node* __first, _Node* __last)
1037     {
1038       _Node* __cur = _M_buckets[__n];
1039       if (__cur == __first)
1040         _M_erase_bucket(__n, __last);
1041       else
1042         {
1043           _Node* __next;
1044           for (__next = __cur->_M_next;
1045                __next != __first;
1046                __cur = __next, __next = __cur->_M_next)
1047             ;
1048           while (__next != __last)
1049             {
1050               __cur->_M_next = __next->_M_next;
1051               _M_delete_node(__next);
1052               __next = __cur->_M_next;
1053               --_M_num_elements;
1054             }
1055         }
1056     }
1057
1058   template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
1059     void
1060     hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::
1061     _M_erase_bucket(const size_type __n, _Node* __last)
1062     {
1063       _Node* __cur = _M_buckets[__n];
1064       while (__cur != __last)
1065         {
1066           _Node* __next = __cur->_M_next;
1067           _M_delete_node(__cur);
1068           __cur = __next;
1069           _M_buckets[__n] = __cur;
1070           --_M_num_elements;
1071         }
1072     }
1073
1074   template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
1075     void
1076     hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::
1077     clear()
1078     {
1079       for (size_type __i = 0; __i < _M_buckets.size(); ++__i)
1080         {
1081           _Node* __cur = _M_buckets[__i];
1082           while (__cur != 0)
1083             {
1084               _Node* __next = __cur->_M_next;
1085               _M_delete_node(__cur);
1086               __cur = __next;
1087             }
1088           _M_buckets[__i] = 0;
1089         }
1090       _M_num_elements = 0;
1091     }
1092
1093   template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
1094     void
1095     hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::
1096     _M_copy_from(const hashtable& __ht)
1097     {
1098       _M_buckets.clear();
1099       _M_buckets.reserve(__ht._M_buckets.size());
1100       _M_buckets.insert(_M_buckets.end(), __ht._M_buckets.size(), (_Node*) 0);
1101       __try
1102         {
1103           for (size_type __i = 0; __i < __ht._M_buckets.size(); ++__i) {
1104             const _Node* __cur = __ht._M_buckets[__i];
1105             if (__cur)
1106               {
1107                 _Node* __local_copy = _M_new_node(__cur->_M_val);
1108                 _M_buckets[__i] = __local_copy;
1109
1110                 for (_Node* __next = __cur->_M_next;
1111                      __next;
1112                      __cur = __next, __next = __cur->_M_next)
1113                   {
1114                     __local_copy->_M_next = _M_new_node(__next->_M_val);
1115                     __local_copy = __local_copy->_M_next;
1116                   }
1117               }
1118           }
1119           _M_num_elements = __ht._M_num_elements;
1120         }
1121       __catch(...)
1122         {
1123           clear();
1124           __throw_exception_again;
1125         }
1126     }
1127
1128 _GLIBCXX_END_NAMESPACE
1129
1130 #endif