Subversion Repositories Kolibri OS

Rev

Blame | Last modification | View Log | RSS feed

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