Boost logo

Boost-Commit :

Subject: [Boost-commit] svn:boost r66151 - in branches/release: boost/unordered boost/unordered/detail libs/unordered libs/unordered/doc libs/unordered/test/exception libs/unordered/test/helpers libs/unordered/test/unordered
From: dnljms_at_[hidden]
Date: 2010-10-23 08:02:21


Author: danieljames
Date: 2010-10-23 08:02:18 EDT (Sat, 23 Oct 2010)
New Revision: 66151
URL: http://svn.boost.org/trac/boost/changeset/66151

Log:
Merge fix for unordered container insertion bug.

Properties modified:
   branches/release/boost/unordered/ (props changed)
   branches/release/libs/unordered/ (props changed)
Text files modified:
   branches/release/boost/unordered/detail/unique.hpp | 63 ++++++++++++++++----------
   branches/release/libs/unordered/doc/changes.qbk | 5 ++
   branches/release/libs/unordered/test/exception/constructor_exception_tests.cpp | 16 ++++++
   branches/release/libs/unordered/test/helpers/input_iterator.hpp | 92 +++++++++++++++++++++++++++++++++++++++
   branches/release/libs/unordered/test/unordered/constructor_tests.cpp | 15 ++++++
   branches/release/libs/unordered/test/unordered/insert_tests.cpp | 14 +++++
   6 files changed, 176 insertions(+), 29 deletions(-)

Modified: branches/release/boost/unordered/detail/unique.hpp
==============================================================================
--- branches/release/boost/unordered/detail/unique.hpp (original)
+++ branches/release/boost/unordered/detail/unique.hpp 2010-10-23 08:02:18 EDT (Sat, 23 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: branches/release/libs/unordered/doc/changes.qbk
==============================================================================
--- branches/release/libs/unordered/doc/changes.qbk (original)
+++ branches/release/libs/unordered/doc/changes.qbk 2010-10-23 08:02:18 EDT (Sat, 23 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: branches/release/libs/unordered/test/exception/constructor_exception_tests.cpp
==============================================================================
--- branches/release/libs/unordered/test/exception/constructor_exception_tests.cpp (original)
+++ branches/release/libs/unordered/test/exception/constructor_exception_tests.cpp 2010-10-23 08:02:18 EDT (Sat, 23 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: branches/release/libs/unordered/test/helpers/input_iterator.hpp
==============================================================================
--- branches/release/libs/unordered/test/helpers/input_iterator.hpp (original)
+++ branches/release/libs/unordered/test/helpers/input_iterator.hpp 2010-10-23 08:02:18 EDT (Sat, 23 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,96 @@
     {
         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_;
+ }
+ value_type operator[](difference_type d) {
+ return base_[d];
+ }
+ copy_iterator_adaptor& operator++() {
+ ++base_; return *this;
+ }
+ copy_iterator_adaptor operator++(int) {
+ copy_iterator_adaptor tmp(*this); ++base_; return tmp;
+ }
+ copy_iterator_adaptor& operator--() {
+ --base_; return *this;
+ }
+ copy_iterator_adaptor operator--(int) {
+ copy_iterator_adaptor tmp(*this); --base_; return tmp;
+ }
+ copy_iterator_adaptor operator+=(difference_type x) {
+ base_ += x;
+ return *this;
+ }
+ copy_iterator_adaptor operator-=(difference_type x) {
+ base_ -= x;
+ return *this;
+ }
+ copy_iterator_adaptor operator+(difference_type n) {
+ return copy_iterator_adaptor(base_+n);
+ }
+ copy_iterator_adaptor operator-(difference_type n) {
+ return copy_iterator_adaptor(base_-n);
+ }
+ friend copy_iterator_adaptor operator+(
+ difference_type n, copy_iterator_adaptor x) {
+ return x+n;
+ }
+ difference_type operator-(copy_iterator_adaptor const& other) {
+ return base_-other.base_;
+ }
+ bool operator==(copy_iterator_adaptor const& x) const {
+ return base_ == x.base_;
+ }
+ bool operator!=(copy_iterator_adaptor const& x) const {
+ return base_ != x.base_;
+ }
+ bool operator<(copy_iterator_adaptor const& x) const {
+ return base_ < x.base_;
+ }
+ bool operator>(copy_iterator_adaptor const& x) const {
+ return base_ > x.base_;
+ }
+ bool operator<=(copy_iterator_adaptor const& x) const {
+ return base_ <= x.base_;
+ }
+ bool operator>=(copy_iterator_adaptor const& x) const {
+ return base_ >= x.base_;
+ }
+ private:
+ Iterator base_;
+ };
+
+ template <class Iterator>
+ copy_iterator_adaptor<Iterator> copy_iterator(Iterator const& it)
+ {
+ return copy_iterator_adaptor<Iterator>(it);
+ }
+
 }
 
 #endif

Modified: branches/release/libs/unordered/test/unordered/constructor_tests.cpp
==============================================================================
--- branches/release/libs/unordered/test/unordered/constructor_tests.cpp (original)
+++ branches/release/libs/unordered/test/unordered/constructor_tests.cpp 2010-10-23 08:02:18 EDT (Sat, 23 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: branches/release/libs/unordered/test/unordered/insert_tests.cpp
==============================================================================
--- branches/release/libs/unordered/test/unordered/insert_tests.cpp (original)
+++ branches/release/libs/unordered/test/unordered/insert_tests.cpp 2010-10-23 08:02:18 EDT (Sat, 23 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)


Boost-Commit list run by bdawes at acm.org, david.abrahams at rcn.com, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk