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

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