contrib/gcc-5.0/libstdc++-v3/include/backward/hashtable.h

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