[Boost-commit] svn:boost r44780 - in branches/unordered/trunk/libs/unordered/test: helpers unordered

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());