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

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