Subject: [Boost-commit] svn:boost r66136 - in trunk: boost/unordered/detail libs/unordered/doc libs/unordered/test/exception libs/unordered/test/helpers libs/unordered/test/unordered
From: dnljms_at_[hidden]
Date: 2010-10-21 16:23:45
Author: danieljames
Date: 2010-10-21 16:23:37 EDT (Thu, 21 Oct 2010)
New Revision: 66136
URL: http://svn.boost.org/trac/boost/changeset/66136
Log:
Fix iterator insert bug in unordered_set/unordered_map.
Text files modified:
trunk/boost/unordered/detail/unique.hpp | 63 ++++++++++++++++++++++++---------------
trunk/libs/unordered/doc/changes.qbk | 5 +++
trunk/libs/unordered/test/exception/constructor_exception_tests.cpp | 16 +++++++++
trunk/libs/unordered/test/helpers/input_iterator.hpp | 61 ++++++++++++++++++++++++++++++++++++++
trunk/libs/unordered/test/unordered/constructor_tests.cpp | 15 ++++++++
trunk/libs/unordered/test/unordered/insert_tests.cpp | 14 ++++++++
6 files changed, 145 insertions(+), 29 deletions(-)
Modified: trunk/boost/unordered/detail/unique.hpp
==============================================================================
--- trunk/boost/unordered/detail/unique.hpp (original)
+++ trunk/boost/unordered/detail/unique.hpp 2010-10-21 16:23:37 EDT (Thu, 21 Oct 2010)
@@ -1,6 +1,6 @@
// Copyright (C) 2003-2004 Jeremy B. Maitin-Shepard.
-// Copyright (C) 2005-2009 Daniel James
+// Copyright (C) 2005-2010 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)
@@ -99,6 +99,8 @@
template <class InputIt>
void insert_range_impl(key_type const&, InputIt i, InputIt j);
template <class InputIt>
+ void insert_range_impl2(node_constructor&, key_type const&, InputIt i, InputIt j);
+ template <class InputIt>
void insert_range_impl(no_key, InputIt i, InputIt j);
};
@@ -422,6 +424,36 @@
template <class T>
template <class InputIt>
+ inline void hash_unique_table<T>::insert_range_impl2(
+ node_constructor& a, key_type const& k, InputIt i, InputIt j)
+ {
+ // No side effects in this initial code
+ std::size_t hash_value = this->hash_function()(k);
+ bucket_ptr bucket = this->bucket_ptr_from_hash(hash_value);
+ node_ptr pos = this->find_iterator(bucket, k);
+
+ if (!BOOST_UNORDERED_BORLAND_BOOL(pos)) {
+ // Doesn't already exist, add to bucket.
+ // Side effects only in this block.
+
+ // Create the node before rehashing in case it throws an
+ // exception (need strong safety in such a case).
+ a.construct(*i);
+
+ // reserve has basic exception safety if the hash function
+ // throws, strong otherwise.
+ if(this->size_ + 1 >= this->max_load_) {
+ this->reserve_for_insert(this->size_ + insert_size(i, j));
+ bucket = this->bucket_ptr_from_hash(hash_value);
+ }
+
+ // Nothing after this point can throw.
+ add_node(a, bucket);
+ }
+ }
+
+ template <class T>
+ template <class InputIt>
inline void hash_unique_table<T>::insert_range_impl(
key_type const&, InputIt i, InputIt j)
{
@@ -435,33 +467,14 @@
}
do {
- // No side effects in this initial code
// 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
// different second_type.
- key_type const& k = extractor::extract(*i);
- std::size_t hash_value = this->hash_function()(k);
- bucket_ptr bucket = this->bucket_ptr_from_hash(hash_value);
- node_ptr pos = this->find_iterator(bucket, k);
-
- if (!BOOST_UNORDERED_BORLAND_BOOL(pos)) {
- // Doesn't already exist, add to bucket.
- // Side effects only in this block.
-
- // Create the node before rehashing in case it throws an
- // exception (need strong safety in such a case).
- a.construct(*i);
-
- // reserve has basic exception safety if the hash function
- // throws, strong otherwise.
- if(this->size_ + 1 >= this->max_load_) {
- this->reserve_for_insert(this->size_ + insert_size(i, j));
- bucket = this->bucket_ptr_from_hash(hash_value);
- }
-
- // Nothing after this point can throw.
- add_node(a, bucket);
- }
+ //
+ // TODO: Might be worth storing the value_type instead of the key
+ // here. Could be more efficient if '*i' is expensive. Could be
+ // less efficient if copying the full value_type is expensive.
+ insert_range_impl2(a, extractor::extract(*i), i, j);
} while(++i != j);
}
Modified: trunk/libs/unordered/doc/changes.qbk
==============================================================================
--- trunk/libs/unordered/doc/changes.qbk (original)
+++ trunk/libs/unordered/doc/changes.qbk 2010-10-21 16:23:37 EDT (Thu, 21 Oct 2010)
@@ -129,4 +129,9 @@
* Use Boost.Exception.
* Stop using deprecated `BOOST_HAS_*` macros.
+[h2 Boost 1.45.0]
+
+* Fix a bug when inserting into an `unordered_map` or `unordered_set` using
+ iterators which returns `value_type` by copy.
+
[endsect]
Modified: trunk/libs/unordered/test/exception/constructor_exception_tests.cpp
==============================================================================
--- trunk/libs/unordered/test/exception/constructor_exception_tests.cpp (original)
+++ trunk/libs/unordered/test/exception/constructor_exception_tests.cpp 2010-10-21 16:23:37 EDT (Thu, 21 Oct 2010)
@@ -148,6 +148,19 @@
}
};
+template <class T>
+struct copy_range_construct_test : public range<T>, objects
+{
+ copy_range_construct_test() : range<T>(60) {}
+
+ void run() const {
+ T x(test::copy_iterator(this->values.begin()),
+ test::copy_iterator(this->values.end()),
+ 0, hash, equal_to, allocator);
+ avoid_unused_warning(x);
+ }
+};
+
RUN_EXCEPTION_TESTS(
(construct_test1)
(construct_test2)
@@ -160,5 +173,6 @@
(range_construct_test3)
(range_construct_test4)
(range_construct_test5)
- (input_range_construct_test),
+ (input_range_construct_test)
+ (copy_range_construct_test),
CONTAINER_SEQ)
Modified: trunk/libs/unordered/test/helpers/input_iterator.hpp
==============================================================================
--- trunk/libs/unordered/test/helpers/input_iterator.hpp (original)
+++ trunk/libs/unordered/test/helpers/input_iterator.hpp 2010-10-21 16:23:37 EDT (Thu, 21 Oct 2010)
@@ -1,5 +1,5 @@
-// Copyright 2005-2009 Daniel James.
+// Copyright 2005-2010 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)
@@ -69,6 +69,65 @@
{
return input_iterator_adaptor<Iterator>(it);
}
+
+ template <class Iterator>
+ struct copy_iterator_adaptor
+ : public boost::iterator<
+ BOOST_DEDUCED_TYPENAME boost::iterator_category<Iterator>::type,
+ BOOST_DEDUCED_TYPENAME boost::iterator_value<Iterator>::type,
+ BOOST_DEDUCED_TYPENAME boost::iterator_difference<Iterator>::type,
+ BOOST_DEDUCED_TYPENAME boost::iterator_pointer<Iterator>::type,
+ proxy<Iterator>
+ >
+ {
+ typedef BOOST_DEDUCED_TYPENAME boost::iterator_value<Iterator>::type
+ value_type;
+ typedef BOOST_DEDUCED_TYPENAME boost::iterator_difference<Iterator>::type
+ difference_type;
+
+ copy_iterator_adaptor()
+ : base_() {}
+ explicit copy_iterator_adaptor(Iterator const& it)
+ : base_(it) {}
+ value_type operator*() const {
+ return *base_;
+ }
+ value_type* operator->() const {
+ return &*base_;
+ }
+ copy_iterator_adaptor& operator++() {
+ ++base_; return *this;
+ }
+ copy_iterator_adaptor operator++(int) {
+ copy_iterator_adaptor tmp(*this); ++base_; return tmp;
+ }
+ bool operator==(copy_iterator_adaptor const& x) const {
+ return base_ == x.base_;
+ }
+ bool operator!=(copy_iterator_adaptor const& x) const {
+ return base_ != x.base_;
+ }
+ copy_iterator_adaptor operator+=(difference_type x) {
+ base_ += x;
+ return *this;
+ }
+ copy_iterator_adaptor operator-=(difference_type x) {
+ base_ -= x;
+ return *this;
+ }
+ difference_type operator-(copy_iterator_adaptor const& other) {
+ return base_-other.base_;
+ }
+ private:
+ Iterator base_;
+ };
+
+ template <class Iterator>
+ copy_iterator_adaptor<Iterator> copy_iterator(Iterator const& it)
+ {
+ return copy_iterator_adaptor<Iterator>(it);
+ }
+
}
#endif
Modified: trunk/libs/unordered/test/unordered/constructor_tests.cpp
==============================================================================
--- trunk/libs/unordered/test/unordered/constructor_tests.cpp (original)
+++ trunk/libs/unordered/test/unordered/constructor_tests.cpp 2010-10-21 16:23:37 EDT (Thu, 21 Oct 2010)
@@ -1,5 +1,5 @@
-// Copyright 2006-2009 Daniel James.
+// Copyright 2006-2010 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)
@@ -260,6 +260,19 @@
test::check_equivalent_keys(y);
}
+ std::cerr<<"Construct 8.5 - from copy iterator\n";
+ {
+ test::random_values<T> v(100, generator);
+ T x(test::copy_iterator(v.begin()),
+ test::copy_iterator(v.end()), 0, hf1, eq1);
+ T y(test::copy_iterator(x.begin()),
+ test::copy_iterator(x.end()), 0, hf2, eq2);
+ test::check_container(x, v);
+ test::check_container(y, x);
+ test::check_equivalent_keys(x);
+ test::check_equivalent_keys(y);
+ }
+
std::cerr<<"Construct 9\n";
{
test::random_values<T> v(100, generator);
Modified: trunk/libs/unordered/test/unordered/insert_tests.cpp
==============================================================================
--- trunk/libs/unordered/test/unordered/insert_tests.cpp (original)
+++ trunk/libs/unordered/test/unordered/insert_tests.cpp 2010-10-21 16:23:37 EDT (Thu, 21 Oct 2010)
@@ -1,5 +1,5 @@
-// Copyright 2006-2009 Daniel James.
+// Copyright 2006-2010 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)
@@ -229,6 +229,18 @@
test::check_equivalent_keys(x);
}
+
+ std::cerr<<"insert copy iterator range tests.\n";
+
+ {
+ X x;
+
+ test::random_values<X> v(1000, generator);
+ x.insert(test::copy_iterator(v.begin()), test::copy_iterator(v.end()));
+ test::check_container(x, v);
+
+ test::check_equivalent_keys(x);
+ }
}
#if !defined(BOOST_NO_RVALUE_REFERENCES) && !defined(BOOST_NO_VARIADIC_TEMPLATES)