ceph/src/boost/libs/unordered/test/unordered/erase_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 // clang-format off
   7 #include "../helpers/prefix.hpp"
   8 #include <boost/unordered_set.hpp>
   9 #include <boost/unordered_map.hpp>
  10 #include "../helpers/postfix.hpp"
  11 // clang-format on
  12
  13 #include "../helpers/test.hpp"
  14 #include "../objects/test.hpp"
  15 #include "../helpers/random_values.hpp"
  16 #include "../helpers/tracker.hpp"
  17 #include "../helpers/equivalent.hpp"
  18 #include "../helpers/helpers.hpp"
  19 #include "../helpers/invariants.hpp"
  20 #include <vector>
  21 #include <cstdlib>
  22
  23 namespace erase_tests {
  24
  25   test::seed_t initialize_seed(85638);
  26
  27   template <class Container>
  28   void erase_tests1(Container*, test::random_generator generator)
  29   {
  30     typedef BOOST_DEDUCED_TYPENAME Container::iterator iterator;
  31     typedef BOOST_DEDUCED_TYPENAME Container::const_iterator c_iterator;
  32
  33     BOOST_LIGHTWEIGHT_TEST_OSTREAM << "Erase by key.\n";
  34     {
  35       test::check_instances check_;
  36
  37       test::random_values<Container> v(1000, generator);
  38       Container x(v.begin(), v.end());
  39       int iterations = 0;
  40       for (BOOST_DEDUCED_TYPENAME test::random_values<Container>::iterator it =
  41              v.begin();
  42            it != v.end(); ++it) {
  43         std::size_t count = x.count(test::get_key<Container>(*it));
  44         std::size_t old_size = x.size();
  45         BOOST_TEST(count == x.erase(test::get_key<Container>(*it)));
  46         BOOST_TEST(x.size() == old_size - count);
  47         BOOST_TEST(x.count(test::get_key<Container>(*it)) == 0);
  48         BOOST_TEST(x.find(test::get_key<Container>(*it)) == x.end());
  49         if (++iterations % 20 == 0)
  50           test::check_equivalent_keys(x);
  51       }
  52     }
  53
  54     BOOST_LIGHTWEIGHT_TEST_OSTREAM << "erase(begin()).\n";
  55     {
  56       test::check_instances check_;
  57
  58       test::random_values<Container> v(1000, generator);
  59       Container x(v.begin(), v.end());
  60       std::size_t size = x.size();
  61       int iterations = 0;
  62       while (size > 0 && !x.empty()) {
  63         BOOST_DEDUCED_TYPENAME Container::key_type key =
  64           test::get_key<Container>(*x.begin());
  65         std::size_t count = x.count(key);
  66         iterator pos = x.erase(x.begin());
  67         --size;
  68         BOOST_TEST(pos == x.begin());
  69         BOOST_TEST(x.count(key) == count - 1);
  70         BOOST_TEST(x.size() == size);
  71         if (++iterations % 20 == 0)
  72           test::check_equivalent_keys(x);
  73       }
  74       BOOST_TEST(x.empty());
  75     }
  76
  77     BOOST_LIGHTWEIGHT_TEST_OSTREAM << "erase(random position).\n";
  78     {
  79       test::check_instances check_;
  80
  81       test::random_values<Container> v(1000, generator);
  82       Container x(v.begin(), v.end());
  83       std::size_t size = x.size();
  84       int iterations = 0;
  85       while (size > 0 && !x.empty()) {
  86         std::size_t index = test::random_value(x.size());
  87         c_iterator prev, pos, next;
  88         if (index == 0) {
  89           prev = pos = x.begin();
  90         } else {
  91           prev = test::next(x.begin(), index - 1);
  92           pos = test::next(prev);
  93         }
  94         next = test::next(pos);
  95         BOOST_DEDUCED_TYPENAME Container::key_type key =
  96           test::get_key<Container>(*pos);
  97         std::size_t count = x.count(key);
  98         BOOST_TEST(count > 0);
  99         BOOST_TEST(next == x.erase(pos));
 100         --size;
 101         if (size > 0)
 102           BOOST_TEST(index == 0 ? next == x.begin() : next == test::next(prev));
 103         BOOST_TEST(x.count(key) == count - 1);
 104         if (x.count(key) != count - 1) {
 105           BOOST_LIGHTWEIGHT_TEST_OSTREAM << count << " => " << x.count(key)
 106                                          << std::endl;
 107         }
 108         BOOST_TEST(x.size() == size);
 109         if (++iterations % 20 == 0)
 110           test::check_equivalent_keys(x);
 111       }
 112       BOOST_TEST(x.empty());
 113     }
 114
 115     BOOST_LIGHTWEIGHT_TEST_OSTREAM << "erase(ranges).\n";
 116     {
 117       test::check_instances check_;
 118
 119       test::random_values<Container> v(500, generator);
 120       Container x(v.begin(), v.end());
 121
 122       std::size_t size = x.size();
 123
 124       // I'm actually stretching it a little here, as the standard says it
 125       // returns 'the iterator immediately following the erase elements'
 126       // and if nothing is erased, then there's nothing to follow. But I
 127       // think this is the only sensible option...
 128       BOOST_TEST(x.erase(x.end(), x.end()) == x.end());
 129       BOOST_TEST(x.erase(x.begin(), x.begin()) == x.begin());
 130       BOOST_TEST(x.size() == size);
 131       test::check_equivalent_keys(x);
 132
 133       BOOST_TEST(x.erase(x.begin(), x.end()) == x.end());
 134       BOOST_TEST(x.empty());
 135       BOOST_TEST(x.begin() == x.end());
 136       test::check_equivalent_keys(x);
 137
 138       BOOST_TEST(x.erase(x.begin(), x.end()) == x.begin());
 139       test::check_equivalent_keys(x);
 140     }
 141
 142     BOOST_LIGHTWEIGHT_TEST_OSTREAM << "erase(random ranges).\n";
 143     {
 144       test::check_instances check_;
 145       Container x;
 146
 147       for (int i = 0; i < 100; ++i) {
 148         test::random_values<Container> v(1000, generator);
 149         x.insert(v.begin(), v.end());
 150
 151         // Note that erase only invalidates the erased iterators.
 152         std::vector<c_iterator> iterators;
 153         for (c_iterator it = x.cbegin(); it != x.cend(); ++it) {
 154           iterators.push_back(it);
 155         }
 156         iterators.push_back(x.cend());
 157
 158         while (iterators.size() > 1) {
 159           std::size_t start = test::random_value(iterators.size());
 160           std::size_t length = test::random_value(iterators.size() - start);
 161           x.erase(iterators[start], iterators[start + length]);
 162           iterators.erase(test::next(iterators.begin(), start),
 163             test::next(iterators.begin(), start + length));
 164
 165           BOOST_TEST(x.size() == iterators.size() - 1);
 166           BOOST_DEDUCED_TYPENAME std::vector<c_iterator>::const_iterator i2 =
 167             iterators.begin();
 168           for (c_iterator i1 = x.cbegin(); i1 != x.cend(); ++i1) {
 169             BOOST_TEST(i1 == *i2);
 170             ++i2;
 171           }
 172           BOOST_TEST(x.cend() == *i2);
 173
 174           test::check_equivalent_keys(x);
 175         }
 176         BOOST_TEST(x.empty());
 177       }
 178     }
 179
 180     BOOST_LIGHTWEIGHT_TEST_OSTREAM << "quick_erase(begin()).\n";
 181     {
 182       test::check_instances check_;
 183
 184       test::random_values<Container> v(1000, generator);
 185       Container x(v.begin(), v.end());
 186       std::size_t size = x.size();
 187       int iterations = 0;
 188       while (size > 0 && !x.empty()) {
 189         BOOST_DEDUCED_TYPENAME Container::key_type key =
 190           test::get_key<Container>(*x.begin());
 191         std::size_t count = x.count(key);
 192         x.quick_erase(x.begin());
 193         --size;
 194         BOOST_TEST(x.count(key) == count - 1);
 195         BOOST_TEST(x.size() == size);
 196         if (++iterations % 20 == 0)
 197           test::check_equivalent_keys(x);
 198       }
 199       BOOST_TEST(x.empty());
 200     }
 201
 202     BOOST_LIGHTWEIGHT_TEST_OSTREAM << "quick_erase(random position).\n";
 203     {
 204       test::check_instances check_;
 205
 206       test::random_values<Container> v(1000, generator);
 207       Container x(v.begin(), v.end());
 208       std::size_t size = x.size();
 209       int iterations = 0;
 210       while (size > 0 && !x.empty()) {
 211         std::size_t index = test::random_value(x.size());
 212         BOOST_DEDUCED_TYPENAME Container::const_iterator prev, pos, next;
 213         if (index == 0) {
 214           prev = pos = x.begin();
 215         } else {
 216           prev = test::next(x.begin(), index - 1);
 217           pos = test::next(prev);
 218         }
 219         next = test::next(pos);
 220         BOOST_DEDUCED_TYPENAME Container::key_type key =
 221           test::get_key<Container>(*pos);
 222         std::size_t count = x.count(key);
 223         BOOST_TEST(count > 0);
 224         x.quick_erase(pos);
 225         --size;
 226         if (size > 0)
 227           BOOST_TEST(index == 0 ? next == x.begin() : next == test::next(prev));
 228         BOOST_TEST(x.count(key) == count - 1);
 229         if (x.count(key) != count - 1) {
 230           BOOST_LIGHTWEIGHT_TEST_OSTREAM << count << " => " << x.count(key)
 231                                          << std::endl;
 232         }
 233         BOOST_TEST(x.size() == size);
 234         if (++iterations % 20 == 0)
 235           test::check_equivalent_keys(x);
 236       }
 237       BOOST_TEST(x.empty());
 238     }
 239
 240     BOOST_LIGHTWEIGHT_TEST_OSTREAM << "clear().\n";
 241     {
 242       test::check_instances check_;
 243
 244       test::random_values<Container> v(500, generator);
 245       Container x(v.begin(), v.end());
 246       x.clear();
 247       BOOST_TEST(x.empty());
 248       BOOST_TEST(x.begin() == x.end());
 249     }
 250
 251     BOOST_LIGHTWEIGHT_TEST_OSTREAM << "\n";
 252   }
 253
 254   boost::unordered_set<test::object, test::hash, test::equal_to,
 255     test::allocator1<test::object> >* test_set;
 256   boost::unordered_multiset<test::object, test::hash, test::equal_to,
 257     test::allocator2<test::object> >* test_multiset;
 258   boost::unordered_map<test::object, test::object, test::hash, test::equal_to,
 259     test::allocator1<test::object> >* test_map;
 260   boost::unordered_multimap<test::object, test::object, test::hash,
 261     test::equal_to, test::allocator2<test::object> >* test_multimap;
 262
 263   using test::default_generator;
 264   using test::generate_collisions;
 265   using test::limited_range;
 266
 267   UNORDERED_TEST(
 268     erase_tests1, ((test_set)(test_multiset)(test_map)(test_multimap))(
 269                     (default_generator)(generate_collisions)(limited_range)))
 270 }
 271
 272 RUN_TESTS()