OSDN Git Service

2006-02-22 Paolo Carlini <pcarlini@suse.de>
[pf3gnuchains/gcc-fork.git] / libstdc++-v3 / include / tr1 / hashtable
index 36e33b0..7092e3c 100644 (file)
@@ -1,6 +1,6 @@
 // Internal header for TR1 unordered_set and unordered_map -*- C++ -*-
 
-// Copyright (C) 2005 Free Software Foundation, Inc.
+// Copyright (C) 2005, 2006 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
@@ -55,6 +55,7 @@
 #define GNU_LIBSTDCXX_TR1_HASHTABLE_
 
 #include <utility>             // For std::pair
+#include <memory>
 #include <iterator>
 #include <cstddef>
 #include <cstdlib>
@@ -100,6 +101,7 @@ namespace Internal
   
 } // namespace Internal
 
+
 //----------------------------------------------------------------------
 // Auxiliary types used for all instantiations of hashtable: nodes
 // and iterators.
@@ -117,16 +119,16 @@ namespace Internal
   template<typename Value>
     struct hash_node<Value, true>
     {
-      Value m_v;
+      Value       m_v;
       std::size_t hash_code;
-      hash_node* m_next;
+      hash_node*  m_next;
     };
 
   template<typename Value>
     struct hash_node<Value, false>
     {
-      Value m_v;
-      hash_node* m_next;
+      Value       m_v;
+      hash_node*  m_next;
     };
 
   // Local iterators, used to iterate within a bucket but not between
@@ -258,7 +260,7 @@ namespace Internal
       void
       m_incr_bucket();
 
-      hash_node<Value, cache>* m_cur_node;
+      hash_node<Value, cache>*  m_cur_node;
       hash_node<Value, cache>** m_cur_bucket;
     };
 
@@ -329,7 +331,8 @@ namespace Internal
       { 
        hashtable_iterator tmp(*this);
        this->incr();
-       return tmp; }
+       return tmp;
+      }
     };
 
   template<typename Value, bool constant_iterators, bool cache>
@@ -374,10 +377,12 @@ namespace Internal
       { 
        hashtable_const_iterator tmp(*this);
        this->incr();
-       return tmp; }
+       return tmp;
+      }
     };
 } // namespace Internal
 
+
 // ----------------------------------------------------------------------
 // Many of class template hashtable's template parameters are policy
 // classes.  These are defaults for the policies.
@@ -410,7 +415,7 @@ namespace Internal
     typedef std::size_t result_type;
 
     result_type
-    operator() (first_argument_type r, second_argument_type N) const
+    operator()(first_argument_type r, second_argument_type N) const
     { return r % N; }
   };
 
@@ -445,8 +450,8 @@ namespace Internal
     std::pair<bool, std::size_t>
     need_rehash(std::size_t n_bkt, std::size_t n_elt, std::size_t n_ins) const;
     
-    float m_max_load_factor;
-    float m_growth_factor;
+    float               m_max_load_factor;
+    float               m_growth_factor;
     mutable std::size_t m_next_resize;
   };
 
@@ -539,7 +544,7 @@ namespace Internal
   next_bkt(std::size_t n) const
   {
     const unsigned long* const last = X<0>::primes + X<0>::n_primes;
-    const unsigned long* p = std::lower_bound (X<0>::primes, last, n);
+    const unsigned long* p = std::lower_bound(X<0>::primes, last, n);
     m_next_resize = static_cast<std::size_t>(std::ceil(*p * m_max_load_factor));
     return *p;
   }
@@ -552,8 +557,8 @@ namespace Internal
   {
     const unsigned long* const last = X<0>::primes + X<0>::n_primes;
     const float min_bkts = n / m_max_load_factor;
-    const unsigned long* p = std::lower_bound (X<0>::primes, last,
-                                              min_bkts, lt());
+    const unsigned long* p = std::lower_bound(X<0>::primes, last,
+                                             min_bkts, lt());
     m_next_resize = static_cast<std::size_t>(std::ceil(*p * m_max_load_factor));
     return *p;
   }
@@ -576,10 +581,10 @@ namespace Internal
        float min_bkts = (float(n_ins) + float(n_elt)) / m_max_load_factor;
        if (min_bkts > n_bkt)
          {
-           min_bkts = std::max (min_bkts, m_growth_factor * n_bkt);
+           min_bkts = std::max(min_bkts, m_growth_factor * n_bkt);
            const unsigned long* const last = X<0>::primes + X<0>::n_primes;
-           const unsigned long* p = std::lower_bound (X<0>::primes, last,
-                                                      min_bkts, lt());
+           const unsigned long* p = std::lower_bound(X<0>::primes, last,
+                                                     min_bkts, lt());
            m_next_resize = 
              static_cast<std::size_t>(std::ceil(*p * m_max_load_factor));
            return std::make_pair(true, *p);
@@ -597,6 +602,7 @@ namespace Internal
 
 } // namespace Internal
 
+
 //----------------------------------------------------------------------
 // Base classes for std::tr1::hashtable.  We define these base classes
 // because in some cases we want to do different things depending on
@@ -650,7 +656,7 @@ namespace Internal
       max_load_factor() const
       {
        const Hashtable* This = static_cast<const Hashtable*>(this);
-       return This->rehash_policy()->max_load_factor();
+       return This->rehash_policy().max_load_factor();
       }
 
       void
@@ -700,15 +706,15 @@ namespace Internal
   
       std::size_t
       bucket_index(const Key& k, hash_code_t, std::size_t N) const
-      { return m_ranged_hash (k, N); }
+      { return m_ranged_hash(k, N); }
 
       std::size_t
       bucket_index(const hash_node<Value, false>* p, std::size_t N) const
-      { return m_ranged_hash (m_extract (p->m_v), N); }
+      { return m_ranged_hash(m_extract(p->m_v), N); }
   
       bool
       compare(const Key& k, hash_code_t, hash_node<Value, false>* n) const
-      { return m_eq (k, m_extract(n->m_v)); }
+      { return m_eq(k, m_extract(n->m_v)); }
 
       void
       store_code(hash_node<Value, false>*, hash_code_t) const
@@ -728,8 +734,8 @@ namespace Internal
 
     protected:
       ExtractKey m_extract;
-      Equal m_eq;
-      H m_ranged_hash;
+      Equal      m_eq;
+      H          m_ranged_hash;
     };
 
 
@@ -776,15 +782,15 @@ namespace Internal
       
       std::size_t
       bucket_index(const Key&, hash_code_t c, std::size_t N) const
-      { return m_h2 (c, N); }
+      { return m_h2(c, N); }
 
       std::size_t
       bucket_index(const hash_node<Value, false>* p, std::size_t N) const
-      { return m_h2 (m_h1 (m_extract (p->m_v)), N); }
+      { return m_h2(m_h1(m_extract(p->m_v)), N); }
 
       bool
       compare(const Key& k, hash_code_t, hash_node<Value, false>* n) const
-      { return m_eq (k, m_extract(n->m_v)); }
+      { return m_eq(k, m_extract(n->m_v)); }
 
       void
       store_code(hash_node<Value, false>*, hash_code_t) const
@@ -805,9 +811,9 @@ namespace Internal
 
     protected:
       ExtractKey m_extract;
-      Equal m_eq;
-      H1 m_h1;
-      H2 m_h2;
+      Equal      m_eq;
+      H1         m_h1;
+      H2         m_h2;
     };
 
   // Specialization: hash function and range-hashing function, 
@@ -833,16 +839,16 @@ namespace Internal
       typedef std::size_t hash_code_t;
   
       hash_code_t
-      m_hash_code (const Key& k) const
+      m_hash_code(const Key& k) const
       { return m_h1(k); }
   
       std::size_t
       bucket_index(const Key&, hash_code_t c, std::size_t N) const
-      { return m_h2 (c, N); }
+      { return m_h2(c, N); }
 
       std::size_t
       bucket_index(const hash_node<Value, true>* p, std::size_t N) const
-      { return m_h2 (p->hash_code, N); }
+      { return m_h2(p->hash_code, N); }
 
       bool
       compare(const Key& k, hash_code_t c, hash_node<Value, true>* n) const
@@ -868,17 +874,17 @@ namespace Internal
       
     protected:
       ExtractKey m_extract;
-      Equal m_eq;
-      H1 m_h1;
-      H2 m_h2;
+      Equal      m_eq;
+      H1         m_h1;
+      H2         m_h2;
     };
 
 } // namespace internal
 
 namespace std
 { 
-namespace tr1
-{
+_GLIBCXX_BEGIN_NAMESPACE(tr1)
+
   //----------------------------------------------------------------------
   // Class template hashtable, class definition.
   
@@ -959,44 +965,44 @@ namespace tr1
                                          unique_keys> >
     {
     public:
-      typedef Allocator                                      allocator_type;
-      typedef Value                                          value_type;
-      typedef Key                                            key_type;
-      typedef Equal                                          key_equal;
+      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 Allocator::reference                  reference;
-      typedef typename Allocator::const_reference            const_reference;
+      typedef typename Allocator::difference_type         difference_type;
+      typedef typename Allocator::size_type               size_type;
+      typedef typename Allocator::reference               reference;
+      typedef typename Allocator::const_reference         const_reference;
       
       typedef Internal::node_iterator<value_type, constant_iterators,
                                      cache_hash_code>
-        local_iterator;
+                                                          local_iterator;
       typedef Internal::node_const_iterator<value_type, constant_iterators,
                                            cache_hash_code>
-        const_local_iterator;
+                                                          const_local_iterator;
 
       typedef Internal::hashtable_iterator<value_type, constant_iterators,
                                           cache_hash_code>
-        iterator;
+                                                          iterator;
       typedef Internal::hashtable_const_iterator<value_type, constant_iterators,
                                                 cache_hash_code>
-        const_iterator;
+                                                          const_iterator;
 
     private:
-      typedef Internal::hash_node<Value, cache_hash_code>    node;
+      typedef Internal::hash_node<Value, cache_hash_code> node;
       typedef typename Allocator::template rebind<node>::other
-        node_allocator_t;
+                                                          node_allocator_t;
       typedef typename Allocator::template rebind<node*>::other
-        bucket_allocator_t;
+                                                          bucket_allocator_t;
 
     private:
-      node_allocator_t m_node_allocator;
-      node** m_buckets;
-      size_type m_bucket_count;
-      size_type m_element_count;
-      RehashPolicy m_rehash_policy;
+      node_allocator_t      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);
@@ -1022,7 +1028,7 @@ namespace tr1
       template<typename InIter>
         hashtable(InIter first, InIter last,
                  size_type bucket_hint,
-                 const H1&, const H2&, const H&,
+                 const H1&, const H2&, const H&, 
                  const Equal&, const ExtractKey&,
                  const allocator_type&);
   
@@ -1078,6 +1084,13 @@ namespace tr1
       max_size() const
       { return m_node_allocator.max_size(); }
 
+    public:                             // Observers
+      key_equal
+      key_eq() const
+      { return this->m_eq; }
+
+      // hash_function, if present, comes from hash_code_base.
+
     public:                            // Bucket operations
       size_type
       bucket_count() const
@@ -1091,9 +1104,11 @@ namespace tr1
       bucket_size(size_type n) const
       { return std::distance(begin(n), end(n)); }
   
-      size_type bucket(const key_type& k) const
+      size_type
+      bucket(const key_type& k) const
       { 
-       return this->bucket_index(k, this->m_hash_code, this->m_bucket_count);
+       return this->bucket_index(k, this->m_hash_code(k),
+                                 this->m_bucket_count);
       }
 
       local_iterator
@@ -1101,7 +1116,7 @@ namespace tr1
       { return local_iterator(m_buckets[n]); }
   
       local_iterator
-      end(size_type n)
+      end(size_type)
       { return local_iterator(0); }
   
       const_local_iterator
@@ -1109,7 +1124,7 @@ namespace tr1
       { return const_local_iterator(m_buckets[n]); }
   
       const_local_iterator
-      end(size_type n) const
+      end(size_type) const
       { return const_local_iterator(0); }
 
       float
@@ -1117,6 +1132,7 @@ namespace tr1
       { 
        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
@@ -1169,6 +1185,9 @@ namespace tr1
       iterator
       insert(const value_type&, std::tr1::false_type);
 
+      void
+      erase_node(node*, node**);
+
     public:                            // Insert and erase
       Insert_Return_Type
       insert(const value_type& v) 
@@ -1191,28 +1210,24 @@ namespace tr1
 
       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();
-      
-    private:
-      // For erase(iterator) and erase(const_iterator).
-      void m_erase(node*, node**);
 
     public:
-      // Set number of buckets to be apropriate for container of n element.
+      // Set number of buckets to be appropriate for container of n element.
       void rehash(size_type n);
       
     private:
@@ -1220,9 +1235,10 @@ namespace tr1
       void m_rehash(size_type n);
     };
 
+
   //----------------------------------------------------------------------
   // Definitions of class template hashtable's out-of-line member functions.
-  
+
   template<typename K, typename V, 
           typename A, typename Ex, typename Eq,
           typename H1, typename H2, typename H, typename RP,
@@ -1272,7 +1288,7 @@ namespace tr1
            {
              node* tmp = p;
              p = p->m_next;
-             m_deallocate_node (tmp);
+             m_deallocate_node(tmp);
            }
          array[i] = 0;
        }
@@ -1290,8 +1306,8 @@ namespace tr1
 
       // 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);
+      node** p = alloc.allocate(n + 1);
+      std::fill(p, p + n, (node*) 0);
       p[n] = reinterpret_cast<node*>(0x1000);
       return p;
     }
@@ -1305,7 +1321,7 @@ namespace tr1
     m_deallocate_buckets(node** p, size_type n)
     {
       bucket_allocator_t alloc(m_node_allocator);
-      alloc.deallocate(p, n+1);
+      alloc.deallocate(p, n + 1);
     }
 
   template<typename K, typename V, 
@@ -1317,7 +1333,7 @@ namespace tr1
              const H1& h1, const H2& h2, const H& h,
              const Eq& eq, const Ex& exk,
              const allocator_type& a)
-    : Internal::rehash_base<RP,hashtable>(),
+    : Internal::rehash_base<RP, hashtable>(),
       Internal::hash_code_base<K, V, Ex, Eq, H1, H2, H, c>(exk, eq, h1, h2, h),
       Internal::map_base<K, V, Ex, u, hashtable>(),
       m_node_allocator(a),
@@ -1340,12 +1356,12 @@ namespace tr1
                const H1& h1, const H2& h2, const H& h,
                const Eq& eq, const Ex& exk,
                const allocator_type& a)
-      : Internal::rehash_base<RP,hashtable>(),
-       Internal::hash_code_base<K, V, Ex, Eq, H1, H2, H, c> (exk, eq,
-                                                             h1, h2, h),
-       Internal::map_base<K,V,Ex,u,hashtable>(),
+      : Internal::rehash_base<RP, hashtable>(),
+       Internal::hash_code_base<K, V, Ex, Eq, H1, H2, H, c>(exk, eq,
+                                                            h1, h2, h),
+       Internal::map_base<K, V, Ex, u, hashtable>(),
        m_node_allocator(a),
-       m_bucket_count (0),
+       m_bucket_count(0),
        m_element_count(0),
        m_rehash_policy()
       {
@@ -1381,10 +1397,10 @@ namespace tr1
       m_element_count(ht.m_element_count),
       m_rehash_policy(ht.m_rehash_policy)
     {
-      m_buckets = m_allocate_buckets (m_bucket_count);
+      m_buckets = m_allocate_buckets(m_bucket_count);
       try
        {
-         for (size_t i = 0; i < ht.m_bucket_count; ++i)
+         for (size_type i = 0; i < ht.m_bucket_count; ++i)
            {
              node* n = ht.m_buckets[i];
              node** tail = m_buckets + i;
@@ -1397,10 +1413,10 @@ namespace tr1
                }
            }
        }
-      catch (...)
+      catch(...)
        {
          clear();
-         m_deallocate_buckets (m_buckets, m_bucket_count);
+         m_deallocate_buckets(m_buckets, m_bucket_count);
          __throw_exception_again;
        }
     }
@@ -1442,8 +1458,11 @@ namespace tr1
       // have different members.
       Internal::hash_code_base<K, V, Ex, Eq, H1, H2, H, c>::m_swap(x);
 
-      // open LWG issue 431
-      // std::swap(m_node_allocator, x.m_node_allocator);
+      // _GLIBCXX_RESOLVE_LIB_DEFECTS
+      // 431. Swapping containers with unequal allocators.
+      std::__alloc_swap<node_allocator_t>::_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);
@@ -1461,7 +1480,7 @@ namespace tr1
       m_rehash_policy = pol;
       size_type n_bkt = pol.bkt_for_elements(m_element_count);
       if (n_bkt > m_bucket_count)
-       m_rehash (n_bkt);
+       m_rehash(n_bkt);
     }
 
   template<typename K, typename V, 
@@ -1472,9 +1491,9 @@ namespace tr1
     hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::
     find(const key_type& k)
     {
-      typename hashtable::hash_code_t code = this->m_hash_code (k);
+      typename hashtable::hash_code_t code = this->m_hash_code(k);
       std::size_t n = this->bucket_index(k, code, this->bucket_count());
-      node* p = find_node (m_buckets[n], k, code);
+      node* p = find_node(m_buckets[n], k, code);
       return p ? iterator(p, m_buckets + n) : this->end();
     }
   
@@ -1486,9 +1505,9 @@ namespace tr1
     hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::
     find(const key_type& k) const
     {
-      typename hashtable::hash_code_t code = this->m_hash_code (k);
+      typename hashtable::hash_code_t code = this->m_hash_code(k);
       std::size_t n = this->bucket_index(k, code, this->bucket_count());
-      node* p = find_node (m_buckets[n], k, code);
+      node* p = find_node(m_buckets[n], k, code);
       return p ? const_iterator(p, m_buckets + n) : this->end();
     }
   
@@ -1500,11 +1519,11 @@ namespace tr1
     hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::
     count(const key_type& k) const
     {
-      typename hashtable::hash_code_t code = this->m_hash_code (k);
-      std::size_t n = this->bucket_index (k, code, this->bucket_count());
-      size_t result = 0;
-      for (node* p = m_buckets[n]; p ; p = p->m_next)
-       if (this->compare (k, code, p))
+      typename hashtable::hash_code_t code = this->m_hash_code(k);
+      std::size_t n = this->bucket_index(k, code, this->bucket_count());
+      std::size_t result = 0;
+      for (node* p = m_buckets[n]; p; p = p->m_next)
+       if (this->compare(k, code, p))
          ++result;
       return result;
     }
@@ -1520,16 +1539,16 @@ namespace tr1
     hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::
     equal_range(const key_type& k)
     {
-      typename hashtable::hash_code_t code = this->m_hash_code (k);
+      typename hashtable::hash_code_t code = this->m_hash_code(k);
       std::size_t n = this->bucket_index(k, code, this->bucket_count());
       node** head = m_buckets + n;
-      node* p = find_node (*head, k, code);
+      node* p = find_node(*head, k, code);
       
       if (p)
        {
          node* p1 = p->m_next;
-         for (; p1 ; p1 = p1->m_next)
-           if (!this->compare (k, code, p1))
+         for (; p1; p1 = p1->m_next)
+           if (!this->compare(k, code, p1))
              break;
 
          iterator first(p, head);
@@ -1553,16 +1572,16 @@ namespace tr1
     hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::
     equal_range(const key_type& k) const
     {
-      typename hashtable::hash_code_t code = this->m_hash_code (k);
+      typename hashtable::hash_code_t code = this->m_hash_code(k);
       std::size_t n = this->bucket_index(k, code, this->bucket_count());
       node** head = m_buckets + n;
-      node* p = find_node (*head, k, code);
+      node* p = find_node(*head, k, code);
 
       if (p)
        {
          node* p1 = p->m_next;
-         for (; p1 ; p1 = p1->m_next)
-           if (!this->compare (k, code, p1))
+         for (; p1; p1 = p1->m_next)
+           if (!this->compare(k, code, p1))
              break;
 
          const_iterator first(p, head);
@@ -1586,8 +1605,8 @@ namespace tr1
     find_node(node* p, const key_type& k,
              typename hashtable::hash_code_t code) const
     {
-      for ( ; p ; p = p->m_next)
-       if (this->compare (k, code, p))
+      for (; p; p = p->m_next)
+       if (this->compare(k, code, p))
          return p;
       return false;
     }
@@ -1603,18 +1622,18 @@ namespace tr1
     insert(const value_type& v, std::tr1::true_type)
     {
       const key_type& k = this->m_extract(v);
-      typename hashtable::hash_code_t code = this->m_hash_code (k);
-      size_type n = this->bucket_index(k, code, m_bucket_count);
+      typename hashtable::hash_code_t code = this->m_hash_code(k);
+      std::size_t n = this->bucket_index(k, code, m_bucket_count);
       
       if (node* p = find_node(m_buckets[n], k, code))
        return std::make_pair(iterator(p, m_buckets + n), false);
 
-      std::pair<bool, size_t> do_rehash
+      std::pair<bool, std::size_t> do_rehash
        = m_rehash_policy.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);
+      node* new_node = m_allocate_node(v);
       
       try
        {
@@ -1630,9 +1649,9 @@ namespace tr1
          ++m_element_count;
          return std::make_pair(iterator(new_node, m_buckets + n), true);
        }
-      catch (...)
+      catch(...)
        {
-         m_deallocate_node (new_node);
+         m_deallocate_node(new_node);
          __throw_exception_again;
        }
     }
@@ -1652,10 +1671,10 @@ namespace tr1
        m_rehash(do_rehash.second);
 
       const key_type& k = this->m_extract(v);
-      typename hashtable::hash_code_t code = this->m_hash_code (k);
-      size_type n = this->bucket_index(k, code, m_bucket_count);
+      typename hashtable::hash_code_t code = this->m_hash_code(k);
+      std::size_t n = this->bucket_index(k, code, m_bucket_count);
       
-      node* new_node = m_allocate_node (v);
+      node* new_node = m_allocate_node(v);
       node* prev = find_node(m_buckets[n], k, code);
       if (prev)
        {
@@ -1673,6 +1692,33 @@ namespace tr1
       return iterator(new_node, m_buckets + n);
     }
 
+  // For erase(iterator) and erase(const_iterator).
+  template<typename K, typename V, 
+          typename A, typename Ex, typename Eq,
+          typename H1, typename H2, typename H, typename RP,
+          bool c, bool ci, bool u>
+    void
+    hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::
+    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;
+    }
+
   template<typename K, typename V, 
           typename A, typename Ex, typename Eq,
           typename H1, typename H2, typename H, typename RP,
@@ -1682,14 +1728,14 @@ namespace tr1
       hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::
       insert(InIter first, InIter last)
       {
-       size_type n_elt = Internal::distance_fw (first, last);
+       size_type n_elt = Internal::distance_fw(first, last);
        std::pair<bool, std::size_t> do_rehash
          = m_rehash_policy.need_rehash(m_bucket_count, m_element_count, n_elt);
        if (do_rehash.first)
          m_rehash(do_rehash.second);
 
        for (; first != last; ++first)
-         this->insert (*first);
+         this->insert(*first);
       }
 
   template<typename K, typename V, 
@@ -1702,7 +1748,7 @@ namespace tr1
     {
       iterator result = i;
       ++result;
-      m_erase(i.m_cur_node, i.m_cur_bucket);
+      erase_node(i.m_cur_node, i.m_cur_bucket);
       return result;
     }
   
@@ -1716,7 +1762,7 @@ namespace tr1
     {
       const_iterator result = i;
       ++result;
-      m_erase(i.m_cur_node, i.m_cur_bucket);
+      erase_node(i.m_cur_node, i.m_cur_bucket);
       return result;
     }
 
@@ -1728,19 +1774,19 @@ namespace tr1
     hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::
     erase(const key_type& k)
     {
-      typename hashtable::hash_code_t code = this->m_hash_code (k);
-      size_type n = this->bucket_index(k, code, m_bucket_count);
+      typename hashtable::hash_code_t code = this->m_hash_code(k);
+      std::size_t n = this->bucket_index(k, code, m_bucket_count);
       size_type result = 0;
       
       node** slot = m_buckets + n;
-      while (*slot && ! this->compare (k, code, *slot))
+      while (*slot && !this->compare(k, code, *slot))
        slot = &((*slot)->m_next);
 
-      while (*slot && this->compare (k, code, *slot))
+      while (*slot && this->compare(k, code, *slot))
        {
-         node* n = *slot;
-         *slot = n->m_next;
-         m_deallocate_node (n);
+         node* p = *slot;
+         *slot = p->m_next;
+         m_deallocate_node(p);
          --m_element_count;
          ++result;
        }
@@ -1788,6 +1834,19 @@ namespace tr1
       m_deallocate_nodes(m_buckets, m_bucket_count);
       m_element_count = 0;
     }
+  template<typename K, typename V, 
+          typename A, typename Ex, typename Eq,
+          typename H1, typename H2, typename H, typename RP,
+          bool c, bool ci, bool u>
+    void
+    hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::
+    rehash(size_type n)
+    {
+      m_rehash(std::max(m_rehash_policy.next_bkt(n),
+                       m_rehash_policy.bkt_for_elements(m_element_count
+                                                        + 1)));
+    }
 
   template<typename K, typename V, 
           typename A, typename Ex, typename Eq,
@@ -1795,63 +1854,38 @@ namespace tr1
           bool c, bool ci, bool u>
     void
     hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::
-    m_rehash(size_type N)
+    m_rehash(size_type n)
     {
-      node** new_array = m_allocate_buckets (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])
              {
-               size_type new_index = this->bucket_index (p, N);
+               std::size_t new_index = this->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_bucket_count = n;
          m_buckets = new_array;
        }
-      catch (...)
+      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(new_array, n);
+         m_deallocate_buckets(new_array, n);
          m_deallocate_nodes(m_buckets, m_bucket_count);
          m_element_count = 0;
          __throw_exception_again;
        }
     }
 
-  template<typename K, typename V, 
-          typename A, typename Ex, typename Eq,
-          typename H1, typename H2, typename H, typename RP,
-          bool c, bool ci, bool u>
-    void
-    hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::
-    m_erase(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;
-    }
-}
+_GLIBCXX_END_NAMESPACE
 }                              // Namespace std::tr1
 
 #endif /* GNU_LIBSTDCXX_TR1_HASHTABLE_ */