l4/pkg/l4re-core/libstdc++-v3/contrib/libstdc++-v3-4.5/include/backward/hashtable.h

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