From: daniel_james_at_[hidden]
Date: 2007-12-19 18:33:31
Author: danieljames
Date: 2007-12-19 18:33:30 EST (Wed, 19 Dec 2007)
New Revision: 42191
URL: http://svn.boost.org/trac/boost/changeset/42191
Log:
Merge: When allocators aren't equal use a slow swap.
Properties modified:
branches/unordered/trunk/ (props changed)
Text files modified:
branches/unordered/trunk/boost/unordered/detail/hash_table_impl.hpp | 43 +++++++++++----------------
branches/unordered/trunk/libs/unordered/doc/rationale.qbk | 61 ++++++++++++++++++++++++++++++++++-----
branches/unordered/trunk/libs/unordered/doc/ref.xml | 48 ++++++++++++++++++++++++++-----
branches/unordered/trunk/libs/unordered/test/exception/Jamfile.v2 | 2
branches/unordered/trunk/libs/unordered/test/unordered/Jamfile.v2 | 2
5 files changed, 113 insertions(+), 43 deletions(-)
Modified: branches/unordered/trunk/boost/unordered/detail/hash_table_impl.hpp
==============================================================================
--- branches/unordered/trunk/boost/unordered/detail/hash_table_impl.hpp (original)
+++ branches/unordered/trunk/boost/unordered/detail/hash_table_impl.hpp 2007-12-19 18:33:30 EST (Wed, 19 Dec 2007)
@@ -1132,32 +1132,17 @@
// Swap
//
- // Swap's behaviour when allocators aren't equal is in dispute, see
- // this paper for full details:
- //
- // http://www.open-std.org/JTC1/SC22/WG21/docs/papers/2004/n1599.html
- //
- // It lists 3 possible behaviours:
- //
- // 1 - If the allocators aren't equal then throw an exception.
- // 2 - Reallocate the elements in the containers with the
- // appropriate allocators - messing up exception safety in
- // the process.
- // 3 - Swap the allocators, hoping that the allocators have a
- // no-throw swap.
- //
- // The paper recommends #3.
+ // Swap's behaviour when allocators aren't equal is in dispute, for
+ // details see:
+ //
+ // http://unordered.nfshost.com/doc/html/unordered/rationale.html#swapping_containers_with_unequal_allocators
//
// ----------------------------------------------------------------
//
// Strong exception safety (might change unused function objects)
//
- // Can throw if hash or predicate object's copy constructor throws.
- // If allocators are unequal:
- // Can throw if allocator's swap throws
- // (I'm assuming that the allocator's swap doesn't throw
- // but this doesn't seem to be guaranteed. Maybe I
- // could double buffer the allocators).
+ // Can throw if hash or predicate object's copy constructor throws
+ // or if allocators are unequal.
void swap(BOOST_UNORDERED_TABLE& x)
{
@@ -1170,10 +1155,18 @@
this->data::swap(x); // no throw
}
else {
- // Note: I'm not sure that allocator swap is guaranteed to be no
- // throw.
- this->allocators_.swap(x.allocators_);
- this->data::swap(x);
+ // 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).
+ data new_this(*this, x.min_buckets_for_size(x.size_));
+ copy_buckets(x, new_this, this->*new_func_this);
+
+ data new_that(x, min_buckets_for_size(this->size_));
+ x.copy_buckets(*this, new_that, x.*new_func_that);
+
+ // Start updating the data here, no throw from now on.
+ this->data::swap(new_this);
+ x.data::swap(new_that);
}
// We've made it, the rest is no throw.
Modified: branches/unordered/trunk/libs/unordered/doc/rationale.qbk
==============================================================================
--- branches/unordered/trunk/libs/unordered/doc/rationale.qbk (original)
+++ branches/unordered/trunk/libs/unordered/doc/rationale.qbk 2007-12-19 18:33:30 EST (Wed, 19 Dec 2007)
@@ -116,19 +116,64 @@
This is
[@http://www.open-std.org/jtc1/sc22/wg21/docs/lwg-active.html#431
Issue 431: Swapping containers with unequal allocators].
+
Howard Hinnant wrote about this in
[@http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2004/n1599.html N1599]
and suggested swapping both the allocators and the containers' contents.
+But the committee have now decided that `swap` should do a fast swap if the
+allocator is Swappable and a slow swap using copy construction otherwise. To
+make this distinction requires concepts.
-There is currently a further issue - if the allocator's swap does throw there's
-no guarantee what state the allocators will be in. The only solution seems to
-be to double buffer the allocators. But I'm assuming that it won't throw for
-now.
+In
+[@http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2007/n2387.pdf
+N2387, Omnibus Allocator Fix-up Proposals],
+Pablo Halpern suggests that there are actually two distinct allocator models,
+"Moves with Value" and "Scoped" which behave differently:
+
+[:
+When allocators are allowed to have state, it is necessary to have a model for
+determining from where an object obtains its allocator. We’ve identified two such
+models: the “Moves with Value†allocator model and the “Scoped†allocator model.
+
+In the “Moves with Value†allocator model, the copy constructor of an allocator-aware
+class will copy both the value and the allocator from its argument. This is the model
+specified in the C++03 standard. With this model, inserting an object into a container
+usually causes the new container item to copy the allocator from the object that was
+inserted. This model can be useful in special circumstances, e.g., if the items within a
+container use an allocator that is specially tuned to the item’s type.
+
+In the “Scoped†allocator model, the allocator used to construct an object is determined
+by the context of that object, much like a storage class. With this model, inserting an
+object into a container causes the new container item to use the same allocator as the
+container. To avoid allocators being used in the wrong context, the allocator is never
+copied during copy or move construction. Thus, it is possible using this model to use
+allocators based on short-lived resources without fear that an object will transfer its
+allocator to a copy that might outlive the (shared) allocator resource. This model is
+reasonably safe and generally useful on a large scale. There was strong support in the
+2005 Tremblant meeting for pursuing an allocator model that propagates allocators
+from container to contained objects.
+]
+
+With these models the choice becomes clearer:
+
+[:
+I introduced the “Moves with Value†allocator model and the
+“Scoped†allocator model. In the former case, the allocator is copied when the container
+is copy-constructed. In the latter case it is not. Swapping the allocators is the right thing
+to do if the containers conform to the “Moves with Value†allocator model and
+absolutely the wrong thing to do if the containers conform to the “Scoped†allocator
+model. With the two allocator models well-defined, the desired behavior becomes clear.
+]
+
+The proposal is that allocators are swapped if the allocator follows the
+"Moves with Value" model and the allocator is swappable. Otherwise a slow swap
+is used. Since containers currently only support the "Moves with Value" model
+this is consistent with the committee's current recommendation (although it
+suggests using a trait to detect if the allocator is swappable rather than a
+concept).
-Update: The committee have now decided that `swap` should do a fast swap if the
-allocator is Swappable and a slow swap using copy construction otherwise. To
-make this distinction requires concepts. For now I'm sticking with the current
-implementation.
+Since there is currently neither have a swappable trait or concept for
+allocators this implementation always performs a slow swap.
[h3 Are insert and erase stable for unordered_multiset and unordered_multimap?]
Modified: branches/unordered/trunk/libs/unordered/doc/ref.xml
==============================================================================
--- branches/unordered/trunk/libs/unordered/doc/ref.xml (original)
+++ branches/unordered/trunk/libs/unordered/doc/ref.xml 2007-12-19 18:33:30 EST (Wed, 19 Dec 2007)
@@ -385,8 +385,12 @@
</parameter>
<type>void</type>
<throws>
- <para>Doesn't throw an exception unless it is thrown by the copy constructor or copy assignment operator of <code>key_equal</code> or <code>hasher</code>.</para>
+ <para>If the allocators are equal, doesn't throw an exception unless it is thrown by the copy constructor or copy assignment operator of <code>key_equal</code> or <code>hasher</code>.</para>
</throws>
+ <notes>
+ <para>For a discussion of the behaviour when allocators aren't equal see
+ <link linkend="unordered.rationale.swapping_containers_with_unequal_allocators">the implementation details</link>.</para>
+ </notes>
</method>
</method-group>
<method-group name="observers">
@@ -610,8 +614,12 @@
<para><code>x.swap(y)</code></para>
</effects>
<throws>
- <para>Doesn't throw an exception unless it is thrown by the copy constructor or copy assignment operator of <code>Hash</code> or <code>Pred</code>.</para>
+ <para>If the allocators are equal, doesn't throw an exception unless it is thrown by the copy constructor or copy assignment operator of <code>Hash</code> or <code>Pred</code>.</para>
</throws>
+ <notes>
+ <para>For a discussion of the behaviour when allocators aren't equal see
+ <link linkend="unordered.rationale.swapping_containers_with_unequal_allocators">the implementation details</link>.</para>
+ </notes>
</function>
</free-function-group>
</class>
@@ -988,8 +996,12 @@
</parameter>
<type>void</type>
<throws>
- <para>Doesn't throw an exception unless it is thrown by the copy constructor or copy assignment operator of <code>key_equal</code> or <code>hasher</code>.</para>
+ <para>If the allocators are equal, doesn't throw an exception unless it is thrown by the copy constructor or copy assignment operator of <code>key_equal</code> or <code>hasher</code>.</para>
</throws>
+ <notes>
+ <para>For a discussion of the behaviour when allocators aren't equal see
+ <link linkend="unordered.rationale.swapping_containers_with_unequal_allocators">the implementation details</link>.</para>
+ </notes>
</method>
</method-group>
<method-group name="observers">
@@ -1213,8 +1225,12 @@
<para><code>x.swap(y)</code></para>
</effects>
<throws>
- <para>Doesn't throw an exception unless it is thrown by the copy constructor or copy assignment operator of <code>Hash</code> or <code>Pred</code>.</para>
+ <para>If the allocators are equal, doesn't throw an exception unless it is thrown by the copy constructor or copy assignment operator of <code>Hash</code> or <code>Pred</code>.</para>
</throws>
+ <notes>
+ <para>For a discussion of the behaviour when allocators aren't equal see
+ <link linkend="unordered.rationale.swapping_containers_with_unequal_allocators">the implementation details</link>.</para>
+ </notes>
</function>
</free-function-group>
</class>
@@ -1608,8 +1624,12 @@
</parameter>
<type>void</type>
<throws>
- <para>Doesn't throw an exception unless it is thrown by the copy constructor or copy assignment operator of <code>key_equal</code> or <code>hasher</code>.</para>
+ <para>If the allocators are equal, doesn't throw an exception unless it is thrown by the copy constructor or copy assignment operator of <code>key_equal</code> or <code>hasher</code>.</para>
</throws>
+ <notes>
+ <para>For a discussion of the behaviour when allocators aren't equal see
+ <link linkend="unordered.rationale.swapping_containers_with_unequal_allocators">the implementation details</link>.</para>
+ </notes>
</method>
</method-group>
<method-group name="observers">
@@ -1869,8 +1889,12 @@
<para><code>x.swap(y)</code></para>
</effects>
<throws>
- <para>Doesn't throw an exception unless it is thrown by the copy constructor or copy assignment operator of <code>Hash</code> or <code>Pred</code>.</para>
+ <para>If the allocators are equal, doesn't throw an exception unless it is thrown by the copy constructor or copy assignment operator of <code>Hash</code> or <code>Pred</code>.</para>
</throws>
+ <notes>
+ <para>For a discussion of the behaviour when allocators aren't equal see
+ <link linkend="unordered.rationale.swapping_containers_with_unequal_allocators">the implementation details</link>.</para>
+ </notes>
</function>
</free-function-group>
</class>
@@ -2255,8 +2279,12 @@
</parameter>
<type>void</type>
<throws>
- <para>Doesn't throw an exception unless it is thrown by the copy constructor or copy assignment operator of <code>key_equal</code> or <code>hasher</code>.</para>
+ <para>If the allocators are equal, doesn't throw an exception unless it is thrown by the copy constructor or copy assignment operator of <code>key_equal</code> or <code>hasher</code>.</para>
</throws>
+ <notes>
+ <para>For a discussion of the behaviour when allocators aren't equal see
+ <link linkend="unordered.rationale.swapping_containers_with_unequal_allocators">the implementation details</link>.</para>
+ </notes>
</method>
</method-group>
<method-group name="observers">
@@ -2482,8 +2510,12 @@
<para><code>x.swap(y)</code></para>
</effects>
<throws>
- <para>Doesn't throw an exception unless it is thrown by the copy constructor or copy assignment operator of <code>Hash</code> or <code>Pred</code>.</para>
+ <para>If the allocators are equal, doesn't throw an exception unless it is thrown by the copy constructor or copy assignment operator of <code>Hash</code> or <code>Pred</code>.</para>
</throws>
+ <notes>
+ <para>For a discussion of the behaviour when allocators aren't equal see
+ <link linkend="unordered.rationale.swapping_containers_with_unequal_allocators">the implementation details</link>.</para>
+ </notes>
</function>
</free-function-group>
</class>
Modified: branches/unordered/trunk/libs/unordered/test/exception/Jamfile.v2
==============================================================================
--- branches/unordered/trunk/libs/unordered/test/exception/Jamfile.v2 (original)
+++ branches/unordered/trunk/libs/unordered/test/exception/Jamfile.v2 2007-12-19 18:33:30 EST (Wed, 19 Dec 2007)
@@ -21,5 +21,5 @@
[ run erase_tests.cpp framework ]
[ run rehash_tests.cpp framework ]
[ run swap_tests.cpp framework : : :
- <define>BOOST_UNORDERED_SWAP_METHOD=3 ]
+ <define>BOOST_UNORDERED_SWAP_METHOD=2 ]
;
Modified: branches/unordered/trunk/libs/unordered/test/unordered/Jamfile.v2
==============================================================================
--- branches/unordered/trunk/libs/unordered/test/unordered/Jamfile.v2 (original)
+++ branches/unordered/trunk/libs/unordered/test/unordered/Jamfile.v2 2007-12-19 18:33:30 EST (Wed, 19 Dec 2007)
@@ -27,5 +27,5 @@
[ run bucket_tests.cpp ]
[ run load_factor_tests.cpp ]
[ run rehash_tests.cpp ]
- [ run swap_tests.cpp : : : <define>BOOST_UNORDERED_SWAP_METHOD=3 ]
+ [ run swap_tests.cpp : : : <define>BOOST_UNORDERED_SWAP_METHOD=2 ]
;