[Boost-commit] svn:boost r56010 - trunk/boost/unordered/detail

Subject: [Boost-commit] svn:boost r56010 - trunk/boost/unordered/detail
From: daniel_james_at_[hidden]
Date: 2009-09-04 03:03:05

Author: danieljames
Date: 2009-09-04 03:03:04 EDT (Fri, 04 Sep 2009)
New Revision: 56010
URL: http://svn.boost.org/trac/boost/changeset/56010

Log:
Move size_ and cached_begin_bucket_ into table, rename hash_table_manager hash_buckets.
Added:
   trunk/boost/unordered/detail/buckets.hpp   (contents, props changed)
Removed:
   trunk/boost/unordered/detail/manager.hpp
Text files modified: 
   trunk/boost/unordered/detail/fwd.hpp   |   133 +++++++++--------                       
   trunk/boost/unordered/detail/table.hpp |   304 ++++++++++++++++++++++++++++++--------- 
   trunk/boost/unordered/detail/util.hpp  |    28 +-                                      
   3 files changed, 318 insertions(+), 147 deletions(-)

Added: trunk/boost/unordered/detail/buckets.hpp
==============================================================================
--- (empty file)
+++ trunk/boost/unordered/detail/buckets.hpp	2009-09-04 03:03:04 EDT (Fri, 04 Sep 2009)
@@ -0,0 +1,262 @@
+
+// Copyright (C) 2003-2004 Jeremy B. Maitin-Shepard.
+// Copyright (C) 2005-2009 Daniel James
+// Distributed under the Boost Software License, Version 1.0. (See accompanying
+// file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
+
+#ifndef BOOST_UNORDERED_DETAIL_MANAGER_HPP_INCLUDED
+#define BOOST_UNORDERED_DETAIL_MANAGER_HPP_INCLUDED
+
+#include <boost/config.hpp>
+#include <boost/assert.hpp>
+#include <boost/unordered/detail/node.hpp>
+
+namespace boost { namespace unordered_detail {
+    
+    ////////////////////////////////////////////////////////////////////////////
+    // Explicitly call a destructor
+
+#if defined(BOOST_MSVC)
+#  define BOOST_UNORDERED_DESTRUCT(x, type) (x)->~type();
+#else
+#  define BOOST_UNORDERED_DESTRUCT(x, type) boost::unordered_detail::destroy(x)
+    template <class T>
+    void destroy(T* x) {
+        x->~T();
+    }
+#endif
+
+    // Constructors
+
+    template <class A, class G>
+    hash_buckets<A, G>::hash_buckets(node_allocator const& a, std::size_t bucket_count)
+        : buckets_(), allocators_(a,a)
+    {
+        // The array constructor will clean up in the event of an
+        // exception.
+        allocator_array_constructor<bucket_allocator>
+            constructor(bucket_alloc());
+
+        // Creates an extra bucket to act as a sentinel.
+        constructor.construct(bucket(), bucket_count + 1);
+
+        // Set up the sentinel (node_ptr cast)
+        bucket_ptr sentinel = constructor.get() + static_cast<ptrdiff_t>(bucket_count);
+        sentinel->next_ = sentinel;
+
+        // Only release the buckets once everything is successfully
+        // done.
+        this->buckets_ = constructor.release();
+        this->bucket_count_ = bucket_count;
+    }
+
+    template <class A, class G>
+    hash_buckets<A, G>::hash_buckets(hash_buckets& x, move_tag)
+        : buckets_(), allocators_(x.allocators_)
+    {
+        this->buckets_ = x.buckets_;
+        this->bucket_count_ = x.bucket_count_;
+        x.buckets_ = bucket_ptr();
+        x.bucket_count_ = 0;
+    }
+
+    template <class A, class G>
+    hash_buckets<A, G>::hash_buckets(hash_buckets& x, value_allocator const& a, move_tag) :
+         buckets_(), allocators_(a,a)
+    {
+        if(this->node_alloc() == x.node_alloc()) {
+            this->buckets_ = x.buckets_;
+            this->bucket_count_ = x.bucket_count_;
+            x.buckets_ = bucket_ptr();
+            x.bucket_count_ = 0;
+        }
+    }
+    
+    template <class A, class G>
+    hash_buckets<A, G>::~hash_buckets()
+    {
+        if(this->buckets_) { delete_buckets(); }
+    }
+
+    // no throw
+    template <class A, class G>
+    inline void hash_buckets<A, G>::move(hash_buckets& other)
+    {
+    	BOOST_ASSERT(node_alloc() == other.node_alloc());
+        delete_buckets();
+        this->buckets_ = other.buckets_;
+        this->bucket_count_ = other.bucket_count_;
+        other.buckets_ = bucket_ptr();
+        other.bucket_count_ = 0;
+    }
+
+    template <class A, class G>
+    inline void hash_buckets<A, G>::swap(hash_buckets<A, G>& other)
+    {
+    	BOOST_ASSERT(node_alloc() == other.node_alloc());
+        std::swap(buckets_, other.buckets_);
+        std::swap(bucket_count_, other.bucket_count_);
+    }
+    
+    // Buckets
+    
+    template <class A, class G>
+    inline std::size_t hash_buckets<A, G>::bucket_count() const
+    {
+        return bucket_count_;
+    }
+    
+    template <class A, class G>
+    inline std::size_t hash_buckets<A, G>::bucket_from_hash(std::size_t hashed) const
+    {
+        return hashed % bucket_count_;
+    }
+
+    template <class A, class G>
+    inline BOOST_DEDUCED_TYPENAME hash_buckets<A, G>::bucket_ptr
+        hash_buckets<A, G>::bucket_ptr_from_hash(std::size_t hashed) const
+    {
+        return buckets_ + static_cast<std::ptrdiff_t>(
+            bucket_from_hash(hashed));
+    }
+    
+    template <class A, class G>
+    inline BOOST_DEDUCED_TYPENAME hash_buckets<A, G>::bucket_ptr
+        hash_buckets<A, G>::buckets_begin() const
+    {
+        return buckets_;
+    }
+
+    template <class A, class G>
+    inline BOOST_DEDUCED_TYPENAME hash_buckets<A, G>::bucket_ptr
+        hash_buckets<A, G>::buckets_end() const
+    {
+        return buckets_ + static_cast<std::ptrdiff_t>(bucket_count_);
+    }
+
+    template <class A, class G>
+    inline std::size_t hash_buckets<A, G>::bucket_size(std::size_t index) const
+    {
+        bucket_ptr ptr = (buckets_ + static_cast<std::ptrdiff_t>(index))->next_;
+        std::size_t count = 0;
+        while(ptr) {
+            ++count;
+            ptr = next_node(ptr);
+        }
+        return count;
+    }
+
+    template <class A, class G>
+    inline BOOST_DEDUCED_TYPENAME hash_buckets<A, G>::bucket_ptr
+        hash_buckets<A, G>::get_bucket(std::size_t n) const
+    {
+        return buckets_ + static_cast<std::ptrdiff_t>(n);
+    }
+
+    template <class A, class G>
+    inline BOOST_DEDUCED_TYPENAME hash_buckets<A, G>::node_ptr
+        hash_buckets<A, G>::bucket_begin(std::size_t n) const
+    {
+        return (buckets_ + static_cast<std::ptrdiff_t>(n))->next_;
+    }
+
+    template <class A, class G>
+    inline BOOST_DEDUCED_TYPENAME hash_buckets<A, G>::node_ptr
+        hash_buckets<A, G>::bucket_end(std::size_t) const
+    {
+        return node_ptr();
+    }
+
+    // Construct/destruct
+    
+    template <class A, class G>
+    inline void hash_buckets<A, G>::destruct_node(node_ptr b)
+    {
+        node* raw_ptr = static_cast<node*>(&*b);
+        BOOST_UNORDERED_DESTRUCT(&raw_ptr->value(), value_type);
+        real_node_ptr n(node_alloc().address(*raw_ptr));
+        node_alloc().destroy(n);
+        node_alloc().deallocate(n, 1);
+    }
+
+    // Delete and clear buckets
+
+    template <class A, class G>
+    inline void hash_buckets<A, G>::delete_group(node_ptr first_node)
+    {
+        delete_nodes(first_node, node::next_group(first_node));
+    }
+    
+    template <class A, class G>
+    inline void hash_buckets<A, G>::delete_nodes(node_ptr begin, node_ptr end)
+    {
+        while(begin != end) {
+            node_ptr node = begin;
+            begin = next_node(begin);
+            destruct_node(node);
+        }
+    }
+
+    template <class A, class G>
+    inline void hash_buckets<A, G>::delete_to_bucket_end(node_ptr begin)
+    {
+        while(BOOST_UNORDERED_BORLAND_BOOL(begin)) {
+            node_ptr node = begin;
+            begin = next_node(begin);
+            destruct_node(node);
+        }
+    }
+
+    template <class A, class G>
+    inline void hash_buckets<A, G>::clear_bucket(bucket_ptr b)
+    {
+        node_ptr node_it = b->next_;
+        b->next_ = node_ptr();
+
+        while(node_it) {
+            node_ptr node_to_destruct = node_it;
+            node_it = next_node(node_it);
+            destruct_node(node_to_destruct);
+        }
+    }
+
+    template <class A, class G>
+    inline void hash_buckets<A, G>::delete_buckets()
+    {      
+        for(bucket_ptr begin = this->buckets_begin(), end = this->buckets_end(); begin != end; ++begin) {
+            clear_bucket(begin);
+        }
+
+        // Destroy the buckets (including the sentinel bucket).
+        bucket_ptr end = this->buckets_end();
+        ++end;
+        for(bucket_ptr begin = this->buckets_begin(); begin != end; ++begin) {
+            bucket_alloc().destroy(begin);
+        }
+
+        bucket_alloc().deallocate(this->buckets_begin(), this->bucket_count() + 1);
+
+        this->buckets_ = bucket_ptr();
+    }
+
+    ////////////////////////////////////////////////////////////////////////////
+    // hash_iterator_base implementation
+    
+    template <class BucketPtr>
+    inline void hash_iterator_base<BucketPtr>::increment(node_ptr node) {
+        while(!node) {
+            ++bucket_;
+            node = bucket_->next_;
+        }
+
+        node_ = node;
+    }
+
+    template <class BucketPtr>
+    inline void hash_iterator_base<BucketPtr>::increment()
+    {
+        increment(next_node(node_));
+    }
+}}
+
+#endif

Modified: trunk/boost/unordered/detail/fwd.hpp
==============================================================================
--- trunk/boost/unordered/detail/fwd.hpp	(original)
+++ trunk/boost/unordered/detail/fwd.hpp	2009-09-04 03:03:04 EDT (Fri, 04 Sep 2009)
@@ -183,7 +183,7 @@
         void increment();
     };
 
-    // hash_table_manager
+    // hash_buckets
     //
     // This is responsible for allocating and deallocating buckets and nodes.
     //
@@ -193,8 +193,11 @@
     //    methods (other than getters and setters).
 
     template <class A, class G>
-    struct hash_table_manager
+    class hash_buckets
     {
+        hash_buckets(hash_buckets const&);
+        hash_buckets& operator=(hash_buckets const&);
+    public:
         // Types
 
         typedef A value_allocator;
@@ -217,8 +220,6 @@
         // Members
 
         bucket_ptr buckets_;
-        bucket_ptr cached_begin_bucket_;
-        std::size_t size_;
         std::size_t bucket_count_;
         boost::compressed_pair<bucket_allocator, node_allocator> allocators_;
         
@@ -228,8 +229,6 @@
         node_allocator const& node_alloc() const { return allocators_.second(); }
         bucket_allocator& bucket_alloc() { return allocators_.first(); }
         node_allocator& node_alloc() { return allocators_.second(); }
-        iterator_base begin() const { return iterator_base(this->cached_begin_bucket_); }
-        iterator_base end() const { return iterator_base(this->buckets_end()); }
         std::size_t max_bucket_count() const {
             // -1 to account for the sentinel.
             return prev_prime(this->bucket_alloc().max_size() - 1);
@@ -239,20 +238,17 @@
         //
         // The copy constructor doesn't copy the buckets.
 
-        hash_table_manager();
-        explicit hash_table_manager(value_allocator const& a);
-        explicit hash_table_manager(hash_table_manager const& h);
-        hash_table_manager(hash_table_manager& x, move_tag m);
-        hash_table_manager(hash_table_manager& x, value_allocator const& a, move_tag m);
-        ~hash_table_manager();
+        hash_buckets(node_allocator const& a, std::size_t n);
+        hash_buckets(hash_buckets& x, move_tag m);
+        hash_buckets(hash_buckets& x, value_allocator const& a, move_tag m);
+        ~hash_buckets();
         
         // no throw
-        void swap(hash_table_manager& other);
-        void move(hash_table_manager& other);
+        void swap(hash_buckets& other);
+        void move(hash_buckets& other);
 
         // Buckets
         
-        void create_buckets(std::size_t bucket_count);
         std::size_t bucket_count() const;
         std::size_t bucket_from_hash(std::size_t hashed) const;
         bucket_ptr bucket_ptr_from_hash(std::size_t hashed) const;
@@ -269,42 +265,15 @@
 
         // 
         void delete_buckets();
-        void clear();
         void clear_bucket(bucket_ptr);
         void delete_group(node_ptr first_node);
         void delete_nodes(node_ptr begin, node_ptr end);
         void delete_to_bucket_end(node_ptr begin);
-
-        // Erase
-        //
-        // no throw
-
-        iterator_base erase(iterator_base r);
-        std::size_t erase_group(node_ptr* it, bucket_ptr bucket);
-        iterator_base erase_range(iterator_base r1, iterator_base r2);
-
-        // recompute_begin_bucket
-        //
-        // After an erase cached_begin_bucket_ might be left pointing to
-        // an empty bucket, so this is called to update it
-        //
-        // no throw
-
-        void recompute_begin_bucket(bucket_ptr b);
-
-        // This is called when a range has been erased
-        //
-        // no throw
-
-        void recompute_begin_bucket(bucket_ptr b1, bucket_ptr b2);
-        
-        // no throw
-        float load_factor() const;
     };
 
     template <class H, class P, class A, class G, class K>
     class hash_table :
-        public hash_table_manager<A, G>
+        public hash_buckets<A, G>
         
     {
     public:
@@ -313,19 +282,19 @@
         typedef A value_allocator;
         typedef G grouped;
         typedef K key_extractor;
-        typedef hash_table_manager<A, G> manager;
+        typedef hash_buckets<A, G> buckets;
         
         typedef BOOST_DEDUCED_TYPENAME value_allocator::value_type value_type;
         typedef BOOST_DEDUCED_TYPENAME key_extractor::BOOST_NESTED_TEMPLATE apply<value_type>
             extractor;    
         typedef BOOST_DEDUCED_TYPENAME extractor::key_type key_type;
 
-        typedef BOOST_DEDUCED_TYPENAME manager::node node;
-        typedef BOOST_DEDUCED_TYPENAME manager::bucket bucket;
-        typedef BOOST_DEDUCED_TYPENAME manager::node_ptr node_ptr;
-        typedef BOOST_DEDUCED_TYPENAME manager::bucket_ptr bucket_ptr;
+        typedef BOOST_DEDUCED_TYPENAME buckets::node node;
+        typedef BOOST_DEDUCED_TYPENAME buckets::bucket bucket;
+        typedef BOOST_DEDUCED_TYPENAME buckets::node_ptr node_ptr;
+        typedef BOOST_DEDUCED_TYPENAME buckets::bucket_ptr bucket_ptr;
 
-        typedef BOOST_DEDUCED_TYPENAME manager::iterator_base iterator_base;
+        typedef BOOST_DEDUCED_TYPENAME buckets::iterator_base iterator_base;
 
         // Types for storing functions
 
@@ -340,6 +309,8 @@
         
         bool func_; // The currently active functions.
         aligned_function funcs_[2];
+        bucket_ptr cached_begin_bucket_;
+        std::size_t size_;
         float mlf_;
         std::size_t max_load_;
         
@@ -395,6 +366,11 @@
         ~hash_table();
         hash_table& operator=(hash_table const&);
 
+        // Iterators
+
+        iterator_base begin() const { return iterator_base(this->cached_begin_bucket_); }
+        iterator_base end() const { return iterator_base(this->buckets_end()); }
+
         // Swap & Move
 
         void swap(hash_table& x);
@@ -409,16 +385,45 @@
 
         // Move/copy buckets
 
-        void move_buckets_to(manager& dst);
-        void copy_buckets_to(manager& dst) const;
+        void move_buckets_to(buckets& dst);
+        void copy_buckets_to(buckets& dst) const;
 
         // Misc. key methods
 
-        std::size_t erase_key(key_type const& k);
         std::size_t count(key_type const& k) const;
         iterator_base find(key_type const& k) const;
         value_type& at(key_type const& k) const;
         std::pair<iterator_base, iterator_base> equal_range(key_type const& k) const;
+
+        // Erase
+        //
+        // no throw
+
+        void clear();
+        std::size_t erase_key(key_type const& k);
+        iterator_base erase(iterator_base r);
+        std::size_t erase_group(node_ptr* it, bucket_ptr bucket);
+        iterator_base erase_range(iterator_base r1, iterator_base r2);
+
+        // recompute_begin_bucket
+
+        void recompute_begin_bucket();
+
+        // After an erase cached_begin_bucket_ might be left pointing to
+        // an empty bucket, so this is called to update it
+        //
+        // no throw
+
+        void recompute_begin_bucket(bucket_ptr b);
+
+        // This is called when a range has been erased
+        //
+        // no throw
+
+        void recompute_begin_bucket(bucket_ptr b1, bucket_ptr b2);
+        
+        // no throw
+        float load_factor() const;
     };
 
     // Iterator Access
@@ -456,9 +461,9 @@
         typedef BOOST_DEDUCED_TYPENAME A::value_type value_type;
 
     private:
-        typedef hash_table_manager<A, G> manager;
-        typedef BOOST_DEDUCED_TYPENAME manager::node_ptr ptr;
-        typedef BOOST_DEDUCED_TYPENAME manager::node node;
+        typedef hash_buckets<A, G> buckets;
+        typedef BOOST_DEDUCED_TYPENAME buckets::node_ptr ptr;
+        typedef BOOST_DEDUCED_TYPENAME buckets::node node;
         typedef hash_const_local_iterator<A, G> const_local_iterator;
 
         friend class hash_const_local_iterator<A, G>;
@@ -491,9 +496,9 @@
         typedef BOOST_DEDUCED_TYPENAME A::value_type value_type;
 
     private:
-        typedef hash_table_manager<A, G> manager;
-        typedef BOOST_DEDUCED_TYPENAME manager::node_ptr ptr;
-        typedef BOOST_DEDUCED_TYPENAME manager::node node;
+        typedef hash_buckets<A, G> buckets;
+        typedef BOOST_DEDUCED_TYPENAME buckets::node_ptr ptr;
+        typedef BOOST_DEDUCED_TYPENAME buckets::node node;
         typedef hash_local_iterator<A, G> local_iterator;
         friend class hash_local_iterator<A, G>;
         ptr ptr_;
@@ -531,9 +536,9 @@
         typedef BOOST_DEDUCED_TYPENAME A::value_type value_type;
 
     private:
-        typedef hash_table_manager<A, G> manager;
-        typedef BOOST_DEDUCED_TYPENAME manager::node node;
-        typedef BOOST_DEDUCED_TYPENAME manager::iterator_base base;
+        typedef hash_buckets<A, G> buckets;
+        typedef BOOST_DEDUCED_TYPENAME buckets::node node;
+        typedef BOOST_DEDUCED_TYPENAME buckets::iterator_base base;
         typedef hash_const_iterator<A, G> const_iterator;
         friend class hash_const_iterator<A, G>;
         base base_;
@@ -566,9 +571,9 @@
         typedef BOOST_DEDUCED_TYPENAME A::value_type value_type;
 
     private:
-        typedef hash_table_manager<A, G> manager;
-        typedef BOOST_DEDUCED_TYPENAME manager::node node;
-        typedef BOOST_DEDUCED_TYPENAME manager::iterator_base base;
+        typedef hash_buckets<A, G> buckets;
+        typedef BOOST_DEDUCED_TYPENAME buckets::node node;
+        typedef BOOST_DEDUCED_TYPENAME buckets::iterator_base base;
         typedef hash_iterator<A, G> iterator;
         friend class hash_iterator<A, G>;
         friend class iterator_access;

Deleted: trunk/boost/unordered/detail/manager.hpp
==============================================================================
--- trunk/boost/unordered/detail/manager.hpp	2009-09-04 03:03:04 EDT (Fri, 04 Sep 2009)
+++ (empty file)
@@ -1,418 +0,0 @@
-
-// Copyright (C) 2003-2004 Jeremy B. Maitin-Shepard.
-// Copyright (C) 2005-2009 Daniel James
-// Distributed under the Boost Software License, Version 1.0. (See accompanying
-// file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
-
-#ifndef BOOST_UNORDERED_DETAIL_MANAGER_HPP_INCLUDED
-#define BOOST_UNORDERED_DETAIL_MANAGER_HPP_INCLUDED
-
-#include <boost/config.hpp>
-#include <boost/assert.hpp>
-#include <boost/unordered/detail/node.hpp>
-
-namespace boost { namespace unordered_detail {
-    
-    ////////////////////////////////////////////////////////////////////////////
-    // Explicitly call a destructor
-
-#if defined(BOOST_MSVC)
-#  define BOOST_UNORDERED_DESTRUCT(x, type) (x)->~type();
-#else
-#  define BOOST_UNORDERED_DESTRUCT(x, type) boost::unordered_detail::destroy(x)
-    template <class T>
-    void destroy(T* x) {
-        x->~T();
-    }
-#endif
-
-    // Constructors
-
-    template <class A, class G>
-    hash_table_manager<A, G>::hash_table_manager()
-        : buckets_(), cached_begin_bucket_(), size_(), allocators_() {}
-
-    template <class A, class G>
-    hash_table_manager<A, G>::hash_table_manager(value_allocator const& a)
-        : buckets_(), cached_begin_bucket_(), size_(), allocators_(a,a) {}
-
-    template <class A, class G>
-    hash_table_manager<A, G>::hash_table_manager(hash_table_manager const& h)
-        : buckets_(), cached_begin_bucket_(), size_(), allocators_(h.allocators_) {}
-
-    template <class A, class G>
-    hash_table_manager<A, G>::hash_table_manager(hash_table_manager& x, move_tag)
-        : buckets_(), cached_begin_bucket_(), size_(), allocators_(x.allocators_)
-    {
-        this->buckets_ = x.buckets_;
-        this->cached_begin_bucket_ = x.cached_begin_bucket_;
-        this->size_ = x.size_;
-        this->bucket_count_ = x.bucket_count_;
-        x.buckets_ = bucket_ptr();
-        x.cached_begin_bucket_ = bucket_ptr();
-        x.size_ = 0;
-        x.bucket_count_ = 0;
-    }
-
-    template <class A, class G>
-    hash_table_manager<A, G>::hash_table_manager(hash_table_manager& x, value_allocator const& a, move_tag) :
-         buckets_(), cached_begin_bucket_(), size_(), allocators_(a,a)
-    {
-        if(this->node_alloc() == x.node_alloc()) {
-            this->buckets_ = x.buckets_;
-            this->cached_begin_bucket_ = x.cached_begin_bucket_;
-            this->size_ = x.size_;
-            this->bucket_count_ = x.bucket_count_;
-            x.buckets_ = bucket_ptr();
-            x.cached_begin_bucket_ = bucket_ptr();
-            x.size_ = 0;
-            x.bucket_count_ = 0;
-        }
-    }
-    
-    template <class A, class G>
-    hash_table_manager<A, G>::~hash_table_manager()
-    {
-        if(this->buckets_) { delete_buckets(); }
-    }
-
-    // no throw
-    template <class A, class G>
-    inline void hash_table_manager<A, G>::move(hash_table_manager& other)
-    {
-    	BOOST_ASSERT(node_alloc() == other.node_alloc());
-        delete_buckets();
-        this->buckets_ = other.buckets_;
-        this->cached_begin_bucket_ = other.cached_begin_bucket_;
-        this->size_ = other.size_;
-        this->bucket_count_ = other.bucket_count_;
-        other.buckets_ = bucket_ptr();
-        other.cached_begin_bucket_ = bucket_ptr();
-        other.size_ = 0;
-        other.bucket_count_ = 0;
-    }
-
-    template <class A, class G>
-    inline void hash_table_manager<A, G>::swap(hash_table_manager<A, G>& other)
-    {
-    	BOOST_ASSERT(node_alloc() == other.node_alloc());
-        std::swap(buckets_, other.buckets_);
-        std::swap(cached_begin_bucket_, other.cached_begin_bucket_);
-        std::swap(size_, other.size_);
-        std::swap(bucket_count_, other.bucket_count_);
-    }
-    
-    // Buckets
-    
-    template <class A, class G>
-    inline std::size_t hash_table_manager<A, G>::bucket_count() const
-    {
-        return bucket_count_;
-    }
-    
-    template <class A, class G>
-    inline std::size_t hash_table_manager<A, G>::bucket_from_hash(std::size_t hashed) const
-    {
-        return hashed % bucket_count_;
-    }
-
-    template <class A, class G>
-    inline BOOST_DEDUCED_TYPENAME hash_table_manager<A, G>::bucket_ptr
-        hash_table_manager<A, G>::bucket_ptr_from_hash(std::size_t hashed) const
-    {
-        return buckets_ + static_cast<std::ptrdiff_t>(
-            bucket_from_hash(hashed));
-    }
-    
-    template <class A, class G>
-    inline BOOST_DEDUCED_TYPENAME hash_table_manager<A, G>::bucket_ptr
-        hash_table_manager<A, G>::buckets_begin() const
-    {
-        return buckets_;
-    }
-
-    template <class A, class G>
-    inline BOOST_DEDUCED_TYPENAME hash_table_manager<A, G>::bucket_ptr
-        hash_table_manager<A, G>::buckets_end() const
-    {
-        return buckets_ + static_cast<std::ptrdiff_t>(bucket_count_);
-    }
-
-    template <class A, class G>
-    inline std::size_t hash_table_manager<A, G>::bucket_size(std::size_t index) const
-    {
-        bucket_ptr ptr = (buckets_ + static_cast<std::ptrdiff_t>(index))->next_;
-        std::size_t count = 0;
-        while(ptr) {
-            ++count;
-            ptr = next_node(ptr);
-        }
-        return count;
-    }
-
-    template <class A, class G>
-    inline BOOST_DEDUCED_TYPENAME hash_table_manager<A, G>::bucket_ptr
-        hash_table_manager<A, G>::get_bucket(std::size_t n) const
-    {
-        return buckets_ + static_cast<std::ptrdiff_t>(n);
-    }
-
-    template <class A, class G>
-    inline BOOST_DEDUCED_TYPENAME hash_table_manager<A, G>::node_ptr
-        hash_table_manager<A, G>::bucket_begin(std::size_t n) const
-    {
-        return (buckets_ + static_cast<std::ptrdiff_t>(n))->next_;
-    }
-
-    template <class A, class G>
-    inline BOOST_DEDUCED_TYPENAME hash_table_manager<A, G>::node_ptr
-        hash_table_manager<A, G>::bucket_end(std::size_t) const
-    {
-        return node_ptr();
-    }
-
-    // recompute_begin_bucket
-    //
-    // After an erase cached_begin_bucket_ might be left pointing to
-    // an empty bucket, so this is called to update it
-    //
-    // no throw
-
-    template <class A, class G>
-    inline void hash_table_manager<A, G>::recompute_begin_bucket(bucket_ptr b)
-    {
-        BOOST_ASSERT(!(b < cached_begin_bucket_));
-
-        if(b == cached_begin_bucket_)
-        {
-            if (size_ != 0) {
-                while (!cached_begin_bucket_->next_)
-                    ++cached_begin_bucket_;
-            } else {
-                cached_begin_bucket_ = buckets_end();
-            }
-        }
-    }
-
-    // This is called when a range has been erased
-    //
-    // no throw
-
-    template <class A, class G>
-    inline void hash_table_manager<A, G>::recompute_begin_bucket(bucket_ptr b1, bucket_ptr b2)
-    {
-        BOOST_ASSERT(!(b1 < cached_begin_bucket_) && !(b2 < b1));
-        BOOST_ASSERT(BOOST_UNORDERED_BORLAND_BOOL(b2->next_));
-
-        if(b1 == cached_begin_bucket_ && !b1->next_)
-            cached_begin_bucket_ = b2;
-    }
-
-    // no throw
-    template <class A, class G>
-    inline float hash_table_manager<A, G>::load_factor() const
-    {
-        BOOST_ASSERT(bucket_count_ != 0);
-        return static_cast<float>(size_)
-            / static_cast<float>(bucket_count_);
-	}
-
-    // Construct/destruct
-    
-    template <class A, class G>
-    void hash_table_manager<A, G>::create_buckets(std::size_t bucket_count) {
-        BOOST_ASSERT(!this->buckets_ && !this->size_);
-        
-        // The array constructor will clean up in the event of an
-        // exception.
-        allocator_array_constructor<bucket_allocator>
-            constructor(bucket_alloc());
-
-        // Creates an extra bucket to act as a sentinel.
-        constructor.construct(bucket(), bucket_count + 1);
-
-        this->cached_begin_bucket_ = constructor.get() + static_cast<ptrdiff_t>(bucket_count);
-
-        // Set up the sentinel (node_ptr cast)
-        this->cached_begin_bucket_->next_ = this->cached_begin_bucket_;
-
-        // Only release the buckets once everything is successfully
-        // done.
-        this->buckets_ = constructor.release();
-        this->bucket_count_ = bucket_count;
-    }
-
-    template <class A, class G>
-    inline void hash_table_manager<A, G>::destruct_node(node_ptr b)
-    {
-        node* raw_ptr = static_cast<node*>(&*b);
-        BOOST_UNORDERED_DESTRUCT(&raw_ptr->value(), value_type);
-        real_node_ptr n(node_alloc().address(*raw_ptr));
-        node_alloc().destroy(n);
-        node_alloc().deallocate(n, 1);
-    }
-
-    // Delete and clear buckets
-
-    template <class A, class G>
-    inline void hash_table_manager<A, G>::delete_group(node_ptr first_node)
-    {
-        delete_nodes(first_node, node::next_group(first_node));
-    }
-    
-    template <class A, class G>
-    inline void hash_table_manager<A, G>::delete_nodes(node_ptr begin, node_ptr end)
-    {
-        while(begin != end) {
-            node_ptr node = begin;
-            begin = next_node(begin);
-            destruct_node(node);
-        }
-    }
-
-    template <class A, class G>
-    inline void hash_table_manager<A, G>::delete_to_bucket_end(node_ptr begin)
-    {
-        while(BOOST_UNORDERED_BORLAND_BOOL(begin)) {
-            node_ptr node = begin;
-            begin = next_node(begin);
-            destruct_node(node);
-        }
-    }
-
-    template <class A, class G>
-    inline void hash_table_manager<A, G>::clear_bucket(bucket_ptr b)
-    {
-        node_ptr node_it = b->next_;
-        b->next_ = node_ptr();
-
-        while(node_it) {
-            node_ptr node_to_destruct = node_it;
-            node_it = next_node(node_it);
-            destruct_node(node_to_destruct);
-        }
-    }
-
-    template <class A, class G>
-    void hash_table_manager<A, G>::clear()
-    {
-        for(bucket_ptr begin = this->buckets_begin(), end = this->buckets_end(); begin != end; ++begin) {
-            clear_bucket(begin);
-        }
-
-        this->cached_begin_bucket_ = this->buckets_end();
-        this->size_ = 0;
-    }
-
-    template <class A, class G>
-    inline void hash_table_manager<A, G>::delete_buckets()
-    {      
-        clear();
-
-        // Destroy the buckets (including the sentinel bucket).
-        bucket_ptr end = this->buckets_end();
-        ++end;
-        for(bucket_ptr begin = this->buckets_begin(); begin != end; ++begin) {
-            bucket_alloc().destroy(begin);
-        }
-
-        bucket_alloc().deallocate(this->buckets_begin(), this->bucket_count() + 1);
-
-        this->buckets_= bucket_ptr();
-    }
-
-    template <class A, class G>
-    BOOST_DEDUCED_TYPENAME hash_table_manager<A, G>::iterator_base
-        hash_table_manager<A, G>::erase(iterator_base r)
-    {
-        BOOST_ASSERT(!r.is_end());
-        iterator_base next = r;
-        next.increment();
-        --this->size_;
-        node::unlink_node(*r.bucket_, r.node_);
-        destruct_node(r.node_);
-        // r has been invalidated but its bucket is still valid
-        this->recompute_begin_bucket(r.bucket_, next.bucket_);
-        return next;
-    }
-
-    template <class A, class G>
-    inline std::size_t hash_table_manager<A, G>::erase_group(node_ptr* it, bucket_ptr bucket)
-    {
-        node_ptr pos = *it;
-        std::size_t count = node::group_count(*it);
-        this->size_ -= count;
-        node::unlink_group(it);
-        delete_group(pos);
-        this->recompute_begin_bucket(bucket);
-        return count;
-    }
-    
-    template <class A, class G>
-    BOOST_DEDUCED_TYPENAME hash_table_manager<A, G>::iterator_base
-        hash_table_manager<A, G>::erase_range(iterator_base r1, iterator_base r2)
-    {
-        if(r1 != r2)
-        {
-            BOOST_ASSERT(!r1.is_end());
-
-            if (r1.bucket_ == r2.bucket_) {
-                this->size_ -= node_count(r1.node_, r2.node_);
-                node::unlink_nodes(*r1.bucket_, r1.node_, r2.node_);
-                delete_nodes(r1.node_, r2.node_);
-
-                // No need to call recompute_begin_bucket because
-                // the nodes are only deleted from one bucket, which
-                // still contains r2 after the erase.
-                BOOST_ASSERT(r1.bucket_->next_);
-            }
-            else {
-                BOOST_ASSERT(r1.bucket_ < r2.bucket_);
-
-                this->size_ -= node_count(r1.node_, node_ptr());
-                node::unlink_nodes(*r1.bucket_, r1.node_, node_ptr());
-                delete_to_bucket_end(r1.node_);
-
-                bucket_ptr i = r1.bucket_;
-                for(++i; i != r2.bucket_; ++i) {
-                    this->size_ -= node_count(i->next_, node_ptr());
-                    clear_bucket(i);
-                }
-
-                if(!r2.is_end()) {
-                    node_ptr first = r2.bucket_->next_;
-                    this->size_ -= node_count(r2.bucket_->next_, r2.node_);
-                    node::unlink_nodes(*r2.bucket_, r2.node_);
-                    delete_nodes(first, r2.node_);
-                }
-
-                // r1 has been invalidated but its bucket is still
-                // valid.
-                this->recompute_begin_bucket(r1.bucket_, r2.bucket_);
-            }
-        }
-
-        return r2;
-    }
-
-    ////////////////////////////////////////////////////////////////////////////
-    // hash_iterator_base implementation
-    
-    template <class BucketPtr>
-    inline void hash_iterator_base<BucketPtr>::increment(node_ptr node) {
-        while(!node) {
-            ++bucket_;
-            node = bucket_->next_;
-        }
-
-        node_ = node;
-    }
-
-    template <class BucketPtr>
-    inline void hash_iterator_base<BucketPtr>::increment()
-    {
-        increment(next_node(node_));
-    }
-}}
-
-#endif

Modified: trunk/boost/unordered/detail/table.hpp
==============================================================================
--- trunk/boost/unordered/detail/table.hpp	(original)
+++ trunk/boost/unordered/detail/table.hpp	2009-09-04 03:03:04 EDT (Fri, 04 Sep 2009)
@@ -13,7 +13,7 @@
 #include <boost/config/no_tr1/cmath.hpp>
 #include <boost/iterator/iterator_categories.hpp>
 
-#include <boost/unordered/detail/manager.hpp>
+#include <boost/unordered/detail/buckets.hpp>
 #include <boost/unordered/detail/util.hpp>
 
 namespace boost { namespace unordered_detail {
@@ -135,24 +135,25 @@
     template <class H, class P, class A, class G, class K>
     hash_table<H, P, A, G, K>
         ::hash_table(std::size_t n, hasher const& hf, key_equal const& eq, value_allocator const& a) :
-            manager(a), func_(false), mlf_(1.0f), max_load_(0)
+            buckets(a, next_prime(n)), func_(false), cached_begin_bucket_(), size_(), mlf_(1.0f), max_load_(0)
     {
         std::uninitialized_fill((functions*)this->funcs_, (functions*)this->funcs_+2,
             functions(hf, eq));
-        this->create_buckets(next_prime(n));
+        this->cached_begin_bucket_ = this->buckets_end();
         this->calculate_max_load();
     }
 
     template <class H, class P, class A, class G, class K>
     hash_table<H, P, A, G, K>
         ::hash_table(hash_table const& x) :
-            manager(x), func_(false), mlf_(x.mlf_), max_load_(0)
+            buckets(x.node_alloc(), next_prime(x.min_buckets_for_size(x.size_))), func_(false), cached_begin_bucket_(), size_(), mlf_(x.mlf_), max_load_(0)
     {
         std::uninitialized_fill((functions*)this->funcs_, (functions*)this->funcs_+2,
             x.current());
-        this->create_buckets(next_prime(x.min_buckets_for_size(x.size_)));
         this->calculate_max_load();
         x.copy_buckets_to(*this);
+        this->size_ = x.size_;
+        this->recompute_begin_bucket();
     }
 
     // Copy Construct with allocator
@@ -160,13 +161,15 @@
     template <class H, class P, class A, class G, class K>
     hash_table<H, P, A, G, K>
         ::hash_table(hash_table const& x, value_allocator const& a) :
-            manager(a), func_(false), mlf_(x.mlf_), max_load_(0)
+            buckets(a, next_prime(x.min_buckets_for_size(x.size_))), func_(false), cached_begin_bucket_(), size_(), mlf_(x.mlf_), max_load_(0)
     {
         std::uninitialized_fill((functions*)this->funcs_, (functions*)this->funcs_+2,
             x.current());
-        this->create_buckets(next_prime(x.min_buckets_for_size(x.size_)));
+        this->cached_begin_bucket_ = this->buckets_end();
         this->calculate_max_load();
         x.copy_buckets_to(*this);
+        this->size_ = x.size_;
+        this->recompute_begin_bucket();
     }
 
     // Move Construct
@@ -174,8 +177,13 @@
     template <class H, class P, class A, class G, class K>
     hash_table<H, P, A, G, K>
         ::hash_table(hash_table& x, move_tag m) :
-            manager(x, m), func_(false), mlf_(x.mlf_), max_load_(0)
+            buckets(x, m), func_(false), cached_begin_bucket_(), size_(), mlf_(x.mlf_), max_load_(0)
     {
+        this->cached_begin_bucket_ = x.cached_begin_bucket_;
+        this->size_ = x.size_;
+        x.cached_begin_bucket_ = bucket_ptr();
+        x.size_ = 0;
+
         // TODO: Shouldn't I move the functions if poss.
         std::uninitialized_fill((functions*)this->funcs_, (functions*)this->funcs_+2,
             x.current());
@@ -184,7 +192,7 @@
     template <class H, class P, class A, class G, class K>
     hash_table<H, P, A, G, K>
         ::hash_table(hash_table& x, value_allocator const& a, move_tag m) :
-            manager(x, a, m), func_(false), mlf_(x.mlf_), max_load_(0)
+            buckets(x, a, m), func_(false), cached_begin_bucket_(), size_(), mlf_(x.mlf_), max_load_(0)
     {
         std::uninitialized_fill((functions*)this->funcs_, (functions*)this->funcs_+2,
             x.current());
@@ -192,10 +200,17 @@
         this->calculate_max_load(); // no throw
 
         if(!this->buckets_) {
-            this->create_buckets(next_prime(x.min_buckets_for_size(x.size_)));
-            // This can throw, but hash_table_manager's destructor will clean
-            // up.
-            x.copy_buckets_to(*this);
+            buckets new_buckets(this->node_alloc(), x.min_buckets_for_size(x.size_));
+            x.copy_buckets_to(new_buckets);
+            new_buckets.swap(*this);
+            this->size_ = x.size_;
+            this->recompute_begin_bucket();
+        }
+        else {
+            this->cached_begin_bucket_ = x.cached_begin_bucket_;
+            this->size_ = x.size_;
+            x.cached_begin_bucket_ = bucket_ptr();
+            x.size_ = 0;
         }
     }
 
@@ -205,7 +220,8 @@
         BOOST_UNORDERED_DESTRUCT(this->get_functions(false), functions);
         BOOST_UNORDERED_DESTRUCT(this->get_functions(true), functions);
     }
-     
+
+    // TODO: Reuse current nodes amd buckets?
     template <class H, class P, class A, class G, class K>
     hash_table<H, P, A, G, K>& hash_table<H, P, A, G, K>::operator=(hash_table const& x)
     {
@@ -214,11 +230,14 @@
             this->set_functions(
                 this->buffer_functions(x));       // throws, strong
             this->mlf_ = x.mlf_;                  // no throw
+            buckets new_buckets(this->node_alloc(), x.min_buckets_for_size(x.size_));
+            x.copy_buckets_to(new_buckets);
+            new_buckets.swap(*this);
             this->calculate_max_load();           // no throw
-            this->reserve(x.size_);               // throws
-            x.copy_buckets_to(*this);             // throws
+            this->size_ = x.size_;
+            this->recompute_begin_bucket();
         }
-        
+
         return *this;
     }
 
@@ -250,25 +269,28 @@
         functions_ptr new_func_that = x.buffer_functions(*this);
 
         if(this->node_alloc() == x.node_alloc()) {
-            this->manager::swap(x); // No throw
+            this->buckets::swap(x); // No throw
+            std::swap(this->cached_begin_bucket_, x.cached_begin_bucket_);
+            std::swap(this->size_, x.size_);
         }
         else {
-            // Create new buckets in separate hash_table_manager objects
+            // Create new buckets in separate hash_buckets objects
             // which will clean up if anything throws an exception.
             // (all can throw, but with no effect as these are new objects).
 
-            manager new_this(*this);
-            new_this.create_buckets(x.min_buckets_for_size(x.size_));
+            buckets new_this(this->node_alloc(), x.min_buckets_for_size(x.size_));
             x.copy_buckets_to(new_this);
 
-            manager new_that(x);
-            new_that.create_buckets(this->min_buckets_for_size(this->size_));
+            buckets new_that(x.node_alloc(), this->min_buckets_for_size(this->size_));
             copy_buckets_to(new_that);
 
             // Modifying the data, so no throw from now on.
             
-            this->manager::swap(new_this);
-            x.manager::swap(new_that);
+            this->buckets::swap(new_this);
+            x.buckets::swap(new_that);
+            std::swap(this->size_, x.size_);
+            this->recompute_begin_bucket();
+            x.recompute_begin_bucket();
         }
 
         // The rest is no throw.
@@ -300,19 +322,24 @@
         functions_ptr new_func_this = this->buffer_functions(x);
 
         if(this->node_alloc() == x.node_alloc()) {
-            this->manager::move(x); // no throw
+            this->buckets::move(x); // no throw
+            this->size_ = x.size_;
+            this->cached_begin_bucket_ = x.cached_begin_bucket_;
+            x.size_ = 0;
+            x.cached_begin_bucket_ = bucket_ptr();
         }
         else {
             // Create new buckets in separate HASH_TABLE_DATA objects
             // which will clean up if anything throws an exception.
             // (all can throw, but with no effect as these are new objects).
             
-            manager new_this(*this);
-            new_this.create_buckets(next_prime(x.min_buckets_for_size(x.size_)));
+            buckets new_this(this->node_alloc(), next_prime(x.min_buckets_for_size(x.size_)));
             x.copy_buckets_to(new_this);
 
             // Start updating the data here, no throw from now on.
-            this->manager::move(new_this);
+            this->buckets::move(new_this);
+            this->size_ = x.size_;
+            this->recompute_begin_bucket();
         }
 
         // We've made it, the rest is no throw.
@@ -383,28 +410,13 @@
         if (n == this->bucket_count())  // no throw
             return;
 
-        manager new_buckets(*this);             // throws, seperate
-        new_buckets.create_buckets(n);          // throws, seperate
-        move_buckets_to(new_buckets);           // basic/no throw
-        new_buckets.swap(*this);                // no throw
-        this->calculate_max_load();             // no throw
-    }
-
-    ////////////////////////////////////////////////////////////////////////////
-    // move_buckets_to & copy_buckets_to
+        // Save the size to restore it if successful
+        std::size_t size = this->size_;
 
-    // move_buckets_to
-    //
-    // if the hash function throws, basic excpetion safety
-    // no throw otherwise
-
-    template <class H, class P, class A, class G, class K>
-    void hash_table<H, P, A, G, K>
-        ::move_buckets_to(manager& dst)
-    {
-        BOOST_ASSERT(this->node_alloc() == dst.node_alloc());
-        BOOST_ASSERT(this->buckets_ && dst.buckets_);
+        // Create another buckets to move the nodes into.
+        buckets dst(this->node_alloc(), n);// throws, separate
 
+        // Move the nodes to dst.
         hasher const& hf = this->hash_function();
         bucket_ptr end = this->buckets_end();
 
@@ -418,17 +430,25 @@
                 bucket_ptr dst_bucket = dst.bucket_ptr_from_hash(
                         hf(extractor::extract(node::get_value(src_bucket->next_))));
 
+                
                 node_ptr n = src_bucket->next_;
-                std::size_t count = node::group_count(src_bucket->next_);
-                this->size_ -= count;
-                dst.size_ += count;
+                this->size_ -= node::group_count(n);
                 node::unlink_group(&src_bucket->next_);
                 node::add_group_to_bucket(n, *dst_bucket);
-                if(dst_bucket < dst.cached_begin_bucket_) dst.cached_begin_bucket_ = dst_bucket;
             }
         }
+
+        // Swap the new nodes back into the container and setup the local
+        // variables.
+        dst.swap(*this);                        // no throw
+        this->size_ = size;
+        this->recompute_begin_bucket();         // no throw
+        this->calculate_max_load();             // no throw
     }
 
+    ////////////////////////////////////////////////////////////////////////////
+    // copy_buckets_to
+
     // copy_buckets_to
     //
     // basic excpetion safety. If an exception is thrown this will
@@ -436,7 +456,7 @@
 
     template <class H, class P, class A, class G, class K>
     void hash_table<H, P, A, G, K>
-        ::copy_buckets_to(manager& dst) const
+        ::copy_buckets_to(buckets& dst) const
     {
         BOOST_ASSERT(this->buckets_ && dst.buckets_);
 
@@ -459,13 +479,10 @@
                 a.construct(node::get_value(it));
                 node_ptr n = a.release();
                 node::add_to_bucket(n, *dst_bucket);
-                ++dst.size_;
-                if(dst_bucket < dst.cached_begin_bucket_) dst.cached_begin_bucket_ = dst_bucket;
         
                 for(it = next_node(it); it != group_end; it = next_node(it)) {
                     a.construct(node::get_value(it));
                     node::add_after_node(a.release(), n);
-                    ++dst.size_;
                 }
             }
         }
@@ -476,18 +493,6 @@
 
     // strong exception safety
 
-    template <class H, class P, class A, class G, class K>
-    std::size_t hash_table<H, P, A, G, K>
-        ::erase_key(key_type const& k)
-    {
-        // No side effects in initial section
-        bucket_ptr bucket = this->get_bucket(this->bucket_index(k));
-        node_ptr* it = find_for_erase(bucket, k);
-
-        // No throw.
-        return *it ? this->erase_group(it, bucket) : 0;
-    }
-
     // count
     //
     // strong exception safety, no side effects
@@ -563,6 +568,167 @@
             return std::pair<iterator_base, iterator_base>(this->end(), this->end());
         }
     }
+    
+    ////////////////////////////////////////////////////////////////////////////
+    // Erase methods    
+    
+    template <class H, class P, class A, class G, class K>
+    void hash_table<H, P, A, G, K>::clear()
+    {
+        for(bucket_ptr begin = this->buckets_begin(), end = this->buckets_end(); begin != end; ++begin) {
+            this->clear_bucket(begin);
+        }
+
+        this->cached_begin_bucket_ = this->buckets_end();
+        this->size_ = 0;
+    }
+
+    template <class H, class P, class A, class G, class K>
+    std::size_t hash_table<H, P, A, G, K>
+        ::erase_key(key_type const& k)
+    {
+        // No side effects in initial section
+        bucket_ptr bucket = this->get_bucket(this->bucket_index(k));
+        node_ptr* it = this->find_for_erase(bucket, k);
+
+        // No throw.
+        return *it ? this->erase_group(it, bucket) : 0;
+    }
+
+
+    template <class H, class P, class A, class G, class K>
+    BOOST_DEDUCED_TYPENAME hash_table<H, P, A, G, K>::iterator_base
+        hash_table<H, P, A, G, K>::erase(iterator_base r)
+    {
+        BOOST_ASSERT(!r.is_end());
+        iterator_base next = r;
+        next.increment();
+        --this->size_;
+        node::unlink_node(*r.bucket_, r.node_);
+        this->destruct_node(r.node_);
+        // r has been invalidated but its bucket is still valid
+        this->recompute_begin_bucket(r.bucket_, next.bucket_);
+        return next;
+    }
+
+    template <class H, class P, class A, class G, class K>
+    inline std::size_t hash_table<H, P, A, G, K>::erase_group(node_ptr* it, bucket_ptr bucket)
+    {
+        node_ptr pos = *it;
+        std::size_t count = node::group_count(*it);
+        this->size_ -= count;
+        node::unlink_group(it);
+        this->delete_group(pos);
+        this->recompute_begin_bucket(bucket);
+        return count;
+    }
+    
+    template <class H, class P, class A, class G, class K>
+    BOOST_DEDUCED_TYPENAME hash_table<H, P, A, G, K>::iterator_base
+        hash_table<H, P, A, G, K>::erase_range(iterator_base r1, iterator_base r2)
+    {
+        if(r1 != r2)
+        {
+            BOOST_ASSERT(!r1.is_end());
+
+            if (r1.bucket_ == r2.bucket_) {
+                this->size_ -= node_count(r1.node_, r2.node_);
+                node::unlink_nodes(*r1.bucket_, r1.node_, r2.node_);
+                this->delete_nodes(r1.node_, r2.node_);
+
+                // No need to call recompute_begin_bucket because
+                // the nodes are only deleted from one bucket, which
+                // still contains r2 after the erase.
+                BOOST_ASSERT(r1.bucket_->next_);
+            }
+            else {
+                BOOST_ASSERT(r1.bucket_ < r2.bucket_);
+
+                this->size_ -= node_count(r1.node_, node_ptr());
+                node::unlink_nodes(*r1.bucket_, r1.node_, node_ptr());
+                this->delete_to_bucket_end(r1.node_);
+
+                bucket_ptr i = r1.bucket_;
+                for(++i; i != r2.bucket_; ++i) {
+                    this->size_ -= node_count(i->next_, node_ptr());
+                    this->clear_bucket(i);
+                }
+
+                if(!r2.is_end()) {
+                    node_ptr first = r2.bucket_->next_;
+                    this->size_ -= node_count(r2.bucket_->next_, r2.node_);
+                    node::unlink_nodes(*r2.bucket_, r2.node_);
+                    this->delete_nodes(first, r2.node_);
+                }
+
+                // r1 has been invalidated but its bucket is still
+                // valid.
+                this->recompute_begin_bucket(r1.bucket_, r2.bucket_);
+            }
+        }
+
+        return r2;
+    }
+
+
+    template <class H, class P, class A, class G, class K>
+    inline void hash_table<H, P, A, G, K>::recompute_begin_bucket()
+    {
+        if (this->size_ != 0) {
+            this->cached_begin_bucket_ = this->buckets_begin();
+            while (!this->cached_begin_bucket_->next_)
+                ++this->cached_begin_bucket_;
+        } else {
+            this->cached_begin_bucket_ = this->buckets_end();
+        }
+    }
+
+    // recompute_begin_bucket
+    //
+    // After an erase cached_begin_bucket_ might be left pointing to
+    // an empty bucket, so this is called to update it
+    //
+    // no throw
+
+    template <class H, class P, class A, class G, class K>
+    inline void hash_table<H, P, A, G, K>::recompute_begin_bucket(bucket_ptr b)
+    {
+        BOOST_ASSERT(!(b < this->cached_begin_bucket_));
+
+        if(b == this->cached_begin_bucket_)
+        {
+            if (this->size_ != 0) {
+                while (!this->cached_begin_bucket_->next_)
+                    ++this->cached_begin_bucket_;
+            } else {
+                this->cached_begin_bucket_ = this->buckets_end();
+            }
+        }
+    }
+
+    // This is called when a range has been erased
+    //
+    // no throw
+
+    template <class H, class P, class A, class G, class K>
+    inline void hash_table<H, P, A, G, K>::recompute_begin_bucket(bucket_ptr b1, bucket_ptr b2)
+    {
+        BOOST_ASSERT(!(b1 < this->cached_begin_bucket_) && !(b2 < b1));
+        BOOST_ASSERT(BOOST_UNORDERED_BORLAND_BOOL(b2->next_));
+
+        if(b1 == this->cached_begin_bucket_ && !b1->next_)
+            this->cached_begin_bucket_ = b2;
+    }
+
+    // no throw
+    template <class H, class P, class A, class G, class K>
+    inline float hash_table<H, P, A, G, K>::load_factor() const
+    {
+        BOOST_ASSERT(this->bucket_count_ != 0);
+        return static_cast<float>(this->size_)
+            / static_cast<float>(this->bucket_count_);
+	}
+
 }}
 
 #endif

Modified: trunk/boost/unordered/detail/util.hpp
==============================================================================
--- trunk/boost/unordered/detail/util.hpp	(original)
+++ trunk/boost/unordered/detail/util.hpp	2009-09-04 03:03:04 EDT (Fri, 04 Sep 2009)
@@ -14,7 +14,7 @@
 #include <boost/iterator/iterator_categories.hpp>
 #include <boost/preprocessor/seq/size.hpp>
 #include <boost/preprocessor/seq/enum.hpp>
-#include <boost/unordered/detail/manager.hpp>
+#include <boost/unordered/detail/buckets.hpp>
 
 #if !defined(BOOST_UNORDERED_STD_FORWARD)
 
@@ -210,20 +210,20 @@
     template <class Alloc, class Grouped>
     class hash_node_constructor
     {
-        typedef hash_table_manager<Alloc, Grouped> manager;
-        typedef BOOST_DEDUCED_TYPENAME manager::node node;
-        typedef BOOST_DEDUCED_TYPENAME manager::real_node_ptr real_node_ptr;
-        typedef BOOST_DEDUCED_TYPENAME manager::value_type value_type;
+        typedef hash_buckets<Alloc, Grouped> buckets;
+        typedef BOOST_DEDUCED_TYPENAME buckets::node node;
+        typedef BOOST_DEDUCED_TYPENAME buckets::real_node_ptr real_node_ptr;
+        typedef BOOST_DEDUCED_TYPENAME buckets::value_type value_type;
 
-        manager& manager_;
+        buckets& buckets_;
         real_node_ptr node_;
         bool node_constructed_;
         bool value_constructed_;
 
     public:
 
-        hash_node_constructor(manager& m) :
-            manager_(m),
+        hash_node_constructor(buckets& m) :
+            buckets_(m),
             node_(),
             node_constructed_(false),
             value_constructed_(false)
@@ -281,12 +281,12 @@
         }
 
         // no throw
-        BOOST_DEDUCED_TYPENAME manager::node_ptr release()
+        BOOST_DEDUCED_TYPENAME buckets::node_ptr release()
         {
             real_node_ptr p = node_;
             node_ = real_node_ptr();
             // node_ptr cast
-            return manager_.bucket_alloc().address(*p);
+            return buckets_.bucket_alloc().address(*p);
         }
 
     private:
@@ -305,9 +305,9 @@
             }
 
             if (node_constructed_)
-                manager_.node_alloc().destroy(node_);
+                buckets_.node_alloc().destroy(node_);
 
-            manager_.node_alloc().deallocate(node_, 1);
+            buckets_.node_alloc().deallocate(node_, 1);
         }
     }
 
@@ -318,8 +318,8 @@
             node_constructed_ = false;
             value_constructed_ = false;
 
-            node_ = manager_.node_alloc().allocate(1);
-            manager_.node_alloc().construct(node_, node());
+            node_ = buckets_.node_alloc().allocate(1);
+            buckets_.node_alloc().construct(node_, node());
             node_constructed_ = true;
         }
         else {