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 // clang-format off
  10 #include "../helpers/prefix.hpp"
  11 #include <boost/unordered_map.hpp>
  12 #include "../helpers/postfix.hpp"
  13 // clang-format on
  14
  15 #include "../helpers/test.hpp"
  16 #include "../helpers/list.hpp"
  17 #include "../helpers/invariants.hpp"
  18 #include "../helpers/helpers.hpp"
  19 #include <set>
  20 #include <iterator>
  21 #include "../objects/test.hpp"
  22
  23 #if BOOST_WORKAROUND(BOOST_MSVC, < 1400)
  24 #pragma warning(disable : 4267) // conversion from 'size_t' to 'unsigned int',
  25                                 // possible loss of data.
  26 #endif
  27
  28 struct write_pair_type
  29 {
  30   template <class X1, class X2>
  31   void operator()(std::pair<X1, X2> const& x) const
  32   {
  33     BOOST_LIGHTWEIGHT_TEST_OSTREAM << "(" << x.first << "," << x.second << ")";
  34   }
  35 } write_pair;
  36
  37 template <class Container> void write_container(Container const& x)
  38 {
  39   std::for_each(x.begin(), x.end(), write_pair);
  40   BOOST_LIGHTWEIGHT_TEST_OSTREAM << "\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
  53   {
  54     return static_cast<std::size_t>(x & 1);
  55   }
  56 };
  57
  58 // For testing erase in lots of buckets.
  59 struct collision3_hash
  60 {
  61   std::size_t operator()(int x) const { return static_cast<std::size_t>(x); }
  62 };
  63
  64 typedef boost::unordered_multimap<int, int, collision_hash, std::equal_to<int>,
  65   test::allocator1<std::pair<int const, int> > >
  66   collide_map;
  67 typedef boost::unordered_multimap<int, int, collision2_hash, std::equal_to<int>,
  68   test::allocator2<std::pair<int const, int> > >
  69   collide_map2;
  70 typedef boost::unordered_multimap<int, int, collision3_hash, std::equal_to<int>,
  71   test::allocator2<std::pair<int const, int> > >
  72   collide_map3;
  73 typedef collide_map::value_type collide_value;
  74 typedef test::list<collide_value> collide_list;
  75
  76 UNORDERED_AUTO_TEST (empty_range_tests) {
  77   collide_map x;
  78   x.erase(x.begin(), x.end());
  79   x.erase(x.begin(), x.begin());
  80   x.erase(x.end(), x.end());
  81   test::check_equivalent_keys(x);
  82 }
  83
  84 UNORDERED_AUTO_TEST (single_item_tests) {
  85   collide_list init;
  86   init.push_back(collide_value(1, 1));
  87
  88   collide_map x(init.begin(), init.end());
  89   x.erase(x.begin(), x.begin());
  90   BOOST_TEST(x.count(1) == 1 && x.size() == 1);
  91   test::check_equivalent_keys(x);
  92   x.erase(x.end(), x.end());
  93   BOOST_TEST(x.count(1) == 1 && x.size() == 1);
  94   test::check_equivalent_keys(x);
  95   x.erase(x.begin(), x.end());
  96   BOOST_TEST(x.count(1) == 0 && x.size() == 0);
  97   test::check_equivalent_keys(x);
  98 }
  99
 100 UNORDERED_AUTO_TEST (two_equivalent_item_tests) {
 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 && x.begin()->first == 1 &&
 117                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 && x.begin()->first == 1 &&
 126                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> void erase_subrange_tests(Container const& x)
 156 {
 157   for (std::size_t length = 0; length < x.size(); ++length) {
 158     for (std::size_t position = 0; position < x.size() - length; ++position) {
 159       Container y(x);
 160       collide_list init(y.begin(), y.end());
 161       if (!general_erase_range_test(y, position, position + length)) {
 162         BOOST_ERROR("general_erase_range_test failed.");
 163         BOOST_LIGHTWEIGHT_TEST_OSTREAM << "Erase: [" << position << ","
 164                                        << position + length << ")\n";
 165         write_container(init);
 166         write_container(y);
 167       }
 168     }
 169   }
 170 }
 171
 172 template <class Container>
 173 void x_by_y_erase_range_tests(Container*, int values, int duplicates)
 174 {
 175   Container y;
 176
 177   for (int i = 0; i < values; ++i) {
 178     for (int j = 0; j < duplicates; ++j) {
 179       y.insert(collide_value(i, j));
 180     }
 181   }
 182
 183   BOOST_LIGHTWEIGHT_TEST_OSTREAM << "Values: " << values
 184                                  << ", Duplicates: " << duplicates << "\n";
 185   erase_subrange_tests(y);
 186 }
 187
 188 template <class Container>
 189 void exhaustive_erase_tests(Container* x, int num_values, int num_duplicated)
 190 {
 191   for (int i = 0; i < num_values; ++i) {
 192     for (int j = 0; j < num_duplicated; ++j) {
 193       x_by_y_erase_range_tests(x, i, j);
 194     }
 195   }
 196 }
 197
 198 UNORDERED_AUTO_TEST (exhaustive_collide_tests) {
 199   BOOST_LIGHTWEIGHT_TEST_OSTREAM << "exhaustive_collide_tests:\n";
 200   collide_map m;
 201   exhaustive_erase_tests((collide_map*)0, 4, 4);
 202   BOOST_LIGHTWEIGHT_TEST_OSTREAM << "\n";
 203 }
 204
 205 UNORDERED_AUTO_TEST (exhaustive_collide2_tests) {
 206   BOOST_LIGHTWEIGHT_TEST_OSTREAM << "exhaustive_collide2_tests:\n";
 207   exhaustive_erase_tests((collide_map2*)0, 8, 4);
 208   BOOST_LIGHTWEIGHT_TEST_OSTREAM << "\n";
 209 }
 210
 211 UNORDERED_AUTO_TEST (exhaustive_collide3_tests) {
 212   BOOST_LIGHTWEIGHT_TEST_OSTREAM << "exhaustive_collide3_tests:\n";
 213   exhaustive_erase_tests((collide_map3*)0, 8, 4);
 214   BOOST_LIGHTWEIGHT_TEST_OSTREAM << "\n";
 215 }
 216
 217 RUN_TESTS()