ceph/src/boost/libs/unordered/test/unordered/erase_equiv_tests.cpp

   1
   2 // Copyright 2006-2009 Daniel James.
   3 // Distributed under the Boost Software License, Version 1.0. (See accompanying
   4 // file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
   5
   6 // The code for erasing elements from containers with equivalent keys is very
   7 // hairy with several tricky edge cases - so explicitly test each one.
   8
   9 #include "../helpers/prefix.hpp"
  10 #include <boost/unordered_map.hpp>
  11 #include "../helpers/postfix.hpp"
  12
  13 #include "../helpers/test.hpp"
  14 #include "../helpers/list.hpp"
  15 #include "../helpers/invariants.hpp"
  16 #include "../helpers/helpers.hpp"
  17 #include <set>
  18 #include <iostream>
  19 #include <iterator>
  20 #include "../objects/test.hpp"
  21
  22 #if BOOST_WORKAROUND(BOOST_MSVC, < 1400)
  23 #pragma warning(disable:4267) // conversion from 'size_t' to 'unsigned int',
  24                               // possible loss of data.
  25 #endif
  26
  27 struct write_pair_type
  28 {
  29     template <class X1, class X2>
  30     void operator()(std::pair<X1, X2> const& x) const
  31     {
  32         std::cout<<"("<<x.first<<","<<x.second<<")";
  33     }
  34 } write_pair;
  35
  36 template <class Container>
  37 void write_container(Container const& x)
  38 {
  39     std::for_each(x.begin(), x.end(), write_pair);
  40     std::cout<<"\n";
  41 }
  42
  43 // Make everything collide - for testing erase in a single bucket.
  44 struct collision_hash
  45 {
  46     std::size_t operator()(int) const { return 0; }
  47 };
  48
  49 // For testing erase in 2 buckets.
  50 struct collision2_hash
  51 {
  52     std::size_t operator()(int x) const { return static_cast<std::size_t>(x & 1); }
  53 };
  54
  55 // For testing erase in lots of buckets.
  56 struct collision3_hash
  57 {
  58     std::size_t operator()(int x) const { return static_cast<std::size_t>(x); }
  59 };
  60
  61 typedef boost::unordered_multimap<int, int,
  62     collision_hash, std::equal_to<int>,
  63     test::allocator1<std::pair<int const, int> > > collide_map;
  64 typedef boost::unordered_multimap<int, int,
  65     collision2_hash, std::equal_to<int>,
  66     test::allocator2<std::pair<int const, int> > > collide_map2;
  67 typedef boost::unordered_multimap<int, int,
  68     collision3_hash, std::equal_to<int>,
  69     test::allocator2<std::pair<int const, int> > > collide_map3;
  70 typedef collide_map::value_type collide_value;
  71 typedef test::list<collide_value> collide_list;
  72
  73 UNORDERED_AUTO_TEST(empty_range_tests)
  74 {
  75     collide_map x;
  76     x.erase(x.begin(), x.end());
  77     x.erase(x.begin(), x.begin());
  78     x.erase(x.end(), x.end());
  79     test::check_equivalent_keys(x);
  80 }
  81
  82 UNORDERED_AUTO_TEST(single_item_tests)
  83 {
  84     collide_list init;
  85     init.push_back(collide_value(1,1));
  86
  87     collide_map x(init.begin(), init.end());
  88     x.erase(x.begin(), x.begin());
  89     BOOST_TEST(x.count(1) == 1 && x.size() == 1);
  90     test::check_equivalent_keys(x);
  91     x.erase(x.end(), x.end());
  92     BOOST_TEST(x.count(1) == 1 && x.size() == 1);
  93     test::check_equivalent_keys(x);
  94     x.erase(x.begin(), x.end());
  95     BOOST_TEST(x.count(1) == 0 && x.size() == 0);
  96     test::check_equivalent_keys(x);
  97 }
  98
  99 UNORDERED_AUTO_TEST(two_equivalent_item_tests)
 100 {
 101     collide_list init;
 102     init.push_back(collide_value(1,1));
 103     init.push_back(collide_value(1,2));
 104
 105     {
 106         collide_map x(init.begin(), init.end());
 107         x.erase(x.begin(), x.end());
 108         BOOST_TEST(x.count(1) == 0 && x.size() == 0);
 109         test::check_equivalent_keys(x);
 110     }
 111
 112     {
 113         collide_map x(init.begin(), init.end());
 114         int value = test::next(x.begin())->second;
 115         x.erase(x.begin(), test::next(x.begin()));
 116         BOOST_TEST(x.count(1) == 1 && x.size() == 1 &&
 117             x.begin()->first == 1 && x.begin()->second == value);
 118         test::check_equivalent_keys(x);
 119     }
 120
 121     {
 122         collide_map x(init.begin(), init.end());
 123         int value = x.begin()->second;
 124         x.erase(test::next(x.begin()), x.end());
 125         BOOST_TEST(x.count(1) == 1 && x.size() == 1 &&
 126                 x.begin()->first == 1 && x.begin()->second == value);
 127         test::check_equivalent_keys(x);
 128     }
 129 }
 130
 131 // More automated tests...
 132
 133 template<class Range1, class Range2>
 134 bool compare(Range1 const& x, Range2 const& y)
 135 {
 136     collide_list a(x.begin(), x.end());
 137     collide_list b(y.begin(), y.end());
 138     a.sort();
 139     b.sort();
 140     return a == b;
 141 }
 142
 143 template <class Container>
 144 bool general_erase_range_test(Container& x, std::size_t start, std::size_t end)
 145 {
 146     collide_list l(x.begin(), x.end());
 147
 148     l.erase(test::next(l.begin(), start), test::next(l.begin(), end));
 149     x.erase(test::next(x.begin(), start), test::next(x.begin(), end));
 150
 151     test::check_equivalent_keys(x);
 152     return compare(l, x);
 153 }
 154
 155 template <class Container>
 156 void erase_subrange_tests(Container const& x)
 157 {
 158     for(std::size_t length = 0; length < x.size(); ++length) {
 159         for(std::size_t position = 0; position < x.size() - length; ++position)
 160         {
 161             Container y(x);
 162             collide_list init(y.begin(), y.end());
 163             if(!general_erase_range_test(y, position, position + length)) {
 164                 BOOST_ERROR("general_erase_range_test failed.");
 165                 std::cout<<"Erase: ["<<position<<","<<position + length<<")\n";
 166                 write_container(init);
 167                 write_container(y);
 168             }
 169         }
 170     }
 171 }
 172
 173 template <class Container>
 174 void x_by_y_erase_range_tests(Container*, int values, int duplicates)
 175 {
 176     Container y;
 177
 178     for(int i = 0; i < values; ++i) {
 179         for(int j = 0; j < duplicates; ++j) {
 180             y.insert(collide_value(i, j));
 181         }
 182     }
 183
 184     std::cout<<"Values: "<<values<<", Duplicates: "<<duplicates<<"\n";
 185     erase_subrange_tests(y);
 186 }
 187
 188 template <class Container>
 189 void exhaustive_erase_tests(Container* x, int num_values,
 190         int num_duplicated)
 191 {
 192     for(int i = 0; i < num_values; ++i) {
 193         for(int j = 0; j < num_duplicated; ++j) {
 194             x_by_y_erase_range_tests(x, i, j);
 195         }
 196     }
 197 }
 198
 199 UNORDERED_AUTO_TEST(exhaustive_collide_tests)
 200 {
 201     std::cout<<"exhaustive_collide_tests:\n";
 202     collide_map m;
 203     exhaustive_erase_tests((collide_map*) 0, 4, 4);
 204     std::cout<<"\n";
 205 }
 206
 207 UNORDERED_AUTO_TEST(exhaustive_collide2_tests)
 208 {
 209     std::cout<<"exhaustive_collide2_tests:\n";
 210     exhaustive_erase_tests((collide_map2*) 0, 8, 4);
 211     std::cout<<"\n";
 212 }
 213
 214 UNORDERED_AUTO_TEST(exhaustive_collide3_tests)
 215 {
 216     std::cout<<"exhaustive_collide3_tests:\n";
 217     exhaustive_erase_tests((collide_map3*) 0, 8, 4);
 218     std::cout<<"\n";
 219 }
 220
 221 RUN_TESTS()