From: daniel_james_at_[hidden]
Date: 2008-04-26 12:28:45
Author: danieljames
Date: 2008-04-26 12:28:44 EDT (Sat, 26 Apr 2008)
New Revision: 44780
URL: http://svn.boost.org/trac/boost/changeset/44780
Log:
Use my own list container to avoid working around STL container bugs.
Added:
branches/unordered/trunk/libs/unordered/test/helpers/list.hpp (contents, props changed)
Text files modified:
branches/unordered/trunk/libs/unordered/test/helpers/equivalent.hpp | 23 +++++++++--------------
branches/unordered/trunk/libs/unordered/test/helpers/metafunctions.hpp | 29 -----------------------------
branches/unordered/trunk/libs/unordered/test/helpers/random_values.hpp | 4 ++--
branches/unordered/trunk/libs/unordered/test/helpers/strong.hpp | 10 +++++-----
branches/unordered/trunk/libs/unordered/test/helpers/tracker.hpp | 31 +++++++++++++------------------
branches/unordered/trunk/libs/unordered/test/unordered/constructor_tests.cpp | 6 ++----
branches/unordered/trunk/libs/unordered/test/unordered/equivalent_keys_tests.cpp | 4 ++--
branches/unordered/trunk/libs/unordered/test/unordered/erase_equiv_tests.cpp | 16 ++++++----------
branches/unordered/trunk/libs/unordered/test/unordered/find_tests.cpp | 4 ++--
branches/unordered/trunk/libs/unordered/test/unordered/insert_tests.cpp | 5 ++---
10 files changed, 43 insertions(+), 89 deletions(-)
Modified: branches/unordered/trunk/libs/unordered/test/helpers/equivalent.hpp
==============================================================================
--- branches/unordered/trunk/libs/unordered/test/helpers/equivalent.hpp (original)
+++ branches/unordered/trunk/libs/unordered/test/helpers/equivalent.hpp 2008-04-26 12:28:44 EDT (Sat, 26 Apr 2008)
@@ -8,10 +8,10 @@
#include <boost/unordered_map.hpp>
#include <boost/unordered_set.hpp>
-#include <vector>
#include <algorithm>
#include "./metafunctions.hpp"
#include "./fwd.hpp"
+#include "./list.hpp"
namespace test
{
@@ -56,20 +56,17 @@
BOOST_DEDUCED_TYPENAME Container::key_equal key_equal_;
float max_load_factor_;
- typedef BOOST_DEDUCED_TYPENAME non_const_value_type<Container>::type value_type;
- std::vector<value_type> values_;
+ typedef test::list<BOOST_DEDUCED_TYPENAME Container::value_type>
+ value_list;
+ value_list values_;
public:
unordered_equivalence_tester(Container const &x)
: size_(x.size()),
hasher_(x.hash_function()), key_equal_(x.key_eq()),
max_load_factor_(x.max_load_factor()),
- values_()
+ values_(x.begin(), x.end())
{
- // Can't initialise values_ straight from x because of Visual C++ 6
- values_.reserve(x.size());
- std::copy(x.begin(), x.end(), std::back_inserter(values_));
-
- std::sort(values_.begin(), values_.end());
+ values_.sort();
}
bool operator()(Container const& x) const
@@ -80,11 +77,9 @@
(max_load_factor_ == x.max_load_factor()) &&
(values_.size() == x.size()))) return false;
- std::vector<value_type> copy;
- copy.reserve(x.size());
- std::copy(x.begin(), x.end(), std::back_inserter(copy));
- std::sort(copy.begin(), copy.end());
- return(std::equal(values_.begin(), values_.end(), copy.begin()));
+ value_list copy(x.begin(), x.end());
+ copy.sort();
+ return values_ == copy;
}
private:
unordered_equivalence_tester();
Added: branches/unordered/trunk/libs/unordered/test/helpers/list.hpp
==============================================================================
--- (empty file)
+++ branches/unordered/trunk/libs/unordered/test/helpers/list.hpp 2008-04-26 12:28:44 EDT (Sat, 26 Apr 2008)
@@ -0,0 +1,239 @@
+
+// Copyright 2008 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)
+
+// Gratuitous single linked list.
+//
+// Sadly some STL implementations aren't up to scratch and I need a simple
+// cross-platform container. So here it is.
+
+#if !defined(UNORDERED_TEST_LIST_HEADER)
+#define UNORDERED_TEST_LIST_HEADER
+
+#include <boost/operators.hpp>
+#include <boost/limits.hpp>
+#include <functional>
+
+namespace test
+{
+ namespace test_detail
+ {
+ template <typename T>
+ class list_impl
+ {
+ public:
+ class iterator;
+ class const_iterator;
+
+ typedef T value_type;
+ typedef value_type& reference;
+ typedef value_type const& const_reference;
+
+ typedef unsigned int size_type;
+
+ struct node {
+ T value_;
+ node* next_;
+
+ node(T const& v) : value_(v), next_(0) {}
+ node(T const& v, node* n) : value_(v), next_(n) {}
+ };
+
+ class iterator
+ : public boost::forward_iterator_helper<
+ iterator, value_type,
+ int, value_type*, value_type&>
+ {
+ friend class const_iterator;
+ friend class list_impl;
+ node* ptr_;
+ public:
+ iterator() : ptr_(0) {};
+ explicit iterator(node* x) : ptr_(x) {}
+
+ value_type& operator*() const { return ptr_->value_; }
+ iterator& operator++() {
+ ptr_ = ptr_->next_; return *this; }
+ friend bool operator==(iterator const& x,
+ iterator const& y) { return x.ptr_ == y.ptr_; }
+ };
+
+ class const_iterator
+ : public boost::forward_iterator_helper<
+ const_iterator, value_type const,
+ int, value_type const*, value_type const&>
+ {
+ friend class list_impl;
+ node* ptr_;
+ public:
+ const_iterator() : ptr_(0) {}
+ const_iterator(iterator const& x) : ptr_(x.ptr_) {}
+
+ value_type const& operator*() const { return ptr_->value_; }
+ const_iterator& operator++() {
+ ptr_ = ptr_->next_; return *this; }
+ friend bool operator==(const_iterator const& x,
+ const_iterator const& y) { return x.ptr_ == y.ptr_; }
+ };
+
+ protected:
+ node* first_;
+ node** last_ptr_;
+ size_type size_;
+
+ public:
+ list_impl() : first_(0), last_ptr_(&first_), size_(0) {}
+
+ ~list_impl() {
+ while(first_) {
+ node* tmp = first_;
+ first_ = first_->next_;
+ delete tmp;
+ }
+ }
+
+ iterator begin() { return iterator(first_); }
+ iterator end() { return iterator(); }
+ const_iterator begin() const { return iterator(first_); }
+ const_iterator end() const { return iterator(); }
+ const_iterator cbegin() const { return iterator(first_); }
+ const_iterator cend() const { return iterator(); }
+
+ template <class InputIterator>
+ void insert(InputIterator i, InputIterator j) {
+ for(; i != j; ++i)
+ push_back(*i);
+ }
+
+ void push_front(value_type const& v) {
+ first_ = new node(v, first_);
+ if(size_) last_ptr_ = &(*last_ptr_)->next_;
+ ++size_;
+ }
+
+ void push_back(value_type const& v) {
+ *last_ptr_ = new node(v);
+ last_ptr_ = &(*last_ptr_)->next_;
+ ++size_;
+ }
+
+ void clear() {
+ while(first_) {
+ node* tmp = first_;
+ first_ = first_->next_;
+ --size_;
+ delete tmp;
+ }
+ last_ptr_ = &first_;
+ }
+
+ void erase(const_iterator start, const_iterator end) {
+ node** ptr = &first_;
+
+ while(*ptr != start.ptr_) {
+ ptr = &(*ptr)->next_;
+ }
+
+ while(*ptr != end.ptr_) {
+ node* to_delete = *ptr;
+ *ptr = (*ptr)->next_;
+ --size_;
+ delete to_delete;
+ }
+
+ if(!*ptr) last_ptr_ = ptr;
+ }
+
+ bool empty() const {
+ return !size_;
+ }
+
+ size_type size() const {
+ return size_;
+ }
+
+ void sort() {
+ sort(std::less<T>());
+ }
+
+ template <typename Less>
+ void sort(Less less = Less()) {
+ if(!this->empty()) merge_sort(&this->first_,
+ (std::numeric_limits<size_type>::max)(), less);
+ }
+
+ private:
+
+ template <typename Less>
+ node** merge_sort(node** l, size_type recurse_limit, Less less)
+ {
+ node** ptr = &(*l)->next_;
+ for(size_type count = 0; count < recurse_limit && *ptr; ++count)
+ {
+ ptr = merge_adjacent_ranges(l, ptr,
+ merge_sort(ptr, count, less), less);
+ }
+ return ptr;
+ }
+
+ template <typename Less>
+ node** merge_adjacent_ranges(node** first, node** second,
+ node** third, Less less)
+ {
+ while(first != second) {
+ if(less((*second)->value_, (*first)->value_)) {
+ swap_adjacent_ranges(first, second, third);
+ std::swap(second, third);
+ }
+ first = &(*first)->next_;
+ }
+ return third;
+ }
+
+ void swap_adjacent_ranges(node** first, node** second, node** third)
+ {
+ node* tmp = *first;
+ *first = *second;
+ *second = *third;
+ *third = tmp;
+ if(!*second) this->last_ptr_ = second;
+ }
+
+ list_impl(list_impl const&);
+ list_impl& operator=(list_impl const&);
+ };
+ }
+
+ template <typename T>
+ class list
+ : public test::test_detail::list_impl<T>,
+ boost::equality_comparable1<list<T> >
+
+ {
+ typedef test::test_detail::list_impl<T> base;
+ public:
+ list() : base() {}
+
+ list(list const& other) : base() {
+ this->insert(other.begin(), other.end());
+ }
+
+ template <class InputIterator>
+ list(InputIterator i, InputIterator j) : base() {
+ this->insert(i, j);
+ }
+
+ list& operator=(list const& other) {
+ this->clear();
+ this->insert(other.begin(), other.end());
+ }
+
+ friend bool operator==(list const& x, list const& y) {
+ return x.size() == y.size() &&
+ std::equal(x.begin(), x.end(), y.begin());
+ }
+ };
+}
+
+#endif
Modified: branches/unordered/trunk/libs/unordered/test/helpers/metafunctions.hpp
==============================================================================
--- branches/unordered/trunk/libs/unordered/test/helpers/metafunctions.hpp (original)
+++ branches/unordered/trunk/libs/unordered/test/helpers/metafunctions.hpp 2008-04-26 12:28:44 EDT (Sat, 26 Apr 2008)
@@ -75,35 +75,6 @@
sizeof(has_unique_key_impl((Container const*)0))
== sizeof(no_type));
};
-
- // Non Const Value Type
-
- template <bool IsMap>
- struct non_const_value_type_impl
- {
- template <class Container>
- struct apply {
- typedef std::pair<
- BOOST_DEDUCED_TYPENAME Container::key_type,
- BOOST_DEDUCED_TYPENAME Container::mapped_type> type;
- };
- };
-
- template<>
- struct non_const_value_type_impl<false>
- {
- template <class Container>
- struct apply {
- typedef BOOST_DEDUCED_TYPENAME Container::value_type type;
- };
- };
-
- template <class Container>
- struct non_const_value_type
- : non_const_value_type_impl< ::test::is_map<Container>::value>::
- BOOST_NESTED_TEMPLATE apply<Container>
- {
- };
}
#endif
Modified: branches/unordered/trunk/libs/unordered/test/helpers/random_values.hpp
==============================================================================
--- branches/unordered/trunk/libs/unordered/test/helpers/random_values.hpp (original)
+++ branches/unordered/trunk/libs/unordered/test/helpers/random_values.hpp 2008-04-26 12:28:44 EDT (Sat, 26 Apr 2008)
@@ -6,7 +6,7 @@
#if !defined(BOOST_UNORDERED_TEST_HELPERS_RANDOM_VALUES_HEADER)
#define BOOST_UNORDERED_TEST_HELPERS_RANDOM_VALUES_HEADER
-#include <list>
+#include "./list.hpp"
#include <algorithm>
#include <boost/mpl/if.hpp>
#include "./generators.hpp"
@@ -97,7 +97,7 @@
template <class X>
struct random_values
- : public std::list<BOOST_DEDUCED_TYPENAME X::value_type>
+ : public test::list<BOOST_DEDUCED_TYPENAME X::value_type>
{
random_values(int count, test::random_generator const& generator =
test::default_generator)
Modified: branches/unordered/trunk/libs/unordered/test/helpers/strong.hpp
==============================================================================
--- branches/unordered/trunk/libs/unordered/test/helpers/strong.hpp (original)
+++ branches/unordered/trunk/libs/unordered/test/helpers/strong.hpp 2008-04-26 12:28:44 EDT (Sat, 26 Apr 2008)
@@ -7,10 +7,10 @@
#define BOOST_UNORDERED_TEST_HELPERS_STRONG_HEADER
#include <boost/config.hpp>
-#include <vector>
#include <iterator>
#include "./metafunctions.hpp"
#include "./equivalent.hpp"
+#include "./list.hpp"
#include "../objects/exception.hpp"
namespace test
@@ -18,19 +18,19 @@
template <class X>
class strong
{
- typedef std::vector<BOOST_DEDUCED_TYPENAME non_const_value_type<X>::type> values_type;
+ typedef test::list<BOOST_DEDUCED_TYPENAME X::value_type> values_type;
values_type values_;
public:
void store(X const& x) {
DISABLE_EXCEPTIONS;
values_.clear();
- values_.reserve(x.size());
- std::copy(x.cbegin(), x.cend(), std::back_inserter(values_));
+ values_.insert(x.cbegin(), x.cend());
}
void test(X const& x) const {
if(!(x.size() == values_.size() &&
- std::equal(x.cbegin(), x.cend(), values_.begin(), test::equivalent)))
+ std::equal(x.cbegin(), x.cend(), values_.begin(),
+ test::equivalent)))
BOOST_ERROR("Strong exception safety failure.");
}
};
Modified: branches/unordered/trunk/libs/unordered/test/helpers/tracker.hpp
==============================================================================
--- branches/unordered/trunk/libs/unordered/test/helpers/tracker.hpp (original)
+++ branches/unordered/trunk/libs/unordered/test/helpers/tracker.hpp 2008-04-26 12:28:44 EDT (Sat, 26 Apr 2008)
@@ -11,7 +11,6 @@
#include <set>
#include <map>
-#include <vector>
#include <iterator>
#include <algorithm>
#include <boost/mpl/if.hpp>
@@ -22,6 +21,7 @@
#include "./metafunctions.hpp"
#include "./helpers.hpp"
#include "./equivalent.hpp"
+#include "./list.hpp"
namespace test
{
@@ -44,27 +44,23 @@
template <class X1, class X2>
void compare_range(X1 const& x1, X2 const& x2)
{
- std::vector<BOOST_DEDUCED_TYPENAME non_const_value_type<X1>::type> values1, values2;
- values1.reserve(x1.size());
- values2.reserve(x2.size());
- std::copy(x1.begin(), x1.end(), std::back_inserter(values1));
- std::copy(x2.begin(), x2.end(), std::back_inserter(values2));
- std::sort(values1.begin(), values1.end());
- std::sort(values2.begin(), values2.end());
+ typedef test::list<BOOST_DEDUCED_TYPENAME X1::value_type> value_list;
+ value_list values1(x1.begin(), x1.end());
+ value_list values2(x2.begin(), x2.end());
+ values1.sort();
+ values2.sort();
BOOST_CHECK(values1.size() == values2.size() &&
- std::equal(values1.begin(), values1.end(), values2.begin(), test::equivalent));
+ std::equal(values1.begin(), values1.end(), values2.begin(),
+ test::equivalent));
}
template <class X1, class X2, class T>
void compare_pairs(X1 const& x1, X2 const& x2, T*)
{
- std::vector<T> values1, values2;
- values1.reserve(std::distance(x1.first, x1.second));
- values2.reserve(std::distance(x2.first, x2.second));
- std::copy(x1.first, x1.second, std::back_inserter(values1));
- std::copy(x2.first, x2.second, std::back_inserter(values2));
- std::sort(values1.begin(), values1.end());
- std::sort(values2.begin(), values2.end());
+ test::list<T> values1(x1.first, x1.second);
+ test::list<T> values2(x2.first, x2.second);
+ values1.sort();
+ values2.sort();
BOOST_CHECK(values1.size() == values2.size() &&
std::equal(values1.begin(), values1.end(), values2.begin(), test::equivalent));
}
@@ -123,8 +119,7 @@
compare_pairs(
x.equal_range(get_key<X>(val)),
this->equal_range(get_key<X>(val)),
- (BOOST_DEDUCED_TYPENAME non_const_value_type<X>::type*) 0
- );
+ (BOOST_DEDUCED_TYPENAME X::value_type*) 0);
}
template <class It>
Modified: branches/unordered/trunk/libs/unordered/test/unordered/constructor_tests.cpp
==============================================================================
--- branches/unordered/trunk/libs/unordered/test/unordered/constructor_tests.cpp (original)
+++ branches/unordered/trunk/libs/unordered/test/unordered/constructor_tests.cpp 2008-04-26 12:28:44 EDT (Sat, 26 Apr 2008)
@@ -257,11 +257,9 @@
{
std::cerr<<"map_constructor_test\n";
- typedef std::list<std::pair<BOOST_DEDUCED_TYPENAME T::key_type, BOOST_DEDUCED_TYPENAME T::mapped_type> > list;
+ typedef test::list<std::pair<BOOST_DEDUCED_TYPENAME T::key_type, BOOST_DEDUCED_TYPENAME T::mapped_type> > list;
test::random_values<T> v(1000);
- list l;
- std::copy(v.begin(), v.end(), std::back_inserter(l));
-
+ list l(v.begin(), v.end());
T x(l.begin(), l.end());
test::check_container(x, v);
Modified: branches/unordered/trunk/libs/unordered/test/unordered/equivalent_keys_tests.cpp
==============================================================================
--- branches/unordered/trunk/libs/unordered/test/unordered/equivalent_keys_tests.cpp (original)
+++ branches/unordered/trunk/libs/unordered/test/unordered/equivalent_keys_tests.cpp 2008-04-26 12:28:44 EDT (Sat, 26 Apr 2008)
@@ -8,7 +8,7 @@
#include "../helpers/test.hpp"
#include <algorithm>
#include <map>
-#include <list>
+#include "../helpers/list.hpp"
#include "../helpers/tracker.hpp"
#include "../helpers/invariants.hpp"
@@ -57,7 +57,7 @@
UNORDERED_AUTO_TEST(map_tests)
{
- typedef std::list<std::pair<int const, int> > values_type;
+ typedef test::list<std::pair<int const, int> > values_type;
values_type v[5];
v[0].push_back(std::pair<int const, int>(1,1));
v[1].push_back(std::pair<int const, int>(28,34));
Modified: branches/unordered/trunk/libs/unordered/test/unordered/erase_equiv_tests.cpp
==============================================================================
--- branches/unordered/trunk/libs/unordered/test/unordered/erase_equiv_tests.cpp (original)
+++ branches/unordered/trunk/libs/unordered/test/unordered/erase_equiv_tests.cpp 2008-04-26 12:28:44 EDT (Sat, 26 Apr 2008)
@@ -8,7 +8,7 @@
#include <boost/unordered_map.hpp>
#include "../helpers/test.hpp"
-#include <list>
+#include "../helpers/list.hpp"
#include <set>
#include <iostream>
#include <iterator>
@@ -50,7 +50,7 @@
collision2_hash, std::equal_to<int>,
test::allocator<std::pair<int const, int> > > collide_map2;
typedef collide_map::value_type collide_value;
-typedef std::list<collide_value> collide_list;
+typedef test::list<collide_value> collide_list;
UNORDERED_AUTO_TEST(empty_range_tests)
{
@@ -108,10 +108,8 @@
template<class Range1, class Range2>
bool compare(Range1 const& x, Range2 const& y)
{
- collide_list a;
- collide_list b;
- std::copy(x.begin(), x.end(), std::back_inserter(a));
- std::copy(y.begin(), y.end(), std::back_inserter(b));
+ collide_list a(x.begin(), x.end());
+ collide_list b(y.begin(), y.end());
a.sort();
b.sort();
return a == b;
@@ -120,8 +118,7 @@
template <class Container>
bool general_erase_range_test(Container& x, int start, int end)
{
- collide_list l;
- std::copy(x.begin(), x.end(), std::back_inserter(l));
+ 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));
return compare(l, x);
@@ -133,8 +130,7 @@
for(std::size_t length = 0; length < x.size(); ++length) {
for(std::size_t position = 0; position < x.size() - length; ++position) {
Container y(x);
- collide_list init;
- std::copy(y.begin(), y.end(), std::back_inserter(init));
+ collide_list init(y.begin(), y.end());
if(!general_erase_range_test(y, position, position + length)) {
BOOST_ERROR("general_erase_range_test failed.");
std::cout<<"Erase: ["<<position<<","<<position + length<<")\n";
Modified: branches/unordered/trunk/libs/unordered/test/unordered/find_tests.cpp
==============================================================================
--- branches/unordered/trunk/libs/unordered/test/unordered/find_tests.cpp (original)
+++ branches/unordered/trunk/libs/unordered/test/unordered/find_tests.cpp 2008-04-26 12:28:44 EDT (Sat, 26 Apr 2008)
@@ -43,10 +43,10 @@
test::compare_pairs(x.equal_range(key),
tracker.equal_range(key),
- (BOOST_DEDUCED_TYPENAME test::non_const_value_type<X>::type*) 0);
+ (BOOST_DEDUCED_TYPENAME X::value_type*) 0);
test::compare_pairs(x_const.equal_range(key),
tracker.equal_range(key),
- (BOOST_DEDUCED_TYPENAME test::non_const_value_type<X>::type*) 0);
+ (BOOST_DEDUCED_TYPENAME X::value_type*) 0);
}
test::random_values<X> v2(500, generator);
Modified: branches/unordered/trunk/libs/unordered/test/unordered/insert_tests.cpp
==============================================================================
--- branches/unordered/trunk/libs/unordered/test/unordered/insert_tests.cpp (original)
+++ branches/unordered/trunk/libs/unordered/test/unordered/insert_tests.cpp 2008-04-26 12:28:44 EDT (Sat, 26 Apr 2008)
@@ -318,10 +318,9 @@
{
std::cerr<<"associative_insert_range_test\n";
- typedef std::list<std::pair<BOOST_DEDUCED_TYPENAME X::key_type, BOOST_DEDUCED_TYPENAME X::mapped_type> > list;
+ typedef test::list<std::pair<BOOST_DEDUCED_TYPENAME X::key_type, BOOST_DEDUCED_TYPENAME X::mapped_type> > list;
test::random_values<X> v(1000, generator);
- list l;
- std::copy(v.begin(), v.end(), std::back_inserter(l));
+ list l(v.begin(), v.end());
X x; x.insert(l.begin(), l.end());