|
|
Boost-Commit : |
Subject: [Boost-commit] svn:boost r80894 - in trunk: boost/unordered/detail libs/unordered/doc libs/unordered/test/unordered
From: dnljms_at_[hidden]
Date: 2012-10-07 04:19:06
Author: danieljames
Date: 2012-10-07 04:19:01 EDT (Sun, 07 Oct 2012)
New Revision: 80894
URL: http://svn.boost.org/trac/boost/changeset/80894
Log:
Unordered: Fix bug when erasing a range, refs #7471.
Text files modified:
trunk/boost/unordered/detail/equivalent.hpp | 4 ++--
trunk/boost/unordered/detail/table.hpp | 11 ++++++++++-
trunk/libs/unordered/doc/changes.qbk | 4 ++++
trunk/libs/unordered/test/unordered/erase_equiv_tests.cpp | 26 ++++++++++++++++++++++++++
trunk/libs/unordered/test/unordered/erase_tests.cpp | 14 ++++++++++++++
5 files changed, 56 insertions(+), 3 deletions(-)
Modified: trunk/boost/unordered/detail/equivalent.hpp
==============================================================================
--- trunk/boost/unordered/detail/equivalent.hpp (original)
+++ trunk/boost/unordered/detail/equivalent.hpp 2012-10-07 04:19:01 EDT (Sun, 07 Oct 2012)
@@ -676,9 +676,9 @@
if(begin == group2) {
link_pointer end1 = group1->group_prev_;
- link_pointer end2 = group2->group_prev_;
+ link_pointer end2 = end->group_prev_;
group1->group_prev_ = end2;
- group2->group_prev_ = end1;
+ end->group_prev_ = end1;
}
}
}
Modified: trunk/boost/unordered/detail/table.hpp
==============================================================================
--- trunk/boost/unordered/detail/table.hpp (original)
+++ trunk/boost/unordered/detail/table.hpp 2012-10-07 04:19:01 EDT (Sun, 07 Oct 2012)
@@ -618,7 +618,16 @@
{
for(;;) {
n = static_cast<node_pointer>(n->next_);
- if (n == end) return;
+ if (n == end) {
+ if (n) {
+ std::size_t new_bucket_index =
+ policy::to_bucket(bucket_count_, n->hash_);
+ if (bucket_index != new_bucket_index) {
+ get_bucket(new_bucket_index)->next_ = prev;
+ }
+ }
+ return;
+ }
std::size_t new_bucket_index =
policy::to_bucket(bucket_count_, n->hash_);
Modified: trunk/libs/unordered/doc/changes.qbk
==============================================================================
--- trunk/libs/unordered/doc/changes.qbk (original)
+++ trunk/libs/unordered/doc/changes.qbk 2012-10-07 04:19:01 EDT (Sun, 07 Oct 2012)
@@ -3,6 +3,9 @@
/ 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) ]
+[template ticket[number]'''<ulink
+ url="https://svn.boost.org/trac/boost/ticket/'''[number]'''">'''#[number]'''</ulink>''']
+
[section:changes Change Log]
[h2 Review Version]
@@ -211,6 +214,7 @@
* Faster assign, which assigns to existing nodes where possible, rather than
creating entirely new nodes and copy constructing.
+* Fixed bug in `erase_range` ([ticket 7471]).
* Reverted some of the internal changes to how nodes are created, especially
for C++11 compilers. 'construct' and 'destroy' should work a little better
for C++11 allocators.
Modified: trunk/libs/unordered/test/unordered/erase_equiv_tests.cpp
==============================================================================
--- trunk/libs/unordered/test/unordered/erase_equiv_tests.cpp (original)
+++ trunk/libs/unordered/test/unordered/erase_equiv_tests.cpp 2012-10-07 04:19:01 EDT (Sun, 07 Oct 2012)
@@ -12,6 +12,7 @@
#include "../helpers/test.hpp"
#include "../helpers/list.hpp"
+#include "../helpers/invariants.hpp"
#include <set>
#include <iostream>
#include <iterator>
@@ -51,12 +52,21 @@
int operator()(int x) const { return x & 1; }
};
+// For testing erase in lots of buckets.
+struct collision3_hash
+{
+ int operator()(int x) const { return x; }
+};
+
typedef boost::unordered_multimap<int, int,
collision_hash, std::equal_to<int>,
test::allocator1<std::pair<int const, int> > > collide_map;
typedef boost::unordered_multimap<int, int,
collision2_hash, std::equal_to<int>,
test::allocator2<std::pair<int const, int> > > collide_map2;
+typedef boost::unordered_multimap<int, int,
+ collision3_hash, std::equal_to<int>,
+ test::allocator2<std::pair<int const, int> > > collide_map3;
typedef collide_map::value_type collide_value;
typedef test::list<collide_value> collide_list;
@@ -66,6 +76,7 @@
x.erase(x.begin(), x.end());
x.erase(x.begin(), x.begin());
x.erase(x.end(), x.end());
+ test::check_equivalent_keys(x);
}
UNORDERED_AUTO_TEST(single_item_tests)
@@ -76,10 +87,13 @@
collide_map x(init.begin(), init.end());
x.erase(x.begin(), x.begin());
BOOST_TEST(x.count(1) == 1 && x.size() == 1);
+ test::check_equivalent_keys(x);
x.erase(x.end(), x.end());
BOOST_TEST(x.count(1) == 1 && x.size() == 1);
+ test::check_equivalent_keys(x);
x.erase(x.begin(), x.end());
BOOST_TEST(x.count(1) == 0 && x.size() == 0);
+ test::check_equivalent_keys(x);
}
UNORDERED_AUTO_TEST(two_equivalent_item_tests)
@@ -92,6 +106,7 @@
collide_map x(init.begin(), init.end());
x.erase(x.begin(), x.end());
BOOST_TEST(x.count(1) == 0 && x.size() == 0);
+ test::check_equivalent_keys(x);
}
{
@@ -100,6 +115,7 @@
x.erase(x.begin(), boost::next(x.begin()));
BOOST_TEST(x.count(1) == 1 && x.size() == 1 &&
x.begin()->first == 1 && x.begin()->second == value);
+ test::check_equivalent_keys(x);
}
{
@@ -108,6 +124,7 @@
x.erase(boost::next(x.begin()), x.end());
BOOST_TEST(x.count(1) == 1 && x.size() == 1 &&
x.begin()->first == 1 && x.begin()->second == value);
+ test::check_equivalent_keys(x);
}
}
@@ -129,6 +146,8 @@
collide_list l(x.begin(), x.end());
l.erase(boost::next(l.begin(), start), boost::next(l.begin(), end));
x.erase(boost::next(x.begin(), start), boost::next(x.begin(), end));
+
+ test::check_equivalent_keys(x);
return compare(l, x);
}
@@ -191,4 +210,11 @@
std::cout<<"\n";
}
+UNORDERED_AUTO_TEST(exhaustive_collide3_tests)
+{
+ std::cout<<"exhaustive_collide3_tests:\n";
+ exhaustive_erase_tests((collide_map3*) 0, 8, 4);
+ std::cout<<"\n";
+}
+
RUN_TESTS()
Modified: trunk/libs/unordered/test/unordered/erase_tests.cpp
==============================================================================
--- trunk/libs/unordered/test/unordered/erase_tests.cpp (original)
+++ trunk/libs/unordered/test/unordered/erase_tests.cpp 2012-10-07 04:19:01 EDT (Sun, 07 Oct 2012)
@@ -15,6 +15,7 @@
#include "../helpers/tracker.hpp"
#include "../helpers/equivalent.hpp"
#include "../helpers/helpers.hpp"
+#include "../helpers/invariants.hpp"
#include <iostream>
@@ -32,6 +33,7 @@
test::random_values<Container> v(1000, generator);
Container x(v.begin(), v.end());
+ int iterations = 0;
for(BOOST_DEDUCED_TYPENAME test::random_values<Container>::iterator
it = v.begin(); it != v.end(); ++it)
{
@@ -41,6 +43,7 @@
BOOST_TEST(x.size() == old_size - count);
BOOST_TEST(x.count(test::get_key<Container>(*it)) == 0);
BOOST_TEST(x.find(test::get_key<Container>(*it)) == x.end());
+ if (++iterations % 20 == 0) test::check_equivalent_keys(x);
}
}
@@ -51,6 +54,7 @@
test::random_values<Container> v(1000, generator);
Container x(v.begin(), v.end());
std::size_t size = x.size();
+ int iterations = 0;
while(size > 0 && !x.empty())
{
BOOST_DEDUCED_TYPENAME Container::key_type
@@ -62,6 +66,7 @@
BOOST_TEST(pos == x.begin());
BOOST_TEST(x.count(key) == count - 1);
BOOST_TEST(x.size() == size);
+ if (++iterations % 20 == 0) test::check_equivalent_keys(x);
}
BOOST_TEST(x.empty());
}
@@ -73,6 +78,7 @@
test::random_values<Container> v(1000, generator);
Container x(v.begin(), v.end());
std::size_t size = x.size();
+ int iterations = 0;
while(size > 0 && !x.empty())
{
using namespace std;
@@ -96,6 +102,7 @@
next == boost::next(prev));
BOOST_TEST(x.count(key) == count - 1);
BOOST_TEST(x.size() == size);
+ if (++iterations % 20 == 0) test::check_equivalent_keys(x);
}
BOOST_TEST(x.empty());
}
@@ -116,12 +123,15 @@
BOOST_TEST(x.erase(x.end(), x.end()) == x.end());
BOOST_TEST(x.erase(x.begin(), x.begin()) == x.begin());
BOOST_TEST(x.size() == size);
+ test::check_equivalent_keys(x);
BOOST_TEST(x.erase(x.begin(), x.end()) == x.end());
BOOST_TEST(x.empty());
BOOST_TEST(x.begin() == x.end());
+ test::check_equivalent_keys(x);
BOOST_TEST(x.erase(x.begin(), x.end()) == x.begin());
+ test::check_equivalent_keys(x);
}
std::cerr<<"quick_erase(begin()).\n";
@@ -131,6 +141,7 @@
test::random_values<Container> v(1000, generator);
Container x(v.begin(), v.end());
std::size_t size = x.size();
+ int iterations = 0;
while(size > 0 && !x.empty())
{
BOOST_DEDUCED_TYPENAME Container::key_type
@@ -140,6 +151,7 @@
--size;
BOOST_TEST(x.count(key) == count - 1);
BOOST_TEST(x.size() == size);
+ if (++iterations % 20 == 0) test::check_equivalent_keys(x);
}
BOOST_TEST(x.empty());
}
@@ -151,6 +163,7 @@
test::random_values<Container> v(1000, generator);
Container x(v.begin(), v.end());
std::size_t size = x.size();
+ int iterations = 0;
while(size > 0 && !x.empty())
{
using namespace std;
@@ -174,6 +187,7 @@
next == boost::next(prev));
BOOST_TEST(x.count(key) == count - 1);
BOOST_TEST(x.size() == size);
+ if (++iterations % 20 == 0) test::check_equivalent_keys(x);
}
BOOST_TEST(x.empty());
}
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