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

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