[Boost-commit] svn:boost r73756 - in trunk: boost/unordered/detail libs/unordered/test/helpers libs/unordered/test/objects libs/unordered/test/unordered

Subject: [Boost-commit] svn:boost r73756 - in trunk: boost/unordered/detail libs/unordered/test/helpers libs/unordered/test/objects libs/unordered/test/unordered
From: dnljms_at_[hidden]
Date: 2011-08-14 14:53:31

Author: danieljames
Date: 2011-08-14 14:53:29 EDT (Sun, 14 Aug 2011)
New Revision: 73756
URL: http://svn.boost.org/trac/boost/changeset/73756

Log:
Unordered: Implement allocator propagation on assignment.

It's pretty messy because I'm trying to avoid swapping allocators in
these cases. I'm also not sure of the exception requirements of
allocator swap and assignment.
Added:
   trunk/libs/unordered/test/objects/cxx11_allocator.hpp   (contents, props changed)
Text files modified: 
   trunk/boost/unordered/detail/buckets.hpp             |    16 +++                                     
   trunk/boost/unordered/detail/node.hpp                |     5 +                                       
   trunk/boost/unordered/detail/table.hpp               |   164 +++++++++++++++++++++------------------ 
   trunk/boost/unordered/detail/unique.hpp              |    19 ++++                                    
   trunk/libs/unordered/test/helpers/memory.hpp         |    36 ++++++++                                
   trunk/libs/unordered/test/objects/test.hpp           |    35 +------                                 
   trunk/libs/unordered/test/unordered/assign_tests.cpp |    62 +++++++++++++-                          
   trunk/libs/unordered/test/unordered/move_tests.cpp   |   116 ++++++++++++++++++++++++++-             
   trunk/libs/unordered/test/unordered/swap_tests.cpp   |    89 +++++++++++++++++----                   
   9 files changed, 402 insertions(+), 140 deletions(-)

Modified: trunk/boost/unordered/detail/buckets.hpp
==============================================================================
--- trunk/boost/unordered/detail/buckets.hpp	(original)
+++ trunk/boost/unordered/detail/buckets.hpp	2011-08-14 14:53:29 EDT (Sun, 14 Aug 2011)
@@ -114,6 +114,17 @@
             size_(),
             allocators_(b.allocators_)
         {
+            swap(b);
+        }
+
+        template <typename T>
+        buckets(table<T>& x, move_tag)
+          : buckets_(),
+            bucket_count_(x.bucket_count_),
+            allocators_(x.allocators_)
+        {
+            swap(x);
+            x.size_ = 0;
         }
         
         inline ~buckets()
@@ -152,10 +163,10 @@
             std::swap(size_, other.size_);
         }
 
-        void move(buckets& other)
+        void move_buckets_from(buckets& other)
         {
             BOOST_ASSERT(node_alloc() == other.node_alloc());
-            if(this->buckets_) { this->delete_buckets(); }
+            BOOST_ASSERT(!this->buckets_);
             this->buckets_ = other.buckets_;
             this->bucket_count_ = other.bucket_count_;
             this->size_ = other.size_;
@@ -754,6 +765,7 @@
                 node_ptr first_node = a.release();
                 node::set_hash(first_node, hash);
                 node_ptr end = prev->next_ = first_node;
+                ++dst.size_;
     
                 for(n = n->next_; n != group_end; n = n->next_) {
                     a.construct(boost::move(node::get_value(n)));

Modified: trunk/boost/unordered/detail/node.hpp
==============================================================================
--- trunk/boost/unordered/detail/node.hpp	(original)
+++ trunk/boost/unordered/detail/node.hpp	2011-08-14 14:53:29 EDT (Sun, 14 Aug 2011)
@@ -21,6 +21,11 @@
 
 namespace boost { namespace unordered { namespace detail {
 
+    // Some forward declarations for buckets and tables
+    
+    template <typename T> class table;
+    template <class A, bool Unique> class buckets;
+
     ////////////////////////////////////////////////////////////////////////////
     //
     // This section implements buckets and nodes. Here's a rough

Modified: trunk/boost/unordered/detail/table.hpp
==============================================================================
--- trunk/boost/unordered/detail/table.hpp	(original)
+++ trunk/boost/unordered/detail/table.hpp	2011-08-14 14:53:29 EDT (Sun, 14 Aug 2011)
@@ -43,7 +43,7 @@
         // Members
         
         float mlf_;
-        std::size_t max_load_;
+        std::size_t max_load_; // Only use if this->buckets_.
 
         // Helper methods
 
@@ -195,20 +195,18 @@
         table(table& x, move_tag m)
           : buckets(x, m),
             functions(x),
-            mlf_(1.0f),
-            max_load_(0)
-        {
-            this->partial_swap(x);
-        }
+            mlf_(x.mlf_),
+            max_load_(this->buckets_ ? calculate_max_load() : 0) {}
 
+        // TODO: Why do I use x's bucket count?
         table(table& x, node_allocator const& a, move_tag m)
           : buckets(a, x.bucket_count_),
             functions(x),
             mlf_(x.mlf_),
-            max_load_(0)
+            max_load_(x.max_load_)
         {
             if(a == x.node_alloc()) {
-                this->partial_swap(x);
+                this->buckets::swap(x, false_type());
             }
             else if(x.size_) {
                 // Use a temporary table because move_buckets_to leaves the
@@ -231,43 +229,74 @@
 
         void assign(table const& x)
         {
+            assign(x, integral_constant<bool,
+                allocator_traits<node_allocator>::
+                propagate_on_container_copy_assignment::value>());
+        }
+
+        void assign(table const& x, false_type)
+        {
             table tmp(x, this->node_alloc());
-            this->fast_swap(tmp);
+            this->swap(tmp, false_type());
+        }
+
+        void assign(table const& x, true_type)
+        {
+            table tmp(x, x.node_alloc());
+            // Need to delete before setting the allocator so that buckets
+            // aren't deleted with the wrong allocator.
+            if(this->buckets_) this->delete_buckets();
+            // TODO: Can allocator assignment throw?
+            this->allocators_ = x.allocators_;
+            this->swap(tmp, false_type());
         }
 
         void move_assign(table& x)
         {
-            // This can throw, but it only affects the function objects
-            // that aren't in use so it is strongly exception safe, via.
-            // double buffering.
-            set_hash_functions<hasher, key_equal> new_func_this(*this, x);
-    
+            move_assign(x, integral_constant<bool,
+                allocator_traits<node_allocator>::
+                propagate_on_container_move_assignment::value>());
+        }
+        
+        void move_assign(table& x, true_type)
+        {
+            if(this->buckets_) this->delete_buckets();
+            this->allocators_ = x.allocators_; // TODO: Move allocators, not copy.
+            move_assign_no_alloc(x);
+        }
+
+        void move_assign(table& x, false_type)
+        {
             if(this->node_alloc() == x.node_alloc()) {
-                this->buckets::move(x); // no throw
-                this->mlf_ = x.mlf_;
-                this->max_load_ = x.max_load_;
+                if(this->buckets_) this->delete_buckets();
+                move_assign_no_alloc(x);
             }
             else {
-                // Create new buckets in separate buckets
-                // which will clean up if anything throws an exception.
-                
-                buckets b(this->node_alloc(), x.min_buckets_for_size(x.size_));
+                set_hash_functions<hasher, key_equal> new_func_this(*this, x);
 
                 if (x.size_) {
-                    // Use a temporary table because move_buckets_to leaves the
-                    // source container in a complete mess.
+                    buckets b(this->node_alloc(), x.min_buckets_for_size(x.size_));
                     buckets tmp(x, move_tag());
                     tmp.move_buckets_to(b);
                     b.swap(*this);
-                    this->mlf_ = x.mlf_;
-                    this->max_load_ = calculate_max_load();
                 }
                 else {
-                    b.swap(*this);
-                    this->mlf_ = x.mlf_;
+                    this->clear();
                 }
+                
+                this->mlf_ = x.mlf_;
+                if (this->buckets_) this->max_load_ = calculate_max_load();
+                new_func_this.commit();
             }
-    
+        }
+        
+        void move_assign_no_alloc(table& x)
+        {
+            set_hash_functions<hasher, key_equal> new_func_this(*this, x);
+            // No throw from here.
+            this->move_buckets_from(x);
+            this->mlf_ = x.mlf_;
+            this->max_load_ = x.max_load_;
             new_func_this.commit();
         }
 
@@ -276,40 +305,28 @@
 
         void swap(table& x)
         {
-            // TODO: Should I actually swap the buckets even if this
-            // is with self?
-            if(this != &x) {
-                {
-                    set_hash_functions<hasher, key_equal> op1(*this, x);
-                    set_hash_functions<hasher, key_equal> op2(x, *this);
-    
-                    this->buckets::swap(x, integral_constant<bool,
-                            allocator_traits<node_allocator>::
-                            propagate_on_container_swap::value>());
-    
-                    op1.commit();
-                    op2.commit();
-                }
-
-                std::swap(this->mlf_, x.mlf_);
-                std::swap(this->max_load_, x.max_load_);
-            }
+            swap(x, integral_constant<bool,
+                    allocator_traits<node_allocator>::
+                    propagate_on_container_swap::value>());
         }
 
-        // Swap everything but the allocators
-        void fast_swap(table& x)
-        {
-            {
-                set_hash_functions<hasher, key_equal> op1(*this, x);
-                set_hash_functions<hasher, key_equal> op2(x, *this);
-                op1.commit();
-                op2.commit();
-            }
-            partial_swap(x);
+        // Only swaps the allocators if Propagate::value
+        template <typename Propagate>
+        void swap(table& x, Propagate p)
+        {
+            set_hash_functions<hasher, key_equal> op1(*this, x);
+            set_hash_functions<hasher, key_equal> op2(x, *this);
+            // I think swap can throw if Propagate::value,
+            // since the allocators' swap can throw. Not sure though.
+            this->buckets::swap(x, p);
+            std::swap(this->mlf_, x.mlf_);
+            std::swap(this->max_load_, x.max_load_);
+            op1.commit();
+            op2.commit();
         }
 
         // Swap everything but the allocators, and the functions objects.
-        void partial_swap(table& x)
+        void swap_contents(table& x)
         {
             this->buckets::swap(x, false_type());
             std::swap(this->mlf_, x.mlf_);
@@ -393,24 +410,22 @@
     template <class T>
     inline bool table<T>::reserve_for_insert(std::size_t size)
     {
-        if(size >= max_load_) {
-            if (!this->buckets_) {
-                std::size_t old_bucket_count = this->bucket_count_;
-                this->bucket_count_ = (std::max)(this->bucket_count_,
-                    this->min_buckets_for_size(size));
-                this->create_buckets();
+        if (!this->buckets_) {
+            std::size_t old_bucket_count = this->bucket_count_;
+            this->bucket_count_ = (std::max)(this->bucket_count_,
+                this->min_buckets_for_size(size));
+            this->create_buckets();
+            this->max_load_ = calculate_max_load();
+            return old_bucket_count != this->bucket_count_;
+        }
+        else if(size >= max_load_) {
+            std::size_t num_buckets
+                = this->min_buckets_for_size((std::max)(size,
+                    this->size_ + (this->size_ >> 1)));
+            if (num_buckets != this->bucket_count_) {
+                this->rehash_impl(num_buckets);
                 this->max_load_ = calculate_max_load();
-                return old_bucket_count != this->bucket_count_;
-            }
-            else {
-                std::size_t num_buckets
-                    = this->min_buckets_for_size((std::max)(size,
-                        this->size_ + (this->size_ >> 1)));
-                if (num_buckets != this->bucket_count_) {
-                    this->rehash_impl(num_buckets);
-                    this->max_load_ = calculate_max_load();
-                    return true;
-                }
+                return true;
             }
         }
         
@@ -428,7 +443,6 @@
         if(!this->size_) {
             if(this->buckets_) this->delete_buckets();
             this->bucket_count_ = next_prime(min_buckets);
-            this->max_load_ = 0;
         }
         else {
             // no throw:

Modified: trunk/boost/unordered/detail/unique.hpp
==============================================================================
--- trunk/boost/unordered/detail/unique.hpp	(original)
+++ trunk/boost/unordered/detail/unique.hpp	2011-08-14 14:53:29 EDT (Sun, 14 Aug 2011)
@@ -316,7 +316,14 @@
         void insert_range_impl(key_type const&, InputIt i, InputIt j)
         {
             node_constructor a(*this);
-    
+
+            // Special case for empty buckets so that we can use
+            // max_load_ (which isn't valid when buckets_ is null).
+            if (!this->buckets_) {
+                insert_range_empty(a, extractor::extract(*i), i, j);
+                if (++i == j) return;
+            }
+
             do {
                 // Note: can't use get_key as '*i' might not be value_type - it
                 // could be a pair with first_types as key_type without const or a
@@ -330,6 +337,16 @@
         }
 
         template <class InputIt>
+        void insert_range_empty(node_constructor& a, key_type const& k,
+            InputIt i, InputIt j)
+        {
+            std::size_t hash = this->hash_function()(k);
+            a.construct(*i);
+            this->reserve_for_insert(this->size_ + insert_size(i, j));
+            add_node(a, hash % this->bucket_count_, hash);
+        }
+
+        template <class InputIt>
         void insert_range_impl2(node_constructor& a, key_type const& k,
             InputIt i, InputIt j)
         {

Modified: trunk/libs/unordered/test/helpers/memory.hpp
==============================================================================
--- trunk/libs/unordered/test/helpers/memory.hpp	(original)
+++ trunk/libs/unordered/test/helpers/memory.hpp	2011-08-14 14:53:29 EDT (Sun, 14 Aug 2011)
@@ -137,7 +137,7 @@
             }
 
             void track_deallocate(void* ptr, std::size_t n, std::size_t size,
-                int tag)
+                int tag, bool check_tag_ = true)
             {
                 BOOST_DEDUCED_TYPENAME allocated_memory_type::iterator pos =
                     allocated_memory.find(
@@ -147,7 +147,7 @@
                 } else {
                     BOOST_TEST(pos->first.start == ptr);
                     BOOST_TEST(pos->first.end == (char*) ptr + n * size);
-                    BOOST_TEST(pos->second.tag_ == tag);
+                    if (check_tag_) BOOST_TEST(pos->second.tag_ == tag);
                     allocated_memory.erase(pos);
                 }
                 BOOST_TEST(count_allocations > 0);
@@ -168,6 +168,38 @@
             }
         };
     }
+
+    namespace detail
+    {
+        // This won't be a problem as I'm only using a single compile unit
+        // in each test (this is actually required by the minimal test
+        // framework).
+        // 
+        // boostinspect:nounnamed
+        namespace {
+            test::detail::memory_tracker<std::allocator<int> > tracker;
+        }
+    }
+    
+    template <bool Value>
+    struct bool_type {
+        enum { value = Value };
+    };
+
+    struct true_type {
+        enum { value = true };
+    };
+
+    struct false_type {
+        enum { value = false };
+    };
+
+    template <typename Alloc>
+    struct is_propagate_on_swap : false_type {};
+    template <typename Alloc>
+    struct is_propagate_on_assign : false_type {};
+    template <typename Alloc>
+    struct is_propagate_on_move : false_type {};
 }
 
 #endif

Added: trunk/libs/unordered/test/objects/cxx11_allocator.hpp
==============================================================================
--- (empty file)
+++ trunk/libs/unordered/test/objects/cxx11_allocator.hpp	2011-08-14 14:53:29 EDT (Sun, 14 Aug 2011)
@@ -0,0 +1,210 @@
+
+// Copyright 2006-2011 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)
+
+#if !defined(BOOST_UNORDERED_TEST_CXX11_ALLOCATOR_HEADER)
+#define BOOST_UNORDERED_TEST_CXX11_ALLOCATOR_HEADER
+
+#include <boost/config.hpp>
+#include <boost/limits.hpp>
+#include <cstddef>
+
+#include "../helpers/memory.hpp"
+
+namespace test
+{
+    enum allocator_flags
+    {
+        allocator_false = 0,
+        select_copy = 1,
+        propagate_swap = 2,
+        propagate_assign = 4,
+        propagate_move = 8,
+        allocator_flags_all = 15,
+        no_select_copy = allocator_flags_all - select_copy,
+        no_propagate_swap = allocator_flags_all - propagate_swap,
+        no_propagate_assign = allocator_flags_all - propagate_assign,
+        no_propagate_move = allocator_flags_all - propagate_move
+    };
+    
+    template <int Flag>
+    struct copy_allocator_base
+    {
+        // select_on_copy goes here.
+    };
+
+    template <>
+    struct copy_allocator_base<allocator_false> {};
+
+    template <int Flag>
+    struct swap_allocator_base
+    {
+        struct propagate_on_container_swap {
+            enum { value = Flag != allocator_false }; };
+    };
+
+    template <int Flag>
+    struct assign_allocator_base
+    {
+        struct propagate_on_container_copy_assignment {
+            enum { value = Flag != allocator_false }; };
+    };
+
+    template <int Flag>
+    struct move_allocator_base
+    {
+        struct propagate_on_container_move_assignment {
+            enum { value = Flag != allocator_false }; };
+    };
+
+    namespace
+    {
+        // boostinspect:nounnamed
+        bool force_equal_allocator_value = false;
+    }
+
+    struct force_equal_allocator
+    {
+        bool old_value_;
+    
+        explicit force_equal_allocator(bool value)
+            : old_value_(force_equal_allocator_value)
+        { force_equal_allocator_value = value; }
+        
+        ~force_equal_allocator()
+        { force_equal_allocator_value = old_value_; }
+    };
+
+    template <typename T, allocator_flags Flags = propagate_swap>
+    struct cxx11_allocator :
+        public copy_allocator_base<Flags & select_copy>,
+        public swap_allocator_base<Flags & propagate_swap>,
+        public assign_allocator_base<Flags & propagate_assign>,
+        public move_allocator_base<Flags & propagate_move>
+    {
+        int tag_;
+
+        typedef std::size_t size_type;
+        typedef std::ptrdiff_t difference_type;
+        typedef T* pointer;
+        typedef T const* const_pointer;
+        typedef T& reference;
+        typedef T const& const_reference;
+        typedef T value_type;
+
+        template <typename U> struct rebind {
+            typedef cxx11_allocator<U, Flags> other;
+        };
+
+        explicit cxx11_allocator(int t = 0) : tag_(t)
+        {
+            detail::tracker.allocator_ref();
+        }
+        
+        template <typename Y> cxx11_allocator(
+                cxx11_allocator<Y, Flags> const& x)
+            : tag_(x.tag_)
+        {
+            detail::tracker.allocator_ref();
+        }
+
+        cxx11_allocator(cxx11_allocator const& x)
+            : tag_(x.tag_)
+        {
+            detail::tracker.allocator_ref();
+        }
+
+        ~cxx11_allocator()
+        {
+            detail::tracker.allocator_unref();
+        }
+
+        pointer address(reference r)
+        {
+            return pointer(&r);
+        }
+
+        const_pointer address(const_reference r)
+        {
+            return const_pointer(&r);
+        }
+
+        pointer allocate(size_type n) {
+            pointer ptr(static_cast<T*>(::operator new(n * sizeof(T))));
+            detail::tracker.track_allocate((void*) ptr, n, sizeof(T), tag_);
+            return ptr;
+        }
+
+        pointer allocate(size_type n, void const* u)
+        {
+            pointer ptr(static_cast<T*>(::operator new(n * sizeof(T))));
+            detail::tracker.track_allocate((void*) ptr, n, sizeof(T), tag_);
+            return ptr;
+        }
+
+        void deallocate(pointer p, size_type n)
+        {
+            // Only checking tags when propagating swap.
+            // Note that tags will be tested
+            // properly in the normal allocator.
+            detail::tracker.track_deallocate((void*) p, n, sizeof(T), tag_,
+                (Flags & propagate_swap));
+            ::operator delete((void*) p);
+        }
+
+        void construct(T* p, T const& t) {
+            detail::tracker.track_construct((void*) p, sizeof(T), tag_);
+            new(p) T(t);
+        }
+
+#if defined(BOOST_UNORDERED_STD_FORWARD_MOVE)
+        template<typename... Args> void construct(T* p, Args&&... args) {
+            detail::tracker.track_construct((void*) p, sizeof(T), tag_);
+            new(p) T(std::forward<Args>(args)...);
+        }
+#endif
+
+        void destroy(T* p) {
+            detail::tracker.track_destroy((void*) p, sizeof(T), tag_);
+            p->~T();
+        }
+
+        size_type max_size() const {
+            return (std::numeric_limits<size_type>::max)();
+        }
+
+        // When not propagating swap, allocators are always equal
+        // to avoid undefined behaviour.
+        bool operator==(cxx11_allocator const& x) const
+        {
+            return force_equal_allocator_value || (tag_ == x.tag_);
+        }
+
+        bool operator!=(cxx11_allocator const& x) const
+        {
+            return !(*this == x);
+        }
+    };
+
+    template <typename T, allocator_flags Flags>
+    bool equivalent_impl(
+            cxx11_allocator<T, Flags> const& x,
+            cxx11_allocator<T, Flags> const& y,
+            test::derived_type)
+    {
+        return x.tag_ == y.tag_;
+    }
+
+    template <typename T, allocator_flags Flags>
+    struct is_propagate_on_swap<cxx11_allocator<T, Flags> >
+        : bool_type<(bool)(Flags & propagate_swap)> {};
+    template <typename T, allocator_flags Flags>
+    struct is_propagate_on_assign<cxx11_allocator<T, Flags> >
+        : bool_type<(bool)(Flags & propagate_assign)> {};
+    template <typename T, allocator_flags Flags>
+    struct is_propagate_on_move<cxx11_allocator<T, Flags> >
+        : bool_type<(bool)(Flags & propagate_move)> {};
+}
+
+#endif

Modified: trunk/libs/unordered/test/objects/test.hpp
==============================================================================
--- trunk/libs/unordered/test/objects/test.hpp	(original)
+++ trunk/libs/unordered/test/objects/test.hpp	2011-08-14 14:53:29 EDT (Sun, 14 Aug 2011)
@@ -9,11 +9,9 @@
 #include <boost/config.hpp>
 #include <boost/limits.hpp>
 #include <cstddef>
-#include <iostream>
 #include "../helpers/fwd.hpp"
 #include "../helpers/count.hpp"
 #include "../helpers/memory.hpp"
-#include <map>
 
 namespace test
 {
@@ -28,16 +26,6 @@
     object generate(object const*);
     implicitly_convertible generate(implicitly_convertible const*);
     
-    struct true_type
-    {
-        enum { value = true };
-    };
-
-    struct false_type
-    {
-        enum { value = false };
-    };
-
     class object : globally_counted_object
     {
         friend class hash;
@@ -195,18 +183,6 @@
         }
     };
 
-    namespace detail
-    {
-        // This won't be a problem as I'm only using a single compile unit
-        // in each test (this is actually require by the minimal test
-        // framework).
-        // 
-        // boostinspect:nounnamed
-        namespace {
-            test::detail::memory_tracker<std::allocator<int> > tracker;
-        }
-    }
-
     template <class T>
     class allocator
     {
@@ -308,12 +284,15 @@
         {
             return tag_ != x.tag_;
         }
-        
-        typedef true_type propagate_on_container_copy_assignment;
-        typedef true_type propagate_on_container_move_assignment;
-        typedef true_type propagate_on_container_swap;
     };
 
+    template <typename T>
+    struct is_propagate_on_swap<allocator<T> > : false_type {};
+    template <typename T>
+    struct is_propagate_on_assign<allocator<T> > : false_type {};
+    template <typename T>
+    struct is_propagate_on_move<allocator<T> > : false_type {};
+
     template <class T>
     bool equivalent_impl(allocator<T> const& x, allocator<T> const& y,
         test::derived_type)

Modified: trunk/libs/unordered/test/unordered/assign_tests.cpp
==============================================================================
--- trunk/libs/unordered/test/unordered/assign_tests.cpp	(original)
+++ trunk/libs/unordered/test/unordered/assign_tests.cpp	2011-08-14 14:53:29 EDT (Sun, 14 Aug 2011)
@@ -9,6 +9,7 @@
 #include <boost/unordered_map.hpp>
 #include "../helpers/test.hpp"
 #include "../objects/test.hpp"
+#include "../objects/cxx11_allocator.hpp"
 #include "../helpers/random_values.hpp"
 #include "../helpers/tracker.hpp"
 #include "../helpers/equivalent.hpp"
@@ -68,7 +69,9 @@
     BOOST_DEDUCED_TYPENAME T::key_equal eq2(2);
     BOOST_DEDUCED_TYPENAME T::allocator_type al1(1);
     BOOST_DEDUCED_TYPENAME T::allocator_type al2(2);
-
+    
+    typedef BOOST_DEDUCED_TYPENAME T::allocator_type allocator_type;
+    
     std::cerr<<"assign_tests2.1\n";
     {
         test::check_instances check_;
@@ -92,7 +95,14 @@
         x2 = x1;
         BOOST_TEST(test::equivalent(x2.hash_function(), hf1));
         BOOST_TEST(test::equivalent(x2.key_eq(), eq1));
-        BOOST_TEST(test::equivalent(x2.get_allocator(), al2));
+        if (test::is_propagate_on_assign<allocator_type>::value) {
+            BOOST_TEST(test::equivalent(x2.get_allocator(), al1));
+            BOOST_TEST(!test::equivalent(x2.get_allocator(), al2));
+        }
+        else {
+            BOOST_TEST(test::equivalent(x2.get_allocator(), al2));
+            BOOST_TEST(!test::equivalent(x2.get_allocator(), al1));
+        }
         test::check_container(x2, v1);
     }
 }
@@ -110,16 +120,56 @@
     test::hash, test::equal_to,
     test::allocator<test::object> >* test_multimap;
 
+boost::unordered_set<test::object,
+        test::hash, test::equal_to,
+        test::cxx11_allocator<test::object, test::propagate_assign> >*
+    test_set_prop_assign;
+boost::unordered_multiset<test::object,
+        test::hash, test::equal_to,
+        test::cxx11_allocator<test::object, test::propagate_assign> >*
+    test_multiset_prop_assign;
+boost::unordered_map<test::object, test::object,
+        test::hash, test::equal_to,
+        test::cxx11_allocator<test::object, test::propagate_assign> >*
+    test_map_prop_assign;
+boost::unordered_multimap<test::object, test::object,
+        test::hash, test::equal_to,
+        test::cxx11_allocator<test::object, test::propagate_assign> >*
+    test_multimap_prop_assign;
+
+boost::unordered_set<test::object,
+        test::hash, test::equal_to,
+        test::cxx11_allocator<test::object, test::no_propagate_assign> >*
+    test_set_no_prop_assign;
+boost::unordered_multiset<test::object,
+        test::hash, test::equal_to,
+        test::cxx11_allocator<test::object, test::no_propagate_assign> >*
+    test_multiset_no_prop_assign;
+boost::unordered_map<test::object, test::object,
+        test::hash, test::equal_to,
+        test::cxx11_allocator<test::object, test::no_propagate_assign> >*
+    test_map_no_prop_assign;
+boost::unordered_multimap<test::object, test::object,
+        test::hash, test::equal_to,
+        test::cxx11_allocator<test::object, test::no_propagate_assign> >*
+    test_multimap_no_prop_assign;
+
 using test::default_generator;
 using test::generate_collisions;
 
-UNORDERED_TEST(assign_tests1,
-    ((test_set)(test_multiset)(test_map)(test_multimap))
+UNORDERED_TEST(assign_tests1, (
+        (test_set)(test_multiset)(test_map)(test_multimap)
+        (test_set_prop_assign)(test_multiset_prop_assign)(test_map_prop_assign)(test_multimap_prop_assign)
+        (test_set_no_prop_assign)(test_multiset_no_prop_assign)(test_map_no_prop_assign)(test_multimap_no_prop_assign)
+    )
     ((default_generator)(generate_collisions))
 )
 
-UNORDERED_TEST(assign_tests2,
-    ((test_set)(test_multiset)(test_map)(test_multimap))
+UNORDERED_TEST(assign_tests2, (
+        (test_set)(test_multiset)(test_map)(test_multimap)
+        (test_set_prop_assign)(test_multiset_prop_assign)(test_map_prop_assign)(test_multimap_prop_assign)
+        (test_set_no_prop_assign)(test_multiset_no_prop_assign)(test_map_no_prop_assign)(test_multimap_no_prop_assign)
+    )
     ((default_generator)(generate_collisions))
 )
 

Modified: trunk/libs/unordered/test/unordered/move_tests.cpp
==============================================================================
--- trunk/libs/unordered/test/unordered/move_tests.cpp	(original)
+++ trunk/libs/unordered/test/unordered/move_tests.cpp	2011-08-14 14:53:29 EDT (Sun, 14 Aug 2011)
@@ -9,6 +9,7 @@
 #include <boost/unordered_map.hpp>
 #include "../helpers/test.hpp"
 #include "../objects/test.hpp"
+#include "../objects/cxx11_allocator.hpp"
 #include "../helpers/random_values.hpp"
 #include "../helpers/tracker.hpp"
 #include "../helpers/equivalent.hpp"
@@ -140,7 +141,7 @@
             BOOST_TEST(y.max_load_factor() == 2.0); // Not necessarily required.
             test::check_equivalent_keys(y);
         }
-/*
+
         {
             test::check_instances check_;
 
@@ -161,7 +162,57 @@
             BOOST_TEST(y.max_load_factor() == 1.0); // Not necessarily required.
             test::check_equivalent_keys(y);
         }
-*/    }
+    }
+
+    template <class T>
+    void move_assign_tests2(T*,
+        test::random_generator const& generator = test::default_generator)
+    {
+        BOOST_DEDUCED_TYPENAME T::hasher hf(1);
+        BOOST_DEDUCED_TYPENAME T::key_equal eq(1);
+        BOOST_DEDUCED_TYPENAME T::allocator_type al1(1);
+        BOOST_DEDUCED_TYPENAME T::allocator_type al2(2);
+        typedef BOOST_DEDUCED_TYPENAME T::allocator_type allocator_type;
+
+        {
+            test::random_values<T> v(500, generator);
+            test::random_values<T> v2(0, generator);
+            T y(v.begin(), v.end(), 0, hf, eq, al1);
+            test::object_count count;
+            y = create(v2, count, hf, eq, al2, 2.0);
+            BOOST_TEST(y.empty());
+            test::check_container(y, v2);
+            test::check_equivalent_keys(y);
+            BOOST_TEST(y.max_load_factor() == 2.0);
+            if (test::is_propagate_on_move<allocator_type>::value) {
+                BOOST_TEST(test::equivalent(y.get_allocator(), al2));
+            }
+            else {
+                BOOST_TEST(test::equivalent(y.get_allocator(), al1));
+            }
+        }
+
+        {
+            test::random_values<T> v(500, generator);
+            test::object_count count;
+            T y(0, hf, eq, al1);
+            y = create(v, count, hf, eq, al2, 0.5);
+#if defined(BOOST_HAS_NRVO)
+            if (test::is_propagate_on_move<allocator_type>::value) {
+                BOOST_TEST(count == test::global_object_count);
+            }
+#endif
+            test::check_container(y, v);
+            test::check_equivalent_keys(y);
+            BOOST_TEST(y.max_load_factor() == 0.5);
+            if (test::is_propagate_on_move<allocator_type>::value) {
+                BOOST_TEST(test::equivalent(y.get_allocator(), al2));
+            }
+            else {
+                BOOST_TEST(test::equivalent(y.get_allocator(), al1));
+            }
+        }
+    }
 
     boost::unordered_set<test::object,
         test::hash, test::equal_to,
@@ -176,19 +227,68 @@
         test::hash, test::equal_to,
         test::allocator<test::object> >* test_multimap;
 
+boost::unordered_set<test::object,
+        test::hash, test::equal_to,
+        test::cxx11_allocator<test::object, test::propagate_move> >*
+    test_set_prop_move;
+boost::unordered_multiset<test::object,
+        test::hash, test::equal_to,
+        test::cxx11_allocator<test::object, test::propagate_move> >*
+    test_multiset_prop_move;
+boost::unordered_map<test::object, test::object,
+        test::hash, test::equal_to,
+        test::cxx11_allocator<test::object, test::propagate_move> >*
+    test_map_prop_move;
+boost::unordered_multimap<test::object, test::object,
+        test::hash, test::equal_to,
+        test::cxx11_allocator<test::object, test::propagate_move> >*
+    test_multimap_prop_move;
+
+boost::unordered_set<test::object,
+        test::hash, test::equal_to,
+        test::cxx11_allocator<test::object, test::no_propagate_move> >*
+    test_set_no_prop_move;
+boost::unordered_multiset<test::object,
+        test::hash, test::equal_to,
+        test::cxx11_allocator<test::object, test::no_propagate_move> >*
+    test_multiset_no_prop_move;
+boost::unordered_map<test::object, test::object,
+        test::hash, test::equal_to,
+        test::cxx11_allocator<test::object, test::no_propagate_move> >*
+    test_map_no_prop_move;
+boost::unordered_multimap<test::object, test::object,
+        test::hash, test::equal_to,
+        test::cxx11_allocator<test::object, test::no_propagate_move> >*
+    test_multimap_no_prop_move;
+
     using test::default_generator;
     using test::generate_collisions;
 
-    UNORDERED_TEST(move_construct_tests1,
-        ((test_set)(test_multiset)(test_map)(test_multimap))
+    UNORDERED_TEST(move_construct_tests1, (
+            (test_set)(test_multiset)(test_map)(test_multimap)
+            (test_set_prop_move)(test_multiset_prop_move)(test_map_prop_move)(test_multimap_prop_move)
+            (test_set_no_prop_move)(test_multiset_no_prop_move)(test_map_no_prop_move)(test_multimap_no_prop_move)
+        )
     )
-    UNORDERED_TEST(move_assign_tests1,
-        ((test_set)(test_multiset)(test_map)(test_multimap))
+    UNORDERED_TEST(move_assign_tests1, (
+            (test_set)(test_multiset)(test_map)(test_multimap)
+            (test_set_prop_move)(test_multiset_prop_move)(test_map_prop_move)(test_multimap_prop_move)
+            (test_set_no_prop_move)(test_multiset_no_prop_move)(test_map_no_prop_move)(test_multimap_no_prop_move)
+        )
     )
-    UNORDERED_TEST(move_construct_tests2,
-        ((test_set)(test_multiset)(test_map)(test_multimap))
+    UNORDERED_TEST(move_construct_tests2, (
+            (test_set)(test_multiset)(test_map)(test_multimap)
+            (test_set_prop_move)(test_multiset_prop_move)(test_map_prop_move)(test_multimap_prop_move)
+            (test_set_no_prop_move)(test_multiset_no_prop_move)(test_map_no_prop_move)(test_multimap_no_prop_move)
+        )
         ((default_generator)(generate_collisions))
     )
+    UNORDERED_TEST(move_assign_tests2, (
+            (test_set)(test_multiset)(test_map)(test_multimap)
+            (test_set_prop_move)(test_multiset_prop_move)(test_map_prop_move)(test_multimap_prop_move)
+            (test_set_no_prop_move)(test_multiset_no_prop_move)(test_map_no_prop_move)(test_multimap_no_prop_move)
+        )
+    )
 }
 
 RUN_TESTS()

Modified: trunk/libs/unordered/test/unordered/swap_tests.cpp
==============================================================================
--- trunk/libs/unordered/test/unordered/swap_tests.cpp	(original)
+++ trunk/libs/unordered/test/unordered/swap_tests.cpp	2011-08-14 14:53:29 EDT (Sun, 14 Aug 2011)
@@ -12,6 +12,7 @@
 #include <boost/unordered_map.hpp>
 #include "../helpers/test.hpp"
 #include "../objects/test.hpp"
+#include "../objects/cxx11_allocator.hpp"
 #include "../helpers/random_values.hpp"
 #include "../helpers/tracker.hpp"
 #include "../helpers/invariants.hpp"
@@ -107,15 +108,24 @@
     }
 
     {
+        test::force_equal_allocator force_(
+            !test::is_propagate_on_swap<allocator_type>::value);
         test::check_instances check_;
 
         test::random_values<X> vx(50, generator), vy(100, generator);
         X x(vx.begin(), vx.end(), 0, hasher(), key_equal(), allocator_type(1));
         X y(vy.begin(), vy.end(), 0, hasher(), key_equal(), allocator_type(2));
-        swap_test_impl(x, y);
+
+        if (test::is_propagate_on_swap<allocator_type>::value ||
+            x.get_allocator() == y.get_allocator())
+        {
+            swap_test_impl(x, y);
+        }
     }
 
     {
+        test::force_equal_allocator force_(
+            !test::is_propagate_on_swap<allocator_type>::value);
         test::check_instances check_;
 
         test::random_values<X> vx(100, generator), vy(100, generator);
@@ -123,31 +133,74 @@
             allocator_type(1));
         X y(vy.begin(), vy.end(), 0, hasher(2), key_equal(2),
             allocator_type(2));
-        swap_test_impl(x, y);
-        swap_test_impl(x, y);
+
+        if (test::is_propagate_on_swap<allocator_type>::value ||
+            x.get_allocator() == y.get_allocator())
+        {
+            swap_test_impl(x, y);
+            swap_test_impl(x, y);
+        }
     }
 }
 
 boost::unordered_set<test::object,
-    test::hash, test::equal_to,
-    test::allocator<test::object> >* test_set;
+        test::hash, test::equal_to,
+        test::allocator<test::object> >* test_set;
+boost::unordered_multiset<test::object,
+        test::hash, test::equal_to,
+        test::allocator<test::object> >* test_multiset;
+boost::unordered_map<test::object, test::object,
+        test::hash, test::equal_to,
+        test::allocator<test::object> >* test_map;
+boost::unordered_multimap<test::object, test::object,
+        test::hash, test::equal_to,
+        test::allocator<test::object> >* test_multimap;
+
+boost::unordered_set<test::object,
+        test::hash, test::equal_to,
+        test::cxx11_allocator<test::object, test::propagate_swap> >*
+    test_set_prop_swap;
 boost::unordered_multiset<test::object,
-    test::hash, test::equal_to,
-    test::allocator<test::object> >* test_multiset;
+        test::hash, test::equal_to,
+        test::cxx11_allocator<test::object, test::propagate_swap> >*
+    test_multiset_prop_swap;
 boost::unordered_map<test::object, test::object,
-    test::hash, test::equal_to,
-    test::allocator<test::object> >* test_map;
+        test::hash, test::equal_to,
+        test::cxx11_allocator<test::object, test::propagate_swap> >*
+    test_map_prop_swap;
 boost::unordered_multimap<test::object, test::object,
-    test::hash, test::equal_to,
-    test::allocator<test::object> >* test_multimap;
+        test::hash, test::equal_to,
+        test::cxx11_allocator<test::object, test::propagate_swap> >*
+    test_multimap_prop_swap;
 
-UNORDERED_TEST(swap_tests1,
-    ((test_set)(test_multiset)(test_map)(test_multimap))
-)
-
-UNORDERED_TEST(swap_tests2,
-    ((test_set)(test_multiset)(test_map)(test_multimap))
-)
+boost::unordered_set<test::object,
+        test::hash, test::equal_to,
+        test::cxx11_allocator<test::object, test::no_propagate_swap> >*
+    test_set_no_prop_swap;
+boost::unordered_multiset<test::object,
+        test::hash, test::equal_to,
+        test::cxx11_allocator<test::object, test::no_propagate_swap> >*
+    test_multiset_no_prop_swap;
+boost::unordered_map<test::object, test::object,
+        test::hash, test::equal_to,
+        test::cxx11_allocator<test::object, test::no_propagate_swap> >*
+    test_map_no_prop_swap;
+boost::unordered_multimap<test::object, test::object,
+        test::hash, test::equal_to,
+        test::cxx11_allocator<test::object, test::no_propagate_swap> >*
+    test_multimap_no_prop_swap;
+
+UNORDERED_TEST(swap_tests1, (
+    (test_set)(test_multiset)(test_map)(test_multimap)
+    (test_set_prop_swap)(test_multiset_prop_swap)(test_map_prop_swap)(test_multimap_prop_swap)
+    (test_set_no_prop_swap)(test_multiset_no_prop_swap)(test_map_no_prop_swap)(test_multimap_no_prop_swap)
+))
+
+UNORDERED_TEST(swap_tests2, (
+    (test_set)(test_multiset)(test_map)(test_multimap)
+    (test_set_prop_swap)(test_multiset_prop_swap)(test_map_prop_swap)(test_multimap_prop_swap)
+    (test_set_no_prop_swap)(test_multiset_no_prop_swap)(test_map_no_prop_swap)(test_multimap_no_prop_swap)
+))
 
 }
 RUN_TESTS()