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