FM / tr1

/usr/include/c++/11/tr1

Name	Size	Mode	Actions
array	6983	0644	edit dl rm
bessel_function.tcc	22937	0644	edit dl rm
beta_function.tcc	5995	0644	edit dl rm
ccomplex	1255	0644	edit dl rm
cctype	1478	0644	edit dl rm
cfenv	2070	0644	edit dl rm
cfloat	1380	0644	edit dl rm
cinttypes	2322	0644	edit dl rm
climits	1454	0644	edit dl rm
cmath	43877	0644	edit dl rm
complex	12385	0644	edit dl rm
complex.h	1261	0644	edit dl rm
cstdarg	1246	0644	edit dl rm
cstdbool	1344	0644	edit dl rm
cstdint	2687	0644	edit dl rm
cstdio	1548	0644	edit dl rm
cstdlib	1862	0644	edit dl rm
ctgmath	1248	0644	edit dl rm
ctime	1234	0644	edit dl rm
ctype.h	1209	0644	edit dl rm
cwchar	1784	0644	edit dl rm
cwctype	1525	0644	edit dl rm
ell_integral.tcc	27133	0644	edit dl rm
exp_integral.tcc	16013	0644	edit dl rm
fenv.h	1204	0644	edit dl rm
float.h	1209	0644	edit dl rm
functional	70731	0644	edit dl rm
functional_hash.h	6043	0644	edit dl rm
gamma.tcc	14682	0644	edit dl rm
hashtable.h	41995	0644	edit dl rm
hashtable_policy.h	25086	0644	edit dl rm
hypergeometric.tcc	28066	0644	edit dl rm
inttypes.h	1267	0644	edit dl rm
legendre_function.tcc	10661	0644	edit dl rm
limits.h	1214	0644	edit dl rm
math.h	4553	0644	edit dl rm
memory	1791	0644	edit dl rm
modified_bessel_func.tcc	16260	0644	edit dl rm
poly_hermite.tcc	3925	0644	edit dl rm
poly_laguerre.tcc	11676	0644	edit dl rm
random	1589	0644	edit dl rm
random.h	73098	0644	edit dl rm
random.tcc	53927	0644	edit dl rm
regex	92922	0644	edit dl rm
riemann_zeta.tcc	14067	0644	edit dl rm
shared_ptr.h	33239	0644	edit dl rm
special_function_util.h	5055	0644	edit dl rm
stdarg.h	1214	0644	edit dl rm
stdbool.h	1219	0644	edit dl rm
stdint.h	1214	0644	edit dl rm
stdio.h	1209	0644	edit dl rm
stdlib.h	1487	0644	edit dl rm
tgmath.h	1255	0644	edit dl rm
tuple	12119	0644	edit dl rm
type_traits	19019	0644	edit dl rm
unordered_map	1574	0644	edit dl rm
unordered_map.h	10216	0644	edit dl rm
unordered_set	1574	0644	edit dl rm
unordered_set.h	9540	0644	edit dl rm
utility	3225	0644	edit dl rm
wchar.h	1249	0644	edit dl rm
wctype.h	1255	0644	edit dl rm

Edit: /usr/include/c++/11/tr1/hashtable.h (41995B)

// TR1 hashtable.h header -*- C++ -*-

// Copyright (C) 2007-2021 Free Software Foundation, Inc.
//
// This file is part of the GNU ISO C++ Library.  This library is free
// software; you can redistribute it and/or modify it under the
// terms of the GNU General Public License as published by the
// Free Software Foundation; either version 3, or (at your option)
// any later version.

// This library is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.

// Under Section 7 of GPL version 3, you are granted additional
// permissions described in the GCC Runtime Library Exception, version
// 3.1, as published by the Free Software Foundation.

// You should have received a copy of the GNU General Public License and
// a copy of the GCC Runtime Library Exception along with this program;
// see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
// <http://www.gnu.org/licenses/>.

/** @file tr1/hashtable.h
 *  This is an internal header file, included by other library headers.
 *  Do not attempt to use it directly.
 *  @headername{tr1/unordered_set, tr1/unordered_map}
 */

#ifndef _GLIBCXX_TR1_HASHTABLE_H
#define _GLIBCXX_TR1_HASHTABLE_H 1

#pragma GCC system_header

#include <tr1/hashtable_policy.h>
#include <ext/alloc_traits.h>

namespace std _GLIBCXX_VISIBILITY(default)
{
_GLIBCXX_BEGIN_NAMESPACE_VERSION

namespace tr1
{
  // Class template _Hashtable, class definition.

// Meaning of class template _Hashtable's template parameters

// _Key and _Value: arbitrary CopyConstructible types.

// _Allocator: an allocator type ([lib.allocator.requirements]) whose
  // value type is Value.  As a conforming extension, we allow for
  // value type != Value.

// _ExtractKey: function object that takes a object of type Value
  // and returns a value of type _Key.

// _Equal: function object that takes two objects of type k and returns
  // a bool-like value that is true if the two objects are considered equal.

// _H1: the hash function.  A unary function object with argument type
  // Key and result type size_t.  Return values should be distributed
  // over the entire range [0, numeric_limits<size_t>:::max()].

// _H2: the range-hashing function (in the terminology of Tavori and
  // Dreizin).  A binary function object whose argument types and result
  // type are all size_t.  Given arguments r and N, the return value is
  // in the range [0, N).

// _Hash: the ranged hash function (Tavori and Dreizin). A binary function
  // whose argument types are _Key and size_t and whose result type is
  // size_t.  Given arguments k and N, the return value is in the range
  // [0, N).  Default: hash(k, N) = h2(h1(k), N).  If _Hash is anything other
  // than the default, _H1 and _H2 are ignored.

// _RehashPolicy: Policy class with three members, all of which govern
  // the bucket count. _M_next_bkt(n) returns a bucket count no smaller
  // than n.  _M_bkt_for_elements(n) returns a bucket count appropriate
  // for an element count of n.  _M_need_rehash(n_bkt, n_elt, n_ins)
  // determines whether, if the current bucket count is n_bkt and the
  // current element count is n_elt, we need to increase the bucket
  // count.  If so, returns make_pair(true, n), where n is the new
  // bucket count.  If not, returns make_pair(false, <anything>).

// ??? Right now it is hard-wired that the number of buckets never
  // shrinks.  Should we allow _RehashPolicy to change that?

// __cache_hash_code: bool.  true if we store the value of the hash
  // function along with the value.  This is a time-space tradeoff.
  // Storing it may improve lookup speed by reducing the number of times
  // we need to call the Equal function.

// __constant_iterators: bool.  true if iterator and const_iterator are
  // both constant iterator types.  This is true for unordered_set and
  // unordered_multiset, false for unordered_map and unordered_multimap.

// __unique_keys: bool.  true if the return value of _Hashtable::count(k)
  // is always at most one, false if it may be an arbitrary number.  This
  // true for unordered_set and unordered_map, false for unordered_multiset
  // and unordered_multimap.

template<typename _Key, typename _Value, typename _Allocator,
	   typename _ExtractKey, typename _Equal,
	   typename _H1, typename _H2, typename _Hash,
	   typename _RehashPolicy,
	   bool __cache_hash_code,
	   bool __constant_iterators,
	   bool __unique_keys>
    class _Hashtable
    : public __detail::_Rehash_base<_RehashPolicy,
				    _Hashtable<_Key, _Value, _Allocator,
					       _ExtractKey,
					       _Equal, _H1, _H2, _Hash,
					       _RehashPolicy,
					       __cache_hash_code,
					       __constant_iterators,
					       __unique_keys> >,
      public __detail::_Hash_code_base<_Key, _Value, _ExtractKey, _Equal,
				       _H1, _H2, _Hash, __cache_hash_code>,
      public __detail::_Map_base<_Key, _Value, _ExtractKey, __unique_keys,
				 _Hashtable<_Key, _Value, _Allocator,
					    _ExtractKey,
					    _Equal, _H1, _H2, _Hash,
					    _RehashPolicy,
					    __cache_hash_code,
					    __constant_iterators,
					    __unique_keys> >
    {
      typedef __gnu_cxx::__alloc_traits<_Allocator> _Alloc_traits;

public:
      typedef _Allocator                                  allocator_type;
      typedef _Value                                      value_type;
      typedef _Key                                        key_type;
      typedef _Equal                                      key_equal;
      // mapped_type, if present, comes from _Map_base.
      // hasher, if present, comes from _Hash_code_base.
      typedef typename _Allocator::difference_type        difference_type;
      typedef typename _Allocator::size_type              size_type;
      typedef typename _Alloc_traits::pointer             pointer;
      typedef typename _Alloc_traits::const_pointer       const_pointer;
      typedef typename _Alloc_traits::reference           reference;
      typedef typename _Alloc_traits::const_reference     const_reference;

typedef __detail::_Node_iterator<value_type, __constant_iterators,
				       __cache_hash_code>
							  local_iterator;
      typedef __detail::_Node_const_iterator<value_type,
					     __constant_iterators,
					     __cache_hash_code>
							  const_local_iterator;

typedef __detail::_Hashtable_iterator<value_type, __constant_iterators,
					    __cache_hash_code>
							  iterator;
      typedef __detail::_Hashtable_const_iterator<value_type,
						  __constant_iterators,
						  __cache_hash_code>
							  const_iterator;

template<typename _Key2, typename _Value2, typename _Ex2, bool __unique2,
	       typename _Hashtable2>
	friend struct __detail::_Map_base;

private:
      typedef __detail::_Hash_node<_Value, __cache_hash_code> _Node;
      typedef typename _Alloc_traits::template rebind<_Node>::other
						      _Node_allocator_type;
      typedef typename _Alloc_traits::template rebind<_Node*>::other
						      _Bucket_allocator_type;

typedef typename _Alloc_traits::template rebind<_Value>::other
						      _Value_allocator_type;

_Node_allocator_type   _M_node_allocator;
      _Node**                _M_buckets;
      size_type              _M_bucket_count;
      size_type              _M_element_count;
      _RehashPolicy          _M_rehash_policy;

_Node*
      _M_allocate_node(const value_type& __v);

void
      _M_deallocate_node(_Node* __n);

void
      _M_deallocate_nodes(_Node**, size_type);

_Node**
      _M_allocate_buckets(size_type __n);

void
      _M_deallocate_buckets(_Node**, size_type __n);

public:
      // Constructor, destructor, assignment, swap
      _Hashtable(size_type __bucket_hint,
		 const _H1&, const _H2&, const _Hash&,
		 const _Equal&, const _ExtractKey&,
		 const allocator_type&);

template<typename _InputIterator>
	_Hashtable(_InputIterator __first, _InputIterator __last,
		   size_type __bucket_hint,
		   const _H1&, const _H2&, const _Hash&,
		   const _Equal&, const _ExtractKey&,
		   const allocator_type&);

_Hashtable(const _Hashtable&);

_Hashtable&
      operator=(const _Hashtable&);

~_Hashtable();

void swap(_Hashtable&);

// Basic container operations
      iterator
      begin()
      {
	iterator __i(_M_buckets);
	if (!__i._M_cur_node)
	  __i._M_incr_bucket();
	return __i;
      }

const_iterator
      begin() const
      {
	const_iterator __i(_M_buckets);
	if (!__i._M_cur_node)
	  __i._M_incr_bucket();
	return __i;
      }

iterator
      end()
      { return iterator(_M_buckets + _M_bucket_count); }

const_iterator
      end() const
      { return const_iterator(_M_buckets + _M_bucket_count); }

size_type
      size() const
      { return _M_element_count; }

_GLIBCXX_NODISCARD bool
      empty() const
      { return size() == 0; }

allocator_type
      get_allocator() const
      { return allocator_type(_M_node_allocator); }

_Value_allocator_type
      _M_get_Value_allocator() const
      { return _Value_allocator_type(_M_node_allocator); }

size_type
      max_size() const
      {
	typedef __gnu_cxx::__alloc_traits<_Node_allocator_type> _Traits;
	return _Traits::max_size(_M_node_allocator);
      }

// Observers
      key_equal
      key_eq() const
      { return this->_M_eq; }

// hash_function, if present, comes from _Hash_code_base.

// Bucket operations
      size_type
      bucket_count() const
      { return _M_bucket_count; }

size_type
      max_bucket_count() const
      { return max_size(); }

size_type
      bucket_size(size_type __n) const
      { return std::distance(begin(__n), end(__n)); }

size_type
      bucket(const key_type& __k) const
      {
	return this->_M_bucket_index(__k, this->_M_hash_code(__k),
				     bucket_count());
      }

local_iterator
      begin(size_type __n)
      { return local_iterator(_M_buckets[__n]); }

local_iterator
      end(size_type)
      { return local_iterator(0); }

const_local_iterator
      begin(size_type __n) const
      { return const_local_iterator(_M_buckets[__n]); }

const_local_iterator
      end(size_type) const
      { return const_local_iterator(0); }

float
      load_factor() const
      {
	return static_cast<float>(size()) / static_cast<float>(bucket_count());
      }

// max_load_factor, if present, comes from _Rehash_base.

// Generalization of max_load_factor.  Extension, not found in TR1.  Only
      // useful if _RehashPolicy is something other than the default.
      const _RehashPolicy&
      __rehash_policy() const
      { return _M_rehash_policy; }

void
      __rehash_policy(const _RehashPolicy&);

// Lookup.
      iterator
      find(const key_type& __k);

const_iterator
      find(const key_type& __k) const;

size_type
      count(const key_type& __k) const;

std::pair<iterator, iterator>
      equal_range(const key_type& __k);

std::pair<const_iterator, const_iterator>
      equal_range(const key_type& __k) const;

private:			// Find, insert and erase helper functions
      // ??? This dispatching is a workaround for the fact that we don't
      // have partial specialization of member templates; it would be
      // better to just specialize insert on __unique_keys.  There may be a
      // cleaner workaround.
      typedef typename __gnu_cxx::__conditional_type<__unique_keys,
		       	    std::pair<iterator, bool>, iterator>::__type
	_Insert_Return_Type;

typedef typename __gnu_cxx::__conditional_type<__unique_keys,
					  std::_Select1st<_Insert_Return_Type>,
				  	  std::_Identity<_Insert_Return_Type>
				   >::__type
	_Insert_Conv_Type;

_Node*
      _M_find_node(_Node*, const key_type&,
		   typename _Hashtable::_Hash_code_type) const;

iterator
      _M_insert_bucket(const value_type&, size_type,
		       typename _Hashtable::_Hash_code_type);

std::pair<iterator, bool>
      _M_insert(const value_type&, std::tr1::true_type);

iterator
      _M_insert(const value_type&, std::tr1::false_type);

void
      _M_erase_node(_Node*, _Node**);

public:
      // Insert and erase
      _Insert_Return_Type
      insert(const value_type& __v)
      { return _M_insert(__v, std::tr1::integral_constant<bool,
			 __unique_keys>()); }

iterator
      insert(iterator, const value_type& __v)
      { return iterator(_Insert_Conv_Type()(this->insert(__v))); }

const_iterator
      insert(const_iterator, const value_type& __v)
      { return const_iterator(_Insert_Conv_Type()(this->insert(__v))); }

template<typename _InputIterator>
	void
	insert(_InputIterator __first, _InputIterator __last);

iterator
      erase(iterator);

const_iterator
      erase(const_iterator);

size_type
      erase(const key_type&);

iterator
      erase(iterator, iterator);

const_iterator
      erase(const_iterator, const_iterator);

void
      clear();

// Set number of buckets to be appropriate for container of n element.
      void rehash(size_type __n);

private:
      // Unconditionally change size of bucket array to n.
      void _M_rehash(size_type __n);
    };

// Definitions of class template _Hashtable's out-of-line member functions.
  template<typename _Key, typename _Value,
	   typename _Allocator, typename _ExtractKey, typename _Equal,
	   typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
	   bool __chc, bool __cit, bool __uk>
    typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
			_H1, _H2, _Hash, _RehashPolicy,
			__chc, __cit, __uk>::_Node*
    _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
	       _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
    _M_allocate_node(const value_type& __v)
    {
      _Node* __n = _M_node_allocator.allocate(1);
      __try
	{
	  _Value_allocator_type __a = _M_get_Value_allocator();
	  typedef __gnu_cxx::__alloc_traits<_Value_allocator_type> _Traits;
	  _Traits::construct(__a, &__n->_M_v, __v);
	  __n->_M_next = 0;
	  return __n;
	}
      __catch(...)
	{
	  _M_node_allocator.deallocate(__n, 1);
	  __throw_exception_again;
	}
    }

// We allocate one extra bucket to hold a sentinel, an arbitrary
      // non-null pointer.  Iterator increment relies on this.
      _Node** __p = __alloc.allocate(__n + 1);
      std::fill(__p, __p + __n, (_Node*) 0);
      __p[__n] = reinterpret_cast<_Node*>(0x1000);
      return __p;
    }

template<typename _Key, typename _Value,
	   typename _Allocator, typename _ExtractKey, typename _Equal,
	   typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
	   bool __chc, bool __cit, bool __uk>
    _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
	       _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
    _Hashtable(size_type __bucket_hint,
	       const _H1& __h1, const _H2& __h2, const _Hash& __h,
	       const _Equal& __eq, const _ExtractKey& __exk,
	       const allocator_type& __a)
    : __detail::_Rehash_base<_RehashPolicy, _Hashtable>(),
      __detail::_Hash_code_base<_Key, _Value, _ExtractKey, _Equal,
				_H1, _H2, _Hash, __chc>(__exk, __eq,
							__h1, __h2, __h),
      __detail::_Map_base<_Key, _Value, _ExtractKey, __uk, _Hashtable>(),
      _M_node_allocator(__a),
      _M_bucket_count(0),
      _M_element_count(0),
      _M_rehash_policy()
    {
      _M_bucket_count = _M_rehash_policy._M_next_bkt(__bucket_hint);
      _M_buckets = _M_allocate_buckets(_M_bucket_count);
    }

template<typename _Key, typename _Value,
	   typename _Allocator, typename _ExtractKey, typename _Equal,
	   typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
	   bool __chc, bool __cit, bool __uk>
    template<typename _InputIterator>
      _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
		 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
      _Hashtable(_InputIterator __f, _InputIterator __l,
		 size_type __bucket_hint,
		 const _H1& __h1, const _H2& __h2, const _Hash& __h,
		 const _Equal& __eq, const _ExtractKey& __exk,
		 const allocator_type& __a)
      : __detail::_Rehash_base<_RehashPolicy, _Hashtable>(),
	__detail::_Hash_code_base<_Key, _Value, _ExtractKey, _Equal,
				  _H1, _H2, _Hash, __chc>(__exk, __eq,
							  __h1, __h2, __h),
	__detail::_Map_base<_Key, _Value, _ExtractKey, __uk, _Hashtable>(),
	_M_node_allocator(__a),
	_M_bucket_count(0),
	_M_element_count(0),
	_M_rehash_policy()
      {
	_M_bucket_count = std::max(_M_rehash_policy._M_next_bkt(__bucket_hint),
				   _M_rehash_policy.
				   _M_bkt_for_elements(__detail::
						       __distance_fw(__f,
								     __l)));
	_M_buckets = _M_allocate_buckets(_M_bucket_count);
	__try
	  {
	    for (; __f != __l; ++__f)
	      this->insert(*__f);
	  }
	__catch(...)
	  {
	    clear();
	    _M_deallocate_buckets(_M_buckets, _M_bucket_count);
	    __throw_exception_again;
	  }
      }

template<typename _Key, typename _Value,
	   typename _Allocator, typename _ExtractKey, typename _Equal,
	   typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
	   bool __chc, bool __cit, bool __uk>
    _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
	       _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
    _Hashtable(const _Hashtable& __ht)
    : __detail::_Rehash_base<_RehashPolicy, _Hashtable>(__ht),
      __detail::_Hash_code_base<_Key, _Value, _ExtractKey, _Equal,
				_H1, _H2, _Hash, __chc>(__ht),
      __detail::_Map_base<_Key, _Value, _ExtractKey, __uk, _Hashtable>(__ht),
      _M_node_allocator(__ht._M_node_allocator),
      _M_bucket_count(__ht._M_bucket_count),
      _M_element_count(__ht._M_element_count),
      _M_rehash_policy(__ht._M_rehash_policy)
    {
      _M_buckets = _M_allocate_buckets(_M_bucket_count);
      __try
	{
	  for (size_type __i = 0; __i < __ht._M_bucket_count; ++__i)
	    {
	      _Node* __n = __ht._M_buckets[__i];
	      _Node** __tail = _M_buckets + __i;
	      while (__n)
		{
		  *__tail = _M_allocate_node(__n->_M_v);
		  this->_M_copy_code(*__tail, __n);
		  __tail = &((*__tail)->_M_next);
		  __n = __n->_M_next;
		}
	    }
	}
      __catch(...)
	{
	  clear();
	  _M_deallocate_buckets(_M_buckets, _M_bucket_count);
	  __throw_exception_again;
	}
    }

// _GLIBCXX_RESOLVE_LIB_DEFECTS
      // 431. Swapping containers with unequal allocators.
      std::__alloc_swap<_Node_allocator_type>::_S_do_it(_M_node_allocator,
							__x._M_node_allocator);

std::swap(_M_rehash_policy, __x._M_rehash_policy);
      std::swap(_M_buckets, __x._M_buckets);
      std::swap(_M_bucket_count, __x._M_bucket_count);
      std::swap(_M_element_count, __x._M_element_count);
    }

if (__p)
	{
	  _Node* __p1 = __p->_M_next;
	  for (; __p1; __p1 = __p1->_M_next)
	    if (!this->_M_compare(__k, __code, __p1))
	      break;

iterator __first(__p, __head);
	  iterator __last(__p1, __head);
	  if (!__p1)
	    __last._M_incr_bucket();
	  return std::make_pair(__first, __last);
	}
      else
	return std::make_pair(this->end(), this->end());
    }

if (__p)
	{
	  _Node* __p1 = __p->_M_next;
	  for (; __p1; __p1 = __p1->_M_next)
	    if (!this->_M_compare(__k, __code, __p1))
	      break;

const_iterator __first(__p, __head);
	  const_iterator __last(__p1, __head);
	  if (!__p1)
	    __last._M_incr_bucket();
	  return std::make_pair(__first, __last);
	}
      else
	return std::make_pair(this->end(), this->end());
    }

// Find the node whose key compares equal to k, beginning the search
  // at p (usually the head of a bucket).  Return zero if no node is found.
  template<typename _Key, typename _Value,
	   typename _Allocator, typename _ExtractKey, typename _Equal,
	   typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
	   bool __chc, bool __cit, bool __uk>
    typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey,
			_Equal, _H1, _H2, _Hash, _RehashPolicy,
			__chc, __cit, __uk>::_Node*
    _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
	       _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
    _M_find_node(_Node* __p, const key_type& __k,
		typename _Hashtable::_Hash_code_type __code) const
    {
      for (; __p; __p = __p->_M_next)
	if (this->_M_compare(__k, __code, __p))
	  return __p;
      return 0;
    }

// Insert v in bucket n (assumes no element with its key already present).
  template<typename _Key, typename _Value,
	   typename _Allocator, typename _ExtractKey, typename _Equal,
	   typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
	   bool __chc, bool __cit, bool __uk>
    typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
			_H1, _H2, _Hash, _RehashPolicy,
			__chc, __cit, __uk>::iterator
    _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
	       _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
    _M_insert_bucket(const value_type& __v, size_type __n,
		    typename _Hashtable::_Hash_code_type __code)
    {
      std::pair<bool, std::size_t> __do_rehash
	= _M_rehash_policy._M_need_rehash(_M_bucket_count,
					  _M_element_count, 1);

// Allocate the new node before doing the rehash so that we don't
      // do a rehash if the allocation throws.
      _Node* __new_node = _M_allocate_node(__v);

__try
	{
	  if (__do_rehash.first)
	    {
	      const key_type& __k = this->_M_extract(__v);
	      __n = this->_M_bucket_index(__k, __code, __do_rehash.second);
	      _M_rehash(__do_rehash.second);
	    }

__new_node->_M_next = _M_buckets[__n];
	  this->_M_store_code(__new_node, __code);
	  _M_buckets[__n] = __new_node;
	  ++_M_element_count;
	  return iterator(__new_node, _M_buckets + __n);
	}
      __catch(...)
	{
	  _M_deallocate_node(__new_node);
	  __throw_exception_again;
	}
    }

// Insert v if no element with its key is already present.
  template<typename _Key, typename _Value,
	   typename _Allocator, typename _ExtractKey, typename _Equal,
	   typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
	   bool __chc, bool __cit, bool __uk>
    std::pair<typename _Hashtable<_Key, _Value, _Allocator,
				  _ExtractKey, _Equal, _H1,
				  _H2, _Hash, _RehashPolicy,
				  __chc, __cit, __uk>::iterator, bool>
    _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
	       _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
  _M_insert(const value_type& __v, std::tr1::true_type)
    {
      const key_type& __k = this->_M_extract(__v);
      typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k);
      size_type __n = this->_M_bucket_index(__k, __code, _M_bucket_count);

if (_Node* __p = _M_find_node(_M_buckets[__n], __k, __code))
	return std::make_pair(iterator(__p, _M_buckets + __n), false);
      return std::make_pair(_M_insert_bucket(__v, __n, __code), true);
    }

// Insert v unconditionally.
  template<typename _Key, typename _Value,
	   typename _Allocator, typename _ExtractKey, typename _Equal,
	   typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
	   bool __chc, bool __cit, bool __uk>
    typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
			_H1, _H2, _Hash, _RehashPolicy,
			__chc, __cit, __uk>::iterator
    _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
	       _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
    _M_insert(const value_type& __v, std::tr1::false_type)
    {
      std::pair<bool, std::size_t> __do_rehash
	= _M_rehash_policy._M_need_rehash(_M_bucket_count,
					  _M_element_count, 1);
      if (__do_rehash.first)
	_M_rehash(__do_rehash.second);

const key_type& __k = this->_M_extract(__v);
      typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k);
      size_type __n = this->_M_bucket_index(__k, __code, _M_bucket_count);

// First find the node, avoid leaking new_node if compare throws.
      _Node* __prev = _M_find_node(_M_buckets[__n], __k, __code);
      _Node* __new_node = _M_allocate_node(__v);

if (__prev)
	{
	  __new_node->_M_next = __prev->_M_next;
	  __prev->_M_next = __new_node;
	}
      else
	{
	  __new_node->_M_next = _M_buckets[__n];
	  _M_buckets[__n] = __new_node;
	}
      this->_M_store_code(__new_node, __code);

++_M_element_count;
      return iterator(__new_node, _M_buckets + __n);
    }

// For erase(iterator) and erase(const_iterator).
  template<typename _Key, typename _Value,
	   typename _Allocator, typename _ExtractKey, typename _Equal,
	   typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
	   bool __chc, bool __cit, bool __uk>
    void
    _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
	       _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
    _M_erase_node(_Node* __p, _Node** __b)
    {
      _Node* __cur = *__b;
      if (__cur == __p)
	*__b = __cur->_M_next;
      else
	{
	  _Node* __next = __cur->_M_next;
	  while (__next != __p)
	    {
	      __cur = __next;
	      __next = __cur->_M_next;
	    }
	  __cur->_M_next = __next->_M_next;
	}

_M_deallocate_node(__p);
      --_M_element_count;
    }

for (; __first != __last; ++__first)
	  this->insert(*__first);
      }

_Node** __slot = _M_buckets + __n;
      while (*__slot && !this->_M_compare(__k, __code, *__slot))
	__slot = &((*__slot)->_M_next);

_Node** __saved_slot = 0;
      while (*__slot && this->_M_compare(__k, __code, *__slot))
	{
	  // _GLIBCXX_RESOLVE_LIB_DEFECTS
	  // 526. Is it undefined if a function in the standard changes
	  // in parameters?
	  if (&this->_M_extract((*__slot)->_M_v) != &__k)
	    {
	      _Node* __p = *__slot;
	      *__slot = __p->_M_next;
	      _M_deallocate_node(__p);
	      --_M_element_count;
	      ++__result;
	    }
	  else
	    {
	      __saved_slot = __slot;
	      __slot = &((*__slot)->_M_next);
	    }
	}

if (__saved_slot)
	{
	  _Node* __p = *__saved_slot;
	  *__saved_slot = __p->_M_next;
	  _M_deallocate_node(__p);
	  --_M_element_count;
	  ++__result;
	}

return __result;
    }

// ??? This could be optimized by taking advantage of the bucket
  // structure, but it's not clear that it's worth doing.  It probably
  // wouldn't even be an optimization unless the load factor is large.
  template<typename _Key, typename _Value,
	   typename _Allocator, typename _ExtractKey, typename _Equal,
	   typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
	   bool __chc, bool __cit, bool __uk>
    typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
			_H1, _H2, _Hash, _RehashPolicy,
			__chc, __cit, __uk>::iterator
    _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
	       _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
    erase(iterator __first, iterator __last)
    {
      while (__first != __last)
	__first = this->erase(__first);
      return __last;
    }

template<typename _Key, typename _Value,
	   typename _Allocator, typename _ExtractKey, typename _Equal,
	   typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
	   bool __chc, bool __cit, bool __uk>
    void
    _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
	       _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
    _M_rehash(size_type __n)
    {
      _Node** __new_array = _M_allocate_buckets(__n);
      __try
	{
	  for (size_type __i = 0; __i < _M_bucket_count; ++__i)
	    while (_Node* __p = _M_buckets[__i])
	      {
		std::size_t __new_index = this->_M_bucket_index(__p, __n);
		_M_buckets[__i] = __p->_M_next;
		__p->_M_next = __new_array[__new_index];
		__new_array[__new_index] = __p;
	      }
	  _M_deallocate_buckets(_M_buckets, _M_bucket_count);
	  _M_bucket_count = __n;
	  _M_buckets = __new_array;
	}
      __catch(...)
	{
	  // A failure here means that a hash function threw an exception.
	  // We can't restore the previous state without calling the hash
	  // function again, so the only sensible recovery is to delete
	  // everything.
	  _M_deallocate_nodes(__new_array, __n);
	  _M_deallocate_buckets(__new_array, __n);
	  _M_deallocate_nodes(_M_buckets, _M_bucket_count);
	  _M_element_count = 0;
	  __throw_exception_again;
	}
    }
} // namespace tr1

_GLIBCXX_END_NAMESPACE_VERSION
} // namespace std

#endif // _GLIBCXX_TR1_HASHTABLE_H

cmd: