l4/pkg/libstdc++-v3/contrib/libstdc++-v3-4.3.3/include/tr1_impl/hashtable

   1 // Internal header for TR1 unordered_set and unordered_map -*- C++ -*-
   2
   3 // Copyright (C) 2007 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 2, 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 // You should have received a copy of the GNU General Public License along
  17 // with this library; see the file COPYING.  If not, write to the Free
  18 // Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,
  19 // USA.
  20
  21 // As a special exception, you may use this file as part of a free software
  22 // library without restriction.  Specifically, if other files instantiate
  23 // templates or use macros or inline functions from this file, or you compile
  24 // this file and link it with other files to produce an executable, this
  25 // file does not by itself cause the resulting executable to be covered by
  26 // the GNU General Public License.  This exception does not however
  27 // invalidate any other reasons why the executable file might be covered by
  28 // the GNU General Public License.
  29
  30 /** @file tr1_impl/hashtable
  31  *  This is an internal header file, included by other library headers.
  32  *  You should not attempt to use it directly.
  33  */
  34
  35 // This header file defines std::tr1::hashtable, which is used to
  36 // implement std::tr1::unordered_set, std::tr1::unordered_map,
  37 // std::tr1::unordered_multiset, and std::tr1::unordered_multimap.
  38 // hashtable has many template parameters, partly to accommodate
  39 // the differences between those four classes and partly to
  40 // accommodate policy choices that go beyond TR1 specifications.
  41
  42 // Class template hashtable attempts to encapsulate all reasonable
  43 // variation among hash tables that use chaining.  It does not handle
  44 // open addressing.
  45
  46 // References:
  47 // M. Austern, "A Proposal to Add Hash Tables to the Standard
  48 //    Library (revision 4)," WG21 Document N1456=03-0039, 2003.
  49 // D. E. Knuth, The Art of Computer Programming, v. 3, Sorting and Searching.
  50 // A. Tavori and V. Dreizin, "Policy-Based Data Structures", 2004.
  51 // http://gcc.gnu.org/onlinedocs/libstdc++/ext/pb_ds/index.html
  52
  53 #include <tr1_impl/hashtable_policy.h>
  54
  55 namespace std
  56 {
  57 _GLIBCXX_BEGIN_NAMESPACE_TR1
  58
  59   // Class template _Hashtable, class definition.
  60
  61   // Meaning of class template _Hashtable's template parameters
  62
  63   // _Key and _Value: arbitrary CopyConstructible types.
  64
  65   // _Allocator: an allocator type ([lib.allocator.requirements]) whose
  66   // value type is Value.  As a conforming extension, we allow for
  67   // value type != Value.
  68
  69   // _ExtractKey: function object that takes a object of type Value
  70   // and returns a value of type _Key.
  71
  72   // _Equal: function object that takes two objects of type k and returns
  73   // a bool-like value that is true if the two objects are considered equal.
  74
  75   // _H1: the hash function.  A unary function object with argument type
  76   // Key and result type size_t.  Return values should be distributed
  77   // over the entire range [0, numeric_limits<size_t>:::max()].
  78
  79   // _H2: the range-hashing function (in the terminology of Tavori and
  80   // Dreizin).  A binary function object whose argument types and result
  81   // type are all size_t.  Given arguments r and N, the return value is
  82   // in the range [0, N).
  83
  84   // _Hash: the ranged hash function (Tavori and Dreizin). A binary function
  85   // whose argument types are _Key and size_t and whose result type is
  86   // size_t.  Given arguments k and N, the return value is in the range
  87   // [0, N).  Default: hash(k, N) = h2(h1(k), N).  If _Hash is anything other
  88   // than the default, _H1 and _H2 are ignored.
  89
  90   // _RehashPolicy: Policy class with three members, all of which govern
  91   // the bucket count. _M_next_bkt(n) returns a bucket count no smaller
  92   // than n.  _M_bkt_for_elements(n) returns a bucket count appropriate
  93   // for an element count of n.  _M_need_rehash(n_bkt, n_elt, n_ins)
  94   // determines whether, if the current bucket count is n_bkt and the
  95   // current element count is n_elt, we need to increase the bucket
  96   // count.  If so, returns make_pair(true, n), where n is the new
  97   // bucket count.  If not, returns make_pair(false, <anything>).
  98
  99   // ??? Right now it is hard-wired that the number of buckets never
 100   // shrinks.  Should we allow _RehashPolicy to change that?
 101
 102   // __cache_hash_code: bool.  true if we store the value of the hash
 103   // function along with the value.  This is a time-space tradeoff.
 104   // Storing it may improve lookup speed by reducing the number of times
 105   // we need to call the Equal function.
 106
 107   // __constant_iterators: bool.  true if iterator and const_iterator are
 108   // both constant iterator types.  This is true for unordered_set and
 109   // unordered_multiset, false for unordered_map and unordered_multimap.
 110
 111   // __unique_keys: bool.  true if the return value of _Hashtable::count(k)
 112   // is always at most one, false if it may be an arbitrary number.  This
 113   // true for unordered_set and unordered_map, false for unordered_multiset
 114   // and unordered_multimap.
 115
 116   template<typename _Key, typename _Value, typename _Allocator,
 117            typename _ExtractKey, typename _Equal,
 118            typename _H1, typename _H2, typename _Hash,
 119            typename _RehashPolicy,
 120            bool __cache_hash_code,
 121            bool __constant_iterators,
 122            bool __unique_keys>
 123     class _Hashtable
 124     : public __detail::_Rehash_base<_RehashPolicy,
 125                                     _Hashtable<_Key, _Value, _Allocator,
 126                                                _ExtractKey,
 127                                                _Equal, _H1, _H2, _Hash,
 128                                                _RehashPolicy,
 129                                                __cache_hash_code,
 130                                                __constant_iterators,
 131                                                __unique_keys> >,
 132       public __detail::_Hash_code_base<_Key, _Value, _ExtractKey, _Equal,
 133                                        _H1, _H2, _Hash, __cache_hash_code>,
 134       public __detail::_Map_base<_Key, _Value, _ExtractKey, __unique_keys,
 135                                  _Hashtable<_Key, _Value, _Allocator,
 136                                             _ExtractKey,
 137                                             _Equal, _H1, _H2, _Hash,
 138                                             _RehashPolicy,
 139                                             __cache_hash_code,
 140                                             __constant_iterators,
 141                                             __unique_keys> >
 142     {
 143     public:
 144       typedef _Allocator                                  allocator_type;
 145       typedef _Value                                      value_type;
 146       typedef _Key                                        key_type;
 147       typedef _Equal                                      key_equal;
 148       // mapped_type, if present, comes from _Map_base.
 149       // hasher, if present, comes from _Hash_code_base.
 150       typedef typename _Allocator::difference_type        difference_type;
 151       typedef typename _Allocator::size_type              size_type;
 152       typedef typename _Allocator::reference              reference;
 153       typedef typename _Allocator::const_reference        const_reference;
 154
 155       typedef __detail::_Node_iterator<value_type, __constant_iterators,
 156                                        __cache_hash_code>
 157                                                           local_iterator;
 158       typedef __detail::_Node_const_iterator<value_type,
 159                                              __constant_iterators,
 160                                              __cache_hash_code>
 161                                                           const_local_iterator;
 162
 163       typedef __detail::_Hashtable_iterator<value_type, __constant_iterators,
 164                                             __cache_hash_code>
 165                                                           iterator;
 166       typedef __detail::_Hashtable_const_iterator<value_type,
 167                                                   __constant_iterators,
 168                                                   __cache_hash_code>
 169                                                           const_iterator;
 170
 171       template<typename _Key2, typename _Value2, typename _Ex2, bool __unique2,
 172                typename _Hashtable2>
 173         friend struct __detail::_Map_base;
 174
 175     private:
 176       typedef __detail::_Hash_node<_Value, __cache_hash_code> _Node;
 177       typedef typename _Allocator::template rebind<_Node>::other
 178                                                         _Node_allocator_type;
 179       typedef typename _Allocator::template rebind<_Node*>::other
 180                                                         _Bucket_allocator_type;
 181
 182       typedef typename _Allocator::template rebind<_Value>::other
 183                                                         _Value_allocator_type;
 184
 185       _Node_allocator_type   _M_node_allocator;
 186       _Node**                _M_buckets;
 187       size_type              _M_bucket_count;
 188       size_type              _M_element_count;
 189       _RehashPolicy          _M_rehash_policy;
 190
 191       _Node*
 192       _M_allocate_node(const value_type& __v);
 193
 194       void
 195       _M_deallocate_node(_Node* __n);
 196
 197       void
 198       _M_deallocate_nodes(_Node**, size_type);
 199
 200       _Node**
 201       _M_allocate_buckets(size_type __n);
 202
 203       void
 204       _M_deallocate_buckets(_Node**, size_type __n);
 205
 206     public:
 207       // Constructor, destructor, assignment, swap
 208       _Hashtable(size_type __bucket_hint,
 209                  const _H1&, const _H2&, const _Hash&,
 210                  const _Equal&, const _ExtractKey&,
 211                  const allocator_type&);
 212
 213       template<typename _InputIterator>
 214         _Hashtable(_InputIterator __first, _InputIterator __last,
 215                    size_type __bucket_hint,
 216                    const _H1&, const _H2&, const _Hash&,
 217                    const _Equal&, const _ExtractKey&,
 218                    const allocator_type&);
 219
 220       _Hashtable(const _Hashtable&);
 221
 222 #ifdef _GLIBCXX_INCLUDE_AS_CXX0X
 223       _Hashtable(_Hashtable&&);
 224 #endif
 225
 226       _Hashtable&
 227       operator=(const _Hashtable&);
 228
 229       ~_Hashtable();
 230
 231 #ifdef _GLIBCXX_INCLUDE_AS_CXX0X
 232       void swap(_Hashtable&&);
 233 #else
 234       void swap(_Hashtable&);
 235 #endif
 236
 237       // Basic container operations
 238       iterator
 239       begin()
 240       {
 241         iterator __i(_M_buckets);
 242         if (!__i._M_cur_node)
 243           __i._M_incr_bucket();
 244         return __i;
 245       }
 246
 247       const_iterator
 248       begin() const
 249       {
 250         const_iterator __i(_M_buckets);
 251         if (!__i._M_cur_node)
 252           __i._M_incr_bucket();
 253         return __i;
 254       }
 255
 256       iterator
 257       end()
 258       { return iterator(_M_buckets + _M_bucket_count); }
 259
 260       const_iterator
 261       end() const
 262       { return const_iterator(_M_buckets + _M_bucket_count); }
 263
 264 #ifdef _GLIBCXX_INCLUDE_AS_CXX0X
 265       const_iterator
 266       cbegin() const
 267       {
 268         const_iterator __i(_M_buckets);
 269         if (!__i._M_cur_node)
 270           __i._M_incr_bucket();
 271         return __i;
 272       }
 273
 274       const_iterator
 275       cend() const
 276       { return const_iterator(_M_buckets + _M_bucket_count); }
 277 #endif
 278
 279       size_type
 280       size() const
 281       { return _M_element_count; }
 282
 283       bool
 284       empty() const
 285       { return size() == 0; }
 286
 287       allocator_type
 288       get_allocator() const
 289       { return allocator_type(_M_node_allocator); }
 290
 291       _Value_allocator_type
 292       _M_get_Value_allocator() const
 293       { return _Value_allocator_type(_M_node_allocator); }
 294
 295       size_type
 296       max_size() const
 297       { return _M_get_Value_allocator().max_size(); }
 298
 299       // Observers
 300       key_equal
 301       key_eq() const
 302       { return this->_M_eq; }
 303
 304       // hash_function, if present, comes from _Hash_code_base.
 305
 306       // Bucket operations
 307       size_type
 308       bucket_count() const
 309       { return _M_bucket_count; }
 310
 311       size_type
 312       max_bucket_count() const
 313       { return max_size(); }
 314
 315       size_type
 316       bucket_size(size_type __n) const
 317       { return std::distance(begin(__n), end(__n)); }
 318
 319       size_type
 320       bucket(const key_type& __k) const
 321       {
 322         return this->_M_bucket_index(__k, this->_M_hash_code(__k),
 323                                      bucket_count());
 324       }
 325
 326       local_iterator
 327       begin(size_type __n)
 328       { return local_iterator(_M_buckets[__n]); }
 329
 330       local_iterator
 331       end(size_type)
 332       { return local_iterator(0); }
 333
 334       const_local_iterator
 335       begin(size_type __n) const
 336       { return const_local_iterator(_M_buckets[__n]); }
 337
 338       const_local_iterator
 339       end(size_type) const
 340       { return const_local_iterator(0); }
 341
 342       float
 343       load_factor() const
 344       {
 345         return static_cast<float>(size()) / static_cast<float>(bucket_count());
 346       }
 347
 348       // max_load_factor, if present, comes from _Rehash_base.
 349
 350       // Generalization of max_load_factor.  Extension, not found in TR1.  Only
 351       // useful if _RehashPolicy is something other than the default.
 352       const _RehashPolicy&
 353       __rehash_policy() const
 354       { return _M_rehash_policy; }
 355
 356       void
 357       __rehash_policy(const _RehashPolicy&);
 358
 359       // Lookup.
 360       iterator
 361       find(const key_type& __k);
 362
 363       const_iterator
 364       find(const key_type& __k) const;
 365
 366       size_type
 367       count(const key_type& __k) const;
 368
 369       std::pair<iterator, iterator>
 370       equal_range(const key_type& __k);
 371
 372       std::pair<const_iterator, const_iterator>
 373       equal_range(const key_type& __k) const;
 374
 375     private:                    // Find, insert and erase helper functions
 376       // ??? This dispatching is a workaround for the fact that we don't
 377       // have partial specialization of member templates; it would be
 378       // better to just specialize insert on __unique_keys.  There may be a
 379       // cleaner workaround.
 380       typedef typename __gnu_cxx::__conditional_type<__unique_keys,
 381                             std::pair<iterator, bool>, iterator>::__type
 382         _Insert_Return_Type;
 383
 384       typedef typename __gnu_cxx::__conditional_type<__unique_keys,
 385                                           std::_Select1st<_Insert_Return_Type>,
 386                                           std::_Identity<_Insert_Return_Type>
 387                                    >::__type
 388         _Insert_Conv_Type;
 389
 390       _Node*
 391       _M_find_node(_Node*, const key_type&,
 392                    typename _Hashtable::_Hash_code_type) const;
 393
 394       iterator
 395       _M_insert_bucket(const value_type&, size_type,
 396                        typename _Hashtable::_Hash_code_type);
 397
 398       std::pair<iterator, bool>
 399       _M_insert(const value_type&, std::_GLIBCXX_TR1 true_type);
 400
 401       iterator
 402       _M_insert(const value_type&, std::_GLIBCXX_TR1 false_type);
 403
 404       void
 405       _M_erase_node(_Node*, _Node**);
 406
 407     public:
 408       // Insert and erase
 409       _Insert_Return_Type
 410       insert(const value_type& __v)
 411       { return _M_insert(__v, std::_GLIBCXX_TR1 integral_constant<bool,
 412                          __unique_keys>()); }
 413
 414       iterator
 415       insert(iterator, const value_type& __v)
 416       { return iterator(_Insert_Conv_Type()(this->insert(__v))); }
 417
 418       const_iterator
 419       insert(const_iterator, const value_type& __v)
 420       { return const_iterator(_Insert_Conv_Type()(this->insert(__v))); }
 421
 422       template<typename _InputIterator>
 423         void
 424         insert(_InputIterator __first, _InputIterator __last);
 425
 426       iterator
 427       erase(iterator);
 428
 429       const_iterator
 430       erase(const_iterator);
 431
 432       size_type
 433       erase(const key_type&);
 434
 435       iterator
 436       erase(iterator, iterator);
 437
 438       const_iterator
 439       erase(const_iterator, const_iterator);
 440
 441       void
 442       clear();
 443
 444       // Set number of buckets to be appropriate for container of n element.
 445       void rehash(size_type __n);
 446
 447     private:
 448       // Unconditionally change size of bucket array to n.
 449       void _M_rehash(size_type __n);
 450     };
 451
 452
 453   // Definitions of class template _Hashtable's out-of-line member functions.
 454   template<typename _Key, typename _Value,
 455            typename _Allocator, typename _ExtractKey, typename _Equal,
 456            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
 457            bool __chc, bool __cit, bool __uk>
 458     typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
 459                         _H1, _H2, _Hash, _RehashPolicy,
 460                         __chc, __cit, __uk>::_Node*
 461     _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
 462                _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
 463     _M_allocate_node(const value_type& __v)
 464     {
 465       _Node* __n = _M_node_allocator.allocate(1);
 466       try
 467         {
 468           _M_get_Value_allocator().construct(&__n->_M_v, __v);
 469           __n->_M_next = 0;
 470           return __n;
 471         }
 472       catch(...)
 473         {
 474           _M_node_allocator.deallocate(__n, 1);
 475           __throw_exception_again;
 476         }
 477     }
 478
 479   template<typename _Key, typename _Value,
 480            typename _Allocator, typename _ExtractKey, typename _Equal,
 481            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
 482            bool __chc, bool __cit, bool __uk>
 483     void
 484     _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
 485                _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
 486     _M_deallocate_node(_Node* __n)
 487     {
 488       _M_get_Value_allocator().destroy(&__n->_M_v);
 489       _M_node_allocator.deallocate(__n, 1);
 490     }
 491
 492   template<typename _Key, typename _Value,
 493            typename _Allocator, typename _ExtractKey, typename _Equal,
 494            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
 495            bool __chc, bool __cit, bool __uk>
 496     void
 497     _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
 498                _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
 499     _M_deallocate_nodes(_Node** __array, size_type __n)
 500     {
 501       for (size_type __i = 0; __i < __n; ++__i)
 502         {
 503           _Node* __p = __array[__i];
 504           while (__p)
 505             {
 506               _Node* __tmp = __p;
 507               __p = __p->_M_next;
 508               _M_deallocate_node(__tmp);
 509             }
 510           __array[__i] = 0;
 511         }
 512     }
 513
 514   template<typename _Key, typename _Value,
 515            typename _Allocator, typename _ExtractKey, typename _Equal,
 516            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
 517            bool __chc, bool __cit, bool __uk>
 518     typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
 519                         _H1, _H2, _Hash, _RehashPolicy,
 520                         __chc, __cit, __uk>::_Node**
 521     _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
 522                _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
 523     _M_allocate_buckets(size_type __n)
 524     {
 525       _Bucket_allocator_type __alloc(_M_node_allocator);
 526
 527       // We allocate one extra bucket to hold a sentinel, an arbitrary
 528       // non-null pointer.  Iterator increment relies on this.
 529       _Node** __p = __alloc.allocate(__n + 1);
 530       std::fill(__p, __p + __n, (_Node*) 0);
 531       __p[__n] = reinterpret_cast<_Node*>(0x1000);
 532       return __p;
 533     }
 534
 535   template<typename _Key, typename _Value,
 536            typename _Allocator, typename _ExtractKey, typename _Equal,
 537            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
 538            bool __chc, bool __cit, bool __uk>
 539     void
 540     _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
 541                _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
 542     _M_deallocate_buckets(_Node** __p, size_type __n)
 543     {
 544       _Bucket_allocator_type __alloc(_M_node_allocator);
 545       __alloc.deallocate(__p, __n + 1);
 546     }
 547
 548   template<typename _Key, typename _Value,
 549            typename _Allocator, typename _ExtractKey, typename _Equal,
 550            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
 551            bool __chc, bool __cit, bool __uk>
 552     _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
 553                _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
 554     _Hashtable(size_type __bucket_hint,
 555                const _H1& __h1, const _H2& __h2, const _Hash& __h,
 556                const _Equal& __eq, const _ExtractKey& __exk,
 557                const allocator_type& __a)
 558     : __detail::_Rehash_base<_RehashPolicy, _Hashtable>(),
 559       __detail::_Hash_code_base<_Key, _Value, _ExtractKey, _Equal,
 560                                 _H1, _H2, _Hash, __chc>(__exk, __eq,
 561                                                         __h1, __h2, __h),
 562       __detail::_Map_base<_Key, _Value, _ExtractKey, __uk, _Hashtable>(),
 563       _M_node_allocator(__a),
 564       _M_bucket_count(0),
 565       _M_element_count(0),
 566       _M_rehash_policy()
 567     {
 568       _M_bucket_count = _M_rehash_policy._M_next_bkt(__bucket_hint);
 569       _M_buckets = _M_allocate_buckets(_M_bucket_count);
 570     }
 571
 572   template<typename _Key, typename _Value,
 573            typename _Allocator, typename _ExtractKey, typename _Equal,
 574            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
 575            bool __chc, bool __cit, bool __uk>
 576     template<typename _InputIterator>
 577       _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
 578                  _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
 579       _Hashtable(_InputIterator __f, _InputIterator __l,
 580                  size_type __bucket_hint,
 581                  const _H1& __h1, const _H2& __h2, const _Hash& __h,
 582                  const _Equal& __eq, const _ExtractKey& __exk,
 583                  const allocator_type& __a)
 584       : __detail::_Rehash_base<_RehashPolicy, _Hashtable>(),
 585         __detail::_Hash_code_base<_Key, _Value, _ExtractKey, _Equal,
 586                                   _H1, _H2, _Hash, __chc>(__exk, __eq,
 587                                                           __h1, __h2, __h),
 588         __detail::_Map_base<_Key, _Value, _ExtractKey, __uk, _Hashtable>(),
 589         _M_node_allocator(__a),
 590         _M_bucket_count(0),
 591         _M_element_count(0),
 592         _M_rehash_policy()
 593       {
 594         _M_bucket_count = std::max(_M_rehash_policy._M_next_bkt(__bucket_hint),
 595                                    _M_rehash_policy.
 596                                    _M_bkt_for_elements(__detail::
 597                                                        __distance_fw(__f,
 598                                                                      __l)));
 599         _M_buckets = _M_allocate_buckets(_M_bucket_count);
 600         try
 601           {
 602             for (; __f != __l; ++__f)
 603               this->insert(*__f);
 604           }
 605         catch(...)
 606           {
 607             clear();
 608             _M_deallocate_buckets(_M_buckets, _M_bucket_count);
 609             __throw_exception_again;
 610           }
 611       }
 612
 613   template<typename _Key, typename _Value,
 614            typename _Allocator, typename _ExtractKey, typename _Equal,
 615            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
 616            bool __chc, bool __cit, bool __uk>
 617     _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
 618                _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
 619     _Hashtable(const _Hashtable& __ht)
 620     : __detail::_Rehash_base<_RehashPolicy, _Hashtable>(__ht),
 621       __detail::_Hash_code_base<_Key, _Value, _ExtractKey, _Equal,
 622                                 _H1, _H2, _Hash, __chc>(__ht),
 623       __detail::_Map_base<_Key, _Value, _ExtractKey, __uk, _Hashtable>(__ht),
 624       _M_node_allocator(__ht._M_node_allocator),
 625       _M_bucket_count(__ht._M_bucket_count),
 626       _M_element_count(__ht._M_element_count),
 627       _M_rehash_policy(__ht._M_rehash_policy)
 628     {
 629       _M_buckets = _M_allocate_buckets(_M_bucket_count);
 630       try
 631         {
 632           for (size_type __i = 0; __i < __ht._M_bucket_count; ++__i)
 633             {
 634               _Node* __n = __ht._M_buckets[__i];
 635               _Node** __tail = _M_buckets + __i;
 636               while (__n)
 637                 {
 638                   *__tail = _M_allocate_node(__n->_M_v);
 639                   this->_M_copy_code(*__tail, __n);
 640                   __tail = &((*__tail)->_M_next);
 641                   __n = __n->_M_next;
 642                 }
 643             }
 644         }
 645       catch(...)
 646         {
 647           clear();
 648           _M_deallocate_buckets(_M_buckets, _M_bucket_count);
 649           __throw_exception_again;
 650         }
 651     }
 652
 653 #ifdef _GLIBCXX_INCLUDE_AS_CXX0X
 654   template<typename _Key, typename _Value,
 655            typename _Allocator, typename _ExtractKey, typename _Equal,
 656            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
 657            bool __chc, bool __cit, bool __uk>
 658     _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
 659                _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
 660     _Hashtable(_Hashtable&& __ht)
 661     : __detail::_Rehash_base<_RehashPolicy, _Hashtable>(__ht),
 662       __detail::_Hash_code_base<_Key, _Value, _ExtractKey, _Equal,
 663                                 _H1, _H2, _Hash, __chc>(__ht),
 664       __detail::_Map_base<_Key, _Value, _ExtractKey, __uk, _Hashtable>(__ht),
 665       _M_node_allocator(__ht._M_node_allocator),
 666       _M_bucket_count(__ht._M_bucket_count),
 667       _M_element_count(__ht._M_element_count),
 668       _M_rehash_policy(__ht._M_rehash_policy),
 669       _M_buckets(__ht._M_buckets)
 670     {
 671       size_type __n_bkt = __ht._M_rehash_policy._M_next_bkt(0);
 672       __ht._M_buckets = __ht._M_allocate_buckets(__n_bkt);
 673       __ht._M_bucket_count = __n_bkt;
 674       __ht._M_element_count = 0;
 675       __ht._M_rehash_policy = _RehashPolicy();
 676     }
 677 #endif
 678
 679   template<typename _Key, typename _Value,
 680            typename _Allocator, typename _ExtractKey, typename _Equal,
 681            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
 682            bool __chc, bool __cit, bool __uk>
 683     _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
 684                _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>&
 685     _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
 686                _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
 687     operator=(const _Hashtable& __ht)
 688     {
 689       _Hashtable __tmp(__ht);
 690       this->swap(__tmp);
 691       return *this;
 692     }
 693
 694   template<typename _Key, typename _Value,
 695            typename _Allocator, typename _ExtractKey, typename _Equal,
 696            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
 697            bool __chc, bool __cit, bool __uk>
 698     _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
 699                _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
 700     ~_Hashtable()
 701     {
 702       clear();
 703       _M_deallocate_buckets(_M_buckets, _M_bucket_count);
 704     }
 705
 706   template<typename _Key, typename _Value,
 707            typename _Allocator, typename _ExtractKey, typename _Equal,
 708            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
 709            bool __chc, bool __cit, bool __uk>
 710     void
 711     _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
 712                _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
 713 #ifdef _GLIBCXX_INCLUDE_AS_CXX0X
 714     swap(_Hashtable&& __x)
 715 #else
 716     swap(_Hashtable& __x)
 717 #endif
 718     {
 719       // The only base class with member variables is hash_code_base.  We
 720       // define _Hash_code_base::_M_swap because different specializations
 721       // have different members.
 722       __detail::_Hash_code_base<_Key, _Value, _ExtractKey, _Equal,
 723         _H1, _H2, _Hash, __chc>::_M_swap(__x);
 724
 725       // _GLIBCXX_RESOLVE_LIB_DEFECTS
 726       // 431. Swapping containers with unequal allocators.
 727       std::__alloc_swap<_Node_allocator_type>::_S_do_it(_M_node_allocator,
 728                                                         __x._M_node_allocator);
 729
 730       std::swap(_M_rehash_policy, __x._M_rehash_policy);
 731       std::swap(_M_buckets, __x._M_buckets);
 732       std::swap(_M_bucket_count, __x._M_bucket_count);
 733       std::swap(_M_element_count, __x._M_element_count);
 734     }
 735
 736   template<typename _Key, typename _Value,
 737            typename _Allocator, typename _ExtractKey, typename _Equal,
 738            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
 739            bool __chc, bool __cit, bool __uk>
 740     void
 741     _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
 742                _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
 743     __rehash_policy(const _RehashPolicy& __pol)
 744     {
 745       _M_rehash_policy = __pol;
 746       size_type __n_bkt = __pol._M_bkt_for_elements(_M_element_count);
 747       if (__n_bkt > _M_bucket_count)
 748         _M_rehash(__n_bkt);
 749     }
 750
 751   template<typename _Key, typename _Value,
 752            typename _Allocator, typename _ExtractKey, typename _Equal,
 753            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
 754            bool __chc, bool __cit, bool __uk>
 755     typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
 756                         _H1, _H2, _Hash, _RehashPolicy,
 757                         __chc, __cit, __uk>::iterator
 758     _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
 759                _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
 760     find(const key_type& __k)
 761     {
 762       typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k);
 763       std::size_t __n = this->_M_bucket_index(__k, __code, _M_bucket_count);
 764       _Node* __p = _M_find_node(_M_buckets[__n], __k, __code);
 765       return __p ? iterator(__p, _M_buckets + __n) : this->end();
 766     }
 767
 768   template<typename _Key, typename _Value,
 769            typename _Allocator, typename _ExtractKey, typename _Equal,
 770            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
 771            bool __chc, bool __cit, bool __uk>
 772     typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
 773                         _H1, _H2, _Hash, _RehashPolicy,
 774                         __chc, __cit, __uk>::const_iterator
 775     _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
 776                _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
 777     find(const key_type& __k) const
 778     {
 779       typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k);
 780       std::size_t __n = this->_M_bucket_index(__k, __code, _M_bucket_count);
 781       _Node* __p = _M_find_node(_M_buckets[__n], __k, __code);
 782       return __p ? const_iterator(__p, _M_buckets + __n) : this->end();
 783     }
 784
 785   template<typename _Key, typename _Value,
 786            typename _Allocator, typename _ExtractKey, typename _Equal,
 787            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
 788            bool __chc, bool __cit, bool __uk>
 789     typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
 790                         _H1, _H2, _Hash, _RehashPolicy,
 791                         __chc, __cit, __uk>::size_type
 792     _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
 793                _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
 794     count(const key_type& __k) const
 795     {
 796       typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k);
 797       std::size_t __n = this->_M_bucket_index(__k, __code, _M_bucket_count);
 798       std::size_t __result = 0;
 799       for (_Node* __p = _M_buckets[__n]; __p; __p = __p->_M_next)
 800         if (this->_M_compare(__k, __code, __p))
 801           ++__result;
 802       return __result;
 803     }
 804
 805   template<typename _Key, typename _Value,
 806            typename _Allocator, typename _ExtractKey, typename _Equal,
 807            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
 808            bool __chc, bool __cit, bool __uk>
 809     std::pair<typename _Hashtable<_Key, _Value, _Allocator,
 810                                   _ExtractKey, _Equal, _H1,
 811                                   _H2, _Hash, _RehashPolicy,
 812                                   __chc, __cit, __uk>::iterator,
 813               typename _Hashtable<_Key, _Value, _Allocator,
 814                                   _ExtractKey, _Equal, _H1,
 815                                   _H2, _Hash, _RehashPolicy,
 816                                   __chc, __cit, __uk>::iterator>
 817     _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
 818                _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
 819     equal_range(const key_type& __k)
 820     {
 821       typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k);
 822       std::size_t __n = this->_M_bucket_index(__k, __code, _M_bucket_count);
 823       _Node** __head = _M_buckets + __n;
 824       _Node* __p = _M_find_node(*__head, __k, __code);
 825
 826       if (__p)
 827         {
 828           _Node* __p1 = __p->_M_next;
 829           for (; __p1; __p1 = __p1->_M_next)
 830             if (!this->_M_compare(__k, __code, __p1))
 831               break;
 832
 833           iterator __first(__p, __head);
 834           iterator __last(__p1, __head);
 835           if (!__p1)
 836             __last._M_incr_bucket();
 837           return std::make_pair(__first, __last);
 838         }
 839       else
 840         return std::make_pair(this->end(), this->end());
 841     }
 842
 843   template<typename _Key, typename _Value,
 844            typename _Allocator, typename _ExtractKey, typename _Equal,
 845            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
 846            bool __chc, bool __cit, bool __uk>
 847     std::pair<typename _Hashtable<_Key, _Value, _Allocator,
 848                                   _ExtractKey, _Equal, _H1,
 849                                   _H2, _Hash, _RehashPolicy,
 850                                   __chc, __cit, __uk>::const_iterator,
 851               typename _Hashtable<_Key, _Value, _Allocator,
 852                                   _ExtractKey, _Equal, _H1,
 853                                   _H2, _Hash, _RehashPolicy,
 854                                   __chc, __cit, __uk>::const_iterator>
 855     _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
 856                _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
 857     equal_range(const key_type& __k) const
 858     {
 859       typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k);
 860       std::size_t __n = this->_M_bucket_index(__k, __code, _M_bucket_count);
 861       _Node** __head = _M_buckets + __n;
 862       _Node* __p = _M_find_node(*__head, __k, __code);
 863
 864       if (__p)
 865         {
 866           _Node* __p1 = __p->_M_next;
 867           for (; __p1; __p1 = __p1->_M_next)
 868             if (!this->_M_compare(__k, __code, __p1))
 869               break;
 870
 871           const_iterator __first(__p, __head);
 872           const_iterator __last(__p1, __head);
 873           if (!__p1)
 874             __last._M_incr_bucket();
 875           return std::make_pair(__first, __last);
 876         }
 877       else
 878         return std::make_pair(this->end(), this->end());
 879     }
 880
 881   // Find the node whose key compares equal to k, beginning the search
 882   // at p (usually the head of a bucket).  Return nil if no node is found.
 883   template<typename _Key, typename _Value,
 884            typename _Allocator, typename _ExtractKey, typename _Equal,
 885            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
 886            bool __chc, bool __cit, bool __uk>
 887     typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey,
 888                         _Equal, _H1, _H2, _Hash, _RehashPolicy,
 889                         __chc, __cit, __uk>::_Node*
 890     _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
 891                _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
 892     _M_find_node(_Node* __p, const key_type& __k,
 893                 typename _Hashtable::_Hash_code_type __code) const
 894     {
 895       for (; __p; __p = __p->_M_next)
 896         if (this->_M_compare(__k, __code, __p))
 897           return __p;
 898       return false;
 899     }
 900
 901   // Insert v in bucket n (assumes no element with its key already present).
 902   template<typename _Key, typename _Value,
 903            typename _Allocator, typename _ExtractKey, typename _Equal,
 904            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
 905            bool __chc, bool __cit, bool __uk>
 906     typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
 907                         _H1, _H2, _Hash, _RehashPolicy,
 908                         __chc, __cit, __uk>::iterator
 909     _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
 910                _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
 911     _M_insert_bucket(const value_type& __v, size_type __n,
 912                     typename _Hashtable::_Hash_code_type __code)
 913     {
 914       std::pair<bool, std::size_t> __do_rehash
 915         = _M_rehash_policy._M_need_rehash(_M_bucket_count,
 916                                           _M_element_count, 1);
 917
 918       // Allocate the new node before doing the rehash so that we don't
 919       // do a rehash if the allocation throws.
 920       _Node* __new_node = _M_allocate_node(__v);
 921
 922       try
 923         {
 924           if (__do_rehash.first)
 925             {
 926               const key_type& __k = this->_M_extract(__v);
 927               __n = this->_M_bucket_index(__k, __code, __do_rehash.second);
 928               _M_rehash(__do_rehash.second);
 929             }
 930
 931           __new_node->_M_next = _M_buckets[__n];
 932           this->_M_store_code(__new_node, __code);
 933           _M_buckets[__n] = __new_node;
 934           ++_M_element_count;
 935           return iterator(__new_node, _M_buckets + __n);
 936         }
 937       catch(...)
 938         {
 939           _M_deallocate_node(__new_node);
 940           __throw_exception_again;
 941         }
 942     }
 943
 944   // Insert v if no element with its key is already present.
 945   template<typename _Key, typename _Value,
 946            typename _Allocator, typename _ExtractKey, typename _Equal,
 947            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
 948            bool __chc, bool __cit, bool __uk>
 949     std::pair<typename _Hashtable<_Key, _Value, _Allocator,
 950                                   _ExtractKey, _Equal, _H1,
 951                                   _H2, _Hash, _RehashPolicy,
 952                                   __chc, __cit, __uk>::iterator, bool>
 953     _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
 954                _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
 955     _M_insert(const value_type& __v, std::_GLIBCXX_TR1 true_type)
 956     {
 957       const key_type& __k = this->_M_extract(__v);
 958       typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k);
 959       size_type __n = this->_M_bucket_index(__k, __code, _M_bucket_count);
 960
 961       if (_Node* __p = _M_find_node(_M_buckets[__n], __k, __code))
 962         return std::make_pair(iterator(__p, _M_buckets + __n), false);
 963       return std::make_pair(_M_insert_bucket(__v, __n, __code), true);
 964     }
 965
 966   // Insert v unconditionally.
 967   template<typename _Key, typename _Value,
 968            typename _Allocator, typename _ExtractKey, typename _Equal,
 969            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
 970            bool __chc, bool __cit, bool __uk>
 971     typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
 972                         _H1, _H2, _Hash, _RehashPolicy,
 973                         __chc, __cit, __uk>::iterator
 974     _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
 975                _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
 976     _M_insert(const value_type& __v, std::_GLIBCXX_TR1 false_type)
 977     {
 978       std::pair<bool, std::size_t> __do_rehash
 979         = _M_rehash_policy._M_need_rehash(_M_bucket_count,
 980                                           _M_element_count, 1);
 981       if (__do_rehash.first)
 982         _M_rehash(__do_rehash.second);
 983
 984       const key_type& __k = this->_M_extract(__v);
 985       typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k);
 986       size_type __n = this->_M_bucket_index(__k, __code, _M_bucket_count);
 987
 988       // First find the node, avoid leaking new_node if compare throws.
 989       _Node* __prev = _M_find_node(_M_buckets[__n], __k, __code);
 990       _Node* __new_node = _M_allocate_node(__v);
 991
 992       if (__prev)
 993         {
 994           __new_node->_M_next = __prev->_M_next;
 995           __prev->_M_next = __new_node;
 996         }
 997       else
 998         {
 999           __new_node->_M_next = _M_buckets[__n];
1000           _M_buckets[__n] = __new_node;
1001         }
1002       this->_M_store_code(__new_node, __code);
1003
1004       ++_M_element_count;
1005       return iterator(__new_node, _M_buckets + __n);
1006     }
1007
1008   // For erase(iterator) and erase(const_iterator).
1009   template<typename _Key, typename _Value,
1010            typename _Allocator, typename _ExtractKey, typename _Equal,
1011            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
1012            bool __chc, bool __cit, bool __uk>
1013     void
1014     _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1015                _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
1016     _M_erase_node(_Node* __p, _Node** __b)
1017     {
1018       _Node* __cur = *__b;
1019       if (__cur == __p)
1020         *__b = __cur->_M_next;
1021       else
1022         {
1023           _Node* __next = __cur->_M_next;
1024           while (__next != __p)
1025             {
1026               __cur = __next;
1027               __next = __cur->_M_next;
1028             }
1029           __cur->_M_next = __next->_M_next;
1030         }
1031
1032       _M_deallocate_node(__p);
1033       --_M_element_count;
1034     }
1035
1036   template<typename _Key, typename _Value,
1037            typename _Allocator, typename _ExtractKey, typename _Equal,
1038            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
1039            bool __chc, bool __cit, bool __uk>
1040     template<typename _InputIterator>
1041       void
1042       _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1043                  _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
1044       insert(_InputIterator __first, _InputIterator __last)
1045       {
1046         size_type __n_elt = __detail::__distance_fw(__first, __last);
1047         std::pair<bool, std::size_t> __do_rehash
1048           = _M_rehash_policy._M_need_rehash(_M_bucket_count,
1049                                             _M_element_count, __n_elt);
1050         if (__do_rehash.first)
1051           _M_rehash(__do_rehash.second);
1052
1053         for (; __first != __last; ++__first)
1054           this->insert(*__first);
1055       }
1056
1057   template<typename _Key, typename _Value,
1058            typename _Allocator, typename _ExtractKey, typename _Equal,
1059            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
1060            bool __chc, bool __cit, bool __uk>
1061     typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1062                         _H1, _H2, _Hash, _RehashPolicy,
1063                         __chc, __cit, __uk>::iterator
1064     _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1065                _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
1066     erase(iterator __it)
1067     {
1068       iterator __result = __it;
1069       ++__result;
1070       _M_erase_node(__it._M_cur_node, __it._M_cur_bucket);
1071       return __result;
1072     }
1073
1074   template<typename _Key, typename _Value,
1075            typename _Allocator, typename _ExtractKey, typename _Equal,
1076            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
1077            bool __chc, bool __cit, bool __uk>
1078     typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1079                         _H1, _H2, _Hash, _RehashPolicy,
1080                         __chc, __cit, __uk>::const_iterator
1081     _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1082                _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
1083     erase(const_iterator __it)
1084     {
1085       const_iterator __result = __it;
1086       ++__result;
1087       _M_erase_node(__it._M_cur_node, __it._M_cur_bucket);
1088       return __result;
1089     }
1090
1091   template<typename _Key, typename _Value,
1092            typename _Allocator, typename _ExtractKey, typename _Equal,
1093            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
1094            bool __chc, bool __cit, bool __uk>
1095     typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1096                         _H1, _H2, _Hash, _RehashPolicy,
1097                         __chc, __cit, __uk>::size_type
1098     _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1099                _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
1100     erase(const key_type& __k)
1101     {
1102       typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k);
1103       std::size_t __n = this->_M_bucket_index(__k, __code, _M_bucket_count);
1104       size_type __result = 0;
1105
1106       _Node** __slot = _M_buckets + __n;
1107       while (*__slot && !this->_M_compare(__k, __code, *__slot))
1108         __slot = &((*__slot)->_M_next);
1109
1110       _Node** __saved_slot = 0;
1111       while (*__slot && this->_M_compare(__k, __code, *__slot))
1112         {
1113           // _GLIBCXX_RESOLVE_LIB_DEFECTS
1114           // 526. Is it undefined if a function in the standard changes
1115           // in parameters?
1116           if (&this->_M_extract((*__slot)->_M_v) != &__k)
1117             {
1118               _Node* __p = *__slot;
1119               *__slot = __p->_M_next;
1120               _M_deallocate_node(__p);
1121               --_M_element_count;
1122               ++__result;
1123             }
1124           else
1125             {
1126               __saved_slot = __slot;
1127               __slot = &((*__slot)->_M_next);
1128             }
1129         }
1130
1131       if (__saved_slot)
1132         {
1133           _Node* __p = *__saved_slot;
1134           *__saved_slot = __p->_M_next;
1135           _M_deallocate_node(__p);
1136           --_M_element_count;
1137           ++__result;
1138         }
1139
1140       return __result;
1141     }
1142
1143   // ??? This could be optimized by taking advantage of the bucket
1144   // structure, but it's not clear that it's worth doing.  It probably
1145   // wouldn't even be an optimization unless the load factor is large.
1146   template<typename _Key, typename _Value,
1147            typename _Allocator, typename _ExtractKey, typename _Equal,
1148            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
1149            bool __chc, bool __cit, bool __uk>
1150     typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1151                         _H1, _H2, _Hash, _RehashPolicy,
1152                         __chc, __cit, __uk>::iterator
1153     _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1154                _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
1155     erase(iterator __first, iterator __last)
1156     {
1157       while (__first != __last)
1158         __first = this->erase(__first);
1159       return __last;
1160     }
1161
1162   template<typename _Key, typename _Value,
1163            typename _Allocator, typename _ExtractKey, typename _Equal,
1164            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
1165            bool __chc, bool __cit, bool __uk>
1166     typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1167                         _H1, _H2, _Hash, _RehashPolicy,
1168                         __chc, __cit, __uk>::const_iterator
1169     _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1170                _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
1171     erase(const_iterator __first, const_iterator __last)
1172     {
1173       while (__first != __last)
1174         __first = this->erase(__first);
1175       return __last;
1176     }
1177
1178   template<typename _Key, typename _Value,
1179            typename _Allocator, typename _ExtractKey, typename _Equal,
1180            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
1181            bool __chc, bool __cit, bool __uk>
1182     void
1183     _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1184                _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
1185     clear()
1186     {
1187       _M_deallocate_nodes(_M_buckets, _M_bucket_count);
1188       _M_element_count = 0;
1189     }
1190
1191   template<typename _Key, typename _Value,
1192            typename _Allocator, typename _ExtractKey, typename _Equal,
1193            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
1194            bool __chc, bool __cit, bool __uk>
1195     void
1196     _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1197                _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
1198     rehash(size_type __n)
1199     {
1200       _M_rehash(std::max(_M_rehash_policy._M_next_bkt(__n),
1201                          _M_rehash_policy._M_bkt_for_elements(_M_element_count
1202                                                               + 1)));
1203     }
1204
1205   template<typename _Key, typename _Value,
1206            typename _Allocator, typename _ExtractKey, typename _Equal,
1207            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
1208            bool __chc, bool __cit, bool __uk>
1209     void
1210     _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1211                _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
1212     _M_rehash(size_type __n)
1213     {
1214       _Node** __new_array = _M_allocate_buckets(__n);
1215       try
1216         {
1217           for (size_type __i = 0; __i < _M_bucket_count; ++__i)
1218             while (_Node* __p = _M_buckets[__i])
1219               {
1220                 std::size_t __new_index = this->_M_bucket_index(__p, __n);
1221                 _M_buckets[__i] = __p->_M_next;
1222                 __p->_M_next = __new_array[__new_index];
1223                 __new_array[__new_index] = __p;
1224               }
1225           _M_deallocate_buckets(_M_buckets, _M_bucket_count);
1226           _M_bucket_count = __n;
1227           _M_buckets = __new_array;
1228         }
1229       catch(...)
1230         {
1231           // A failure here means that a hash function threw an exception.
1232           // We can't restore the previous state without calling the hash
1233           // function again, so the only sensible recovery is to delete
1234           // everything.
1235           _M_deallocate_nodes(__new_array, __n);
1236           _M_deallocate_buckets(__new_array, __n);
1237           _M_deallocate_nodes(_M_buckets, _M_bucket_count);
1238           _M_element_count = 0;
1239           __throw_exception_again;
1240         }
1241     }
1242
1243 _GLIBCXX_END_NAMESPACE_TR1
1244 }