The C and C++ Include Header Files

/usr/include/c++/11/tr1/hashtable.h


$ cat -n /usr/include/c++/11/tr1/hashtable.h

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